Do not allow multiple possibly aliasing ptrs in an expression

  Relational comparisons should not involve multiple potentially
  aliasing pointers. Similarly this should hold for switch conditions
  and the two conditions involved in equality comparisons (separately!).
  This is a heuristic based on the C semantics that does only allow such
  operations when the base pointers do point into the same object.
  Since this makes aliasing likely we will bail out early instead of
  producing a probably failing runtime check.

llvm-svn: 288516

2 files changed, 57 insertions, 0 deletions

diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h
index ef6c95ebf01..2bca384041f 100644
--- a/polly/include/polly/ScopDetection.h
+++ b/polly/include/polly/ScopDetection.h
@@ -219,6 +219,16 @@ private:
   /// Remove cached results for the children of @p R recursively.
   void removeCachedResultsRecursively(const Region &R);
 
+  /// Check if @p S0 and @p S1 do contain multiple possibly aliasing pointers.
+  ///
+  /// @param S0    A expression to check.
+  /// @param S1    Another expression to check or nullptr.
+  /// @param Scope The loop/scope the expressions are checked in.
+  ///
+  /// @returns True, if multiple possibly aliasing pointers are used in @p S0
+  ///          (and @p S1 if given).
+  bool involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const;
+
   /// Add the region @p AR as over approximated sub-region in @p Context.
   ///
   /// @param AR      The non-affine subregion.
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 438d80a8703..756cb5d6d68 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -346,6 +346,40 @@ bool ScopDetection::onlyValidRequiredInvariantLoads(
   return true;
 }
 
+bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1,
+                                         Loop *Scope) const {
+  SetVector<Value *> Values;
+  findValues(S0, *SE, Values);
+  if (S1)
+    findValues(S1, *SE, Values);
+
+  SmallPtrSet<Value *, 8> PtrVals;
+  for (auto *V : Values) {
+    if (auto *P2I = dyn_cast<PtrToIntInst>(V))
+      V = P2I->getOperand(0);
+
+    if (!V->getType()->isPointerTy())
+      continue;
+
+    auto *PtrSCEV = SE->getSCEVAtScope(V, Scope);
+    if (isa<SCEVConstant>(PtrSCEV))
+      continue;
+
+    auto *BasePtr = dyn_cast<SCEVUnknown>(SE->getPointerBase(PtrSCEV));
+    if (!BasePtr)
+      return true;
+
+    auto *BasePtrVal = BasePtr->getValue();
+    if (PtrVals.insert(BasePtrVal).second) {
+      for (auto *PtrVal : PtrVals)
+        if (PtrVal != BasePtrVal && !AA->isNoAlias(PtrVal, BasePtrVal))
+          return true;
+    }
+  }
+
+  return false;
+}
+
 bool ScopDetection::isAffine(const SCEV *S, Loop *Scope,
                              DetectionContext &Context) const {
 
@@ -368,6 +402,10 @@ bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI,
   if (IsLoopBranch && L->isLoopLatch(&BB))
     return false;
 
+  // Check for invalid usage of different pointers in one expression.
+  if (involvesMultiplePtrs(ConditionSCEV, nullptr, L))
+    return false;
+
   if (isAffine(ConditionSCEV, L, Context))
     return true;
 
@@ -416,6 +454,15 @@ bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
   const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
   const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
 
+  // Check for invalid usage of different pointers in one expression.
+  if (ICmp->isEquality() && involvesMultiplePtrs(LHS, nullptr, L) &&
+      involvesMultiplePtrs(RHS, nullptr, L))
+    return false;
+
+  // Check for invalid usage of different pointers in a relational comparison.
+  if (ICmp->isRelational() && involvesMultiplePtrs(LHS, RHS, L))
+    return false;
+
   if (isAffine(LHS, L, Context) && isAffine(RHS, L, Context))
     return true;