Comprehensive isomorphic subtree enumeration

ABSTRACT

A fundamental problem in program analysis and optimization concerns the discovery of structural similarities between different sections of a given program and/or across different programs. Specifically, there is a need to find topologically identical segments within compiler intermediate representations (IRs).

Such topological isomorphism has many applications. For example, finding isomorphic sub-trees within different expression trees points to common computational resources that can be shared when targeting application-specific hardware. Isomorphism in the controlflow graph can be used to discovery of custom instructions for customizable processors. Discovering isomorphism in context call trees during program execution is invaluable to several JIT compiler optimizations. Thus, all these different applications rely on the fundamental ability to find topologically identical segments within a given tree or graph representation.

In this paper, we present a generic formulation of the subtree isomorphism problem that is more powerful than previous proposals. We prove that an optimal quadratic time solution exists for this problem. We employ a dynamic programming based algorithm to efficiently enumerate all isomorphic sub-trees within given reference trees and also demonstrate its efficacy in a production compiler.

REFERENCES

• 1: A. V. Aho , S. C. Johnson , J. D. Ullman, Code generation for expressions with common subexpressions (Extended Abstract), Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.19-31, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811537]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Satamoto, and S. Arikawa. Efficient substructure discovery from large semi-structured data. In SIAM Int. Conf. on Data Mining, Arlington, VA, 2002.
• 5: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 6: Samuel R. Buss, Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization, Proceedings of the 5th Kurt Gödel Colloquium on Computational Logic and Proof Theory, p.18-33, August 25-29, 1997
• 7: Yun Chi , Richard R. Muntz , Siegfried Nijssen , Joost N. Kok, Frequent Subtree Mining - An Overview, Fundamenta Informaticae, v.66 n.1-2, p.161-198, November 2004
• 8: Jason Cong , Wei Jiang, Pattern-based behavior synthesis for FPGA resource reduction, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344688]
• 9: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• 10: K. Keutzer, DAGON: Technology binding and local optimization by DAG matching, Papers on Twenty-five years of electronic design automation, p.617-624, June 1988 [doi>10.1145/62882.62957]
• 11: Pekka Kilpelainen , Heikki Mannila, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing, v.24 n.2, p.340-356, April 1995 [doi>10.1137/S0097539791218202]
• 12: T. Kim, N. Yonezawa, J.W.S. Liu, and C.L. Liu. A scheduling algorithm for conditional resource sharing - a hierarchical reduction approach. IEEE TCAD, 13(4):425--438, 1994.
• 13: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 14: R. Shamir , D. Tsur, Faster subtree isomorphism, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.126, June 17-19, 1997
• 15: Gabriel Valiente, Algorithms on Trees and Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 16: Yun Chi , Yi Xia , Yirong Yang , Richard R. Muntz, Mining Closed and Maximal Frequent Subtrees from Databases of Labeled Rooted Trees, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.190-202, February 2005 [doi>10.1109/TKDE.2005.30]
• 17: Xiaotong Zhuang , Suhyun Kim , Mauri io Serrano , Jong-Deok Choi, Perfdiff: a framework for performance difference analysis in a virtual machine environment, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA [doi>10.1145/1356058.1356060]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design

Keywords:
embedded systems, subtree isomorphism, subtree matching algorithm