[DAGCombine] Allow alias analysis with inline asm calls and GluedNodes.

[niravd]

Summary

Teach alias analysis to reason about inline assembly nodes and
associated glued CopyToReg/CopyFromReg nodes.

This fixes PR9517.

[niravd]

Rebase to tip.

[hfinkel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

19381

Please document here what each member of the pair represents.

[niravd]

Add comments.

[niravd]

Ping.

[niravd]

Ping.

[efriedma]

llvm/test/CodeGen/X86/oddshuffles.ll

1670 ↗

(On Diff #169013)

Why is this changing? I don't see any inline asm...

[niravd]

Rebase to tip.

[niravd]

oddshuffles.ll is definitely unrelated. It seems to have disappeared post rebase. Not sure how it appears as neither this patch or its predecessor patch touched it.

[efriedma]

I'm not sure I like the algorithm here. It seems like it would be more straightforward to handle the INLINEASM and all the glued nodes together, in a separate inner loop.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

19453–19454

Wrong indentation.

19461–19462

I don't think there's an comment anywhere explaining why you're putting chain operands into the visited list? Thinking about it a bit, I guess you're trying to avoid computing "useless" aliases? Does that actually work reliably, given the visitation order of the operands of a TokenFactor is sort of arbitrary?

19464

Commented-out code?

19472

Incomplete comment?

[niravd]

Rebase, improve comments and minor name cleanup.

[niravd]

NFC Refactoring of GatherAllAliases on top of which the patch will occur.

[niravd]

patch on to p of refactoring.

[niravd]

Abandoning this in favor of D59039

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (UseAA && AA &&
     if (AAResult == NoAlias)
       return false;
   }
 
   // Otherwise we have to assume they alias.
   return true;
 }
 
-/// Walk up chain skipping non-aliasing memory nodes,
-/// looking for aliasing nodes and adding them to the Aliases vector.
 void DAGCombiner::GatherAllAliases(LSBaseSDNode *N, SDValue OriginalChain,
                                    SmallVectorImpl<SDValue> &Aliases) {
   SmallVector<SDValue, 8> Chains;     // List of chains to visit.
   SmallPtrSet<SDNode *, 16> Visited;  // Visited node set.
 
   // Get alias information for node.
-  bool IsLoad = isa<LoadSDNode>(N) && !N->isVolatile();
+  const bool IsLoad = isa<LoadSDNode>(N) && !N->isVolatile();
 
   // Starting off.
   Chains.push_back(OriginalChain);
   unsigned Depth = 0;
 
+  // Attempt to improve chain by a single step
+  std::function<bool(SDValue &)> ImproveChain = [&](SDValue &C) -> bool {
+    switch (C.getOpcode()) {
+    case ISD::EntryToken:
+      // No need to mark EntryToken.
+      C = SDValue();
+      return true;
+    case ISD::LOAD:
+    case ISD::STORE: {
+      // Get alias information for C.
+      auto LSChain = cast<LSBaseSDNode>(C.getNode());
+      bool IsOpLoad = isa<LoadSDNode>(C.getNode()) && !LSChain->isVolatile();
+      if ((IsLoad && IsOpLoad) || !isAlias(N, LSChain)) {
+        // Look further up the chain.
+        C = C.getOperand(0);
+        return true;
+      }
+      // Alias, so stop here.
+      return false;
+    }
+
+    case ISD::CopyFromReg:
+      // Always forward past past CopyFromReg.
+      C = C.getOperand(0);
+      return true;
+    default:
+      return false;
+    }
+  };
+
   // Look at each chain and determine if it is an alias.  If so, add it to the
   // aliases list.  If not, then continue up the chain looking for the next
   // candidate.
   while (!Chains.empty()) {
     SDValue Chain = Chains.pop_back_val();
 
+    // Don't bother if we've seen Chain before.
+    if (!Visited.insert(Chain.getNode()).second)
+      continue;
+
     // For TokenFactor nodes, look at each operand and only continue up the
     // chain until we reach the depth limit.
     //
     // FIXME: The depth check could be made to return the last non-aliasing
     // chain we found before we hit a tokenfactor rather than the original
     // chain.
     if (Depth > TLI.getGatherAllAliasesMaxDepth()) {
       Aliases.clear();
       Aliases.push_back(OriginalChain);
       return;
     }
 
-    // Don't bother if we've been before.
-    if (!Visited.insert(Chain.getNode()).second)
-      continue;
-
-    switch (Chain.getOpcode()) {
-    case ISD::EntryToken:
-      // Entry token is ideal chain operand, but handled in FindBetterChain.
-      break;
-
-    case ISD::LOAD:
-    case ISD::STORE: {
-      // Get alias information for Chain.
-      bool IsOpLoad = isa<LoadSDNode>(Chain.getNode()) &&
-          !cast<LSBaseSDNode>(Chain.getNode())->isVolatile();
-
-      // If chain is alias then stop here.
-      if (!(IsLoad && IsOpLoad) &&
-          isAlias(N, cast<LSBaseSDNode>(Chain.getNode()))) {
-        Aliases.push_back(Chain);
-      } else {
-        // Look further up the chain.
-        Chains.push_back(Chain.getOperand(0));
-        ++Depth;
-      }
-      break;
-    }
-
-    case ISD::TokenFactor:
+    if (Chain.getOpcode() == ISD::TokenFactor) {
       // We have to check each of the operands of the token factor for "small"
       // token factors, so we queue them up.  Adding the operands to the queue
       // (stack) in reverse order maintains the original order and increases the
       // likelihood that getNode will find a matching token factor (CSE.)
       if (Chain.getNumOperands() > 16) {
         Aliases.push_back(Chain);
-        break;
+        continue;
       }
       for (unsigned n = Chain.getNumOperands(); n;)
         Chains.push_back(Chain.getOperand(--n));
       ++Depth;
-      break;
-
-    case ISD::CopyFromReg:
-      // Forward past CopyFromReg.
-      Chains.push_back(Chain.getOperand(0));
+      continue;
+    }
+    // Everything else
+    if (ImproveChain(Chain)) {
+      // Updated Chain Found, Consider new chain if one exists.
+      if (Chain.getNode())
+        Chains.push_back(Chain);
       ++Depth;
-      break;
-
-    default:
-      // For all other instructions we will just have to take what we can get.
-      Aliases.push_back(Chain);
-      break;
+      continue;
     }
+    // No Improved Chain Possible, treat as Alias.
+    Aliases.push_back(Chain);
   }
 }
 
 /// Walk up chain skipping non-aliasing memory nodes, looking for a better chain
 /// (aliasing node.)
 SDValue DAGCombiner::FindBetterChain(LSBaseSDNode *N, SDValue OldChain) {
   if (OptLevel == CodeGenOpt::None)
     return OldChain;
 
   // Ops for replacing token factor.
   SmallVector<SDValue, 8> Aliases;
 
   // Accumulate all the aliases to this node.
   GatherAllAliases(N, OldChain, Aliases);