[Polly] Load hoisting of indirect loads

[gareevroman]

Summary

Invariant-load-hoisting pre-loads values before the execution of the SCoP itself to avoid loading the same value several times and also to make parameters (like array size) available in the isl sets/maps.

Currently, we cannot load-hoist from pointers that by themselves are defined within the SCoP, but are themselves invariant. The reason is inability of the scalar evolution used by isHoistableLoad to check invariance of the SCEV representing the load. If this is the case, we skip the check since the invariant load hoisting can handle it.

[Meinersbur]

All the callers of isHoistableLoad do add the load to Context.RequiredILS to ensure that the load is indeed preloaded (a precondition to be a SCoP). With this patch this is only done with the LoadInst itself, but not the loads it depends on.

In your test case it still happens anyway because hoistability/invariance is also checked individually for their base pointer to be invariant so that they get into the RequiredILS. However, by themselves they might not be required to be load-hoisted. This could result in the %tmp3 to be hoisted, but not %tmp2 or %tmp1.

Could you either add a comment explaining why the dependent loads are also always load-hoisted - or - also add the dependent loads to RequiredILS?

I tested your patch on the test-suite. Compilation of test-suite/MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/jidctfst.c does not finish.

[jdoerfert]

lib/Support/ScopHelper.cpp

440

1. This avoids the heuristic in line 447-467 completely [bad idea!].
2. You can just prevent the loop invariance check for loads (line 441-445) if the base pointer is a load. Invariant load hoisting should take care of the rest.

[grosser]

@gareevroman : Hi Roman, did you had a look at Johannes' reply. This might indeed be a good solution.

[gareevroman]

Hi,

thanks for the comments!

All the callers of isHoistableLoad do add the load to Context.RequiredILS to ensure that the load is indeed preloaded (a precondition to be a SCoP). With this patch this is only done with the LoadInst itself, but not the loads it depends on.
In your test case it still happens anyway because hoistability/invariance is also checked individually for their base pointer to be invariant so that they get into the RequiredILS. However, by themselves they might not be required to be load-hoisted. This could result in the %tmp3 to be hoisted, but not %tmp2 or %tmp1.
Could you either add a comment explaining why the dependent loads are also always load-hoisted - or - also add the dependent loads to RequiredILS?
I tested your patch on the test-suite. Compilation of test-suite/MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/jidctfst.c does not finish.

AFAIU, Johannes's approach doesn't cause the issue.

Johannes, could you please clarify how isHoistableLoad function works? I just want to make sure I understand it correctly:

1. It checks that the pointer operand of LInst is unchanging in the loops of region R.
2. Subsequently, it checks that there is no an instruction UserI from R that can modify the pointer operand and/or dominates all predecessors of the region exit of R.

Why should we check that UserI doesn't dominate all predecessors of the region exit of R?

[gareevroman]

In D31842#753366, @gareevroman wrote:

Hi,

thanks for the comments!

All the callers of isHoistableLoad do add the load to Context.RequiredILS to ensure that the load is indeed preloaded (a precondition to be a SCoP). With this patch this is only done with the LoadInst itself, but not the loads it depends on.
In your test case it still happens anyway because hoistability/invariance is also checked individually for their base pointer to be invariant so that they get into the RequiredILS. However, by themselves they might not be required to be load-hoisted. This could result in the %tmp3 to be hoisted, but not %tmp2 or %tmp1.
Could you either add a comment explaining why the dependent loads are also always load-hoisted - or - also add the dependent loads to RequiredILS?
I tested your patch on the test-suite. Compilation of test-suite/MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/jidctfst.c does not finish.

AFAIU, Johannes's approach doesn't cause the issue.

Johannes, could you please clarify how isHoistableLoad function works? I just want to make sure I understand it correctly:

1. It checks that the pointer operand of LInst is unchanging in the loops of region R.
2. Subsequently, it checks that there is no an instruction UserI from R that can modify the pointer operand and/or dominates all predecessors of the region exit of R.

Why should we check that UserI doesn't dominate all predecessors of the region exit of R?

Hi Johannes,

could you accept the revision, if it's fine?

Btw, it'd probably be helpful to complement the comment of isHoistableLoad. What do you think about the following?

/// Check if @p LInst can be hoisted in @p R.
///
+/// Check invariance of the pointer operand of @p LInst using the scalar evolution. In case it is invariant or the pointer operand is a load instruction, check that it is not used by another instruction in the SCoP that may write to memory and is always executed.
+///
/// @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.
///
/// @return True if @p LInst can be hoisted in @p R.

P.S.: ASFAIU, according to r287272,

bool DominatesAllPredecessors = true;
for (auto Pred : predecessors(R.getExit()))
  if (R.contains(Pred) && !DT.dominates(&BB, Pred))
    DominatesAllPredecessors = false;

if (!DominatesAllPredecessors)
  continue;

helps to check that a load to be hoistable/invariant if the pointer is used by another instruction in the SCoP that might write to memory and that is always executed.

Could you please explain why we can assume that @p LInst is hoistable if another instruction that uses the pointer is executed only in some cases?

lib/Support/ScopHelper.cpp

Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
   return nullptr;
 }
 
 bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
                             ScalarEvolution &SE, const DominatorTree &DT) {
   Loop *L = LI.getLoopFor(LInst->getParent());
   auto *Ptr = LInst->getPointerOperand();
   const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
+
+  if (auto *SU = dyn_cast<SCEVUnknown>(SE.getPointerBase(PtrSCEV)))
+    if (!dyn_cast<LoadInst>(SU->getValue()))
       while (L && R.contains(L)) {
         if (!SE.isLoopInvariant(PtrSCEV, L))
           return false;
         L = L->getParentLoop();
       }
 
   for (auto *User : Ptr->users()) {
     auto *UserI = dyn_cast<Instruction>(User);
     if (!UserI || !R.contains(UserI))
       continue;
     if (!UserI->mayWriteToMemory())
       continue;
 

test/Isl/CodeGen/indirect_invariant_load_hoist.ll

+; RUN: opt %loadPolly -polly-codegen -S -polly-invariant-load-hoisting=true \
+; RUN: < %s | FileCheck %s
+;
+; Check load-hoisting from pointers that by themselves are defined within the
+; SCoP, but are themselves invariant.
+;
+; CHECK: store i32 %polly.access.polly.access.polly.access.A.load.load.load, i32* %B
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-unknown"
+
+define void @f(i32*** %A, i32* %B) {
+entry:
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %entry
+  %i = phi i64 [ %i.next, %bb1 ], [ 0, %entry ]
+  %tmp1 = load i32**, i32*** %A, align 8
+  %tmp2 = load i32*, i32** %tmp1, align 8
+  %tmp3 = load i32, i32* %tmp2, align 8
+  store i32 %tmp3, i32* %B, align 8
+  %i.next = add i64 %i, 1
+  %exitcond = icmp eq i64 %i.next, 4
+  br i1 %exitcond, label %return, label %bb1
+
+return:                                             ; preds = %bb1
+  ret void
+}