Page MenuHomePhabricator

Prevent construction of cycle in DAG store merge

Authored by niravd on Mar 21 2016, 2:40 PM.



When merging stores, add checks to ensure that no data dependences are introduced. Previously we checked only chain dependencies but ignored data dependencies.
There two checks capture the differences between the cases where we use Anti-aliasing (and can limit the search chain-parallel stores) vs. when we do not and consider direct chains of stores.

Diff Detail


Event Timeline

yinma updated this revision to Diff 51233.Mar 21 2016, 2:40 PM
yinma retitled this revision from to Prevent cycle in DAG store merge to vector.
yinma updated this object.

Adding reviewers of:

Does that patch resolve this case?

Changing finding better chain algorithm may hide the problem fixed by this patch, but for our test case, changing the FindBetterChain algorithm doesn't help.

niravd commandeered this revision.Mar 24 2016, 11:09 AM
niravd edited reviewers, added: yinma; removed: niravd.

This is incomplete. It's missing the case for UseAA merges (which is also needed to resolve the underlying bug 18321/14834). I have a patch that captures this, though I haven't gotten a test which will exercises the useAA case.

Comandeering to upload patch.

niravd updated this revision to Diff 51572.Mar 24 2016, 11:11 AM
niravd updated this object.
niravd edited edge metadata.

Add check to ensuring no loops in data dependences are constructed from store merging
in the case we use Anti-aliasing analysis.

niravd retitled this revision from Prevent cycle in DAG store merge to vector to Prevent construction of cycle in DAG store merge.Mar 24 2016, 11:22 AM
niravd updated this object.
jyknight added inline comments.Mar 24 2016, 12:03 PM
11136 ↗(On Diff #51572)

I'm not sure if it's valid to use setNodeId here. But that's irrelevant, because this function shouldn't exist, since the code should be using hasPredecessor.

11182 ↗(On Diff #51572)

There are formatting/spacing issues throughout this. Please clang-format.

11192 ↗(On Diff #51572)

This is obfuscated; please refactor the hasPredecessor family to have a static function which requires the worklist to be pre-populated, instead of passing in a dummy node here.

11205 ↗(On Diff #51572)

Should use hasPredecessor.

10 ↗(On Diff #51572)

This test can almost certainly be simplified. It would be nice to spend a bit of time to remove irrelevant stuff from it so it's easier to see what's actually going on is just:
%l1 = load
store half of %l1 -> offset 0
%l2 = load
store half of %l2 -> offset -1
store half of %l2 -> offset 1

And then, merging the store to offsets -1 and 0 into a single store, which results in the %l2 load chain-depending on it, but yet the merged-store requires that load as a value.

(I think)

niravd updated this revision to Diff 51583.Mar 24 2016, 12:19 PM
niravd updated this object.

Test now correctly fails without this patch and succeed with

yinma edited edge metadata.Mar 24 2016, 1:42 PM

Hi Nirav, I think the problem need to be solved should be the same with and without AA. It is testing the node predecessors. For your new upload, you use different check with UseAA. For my algorithm, it only tests the latest node in the store array because it is the one that links with the successors. Do you have another test case that shows failure with UseAA? What could be the different with UseAA?

yinma added inline comments.Mar 24 2016, 1:47 PM
11184 ↗(On Diff #51583)

if UseAA creates a different but broader case. we should try to merge testing with UseAA and without UsaAA to be one testing.

11 ↗(On Diff #51583)

My code is reduced by bugpoint, The idea is shown exactly in your suggestion.

niravd updated this revision to Diff 51601.Mar 24 2016, 2:03 PM
niravd edited edge metadata.
  • Add useAA case

There are two cases we do. In the case of AA we look for stores which are
parallel in regards to the chain dependencies. Otherwise we walk up the
chain to merge stores. Either way we fail to check if there are data
dependencies that we contradict (i.e. make a cycle).

Your patch handles the later case only because it relies on the fact that
all stores are predecessors to the latest one and there are not multiple
chain descendent. Thus if we walk through uses of that we implicitly are
doing the walk for all of them but it wouldn't necessarily hold in the
parallel case.

You're right about us only needing one path. We could unify them modifying
the parallel case to searching up the non-chain operands and not stores
themselves to avoid chained stores from always failing. Once D14834 is
committed the nonparallel case will disappear and we can return to the
simpler case.

niravd updated this revision to Diff 51612.Mar 24 2016, 3:35 PM

Implement hasPredecessorHelper cleanup and merge two checks as per discussion
cleanup hasPredecessorHelper fixes and merge checks back together as per discussions

jyknight added inline comments.Mar 25 2016, 7:02 AM
628 ↗(On Diff #51612)

Lots of typos. Visitedo. unino. "operand_dependences" sounds like it's referring to a variable or function but isn't actually.

"Null" is strangely capitalized.

Much of the old comment you deleted seems still relevant, too.

634 ↗(On Diff #51612)

Why removed the Visited check? It seems to me like that was still a more natural interface.

Then you can just ask all your "is Node X a predecessor" questions with the same interface.

9638 ↗(On Diff #51612)

Why search completely? Isn't it better to escape early if you happen to be able to?

11158–11160 ↗(On Diff #51612)

This comment isn't very clear.

11166 ↗(On Diff #51612)

That you're skipping the chain operand deserves a mention, here.

12 ↗(On Diff #51612)

Yes, I see that. It's just that there's a lot of (probably?) irrelevant metadata args which can be removed, variable names shortened/made clearer, possibly the loop could go away too.

And a comment in the test about what it is actually intending to test would be good, too.

niravd updated this revision to Diff 51637.Mar 25 2016, 8:04 AM
niravd marked 7 inline comments as done.

Cleanup comments and revert removal of early exit in HasPredecessorHelper calls

niravd updated this revision to Diff 51639.Mar 25 2016, 8:58 AM
niravd marked 3 inline comments as done.

Simplify test case.

niravd marked 3 inline comments as done.Mar 25 2016, 8:58 AM

All code and testcase comments resolved.

jyknight added inline comments.Mar 25 2016, 9:08 AM
9687 ↗(On Diff #51639)

Missed this spot.

11160 ↗(On Diff #51639)

"indirectly" is in there twice.

11162 ↗(On Diff #51639)

redundant "candidate".

13 ↗(On Diff #51639)

Still need to add comment about what the test is testing.

niravd updated this revision to Diff 51644.Mar 25 2016, 9:31 AM

Add missing test case comment

niravd marked an inline comment as done.Mar 25 2016, 9:38 AM
niravd added inline comments.
14 ↗(On Diff #51644)


niravd updated this revision to Diff 51659.Mar 25 2016, 10:54 AM
niravd marked an inline comment as done.

Fix comment and stray reference for Visited.count

niravd updated this revision to Diff 51681.Mar 25 2016, 1:30 PM

Separate check into a separate function.
Fix test case to check both AA and non-AA cases.
Do loop dependences check only in AA cases

jyknight accepted this revision.Mar 25 2016, 2:02 PM
jyknight edited edge metadata.

Thanks, lgtm.

Note for readers: we spent some time going over this, and noted that 1) The original test case was using UseAA mode (which we'd not noticed before) 2) The bug doesn't actually exist in !UseAA, because of the different way it traverses the chain.

So this final version reflects that.

This revision is now accepted and ready to land.Mar 25 2016, 2:02 PM
This revision was automatically updated to reflect the committed changes.