@article{oai:ipsj.ixsq.nii.ac.jp:00227249,
 author = {Yuya, Yanase and Yasunobu, Sumikawa and Yuya, Yanase and Yasunobu, Sumikawa},
 issue = {8},
 journal = {情報処理学会論文誌},
 month = {Aug},
 note = {Partial redundancy elimination (PRE) is a code optimization algorithm that simultaneously performs common sub-expression elimination and loop-invariant code motion. Traditional PREs analyze the entire program and eliminate redundancies. By contrast, demand-driven PRE (DDPRRE) is proposed as an algorithm to analyze only a part of the program to determine whether each expression is redundant by query propagation. The previous DDPRE reduces the analysis time because it limits the analysis range; however, it is known that redundancy may not be eliminated when the nodes in the loop are revisited. We propose a novel DDPRE, named lazy demand-driven PRE (LDPRE), which eliminates redundancy by delaying the decision of whether the analyzing expression is redundant or not when a node in a loop is revisited and redundancy cannot be analyzed. LDPRE uses a semi-lattice as the answer space during the query propagation. The semi-lattice includes not only true/false implying that the queried expression is redundant or not, but also top for undecidability. While maintaining the analytical efficiency characteristic of demand-driven analysis, our algorithm eliminates redundancy that previous DDPRE could not eliminate by determining the answer using semi-lattice.
------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.31(2023) (online)
DOI　http://dx.doi.org/10.2197/ipsjjip.31.459
------------------------------, Partial redundancy elimination (PRE) is a code optimization algorithm that simultaneously performs common sub-expression elimination and loop-invariant code motion. Traditional PREs analyze the entire program and eliminate redundancies. By contrast, demand-driven PRE (DDPRRE) is proposed as an algorithm to analyze only a part of the program to determine whether each expression is redundant by query propagation. The previous DDPRE reduces the analysis time because it limits the analysis range; however, it is known that redundancy may not be eliminated when the nodes in the loop are revisited. We propose a novel DDPRE, named lazy demand-driven PRE (LDPRE), which eliminates redundancy by delaying the decision of whether the analyzing expression is redundant or not when a node in a loop is revisited and redundancy cannot be analyzed. LDPRE uses a semi-lattice as the answer space during the query propagation. The semi-lattice includes not only true/false implying that the queried expression is redundant or not, but also top for undecidability. While maintaining the analytical efficiency characteristic of demand-driven analysis, our algorithm eliminates redundancy that previous DDPRE could not eliminate by determining the answer using semi-lattice.
------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.31(2023) (online)
DOI　http://dx.doi.org/10.2197/ipsjjip.31.459
------------------------------},
 title = {Lazy Demand-driven Partial Redundancy Elimination},
 volume = {64},
 year = {2023}
}