Page MenuHomePhabricator

Use invariants in ScalarEvolution

Authored by hfinkel on Jul 17 2014, 11:00 AM.



This patch adds a basic (but important) use of invariants in ScalarEvolution. When SE is attempting to validate a condition guarding a loop (such as whether or not the loop count can be zero), this check should also include dominating invariants.

Diff Detail

Event Timeline

hfinkel updated this revision to Diff 11598.Jul 17 2014, 11:00 AM
hfinkel retitled this revision from to Use invariants in ScalarEvolution.
hfinkel updated this object.
hfinkel edited the test plan for this revision. (Show Details)
hfinkel added reviewers: chandlerc, atrick.
hfinkel added a subscriber: Unknown Object (MLST).
hfinkel updated this revision to Diff 11701.Jul 20 2014, 12:01 PM

Renamed to llvm.assume.

reames added a subscriber: reames.Jul 23 2014, 3:41 PM

I'm not knowledgeable of this code, but I don't see anything which is obviously wrong. Feel free to take or ignore the ordering and style comments.


It seems like the assumption code could also apply here. The patterns are very similar.

I can't think of a case of the top of my head where this would be profitable though. Maybe something about pre and post alignment loops in vectorized code? (i.e. we can conclude that only one iteration is needed from alignment info)


Shouldn't this be after the if(!LoopEntryPredicate) early return?

It also feels like it should be after the branch condition check since that's likely to be cheaper.

I even wonder if the assumption processing shouldn't be done as a separate loop to avoid searching out invariants in what might be a common case.


You have this pattern of checks a lot in different changes. Time to extract a helper function somewhere common? isAssumeIntrinsic(Instruction* I)?

hfinkel added inline comments.Jul 25 2014, 1:58 PM

Good point. I also could not particularly think of a place where this would help, but the cost of finding the intrinsics and determining applicability here is low, so we might as well.


It could be, but then I'd also need to split the early return (because we don't want it after the LoopEntryPredicate->isUnconditional() part of the early return). Thinking about it, splitting the early-return check is the cleaner thing to do.


True. In many places I use the PatternMatch header facilities to make this easier, and I should perhaps do so more often (like here, for example).

hfinkel updated this revision to Diff 11936.Jul 27 2014, 11:28 PM

Updated to use AssumptionTracker (and those review comments still relevant (hopefully I got them all)).

hfinkel accepted this revision.Sep 7 2014, 2:47 PM
hfinkel added a reviewer: hfinkel.

(will close)

This revision is now accepted and ready to land.Sep 7 2014, 2:47 PM
hfinkel closed this revision.Sep 7 2014, 2:47 PM