Delayed Reduction Algorithms of DJ Graph using Path Compression


The KIPS Transactions:PartA, Vol. 9, No. 2, pp. 171-180, Jun. 2002
10.3745/KIPSTA.2002.9.2.171,   PDF Download:

Abstract

The effective and accurate data flow problem analysis uses the dominator tree and DJ graphs. The data flow problem solving is to safely reduce the flow graph to the dominator tree. The flow graph replaces a parse tree and used to accurately reduce either reducible or irreducible flow graph to the dominator tree. In this paper, in order to utilize Tarjan''s path compress algorithm, the Top node finding algorithm is suggested and the existing delay reduction algorithm is improved using path compression. The delayed reduction algorithm using path compression actually compresses the pathway of the dominator tree by hoisting the node while reducing to delay the DJ graph. Really, the suggested algorithm had hoisted nodes in 22% and had compressed path in 20%. The compressed dominator tree makes it possible to analyze the effective data flow analysis and brings the improved effect for the complexity of code optimization process with the node hoisting effect of code optimization process.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. K. Sim and H. H. Ahn, "Delayed Reduction Algorithms of DJ Graph using Path Compression," The KIPS Transactions:PartA, vol. 9, no. 2, pp. 171-180, 2002. DOI: 10.3745/KIPSTA.2002.9.2.171.

[ACM Style]
Son Kweon Sim and Heui Hak Ahn. 2002. Delayed Reduction Algorithms of DJ Graph using Path Compression. The KIPS Transactions:PartA, 9, 2, (2002), 171-180. DOI: 10.3745/KIPSTA.2002.9.2.171.