This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Enable more pre-indexed stores
ClosedPublic

Authored by samparker on Jan 15 2019, 6:57 AM.

Details

Summary

The DAG combiner previously would not produce a pre-indexed store if the base pointer was a predecessor of the value being stored, so to prevent a cycle in the DAG. However, we could produce a pre-inc store if the store is final use of base pointer.

Diff Detail

Event Timeline

samparker created this revision.Jan 15 2019, 6:57 AM
efriedma added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12644

This needs a better comment explaining exactly what cases this is rejecting, and which cases it is accepting. (I'm not sure I follow the logic here. What cases need to be rejected for correctness? Are there cases which could be transformed, but shouldn't be transformed to avoid register copies?)

I'm a bit concerned about performance here. isPredecessorOf is expensive.

samparker updated this revision to Diff 182029.Jan 16 2019, 6:30 AM

Hi Eli,

I've added more tests and a few comments.

Yes, predecessor checks are expensive, how about adding an upper limit of uses and/or performing this check under a target flag?

hasPredecessorHelper supports a limit, that would be fine, probably. (The check is probably fast enough in practice in common cases, so it should be fine as long as it doesn't explode quadratically in extreme cases.)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12664

Could you clarify what "last use" means? It's not obvious when you're dealing with a DAG. I guess it means the store must be scheduled after every other use of BasePtr?

12666

I think this could still use a bit more clarification...

There are two different uses of ReplaceAllUsesOfValueWith which could cause a cycle related to stored value: the replacement of Ptr with the pre-indexed result, and the rewritten arithmetic relative to BasePtr in OtherUses. Are you trying to prevent both those cycles? Could we be more aggressive if we separated those checks?

12669

The equality check here seems suspect; what if Val is a use of one of the direct users of BasePtr?

samparker marked 4 inline comments as done.Jan 17 2019, 7:13 AM
samparker added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12664

Yes, scheduled last is what I mean.

12666

So yes, I am trying to make sure that Ptr can be replaced legally and I have assumed that by allowing the last scheduled user to be a pre-indexed store, we don't have to worry about OtherUses. Though I am now confused after re-reading statement (3) from above which appears to directly contradict my thoughts.

12669

Hmm. Would it be valid to create an ADD/SUB node and check whether it becomes a predecessor of Val...?

I just did a very brief experiment, and just checking if (Val == BasePtr || Val == Ptr || Ptr->isPredecessorOf(Val.getNode())) seems to do the right thing without any additional checks. Is all this extra code really necessary?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12666

There's a hasPredecessorHelper call later; I think that handles cases like (3).

12669

ADD/SUB of what, exactly?

More generally, we want to avoid performing predecessor checking more than once, since it's expensive.

I just did a very brief experiment, and just checking if (Val == BasePtr || Val == Ptr || Ptr->isPredecessorOf(Val.getNode())) seems to do the right thing without any additional checks.

Err, nevermind, that doesn't do anything; please ignore.

I just did a very brief experiment, and just checking if (Val == BasePtr || Val == Ptr || Ptr->isPredecessorOf(Val.getNode())) seems to do the right thing without any additional checks.

Err, nevermind, that doesn't do anything; please ignore.

Hmm... actually, I'm just confusing myself. My suggestion appears to fix your pre_inc_str_multi without causing any regressions (although I haven't run anything outside the regression tests). I'm assuming that's the primary case you're interested in?

samparker updated this revision to Diff 182874.Jan 22 2019, 2:57 AM

Thanks for your suggestion Eli, that works for me.

This revision is now accepted and ready to land.Jan 22 2019, 1:23 PM
This revision was automatically updated to reflect the committed changes.