Fold constant & invariant loads into uses over barrier instructions

[reames]

Summary

PeepholeOpt knows how to fold loads into using instructions, but if we encounter an instruction w/store semantics, we discard all candidates. This patch relaxes that slightly for memory accesses which are known to be invariant. This is one step towards a more general selective clearing based on aliasing, but doing the full aliasing scheme efficiently would be challenging.

There are two design questions which come up where I need input from reviewers:

1. Currently, loads from constant global variables are not treated as invariant when queried from PeepholdOpt. This is because PeepholeOpt doesn't have access to AA, and the query function uses pointsToConstantMemory. I can tackle this in three ways: a) add direct GV checking in the query routine, or b) set the associated flag in SslectionDAG, or c) pipe through AA. (c) would be complicated, so I'm tentatively rejecting that. Out of (a) and (b), what is more consistent with overall design? I've included both in the patch so that you can see what they look like.
2. The patch implemented waits until a fold barrier is encountered, and the selectively filtered the sets. Unfortunately, this makes the operation O(n^2) in the worst case. Other options would be to maintain a separate InvariantFoldSet - O(n) - or to simply query each operand at the using instruction - O(operands), but provides cross block functionality. What would folks prefer to see?

p.s. The current tests are all atomic loads, but there's nothing atomic specific about this. I'll add new tests, and rebase once the design questions are mostly settled.

[reames]

Ready for review.

[reames]

ping?

[jfb]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

4555

?

4574

?

[reames]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

4555

See the patch comment (part 1)

[reames]

Abandoning an old review I'm not going to return to any time soon.

lib/CodeGen/MachineInstr.cpp

if (MMO->isInvariant() && MMO->isDereferenceable())
       continue;
 
     // A load from a constant PseudoSourceValue is invariant.
     if (const PseudoSourceValue *PSV = MMO->getPseudoValue())
       if (PSV->isConstant(&MFI))
         continue;
 
     if (const Value *V = MMO->getValue()) {
+      // In case we don't have AA, handle a few common cases
+      if (auto *GV = dyn_cast<GlobalVariable>(V))
+        if (GV->isConstant() &&
+            MMO->getSize() <= GV->getParent()->getDataLayout().getTypeStoreSize(GV->getType()))
+          continue;
       // If we have an AliasAnalysis, ask it whether the memory is constant.
       if (AA &&
           AA->pointsToConstantMemory(
               MemoryLocation(V, MMO->getSize(), MMO->getAAInfo())))
         continue;
     }
 
     // Otherwise assume conservatively.

lib/CodeGen/PeepholeOptimizer.cpp

for (MachineBasicBlock::iterator MII = MBB.begin(), MIE = MBB.end();
         }
       }
 
       // If we run into an instruction we can't fold across, discard
       // the load candidates.  Note: We might be able to fold *into* this
       // instruction, so this needs to be after the folding logic.
       if (MI->isLoadFoldBarrier()) {
         LLVM_DEBUG(dbgs() << "Encountered load fold barrier on " << *MI);
-        FoldAsLoadDefCandidates.clear();
+        SmallSet<unsigned, 16> InvariantDefs;
+        for (unsigned VReg : FoldAsLoadDefCandidates) {
+          auto *DefMI = MRI->getVRegDef(VReg);
+          if (!DefMI->isDereferenceableInvariantLoad(nullptr))
+            continue;
+          InvariantDefs.insert(VReg);
+        }
+        FoldAsLoadDefCandidates = InvariantDefs;
       }
     }
   }
 
   return Changed;
 }
 
 ValueTrackerResult ValueTracker::getNextSourceFromCopy() {

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitFence(const FenceInst &I) {
   DAG.setRoot(DAG.getNode(ISD::ATOMIC_FENCE, dl, MVT::Other, Ops));
 }
 
 void SelectionDAGBuilder::visitAtomicLoad(const LoadInst &I) {
   SDLoc dl = getCurSDLoc();
   AtomicOrdering Order = I.getOrdering();
   SyncScope::ID SSID = I.getSyncScopeID();
 
+#if 0
+  AAMDNodes AAInfo;
+  I.getAAMetadata(AAInfo);
+#endif
+
   SDValue InChain = getRoot();
 
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   EVT VT = TLI.getValueType(DAG.getDataLayout(), I.getType());
 
   if (!TLI.supportsUnalignedAtomics() &&
       I.getAlignment() < VT.getStoreSize())
     report_fatal_error("Cannot generate unaligned atomic load");
 
   auto Flags = MachineMemOperand::MOLoad;
   if (I.isVolatile())
     Flags |= MachineMemOperand::MOVolatile;
   if (I.getMetadata(LLVMContext::MD_invariant_load) != nullptr)
     Flags |= MachineMemOperand::MOInvariant;
+#if 0
+  if (AA &&
+      AA->pointsToConstantMemory(MemoryLocation(I.getPointerOperand(),
+                                                LocationSize::precise(DAG.getDataLayout().getTypeStoreSize(I.getType())),
+                                                AAInfo)))
+    Flags |= MachineMemOperand::MOInvariant;
+#endif
   if (isDereferenceablePointer(I.getPointerOperand(), DAG.getDataLayout()))
     Flags |= MachineMemOperand::MODereferenceable;
 
   Flags |= TLI.getMMOFlags(I);
 
   MachineMemOperand *MMO =
       DAG.getMachineFunction().
       getMachineMemOperand(MachinePointerInfo(I.getPointerOperand()),

test/CodeGen/X86/atomic-unordered.ll

 ; CHECK-O0:       # %bb.0:
 ; CHECK-O0-NEXT:    movq {{.*}}(%rip), %rax
 ; CHECK-O0-NEXT:    movq $5, (%rdi)
 ; CHECK-O0-NEXT:    addq %rsi, %rax
 ; CHECK-O0-NEXT:    retq
 ;
 ; CHECK-O3-LABEL: fold_constant_clobber:
 ; CHECK-O3:       # %bb.0:
-; CHECK-O3-NEXT:    movq {{.*}}(%rip), %rax
+; CHECK-O3-NEXT:    movq %rsi, %rax
 ; CHECK-O3-NEXT:    movq $5, (%rdi)
-; CHECK-O3-NEXT:    addq %rsi, %rax
+; CHECK-O3-NEXT:    addq {{.*}}(%rip), %rax
 ; CHECK-O3-NEXT:    retq
   %v = load atomic i64, i64* @Constant unordered, align 8
   store i64 5, i64* %p
   %ret = add i64 %v, %arg
   ret i64 %ret
 }
 
 define i64 @fold_constant_fence(i64 %arg) {
 ; CHECK-O0-LABEL: fold_constant_fence:
 ; CHECK-O0:       # %bb.0:
 ; CHECK-O0-NEXT:    movq {{.*}}(%rip), %rax
 ; CHECK-O0-NEXT:    mfence
 ; CHECK-O0-NEXT:    addq %rdi, %rax
 ; CHECK-O0-NEXT:    retq
 ;
 ; CHECK-O3-LABEL: fold_constant_fence:
 ; CHECK-O3:       # %bb.0:
-; CHECK-O3-NEXT:    movq {{.*}}(%rip), %rax
+; CHECK-O3-NEXT:    movq %rdi, %rax
 ; CHECK-O3-NEXT:    mfence
-; CHECK-O3-NEXT:    addq %rdi, %rax
+; CHECK-O3-NEXT:    addq {{.*}}(%rip), %rax
 ; CHECK-O3-NEXT:    retq
   %v = load atomic i64, i64* @Constant unordered, align 8
   fence seq_cst
   %ret = add i64 %v, %arg
   ret i64 %ret
 }
 
 define i64 @fold_invariant_clobber(i64* dereferenceable(8) %p, i64 %arg) {
 ; CHECK-O0-LABEL: fold_invariant_clobber:
 ; CHECK-O0:       # %bb.0:
 ; CHECK-O0-NEXT:    movq (%rdi), %rax
 ; CHECK-O0-NEXT:    movq $5, (%rdi)
 ; CHECK-O0-NEXT:    addq %rsi, %rax
 ; CHECK-O0-NEXT:    retq
 ;
 ; CHECK-O3-LABEL: fold_invariant_clobber:
 ; CHECK-O3:       # %bb.0:
-; CHECK-O3-NEXT:    movq (%rdi), %rax
+; CHECK-O3-NEXT:    movq %rsi, %rax
 ; CHECK-O3-NEXT:    movq $5, (%rdi)
-; CHECK-O3-NEXT:    addq %rsi, %rax
+; CHECK-O3-NEXT:    addq (%rdi), %rax
 ; CHECK-O3-NEXT:    retq
   %v = load atomic i64, i64* %p unordered, align 8, !invariant.load !{}
   store i64 5, i64* %p
   %ret = add i64 %v, %arg
   ret i64 %ret
 }
 
 
 define i64 @fold_invariant_fence(i64* dereferenceable(8) %p, i64 %arg) {
 ; CHECK-O0-LABEL: fold_invariant_fence:
 ; CHECK-O0:       # %bb.0:
 ; CHECK-O0-NEXT:    movq (%rdi), %rdi
 ; CHECK-O0-NEXT:    mfence
 ; CHECK-O0-NEXT:    addq %rsi, %rdi
 ; CHECK-O0-NEXT:    movq %rdi, %rax
 ; CHECK-O0-NEXT:    retq
 ;
 ; CHECK-O3-LABEL: fold_invariant_fence:
 ; CHECK-O3:       # %bb.0:
-; CHECK-O3-NEXT:    movq (%rdi), %rax
+; CHECK-O3-NEXT:    movq %rsi, %rax
 ; CHECK-O3-NEXT:    mfence
-; CHECK-O3-NEXT:    addq %rsi, %rax
+; CHECK-O3-NEXT:    addq (%rdi), %rax
 ; CHECK-O3-NEXT:    retq
   %v = load atomic i64, i64* %p unordered, align 8, !invariant.load !{}
   fence seq_cst
   %ret = add i64 %v, %arg
   ret i64 %ret
 }