[SelectionDAGIsel] Long series of chained stores may cause severe compile-time regression in instruction selection lowering

[llvmbot]

Bugzilla Link	21759
Version	trunk
OS	Linux
Attachments	Bad IR, Bad IR after InstCombine
Reporter	LLVM Bugzilla Contributor
CC	@chandlerc,@hfinkel,@jmolloy,@TNorthover

Extended Description

Unfortunately, I can only reproduce this on our internal branch, but the problem exists on mainline as well.

Given the following loop:

void foo (int a[]) { int ptr = a; for (int i = 0; i <= 127; i++) ptr++ = 0xff; }

Our internal branch will completely unroll the loop during the second call to the LoopUnrollPass. The resulting IR (see attached bad.ll) causes a severe compile-time regression when instruction selection begins recursively calling WalkChainUsers in SelectionDAGISel.cpp.

If unrolling occurs during the first call to the LoopUnrollPass a later call to InstCombine removes the chain by having all the gep use base + offset (see attached bad.instcombine.ll).

I imagine the simplest solution would be to run InstCombine after the second loop unrolling pass, but I'd like to get feedback before moving forward.

[llvmbot]

http://reviews.llvm.org/D16340

[llvmbot]

One of our internal developers has proposed caching the chain results.

Does the below look like a reasonable solution? If so, I'll upload a complete patch and associated test cases.

---

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index a610e57..5f43296 100755 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1980,6 +1980,8 @@ enum ChainResult { CR_LeadsToInteriorNode };

+typedef DenseMap<const SDNode , ChainResult> TFCacheMapT; + /// WalkChainUsers - Walk down the users of the specified chained node that is /// part of the pattern we're matching, looking at all of the users we find. /// This determines whether something is an interior node, whether we have a @@ -1992,7 +1994,8 @@ enum ChainResult { static ChainResult WalkChainUsers(const SDNode ChainedNode, SmallVectorImpl<SDNode*> &ChainedNodesInPattern,

• SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
• SmallVectorImpl<SDNode*> &InteriorChainedNodes,

• TFCacheMapT &TFCacheMap) { ChainResult Result = CR_Simple;

  for (SDNode::use_iterator UI = ChainedNode->use_begin(), @@ -2073,7 +2076,16 @@ WalkChainUsers(const SDNode *ChainedNode, // as a new TokenFactor. // // To distinguish these two cases, do a recursive walk down the uses.

• switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
• ChainResult UserResult;
• if (TFCacheMap.count(User)) {
• UserResult = TFCacheMap[User];
• } else {
• UserResult = WalkChainUsers(User, ChainedNodesInPattern,
• InteriorChainedNodes, TFCacheMap);
• TFCacheMap[User] = UserResult;
• }
• switch (UserResult) { case CR_Simple: // If the uses of the TokenFactor are just already-selected nodes, ignore // it, it is "below" our pattern. @@ -2114,9 +2126,10 @@ HandleMergeInputChains(SmallVectorImpl<SDNode> &ChainNodesMatched, // users of the chain result. This adds any TokenFactor nodes that are caught // in between chained nodes to the chained and interior nodes list. SmallVector<SDNode, 3> InteriorChainedNodes;
• TFCacheMapT TFCacheMap; for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
• InteriorChainedNodes) == CR_InducesCycle)
• InteriorChainedNodes, TFCacheMap) == CR_InducesCycle) return SDValue(); // Would induce a cycle. }

[llvmbot]

Some additional context. Internally, if we see a loop that has a known iteration count, and the body of the loop could be simplified by complete unrolling, we increase the threshold to make the loop more likely to be unrolled. Unlike the community branch, we double the threshold on the second call to the LoopUnrollPass, which is exposing the issue.