LoadCombine Load Aliasing Fix

[rriddle]

Summary

Removed the alias set tracker and added individual load aliasing checks for each individual chain.

[majnemer]

Please add testcases to the tests directory. Also, please split out each independent change. Each change is easier to analyze in isolation.

[rriddle]

Removed the other patch fixes and added a test to the test suite

[eli.friedman]

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

12

What transform is this testcase checking for? I don't think you can prove any useful aliasing property between %i, %i1, and %str?

[rriddle]

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

12

In the current implementation %1 is being aliased in that store operation which would cause every load chain to try and combine which would prevent the load at %0 from being able to combine with %2, %4, etc.

[eli.friedman]

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

12

I'm not sure I follow... is the transform you're trying to perform something like this?

void f(int* a, int* b) {
  a[0] = b[0];
  a[1] = b[1];
  a[2] = b[2];
  a[3] = b[3];
  // Combine to "memcpy(a, b, 16)"???
}

[rriddle]

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

12

No, the point of transform is to combine each of the individual loads into a single large one. In this specific test, there are multiple GEP + load pairs coming from %i. Each of those will combine down to a single i128 load. It may be easier to see with this output

define i32 @Load_MultiChain(i32* %i) {
  %1 = getelementptr inbounds i32, i32* %i, i64 1
  %2 = bitcast i32* %i to i8*
  %3 = getelementptr i8, i8* %2, i64 0
  %4 = bitcast i8* %3 to i128*
  %.combined = load i128, i128* %4, align 4
  %combine.extract.shift = lshr i128 %.combined, 32
  %combine.extract.trunc1 = trunc i128 %combine.extract.shift to i32
  %5 = load i32, i32* %1, align 4
  %combine.extract.trunc = trunc i128 %.combined to i32
  %6 = load i32, i32* %i, align 4
  %7 = getelementptr inbounds i32, i32* %i, i64 2
  %combine.extract.shift2 = lshr i128 %.combined, 64
  %combine.extract.trunc3 = trunc i128 %combine.extract.shift2 to i32
  %8 = load i32, i32* %7, align 4
  %9 = getelementptr inbounds i32, i32* %i, i64 3
  %combine.extract.shift4 = lshr i128 %.combined, 96
  %combine.extract.trunc5 = trunc i128 %combine.extract.shift4 to i32
  %10 = load i32, i32* %9, align 4
  %11 = getelementptr inbounds i32, i32* %i, i64 4
  %12 = load i32, i32* %11, align 4
  %13 = getelementptr inbounds i32, i32* %i, i64 5
  %14 = load i32, i32* %13, align 4
  %15 = add nsw i32 %combine.extract.trunc, %14
  ret i32 %15
}

In the above every load that originated from i has been combined into a single i128 load. This test is not about transforming into the most optimal result it is testing to make sure that a referenced load chain does not affect all of the other load chains in the basic block. The problem with the current implementation is that it is too conservative when it comes to a write operation that aliases a load. When it reaches such an instruction it tries to combine all of the load chains at that point. This reduces the amount of loads that will be combined if it combines every chain when it reaches a store that references a load.

[rriddle]

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

12

The line at 12 makes more sense when you visualize the load chains at that point. I will visualize the load chains in this format {base_ptr : referenced loads by instruction name }.
So at line 12 the load chains are as follows :

{ %i : %0 } 
{ %str : %1}

The store instruction at line 12 is storing into %i1 which aliases the base ptr %str. This causes every load chain to try and combine, but at this point each only has 1 load; so there is no combine operation performed. The problem with this is that the chain with baseptr %i wasn't referenced by that store operation so why are we trying to combine that chain at this point.

[eli.friedman]

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

12

The problem isn't whether it's optimal... the problem is that the transformation doesn't preserve the semantics of the code. For my C code, -load-combine (plus instcombine to clean up the result) gives:

define void @f(i32* nocapture %a, i32* nocapture readonly %b) local_unnamed_addr #0 {
entry:
  %0 = bitcast i32* %b to i128*
  %.combined = load i128, i128* %0, align 4
  %combine.extract.trunc = trunc i128 %.combined to i32
  store i32 %combine.extract.trunc, i32* %a, align 4, !tbaa !1
  %combine.extract.shift = lshr i128 %.combined, 32
  %combine.extract.trunc1 = trunc i128 %combine.extract.shift to i32
  %arrayidx3 = getelementptr inbounds i32, i32* %a, i64 1
  store i32 %combine.extract.trunc1, i32* %arrayidx3, align 4, !tbaa !1
  %combine.extract.shift2 = lshr i128 %.combined, 64
  %combine.extract.trunc3 = trunc i128 %combine.extract.shift2 to i32
  %arrayidx5 = getelementptr inbounds i32, i32* %a, i64 2
  store i32 %combine.extract.trunc3, i32* %arrayidx5, align 4, !tbaa !1
  %combine.extract.shift4 = lshr i128 %.combined, 96
  %combine.extract.trunc5 = trunc i128 %combine.extract.shift4 to i32
  %arrayidx7 = getelementptr inbounds i32, i32* %a, i64 3
  store i32 %combine.extract.trunc5, i32* %arrayidx7, align 4, !tbaa !1
  ret void
}

This is completely, utterly wrong.

[rriddle]

Fixed argument aliasing and updated test suite

[rriddle]

Updated Memory location creation

[eli.friedman]

/Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Scalar/LoadCombine.cpp

240

Useless comment.

253

Useless comment.

254

Convention is to write this as "if (RefInfo & MRI_Mod)".

256

Isn't this missing the step of sorting Loads->second?

266

What's the justification for the early exit here? Testcase?

270

Is updating the end iterator actually necessary?

274

Useless comment.

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

10

Maybe it would be better to use noalias argument pointers instead of allocas? This testcase is a little weird because you're loading undef.

34

The allocas seem unnecessary here.

[rriddle]

Redundant checks and comments. Updated test arguments.

[rriddle]

Fixed load sorting

[eli.friedman]

/Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Scalar/LoadCombine.cpp

243

Weird indentation.

261

This block of code is very similar to the body of LoadCombine::combineLoads; please refactor.

[rriddle]

Refactor CombineLoads

[eli.friedman]

LGTM. If you don't have commit access, I'll commit this for you.

[majnemer]

/Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Scalar/LoadCombine.cpp

145–146

Please appropriately format this.

254

Please format this appropriately.

[eli.friedman]

I was going over this one more time before committing it... and I realized you don't actually have any test coverage for this change. I'm pretty sure the given testcase passes without your patch.

[rriddle]

Updated tests

[rriddle]

Sorry about that.

/Users/rriddle/Desktop/llvm/llvm/lib/Transforms/Scalar/LoadCombine.cpp

 
 private:
   BuilderTy *Builder;
 
   PointerOffsetPair getPointerOffsetPair(LoadInst &);
   bool combineLoads(DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &);
   bool aggregateLoads(SmallVectorImpl<LoadPOPPair> &);
   bool combineLoads(SmallVectorImpl<LoadPOPPair> &);
+
+  bool
+  checkPointerAlias(Value *,
+                      DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &);
+  bool
+  checkGenericInstAlias(Instruction *,
+                        DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &);
+  const Value *getTopLevelPointer(const Value *);
 };
 }
 
 bool LoadCombine::doInitialization(Function &F) {
   DEBUG(dbgs() << "LoadCombine function: " << F.getName() << "\n");
   C = &F.getContext();
   return true;
 }
bool LoadCombine::combineLoads(
   return Combined;
 }
 
 /// \brief Try to aggregate loads from a sorted list of loads to be combined.
 ///
 /// It is guaranteed that no writes occur between any of the loads. All loads
 /// have the same base pointer. There are at least two loads.
 bool LoadCombine::aggregateLoads(SmallVectorImpl<LoadPOPPair> &Loads) {
   assert(Loads.size() >= 2 && "Insufficient loads!");
   LoadInst *BaseLoad = nullptr;
   SmallVector<LoadPOPPair, 8> AggregateLoads;
   bool Combined = false;
   uint64_t PrevOffset = -1ull;
   uint64_t PrevSize = 0;
   for (auto &L : Loads) {
     if (PrevOffset == -1ull) {
       BaseLoad = L.Load;
       PrevOffset = L.POP.Offset;
Value *V = Builder->CreateExtractInteger(
         L.POP.Offset - Loads[0].POP.Offset, "combine.extract");
     L.Load->replaceAllUsesWith(V);
   }
 
   NumLoadsCombined = NumLoadsCombined + Loads.size();
   return true;
 }
 
+// Handle an alias from a store inst.
+bool LoadCombine::checkPointerAlias(
+    Value *SIPtrOp,
+    DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &LoadMap) {
+  // Get the top level pointer parent.
+  const Value *Parent = getTopLevelPointer(SIPtrOp);
+  if (!Parent)
+    return false;
+
+  // Check the load map for uses.
+  auto Loads = LoadMap.find(Parent);
+  if (Loads == LoadMap.end())
+    return false;
+
+  bool Combined = false;
+
+  // Check for single load.
+  if (Loads->second.size() > 1) {
+    // Combine the loads and clear the maps.
+    if (aggregateLoads(Loads->second))
+      Combined = true;
+  }
+
+  LoadMap.erase(Loads);
+  return Combined;
+}
+
+// Get the top level element pointer.
+const Value *LoadCombine::getTopLevelPointer(const Value *V) {
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(V))
+    return getTopLevelPointer(GEP->getPointerOperand());
+  if (auto *BC = dyn_cast<BitCastInst>(V))
+    return getTopLevelPointer(BC->getOperand(0));
+  if (V->getType()->isPointerTy() == false)
+    return nullptr;
+  return V;
+}
+
+bool LoadCombine::checkGenericInstAlias(
+    Instruction *V,
+    DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &LoadMap) {
+  // If we combined or not.
+  bool Combined = false;
+
+  // Loop over each load and check to see if it is aliased by
+  //   this instruction.
+  auto LoadMapEnd = LoadMap.end();
+  for (auto Loads = LoadMap.begin(); Loads != LoadMapEnd;) {
+    // Check the AA results for an alias.
+    // FIXME:We could calculate the size for the memory location instead of
+    // leaving it unknown.
+    auto RefInfo =
+        AA->getModRefInfo(V, MemoryLocation(getTopLevelPointer(Loads->first)));
+
+    // Check the result.
+    if (RefInfo == ModRefInfo::MRI_Mod || RefInfo == ModRefInfo::MRI_ModRef) {
+      // Check the load count and try to aggregate.
+      if (Loads->second.size() > 1 && aggregateLoads(Loads->second))
+        Combined = true;
+
+      // Get the current iterator.
+      auto CurLoads = Loads++;
+
+      // Remove the loads.
+      LoadMap.erase(CurLoads);
+
+      // Update the end iterator and continue.
+      LoadMapEnd = LoadMap.end();
+      continue;
+    }
+
+    // Update the iterator.
+    ++Loads;
+  }
+  return Combined;
+}
+
 bool LoadCombine::runOnBasicBlock(BasicBlock &BB) {
   if (skipBasicBlock(BB))
     return false;
 
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   IRBuilder<TargetFolder> TheBuilder(
       BB.getContext(), TargetFolder(BB.getModule()->getDataLayout()));
   Builder = &TheBuilder;
 
   DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> LoadMap;
-  AliasSetTracker AST(*AA);
 
   bool Combined = false;
   unsigned Index = 0;
   for (auto &I : BB) {
-    if (I.mayThrow() || (I.mayWriteToMemory() && AST.containsUnknown(&I))) {
+    // If this instruction may throw then we need to combine the loadmap now.
+    if (I.mayThrow()) {
       if (combineLoads(LoadMap))
         Combined = true;
       LoadMap.clear();
-      AST.clear();
+      continue;
+    }
+    // Check if the instruction might write to memory.
+    if (I.mayWriteToMemory()) {
+      // FIXME:Could add specializations for the other simple mayWrite ops.
+      // Check to see if this is a store instance. Provide a special check for
+      // store instances because they are the most common and can be handled
+      // quickly.
+      if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
+        // Check to see if we are using a pointer operand that is aliasing our
+        //  loadmap.
+        if (checkPointerAlias(SI->getPointerOperand(), LoadMap))
+          Combined = true;
+        continue;
+      }
+      // Check for an alias from generic analysis.
+      if (checkGenericInstAlias(&I, LoadMap))
+        Combined = true;
       continue;
     }
     LoadInst *LI = dyn_cast<LoadInst>(&I);
     if (!LI)
       continue;
     ++NumLoadsAnalyzed;
     if (!LI->isSimple() || !LI->getType()->isIntegerTy())
       continue;
     auto POP = getPointerOffsetPair(*LI);
     if (!POP.Pointer)
       continue;
     LoadMap[POP.Pointer].push_back(LoadPOPPair(LI, POP, Index++));
-    AST.add(LI);
   }
   if (combineLoads(LoadMap))
     Combined = true;
   return Combined;
 }
 
 char LoadCombine::ID = 0;
 
 BasicBlockPass *llvm::createLoadCombinePass() {
   return new LoadCombine();
 }
 
 INITIALIZE_PASS_BEGIN(LoadCombine, "load-combine", LDCOMBINE_NAME, false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_END(LoadCombine, "load-combine", LDCOMBINE_NAME, false, false)
+INITIALIZE_PASS_END(LoadCombine, "load-combine", LDCOMBINE_NAME, false, false)
 No newline at end of file

/Users/rriddle/Desktop/llvm/llvm/test/Transforms/LoadCombine/load-combine-alias.ll

+; RUN: opt -basicaa -load-combine -instcombine -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+%struct.Str = type { i32 }
+
+define i32 @Load_i128(i32* %i, %struct.Str** %str) {
+entry:
+  %0 = load i32, i32* %i, align 4
+  %1 = load %struct.Str*, %struct.Str** %str, align 8
+  %i1 = getelementptr inbounds %struct.Str, %struct.Str* %1, i64 0, i32 0
+  store i32 %0, i32* %i1, align 4
+  %add.ptr = getelementptr inbounds i32, i32* %i, i64 1
+  %2 = load i32, i32* %add.ptr, align 4
+  %arrayidx = getelementptr inbounds %struct.Str*, %struct.Str** %str, i64 1
+  %3 = load %struct.Str*, %struct.Str** %arrayidx, align 8
+  %i2 = getelementptr inbounds %struct.Str, %struct.Str* %3, i64 0, i32 0
+  store i32 %2, i32* %i2, align 4
+  %add.ptr3 = getelementptr inbounds i32, i32* %i, i64 2
+  %4 = load i32, i32* %add.ptr3, align 4
+  %arrayidx4 = getelementptr inbounds %struct.Str*, %struct.Str** %str, i64 2
+  %5 = load %struct.Str*, %struct.Str** %arrayidx4, align 8
+  %i5 = getelementptr inbounds %struct.Str, %struct.Str* %5, i64 0, i32 0
+  store i32 %4, i32* %i5, align 4
+  %add.ptr6 = getelementptr inbounds i32, i32* %i, i64 3
+  %6 = load i32, i32* %add.ptr6, align 4
+  ret i32 %6
+; CHECK-LABEL: @Load_i128(
+; CHECK: load i128, i128* %{{.*}}, align 4
+; CHECK-NOT: load i32
+}
+