Page MenuHomePhabricator

[DAG] Improve candidate pruning in store merge failure case. NFCI
ClosedPublic

Authored by niravd on Jul 26 2017, 9:40 AM.

Details

Summary

During store merge we construct a sorted list of consecutive store candidates and consider
subsequences for merging into a single store. For each subsequence we check if the stored
value type is legal the merged store would have valid and fast and if the constructed value
to be stored is valid. The only properties that affect this check between subsequences is the
size of the subsequence, the alignment of the first store, the alignment of the stored load
value (when merging stores-of-loads), and whether the merged value is a constant zero.

If we do not find a viable mergeable subsequence starting from the first store of length N,
we know that a subsequence starting at a later store of length N will also fail unless the
new store's alignment, the new load's alignment (if we're merging store-of-loads), or we've
dropped stores of nonzero value and could construct a merged stores of zero (for merging
constants).

As a result if we fail to find a valid subsequence starting from the first store we can safely
skip considering subsequences that start with subsequent stores unless one of the above
properties is true. This significantly (2x) improves compile time in some pathological cases.

Diff Detail

Repository
rL LLVM

Event Timeline

niravd created this revision.Jul 26 2017, 9:40 AM
niravd planned changes to this revision.Jul 26 2017, 10:57 AM
niravd updated this revision to Diff 108336.Jul 26 2017, 11:49 AM
niravd edited the summary of this revision. (Show Details)

In addition to alignment, we less restrictive of const zero stores over other constant stores. Add logic to prevent skipping zero cases.

grandinj added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12853 ↗(On Diff #108336)

beggining -> beginning

12855 ↗(On Diff #108336)

another of the same size would not have does not is if the
->
another of the same size would not have, is if the

12927 ↗(On Diff #108336)

ditto x 2

niravd updated this revision to Diff 108490.Jul 27 2017, 9:35 AM

Comment cleanup and apply same logic to final leg of store merge reasoning.

niravd marked 3 inline comments as done.Jul 27 2017, 9:38 AM
niravd retitled this revision from [DAG] Improve candidate pruning in store merge failure case. NFC. to [DAG] Improve candidate pruning in store merge failure case. NFCI.Jul 31 2017, 8:51 AM
niravd edited the summary of this revision. (Show Details)
niravd added a reviewer: waltl.Aug 2 2017, 7:28 AM
niravd updated this revision to Diff 109356.Aug 2 2017, 8:15 AM
niravd edited the summary of this revision. (Show Details)

Cleanup FirstZeroAfterNonZero calc.

waltl accepted this revision.Aug 2 2017, 9:17 AM
This revision is now accepted and ready to land.Aug 2 2017, 9:17 AM
This revision was automatically updated to reflect the committed changes.