[DAGCombine] Improve alias analysis for chain of independent stores.
ClosedPublic

Authored by niravd on Mon, Oct 22, 8:32 PM.

Details

Summary

FindBetterNeighborChains simulateanously improves the chain
dependencies of a chain of related stores avoiding the generation of
extra token factors. For chains longer than the GatherAllAliasDepths,
stores further down in the chain will necessarily fail, a potentially
significant waste and preventing otherwise trivial parallelization.

This patch directly parallelize the chains of stores before improving
each store. This generally improves DAG-level parallelism.

Diff Detail

Repository
rL LLVM
niravd created this revision.Mon, Oct 22, 8:32 PM

courbet@, I think this should produce at least as good compile time as D53289. Can you verify on your testcase? If so, I move we drop D53289 (and D31068) in favor of this.

llvm/test/CodeGen/Mips/fastcc.ll
226 ↗(On Diff #170565)

Apparently FileCheck balks at dealing with this many too many deferred lines in a DAG match. This is just a noop reordering to be closer to the output asm.

courbet@, I think this should produce at least as good compile time as D53289. Can you verify on your testcase? If so, I move we drop D53289 (and D31068) in favor of this.

I have not had the time to look at the diff yet, but I patched it and re-ran the benchmarks. I can confirm that this fixes the compile-time performance issue as well or better as D53289:

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
19060 ↗(On Diff #170565)

this is never used

courbet added inline comments.Fri, Oct 26, 2:12 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
18944 ↗(On Diff #170565)

I think readability would be much better if this was split a bit:

bool DAGCombiner::findBetterNeighborChains(StoreSDNode *St) {
  if (OptLevel == CodeGenOpt::None)
    return false;

  // This holds the base pointer, index, and the offset in bytes from the base
  // pointer.
  BaseIndexOffset BasePtr = BaseIndexOffset::match(St, DAG);

  // We must have a base and an offset.
  if (!BasePtr.getBase().getNode())
    return false;

  // Do not handle stores to undef base pointers.
  if (BasePtr.getBase().isUndef())
    return false;
  
  // First try to merge chained stores.
  StoreSDNode *STChain = St;
  SmallVector<StoreSDNode *, 8> ChainedStores = findChainedStores(STChain, BasePtr);
  if (ChainedStores.size() > 0) {
     mergeChainedStores(ChainedStores);
     return true;
  }

  // Improve St's Chain..
  SDValue BetterChain = FindBetterChain(St, St->getChain());
  if (St->getChain() != BetterChain) {
    replaceStoreChain(St, BetterChain);
    return true;
  }
  return false;
}

(maybe even merge findChainedStores into mergeChainedStores)

18950 ↗(On Diff #170565)

Please make this const to save the reader the trouble of tracking all uses.

18969 ↗(On Diff #170565)

this is unused

18982 ↗(On Diff #170565)

we're -> we

18984 ↗(On Diff #170565)

What about using llvm::IntervalMap<int64_t, int> for IntervalsCovered ? It would simplify the code here.

18987 ↗(On Diff #170565)

why are you checking the iterator (rhs) ? The first check should be enough.

19015 ↗(On Diff #170565)

please move this closer to where it's used.

19055 ↗(On Diff #170565)

remove

niravd updated this revision to Diff 171738.Tue, Oct 30, 11:19 AM
niravd marked 4 inline comments as done.

Simplify. Update chain after both parallelizing chain and individual chain improvements. Also use IntervalMap.

niravd marked 4 inline comments as done.Tue, Oct 30, 11:20 AM
courbet added inline comments.Mon, Nov 5, 2:41 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
19008 ↗(On Diff #171738)

every*

19022 ↗(On Diff #171738)

Why ? This is return true AFAICT...

19026 ↗(On Diff #171738)

ditto

19049 ↗(On Diff #171738)

interval*

19126 ↗(On Diff #171738)

Please fix the comment.

19127 ↗(On Diff #171738)

this returns true if St has no base and offset. This is weird. I know that this cannot happen because we just made the check above, but it's misleading and redundant. Maybe pass BasePtr to findBetterNeighborChains() and assert ?

niravd updated this revision to Diff 173002.Wed, Nov 7, 12:26 PM
niravd marked 7 inline comments as done.

Address comments (typos and comment fixes) and rebase.

courbet accepted this revision.Wed, Nov 7, 11:23 PM
This revision is now accepted and ready to land.Wed, Nov 7, 11:23 PM
This revision was automatically updated to reflect the committed changes.