[Polly][ForwardOpTree] Allow out-of-quota in examination part of forwardTree.

[Meinersbur]

Summary

Computing the reaching definition in forwardTree() can take a long time if the coefficients are large. When the forwarding is carried-out (doIt==true), forwardTree() must execute entirely or not at all to get a consistent output, which means we cannot just allow out-of-quota errors to happen in the middle of the processing.

We introduce the class IslQuotaScope which allows to opt-in code that is conformant and has been tested with out-of-quota events. In case of ForwardOpTree, out-of-quota is allowed during the operand tree examination, but not during the transformation. The same forwardTree() recursion is used for examination and execution, meaning that the reaching definition has already been computed in the examination tree walk and cached for reuse in the transformation tree walk.

This should fix the time-out of grtestutils.ll of the asop buildbot. If the compilation still takes too long, we can reduce the max-operations allows for -polly-optree.

[grosser]

LGTM. Thank you!

lib/Transform/ForwardOpTree.cpp

267 ↗

(On Diff #115678)

Maybe use the real type instead of auto?

450 ↗

(On Diff #115678)

Maybe use the real type instead of auto?

polly/trunk/include/polly/Support/GICHelper.h

 
 inline llvm::DiagnosticInfoOptimizationBase &
 operator<<(llvm::DiagnosticInfoOptimizationBase &OS,
            const isl::union_map &Obj) {
   OS << Obj.to_str();
   return OS;
 }
 
+/// Scope guard for code that allows arbitrary isl function to return an error
+/// if the max-operations quota exceeds.
+///
+/// This allows to opt-in code sections that have known long executions times.
+/// code not in a hot path can continue to assume that no unexpected error
+/// occurs.
+///
+/// This is typically used inside a nested IslMaxOperationsGuard scope. The
+/// IslMaxOperationsGuard defines the number of allowed base operations for some
+/// code, IslQuotaScope defines where it is allowed to return an error result.
+class IslQuotaScope {
+  isl_ctx *IslCtx;
+  int OldOnError;
+
+public:
+  IslQuotaScope() : IslCtx(nullptr) {}
+  IslQuotaScope(const IslQuotaScope &) = delete;
+  IslQuotaScope(IslQuotaScope &&Other)
+      : IslCtx(Other.IslCtx), OldOnError(Other.OldOnError) {
+    Other.IslCtx = nullptr;
+  }
+  const IslQuotaScope &operator=(IslQuotaScope &&Other) {
+    std::swap(this->IslCtx, Other.IslCtx);
+    std::swap(this->OldOnError, Other.OldOnError);
+    return *this;
+  }
+
+  /// Enter a quota-aware scope.
+  ///
+  /// Should not be used directly. Use IslMaxOperationsGuard::enter() instead.
+  explicit IslQuotaScope(isl_ctx *IslCtx, unsigned long LocalMaxOps)
+      : IslCtx(IslCtx) {
+    assert(IslCtx);
+    assert(isl_ctx_get_max_operations(IslCtx) == 0 && "Incorrect nesting");
+    if (LocalMaxOps == 0) {
+      this->IslCtx = nullptr;
+      return;
+    }
+
+    OldOnError = isl_options_get_on_error(IslCtx);
+    isl_options_set_on_error(IslCtx, ISL_ON_ERROR_CONTINUE);
+    isl_ctx_reset_error(IslCtx);
+    isl_ctx_set_max_operations(IslCtx, LocalMaxOps);
+  }
+
+  ~IslQuotaScope() {
+    if (!IslCtx)
+      return;
+
+    assert(isl_ctx_get_max_operations(IslCtx) > 0 && "Incorrect nesting");
+    assert(isl_options_get_on_error(IslCtx) == ISL_ON_ERROR_CONTINUE &&
+           "Incorrect nesting");
+    isl_ctx_set_max_operations(IslCtx, 0);
+    isl_options_set_on_error(IslCtx, OldOnError);
+  }
+
+  /// Return whether the current quota has exceeded.
+  bool hasQuotaExceeded() const {
+    if (!IslCtx)
+      return false;
+
+    return isl_ctx_last_error(IslCtx) == isl_error_quota;
+  }
+};
+
 /// Scoped limit of ISL operations.
 ///
 /// Limits the number of ISL operations during the lifetime of this object. The
 /// idea is to use this as an RAII guard for the scope where the code is aware
 /// that ISL can return errors even when all input is valid. After leaving the
 /// scope, it will return to the error setting as it was before. That also means
 /// that the error setting should not be changed while in that scope.
 ///
 /// Such scopes are not allowed to be nested because the previous operations
 /// counter cannot be reset to the previous state, or one that adds the
 /// operations while being in the nested scope. Use therefore is only allowed
 /// while currently a no operations-limit is active.
 class IslMaxOperationsGuard {
 private:
   /// The ISL context to set the operations limit.
   ///
   /// If set to nullptr, there is no need for any action at the end of the
   /// scope.
   isl_ctx *IslCtx;
 
-  /// Old OnError setting; to reset to when the scope ends.
-  int OldOnError;
+  /// Maximum number of operations for the scope.
+  unsigned long LocalMaxOps;
+
+  /// When AutoEnter is enabled, holds the IslQuotaScope object.
+  IslQuotaScope TopLevelScope;
 
 public:
   /// Enter a max operations scope.
   ///
   /// @param IslCtx      The ISL context to set the operations limit for.
   /// @param LocalMaxOps Maximum number of operations allowed in the
   ///                    scope. If set to zero, no operations limit is enforced.
-  IslMaxOperationsGuard(isl_ctx *IslCtx, unsigned long LocalMaxOps)
-      : IslCtx(IslCtx) {
+  /// @param AutoEnter   If true, automatically enters an IslQuotaScope such
+  ///                    that isl operations may return quota errors
+  ///                    immediately. If false, only starts the operations
+  ///                    counter, but isl does not return quota errors before
+  ///                    calling enter().
+  IslMaxOperationsGuard(isl_ctx *IslCtx, unsigned long LocalMaxOps,
+                        bool AutoEnter = true)
+      : IslCtx(IslCtx), LocalMaxOps(LocalMaxOps) {
     assert(IslCtx);
     assert(isl_ctx_get_max_operations(IslCtx) == 0 &&
            "Nested max operations not supported");
 
     if (LocalMaxOps == 0) {
       // No limit on operations; also disable restoring on_error/max_operations.
       this->IslCtx = nullptr;
       return;
     }
 
-    // Save previous state.
-    OldOnError = isl_options_get_on_error(IslCtx);
-
-    // Activate the new setting.
-    isl_ctx_set_max_operations(IslCtx, LocalMaxOps);
     isl_ctx_reset_operations(IslCtx);
-    isl_options_set_on_error(IslCtx, ISL_ON_ERROR_CONTINUE);
+    TopLevelScope = enter(AutoEnter);
   }
 
-  /// Leave the max operations scope.
-  ~IslMaxOperationsGuard() {
-    if (!IslCtx)
-      return;
+  /// Enter a scope that can handle out-of-quota errors.
+  ///
+  /// @param AllowReturnNull Whether the scoped code can handle out-of-quota
+  ///                        errors. If false, returns a dummy scope object that
+  ///                        does nothing.
+  IslQuotaScope enter(bool AllowReturnNull = true) {
+    return AllowReturnNull && IslCtx ? IslQuotaScope(IslCtx, LocalMaxOps)
+                                     : IslQuotaScope();
+  }
 
-    assert(isl_options_get_on_error(IslCtx) == ISL_ON_ERROR_CONTINUE &&
-           "Unexpected change of the on_error setting");
+  /// Return whether the current quota has exceeded.
+  bool hasQuotaExceeded() const {
+    if (!IslCtx)
+      return false;
 
-    // Return to the previous error setting.
-    isl_ctx_set_max_operations(IslCtx, 0);
-    isl_options_set_on_error(IslCtx, OldOnError);
+    return isl_ctx_last_error(IslCtx) == isl_error_quota;
   }
 };
 
 } // end namespace polly
 
 #endif

polly/trunk/lib/Transform/ForwardOpTree.cpp

 ///
 /// For a statement that requires a scalar value (through a value read
 /// MemoryAccess), see if its operand can be moved into the statement. If so,
 /// the MemoryAccess is removed and the all the operand tree instructions are
 /// moved into the statement. All original instructions are left in the source
 /// statements. The simplification pass can clean these up.
 class ForwardOpTreeImpl : ZoneAlgorithm {
 private:
+  /// Scope guard to limit the number of isl operations for this pass.
+  IslMaxOperationsGuard &MaxOpGuard;
+
   /// How many instructions have been copied to other statements.
   int NumInstructionsCopied = 0;
 
   /// Number of loads forwarded because their value was known.
   int NumKnownLoadsForwarded = 0;
 
   /// How many read-only accesses have been copied.
   int NumReadOnlyCopied = 0;
MustKnown.foreach_map([&](isl::map Map) -> isl::stat {
       Result = Map.lexmin();
       return isl::stat::error; // break
     });
 
     return Result;
   }
 
 public:
-  ForwardOpTreeImpl(Scop *S, LoopInfo *LI)
-      : ZoneAlgorithm("polly-optree", S, LI) {}
+  ForwardOpTreeImpl(Scop *S, LoopInfo *LI, IslMaxOperationsGuard &MaxOpGuard)
+      : ZoneAlgorithm("polly-optree", S, LI), MaxOpGuard(MaxOpGuard) {}
 
   /// Compute the zones of known array element contents.
   ///
   /// @return True if the computed #Known is usable.
   bool computeKnownValues() {
     isl::union_map MustKnown, KnownFromLoad, KnownFromInit;
 
     // Check that nothing strange occurs.
     collectCompatibleElts();
 
-    isl_ctx_reset_error(IslCtx.get());
     {
-      IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), MaxOps);
+      IslQuotaScope QuotaScope = MaxOpGuard.enter();
 
       computeCommon();
       Known = computeKnown(true, true);
 
       // Preexisting ValInsts use the known content analysis of themselves.
       Translator = makeIdentityMap(Known.range(), false);
     }
 
     if (!Known || !Translator) {
       assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);
-      KnownOutOfQuota++;
       Known = nullptr;
       Translator = nullptr;
       DEBUG(dbgs() << "Known analysis exceeded max_operations\n");
       return false;
     }
 
     KnownAnalyzed++;
     DEBUG(dbgs() << "All known: " << Known << "\n");
public:
   ///         FD_CanForwardTree if @p Inst is forwardable.
   ///         FD_DidForward     if @p DoIt was true.
   ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
                                       ScopStmt *UseStmt, Loop *UseLoop,
                                       isl::map UseToTarget, ScopStmt *DefStmt,
                                       Loop *DefLoop, isl::map DefToTarget,
                                       bool DoIt) {
     // Cannot do anything without successful known analysis.
-    if (Known.is_null())
+    if (Known.is_null() || Translator.is_null() || UseToTarget.is_null() ||
+        DefToTarget.is_null() || MaxOpGuard.hasQuotaExceeded())
       return FD_NotApplicable;
 
     LoadInst *LI = dyn_cast<LoadInst>(Inst);
     if (!LI)
       return FD_NotApplicable;
 
     // If the load is already in the statement, no forwarding is necessary.
     // However, it might happen that the LoadInst is already present in the
ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
     case FD_DidForward:
       assert(DoIt);
       break;
 
     default:
       llvm_unreachable("Shouldn't return this");
     }
 
+    IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
+
     // { DomainDef[] -> ValInst[] }
     isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);
 
     // { DomainTarget[] -> ValInst[] }
     isl::map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);
     isl::union_map TranslatedExpectedVal =
         isl::union_map(TargetExpectedVal).apply_range(Translator);
 
case VirtualUse::Inter:
         DefStmt = S->getStmtFor(Inst);
         if (!DefStmt)
           return FD_CannotForward;
       }
 
       DefLoop = LI->getLoopFor(Inst->getParent());
 
       if (DefToTarget.is_null() && !Known.is_null()) {
+        IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
+
         // { UseDomain[] -> DefDomain[] }
         isl::map UseToDef = computeUseToDefFlowDependency(UseStmt, DefStmt);
 
         // { DefDomain[] -> UseDomain[] -> TargetDomain[] } shortened to
         // { DefDomain[] -> TargetDomain[] }
         DefToTarget = UseToTarget.apply_domain(UseToDef);
         simplify(DefToTarget);
       }
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 
   bool runOnScop(Scop &S) override {
     // Free resources for previous SCoP's computation, if not yet done.
     releaseMemory();
 
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    Impl = llvm::make_unique<ForwardOpTreeImpl>(&S, &LI);
+
+    {
+      IslMaxOperationsGuard MaxOpGuard(S.getIslCtx(), MaxOps, false);
+      Impl = llvm::make_unique<ForwardOpTreeImpl>(&S, &LI, MaxOpGuard);
 
       if (AnalyzeKnown) {
         DEBUG(dbgs() << "Prepare forwarders...\n");
         Impl->computeKnownValues();
       }
 
       DEBUG(dbgs() << "Forwarding operand trees...\n");
       Impl->forwardOperandTrees();
 
+      if (MaxOpGuard.hasQuotaExceeded()) {
+        DEBUG(dbgs() << "Not all operations completed because of "
+                        "max_operations exceeded\n");
+        KnownOutOfQuota++;
+      }
+    }
+
     DEBUG(dbgs() << "\nFinal Scop:\n");
     DEBUG(dbgs() << S);
 
     // Update statistics
     auto ScopStats = S.getStatistics();
     NumValueWrites += ScopStats.NumValueWrites;
     NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
     NumPHIWrites += ScopStats.NumPHIWrites;