Page MenuHomePhabricator

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Authored by chenli on Jan 25 2016, 10:01 PM.



This is a revised version of D13974, and the following quoted summary are from D13974

"This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch."

D13974 was committed but failed one lnt test. The bug was that we only checked the condition from loop exit's incoming block was a loop invariant. But there could be another condition from loop header to that incoming block not being a loop invariant. This would produce miscompiled code.

This patch fixes the issue by checking if the incoming block is loop header, and if not, don't perform the rewrite. The could be further improved by recursively checking all conditions leading to loop exit block, but I'd like to check in this simple version first and improve it with future patches.

Diff Detail

Event Timeline

chenli retitled this revision from to [IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader.
chenli updated this object.
chenli added a reviewer: sanjoy.
chenli added a subscriber: llvm-commits.

The original diff file was from D13974 for the purpose of comparison. This is the updated diff file.


This is the fix to the problem mentioned in summary.

sanjoy accepted this revision.Jan 26 2016, 9:26 PM
sanjoy edited edge metadata.

lgtm with minor nits inline


Nit: LLVM style is BasicBlock::iterator BBI = ExitBB->begin(); or BasicBlock::iterator Begin = ExitBB->begin();


I don't think you have to special case this -- isLoopInvariant takes a Value * and returns true for non instructions.


Since you're calling getBasicBlockIndex, why not save the index and re-use it here?

This revision is now accepted and ready to land.Jan 26 2016, 9:26 PM
chenli updated this object.Jan 26 2016, 9:58 PM
chenli edited edge metadata.
chenli closed this revision.Jan 26 2016, 11:44 PM