Enable ExitValue rewrite only when expansion cost is low.

[wmi]

Summary

The patch is to enable ExitValue rewrite (In IndVarSimplify pass) only when the cost of expansion is low, just like LinearFunctionTestReplace does right now. The problem is described in https://llvm.org/bugs/show_bug.cgi?id=23538.

It includes these changes:

1. Add an option. -replexitval=cheap is the default. -replexitval - Choose the strategy to replace exit value in IndVarSimplify =never - never replace exit value =cheap - only replace exit value when the cost is cheap =always - always replace exit value whenever possible

2. The existing logic of SCEVExpander::isHighCostExpansionHelper is problematic. It cannot find out the udiv operator inside SCEVNAryExpr other than SCEVAddExpr. It doesn't check the sub SCEV inside SCEVTruncateExpr/SCEVZeroExtendExpr/SCEVSignExtendExpr. Like the SCEV: (-12 + (-12 * ((-12 + %len) /u 12)) + %len), SCEVExpander::isHighCostExpansionHelper will return false for it now. Fix the logic.

The patch improved an internal benchmark by 10%. It improved bzip2 in spec2000 by 1%.

[hfinkel]

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

lib/Transforms/Scalar/IndVarSimplify.cpp

616 ↗

(On Diff #25880)

No { } needed here.

[wmi]

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

Yes, it makes sense, although it will increase the code complexity a little bit. I think it can be done like this: The loop can be removed only when all the phi nodes in exitBB with incoming values from the loop can be rewritten. We need to hold the transformations of all the phi in every ExitBB of the loop, get the information whether the loop can be removed, then do the transformation for all the phi in the end.

I will get a new patch to implement it.

[hfinkel]

In D9800#175987, @wmi wrote:

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

Yes, it makes sense, although it will increase the code complexity a little bit. I think it can be done like this: The loop can be removed only when all the phi nodes in exitBB with incoming values from the loop can be rewritten. We need to hold the transformations of all the phi in every ExitBB of the loop, get the information whether the loop can be removed, then do the transformation for all the phi in the end.

I will get a new patch to implement it.

Great! Do you also need to check the loops for instructions with side effects?

[wmi]

In D9800#176008, @hfinkel wrote:

In D9800#175987, @wmi wrote:

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

Yes, it makes sense, although it will increase the code complexity a little bit. I think it can be done like this: The loop can be removed only when all the phi nodes in exitBB with incoming values from the loop can be rewritten. We need to hold the transformations of all the phi in every ExitBB of the loop, get the information whether the loop can be removed, then do the transformation for all the phi in the end.

I will get a new patch to implement it.

Great! Do you also need to check the loops for instructions with side effects?

Yes, it is needed. Thanks for reminding. I will check the existing legality check logic to remove a loop when it is dead.

[wmi]

I updated the patch to enable aggressive exit value rewriting if the loop can be deleted after the rewrite.

Thanks,
Wei.

[hfinkel]

Thanks for continuing to work on this. A few comments below, and I'd like Andy to look at this.

lib/Transforms/Scalar/IndVarSimplify.cpp

718 ↗

(On Diff #26625)

Once LoopCanBeDel is false, it will never become true again. Please remove this variable and just 'return false' in all places where you set LoopCanBeDel to false.

740 ↗

(On Diff #26625)

incoming -> Incoming

[atrick]

Nice work.

Please update you patch for trunk. You probably don't need LastPN.

IsLoopCanBeDel should be phrased "CanLoopBeDeleted". However, it's not just a query; it at least needs a very clear comment that it may hoist instructions into the preheader to facilitate the query.

As Hal pointed out, it's very important to return early from CanLoopBeDeleted. We should only scan all instructions in the loop if we know the loop can otherwise be deleted.

I'm curious why you needed to enable aggressive exit value replacement in four unit tests. Can your logic determine that the loops can be deleted in those cases?

[wmi]

Hal and Andy, thanks for the helpful comments.

Once LoopCanBeDel is false, it will never become true again. Please remove this variable and just 'return false' in all places where you set LoopCanBeDel to false.

Done.

incoming -> Incoming

Done.

Please update you patch for trunk. You probably don't need LastPN.

Done.

IsLoopCanBeDel should be phrased "CanLoopBeDeleted". However, it's not just a query; it at least needs a very clear comment that it may hoist instructions into the preheader to facilitate the query.

I think it is fine to let later phase to do the LICM so I changed Loop::makeLoopInvariant to Loop::hasLoopInvariantOperands. CanLoopBeDeleted is a query only func now.

As Hal pointed out, it's very important to return early from CanLoopBeDeleted. We should only scan all instructions in the loop if we know the loop can otherwise be deleted.

Done.

I'm curious why you needed to enable aggressive exit value replacement in four unit tests. Can your logic determine that the loops can be deleted in those cases?

I changed the tests. Now aggressive exit value replacement is only enabled in test/Transforms/IndVarSimplify/lcssa-preservation.ll. That test is used to check IndVars preserves LCSSA form. I preserve the original test behavior by enabling aggressive exit value replacement. For other three tests, loops can be deleted.

Thanks,
Wei.

[atrick]

LGTM

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

for (SmallVectorImpl<PHINode*>::const_iterator PIter = Phis.begin(),
     Phi->replaceAllUsesWith(NewIV);
     DeadInsts.push_back(Phi);
   }
   return NumElim;
 }
 
 bool SCEVExpander::isHighCostExpansionHelper(
     const SCEV *S, Loop *L, SmallPtrSetImpl<const SCEV *> &Processed) {
+
+  // Zero/One operand expressions
+  switch (S->getSCEVType()) {
+  case scUnknown:
+  case scConstant:
+    return false;
+  case scTruncate:
+    return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(), L,
+                                     Processed);
+  case scZeroExtend:
+    return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
+                                     L, Processed);
+  case scSignExtend:
+    return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
+                                     L, Processed);
+  }
+
   if (!Processed.insert(S).second)
     return false;
 
   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // If the divisor is a power of two and the SCEV type fits in a native
     // integer, consider the divison cheap irrespective of whether it occurs in
     // the user code since it can be lowered into a right shift.
     if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     if (RHS != S) {
       const SCEV *LHS = SE.getSCEV(OrigCond->getOperand(0));
       LHS = SE.getMinusSCEV(LHS, SE.getConstant(LHS->getType(), 1));
       if (LHS != S)
         return true;
     }
   }
 
-  // Recurse past add expressions, which commonly occur in the
+  // HowManyLessThans uses a Max expression whenever the loop is not guarded by
+  // the exit condition.
+  if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
+    return true;
+
+  // Recurse past nary expressions, which commonly occur in the
   // BackedgeTakenCount. They may already exist in program code, and if not,
   // they are not too expensive rematerialize.
-  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
-    for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
+  if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
+    for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
          I != E; ++I) {
       if (isHighCostExpansionHelper(*I, L, Processed))
         return true;
     }
-    return false;
   }
 
-  // HowManyLessThans uses a Max expression whenever the loop is not guarded by
-  // the exit condition.
-  if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
-    return true;
-
   // If we haven't recognized an expensive SCEV pattern, assume it's an
   // expression produced by program code.
   return false;
 }
 
 namespace {
 // Search for a SCEV subexpression that is not safe to expand.  Any expression
 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely

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

 // use the verify-indvars flag, which may assert in some cases.
 static cl::opt<bool> VerifyIndvars(
   "verify-indvars", cl::Hidden,
   cl::desc("Verify the ScalarEvolution result after running indvars"));
 
 static cl::opt<bool> ReduceLiveIVs("liv-reduce", cl::Hidden,
   cl::desc("Reduce live induction variables."));
 
+enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, AlwaysRepl };
+
+static cl::opt<ReplaceExitVal> ReplaceExitValue(
+    "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
+    cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),
+    cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"),
+               clEnumValN(OnlyCheapRepl, "cheap",
+                          "only replace exit value when the cost is cheap"),
+               clEnumValN(AlwaysRepl, "always",
+                          "always replace exit value whenever possible"),
+               clEnumValEnd));
+
+namespace {
+struct RewritePhi;
+}
+
 namespace {
   class IndVarSimplify : public LoopPass {
     LoopInfo                  *LI;
     ScalarEvolution           *SE;
     DominatorTree             *DT;
     TargetLibraryInfo         *TLI;
     const TargetTransformInfo *TTI;
 
private:
 
     bool isValidRewrite(Value *FromVal, Value *ToVal);
 
     void HandleFloatingPointIV(Loop *L, PHINode *PH);
     void RewriteNonIntegerIVs(Loop *L);
 
     void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM);
 
+    bool CanLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
     void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
 
     Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
                                      PHINode *IndVar, SCEVExpander &Rewriter);
 
     void SinkUnusedInvariants(Loop *L);
   };
 }
void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
 
   // If the loop previously had floating-point IV, ScalarEvolution
   // may not have been able to compute a trip count. Now that we've done some
   // re-writing, the trip count may be computable.
   if (Changed)
     SE->forgetLoop(L);
 }
 
+namespace {
+// Collect information about PHI nodes which can be transformed in
+// RewriteLoopExitValues.
+struct RewritePhi {
+  PHINode *PN;
+  unsigned Ith;  // Ith incoming value.
+  Value *Val;    // Exit value after expansion.
+  bool HighCost; // High Cost when expansion.
+  bool SafePhi;  // LCSSASafePhiForRAUW.
+
+  RewritePhi(PHINode *P, unsigned I, Value *V, bool H, bool S)
+      : PN(P), Ith(I), Val(V), HighCost(H), SafePhi(S) {}
+};
+}
+
 //===----------------------------------------------------------------------===//
 // RewriteLoopExitValues - Optimize IV users outside the loop.
 // As a side effect, reduces the amount of IV processing within the loop.
 //===----------------------------------------------------------------------===//
 
 /// RewriteLoopExitValues - 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
 /// able to brute-force evaluate arbitrary instructions as long as they have
 /// constant operands at the beginning of the loop.
 void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
   // Verify the input to the pass in already in LCSSA form.
   assert(L->isLCSSAForm(*DT));
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
 
+  SmallVector<RewritePhi, 8> RewritePhiSet;
   // Find all values that are computed inside the loop, but used outside of it.
   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
   // the exit blocks of the loop to find them.
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
     BasicBlock *ExitBB = ExitBlocks[i];
 
     // If there are no PHI nodes in this exit block, then no values defined
     // inside the loop are used on this path, skip it.
while ((PN = dyn_cast<PHINode>(BBI++))) {
 
         DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n'
                      << "  LoopVal = " << *Inst << "\n");
 
         if (!isValidRewrite(Inst, ExitVal)) {
           DeadInsts.push_back(ExitVal);
           continue;
         }
-        Changed = true;
-        ++NumReplaced;
-
-        PN->setIncomingValue(i, ExitVal);
+        bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L);
+
+        // Collect all the candidate PHINodes to be rewritten.
+        RewritePhiSet.push_back(
+            RewritePhi(PN, i, ExitVal, HighCost, LCSSASafePhiForRAUW));
+      }
+    }
+  }
+
+  bool LoopCanBeDel = CanLoopBeDeleted(L, RewritePhiSet);
+
+  // Transformation.
+  for (const RewritePhi &Phi : RewritePhiSet) {
+    PHINode *PN = Phi.PN;
+    Value *ExitVal = Phi.Val;
+
+    // Only do the rewrite when the ExitValue can be expanded cheaply.
+    // If LoopCanBeDel is true, rewrite exit value aggressively.
+    if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
+      DeadInsts.push_back(ExitVal);
+      continue;
+    }
+
+    Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
+    PN->setIncomingValue(Phi.Ith, ExitVal);
 
-        // If this instruction is dead now, delete it. Don't do it now to avoid
-        // invalidating iterators.
-        if (isInstructionTriviallyDead(Inst, TLI))
-          DeadInsts.push_back(Inst);
 
-        // If we determined that this PHI is safe to replace even if an LCSSA
-        // PHI, do so.
-        if (LCSSASafePhiForRAUW) {
-          PN->replaceAllUsesWith(ExitVal);
-          PN->eraseFromParent();
-        }
-      }
-    }
-  }
+    if (Phi.SafePhi) {
 
   // The insertion point instruction may have been deleted; clear it out
   // so that the rewriter doesn't trip over it later.
   Rewriter.clearInsertPoint();
 }
 
+/// CanLoopBeDeleted - Check whether it is possible to delete the loop after
+/// rewriting exit value. If it is possible, ignore ReplaceExitValue and
+/// do rewriting aggressively.
+bool IndVarSimplify::CanLoopBeDeleted(
+    Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
+
+  BasicBlock *Preheader = L->getLoopPreheader();
+  // If there is no preheader, the loop will not be deleted.
+  if (!Preheader)
+    return false;
+
+  // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
+  // We obviate multiple ExitingBlocks case for simplicity.
+  // TODO: If we see testcase with multiple ExitingBlocks can be deleted
+  // after exit value rewriting, we can enhance the logic here.
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  SmallVector<BasicBlock *, 8> ExitBlocks;
+  L->getUniqueExitBlocks(ExitBlocks);
+  if (ExitBlocks.size() > 1 || ExitingBlocks.size() > 1)
+    return false;
+
+  BasicBlock *ExitBlock = ExitBlocks[0];
+  BasicBlock::iterator BI = ExitBlock->begin();
+  while (PHINode *P = dyn_cast<PHINode>(BI)) {
+    Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
+
+    // If the Incoming value of P is found in RewritePhiSet, we know it
+    // could be rewritten to use a loop invariant value in transformation
+    // phase later. Skip it in the loop invariant check below.
+    bool found = false;
+    for (const RewritePhi &Phi : RewritePhiSet) {
+      unsigned i = Phi.Ith;
+      if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
+        found = true;
+        break;
+      }
+    }
+
+    Instruction *I;
+    if (!found && (I = dyn_cast<Instruction>(Incoming)))
+      if (!L->hasLoopInvariantOperands(I))
+        return false;
+
+    ++BI;
+  }
+
+  for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
+       LI != LE; ++LI) {
+    for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); BI != BE;
+         ++BI) {
+      if (BI->mayHaveSideEffects())
+        return false;
+    }
+  }
+
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 //  IV Widening - Extend the width of an IV to cover its widest uses.
 //===----------------------------------------------------------------------===//
 
 namespace {
   // Collect information about induction variables that are used by sign/zero
   // extend operations. This information is recorded by CollectExtend and
   // provides the input to WidenIV.
#endif
   SimplifyAndExtend(L, Rewriter, LPM);
 
   // 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.
   //
-  if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
+  if (ReplaceExitValue != NeverRepl &&
+      !isa<SCEVCouldNotCompute>(BackedgeTakenCount))
     RewriteLoopExitValues(L, Rewriter);
 
   // Eliminate redundant IV cycles.
   NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
 
   // If we have a trip count expression, rewrite the loop's exit condition
   // using it.  We can currently only handle loops with a single exit.
   if (canExpandBackedgeTakenCount(L, SE, Rewriter) && needsLFTR(L, DT)) {

llvm/trunk/test/Transforms/IndVarSimplify/exit_value_test2.ll

+; PR23538
+; RUN: opt < %s -indvars -loop-deletion -S | FileCheck %s
+
+; Check IndVarSimplify should not replace exit value because or else
+; udiv will be introduced by expand and the cost will be high.
+;
+; CHECK-LABEL: @_Z3fooPKcjj(
+; CHECK-NOT: udiv
+
+declare void @_Z3mixRjj(i32* dereferenceable(4), i32)
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+define i32 @_Z3fooPKcjj(i8* nocapture readonly %s, i32 %len, i32 %c) {
+entry:
+  %a = alloca i32, align 4
+  %tmp = bitcast i32* %a to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %tmp)
+  store i32 -1640531527, i32* %a, align 4
+  %cmp8 = icmp ugt i32 %len, 11
+  br i1 %cmp8, label %while.body.lr.ph, label %while.end
+
+while.body.lr.ph:                                 ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %while.body, %while.body.lr.ph
+  %keylen.010 = phi i32 [ %len, %while.body.lr.ph ], [ %sub, %while.body ]
+  %s.addr.09 = phi i8* [ %s, %while.body.lr.ph ], [ %add.ptr, %while.body ]
+  %tmp1 = bitcast i8* %s.addr.09 to i32*
+  %tmp2 = load i32, i32* %tmp1, align 4
+  %shl.i = shl i32 %tmp2, 1
+  %and.i = and i32 %shl.i, 16843008
+  %tmp3 = load i32, i32* %a, align 4
+  %sub.i = add i32 %tmp3, %tmp2
+  %add = sub i32 %sub.i, %and.i
+  store i32 %add, i32* %a, align 4
+  %add.ptr = getelementptr inbounds i8, i8* %s.addr.09, i64 12
+  %sub = add i32 %keylen.010, -12
+  %cmp = icmp ugt i32 %sub, 11
+  br i1 %cmp, label %while.body, label %while.cond.while.end_crit_edge
+
+while.cond.while.end_crit_edge:                   ; preds = %while.body
+  %sub.lcssa = phi i32 [ %sub, %while.body ]
+  br label %while.end
+
+while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
+  %keylen.0.lcssa = phi i32 [ %sub.lcssa, %while.cond.while.end_crit_edge ], [ %len, %entry ]
+  call void @_Z3mixRjj(i32* dereferenceable(4) %a, i32 %keylen.0.lcssa)
+  %tmp4 = load i32, i32* %a, align 4
+  call void @llvm.lifetime.end(i64 4, i8* %tmp)
+  ret i32 %tmp4
+}

llvm/trunk/test/Transforms/IndVarSimplify/exit_value_test3.ll

+; RUN: opt < %s -indvars -loop-deletion -S |FileCheck %s
+
+; Check IndVarSimplify should replace exit value even if the expansion cost
+; is high because the loop can be deleted after the exit value rewrite.
+;
+; CHECK-LABEL: @_Z3fooPKcjj(
+; CHECK: udiv
+; CHECK: [[LABEL:^[a-zA-Z0-9_.]+]]:
+; CHECK-NOT: br {{.*}} [[LABEL]]
+
+define i32 @_Z3fooPKcjj(i8* nocapture readnone %s, i32 %len, i32 %c) #0 {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.cond, %entry
+  %klen.0 = phi i32 [ %len, %entry ], [ %sub, %while.cond ]
+  %cmp = icmp ugt i32 %klen.0, 11
+  %sub = add i32 %klen.0, -12
+  br i1 %cmp, label %while.cond, label %while.end
+
+while.end:                                        ; preds = %while.cond
+  %klen.0.lcssa = phi i32 [ %klen.0, %while.cond ]
+  ret i32 %klen.0.lcssa
+}

llvm/trunk/test/Transforms/IndVarSimplify/lcssa-preservation.ll

-; RUN: opt < %s -indvars -S | FileCheck %s
-;
+; RUN: opt < %s -indvars -replexitval=always -S | FileCheck %s
 ; Make sure IndVars preserves LCSSA form, especially across loop nests. 
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 define void @PR18642(i32 %x) {
 ; CHECK-LABEL: @PR18642(
 entry:
   br label %outer.header