Add basic support for removal of load that are fed by a store of an aggregate

[dotdash]

Summary

If we have a simple load through a GEP that is fed by a store of an
aggregate, we can use the GEP indices to walk the stored aggregate and
extract the appropriate value to replace the load.

include/llvm/Analysis/Loads.h

 
 #include "llvm/IR/BasicBlock.h"
 
 namespace llvm {
 
 class AliasAnalysis;
 class DataLayout;
 class MDNode;
+class StoreInst;
 
 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
 /// from this value cannot trap.  If it is not obviously safe to load from the
 /// specified pointer, we do a quick local scan of the basic block containing
 /// ScanFrom, to determine if the address is already accessed.
 bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
                                  unsigned Align,
                                  const DataLayout *TD = nullptr);

 /// load or store are recorded there.  If there are no AA tags or if no access
 /// is found, it is left unmodified.
 Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
                                 BasicBlock::iterator &ScanFrom,
                                 unsigned MaxInstsToScan = 6,
                                 AliasAnalysis *AA = nullptr,
                                 AAMDNodes *AATags = nullptr);
 
+/// ExtractValueFromStoredAggregate - Check if the pointer Ptr points
+/// into an aggregate stored by the SI in a way that allows to extract the
+/// value that it points at. If so return that value.
+Value *ExtractValueFromStoredAggregate(Value *Ptr, StoreInst *SI);
+
 }
 
 #endif

lib/Analysis/Loads.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       if (AreEquivalentAddressValues(StorePtr, StrippedPtr) &&
           CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(),
                                                AccessTy, DL)) {
         if (AATags)
           SI->getAAMetadata(*AATags);
         return SI->getOperand(0);
       }
 
+      if (Value *V = ExtractValueFromStoredAggregate(Ptr, SI)) {
+        if (AATags)
+          SI->getAAMetadata(*AATags);
+        return V;
+      }
+
       // If both StrippedPtr and StorePtr reach all the way to an alloca or
       // global and they are different, ignore the store. This is a trivial form
       // of alias analysis that is important for reg2mem'd code.
       if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
           (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
           StrippedPtr != StorePtr)
         continue;
 
if (Inst->mayWriteToMemory()) {
       return nullptr;
     }
   }
 
   // Got to the start of the block, we didn't find it, but are done for this
   // block.
   return nullptr;
 }
+
+/// ExtractValueFromStoredAggregate - Check if the pointer Ptr points
+/// into an aggregate stored by the SI in a way that allows to extract the
+/// value that it points at. If so return that value.
+Value *llvm::ExtractValueFromStoredAggregate(Value *Ptr, StoreInst *SI) {
+  // If this load is through a GEPI, we can possibly extract the loaded value
+  // from the stored aggregate
+  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) {
+    Value *StoredVal = SI->getValueOperand();
+    if (StoredVal->getType()->isAggregateType() &&
+        GEPI->getOperand(0) == SI->getPointerOperand() &&
+        GEPI->isInBounds() && GEPI->hasAllConstantIndices() &&
+        cast<ConstantInt>(GEPI->getOperand(1))->isZero()) {
+      std::vector<unsigned> Indices;
+      Indices.reserve(GEPI->getNumIndices());
+      for (auto II = GEPI->idx_begin() + 1, IE = GEPI->idx_end(); II != IE; ++II)
+        Indices.push_back(cast<ConstantInt>(*II)->getSExtValue());
+
+      return FindInsertedValue(StoredVal, Indices);
+    }
+  }
+
+  return nullptr;
+}

lib/Transforms/Scalar/GVN.cpp

if (DepInfo.isClobber()) {
                                                       DepSI, *DL);
           if (Offset != -1) {
             ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
                                                        DepSI->getValueOperand(),
                                                                 Offset));
             continue;
           }
         }
+
+        if (Value *V = ExtractValueFromStoredAggregate(
+              LI->getPointerOperand(), DepSI)) {
+          ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB, V));
+          continue;
+        }
       }
 
       // Check to see if we have something like this:
       //    load i32* P
       //    load i8* (P+1)
       // if we have this, replace the later with an extraction from the former.
       if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) {
         // If this is a clobber and L is the first instruction in its block, then
if (isCallocLikeFn(DepInst, TLI)) {
           DepBB, Constant::getNullValue(LI->getType())));
       continue;
     }
 
     if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
       // Reject loads and stores that are to the same address but are of
       // different types if we have to.
       if (S->getValueOperand()->getType() != LI->getType()) {
+        if (Value *V = ExtractValueFromStoredAggregate(
+              LI->getPointerOperand(), S)) {
+          ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB, V));
+          continue;
+        }
+
         // If the stored value is larger or equal to the loaded value, we can
         // reuse it.
         if (!DL || !CanCoerceMustAliasedValueToLoad(S->getValueOperand(),
                                                     LI->getType(), *DL)) {
           UnavailableBlocks.push_back(DepBB);
           continue;
         }
       }
if (AvailVal) {
       if (AvailVal->getType()->getScalarType()->isPointerTy())
         MD->invalidateCachedPointerInfo(AvailVal);
       markInstructionForDeletion(L);
       ++NumGVNLoad;
       return true;
     }
   }
 
-  // If the value isn't available, don't do anything!
   if (Dep.isClobber()) {
+    // Check if the load is fed by a store of an aggregate from which we can
+    // extract the value
+    if (StoreInst *DepSI = dyn_cast<StoreInst>(Dep.getInst())) {
+      if (Value *AvailVal = ExtractValueFromStoredAggregate(
+            L->getPointerOperand(), DepSI)) {
+        // Replace the load!
+        L->replaceAllUsesWith(AvailVal);
+        if (AvailVal->getType()->getScalarType()->isPointerTy())
+          MD->invalidateCachedPointerInfo(AvailVal);
+        markInstructionForDeletion(L);
+        ++NumGVNLoad;
+        return true;
+      }
+    }
+
+    // If the value isn't available, don't do anything!
     DEBUG(
       // fast print dep, using operator<< on instruction is too slow.
       dbgs() << "GVN: load ";
       L->printAsOperand(dbgs());
       Instruction *I = Dep.getInst();
       dbgs() << " is clobbered by " << *I << '\n';
     );
     return false;
bool GVN::processLoad(LoadInst *L) {
   Instruction *DepInst = Dep.getInst();
   if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
     Value *StoredVal = DepSI->getValueOperand();
 
     // The store and load are to a must-aliased pointer, but they may not
     // actually have the same type.  See if we know how to reuse the stored
     // value (depending on its type).
     if (StoredVal->getType() != L->getType()) {
-      if (DL) {
+      if (Value *V = ExtractValueFromStoredAggregate(
+            L->getPointerOperand(), DepSI))
+        StoredVal = V;
+      else if (DL) {
         StoredVal = CoerceAvailableValueToLoadType(StoredVal, L->getType(),
                                                    L, *DL);
         if (!StoredVal)
           return false;
 
         DEBUG(dbgs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal
                      << '\n' << *L << "\n\n\n");
       }

test/Transforms/GVN/load-from-fca.ll

+; RUN: opt -S -basicaa -gvn < %s | FileCheck %s
+
+define i8 @local_load_from_fca_def({ i8, i8 }* %tmp) {
+block1:
+  store { i8, i8 } { i8 0, i8 1 }, { i8, i8 }* %tmp
+  %ptr = getelementptr inbounds { i8, i8 }* %tmp, i64 0, i32 0
+  %val = load i8* %ptr
+  ret i8 %val
+; CHECK-NOT: %val = load i8* %ptr
+; CHECK: ret i8 0
+}
+
+define i8 @local_load_from_fca_clobber({ i8, i8 }* %tmp) {
+block1:
+  store { i8, i8 } { i8 0, i8 1 }, { i8, i8 }* %tmp
+  %ptr = getelementptr inbounds { i8, i8 }* %tmp, i64 0, i32 1
+  %val = load i8* %ptr
+  ret i8 %val
+; CHECK-NOT: %val = load i8* %ptr
+; CHECK: ret i8 1
+}
+
+define i8 @nonlocal_load_from_fca_def({ i8, i8 }* %tmp, i1 %c) {
+block1:
+  %ptr = getelementptr inbounds { i8, i8 }* %tmp, i64 0, i32 0
+  br i1 %c, label %then, label %out
+then:
+  br label %out
+out:
+  store { i8, i8 } { i8 2, i8 3 }, { i8, i8 }* %tmp
+  %val = load i8* %ptr
+  ret i8 %val
+; CHECK-NOT: %val = load i8* %ptr
+; CHECK: ret i8 2
+}
+
+define i8 @nonlocal_load_from_fca_clobber({ i8, i8 }* %tmp, i1 %c) {
+block1:
+  store { i8, i8 } { i8 2, i8 3 }, { i8, i8 }* %tmp
+  br i1 %c, label %then, label %out
+then:
+  br label %out
+out:
+  %ptr = getelementptr inbounds { i8, i8 }* %tmp, i64 0, i32 1
+  %val = load i8* %ptr
+  ret i8 %val
+; CHECK-NOT: %val = load i8* %ptr
+; CHECK: ret i8 3
+}