[Polly][WIP] Emit remarks for taken assumptions

[jdoerfert]

Summary

• Mainly unit tests are missing --

[grosser]

Hi Johannes,

this looks generally good. Please make sure to add good test cases.

Best,
Tobias

include/polly/ScopInfo.h

77 ↗

(On Diff #39457)

DELINEARIZATION

lib/Analysis/ScopInfo.cpp

102 ↗

(On Diff #39457)

The option name made me first think that this is actually about taking assumptions or not, but indeed this only affects the reporting. This caused confusion. As this is anyhow can be controlled byt the -Rpass, -pass-remarks flags I wonder if we should not just drop this option.

2357 ↗

(On Diff #39457)

This seems to be an independent change and could be committed by itself.

2868 ↗

(On Diff #39457)

We might want to add this logic to ScopDetectionDiagnostic.cpp

3836 ↗

(On Diff #39457)

These changes seem unrelated and also seem to duplicate the logic in emitValidRemarks().

[jdoerfert]

Thanks for the feedback.

lib/Analysis/ScopInfo.cpp

102 ↗

(On Diff #39457)

I was thinking it would save time in the 99% of the runs we do not activate the Rpass option but I don't need it.

2357 ↗

(On Diff #39457)

Ok.

2868 ↗

(On Diff #39457)

Why? It has nothing to do with ScopDetection and it cannot be reused...

3836 ↗

(On Diff #39457)

True, I will commit it separatly and drop emitValidRemarks

[jdoerfert]

lib/Analysis/ScopInfo.cpp

3836 ↗

(On Diff #39457)

Btw. -polly-report and emitValidRemarks were already doing the same thing,...

polly/trunk/include/polly/ScopInfo.h

 
 class MemoryAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 
 //===---------------------------------------------------------------------===//
 
+/// @brief Enumeration of assumptions Polly can take.
+enum AssumptionKind {
+  ALIASING,
+  INBOUNDS,
+  WRAPPING,
+  ERRORBLOCK,
+  INFINITELOOP,
+  INVARIANTLOAD,
+  DELINEARIZATION,
+};
+
 /// Maps from a loop to the affine function expressing its backedge taken count.
 /// The backedge taken count already enough to express iteration domain as we
 /// only allow loops with canonical induction variable.
 /// A canonical induction variable is:
 /// an integer recurrence that starts at 0 and increments by one each time
 /// through the loop.
 typedef std::map<const Loop *, const SCEV *> LoopBoundMapType;
 
public:
   /// @brief Return true if the optimized SCoP can be executed.
   ///
   /// In addition to the runtime check context this will also utilize the domain
   /// constraints to decide it the optimized version can actually be executed.
   ///
   /// @returns True if the optimized SCoP can be executed.
   bool hasFeasibleRuntimeContext() const;
 
+  /// @brief Track and report an assumption.
+  ///
+  /// Use 'clang -Rpass-analysis=polly-scops' or 'opt -pass-remarks=polly-scops'
+  /// to output the assumptions.
+  ///
+  /// @param Kind The assumption kind describing the underlying cause.
+  /// @param Set  The relations between parameters that are assumed to hold.
+  /// @param Loc  The location in the source that caused this assumption.
+  void trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set,
+                       DebugLoc Loc);
+
   /// @brief Add assumptions to assumed context.
   ///
   /// The assumptions added will be assumed to hold during the execution of the
   /// scop. However, as they are generally not statically provable, at code
   /// generation time run-time checks will be generated that ensure the
   /// assumptions hold.
   ///
   /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
   ///          that assumptions do not change the set of statement instances
   ///          executed.
   ///
-  /// @param Set A set describing relations between parameters that are assumed
-  ///            to hold.
-  void addAssumption(__isl_take isl_set *Set);
+  /// @param Kind The assumption kind describing the underlying cause.
+  /// @param Set  The relations between parameters that are assumed to hold.
+  /// @param Loc  The location in the source that caused this assumption.
+  void addAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
+                     DebugLoc Loc);
 
   /// @brief Get the boundary context for this Scop.
   ///
   /// @return The boundary context of this Scop.
   __isl_give isl_set *getBoundaryContext() const;
 
   /// @brief Build the alias checks for this SCoP.
   void buildAliasChecks(AliasAnalysis &AA);

polly/trunk/lib/Analysis/ScopInfo.cpp

void MemoryAccess::assumeNoOutOfBound() {
   Outside = isl_set_params(Outside);
 
   // Remove divs to avoid the construction of overly complicated assumptions.
   // Doing so increases the set of parameter combinations that are assumed to
   // not appear. This is always save, but may make the resulting run-time check
   // bail out more often than strictly necessary.
   Outside = isl_set_remove_divs(Outside);
   Outside = isl_set_complement(Outside);
-  Statement->getParent()->addAssumption(Outside);
+  Statement->getParent()->addAssumption(INBOUNDS, Outside,
+                                        getAccessInstruction()->getDebugLoc());
   isl_space_free(Space);
 }
 
 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
   ScalarEvolution *SE = Statement->getParent()->getSE();
 
   Value *Ptr = getPointerOperand(*getAccessInstruction());
   if (!Ptr || !SE->isSCEVable(Ptr->getType()))
for (size_t i = 0; i < Sizes.size(); i++) {
     OutOfBound = isl_set_params(OutOfBound);
     isl_set *InBound = isl_set_complement(OutOfBound);
     isl_set *Executed = isl_set_params(getDomain());
 
     // A => B == !A or B
     isl_set *InBoundIfExecuted =
         isl_set_union(isl_set_complement(Executed), InBound);
 
-    Parent.addAssumption(InBoundIfExecuted);
+    Parent.addAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc());
   }
 
   isl_local_space_free(LSpace);
 }
 
 void ScopStmt::deriveAssumptions(BasicBlock *Block) {
   for (Instruction &Inst : *Block)
     if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
if (isl_ctx_last_error(getIslCtx()) == isl_error_quota) {
     isl_set_free(BoundaryContext);
     BoundaryContext = isl_set_empty(getParamSpace());
   }
 
   isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
   isl_ctx_reset_operations(getIslCtx());
   isl_ctx_set_max_operations(getIslCtx(), MaxOpsOld);
   BoundaryContext = isl_set_gist_params(BoundaryContext, getContext());
+  trackAssumption(WRAPPING, BoundaryContext, DebugLoc());
 }
 
 void Scop::addUserContext() {
   if (UserContextStr.empty())
     return;
 
   isl_set *UserContext = isl_set_read_from_str(IslCtx, UserContextStr.c_str());
   isl_space *Space = getParamSpace();
for (auto *RN : RTraversal) {
 
     if (BBLoop && BBLoop->getHeader() == BB && getRegion().contains(BBLoop))
       addLoopBoundsToHeaderDomain(BBLoop);
 
     // Add assumptions for error blocks.
     if (containsErrorBlock(RN, getRegion(), LI, DT)) {
       IsOptimized = true;
       isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
-      addAssumption(isl_set_complement(DomPar));
+      addAssumption(ERRORBLOCK, isl_set_complement(DomPar),
+                    BB->getTerminator()->getDebugLoc());
     }
   }
 }
 
 /// @brief Create a map from SetSpace -> SetSpace where the dimensions @p Dim
 ///        is incremented by one and all other dimensions are equal, e.g.,
 ///             [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
 ///        if @p Dim is 2 and @p SetSpace has 4 dimensions.
void Scop::addLoopBoundsToHeaderDomain(Loop *L) {
   // <nsw> tag.
   if (Affinator.hasNSWAddRecForLoop(L)) {
     isl_set_free(Parts.first);
     return;
   }
 
   isl_set *UnboundedCtx = isl_set_params(Parts.first);
   isl_set *BoundedCtx = isl_set_complement(UnboundedCtx);
-  addAssumption(BoundedCtx);
+  addAssumption(INFINITELOOP, BoundedCtx,
+                HeaderBB->getTerminator()->getDebugLoc());
 }
 
 void Scop::buildAliasChecks(AliasAnalysis &AA) {
   if (!PollyUseRuntimeAliasChecks)
     return;
 
   if (buildAliasGroups(AA))
     return;
 
   // If a problem occurs while building the alias groups we need to delete
   // this SCoP and pretend it wasn't valid in the first place. To this end
   // we make the assumed context infeasible.
-  addAssumption(isl_set_empty(getParamSpace()));
+  addAssumption(ALIASING, isl_set_empty(getParamSpace()), DebugLoc());
 
   DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()
                << " could not be created as the number of parameters involved "
                   "is too high. The SCoP will be "
                   "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
                   "the maximal number of parameters but be advised that the "
                   "compile time might increase exponentially.\n\n");
 }
void Scop::hoistInvariantLoads() {
   for (LoadInst *LI : ScopRIL) {
     assert(LI && getRegion().contains(LI));
     ScopStmt *Stmt = getStmtForBasicBlock(LI->getParent());
     if (Stmt && Stmt->lookupAccessesFor(LI) != nullptr) {
       DEBUG(dbgs() << "\n\nWARNING: Load (" << *LI
                    << ") is required to be invariant but was not marked as "
                       "such. SCoP for "
                    << getRegion() << " will be dropped\n\n");
-      addAssumption(isl_set_empty(getParamSpace()));
+      addAssumption(INVARIANTLOAD, isl_set_empty(getParamSpace()),
+                    LI->getDebugLoc());
       return;
     }
   }
 }
 
 const ScopArrayInfo *
 Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
                                ArrayRef<const SCEV *> Sizes,
                                ScopArrayInfo::ARRAYKIND Kind) {
   auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)];
   if (!SAI) {
     SAI.reset(
         new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, Kind, this));
   } else {
     // In case of mismatching array sizes, we bail out by setting the run-time
     // context to false.
     if (!SAI->updateSizes(Sizes))
-      addAssumption(isl_set_empty(getParamSpace()));
+      addAssumption(DELINEARIZATION, isl_set_empty(getParamSpace()),
+                    DebugLoc());
   }
   return SAI.get();
 }
 
 const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr,
                                             ScopArrayInfo::ARRAYKIND Kind) {
   auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
   assert(SAI && "No ScopArrayInfo available for this base pointer");

 bool Scop::hasFeasibleRuntimeContext() const {
   isl_set *RuntimeCheckContext = getRuntimeCheckContext();
   RuntimeCheckContext = addNonEmptyDomainConstraints(RuntimeCheckContext);
   bool IsFeasible = !isl_set_is_empty(RuntimeCheckContext);
   isl_set_free(RuntimeCheckContext);
   return IsFeasible;
 }
 
-void Scop::addAssumption(__isl_take isl_set *Set) {
+static std::string toString(AssumptionKind Kind) {
+  switch (Kind) {
+  case ALIASING:
+    return "No-aliasing";
+  case INBOUNDS:
+    return "Inbounds";
+  case WRAPPING:
+    return "No-overflows";
+  case ERRORBLOCK:
+    return "No-error";
+  case INFINITELOOP:
+    return "Finite loop";
+  case INVARIANTLOAD:
+    return "Invariant load";
+  case DELINEARIZATION:
+    return "Delinearization";
+  }
+  llvm_unreachable("Unknown AssumptionKind!");
+}
+
+void Scop::trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set,
+                           DebugLoc Loc) {
+  if (isl_set_is_subset(Context, Set))
+    return;
+
+  if (isl_set_is_subset(AssumedContext, Set))
+    return;
+
+  auto &F = *getRegion().getEntry()->getParent();
+  std::string Msg = toString(Kind) + " assumption:\t" + stringFromIslObj(Set);
+  emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE, F, Loc, Msg);
+}
+
+void Scop::addAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
+                         DebugLoc Loc) {
+  trackAssumption(Kind, Set, Loc);
   AssumedContext = isl_set_intersect(AssumedContext, Set);
 
   int NSets = isl_set_n_basic_set(AssumedContext);
   if (NSets >= MaxDisjunctsAssumed) {
     isl_space *Space = isl_set_get_space(AssumedContext);
     isl_set_free(AssumedContext);
     AssumedContext = isl_set_empty(Space);
   }

polly/trunk/test/ScopInfo/remarks.ll

 ; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops < %s 2>&1| FileCheck %s
 ;
 ; CHECK: remark: test/ScopInfo/remarks.c:4:7: SCoP begins here.
+; CHECK: remark: test/ScopInfo/remarks.c:8:5: Finite loop assumption: [M, N, Debug] -> {  : M >= 0 or (M <= -2 and N <= 0) or (M = -1 and N <= 0) }
+; CHECK: remark: test/ScopInfo/remarks.c:13:7: No-error assumption: [M, N, Debug] -> {  : M <= -1 or (M >= 0 and N <= 0) or (Debug = 0 and M >= 0 and N >= 1) }
+; CHECK: remark: test/ScopInfo/remarks.c:9:15: Inbounds assumption: [M, N, Debug] -> {  : M <= 100 or (M >= 101 and N <= 0) }
+; CHECK: remark: <unknown>:0:0: No-overflows assumption: [N, M, Debug] -> {  : M <= 2147483647 - N and M >= -2147483648 - N }
 ; CHECK: remark: test/ScopInfo/remarks.c:9:18: Possibly aliasing pointer, use restrict keyword.
 ; CHECK: remark: test/ScopInfo/remarks.c:9:33: Possibly aliasing pointer, use restrict keyword.
 ; CHECK: remark: test/ScopInfo/remarks.c:9:15: Possibly aliasing pointer, use restrict keyword.
 ; CHECK: remark: test/ScopInfo/remarks.c:14:3: SCoP ends here.
 ; CHECK: remark: test/ScopInfo/remarks.c:19:3: SCoP begins here.
+; CHECK: remark: test/ScopInfo/remarks.c:21:11: Invariant load assumption: [tmp] -> {  : 1 = 0 }
 ; CHECK: remark: test/ScopInfo/remarks.c:22:16: SCoP ends here but was dismissed.
 ;
 ;    #include <stdio.h>
 ;
 ;    void valid(int *A, int *B, int N, int M, int C[100][100], int Debug) {
 ;      if (N + M == -1)
 ;        C[0][0] = 0;
 ;