This is an archive of the discontinued LLVM Phabricator instance.

[LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions
ClosedPublic

Authored by sbaranga on Nov 3 2015, 10:58 AM.

Details

Summary

This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the
usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge
by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is
that both LAA and LV should use this interface everywhere.

This also solves a problem involving the result of SCEV expression rewritting when
the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates

P1: {a,+,b} has nsw
P2: b = 1.

Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us
sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies).
The SCEVPredicatedLayer maintains the order of transformations by feeding back
the results of previous transformations into new transformations, and therefore
avoiding this issue.

The SCEVPredicatedLayer maintains a cache to remember the results of previous
SCEV rewritting results. This also has the benefit of reducing the overall number
of expression rewrites.

Diff Detail

Event Timeline

sbaranga updated this revision to Diff 39093.Nov 3 2015, 10:58 AM
sbaranga retitled this revision from to [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions.
sbaranga updated this object.
sbaranga added reviewers: mzolotukhin, anemet.
sbaranga added a subscriber: llvm-commits.
sbaranga updated this revision to Diff 39691.Nov 9 2015, 7:33 AM

Replaced SE with PredSE wherever possible in LV and LAA.
Performed a rebase as the previous review was conflicting with HEAD.

Hi,

So most of this patch is just plumbing and renaming - the guts is the addition of SCEVPredicateLayer.

Bikeshedding: I'm not too happy with the name. SCEV is the prefix used for the internal node types of ScalarEvolution. Something like PredicatedScalarEvolution might sound better?

I'm a bit worried about how easy it is to subvert the predicated mechanism. For example:

PSE.getSCEV(); // Gets a scev under a predicate
PSE.getSE()->getSCEV(); // Gets a scev not under a predicate

And there are places in LoopVectorize that sem to use "PSE.getSE()" quite a bit... are we sure they aren't subverting the predicates? If they do, is that a correctness or a performance issue?

If it's just a performance thing, it might be nice to make use of ScalarEvolution even easier by defining an operator->/operator* so you can do

PSE->getEqualPredicate();
PSE.getSCEV();

James

Hi James,

Hi,

So most of this patch is just plumbing and renaming - the guts is the addition of SCEVPredicateLayer.

Correct.

Bikeshedding: I'm not too happy with the name. SCEV is the prefix used for the internal node types of ScalarEvolution. Something like PredicatedScalarEvolution might sound better?

I don't have a strong preference here.

I'm a bit worried about how easy it is to subvert the predicated mechanism. For example:

PSE.getSCEV(); // Gets a scev under a predicate
PSE.getSE()->getSCEV(); // Gets a scev not under a predicate

Yes, but the two have different meanings (they are not equal when the predicate evaluates to false), so you should be able to do both things?

And there are places in LoopVectorize that sem to use "PSE.getSE()" quite a bit... are we sure they aren't subverting the predicates? If they do, is that a correctness or a performance issue?

It would only be a correctness problem if you would expect some expression to have some form and only the predicated version would have that problem.
Otherwise SE.getSCEV() and PredSE.getSCEV() would produce expressions evaluating to the same values (as long as we pass the runtime checks).
I've audited all the uses in LV and I believe there wouldn't be any correctness problem. There might be issues in other passes (LLE in particular), which I plan to address in a future commit.

If it's just a performance thing, it might be nice to make use of ScalarEvolution even easier by defining an operator->/operator* so you can do

PSE->getEqualPredicate();
PSE.getSCEV();

That's an interesting idea. You could still do PSE->getSCEV() though?

-Silviu

You could still do PSE->getSCEV() though?

yep:

PSE.getSCEV(); // get predicated scev
PSE->getSCEV(); // get non-predicated scev

You could still do PSE->getSCEV() though?

yep:

PSE.getSCEV(); // get predicated scev
PSE->getSCEV(); // get non-predicated scev

My problem with this is that it makes it easy to make mistakes and get something else (for example I frequently get -> with . mixed up).

sbaranga updated this revision to Diff 40041.Nov 12 2015, 6:12 AM

Rebased on ToT.

Performed some renaming:

SCEVPredicatedLayer -> PredicatedScalarEvolution
PredSE -> PSE

Updated comments to reflect this.

James, how strongly do you feel about defining the operators->/*? Because of the reasons above I have a slight preference not to do this.

-Silviu

anemet edited edge metadata.Nov 12 2015, 10:11 PM

And there are places in LoopVectorize that sem to use "PSE.getSE()" quite a bit... are we sure they aren't subverting the predicates? If they do, is that a correctness or a performance issue?

It would only be a correctness problem if you would expect some expression to have some form and only the predicated version would have that problem.
Otherwise SE.getSCEV() and PredSE.getSCEV() would produce expressions evaluating to the same values (as long as we pass the runtime checks).
I've audited all the uses in LV and I believe there wouldn't be any correctness problem. There might be issues in other passes (LLE in particular), which I plan to address in a future commit.

You guys lost me at this point. AIUI, SE->getSCEV(value) returns the SCEV without any assumptions. PSE->getSCEV(value) returns a SCEV with the assumption backed in. The only problem I can see is when the latter is used without run-time guarding it with the corresponding predicate. What am I missing, how is LLE potentially broken?

include/llvm/Transforms/Utils/LoopUtils.h
388

expression

406–409

Please comment these too

You guys lost me at this point. AIUI, SE->getSCEV(value) returns the SCEV without any assumptions. PSE->getSCEV(value) returns a SCEV with the assumption backed in. The only problem I can see is when the latter is used without run-time guarding it with the corresponding predicate. What am I missing, how is LLE potentially broken?

LLE is not broken, but introducing some new SCEV predicates might break it.

There are some places where it should do PSE->getSCEV(Value) instead of SE->getValue(). To be more specific, in isDependenceDistanceOfOne we assume that pointers from a forward/backward dependence are AddRecExprs when we query SCEV directly. However, with predicates, they might not be. I expect this might trigger an assert in some cases after we introduce predicates for overflows. So before introducing the new predicates, we have to change LLE to use PSE there.

sbaranga updated this revision to Diff 40132.Nov 13 2015, 3:28 AM
sbaranga edited edge metadata.

Add more comments for PredicatedScalarEvolution and fix a typo.

LLE is not broken, but introducing some new SCEV predicates might break it.

There are some places where it should do PSE->getSCEV(Value) instead of SE->getValue(). To be more specific, in isDependenceDistanceOfOne we assume that pointers from a forward/backward dependence are AddRecExprs when we query SCEV directly. However, with predicates, they might not be. I expect this might trigger an assert in some cases after we introduce predicates for overflows. So before introducing the new predicates, we have to change LLE to use PSE there.

OK, that makes sense.

A gentle ping?

-Silviu

Hi Silviu,

From my side I'm going to back out of this review - anemet is the right person to review this.

Cheers,

James

anemet added a comment.Dec 7 2015, 2:02 PM

Pretty minor comments. Sorry about the delay.

include/llvm/Analysis/LoopAccessAnalysis.h
504–506

You probably want to say that union predicate is now inside PSE.

include/llvm/Transforms/Utils/LoopUtils.h
390

Why is this in LoopUtils.h, for example as opposed to SE.h? I don't have a preference but it's not immediately obvious to me.

lib/Transforms/Scalar/LoopDistribute.cpp
764

Nit: We keep going back between plural and singular. The point I think is trying to avoid somehow suggesting that we can only handle a single predicate by using singular.

Can we use getUnionPredicate or something like that perhaps? What do you think?

lib/Transforms/Utils/LoopUtils.cpp
734–749

I think the logic would be tighter like this:

if (found && version matches)
  return it

// Use the previously rewritten value to preserve the order of applying 
// the predicates
if (found)
  Expr = II->second.second

NewExpr = SE.rewriteUsingPredicate(Expr, Preds);
RewriteMap[Expr] = {Generation, NewExpr};
return NewExpr;

Also I forgot the API now but is there a way to get an iterator that we can always write (regardless whether we're adding a new entry). You do two lookups here.

763–765

Nit: I would fold the increment in the if condition.

Thanks! Some replies inline. I'll have a new version that addresses these issues out soon.

-Silviu

include/llvm/Transforms/Utils/LoopUtils.h
390

It could live in SE.h as well, it isn't obvious for me where it should live either. I added it here because it seemed to be solving a problem specific to LV/LAA then SCEV.

lib/Transforms/Utils/LoopUtils.cpp
734–749

It looks like we can in fact rewrite this to do a single lookup.

sbaranga updated this revision to Diff 42161.Dec 8 2015, 4:28 AM

Addressed review comments:

  • updated the addPredicate logic to make a single DenseMap lookup
  • changed getPredicate to getUnionPredicate
anemet accepted this revision.Dec 8 2015, 12:29 PM
anemet edited edge metadata.

LGTM.

include/llvm/Transforms/Utils/LoopUtils.h
390

Fair enough.

lib/Transforms/Utils/LoopUtils.cpp
736

The inserted value is irrelevant here so we should use some invalid values.

Also, can we avoid this with DenseMap::FindAndConstruct?

This revision is now accepted and ready to land.Dec 8 2015, 12:29 PM
sbaranga updated this revision to Diff 42297.Dec 9 2015, 7:06 AM
sbaranga edited edge metadata.

Replace insert with [] when adding to the map. This will initally add
an invalid entry to the map (with nullptr for the expression), which
we will later update to something valid.

sbaranga closed this revision.Dec 9 2015, 7:06 AM

Thanks, Adam! r255115

-Silviu

lib/Transforms/Utils/LoopUtils.cpp
736

We can. I used [] instead which does FindAndConstruct.