[IndVars] Strengthen restricton in rewriteLoopExitValues

[mkazantsev]

Summary

For some unclear reason rewriteLoopExitValues considers recalculation
after the loop profitable if it has some "soft uses" outside the loop (i.e. any
use other than call and return), even if we have proved that it has a user inside
the loop which we think will not be optimized away.

There is no existing unit test that would explain this. This patch provides an
example when rematerialisation of exit value is not profitable but it passes
this check due to presence of a "soft use" outside the loop.

It makes no sense to recalculate value on exit if we are going to compute it
due to some irremovable within the loop. This patch disallows applying this
transform in the described situation.

[mkazantsev]

Rebased.

[etherzhhb]

For some unclear reason rewriteLoopExitValues considers recalculation
after the loop profitable if it has some "soft uses" outside the loop (i.e. any
use other than call and return), even if we have proved that it has a user inside
the loop which we think will not be optimized away.

This also confuse me. Why it must be "soft uses" outside the loop that matter?
What I can guess is that, if there is no use outside, there is *no need* to rewrite the exit value.

lib/Transforms/Scalar/IndVarSimplify.cpp

601–602 ↗

(On Diff #165893)

looks like these comments describe the scenario of "SoftExternalUses", do we need to delete this as we deleted the corresponding code?

605–615 ↗

(On Diff #165893)

we can further write:

// Skip if  Inst is used inside the loop in a way which can not be
//    optimized away.
if (llvm::any_of(Inst->users(), [L](auto *U) {
  return isa<CallInst>(UseInstr) && L->contains(UseInstr);
}))
  continue;

which is easier to read

607–608 ↗

(On Diff #165893)

since opc is used only once now, maybe we could write:

if (isa<CallInst>(UseInstr) && L->contains(UseInstr)) {

Also, how about invoke?

[etherzhhb]

lib/Transforms/Scalar/IndVarSimplify.cpp

605–615 ↗

(On Diff #165893)

I forgot there is a follow up patch to rewrite this :)

You could decide if you want to rewrite the loop or leave it to the next patch

607–608 ↗

(On Diff #165893)

I think the invoke is addressed in the follow up patch

[mkazantsev]

Fixed comment. All style rework can be done in follow-up, provided that the dependent pass is going to isolate this code into a separate method.

[mkazantsev]

lib/Transforms/Scalar/IndVarSimplify.cpp

605–615 ↗

(On Diff #165893)

Better to do it in a follow-up too. :)

607–608 ↗

(On Diff #165893)

Yes, it's better to do it in a follow-up.

[etherzhhb]

Sorry for the delay. I think since most of the suggested changes are actually in a follow up patch. LGTM

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
         // Okay, this instruction has a user outside of the current loop
         // and varies predictably *inside* the loop.  Evaluate the value it
         // contains when the loop exits, if possible.
         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
         if (!SE->isLoopInvariant(ExitValue, L) ||
             !isSafeToExpand(ExitValue, *SE))
           continue;
 
-        // Computing the value outside of the loop brings no benefit if :
-        //  - it is definitely used inside the loop in a way which can not be
-        //    optimized away.
-        //  - no use outside of the loop can take advantage of hoisting the
-        //    computation out of the loop
+        // Computing the value outside of the loop brings no benefit if it is
+        // definitely used inside the loop in a way which can not be optimized
+        // away.
         if (ExitValue->getSCEVType()>=scMulExpr) {
           bool HasHardInternalUses = false;
-          bool HasSoftExternalUses = false;
           for (auto *IB : Inst->users()) {
             Instruction *UseInstr = cast<Instruction>(IB);
             unsigned Opc = UseInstr->getOpcode();
-            if (L->contains(UseInstr)) {
-              if (Opc == Instruction::Call)
-                HasHardInternalUses = true;
-            } else {
-              if (Opc == Instruction::PHI) {
-                // Do not count the Phi as a use. LCSSA may have inserted
-                // plenty of trivial ones.
-                for (auto *PB : UseInstr->users()) {
-                  unsigned PhiOpc = cast<Instruction>(PB)->getOpcode();
-                  if (PhiOpc != Instruction::Call &&
-                      PhiOpc != Instruction::Ret) {
-                    HasSoftExternalUses = true;
-                    break;
-                  }
-                }
-                continue;
-              }
-              if (Opc != Instruction::Call && Opc != Instruction::Ret) {
-                HasSoftExternalUses = true;
-                break;
-              }
-            }
-          }
-          if (HasHardInternalUses && !HasSoftExternalUses)
+            if (L->contains(UseInstr) && Opc == Instruction::Call) {
+          if (HasHardInternalUses)
             continue;
         }
 
         bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
         Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
 
         LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
                           << '\n'

llvm/trunk/test/Transforms/IndVarSimplify/dont-recompute.ll

 for.end:                                          ; preds = %for.body
 ; CHECK: for.end:
 ; CHECK-NOT: mul i32 %m, 186
 ; CHECK:%add.lcssa = phi i32 [ %add, %for.body ]
 ; CHECK-NEXT: tail call void @func(i32 %add.lcssa)
   tail call void @func(i32 %add)
   ret void
 }
+
+; CHECK-LABEL: @test4(
+define void @test4(i32 %m) nounwind uwtable {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %a.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %add = add i32 %a.05, %m
+; CHECK: tail call void @func(i32 %add)
+  tail call void @func(i32 %add)
+  %inc = add nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 186
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+; CHECK: for.end:
+; CHECK-NOT: mul i32 %m, 186
+; CHECK:%add.lcssa = phi i32 [ %add, %for.body ]
+; CHECK-NEXT: %soft_use = add i32 %add.lcssa, 123
+; CHECK-NEXT: tail call void @func(i32 %soft_use)
+  %soft_use = add i32 %add, 123
+  tail call void @func(i32 %soft_use)
+  ret void
+}