[ScopHelper] Provide support for recognising collective invariant loads

[cs15btech11044]

Summary

This patch aims to provide support for detecting load patterns which are collectively invariant but right now isHoistableLoad() is checking each load instruction individually which cannot detect the load pattern as a whole.

[Meinersbur]

[serious] Could you add a test-case?

If I understand this correctly, this matches a specific pattern that mark a load as invariant if its address is also invariant.

[serious] As implemented, it is not stable since it depends on the order of in which LoadInsts are added to RequiredILS/isHoistableLoad being called. I.e. if isHoistableLoad is called on an address which has not yet been added to RequiredILS, it will be rejected.

[serious] It is also very specific to the address being computed using a single GEP instruction. Consider using ScalarEvolution to see that the address does not depend on an iteration counter or instruction inside the loop.

include/polly/Support/ScopHelper.h

394 ↗

(On Diff #150750)

[serious] The doxygen comment should also cover the added parameter.

lib/Support/ScopHelper.cpp

450 ↗

(On Diff #150750)

[style] Please name variable according to the LLVM coding standard.

Consider adding a comment about what this code is doing.

451 ↗

(On Diff #150750)

[style] if (auto *prev_inst = dyn_cast<GetElementPtrInst>(Ptr))

455 ↗

(On Diff #150750)

[style] Use a C++ foreach or a standard library function.

[philip.pfaffe]

As I mentioned in person: Instead of detecting this specific pattern, would it be possible to treat this as a fixpoint iteration? I.e., maintain a set of undecided address sources and keep shrinking it until only the non-invariant ones remein.

[cs15btech11044]

Updates made in this patch:

1. Implemented @philip.pfaffe 's fixed-point iteration idea to decide the invariant loads, which also solves the instability issue of the previous approach.
2. Added Doxygen comment for the newly introduced parameter.
3. Renamed the temporary variables according to LLVM standards.
4. Used foreach for iterating over the invariant load set.

[philip.pfaffe]

lib/Analysis/ScopDetection.cpp

1168 ↗

(On Diff #152269)

Why do you break on the first invariant load? Why not mark all hoistables in one go?

[cs15btech11044]

lib/Analysis/ScopDetection.cpp

1168 ↗

(On Diff #152269)

As soon as it is decided that a load is invariant, it is put in a set and we restart this process. This would ensure invariant loads which are collective(i.e a load depending on a previous invariant load instruction), if they appear out-of-order during iteration, we still detect it as invariant.

[philip.pfaffe]

lib/Analysis/ScopDetection.cpp

1168 ↗

(On Diff #152269)

The early break causes the loop to restart every time an invariant load is detected, even if loads are _not_ collective.

lib/Support/ScopHelper.cpp

450 ↗

(On Diff #150750)

Variable names should be ProudCamelCase.

[philip.pfaffe]

lib/Support/ScopHelper.cpp

455 ↗

(On Diff #150750)

Why are you looping at all? This is a RequiredILS is a set, just call O(1) count().

[cs15btech11044]

Updates made to this diff:

1. Addressed Phillip's concerns.
2. Some more variable name changes.
3. Minor updates to the fixed-point iteration approach.

[philip.pfaffe]

This is starting to look good! Only cosmetic nits left.

The testcase is still missing though.

lib/Analysis/ScopDetection.cpp

1170 ↗

(On Diff #152452)

This should be removed.

lib/Support/ScopHelper.cpp

446 ↗

(On Diff #152452)

RequiredILS should be const&.

More bikeshed: Why 'Required'? I'd consider 'KnownInvariantLoads' to be more apt, what do you think?

[bollu]

lib/Analysis/ScopDetection.cpp

1155 ↗

(On Diff #152452)

consider const unsigned int? Also, I prefer a name like CurrentVariantSize and CurrentInvariantSize, since this indicates that the sizes will be changing soon after.

[cs15btech11044]

Updates in this patch:

1. Added a test case
2. Removed // break
3. Added const to variables which do not change.

[bollu]

test/ScopDetect/collective_invariant_loads.ll

28 ↗

(On Diff #152465)

We can get rid of many of these type definitions, please remove the unnecesasary ones.

47 ↗

(On Diff #152465)

We can probably rename _array_DefaultRectangularArr_2_int64_t_F__real64_int64_t to something shorter like array_ty

51 ↗

(On Diff #152465)

Can we give the variables sane names? If it's too much work, don't bother

81 ↗

(On Diff #152465)

Please remove un-necessary metadata

[cs15btech11044]

lib/Support/ScopHelper.cpp

446 ↗

(On Diff #152452)

I agree. It sounds apter here.

[cs15btech11044]

Refined the test case according to the comments.

[bollu]

Also, please run the file through instnamer. That way, we will have "named" instructions and not "numbered" instructions. This is useful to modify the testcase in the future (it is less brittle): "numbered" instructions must be sequential, while named instructions need to be.

Hence, we try to keep all of our testcases with named instructions.

test/ScopDetect/collective_invariant_loads.ll

1 ↗

(On Diff #152478)

Please remove unnecessary options. Simply opt %s -polly-scops -polly-invariant-load-hositing -analyze | FileCheck %s should be enough?

That way, we can actually pattern match for the invariant loads.

Please make the CHECK line check for the invariant loads, like this

Pinging @grosser, @Meinersbur and @philip.pfaffe if there is a nicer way to test for this?

37 ↗

(On Diff #152478)

I think tbaa metadata can also be removed.

68 ↗

(On Diff #152478)

Do we actually need all of this metadata? I believe we can safely remove all of this

[cs15btech11044]

test/ScopDetect/collective_invariant_loads.ll

68 ↗

(On Diff #152478)

Does that apply for !0 and !1 as well?

[cs15btech11044]

Addressed all the comments related to the test case.

[philip.pfaffe]

There is still some clutter left, such as irrelevant metadata, a function declaration, and some computations, such as the value stored to memory.

[cs15btech11044]

Addressed Philip's concerns and removed unnecessary declarations and instructions.

[cs15btech11044]

Removed unnecessary BB's in the test case.

[philip.pfaffe]

Thanks, LGTM!

[cs15btech11044]

Added comments in ScopHelper.cpp explaining the purpose of the new code.

[Meinersbur]

I tried to make a test case for what I tried to explain during the phone call:

collective_invariant_loads2.ll3 KBDownload

The different address levels are different alias sets due to the -scoped-noalias metadata. These have to be MayAlias sets otherwise there is no reason to check for aliasing (this are what the dummy loads are for). Next, the last load (%tmp9) has to be processed first, before the load its address depends on (%tmp5) is known to be invariant. I put the loads in reverse order in the source to be iterated over in the order reverse of how it is executed.

Unfortunately this does not work, the block iteration comes from RegionInfo, which iterates in depth-first order. This should guarantee that dominators (where the invariant address is loaded) are visited before the block that loads from that address. This is, unless we also support invariant PHINodes, there is probably no counterexample. Still, depending in the check order is not robust, but no pressing issue.

I found a correctness issue which I marked with [serious]. Because of this, I mark the patch as "request changes" to overwrite the "Accepted" status.

lib/Analysis/ScopDetection.cpp

1154 ↗

(On Diff #152726)

Could you add comment(s) for this code as well?

lib/Support/ScopHelper.cpp

449–450 ↗

(On Diff #152726)

polly-check-format will complain about two consecutive empty lines.

451–453 ↗

(On Diff #152726)

Could you reformulate this? It sounds like the previous load being invariant is a necessary condition. Also, could you add a TODO about avoiding the pattern matching.

Suggestion:

An LoadInst is hoistable if the address it is loading from is also invariant; in this case: another invariant load (whether that address is also not written to has to be checked separately).
TODO: The only checks for a LoadInst->GetElementPtrInst->LoadInst pattern generated by the Chapel frontend, but generally this applies for any chain of instruction that does not also depend on any induction variable.

[serious] While writing this, I noticed that the pattern checked is not sufficient. The index argument could be an induction variable, meaning that the address loaded from changes in every iteration, i.e. the load is not invariant.

[cs15btech11044]

Strengthened the condition for pattern matching and added the required comments.

[philip.pfaffe]

lib/Support/ScopHelper.cpp

462 ↗

(On Diff #152856)

Don't use almost-always-auto please.

465 ↗

(On Diff #152856)

No this doesn't work.

Consider this:

struct A {
int a[M][N];
}
struct A a[L];

for (int i = 0; i < N; ++i)
  for (int j = 0; j < M; ++i)
      for (int k = 0; k < L; ++k)
          a[k].a[j][i] = 8;

You can't make assumptions about the order of GEP indices wrt. surrounding loops.

[cs15btech11044]

Improved the patch, which now analyzes every GEP index for all the nested loops.

[philip.pfaffe]

lib/Support/ScopHelper.cpp

465 ↗

(On Diff #152866)

This can be greatly simplified by calling Loop::isLoopInvariant for Val on the top-level-loop of the region, which you get from Region::outermostLoopInRegion. That makes this a one-liner.

[cs15btech11044]

Simplified the GEP index checks by just checking invariant property at the outermost loop.

[philip.pfaffe]

OK, this looks good! You haven't addressed Micheal's testcase yet for the invariant cascade crossing alias set boundaries. For the sake of progress IMO it's okay to leave a TODO and address it in a followup change. @Meinersbur what do you think?

lib/Support/ScopHelper.cpp

453 ↗

(On Diff #152871)

Unmatched parenthesis

[Meinersbur]

In D48026#1143538, @philip.pfaffe wrote:

For the sake of progress IMO it's okay to leave a TODO and address it in a followup change. @Meinersbur what do you think?

Agreed.

lib/Support/ScopHelper.cpp

461 ↗

(On Diff #152871)

[style] Do not evaluate something invariant in the loop exit condition

[serious] Off-by-one-error: getNumIndices() returns getNumOperands() - 1, so you are skipping the last element here.

[style] Could use a foreach-loop: for (const Use &Val : llvm::drop_begin(this->operands(), 1)), but this could require D48598.

467–468 ↗

(On Diff #152871)

[style] Instead of using a flag, this pattern of "find element that matches a condition" can be simplified by outlining the loop into a hasVariantIndex function that return true; if such an element is found and return false; after the loop. Alterntively, std::any_of with a lambda could be useful.

(I don't require this change for me accept this patch)

[cs15btech11044]

lib/Support/ScopHelper.cpp

461 ↗

(On Diff #152871)

If the foreach loop requires D48598, I would wait till it gets committed to LLVM repository. This change could be taken up in the tentative follow-up patch.

[cs15btech11044]

Outlined the loop as per @Meinersbur 's suggestion and corrected the loop header responsible for checking invariant nature of the GEP indices.

[Meinersbur]

All tests passed for me. I also tried your test case with -polly-use-runtime-alias-checks=false -polly-ignore-aliasing and it still works with codegen (I had doubts that if your additional code is not executing, the chain of address loads would not end up in RequiredILs).

Before the patch is good to be landed, please address the [serious] remark.

lib/Analysis/ScopDetection.cpp

1146 ↗

(On Diff #153012)

[nit] Unrelated change

lib/Support/ScopHelper.cpp

445–446 ↗

(On Diff #153012)

[remark] hasVariantIndex is only used in this file, so a declaration static bool hasVariantIndex(... (or a lambda) without anything added to the header file would have been enough.

452–454 ↗

(On Diff #153012)

[nit] We usually do not enclose a single statement following an if in braces.

test/ScopDetect/collective_invariant_loads.ll

1 ↗

(On Diff #153012)

[serious] %loadPolly missing

[style] [[ https://www.llvm.org/docs/TestingGuide.html#fragile-tests | Use < %s ]]

[suggestion] 2>&1 is unnecessary

22 ↗

(On Diff #153012)

[style] The target triple. ModuleID and source_filename lines can be removed; The target triple in particular can cause the test to fail if LLVM_TARGETS_TO_BUILD does not include X86.

[cs15btech11044]

Used for-each loop with llvm::drop_begin() in hasVariantIndex().
Removed hasVariantIndex()definition from header file and made it static.
Added %loadPolly in the test case and modified the run statement.

[Meinersbur]

Thanks for all the changes.

@philip.pfaffe Since Sahil does not have commit rights (yet), do you want to land it?

Michael

polly/trunk/include/polly/Support/ScopHelper.h

 
 /// Check if @p LInst can be hoisted in @p R.
 ///
 /// @param LInst The load to check.
 /// @param R     The analyzed region.
 /// @param LI    The loop info.
 /// @param SE    The scalar evolution analysis.
 /// @param DT    The dominator tree of the function.
+/// @param KnownInvariantLoads The invariant load set.
 ///
 /// @return True if @p LInst can be hoisted in @p R.
 bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI,
-                     llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT);
+                     llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT,
+                     const InvariantLoadsSetTy &KnownInvariantLoads);
 
 /// Return true iff @p V is an intrinsic that we ignore during code
 ///        generation.
 bool isIgnoredIntrinsic(const llvm::Value *V);
 
 /// Check whether a value an be synthesized by the code generator.
 ///
 /// Some value will be recalculated only from information that is code generated

polly/trunk/lib/Analysis/ScopDetection.cpp

bool ScopDetection::onlyValidRequiredInvariantLoads(
   for (LoadInst *Load : RequiredILS) {
     // If we already know a load has been accepted as required invariant, we
     // already run the validation below once and consequently don't need to
     // run it again. Hence, we return early. For certain test cases (e.g.,
     // COSMO this avoids us spending 50% of scop-detection time in this
     // very function (and its children).
     if (Context.RequiredILS.count(Load))
       continue;
-
-    if (!isHoistableLoad(Load, CurRegion, LI, SE, DT))
+    if (!isHoistableLoad(Load, CurRegion, LI, SE, DT, Context.RequiredILS))
       return false;
 
     for (auto NonAffineRegion : Context.NonAffineSubRegionSet) {
       if (isSafeToLoadUnconditionally(Load->getPointerOperand(),
                                       Load->getAlignment(), DL))
         continue;
 
       if (NonAffineRegion->contains(Load) &&
for (const SCEV *DelinearizedSize : Sizes) {
     if (!isAffine(DelinearizedSize, Scope, Context)) {
       Sizes.clear();
       break;
     }
     if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
       auto *V = dyn_cast<Value>(Unknown->getValue());
       if (auto *Load = dyn_cast<LoadInst>(V)) {
         if (Context.CurRegion.contains(Load) &&
-            isHoistableLoad(Load, CurRegion, LI, SE, DT))
+            isHoistableLoad(Load, CurRegion, LI, SE, DT, Context.RequiredILS))
           Context.RequiredILS.insert(Load);
         continue;
       }
     }
     if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion, Scope, false,
                                   Context.RequiredILS))
       return invalid<ReportNonAffineAccess>(
           Context, /*Assert=*/true, DelinearizedSize,
bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF,
   if (!AS.isMustAlias()) {
     if (PollyUseRuntimeAliasChecks) {
       bool CanBuildRunTimeCheck = true;
       // The run-time alias check places code that involves the base pointer at
       // the beginning of the SCoP. This breaks if the base pointer is defined
       // inside the scop. Hence, we can only create a run-time check if we are
       // sure the base pointer is not an instruction defined inside the scop.
       // However, we can ignore loads that will be hoisted.
+
+      InvariantLoadsSetTy VariantLS, InvariantLS;
+      // In order to detect loads which are dependent on other invariant loads
+      // as invariant, we use fixed-point iteration method here i.e we iterate
+      // over the alias set for arbitrary number of times until it is safe to
+      // assume that all the invariant loads have been detected
+      while (1) {
+        const unsigned int VariantSize = VariantLS.size(),
+                           InvariantSize = InvariantLS.size();
+
         for (const auto &Ptr : AS) {
           Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
           if (Inst && Context.CurRegion.contains(Inst)) {
             auto *Load = dyn_cast<LoadInst>(Inst);
-          if (Load && isHoistableLoad(Load, Context.CurRegion, LI, SE, DT)) {
-            Context.RequiredILS.insert(Load);
+            if (Load && InvariantLS.count(Load))
               continue;
-          }
+            if (Load && isHoistableLoad(Load, Context.CurRegion, LI, SE, DT,
+                                        InvariantLS)) {
+              if (VariantLS.count(Load))
+                VariantLS.remove(Load);
+              Context.RequiredILS.insert(Load);
+              InvariantLS.insert(Load);
+            } else {
+              CanBuildRunTimeCheck = false;
+              VariantLS.insert(Load);
+            }
+          }
 
-          CanBuildRunTimeCheck = false;
+        if (InvariantSize == InvariantLS.size() &&
+            VariantSize == VariantLS.size())
           break;
-        }
-      }
 
       if (CanBuildRunTimeCheck)
         return true;
     }
     return invalid<ReportAlias>(Context, /*Assert=*/true, Inst, AS);
   }
 
   return true;

polly/trunk/lib/Support/ScopHelper.cpp

 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/ScopHelper.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/SCEVValidator.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
+#include "llvm/Analysis/RegionInfoImpl.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
   }
 
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
     return SI->getCondition();
 
   return nullptr;
 }
 
+static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,
+                            ScalarEvolution &SE) {
+  for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {
+    const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L);
+    Loop *OuterLoop = R.outermostLoopInRegion(L);
+    if (!SE.isLoopInvariant(PtrSCEV, OuterLoop))
+      return true;
+  }
+  return false;
+}
+
 bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
-                            ScalarEvolution &SE, const DominatorTree &DT) {
+                            ScalarEvolution &SE, const DominatorTree &DT,
+                            const InvariantLoadsSetTy &KnownInvariantLoads) {
   Loop *L = LI.getLoopFor(LInst->getParent());
   auto *Ptr = LInst->getPointerOperand();
+
+  // A LoadInst is hoistable if the address it is loading from is also
+  // invariant; in this case: another invariant load (whether that address
+  // is also not written to has to be checked separately)
+  // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst
+  // pattern generated by the Chapel frontend, but generally this applies
+  // for any chain of instruction that does not also depend on any
+  // induction variable
+  if (auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) {
+    if (!hasVariantIndex(GepInst, L, R, SE)) {
+      if (auto *DecidingLoad =
+              dyn_cast<LoadInst>(GepInst->getPointerOperand())) {
+        if (KnownInvariantLoads.count(DecidingLoad))
+          return true;
+      }
+    }
+  }
+
   const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
   while (L && R.contains(L)) {
     if (!SE.isLoopInvariant(PtrSCEV, L))
       return false;
     L = L->getParentLoop();
   }
 
   for (auto *User : Ptr->users()) {

polly/trunk/test/ScopDetect/collective_invariant_loads.ll

+; RUN: opt %loadPolly -polly-scops -polly-invariant-load-hoisting -analyze < %s | FileCheck %s
+
+;CHECK:     Function: test_init_chpl
+;CHECK-NEXT:     Region: %bb1---%bb16
+;CHECK-NEXT:     Max Loop Depth:  2
+;CHECK-NEXT:     Invariant Accesses: {
+;CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+;CHECK-NEXT:                 [tmp5] -> { Stmt_bb2[i0, i1] -> MemRef_arg[1] };
+;CHECK-NEXT:             Execution Context: [tmp5] -> {  :  }
+;CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+;CHECK-NEXT:                 [tmp5] -> { Stmt_bb2[i0, i1] -> MemRef_tmp3[9] };
+;CHECK-NEXT:             Execution Context: [tmp5] -> {  :  }
+;CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+;CHECK-NEXT:                 [tmp5] -> { Stmt_bb2[i0, i1] -> MemRef_tmp3[2] };
+;CHECK-NEXT:             Execution Context: [tmp5] -> {  :  }
+;CHECK-NEXT:     }
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%array_ty = type { i64, %array_ptr*, i8 }
+%array_ptr = type { [2 x i64], [2 x i64], [2 x i64], i64, i64, double*, double*, i8 }
+
+; Function Attrs: noinline
+define weak dso_local void @test_init_chpl(%array_ty* nonnull %arg) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb14, %bb
+  %.0 = phi i64 [ 0, %bb ], [ %tmp15, %bb14 ]
+  br label %bb2
+
+bb2:                                              ; preds = %bb2, %bb1
+  %.01 = phi i64 [ 0, %bb1 ], [ %tmp13, %bb2 ]
+  %tmp = getelementptr inbounds %array_ty, %array_ty* %arg, i64 0, i32 1
+  %tmp3 = load %array_ptr*, %array_ptr** %tmp, align 8
+  %tmp4 = getelementptr inbounds %array_ptr, %array_ptr* %tmp3, i64 0, i32 1, i64 0
+  %tmp5 = load i64, i64* %tmp4, align 8
+  %tmp6 = mul nsw i64 %tmp5, %.0
+  %tmp7 = add nsw i64 %tmp6, %.01
+  %tmp8 = getelementptr inbounds %array_ptr, %array_ptr* %tmp3, i64 0, i32 6
+  %tmp9 = load double*, double** %tmp8, align 8
+  %tmp10 = getelementptr inbounds double, double* %tmp9, i64 %tmp7
+  store double 13.0, double* %tmp10, align 8
+  %tmp13 = add nuw nsw i64 %.01, 1
+  %exitcond = icmp ne i64 %tmp13, 1000
+  br i1 %exitcond, label %bb2, label %bb14
+
+bb14:                                             ; preds = %bb2
+  %tmp15 = add nuw nsw i64 %.0, 1
+  %exitcond8 = icmp ne i64 %tmp15, 1000
+  br i1 %exitcond8, label %bb1, label %bb16
+
+bb16:                                             ; preds = %bb14
+  ret void
+}