Page MenuHomePhabricator

[SCEV] Don't require dominance ordering of add/mul/min/max expressions
Needs ReviewPublic

Authored by reames on Jun 17 2021, 6:46 PM.

Details

Summary

I'm a bit hesitant about this patch, and welcome ideas on other approaches.

The test case test_non_dom demonstrates a case where scev-aa crashes today. (If exercised either by -eval-aa or -licm.) The basic problem is that SCEV-AA expects to be able to compute a pointer difference between two SCEVs for any two pair of pointers we do an alias query on. For (valid, but out of scope) reasons, we can end up asking whether expressions in different sub-loops can alias each other. This results in a subtraction expression being formed where neither operand dominates the other.

Looking at SCEV, I can't find a reason why the dominance invariant on operands is actually required. The code which references it is simply a optimization rule, the worst that happens is we fail to caonicalize a hypothetical (i.e. not corresponding to an IR Value) expression.

This does result in somewhat odd scev expressions becoming possible. For instance, the getMinusSCEV(getSCEV(%addr1), getSCEV(%addr2)) results in "({(-3200 + (-1 * %data)),+,-8}<nw><%subloop2> + {%data,+,8}<nw><%subloop1>)". I can't find an immediate problem with that, but I am sorta wondering if I'm missing something here.

Diff Detail

Event Timeline

reames created this revision.Jun 17 2021, 6:46 PM
reames requested review of this revision.Jun 17 2021, 6:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 17 2021, 6:46 PM

I'm pretty sure if you try to give an expression where arguments don't dominate one another to SCEV Expander, it should break.

reames planned changes to this revision.Jun 18 2021, 9:49 AM

Max is correct. I think I can handle that easily, but let me make sure and then repost.

There are two relevant questions:

  1. Does SCEV do something reasonable with such an expression? I mean, you obviously can't expand it; there isn't any viable insertion point. More generally, I'm not sure it's meaningful; even if we drop the assertions, it's not clear what the result is supposed to represent. If we want to support "subtracting" two addrecs to do dependency analysis, we should probably add a dedicated method, which returns something that isn't a regular SCEV expression.
  2. Why is SCEVAA trying to construct such an expression? AliasAnalysis::alias() doesn't make any sense if there isn't a dominance relationship between the two pointers.

There are two relevant questions:

  1. Does SCEV do something reasonable with such an expression? I mean, you obviously can't expand it; there isn't any viable insertion point. More generally, I'm not sure it's meaningful; even if we drop the assertions, it's not clear what the result is supposed to represent. If we want to support "subtracting" two addrecs to do dependency analysis, we should probably add a dedicated method, which returns something that isn't a regular SCEV expression.
  2. Why is SCEVAA trying to construct such an expression? AliasAnalysis::alias() doesn't make any sense if there isn't a dominance relationship between the two pointers.

On (1), I think that point has convinced me we need to not create such scevs and return could not compute instead. Will give it a bit more thought, but that's the way I'm currently leaning.

On (2), alias set tracker doesn't check dominance relations. I haven't confirmed, but I'm 90% sure that's the issue. aa-eval also does a cross product without concern for dominance.

On (2), alias set tracker doesn't check dominance relations. I haven't confirmed, but I'm 90% sure that's the issue

On trunk, LICM doesn't use AliasSetTracker by default, so this conclusion is a bit suspicious.

Do you think it's worth trying to enforce dominance relations in AA calls more generally, as opposed to trying to address this specifically in SCEVAA?

nikic added a comment.Jun 21 2021, 1:44 PM

@efriedma LICM still uses AST for scalar promotion.

It's also not obvious to me why AA queries without dominance relationship are necessarily problematic. Consider something like this:

p = ...
if (...) {
    p1 = gep p, 1
    store p1
}
p2 = gep p, 1
load p2

p1 and p2 are not in a dominance relationship, but an AA query between them seems meaningful (and would answer MustAlias here). I'd expect that e.g. MemorySSA would also perform such queries when traversing MemoryPhi's.

p1 and p2 are not in a dominance relationship, but an AA query between them seems meaningful

In general, an alias() query involves two input pointers/sizes, and a position in the CFG. But in the LLVM API, the "position" is implicit. The easiest way to define this position is "any position dominated by both pointers". Anything else gets more complicated. Consider, for example:

if (cond) {
  a[getc(file1)]++;
} else
  a[getc(file2)]++;
}

Do these accesses alias? What does it even mean for them to alias?


For your example with a GEP after an if statement, there's a sort of "obvious" rule: you can solve the position issue by implicitly hoisting the GEP before the if statement. I guess we could define some sort of "extended" dominance relationship that includes some amount of hoisting. But it's not clear how the caller would know it's dealing with a value that can be hoisted.

nikic added a comment.Jun 22 2021, 1:18 AM

@efriedma For AA, the relevant concept is reachability, not dominance. Querying modref between two instructions is sensible as long as one is reachable from the other. For your example (assuming it is not part of a loop), AA is not meaningful, because the instructions are not reachable in either direction. But generally, there are many cases where AA is meaningful, but no dominance relationship holds. As such, I do not believe it makes sense to enforce dominance on the level of the AA API.

reames updated this revision to Diff 355069.EditedJun 28 2021, 4:48 PM

Refresh, mostly to add test for following comment.

After giving them some more thought, I believe I've convinced myself that this is the correct approach. Why? Because it's exactly the approach we already use.

If you look at the newly added test_non_dom2 test case, you'll find an example which is identical to the test_non_dom case except that I replaced a gep with a call to an external function. Assume that external function just contains the original gep, and returns it's result. The modified test case didn't crash, and we do in fact form SCEVs with non-dominating arguments.

In the example, we happily form the SCEV "((-1 * %addr1) + %addr2)" where %addr1 and %add2 represent SCEVUnknowns, and neither dominate the other. As Max points out, it's odd that such an expression isn't expandable, but we already have that problem. This patch does not introduce a new concept after all.

(Edit - And it turns out SCEVExpander already guards against this case. In isSafeToExpandAt, we check that the SCEV dominates the insertion point. In this example, the "odd" SCEVs above will not dominate any insertion point, and are thus never expanded.)

efriedma added inline comments.Jun 29 2021, 11:44 AM
llvm/lib/Analysis/ScalarEvolution.cpp
752–755

I'm not sure this produces a strict weak ordering suitable for sorting. We've run into issues with other code that tries to sort on dominates(). The solution is usually to use domtree DFS numbering instead.

reames added inline comments.Thu, Jul 1, 10:07 AM
llvm/lib/Analysis/ScalarEvolution.cpp
752–755

I'm happy to make the change, but do you have an example? I don't see how we'd end up with anything problematic here.

efriedma added inline comments.Thu, Jul 1, 10:26 AM
llvm/lib/Analysis/ScalarEvolution.cpp
752–755

For example, D103441

reames updated this revision to Diff 357066.Wed, Jul 7, 1:40 PM

Address review comment re: dominance sorting

I think you need to call updateDFSNumbers() somewhere?