[IndVars] Smart hard uses detection

[mkazantsev]

Summary

When rewriting loop exit values, IndVars considers this transform not profitable if
the loop instruction has a loop user which it believes cannot be optimized away.
In current implementation only calls that immediately use the instruction are considered
as such.

This patch extends the definition of "hard" users to any side-effecting instructions
(which usually cannot be optimized away from the loop) and also allows handling
of not just immediate users, but use chains.

[etherzhhb]

lib/Transforms/Scalar/IndVarSimplify.cpp

557–558

we may also stop and return true if Curr is a phi node, since phi nodes cannot be eliminated easily.

But we need to be careful that:

define void @test6(i32 %m, i32* %p) 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 ]
  %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
  tail call void @func(i32 %inc)
  ret void
}

In this case we still what to rewrite %inc outside of the loop to a constant. (or it is handle by the other part of this pass?)

[etherzhhb]

LGTM, but this patch may add a negligible increment on LLVM's compile time. Make sure you talk to some people that care about the LLVM compile time for their opinions

[mkazantsev]

lib/Transforms/Scalar/IndVarSimplify.cpp

557–558

I guess constant values are always profitable to rewrite and don't need to pass through hard uses check. I'll take a look how exactly it's handled. It should not go on this check anyways.

[mkazantsev]

https://reviews.llvm.org/rL345814

[cfang]

I am working on a regression caused by this patch. It is a memory access fault actually.
However, if we put back the original consition, my test would pass.

Could you explain why the original condition was removed in your patch?

+if (ExitValue->getSCEVType()>=scMulExpr) {

if (!isa<SCEVConstant>(ExitValue) && hasHardUserWithinLoop(L, Inst))
  continue;

+ }

[dendibakh]

I also found performance regression as a result of this commit:
http://lists.llvm.org/pipermail/llvm-dev/2019-March/131308.html

lib/Transforms/Scalar/IndVarSimplify.cpp

#endif
 
   void handleFloatingPointIV(Loop *L, PHINode *PH);
   void rewriteNonIntegerIVs(Loop *L);
 
   void simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
 
   bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
   void rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
+  bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) const;
   void rewriteFirstIterationLoopExitValues(Loop *L);
 
   Value *linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
                                    PHINode *IndVar, SCEVExpander &Rewriter);
 
   void sinkUnusedInvariants(Loop *L);
 
   Value *expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S, Loop *L,
Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
   return Rewriter.expandCodeFor(S, ResultTy, InsertPt);
 }
 
 //===----------------------------------------------------------------------===//
 // rewriteLoopExitValues - Optimize IV users outside the loop.
 // As a side effect, reduces the amount of IV processing within the loop.
 //===----------------------------------------------------------------------===//
 
+bool IndVarSimplify::hasHardUserWithinLoop(const Loop *L, const Instruction *I) const {
+  SmallPtrSet<const Instruction *, 8> Visited;
+  SmallVector<const Instruction *, 8> WorkList;
+  Visited.insert(I);
+  WorkList.push_back(I);
+  while (!WorkList.empty()) {
+    const Instruction *Curr = WorkList.pop_back_val();
+    // This use is outside the loop, nothing to do.
+    if (!L->contains(Curr))
+      continue;
+    // Do we assume it is a "hard" use which will not be eliminated easily?
+    if (Curr->mayHaveSideEffects())
+      return true;
+    // Otherwise, add all its users to worklist.
+    for (auto U : Curr->users()) {
+      auto *UI = cast<Instruction>(U);
+      if (Visited.insert(UI).second)
+        WorkList.push_back(UI);
+    }
+  }
+  return false;
+}
+
 /// Check to see if this loop has a computable loop-invariant execution count.
 /// If so, this means that we can compute the final value of any expressions
 /// that are recurrent in the loop, and substitute the exit values from the loop
 /// into any instructions outside of the loop that use the final values of the
 /// current expressions.
 ///
 /// This is mostly redundant with the regular IndVarSimplify activities that
 /// happen later, except that it's more powerful in some cases, because it's
while ((PN = dyn_cast<PHINode>(BBI++))) {
         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.
-        if (ExitValue->getSCEVType()>=scMulExpr) {
-          bool HasHardInternalUses = false;
-          for (auto *IB : Inst->users()) {
-            Instruction *UseInstr = cast<Instruction>(IB);
-            unsigned Opc = UseInstr->getOpcode();
-            if (L->contains(UseInstr) && Opc == Instruction::Call) {
-              HasHardInternalUses = true;
-              break;
-            }
-          }
-          if (HasHardInternalUses)
-            continue;
-        }
+        if (hasHardUserWithinLoop(L, Inst))
 
         bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
         Value *ExitVal =
             expandSCEVIfNeeded(Rewriter, ExitValue, L, Inst, PN->getType());
 
         LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
                           << '\n'
                           << "  LoopVal = " << *Inst << "\n");

test/Analysis/ScalarEvolution/pr28705.ll

 ; PR28705
 ; RUN: opt < %s -indvars -S | FileCheck %s
 
-; Check IndVarSimplify replaces the exitval use of the induction var "%inc.i.i"
-; with "%.sroa.speculated + 1".
+; Check IndVarSimplify doesn't replace external use of the induction var
+; "%inc.i.i" with "%.sroa.speculated + 1" because it is not profitable.
 ;
 ; CHECK-LABEL: @foo(
-; CHECK: %[[EXIT:.+]] = sub i32 %.sroa.speculated, -1
+; CHECK: %[[EXIT:.+]] = phi i32 [ %inc.i.i, %for.body650 ]
 ; CHECK: %DB.sroa.9.0.lcssa = phi i32 [ 1, %entry ], [ %[[EXIT]], %loopexit ]
 ;
 define void @foo(i32 %sub.ptr.div.i, i8* %ref.i1174) local_unnamed_addr {
 entry:
   %cmp.i1137 = icmp ugt i32 %sub.ptr.div.i, 3
   %.sroa.speculated = select i1 %cmp.i1137, i32 3, i32 %sub.ptr.div.i
   %cmp6483126 = icmp eq i32 %.sroa.speculated, 0
   br i1 %cmp6483126, label %XZ.exit, label %for.body650.lr.ph

test/Transforms/IndVarSimplify/dont-recompute.ll

 ; 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
 }
+
+; CHECK-LABEL: @test5(
+define void @test5(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
+  %soft_use = add i32 %add, 123
+; CHECK: tail call void @func(i32 %soft_use)
+  tail call void @func(i32 %soft_use)
+  %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: tail call void @func(i32 %add.lcssa)
+  tail call void @func(i32 %add)
+  ret void
+}
+
+; CHECK-LABEL: @test6(
+define void @test6(i32 %m, i32* %p) 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
+  %soft_use = add i32 %add, 123
+; CHECK: store i32 %soft_use, i32* %pidx
+  %pidx = getelementptr i32, i32* %p, i32 %add
+  store i32 %soft_use, i32* %pidx
+  %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: tail call void @func(i32 %add.lcssa)
+  tail call void @func(i32 %add)
+  ret void
+}

test/Transforms/IndVarSimplify/lrev-existing-umin.ll

 ; RUN: opt -S -indvars < %s | FileCheck %s
 
+; Do not rewrite the user outside the loop because we must keep the instruction
+; inside the loop due to store. Rewrite doesn't give us any profit.
 define void @f(i32 %length.i.88, i32 %length.i, i8* %tmp12, i32 %tmp10, i8* %tmp8) {
 ; CHECK-LABEL: @f(
 not_zero11.preheader:
   %tmp13 = icmp ugt i32 %length.i, %length.i.88
   %tmp14 = select i1 %tmp13, i32 %length.i.88, i32 %length.i
   %tmp15 = icmp sgt i32 %tmp14, 0
   br i1 %tmp15, label %not_zero11, label %not_zero11.postloop
 
 not_zero11:
   %v_1 = phi i32 [ %tmp22, %not_zero11 ], [ 0, %not_zero11.preheader ]
   %tmp16 = zext i32 %v_1 to i64
   %tmp17 = getelementptr inbounds i8, i8* %tmp8, i64 %tmp16
   %tmp18 = load i8, i8* %tmp17, align 1
   %tmp19 = zext i8 %tmp18 to i32
   %tmp20 = or i32 %tmp19, %tmp10
   %tmp21 = trunc i32 %tmp20 to i8
   %addr22 = getelementptr inbounds i8, i8* %tmp12, i64 %tmp16
   store i8 %tmp21, i8* %addr22, align 1
   %tmp22 = add nuw nsw i32 %v_1, 1
   %tmp23 = icmp slt i32 %tmp22, %tmp14
   br i1 %tmp23, label %not_zero11, label %main.exit.selector
 
 main.exit.selector:
 ; CHECK-LABEL: main.exit.selector:
+; CHECK:   %tmp22.lcssa = phi i32 [ %tmp22, %not_zero11 ]
+; CHECK:   %tmp24 = icmp slt i32 %tmp22.lcssa, %length.
+  %tmp24 = icmp slt i32 %tmp22, %length.i
+  br i1 %tmp24, label %not_zero11.postloop, label %leave
+
+leave:
+  ret void
+
+not_zero11.postloop:
+  ret void
+}
+
+; Rewrite the user outside the loop because there is no hard users inside the loop.
+define void @f1(i32 %length.i.88, i32 %length.i, i8* %tmp12, i32 %tmp10, i8* %tmp8) {
+; CHECK-LABEL: @f1(
+not_zero11.preheader:
+  %tmp13 = icmp ugt i32 %length.i, %length.i.88
+  %tmp14 = select i1 %tmp13, i32 %length.i.88, i32 %length.i
+  %tmp15 = icmp sgt i32 %tmp14, 0
+  br i1 %tmp15, label %not_zero11, label %not_zero11.postloop
+
+not_zero11:
+  %v_1 = phi i32 [ %tmp22, %not_zero11 ], [ 0, %not_zero11.preheader ]
+  %tmp16 = zext i32 %v_1 to i64
+  %tmp17 = getelementptr inbounds i8, i8* %tmp8, i64 %tmp16
+  %tmp18 = load i8, i8* %tmp17, align 1
+  %tmp19 = zext i8 %tmp18 to i32
+  %tmp20 = or i32 %tmp19, %tmp10
+  %tmp21 = trunc i32 %tmp20 to i8
+  %addr22 = getelementptr inbounds i8, i8* %tmp12, i64 %tmp16
+  %tmp22 = add nuw nsw i32 %v_1, 1
+  %tmp23 = icmp slt i32 %tmp22, %tmp14
+  br i1 %tmp23, label %not_zero11, label %main.exit.selector
+
+main.exit.selector:
+; CHECK-LABEL: main.exit.selector:
 ; CHECK: %tmp24 = icmp slt i32 %tmp14, %length.i
   %tmp24 = icmp slt i32 %tmp22, %length.i
   br i1 %tmp24, label %not_zero11.postloop, label %leave
 
 leave:
   ret void
 
 not_zero11.postloop:
   ret void
 }