[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 ↗

(On Diff #97171)

How about createSimpleAffineAddRec?

4097 ↗

(On Diff #97171)

Bad space?

4108 ↗

(On Diff #97171)

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 ↗

(On Diff #97171)

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

4118 ↗

(On Diff #97171)

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

4176 ↗

(On Diff #97171)

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 ↗

(On Diff #97737)

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

llvm/trunk/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 *createSimpleAffineAddRec(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,

llvm/trunk/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::createSimpleAffineAddRec(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 && L->isLoopInvariant(BO->RHS))
+    Accum = getSCEV(BO->RHS);
+  else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
+    Accum = getSCEV(BO->LHS);
+
+  if (!Accum)
+    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 = createSimpleAffineAddRec(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.

llvm/trunk/test/Analysis/ScalarEvolution/ZeroStep.ll

+; RUN: opt -analyze -scalar-evolution < %s  -o - -S | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.9.0"
+
+; Test that SCEV is capable of figuring out value of 'IV' that actually does not change.
+; CHECK: Classifying expressions for: @foo
+; CHECK: %iv.i = phi i64
+; CHECK: -5 U: [-5,-4) S: [-5,-4)         Exits: -5               LoopDispositions: { %loop: Invariant }
+define void @foo() {
+entry:
+  br label %loop
+
+loop:
+  %iv.i = phi i64 [ -5, %entry ], [ %iv.next.i, %loop ]
+  %iv.next.i = add nsw i64 %iv.i, 0
+  br label %loop
+}

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

 ; CHECK: Contents of __compact_unwind section
 ; CHECK: ___asan_report_error
 
 ; Because of incorrect push instruction size in X86AsmBackend.cpp the stack
 ; size was also calculated incorrectly.
 ; CHECK-NOT: {{compact encoding:.*0x0309f800}}
 ; CHECK: {{compact encoding:.*0x030df800}}
 
-define void @__asan_report_error() #0 {
+define void @__asan_report_error(i64 %step) #0 {
   %str.i = alloca i64, align 8
   %stack = alloca [256 x i64], align 8
   br label %print_shadow_bytes.exit.i
 
 print_shadow_bytes.exit.i: ; preds = %print_shadow_bytes.exit.i, %0
   %iv.i = phi i64 [ -5, %0 ], [ %iv.next.i, %print_shadow_bytes.exit.i ]
   %reg15 = icmp eq i64 %iv.i, 0
   %.str..str1.i = select i1 %reg15, [3 x i8]* @.str, [3 x i8]* @.str1
   %reg16 = getelementptr inbounds [3 x i8], [3 x i8]* %.str..str1.i, i64 0, i64 0
   %reg17 = shl i64 %iv.i, 1
   %reg19 = inttoptr i64 %reg17 to i8*
   call void (i64*, i8*, ...) @append(i64* %str.i, i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str2, i64 0, i64 0), i8* %reg16, i8* %reg19)
-  %iv.next.i = add nsw i64 %iv.i, 0
+  %iv.next.i = add nsw i64 %iv.i, %step
   br label %print_shadow_bytes.exit.i
 }
 
 declare void @append(i64*, i8*, ...)
 
 attributes #0 = { "no-frame-pointer-elim"="false" }