I choose to name the pass Loop Fission to avoid confusion with the existing LoopDistribution pass (eventually Loop Fission should replace that pass). Also Loop Fission is the opposite of Loop Fusion :-) ?

Addressed review comments from @Meinersbur

ping

ping

Addressing code review comments.

Based on the feedback received during code review I have added a new public member function called 'getPerfectLoops' which can be used to retrieve a list of loops that are perfect with respect to each other.
For example, given the following loop nest containing 4 loops, 'getPerfectLoops' would return {{L1,L2},{L3,L4}}.

for(i) // L1
  for(j) // L2
    <code>
    for(k) // L3
       for(l) // L4

In D68789#1753797, @bmahjour wrote:

In D68789#1753777, @Meinersbur wrote:

[suggestion] Add a methods that returns/fills a vector with all the Loop*s that are part of the perfect loop nest.

That sounds like a good idea. I'd suggest returning a vector of vectors actually in case where there are multiple perfect sub nests in a loop nest. ie:

L1
  L2
   <code>
    L3
      L4
        L5

return:
{{L1,L2},{L3,L4,L5}}

Addressing code review comments from Michael.

In D63459#1731032, @Meinersbur wrote:

In D63459#1731015, @xbolva00 wrote:

/home/xbolva00/LLVM/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp 353 warn V612 An unconditional 'return' within a loop.

This indeed does not look right. There are beaks and returns in the loop, but no continue. Meaning the loop is only iterated for one element (in this case: the innermost loop). I think nothing else than the innermost loop is needed for delinearization, in which case it could be made a conditional instead of a for-statement.

/home/xbolva00/LLVM/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp 456 err V502 Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the '==' operator.

TRT(TRT == None ? Optional<unsigned>(TemporalReuseThreshold) : TRT),

Could add parens around TRT == None to silence the analyzer.

Partially address code review comments from @Meinersbur.

ping

ping

In D63459#1625843, @xbolva00 wrote:

/home/xbolva00/LLVM/llvm/lib/Analysis/LoopCacheAnalysis.cpp:110:14: warning: ‘llvm::raw_ostream& llvm::operator<<(llvm::raw_ostream&, const llvm::IndexedReference&)’ has not been declared within llvm

raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) {
             ^~~~

In file included from /home/xbolva00/LLVM/llvm/lib/Analysis/LoopCacheAnalysis.cpp:28:0:
/home/xbolva00/LLVM/llvm/include/llvm/Analysis/LoopCacheAnalysis.h:45:23: note: only here as a friend

friend raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R);
                    ^~~~~~~~

/home/xbolva00/LLVM/llvm/lib/Analysis/LoopCacheAnalysis.cpp:443:14: warning: ‘llvm::raw_ostream& llvm::operator<<(llvm::raw_ostream&, const llvm::CacheCost&)’ has not been declared within llvm

raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) {
             ^~~~

In file included from /home/xbolva00/LLVM/llvm/lib/Analysis/LoopCacheAnalysis.cpp:28:0:
/home/xbolva00/LLVM/llvm/include/llvm/Analysis/LoopCacheAnalysis.h:174:23: note: only here as a friend

friend raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC);

GCC 7 Linux.

Fix build warning for operator<< when using GCC 7.

Added a command line option to specify the threshold for temporal reuse.

Right, are you planning on submitting a patch for loop interchange upstream?

I used the printer on some of the loop interchange tests, but the delinearization does not support some cases there yet. I hope I find some time to look into that next week and maybe also integrating it into loop interchange unless you plan to do so.

In D63459#1605923, @fhahn wrote:

Can you re-run clang-format on the latest version of the patch? I think it would be good to get an in-tree user of this soon, to make sure the modeling works as expected on real hardware/benchmarks. Do you have a timeline to get this used? I think you mentioned LoopFusion as one of the first planned users?

Run clang-format, address comments from @fhahn.

LGTM. I found a typo, you can fix it while committing.

I addressed all pending review comments, @fhahn @reames does it look ok to you guys now?

Addressing review comment from @reames

Address remaining comments from @fhahn

In D63459#1590173, @fhahn wrote:

I would like to take another look, but do not want to block this for too long. Please feel free to commit if you don't hear from me by Monday.

Addressing code review comments given by @Meinersbur and @fhahn.

@fhahn @Meinersbur do you have further comments? If not can this be approved?

Note: Because I removed the getLoops static function in the last path older comments in LoopCacheAnalysis.cpp are unfortunately no longer attached to the correct line.

Addressed suggestions from @fhahn and dropped the pass as an analysis. Instead I provided a static member function in the CacheCost class to compute the cache cost of a nest rooted by a given loop.

I can use breadth_first from ADT/BreadthFirstIterator.h to collect the loops in breadth-first order. Arguably the getLoopsInPreorder() member functions could also be removed in favor of using ADT/DepthFirstIterator.h (need to confirm whether that does a preorder traversal).

Addressed Michael Kruse comments.

ping

In D63885#1563560, @Whitney wrote:

Strengthen the definition of loop guard by disallowing non safe instructions guarded by the branch but not in the loop.

In D63885#1563442, @Whitney wrote:

@reames Thanks for the review! I agree that there are still much more to consider for how we want to define a loop guard, to make the most use of it.

What's others opinion on disallow instructions with side effects in between the loop guard block and the loop header?

This looks pretty good to me. I just added some minor inline comments.

In D63459#1549307, @Meinersbur wrote:

How would a pass use this analysis? It computes a cost for the current IR, but there is nothing to compare it to unless the transformation pass emits the transformed loop nest next to the original pass such that the LoopCacheAnalysis can compute its cost.

Addressed review comment from M. Kruse.