[IndVarSimplify][LoopUtils] Track rewrite cost per unique BB (PR45835)

[dmajor]

Summary

If a PHI node has multiple (identical) values for a given block, rewriteLoopExitValues must either rewrite all of them or none of them. Therefore, instead of tracking the cost for the individual values, track the cost per unique BB.

See PR45835

[dmajor]

Note: the test case does not currently fail on trunk before this change (although it does fail on the 10.0 release branch, where I would eventually like to get this merged) because after D73744 it is no longer blanket assumed that SCEVMinMaxExpr is high cost. Any pointers on how I could modify the test to get around that? (I'm not familiar with why this IR is considered to have a SCEVMinMaxExpr or what it would take to make it high cost.)

[lebedev.ri]

Thank you for looking into it!

(In reply to dmajor from https://bugs.llvm.org/show_bug.cgi?id=45835#c3)

For anyone curious where the different values of HighCost come from...

When we're recursively looking at the second NAry operand [0] of the first
value, that operand is considered high cost due to [1]:

if (isa<SCEVMinMaxExpr>(S))
  return true;

When we're looking at the second NAry operand of the second value, it is
considered low cost due to [2]:

// If we can find an existing value for this scev available at the point "At"
// then consider the expression cheap.
if (At && getRelatedExistingExpansion(S, At, L))
  return false;

Yes, but it is still not obvious to me as to why that happens?
It's the same PHI node, we are asking about the same value, for the same basic block.
Why do we not find expansion first time but do find it second time?
Did we perform some expansion inbetween?

[0]
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/
ScalarEvolutionExpander.cpp#L2198-L2205
[1]
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/
ScalarEvolutionExpander.cpp#L2193-L2196
[2]
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/
ScalarEvolutionExpander.cpp#L2135-L2138

[dmajor]

In D79720#2029647, @lebedev.ri wrote:

Yes, but it is still not obvious to me as to why that happens?
It's the same PHI node, we are asking about the same value, for the same basic block.
Why do we not find expansion first time but do find it second time?
Did we perform some expansion inbetween?

If I'm understanding my recording correctly -- the reason the expansion was found the second time was that we expanded the value the first time, immediately after computing isHighCostExpansion: https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp#L675

[lebedev.ri]

In D79720#2029902, @dmajor wrote:

In D79720#2029647, @lebedev.ri wrote:

Yes, but it is still not obvious to me as to why that happens?
It's the same PHI node, we are asking about the same value, for the same basic block.
Why do we not find expansion first time but do find it second time?
Did we perform some expansion inbetween?

If I'm understanding my recording correctly -- the reason the expansion was found the second time was that we expanded the value the first time, immediately after computing isHighCostExpansion: https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp#L675

But that doesn't make sense to me.
How/why could have we expanded it if we've decided that it is high cost?
Did we expand it just because, and then not actually used the expansion?

[lebedev.ri]

As discussed in IRC, there is a much more fundamental problem that needs to be solved.
I'll take a look.

[lebedev.ri]

D79787

[dmajor]

Abandoning in favor of D79787. Thanks!

llvm/lib/Transforms/Utils/LoopUtils.cpp

static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
   return false;
 }
 
 // Collect information about PHI nodes which can be transformed in
 // rewriteLoopExitValues.
 struct RewritePhi {
   PHINode *PN;
   unsigned Ith;   // Ith incoming value.
+  BasicBlock *BB; // Basic block for this value.
   Value *Val;     // Exit value after expansion.
-  bool HighCost;  // High Cost when expansion.
 
-  RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
-      : PN(P), Ith(I), Val(V), HighCost(H) {}
+  RewritePhi(PHINode *P, unsigned I, BasicBlock *B, Value *V)
+      : PN(P), Ith(I), BB(B), Val(V) {}
 };
 
 // Check whether it is possible to delete the loop after rewriting exit
 // value. If it is possible, ignore ReplaceExitValue and do rewriting
 // aggressively.
 static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
   BasicBlock *Preheader = L->getLoopPreheader();
   // If there is no preheader, the loop will not be deleted.
int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
   // Check a pre-condition.
   assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
          "Indvars did not preserve LCSSA!");
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
 
   SmallVector<RewritePhi, 8> RewritePhiSet;
+  SmallSet<std::pair<PHINode*, BasicBlock*>, 8> HighCostPhiPreds;
+
   // 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 (BasicBlock *ExitBB : ExitBlocks) {
     // If there are no PHI nodes in this exit block, then no values defined
     // inside the loop are used on this path, skip it.
     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
     if (!PN) continue;
 
     unsigned NumPreds = PN->getNumIncomingValues();
 
     // Iterate over all of the PHI nodes.
     BasicBlock::iterator BBI = ExitBB->begin();
while ((PN = dyn_cast<PHINode>(BBI++))) {
       // Iterate over all of the values in all the PHI nodes.
       for (unsigned i = 0; i != NumPreds; ++i) {
         // If the value being merged in is not integer or is not defined
         // in the loop, skip it.
         Value *InVal = PN->getIncomingValue(i);
         if (!isa<Instruction>(InVal))
           continue;
 
+        BasicBlock *BB = PN->getIncomingBlock(i);
+
         // If this pred is for a subloop, not L itself, skip it.
-        if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
+        if (LI->getLoopFor(BB) != L)
           continue; // The Block is in a subloop, skip it.
 
         // Check that InVal is defined in the loop.
         Instruction *Inst = cast<Instruction>(InVal);
         if (!L->contains(Inst))
           continue;
 
         // Okay, this instruction has a user outside of the current loop
#ifndef NDEBUG
         // creating a new use of its instruction.
         if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
           if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
             if (EVL != L)
               assert(EVL->contains(L) && "LCSSA breach detected!");
 #endif
 
         // Collect all the candidate PHINodes to be rewritten.
-        RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
+        RewritePhiSet.emplace_back(PN, i, BB, ExitVal);
+        if (HighCost)
+          HighCostPhiPreds.insert(std::make_pair(PN, BB));
       }
     }
   }
 
   bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
   int NumReplaced = 0;
 
   // Transformation.
   for (const RewritePhi &Phi : RewritePhiSet) {
     PHINode *PN = Phi.PN;
     Value *ExitVal = Phi.Val;
+    BasicBlock *BB = Phi.BB;
 
     // 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) {
+    if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel &&
+        HighCostPhiPreds.count(std::make_pair(PN, BB))) {
       DeadInsts.push_back(ExitVal);
       continue;
     }
 
     NumReplaced++;
     Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
     PN->setIncomingValue(Phi.Ith, ExitVal);
 

llvm/test/Transforms/IndVarSimplify/pr45835.ll

+; RUN: opt < %s -indvars -replexitval=always -S | FileCheck %s --check-prefix=ALWAYS
+; RUN: opt < %s -indvars -replexitval=never -S | FileCheck %s --check-prefix=NEVER
+; RUN: opt < %s -indvars -replexitval=cheap -S | FileCheck %s --check-prefix=CHEAP
+; rewriteLoopExitValues must rewrite all or none of a PHI's values from a given
+; block, even if they have different costs.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+@a = common global i8 0, align 1
+
+define internal fastcc void @d(i8* %c) unnamed_addr #0 {
+entry:
+  %cmp = icmp ule i8* %c, getelementptr inbounds (i8, i8* @a, i64 65535)
+  %add.ptr = getelementptr inbounds i8, i8* %c, i64 -65535
+  br label %while.cond
+
+while.cond:
+  br i1 icmp ne (i8 0, i8 0), label %cont, label %while.end
+
+cont:
+  %a.mux = select i1 %cmp, i8* @a, i8* %add.ptr
+  switch i64 0, label %while.cond [
+    i64 -1, label %handler.pointer_overflow.i
+    i64 0, label %handler.pointer_overflow.i
+  ]
+
+handler.pointer_overflow.i:
+  %a.mux.lcssa4 = phi i8* [ %a.mux, %cont ], [ %a.mux, %cont ]
+; ALWAYS: [ %scevgep, %cont ], [ %scevgep, %cont ]
+; NEVER: [ %a.mux, %cont ], [ %a.mux, %cont ]
+; In cheap mode, use either one as long as it's consistent.
+; CHEAP: [ %[[VAL:.*]], %cont ], [ %[[VAL]], %cont ]
+  %x5 = ptrtoint i8* %a.mux.lcssa4 to i64
+  br label %while.end
+
+while.end:
+  ret void
+}
+