[Polly][WIP] Add polly profitable source annotation

[jdoerfert]

Summary

Profitable annotations can be placend in the source via:
  __builtin_assume(__polly_profitable == X)
where X has to be the constant 0 (=unprofitable) or 1 (=profitable) and
__polly_profitable a global variable.

If multiple annotations dominate a region, the number of
"profitable"/"unprofitable" annotations is used to decide what to do.

-- Missing unit tests

[jdoerfert]

Added test case

[grosser]

I never wrote this down, but I believe adding writes to global constants just to annotate the source code is not the right approach. As this patch is old I suggest to open a new review in case this becomes interesting again. I resign from this review to empy my queue.

include/polly/ScopDetection.h

 #include "llvm/Pass.h"
 #include <map>
 #include <memory>
 #include <set>
 
 using namespace llvm;
 
 namespace llvm {
+class AssumptionCache;
 class RegionInfo;
 class Region;
 class LoopInfo;
 class Loop;
 class ScalarEvolution;
 class SCEV;
 class SCEVAddRecExpr;
 class SCEVUnknown;
private:
 
   /// @brief Analysis passes used.
   //@{
   const DominatorTree *DT;
   ScalarEvolution *SE;
   LoopInfo *LI;
   RegionInfo *RI;
   AliasAnalysis *AA;
+  AssumptionCache *AC;
   //@}
 
   /// @brief Map to remember detection contexts for valid regions.
   using DetectionContextMapTy = DenseMap<const Region *, DetectionContext>;
   mutable DetectionContextMapTy DetectionContextMap;
 
   // Remember a list of errors for every region.
   mutable RejectLogsContainer RejectLogs;
private:
   /// @param Context The context of scop detection.
   ///
   /// @return True if ISL can compute the trip count of the loop.
   bool canUseISLTripCount(Loop *L, DetectionContext &Context) const;
 
   /// @brief Print the locations of all detected scops.
   void printLocations(llvm::Function &F);
 
+  /// @brief Get the users profitable annotation for the given region if any.
+  ///
+  /// Profitable annotations can be placend in the source via:
+  ///   __builtin_assume(__polly_profitable == X)
+  /// where X has to be the constant 0 (=unprofitable) or 1 (=profitable) and
+  /// __polly_profitable a global variable.
+  ///
+  /// @returns >0/<0 if annotatations suggest profitable/non-profitable, or 0.
+  int getProfitableAnnotation(const Region &R) const;
+
   /// @brief Track diagnostics for invalid scops.
   ///
   /// @param Context The context of scop detection.
   /// @param Assert Throw an assert in verify mode or not.
   /// @param Args Argument list that gets passed to the constructor of RR.
   template <class RR, typename... Args>
   inline bool invalid(DetectionContext &Context, bool Assert,
                       Args &&... Arguments) const;

lib/Analysis/ScopDetection.cpp

 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopDetectionDiagnostic.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopLocation.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
   }
 
   if (!hasAffineMemoryAccesses(Context))
     return false;
 
   return true;
 }
 
+int ScopDetection::getProfitableAnnotation(const Region &R) const {
+  unsigned One = 0, Zero = 0;
+  for (auto &Assumption : AC->assumptions()) {
+    auto *CI = dyn_cast_or_null<CallInst>(Assumption);
+    if (!CI || CI->getNumArgOperands() != 1)
+      continue;
+    if (!DT->dominates(CI->getParent(), R.getEntry()))
+      continue;
+    auto *ICmp = dyn_cast<ICmpInst>(CI->getArgOperand(0));
+    if (!ICmp || !ICmp->isEquality())
+      continue;
+    auto *L = dyn_cast<LoadInst>(ICmp->getOperand(0));
+    auto *C = dyn_cast<ConstantInt>(ICmp->getOperand(1));
+    if (!L || !C || !(C->isZero() || C->isOne()))
+      continue;
+    auto *P = dyn_cast<GlobalVariable>(L->getPointerOperand());
+    if (!P || !P->getName().equals("__polly_profitable"))
+      continue;
+    One += C->isOne();
+    Zero += C->isZero();
+  }
+  return One - Zero;
+}
+
 bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
+  int ProfitableAnnotation = getProfitableAnnotation(CurRegion);
+  if (ProfitableAnnotation < 0) {
+    DEBUG(dbgs() << "Annotated unprofitable\n");
+    return false;
+  }
 
   if (CurRegion.isTopLevelRegion()) {
     DEBUG(dbgs() << "Top level region is invalid\n");
     return false;
   }
 
   if (!CurRegion.getEntry()->getName().count(OnlyRegion)) {
     DEBUG({
bool ScopDetection::isValidRegion(DetectionContext &Context) const {
 
   // SCoP cannot contain the entry block of the function, because we need
   // to insert alloca instruction there when translate scalar to array.
   if (CurRegion.getEntry() ==
       &(CurRegion.getEntry()->getParent()->getEntryBlock()))
     return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());
 
   int NumLoops = countBeneficialLoops(&CurRegion);
-  if (!PollyProcessUnprofitable && NumLoops < 2)
+  if (!PollyProcessUnprofitable && ProfitableAnnotation == 0 && NumLoops < 2)
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 
   if (!allBlocksValid(Context))
     return false;
 
   // We can probably not do a lot on scops that only write or only read
   // data.
-  if (!PollyProcessUnprofitable && (!Context.hasStores || !Context.hasLoads))
+  if (!PollyProcessUnprofitable && ProfitableAnnotation == 0 &&
+      (!Context.hasStores || !Context.hasLoads))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 
   // Check if there are sufficent non-overapproximated loops.
   int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size();
-  if (!PollyProcessUnprofitable && NumAffineLoops < 2)
+  if (!PollyProcessUnprofitable && ProfitableAnnotation == 0 &&
+      NumAffineLoops < 2)
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 
   DEBUG(dbgs() << "OK\n");
   return true;
 }
 
 void ScopDetection::markFunctionAsInvalid(Function *F) const {
   F->addFnAttr(PollySkipFnAttr);
else {
       }
     }
   }
 }
 
 bool ScopDetection::runOnFunction(llvm::Function &F) {
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
-  if (!PollyProcessUnprofitable && LI->empty())
+  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  if (!PollyProcessUnprofitable && LI->empty() && AC->assumptions().empty())
     return false;
 
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   Region *TopRegion = RI->getTopLevelRegion();
 
   releaseMemory();
if (!VerifyScops)
     return;
 
   for (const Region *R : ValidRegions)
     verifyRegion(*R);
 }
 
 void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<ScalarEvolutionWrapperPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   // We also need AA and RegionInfo when we are verifying analysis.
   AU.addRequiredTransitive<AAResultsWrapperPass>();
   AU.addRequiredTransitive<RegionInfoPass>();
   AU.setPreservesAll();
 }
 

 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
 
 INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect",
                       "Polly - Detect static control parts (SCoPs)", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_END(ScopDetection, "polly-detect",
                     "Polly - Detect static control parts (SCoPs)", false, false)

test/ScopDetect/profitable_source_annotation.ll

+; RUN: opt %loadPolly -polly-detect -polly-process-unprofitable=false -analyze < %s | FileCheck %s
+;
+; CHECK: Valid
+;
+;    int __polly_profitable;
+;    void f(int *A) {
+;      __builtin_assume(__polly_profitable == 1);
+;      for (int i = 0; i < 100; i++)
+;        A[i] = i;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@__polly_profitable = common global i32 0, align 4
+
+define void @f(i32* %A) {
+entry:
+  %tmp = load i32, i32* @__polly_profitable, align 4
+  %cmp = icmp eq i32 %tmp, 1
+  call void @llvm.assume(i1 %cmp)
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = trunc i64 %indvars.iv to i32
+  store i32 %tmp1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.assume(i1) #1