Load Combine : Combine Loads formed from GEPS with negative indexes

[rriddle]

Summary

Changed the underlying offset and comparisons to use int64_t instead of uint64_t

[majnemer]

I would avoid using an in-band value as a sentinel, there can be unintended consequences. Consider what happens when the GEP index is 9223372036854775807.

Instead, I'd use a separate bool indicating that PrevOffset holds a good value or make PrevOffset an Optional.

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

141 ↗

(On Diff #61181)

While I know of no platform that LLVM supports where LLONG_MAX != INT64_MAX, we would still prefer INT64_MAX.

142 ↗

(On Diff #61181)

Hmm, any reason why PrevSize had to become an int64_t ?

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

1 ↗

(On Diff #61181)

Please don't run instcombine, we try to minimize the number of passes involved in each test.

[rriddle]

Fixed the size type change mistake. Changed the iteration variable to be a separate value.

[majnemer]

LGTM

[majnemer]

Hi River,

Do you need someone to commit this for you?

[rriddle]

Hey David, This is my first patch so Im not too sure about the process for committing. Accordingly, Im fairly certain that I don't have commit access.
Thanks River

llvm/trunk/lib/Transforms/Scalar/LoadCombine.cpp

 STATISTIC(NumLoadsAnalyzed, "Number of loads analyzed for combining");
 STATISTIC(NumLoadsCombined, "Number of loads combined");
 
 #define LDCOMBINE_NAME "Combine Adjacent Loads"
 
 namespace {
 struct PointerOffsetPair {
   Value *Pointer;
-  uint64_t Offset;
+  int64_t Offset;
 };
 
 struct LoadPOPPair {
   LoadPOPPair() = default;
   LoadPOPPair(LoadInst *L, PointerOffsetPair P, unsigned O)
       : Load(L), POP(P), InsertOrder(O) {}
   LoadInst *Load;
   PointerOffsetPair POP;
PointerOffsetPair LoadCombine::getPointerOffsetPair(LoadInst &LI) {
   POP.Pointer = LI.getPointerOperand();
   POP.Offset = 0;
   while (isa<BitCastInst>(POP.Pointer) || isa<GetElementPtrInst>(POP.Pointer)) {
     if (auto *GEP = dyn_cast<GetElementPtrInst>(POP.Pointer)) {
       auto &DL = LI.getModule()->getDataLayout();
       unsigned BitWidth = DL.getPointerTypeSizeInBits(GEP->getType());
       APInt Offset(BitWidth, 0);
       if (GEP->accumulateConstantOffset(DL, Offset))
-        POP.Offset += Offset.getZExtValue();
+        POP.Offset += Offset.getSExtValue();
       else
         // Can't handle GEPs with variable indices.
         return POP;
       POP.Pointer = GEP->getPointerOperand();
     } else if (auto *BC = dyn_cast<BitCastInst>(POP.Pointer))
       POP.Pointer = BC->getOperand(0);
   }
   return POP;

 ///
 /// 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;
+  bool ValidPrevOffset = false;
+  int64_t PrevOffset = 0;
   uint64_t PrevSize = 0;
   for (auto &L : Loads) {
-    if (PrevOffset == -1ull) {
+    if (ValidPrevOffset == false) {
       BaseLoad = L.Load;
       PrevOffset = L.POP.Offset;
       PrevSize = L.Load->getModule()->getDataLayout().getTypeStoreSize(
           L.Load->getType());
       AggregateLoads.push_back(L);
+      ValidPrevOffset = true;
       continue;
     }
     if (L.Load->getAlignment() > BaseLoad->getAlignment())
       continue;
-    if (L.POP.Offset > PrevOffset + PrevSize) {
+    int64_t PrevEnd = PrevOffset + PrevSize;
+    if (L.POP.Offset > PrevEnd) {
       // No other load will be combinable
       if (combineLoads(AggregateLoads))
         Combined = true;
       AggregateLoads.clear();
-      PrevOffset = -1;
+      ValidPrevOffset = false;
       continue;
     }
-    if (L.POP.Offset != PrevOffset + PrevSize)
+    if (L.POP.Offset != PrevEnd)
       // This load is offset less than the size of the last load.
       // FIXME: We may want to handle this case.
       continue;
     PrevOffset = L.POP.Offset;
     PrevSize = L.Load->getModule()->getDataLayout().getTypeStoreSize(
         L.Load->getType());
     AggregateLoads.push_back(L);
   }

llvm/trunk/test/Transforms/LoadCombine/load-combine-negativegep.ll

+; RUN: opt -basicaa -load-combine -S < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @Load_NegGep(i32* %i){
+  %1 = getelementptr inbounds i32, i32* %i, i64 -1
+  %2 = load i32, i32* %1, align 4
+  %3 = load i32, i32* %i, align 4
+  %4 = add nsw i32 %3, %2
+  ret i32 %4
+; CHECK-LABEL: @Load_NegGep(
+; CHECK:  %[[load:.*]] = load i64
+; CHECK:  %[[combine_extract_lo:.*]] = trunc i64 %[[load]] to i32
+; CHECK:  %[[combine_extract_shift:.*]] = lshr i64 %[[load]], 32
+; CHECK:  %[[combine_extract_hi:.*]] = trunc i64 %[[combine_extract_shift]] to i32
+; CHECK:  %[[add:.*]] = add nsw i32 %[[combine_extract_hi]], %[[combine_extract_lo]]
+}
+
+