Loop passes (indvars) do not simplify the CFG before other loop passes run (loop-deletion).

[dotdash]

Bugzilla Link	18449
Version	unspecified
OS	Linux
CC	@atrick,@hfinkel

Extended Description

Given this code:

; ModuleID = '<stdin>'

define void @&#8203;test() {
"function top level":
  br label %loop

loop:                                             ; preds = %body, %"function top level"
  %0 = phi i64 [ 0, %"function top level" ], [ %2, %body ]
  %1 = icmp ugt i64 %0, 2
  br i1 %1, label %fail, label %body

fail:                                             ; preds = %loop
  tail call void @&#8203;bounds_fail()
  unreachable

body:                                             ; preds = %loop
  %2 = add i64 %0, 1
  %3 = icmp slt i64 %2, 3
  br i1 %3, label %loop, label %out

out:                                              ; preds = %body
  ret void
}

declare void @&#8203;bounds_fail()

opt from LLVM 3.2 was able to optimize that to:

; ModuleID = '<stdin>'

define void @&#8203;test() {
body.2:
  ret void
}

But opt from LLVM 3.3, 3.4 and 3.5~svn197556-1 (from Debian Sid) fail to do so and leave the code unchanged.

This is from rust issue rust-lang/rust#9024

[llvmbot]

This is a result of the fixes from #16505 (http://llvm.org/bugs/show_bug.cgi?id=16130). In particular, r183060. Andy mentioned something about revisiting the trip count computation, but I am not sure if this case falls into that bucket.

[atrick]

The issue with -indvars failing to remove the first branch (%1 = icmp ugt) is fixed in r199299.

However, the dead loop is not actually deleted with -O2. This looks like an accident of phase ordering. It's a separate issue. If we run -indvars -simplifycfg -loop-deletionm then all is well. However, indvars/loop-deletion are in the same loop pass manager and I don't know how to simplify CFG in between. (I'm not sure how 3.2 handled it).

[llvmbot]

opt from trunk gives this for the IR

; ModuleID = 'test.ll'

define void @​test() {
"function top level":
br label %body

body: ; preds = %"function top level"
ret void
}

it is still leaving one branch instruction but no dead loop.

[atrick]

There's no problem with the generated code. But it is odd that the fall-thru branch is not removed at IR level. It's not removed until we run "Control Flow Optimizer" after regalloc. The reason is that we don't run SimplifyCFG after the last LoopUnroll Pass. Full unrolling should generally be done early, but in this case we need IVsimplify and instcombine to run first: IndVarsimplify->InstCombine->Unroll

I related this to: Bug 17809 - Reordering IR-level optimization passes.

Another issue that that we should be able to delete the loop even if we don't unroll it. The problem here is that SimplifyCFG is not after IndVars and before other loop opts like LoopDeletion.

I'll claim that the solution is to bring enough SimplifyCFG utility to the loop passes so that can clean up after themselves. In this case, if indvars creates a branch-on-constant, it should run enough of SimplifyCFG on the branch's block to remove the branch.

[llvmbot]

I got the point and it make sense to re-order IR optimization pipeline.

It is also interesting to update loop passes to produce clean code by using simplifyCFG and other utility. Can we take up this activity or it needs approval from the community first.

As you have already mentioned, delete loop pass was not able to delete loop because of multiple (2) exits ni the loop even though only one of them is valid.

Can't we teach indvars to change branch to unconditional branch in place of creating branch on constant. I tried setting both successor of bransh instruction same and now delete loop pass was able to delete that loop. But I am not sure if transform like it is in scope of indvars.

[atrick]

Yes, I think IndVars should convert the branch on-the-spot. I was hoping to reuse some logic from SimplifyCFG to do this to avoid adding any new logic to indvars. However, I don't see an obvious way to factor it and it's not hard to just create the unconditional branch and add the old branch to DeadInsts.

[rotateright]

mentioned in issue llvm/llvm-bugzilla-archive#19799