[SCEV] createAddRecFromPHI: Optimize for the most common case.

[mzolotukhin]

Summary

The existing implementation creates a symbolic SCEV expression every
time we analyze a phi node and then has to remove it, when the analysis
is finished. This is very expensive, and in most of the cases it's also
unnecessary. According to the data I collected, ~60-70% of analyzed phi
nodes (measured on SPEC) have the following form:

PN = phi(Start, OP(Self, Constant))

Handling such cases separately significantly speeds this up.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

4092

How about createSimpleAffineAddRec?

4097

Bad space?

4108

I'd avoid using getExistingSCEV here. Instead, how about checking L->isLoopInvariant(BO->RHS or BO->LHS) and if so, call getSCEV? Then you won't waste work since if L->isLoopInvariant(BO->RHS or BO->LHS) is true then you know you're going to be able to return an add recurrence.

4109

As discussed on IRC, please check if this is actually viable.

4118

If you do the check above on L->isLoopInvariant(BO->RHS or BO->LHS) then this won't be necessary.

4176

auto *.

[mzolotukhin]

• Address Sanjoy's remarks.

[mzolotukhin]

Thanks for taking a look, I've updated the patch.

The change in 2014-08-29-CompactUnwind.ll is caused by the fact that SCEV started to produce a simpler expression for %iv.i, which allowed LSR to optimize the test harder. The test seems to exercise instructions positions, so I tried to keep them untouched with this change. It's still a question why the original SCEV algorithm failed to construct the simpler expression for this case, I'll take a look at it later if I find a time.

Michael

[sanjoy]

lgtm, but the test case change looks fishy. This change is NFC right?

include/llvm/Analysis/ScalarEvolution.h

820

Indent?

test/CodeGen/X86/2014-08-29-CompactUnwind.ll

27 ↗

(On Diff #97737)

Why did you change this?

[mzolotukhin]

• Fix indentation.

[mzolotukhin]

This change is NFC right?

I wanted it to be so, but apparently it's not. See more details in my previous reply.

Michael

[sanjoy]

In D32663#745401, @mzolotukhin wrote:

Thanks for taking a look, I've updated the patch.

The change in 2014-08-29-CompactUnwind.ll is caused by the fact that SCEV started to produce a simpler expression for %iv.i, which allowed LSR to optimize the test harder.

Hm, I suspect this is because BEValue would be a SCEVUnknown in that case (== the symbolic phi) in the slow path since %iv.i+0 would be simplified to %iv.i.

So that means this change isn't quite NFC. Can you please add a dedicated test case checking the difference in behavior above ^?

The test seems to exercise instructions positions, so I tried to keep them untouched with this change. It's still a question why the original SCEV algorithm failed to construct the simpler expression for this case, I'll take a look at it later if I find a time.

Michael

include/llvm/Analysis/ScalarEvolution.h

private:
   const SCEV *createSCEV(Value *V);
 
   /// Provide the special handling we need to analyze PHI SCEVs.
   const SCEV *createNodeForPHI(PHINode *PN);
 
   /// Helper function called from createNodeForPHI.
   const SCEV *createAddRecFromPHI(PHINode *PN);
 
+  /// A helper function for createAddRecFromPHI to handle simple cases.
+  const SCEV *createAddRecFromPHISimpleCase(PHINode *PN, Value *BEValueV,
+                                            Value *StartValueV);
+
   /// Helper function called from createNodeForPHI.
   const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
 
   /// Provide special handling for a select-like instruction (currently this
   /// is either a select instruction or a phi node).  \p I is the instruction
   /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
   /// FalseVal".
   const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,

lib/Analysis/ScalarEvolution.cpp

static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) {
 
   default:
     break;
   }
 
   return None;
 }
 
+/// A helper function for createAddRecFromPHI to handle simple cases.
+///
+/// This function tries to find an AddRec expression for the simplest (yet most
+/// common) cases: PN = PHI(Start, OP(Self, LoopInvariant)).
+/// If it fails, createAddRecFromPHI will use a more general, but slow,
+/// technique for finding the AddRec expression.
+const SCEV *ScalarEvolution::createAddRecFromPHISimpleCase(PHINode *PN,
+                                                           Value *BEValueV,
+                                                           Value *StartValueV) {
+  const Loop *L = LI.getLoopFor(PN->getParent());
+  assert(L && L->getHeader() == PN->getParent());
+  assert (BEValueV && StartValueV);
+
+  auto BO = MatchBinaryOp(BEValueV, DT);
+  if (!BO)
+    return nullptr;
+
+  if (BO->Opcode != Instruction::Add)
+    return nullptr;
+
+  const SCEV *Accum = nullptr;
+  if (BO->LHS == PN)
+    Accum = getExistingSCEV(BO->RHS);
+  else if (BO->RHS == PN)
+    Accum = getExistingSCEV(BO->LHS);
+
+  if (!Accum)
+    return nullptr;
+
+  // This is not a valid addrec if the step amount is varying each
+  // loop iteration, but is not itself an addrec in this loop.
+  if (!isLoopInvariant(Accum, L) &&
+      (!isa<SCEVAddRecExpr>(Accum) ||
+       cast<SCEVAddRecExpr>(Accum)->getLoop() != L))
+    return nullptr;
+
+  SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
+  if (BO->IsNUW)
+    Flags = setFlags(Flags, SCEV::FlagNUW);
+  if (BO->IsNSW)
+    Flags = setFlags(Flags, SCEV::FlagNSW);
+
+  const SCEV *StartVal = getSCEV(StartValueV);
+  const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
+
+  ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
+
+  // We can add Flags to the post-inc expression only if we
+  // know that it us *undefined behavior* for BEValueV to
+  // overflow.
+  if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
+    if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
+      (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
+
+  return PHISCEV;
+}
+
 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
   const Loop *L = LI.getLoopFor(PN->getParent());
   if (!L || L->getHeader() != PN->getParent())
     return nullptr;
 
   // The loop may have multiple entrances or multiple exits; we can analyze
   // this phi as an addrec if it has a unique entry value and a unique
   // backedge value.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     } else if (StartValueV != V) {
       StartValueV = nullptr;
       break;
     }
   }
   if (!BEValueV || !StartValueV)
     return nullptr;
 
-  // While we are analyzing this PHI node, handle its value symbolically.
-  const SCEV *SymbolicName = getUnknown(PN);
   assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
          "PHI node already processed?");
+
+  // First, try to find AddRec expression without creating a fictituos symbolic
+  // value for PN.
+  if (auto S = createAddRecFromPHISimpleCase(PN, BEValueV, StartValueV))
+    return S;
+
+  // Handle PHI node value symbolically.
+  const SCEV *SymbolicName = getUnknown(PN);
   ValueExprMap.insert({SCEVCallbackVH(PN, this), SymbolicName});
 
   // Using this symbolic name for the PHI, analyze the value coming around
   // the back-edge.
   const SCEV *BEValue = getSCEV(BEValueV);
 
   // NOTE: If BEValue is loop invariant, we know that the PHI node just
   // has a special value for the first iteration of the loop.