Page MenuHomePhabricator

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

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

Details

Summary

This is a simpler fix to the problem than the dominator approach in
http://reviews.llvm.org/D16251. 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
queue:
%.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,
%if.end.i54
%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).
And
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
    DFT.push_back(I->getOperand(0));

    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.

lib/Transforms/Utils/SimplifyCFG.cpp
514

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

test/Transforms/SimplifyCFG/InfLoop.ll
171

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!

test/Transforms/SimplifyCFG/InfLoop.ll
171

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

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