[prev in list] [next in list] [prev in thread] [next in thread] 

List:       llvm-commits
Subject:    [PATCH] D110892: [SCEV] Remove invariant requirement from isSCEVExprNeverPoison
From:       Philip Reames via Phabricator via llvm-commits <llvm-commits () lists ! llvm ! org>
Date:       2021-09-30 23:17:48
Message-ID: MjpC-fFUTkKGGCeocgDExQ () ismtpd0167p1mdw1 ! sendgrid ! net
[Download RAW message or body]

reames created this revision.
reames added reviewers: nikic, efriedma.
Herald added subscribers: javed.absar, bollu, hiraditya, mcrosier.
reames requested review of this revision.
Herald added a project: LLVM.

This code is attempting to prove that I must execute if we enter the defining scope \
of the SCEV which will be created from I.  In the case where it found a defining \
addrec scope, it had a rather odd restriction that all of the other operands must be \
loop invariant in that addrec's loop.

As near as I can tell here, we really only need a upper bound on the defining scope.  \
If we can prove the stronger property, then we must also have proven the property on \
the exact defining scope as well.

In practice, the actual effect of this change is narrow.  The compile time \
restriction at the top of the routine basically limits us to I being an arithmetic in \
some loop L with both an addrec operand in L, and a unknown operands in L.  Possible \
to demonstrate, but the main value of the change is removing unneeded code.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D110892

Files:
  llvm/lib/Analysis/ScalarEvolution.cpp


Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -6582,15 +6582,11 @@
   // instructions can map to the same SCEV. If we apply NSW or NUW from I to
   // the SCEV, we must guarantee no wrapping for that SCEV also when it is
   // derived from other instructions that map to the same SCEV. We cannot make
-  // that guarantee for cases where I is not executed. So we need to find the
-  // loop that I is considered in relation to and prove that I is executed for
-  // every iteration of that loop. That implies that the value that I
-  // calculates does not wrap anywhere in the loop, so then we can apply the
-  // flags to the SCEV.
-  //
-  // We check isLoopInvariant to disambiguate in case we are adding recurrences
-  // from different loops, so that we know which loop to prove that I is
-  // executed in.
+  // that guarantee for cases where I is not executed. So we need to find a
+  // upper bound on the defining scope for the SCEV, and prove that I is
+  // executed every time we enter that scope.  (When the bounding scope is a
+  // loop (the common case), this is equivalent to proving I executes on every
+  // iteration of that loop.
   for (const Use &Op : I->operands()) {
     // I could be an extractvalue from a call to an overflow intrinsic.
     // TODO: We can do better here in some cases.
@@ -6598,14 +6594,7 @@
       return false;
     const SCEV *OpS = getSCEV(Op);
     if (auto *AddRecS = dyn_cast<SCEVAddRecExpr>(OpS)) {
-      const bool AllOtherOpsLoopInvariant =
-        llvm::all_of(I->operands(), [&](const Use &Op2) -> bool {
-          if (Op.getOperandNo() == Op2.getOperandNo())
-            return true;
-          const SCEV *OtherOp = getSCEV(Op2);
-          return isLoopInvariant(OtherOp, AddRecS->getLoop());
-        });
-      if (AllOtherOpsLoopInvariant &&
+      if (AddRecS->getLoop() == InnermostContainingLoop &&
           isGuaranteedToExecuteForEveryIteration(I, AddRecS->getLoop()))
         return true;
     }


["D110892.376384.patch" (D110892.376384.patch)]

Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -6582,15 +6582,11 @@
   // instructions can map to the same SCEV. If we apply NSW or NUW from I to
   // the SCEV, we must guarantee no wrapping for that SCEV also when it is
   // derived from other instructions that map to the same SCEV. We cannot make
-  // that guarantee for cases where I is not executed. So we need to find the
-  // loop that I is considered in relation to and prove that I is executed for
-  // every iteration of that loop. That implies that the value that I
-  // calculates does not wrap anywhere in the loop, so then we can apply the
-  // flags to the SCEV.
-  //
-  // We check isLoopInvariant to disambiguate in case we are adding recurrences
-  // from different loops, so that we know which loop to prove that I is
-  // executed in.
+  // that guarantee for cases where I is not executed. So we need to find a
+  // upper bound on the defining scope for the SCEV, and prove that I is
+  // executed every time we enter that scope.  (When the bounding scope is a
+  // loop (the common case), this is equivalent to proving I executes on every
+  // iteration of that loop.
   for (const Use &Op : I->operands()) {
     // I could be an extractvalue from a call to an overflow intrinsic.
     // TODO: We can do better here in some cases.
@@ -6598,14 +6594,7 @@
       return false;
     const SCEV *OpS = getSCEV(Op);
     if (auto *AddRecS = dyn_cast<SCEVAddRecExpr>(OpS)) {
-      const bool AllOtherOpsLoopInvariant =
-        llvm::all_of(I->operands(), [&](const Use &Op2) -> bool {
-          if (Op.getOperandNo() == Op2.getOperandNo())
-            return true;
-          const SCEV *OtherOp = getSCEV(Op2);
-          return isLoopInvariant(OtherOp, AddRecS->getLoop());
-        });
-      if (AllOtherOpsLoopInvariant &&
+      if (AddRecS->getLoop() == InnermostContainingLoop &&
           isGuaranteedToExecuteForEveryIteration(I, AddRecS->getLoop()))
         return true;
     }

[Attachment #4 (text/plain)]

_______________________________________________
llvm-commits mailing list
llvm-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits


[prev in list] [next in list] [prev in thread] [next in thread]