Page MenuHomePhabricator

Make ScalarEvolution::ComputeExitLimit more agressive
AbandonedPublic

Authored by sanjoy on Jan 2 2015, 4:13 PM.

Details

Summary

Test case included demonstrates a situation where this matters

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 17767.Jan 2 2015, 4:13 PM
sanjoy retitled this revision from to Make ScalarEvolution::ComputeExitLimit more agressive.
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: reames, hfinkel, atrick, majnemer.
sanjoy added a subscriber: Unknown Object (MLST).

Cursory review.

include/llvm/IR/BasicBlock.h
214

s/successir/successor/

217

Slightly tangential: is a hypothetical getSingleSucessor() not useful yet?

lib/Analysis/ScalarEvolution.cpp
4827

Um, pred_size()?

4831

Are you worried that L->getHeader() might be nullptr? Why check Next separately then?

4857–4862

Redundant && MustExecuteLoopHeader -- you do an &= anyway.

lib/IR/BasicBlock.cpp
249

succ_empty()?

252

Probably nicer with a range-based loop or std::all_of.

test/Analysis/ScalarEvolution/compute-exit-limit-aggressively.ll
73

Why have you shown two of these examples with the unknown parameter passed?

Replies inline.

include/llvm/IR/BasicBlock.h
214

Will fix.

217

Even if it is, that's not relevant to this patch. But honestly, I don't know.

lib/Analysis/ScalarEvolution.cpp
4827

I can't find a pred_size.

4831

L->getHeader() cannot be nullptr. Given that, I don't follow this comment -- I want to break if Next is nullptr OR Next is L->getHeader(). How do I do that with a single check?

4857–4862

DominatesHeaderIgnoringLoopEntry is not free, and I don't want to call it if MustExecuteLoopHeader is false.

lib/IR/BasicBlock.cpp
249

Again, I cannot find a succ_empty. But I did notice that // No preds. should be // No successors..

252

std::all_of is a good idea. I don't want to make that change in this patch because I want getUniqueSuccessor to be an exact dual of getUniquePredecessor. But I can refactor both in a cleanup change.

test/Analysis/ScalarEvolution/compute-exit-limit-aggressively.ll
73

These are negative tests that demonstrate that the transform does not fire incorrectly.

sanjoy updated this revision to Diff 17991.Jan 11 2015, 4:56 PM

Fix nits in comments.

hfinkel added inline comments.Jan 27 2015, 7:00 PM
lib/Analysis/ScalarEvolution.cpp
4820

There really should not be any non-trivial "chains" of blocks with unique predecessors and successors once SimplifyCFG has run (as I understand it). What motivates this?

4827

This needs a comment. Why are you bailing out if there is more than one predecessor?

4844

In conclusion, I think this function is both overly limiting and too complicated (it handles a chain case that should not really occur -- although I certainly could be wrong about this).

It is also not quite correct (because you also need to check that none of these blocks have functions that might throw).

I think that a direct general approach would be better. Just walk the predecessor graph starting at BB, bailing out if you hit an edge that leaves the loop, and stopping when you hit the loop header. You also need to check for functions that might throw (this is what LICM does).

Thank you for taking out the time to review this!

It is quite possible that what I'm trying to fix can be solved by the right pass order in our frontend, I'll give that a try first before redoing this.

sanjoy abandoned this revision.Feb 7 2015, 5:44 PM