Page MenuHomePhabricator

Fix CombineToPreIndexedLoadStore O(n^2) behavior
ClosedPublic

Authored by timshen on Jan 26 2016, 4:16 PM.

Details

Summary

This patch consists of two parts: a performance fix in DAGCombiner.cpp and a correctness fix in SelectionDAG.cpp.

The test case tests the bug that's uncovered by the performance fix, and fixed by the correctness fix.

The performance fix keeps the containers required by the hasPredecessorHelper (which is a lazy DFS) and reuse them. Since hasPredecessorHelper is called in a loop, the overall efficiency reduced from O(n^2) to O(n), where n is the number of SDNodes.

The correctness fix keeps iterating the neighbor list even if it's time to early return. It will return after finishing adding all neighbors to Worklist, so that no neighbors are discarded due to the original early return.

Diff Detail

Event Timeline

timshen updated this revision to Diff 46070.Jan 26 2016, 4:16 PM
timshen retitled this revision from to Fix CombineToPreIndexedLoadStore O(n^2) behavior.
timshen updated this object.
timshen added reviewers: echristo, iteratee.
timshen added a subscriber: llvm-commits.
iteratee added inline comments.Jan 26 2016, 4:27 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
9596

Can you add a const annotation to N so that this is obviously correct?

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
6936

Can you add some header comments for hasPredecessorHelper while you're here?

timshen marked an inline comment as done.Jan 26 2016, 4:58 PM
timshen added inline comments.
lib/CodeGen/SelectionDAG/SelectionDAG.cpp
6936

I agree with you in technical perspective, but it's conventional not to make a function parameter passed by const value for reasons I don't quite know :P.

Another solution is to make a local const copy of N and use that, but then it's confusing in another way, since there are more variables.

timshen marked 3 inline comments as done.Jan 26 2016, 5:16 PM
timshen added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
9596

I agree with you in technical perspective, but it's conventional not to make a function parameter passed by const value for reasons I don't quite know :P.

Another solution is to make a local const copy of N and use that, but then it's confusing in another way, since there are more variables.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
6936

Sorry - above is the reply for the previous comment.

For this comment - I think we already got complete comment in include/llvm/CodeGen/SelectionDAGNodes.h

iteratee accepted this revision.Jan 27 2016, 5:38 PM
iteratee edited edge metadata.

I'm OK with this. If you can find someone in the next few days that's more familiar with this, that would be good, but It looks just fine to me.

This revision is now accepted and ready to land.Jan 27 2016, 5:38 PM
timshen marked 2 inline comments as done.

Added hfinkel for a double check - got the name from git blame.

timshen updated this revision to Diff 46349.Jan 28 2016, 9:17 PM

Modify test to take input from stdin.

majnemer added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
9596

Comments should be complete sentences.

9615

Please format this with clang-format

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
6958

Please clang-format this.

6960

And this.

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll
2

No FileCheck lines?

timshen updated this revision to Diff 46355.Jan 28 2016, 10:48 PM

Update format and comment.

timshen marked 6 inline comments as done.Jan 28 2016, 10:50 PM
timshen added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
9615

I was using a very old version. Re-formanted using trunk version. Thanks!

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll
2

Yes, the error is a crash, as the file name indicates

echristo added inline comments.Jan 28 2016, 10:56 PM
test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll
3

In general you should still check that the correct code is generated out of the other end if you can.

timshen updated this revision to Diff 46357.Jan 28 2016, 11:15 PM
timshen marked 2 inline comments as done.

Add CHECKs for test.

timshen marked 2 inline comments as done.Jan 28 2016, 11:17 PM
timshen added inline comments.
test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll
3

I didn't put very specific logic check into the test, since that may cause brittle test.

hfinkel accepted this revision.Feb 2 2016, 6:06 PM
hfinkel edited edge metadata.

LGTM too.

timshen closed this revision.Feb 3 2016, 1:08 PM
timshen marked an inline comment as done.

Committed as r259691.