Use the new 'InvariantInfo' property to eliminate redundant loads with --gvn.

[lvoufo]

Summary

While processing instructions in GVN, mark global variables and alloca instructions corresponding to each encountered invariant intrinsic call as indicating 'writeonce' memory locations that either have been written into or can be written into again (once). Then, while scanning instructions backwards looking for pointer dependencies for a given load instruction, be sure to temporarily disable or reset the markings, as appropriate.

This patch is a break-down of (corrected) D13606.

[sanjoy]

Please add some tests.

[lvoufo]

In D14004#273693, @sanjoy wrote:

Please add some tests.

See D14006. This is a split-up of a larger patch to help readability.

[nlewycky]

This adds a call to "processInvariantIntrinsic" in GVN.cpp, but there is no such function and it isn't defined in this patch?

[lvoufo]

In D14004#284819, @nlewycky wrote:

This adds a call to "processInvariantIntrinsic" in GVN.cpp, but there is no such function and it isn't defined in this patch?

processInvariantIntrinsic is defined in D14003, which this patch depends on. Does this help?

lib/Analysis/MemoryDependenceAnalysis.cpp

MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom(
   if (isLoad && QueryInst) {
     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
     if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
       isInvariantLoad = true;
   }
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
+  // We're about to scan backwards. Preserve the initial invariant_start
+  // intrinsic marking on this load, for subsequent instructions.
+  // First, compute the info to preserve.
+  // Then, actually preserve the info before backward scanning starts.
+  InvariantInfo &InvInfo = BB->getModule()->getInvariantInfo();
+  PreservedInvariantInfo Preserved(isLoad ? QueryInst : nullptr, DL, InvInfo);
+  PreserveInvariantInfo PIO(Preserved);
+
   // Create a numbered basic block to lazily compute and cache instruction
   // positions inside a BB. This is used to provide fast queries for relative
   // position between two instructions in a BB and can be used by
   // AliasAnalysis::callCapturesBefore.
   OrderedBasicBlock OBB(BB);
 
   // Walk backwards through the basic block, looking for dependencies.
   while (ScanIt != BB->begin()) {
     Instruction *Inst = --ScanIt;
 
-    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       // Debug intrinsics don't (and can't) cause dependencies.
       if (isa<DbgInfoIntrinsic>(II)) continue;
 
+      // Same for invariant intrinsics, which may also unset preserved
+      // invariant info.
+      if (BackwardScanInvariantIntrinsic(II, Preserved, InvInfo)) continue;
+    }
+
     // Limit the amount of scanning we do so we don't end up with quadratic
     // running time on extreme testcases.
     --Limit;
     if (!Limit)
       return MemDepResult::getUnknown();
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       // If we reach a lifetime begin or end marker, then the query ends here

lib/Transforms/Scalar/GVN.cpp

 
 /// When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
 bool GVN::processInstruction(Instruction *I) {
   // Ignore dbg info intrinsics.
   if (isa<DbgInfoIntrinsic>(I))
     return false;
 
+
+  // Also ignore invariant intrinsics, after processing them.
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+    InvariantInfo &InvInfo = I->getModule()->getInvariantInfo();
+    if (processInvariantIntrinsic(II, InvInfo)) return false;
+  }
+
   // If the instruction can be easily simplified then do so now in preference
   // to value numbering it.  Value numbering often exposes redundancies, for
   // example if it determines that %y is equal to %x then the instruction
   // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
   const DataLayout &DL = I->getModule()->getDataLayout();
   if (Value *V = SimplifyInstruction(I, DL, TLI, DT, AC)) {
     I->replaceAllUsesWith(V);
     if (MD && V->getType()->getScalarType()->isPointerTy())