Page MenuHomePhabricator

[LoopNest]: Analysis to discover properties of a loop nest.
Needs ReviewPublic

Authored by etiotto on Oct 10 2019, 7:38 AM.

Details

Summary

This patch adds an analysis pass to collect loop nests and summarize properties of the nest (e.g the nest depth, whether the nest is perfect, what's the innermost loop, etc...).

The motivation for this patch was discussed at the latest meeting of the LLVM loop group (https://ibm.box.com/v/llvm-loop-nest-analysis) where we discussed
the unimodular loop transformation framework ( “A Loop Transformation Theory and an Algorithm to Maximize Parallelism”, Michael E. Wolf and Monica S. Lam, IEEE TPDS, October 1991). The unimodular framework provides a convenient way to unify legality checking and code generation for several loop nest transformations (e.g. loop reversal, loop interchange, loop skewing) and their compositions. Given that the unimodular framework is applicable to perfect loop nests this is one property of interest we expose in this analysis. Several other utility functions are also provided. In the future other properties of interest can be added in a centralized place.

Diff Detail

Repository
rL LLVM

Event Timeline

etiotto created this revision.Oct 10 2019, 7:38 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 10 2019, 7:38 AM
etiotto edited the summary of this revision. (Show Details)Oct 10 2019, 7:39 AM
fhahn added a comment.Oct 10 2019, 8:42 AM

The motivation for this patch was discussed at the latest meeting of the LLVM loop group (https://ibm.box.com/s/xn1sfd80jkpfssiqhal6t88yvzxebcex).

I think it would be great to summarize the motivation in the summary as well in a few sentences.

The motivation for this patch was discussed at the latest meeting of the LLVM loop group (https://ibm.box.com/s/xn1sfd80jkpfssiqhal6t88yvzxebcex).

Please change the link to: https://ibm.box.com/v/llvm-loop-nest-analysis

typo in title: [LoopNext] -> [LoopNest]

etiotto edited the summary of this revision. (Show Details)
etiotto retitled this revision from [LoopNext]: Analysis to discover properties of a loop nest. to [LoopNest]: Analysis to discover properties of a loop nest..
etiotto edited the summary of this revision. (Show Details)Oct 10 2019, 1:52 PM

[serious] I think this pass should determine the maximum set of loops that are perfectly nested, as getMaxPerfectDepth returns. This would make

for (int i)
  for (int j) {
    preStmt();
    for (int k) ...
    postStmt();
  }

a perfectly nested loop nest of depth 2 with a body that contains a loop. In fact, any loop would be perfectly nested, but possibly just with depth one. This would avoid different analysis result between the above loop nest and

for (int i)
  for (int j) {
    OutlinedBody(i,j);
  }

[serious] There could be irreducible control flow between two loops, that needs to be ruled-out.

llvm/include/llvm/Analysis/LoopNestAnalysis.h
66

[nit] outermost is a proper english word, so I suggest: getOutermostLoop()

78

[typo] breadth

125

[discussion] I understand "perfectly nested" as a property of a set of loops. That is, in

for (int i)
  for (int j) {
    preStmt();
    for (int k) ...
    postStmt();
  }

I'd understand the loop i and j to be a perfect loop nest. What code is in the body does not matter.

llvm/lib/Analysis/LoopNestAnalysis.cpp
24

Is this an established pattern? Never seen this before, but looks practical. The other pattern is VerboseFusionDebugging. Maybe we should agree on one patten.

71

[unrelated to this patch] Why isn't this prefixed with LLVM?

[suggestion] We could #define LLVM_DEBUG_VERBOSE(...) DEBUG_WITH_TYPE(DEBUG_TYPE "-verbose", __VA_ARGS__)

93–95

[serious] Should this just use llvm::isSafeToSpeculativelyExecute? It basically contains anything that could just be moved into the innermost loop such that it is executed multiple times.

178–181

[serious] This looks inconsistent with getMaxPerfectDepth() which understand "perfectly nested" as a property of a set of loops. That is, in

for (int i)
  for (int j) {
    preStmt();
    for (int k) ...
    postStmt();
  }

I'd understand the loop i and j to be a perfect loop nest. What code is in the body does not matter.

It doesn't seem to be used, so I'd just remove this function.

I am very much not convinced of either this analysis or the motivation.

First, restricting transformations to perfectly nested loops when there are known techniques to handle imperfect loop nests does not seem worthwhile. As such, I strongly reject the notion that we should make perfect nesting a requirement for all of our loop transformations.

Secondly, even if I accept the premise that perfect nesting is useful, I do not see the value of this analysis pass. We have an existing description of a loop and loop nest in loop info. How is this anything more than a set of helper function implemented over the existing analysis? (i.e. LoopNestUtils.hpp/cpp?)

First, restricting transformations to perfectly nested loops when there are known techniques to handle imperfect loop nests does not seem worthwhile. As such, I strongly reject the notion that we should make perfect nesting a requirement for all of our loop transformations.

I'd see it as a tool for transformations that need perfect loop nests (interchange, tiling, unrollandjam, ...) rather as a new requirement.

Secondly, even if I accept the premise that perfect nesting is useful, I do not see the value of this analysis pass. We have an existing description of a loop and loop nest in loop info. How is this anything more than a set of helper function implemented over the existing analysis? (i.e. LoopNestUtils.hpp/cpp?)

We already had this discussion in D63459. In this case, I don't have a strong opinion on whether it should be a LoopAnalysis or a utility. In this case an advantage could be that passes may mark the analysis as preserved (e.g. it doesn't change the loop nest) rather it being recomputed.

etiotto marked 11 inline comments as done.Tue, Oct 29, 1:48 PM
etiotto added inline comments.
llvm/include/llvm/Analysis/LoopNestAnalysis.h
66

ok, I will also rename getInnerMost() to getInnermost() for consistency.

125

Correct. In your example loops i and j are perfectly nested with respect to each other. Loop j and k on the other hand are not perfectly nested because of the present of stmts between the loops. The entire loop nest is imperfect because of that.

So the isPerfect member function returns true if and only if any adjacent pair of loops in the nest are perfectly nested with respect to each other (not only the othermost 2 loops). That is the only loop containing user code is the innermost loop.

llvm/lib/Analysis/LoopNestAnalysis.cpp
24

I personally like this one because is shorter than --debug-only=loopnest-verbose-debug.... but if ppl objects then I can change it.

71

Yep I like it. Would be useful to have the LLVM_DEBUG_VERBOSE macro to drive consistency in how debug traces could be toggled.

It would be even better to have a way to pass a verbosity level to the debug/tracing infrastructure. Users would then be able to select which level of verbosity to associated with a particular debug stmt:

#define LLVM_DEBUG_VERBOSE(DbgLvl, ...) DEBUG_WITH_TYPE(DEBUG_TYPE "-verbose-" + DbgLvl, VA_ARGS)

178–181

This function would return false for the`j` loop in the example because the loop nest it 'roots' is imperfect given that there is code between loops j and k. It would also return false of loop i given that its containing loop nest is imperfect. Does that answer your question?

etiotto updated this revision to Diff 226963.Tue, Oct 29, 1:59 PM
etiotto marked 5 inline comments as done.

Partially address code review comments from @Meinersbur.

Meinersbur added inline comments.Wed, Oct 30, 9:18 AM
llvm/include/llvm/Analysis/LoopNestAnalysis.h
125

I am arguing that we should remove isPerfect entirely and replace by something that returns the maximum perfect loop nest depth. To avoid a difference whether in

for (int i)
  for (int j) {
    OutlinedBody(i,j);
  }

the function OutlinedBody is inlined or not.

Also, since this is a loop analysis, there should be a function determining whether the currently analyzed loop is the outermost loop nest. A loop pass could use this to skip optimizing a loop of depth 2 when when including another outer loop it could optimize a loop nest depth of 3 (since the order of optimization is determined by the LoopPassManager and can be arbitrary).

bmahjour added inline comments.Fri, Nov 1, 11:18 AM
llvm/lib/Analysis/LoopNestAnalysis.cpp
93–95

isSafeToSpeculativelyExecute returns false for phi nodes, branches and most integer divisions.
We need to allow phi and branches due to inner loop induction and control.
As far as I know integer divisions are safe to speculate most of the time, except on some platforms where zero-division generate a trap.
It puzzles me why isSafeToSpeculativelyExecute checks for integer division but completely ignores floating-point division which would have visible side-effects on more platforms!

[serious] Could you add a test with early exits, e.g.

for (i = 0; i<ni; ++i) {
    for (j=0; j<nj; j+=1) {
       if (c)
        return i+j;
    }
}
llvm/lib/Analysis/LoopNestAnalysis.cpp
93–95

I guess control flow instructions are out of the scope of isSafeToSpeculativelyExecute, but could be checked explicitly.

isSafeToSpeculativelyExecute should be the reference for whether a non-control-flow instruction can be executed speculatively/redundantly. If it returns true for something that has side-effect, it's a bug, not just if called here. If it can be improved, then we can improve it. For instance, passing the target determining whether division by zero is undefined or poison (by the LangRef, it's always undefined).

Another question is whether isSafeToSpeculativelyExecute is what we need. It may return true on loads, but I'd exclude loads here (which may give us problems since LICM likes to move loads out if the innermost loop). If something can be moved into the innermost loop, then it does not matter whether it might be undefined behavior since execution of the innermost loop is required for anything in the innermost to execute.
On the other side, hoisting out of the outermost loop might be required if needed to compute the iteration count of the innermost loop (e.g. for loop interchange). We cannot risk a division-by-zero to occur of it did not occur in the original loop nest.

I think isSafeToSpeculativelyExecute is a safe default and we may think about loosen the requirements if we know what should happen with instructions of this kind for loop nest transformations. It's also better to have a more central place for the property we need.

llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll
224

Does the guard condition be consistent with the loop exist condition? I.e. is

for (i = 0; i<ni; ++i) {
  if (5<nj) { // this a guard?
    for (j=0; j<nj; j+=1) 
      x+=(i+j);
  }
}