Page MenuHomePhabricator

[Polly] Load hoisting of indirect loads
Needs ReviewPublic

Authored by gareevroman on Apr 7 2017, 11:48 PM.

Details

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.

Diff Detail

Event Timeline

gareevroman created this revision.Apr 7 2017, 11:48 PM
Meinersbur edited edge metadata.Apr 10 2017, 9:32 AM

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 added inline comments.Apr 11 2017, 4:26 AM
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 edited edge metadata.May 8 2017, 12:40 PM

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

gareevroman edited the summary of this revision. (Show Details)

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,

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?

jdoerfert resigned from this revision.Jun 11 2019, 7:57 AM