This is an archive of the discontinued LLVM Phabricator instance.

Make cost estimation in RewriteLoopExitValues smarter
ClosedPublic

Authored by igor-laevsky on Jul 31 2015, 11:50 AM.

Details

Summary

In the recent change (http://reviews.llvm.org/D10782) Sanjoy updated cost estimation for the RewriteLoopExitValues to consider complicated SCEV expressions as cheap if there already exists llvm-ir expression which computes same value.

However if such expression is wrapped in a several other expressions we will still consider it as high cost.
For example this is considered high cost:

{-2,+,1} + (zext (<expr>)), where <expr> is high cost expression already defined in the IR.

In this change I updated cost estimation to evaluate such nested expressions as cheap. Turns out it is fairly important on one of our benchmarks (~20% performance).

In order to do that I have added new method "TryToGetValueForSCEVAt" into SCEVExpander, which tries to look for pre-existing llvm ir value. This method is used inside "ExpandSCEVIfNeeded" and inside "isHighCostExpansionHelper"

It would be natural to add "InsertedExpressions" lookup into this method, but I am not sure if there is really need for this. Also it is possible to use this method during "SCEVExpander::expand", but I am worried about having to much impact on the unrelated areas with no good reason.

Diff Detail

Event Timeline

igor-laevsky retitled this revision from to Make cost estimation in RewriteLoopExitValues smarter.
igor-laevsky updated this object.
igor-laevsky added reviewers: sanjoy, atrick, hfinkel.
igor-laevsky added a subscriber: llvm-commits.
sanjoy edited edge metadata.Aug 5 2015, 2:54 PM

This needs test cases.

include/llvm/Analysis/ScalarEvolutionExpander.h
121

Nit: spacing around =.

121

Please document what At does here.

197

Nit: "available"

197

Nit: I'd use "LLVM IR"

201

Nit: "exhaustive".

202

Nit: "didn't find"

203

I'd call this getExistingSCEVExpansion, making it clear that we're looking for a value that already exists.

lib/Analysis/ScalarEvolutionExpander.cpp
1823

The way we're using this now in RewriteLoopExitValues, S is not an induction variable, but is an operand to the loop's backedge comparison which happens to be equal to the trip count of the loop.

I'd just leave in the first sentence in the comment, and delete the rest.

1894

Should this division case also use TryToGetValueForSCEVAt? The search logic here is basically identical, except the SCEV subtraction in the end (and perhaps we should change TryToGetValueForSCEVAt to look at exiting blocks too?).

igor-laevsky edited edge metadata.
igor-laevsky set the repository for this revision to rL LLVM.
igor-laevsky marked 8 inline comments as done.

Thanks for the comments!

include/llvm/Analysis/ScalarEvolutionExpander.h
203

Renamed to tryToGetExistingExpansion. I'd like to leave tryTo in the name to emphasise that function can sometimes fail to find any value.

lib/Analysis/ScalarEvolutionExpander.cpp
1894

In TryToGetValueForSCEVAt we are looking for:
ExitCond == S, where ExitCond is LHS or RHS
On success we return ExitCond, because it is existing LLVM IR value for S.

For division we are looking for:
(ExitCond - 1) == S, where ExitCond is LHS or RHS
If we move this subtraction logic into TryToGetValueForSCEVAt we will not be able to return anything since we actually didn't find any pre-existing LLVM IR value.

I suspect we can completely remove division special handling if:

  1. (ExitCond - 1) == S <=> ExitCond == (S + 1) (or other non AddRec expression with S)
  2. isHighCostExpansionHelper can recursively look into expressions. I.e IsHighCost(a + b) == IsHighCost(a) || isHighCost(b) (this is true right now)
  3. We will update TryToGetValueForSCEVAt to look into exiting blocks

However I am afraid to break something, so I will do it in separate change. (But first I will check that division case is covered by existing tests.)

sanjoy accepted this revision.Aug 10 2015, 9:22 AM
sanjoy edited edge metadata.

LGTM with some comments inline.

include/llvm/Analysis/ScalarEvolutionExpander.h
203

How about findExistingExpansion then?

lib/Analysis/ScalarEvolutionExpander.cpp
1853

Minor: I'm not a native English speaker, but are there some prepositions missing here? I'd have expected "If we can find an existing value for this SCEV available at At then consider the expression cheap".

This revision is now accepted and ready to land.Aug 10 2015, 9:22 AM
igor-laevsky marked 2 inline comments as done.Aug 10 2015, 11:08 AM
This revision was automatically updated to reflect the committed changes.