Page MenuHomePhabricator

[SimplifyCFG] Fix for "endless" loop after dead code removal (Alternative to D16251)

Authored by Gerolf on Feb 2 2016, 8:38 PM.



This is a simpler fix to the problem than the dominator approach in It adds only values into the gather() while loop
that have been seen before.

The actual endless loop is in the constant compare gather() routine in
Utils/SimplifyCFG.cpp. The same value ret.0.off0.i is pushed back into the
%.ret.0.off0.i = or i1 %.ret.0.off0.i, %cmp10.i

Here is what happens at the IR level:

for.cond.i: ; preds = %if.end6.i,
%ix.0.i = phi i32 [ 0, %if.end.i54 ], [ %inc.i55, %if.end6.i ]
%ret.0.off0.i = phi i1 [false, %if.end.i54], [%.ret.0.off0.i, %if.end6.i] <<<
%cmp2.i = icmp ult i32 %ix.0.i, %11
br i1 %cmp2.i, label %for.body.i, label %LBJ_TmpSimpleNeedExt.exit

if.end6.i: ; preds = %for.body.i
%cmp10.i = icmp ugt i32 %conv.i, %add9.i
%.ret.0.off0.i = or i1 %ret.0.off0.i, %cmp10.i <<<

When if.end.i54 gets eliminated which removes the definition of ret.0.off0.i.
The result is the expression %.ret.0.off0.i = or i1 %.ret.0.off0.i, %cmp10.i
(Note the first ‘or’ operand is now %.ret.0.off0.i, and *NOT* %ret.0.off0.i).
now there is use of .ret.0.off0.i before a definition which triggers the
“endless” loop in gather():

while(!DFT.empty()) {

V = DFT.pop_back_val();   // V is .ret.0.off0.i

if (Instruction *I = dyn_cast<Instruction>(V)) {
  // If it is a || (or && depending on isEQ), process the operands.
  if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) {
    DFT.push_back(I->getOperand(1));  // This is now .ret.0.off0.i also

    continue; // “endless loop” for .ret.0.off0.i

Diff Detail

Event Timeline

Gerolf updated this revision to Diff 46736.Feb 2 2016, 8:38 PM
Gerolf retitled this revision from to [SimplifyCFG] Fix for "endless" loop after dead code removal (Alternative to D16251).
Gerolf updated this object.
Gerolf added reviewers: reames, ahatanak.
Gerolf added a subscriber: llvm-commits.
ahatanak accepted this revision.Feb 3 2016, 9:22 AM
ahatanak edited edge metadata.

LGTM with a few nits.


You can just insert the value without checking the boolean value (the boolean value should always be true here).


Can this test be smaller?

This revision is now accepted and ready to land.Feb 3 2016, 9:22 AM
Gerolf marked an inline comment as done.Feb 3 2016, 3:57 PM

Thank you, Akira!


Reduced it by another ~30% to about fairly simple lines.

Gerolf closed this revision.Feb 3 2016, 3:58 PM