Remove unnecessary variable indexing into single-element arrays

[hfinkel]

Summary

This patch is intended to address PR22629. To copy from the bug report:

[from the bug report]

Consider this code:

int f(int x) {
  int a[] = {12};
  return a[x];
}

GCC knows to optimize this to

movl     $12, %eax
ret

The code generated by recent Clang at -O3 is:

movslq   %edi, %rax
movl     .L_ZZ1fiE1a(,%rax,4), %eax
retq

.L_ZZ1fiE1a:
  .long    12                      # 0xc

[end from the bug report]

This definitely seems worth fixing. I've also seen this kind of code before (as the base case of generic vector wrapper templates with one element).

The general idea is to look at the GEP feeding a load or a store, which has some variable as its first non-zero index, and determine if that index must be zero (or else an out-of-bounds access would occur). We can do this for allocas and globals with constant initializers where we know the maximum size of the underlying object. When we find such a GEP, we create a new one for the memory access with that first variable index replaced with a constant zero.

Even if we can't eliminate the memory access (and sometimes we can't), it is still useful because it removes unnecessary indexing calculations.

[chandlerc]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

480

Why bother? We strip when popping.

509–510

We don't return true here though, we keep searching. I would state this inverted. "If we find an object that isn't less then MaxSize, we're done, bail." or some such.

520

What if this multiply wraps? I know, I know, it won't but it could in theory. I would write this in some way that no one has to think about that. Maybe just use the APInt we get from the array size?

541–550

Merge the comment blocks? Maybe make them doxygen?

I think it would be nice to generalize this to fold *any* GEP index which would trigger UB if > zero to zero. Maybe just leave a FIXME if doing this is hard? You could maybe put it better down below to not bail at the first non-zero constant index, but to keep going to the first non-constant index.

This is only sound for inbounds GEPs, no? I would probably restrict it to them, see below.

554

What GEP has fewer than 2 operands but passes the verifier?

588–591

You don't need to do this. If the GEP is inbounds, than all intermediate pointer values must be inbounds, so you can skip checking the tail once you have observed badness. However, see my comment below.

Also, the implementation checks for non-negative numbers, not positive numbers.

665–667

Gah. Almost. But not quite.

We have to be able to form one-past-the-end of the object. So if all the subsequent pointers are 0, the one that strides the object could be 1 instead of 0.

I think we need to look for a *positive* tail (not just non-negative) of the GEP, or we need to look at the users and fold if they would be UB for a one-past-the-end GEP. Essentially, as long as we're post-dominated or only used by a load or store, we're golden.

850–854

Fold this into the helper so that it returns the rewritten GEP?

856

As long as you use the instruction combiner's IR builder, this isn't necessary.

[hfinkel]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

480

Good point.

509–510

Ack. Code is new and already an out-of-sync comment ;)

520

Will do.

541–550

Merge the comment blocks? Maybe make them doxygen?

Merged.

I think it would be nice to generalize this to fold *any* GEP index which would trigger UB if > zero to zero. Maybe just leave a FIXME if doing this is hard? You could maybe put it better down below to not bail at the first non-zero constant index, but to keep going to the first non-constant index.

I'll add a FIXME (for both). I need to think about how to do that. For the second point, yes, although we'd also need to keep track of the offsets those indices implied from the start of the object.

This is only sound for inbounds GEPs, no? I would probably restrict it to them, see below.

Ah, yes, if there are other indices then, even if positive, they could wrap.

554

Good question. But SimplifyGEPInst in lib/Analysis/InstructionSimplify.cpp has:

// getelementptr P -> P.
if (Ops.size() == 1)
  return Ops[0];

So, to be safe...

588–591

You don't need to do this. If the GEP is inbounds, than all intermediate pointer values must be inbounds, so you can skip checking the tail once you have observed badness. However, see my comment below.

Right, but one past the end still works, and then we could use a negative offset of some contained array to get back inside the object.

Also, the implementation checks for non-negative numbers, not positive numbers.

Indeed; Positive -> NonNegative

665–667

No, I think this is fine. We do need to be able to form one-past-the-end, but we don't need to load from it. Here I know we're loading from it, so it can't be the one-past-the-end pointer.

This is why I clone the GEP and then change it, so only the load or store gets the rewritten GEP, not any other users of the original pointer.

850–854

Sure.

856

Right, but I'm not.

[hfinkel]

Updates in response to Chandler's review.

[chandlerc]

Generally looks fine to commit whenever. Mostly small bits below.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

474

Add a FIXME to hoist this into Analysis or somewhere it can be re-used? We should make it widely available. This is a great pattern to detect.

592–595

Maybe too clever, but what do you think about bailing the first time you see a positive index as well since you're checking for inbounds? You could make the predicate "canBacktrackFromPastEnd" or some such. As soon as you see a potentially negative index return true, as soon as you see a definitely positive index, return false, if you exhaust the indices return false.

596

nit: no need for explicit return type. You can make it more explicit this is a predicate with an 'is' or can' name prefix...

665–667

Totally missed that you were carefully only transforming a load or store's GEP. Yea, we're on the same page now.

856

Could you? I find that pattern cleaner. We pass IR builders into helper functions regularly.

[hfinkel]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

474

Sure.

592–595

I'm not sure that works. Even after a positive index, we could have a "larger" negative index, and we could still keep everthing inbounds.

596

Sure.

856

Could? Yes. But I'm not sure that's better (if I use the builder interface, I still need to worry about subsequently copying over the inbounds flag -- but only if the builder did not fold the GEP to something else anyway, in which case I need to be careful that it is not folded to some other GEP that used to be related to the original GEP's first operand, etc.).

[hfinkel]

r229959, thanks!

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (auto *BC = dyn_cast<BitCastInst>(LI.user_back())) {
       return &LI;
     }
 
   // FIXME: We should also canonicalize loads of vectors when their elements are
   // cast to other types.
   return nullptr;
 }
 
+// If we can determine that all possible objects pointed to by the provided
+// pointer value are, not only dereferenceable, but also definitively less than
+// or equal to the provided maximum size, then return true. Otherwise, return
+// false (constant global values and allocas fall into this category).
+static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize,
+                                     const DataLayout *DL) {
+  SmallPtrSet<Value *, 4> Visited;
+  SmallVector<Value *, 4> Worklist(1, V);
+
+  do {
+    Value *P = Worklist.pop_back_val();
+    P = P->stripPointerCasts();
+
+    if (!Visited.insert(P).second)
+      continue;
+
+    if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
+      Worklist.push_back(SI->getTrueValue());
+      Worklist.push_back(SI->getFalseValue());
+      continue;
+    }
+
+    if (PHINode *PN = dyn_cast<PHINode>(P)) {
+      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+        Worklist.push_back(PN->getIncomingValue(i));
+      continue;
+    }
+
+    if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) {
+      if (GA->mayBeOverridden())
+        return false;
+      Worklist.push_back(GA->getAliasee());
+      continue;
+    }
+
+    // If we know how big this object is, and it is less than MaxSize, continue
+    // searching. Otherwise, return false.
+    if (AllocaInst *AI = dyn_cast<AllocaInst>(P)) {
+      if (!AI->getAllocatedType()->isSized())
+        return false;
+
+      ConstantInt *CS = dyn_cast<ConstantInt>(AI->getArraySize());
+      if (!CS)
+        return false;
+
+      uint64_t TypeSize = DL->getTypeAllocSize(AI->getAllocatedType());
+      // Make sure that, even if the multiplication below would wrap as an
+      // uint64_t, we still do the right thing.
+      if ((CS->getValue().zextOrSelf(128)*APInt(128, TypeSize)).ugt(MaxSize))
+        return false;
+      continue;
+    }
+
+    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
+      if (!GV->hasDefinitiveInitializer() || !GV->isConstant())
+        return false;
+
+      uint64_t InitSize = DL->getTypeAllocSize(GV->getType()->getElementType());
+      if (InitSize > MaxSize)
+        return false;
+      continue;
+    }
+
+    return false;
+  } while (!Worklist.empty());
+
+  return true;
+}
+
+// If we're indexing into an object of a known size, and the outer index is
+// not a constant, but having any value but zero would lead to undefined
+// behavior, replace it with zero.
+//
+// For example, if we have:
+// @f.a = private unnamed_addr constant [1 x i32] [i32 12], align 4
+// ...
+// %arrayidx = getelementptr inbounds [1 x i32]* @f.a, i64 0, i64 %x
+// ... = load i32* %arrayidx, align 4
+// Then we know that we can replace %x in the GEP with i64 0.
+//
+// FIXME: We could fold any GEP index to zero that would cause UB if it were
+// not zero. Currently, we only handle the first such index. Also, we could
+// also search through non-zero constant indices if we kept track of the
+// offsets those indices implied.
+static bool canReplaceGEPIdxWithZero(InstCombiner &IC, GetElementPtrInst *GEPI,
+                                     Instruction *MemI, unsigned &Idx) {
+  const DataLayout *DL = IC.getDataLayout();
+  if (GEPI->getNumOperands() < 2 || !DL)
+    return false;
+
+  // Find the first non-zero index of a GEP. If all indices are zero, return
+  // one past the last index.
+  auto FirstNZIdx = [](const GetElementPtrInst *GEPI) {
+    unsigned I = 1;
+    for (unsigned IE = GEPI->getNumOperands(); I != IE; ++I) {
+      Value *V = GEPI->getOperand(I);
+      if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
+        if (CI->isZero())
+          continue;
+
+      break;
+    }
+
+    return I;
+  };
+
+  // Skip through initial 'zero' indices, and find the corresponding pointer
+  // type. See if the next index is not a constant.
+  Idx = FirstNZIdx(GEPI);
+  if (Idx == GEPI->getNumOperands())
+    return false;
+  if (isa<Constant>(GEPI->getOperand(Idx)))
+    return false;
+
+  SmallVector<Value *, 4> Ops(GEPI->idx_begin(), GEPI->idx_begin() + Idx);
+  Type *AllocTy =
+    GetElementPtrInst::getIndexedType(GEPI->getOperand(0)->getType(), Ops);
+  if (!AllocTy || !AllocTy->isSized())
+    return false;
+  uint64_t TyAllocSize = DL->getTypeAllocSize(AllocTy);
+
+  // If there are more indices after the one we might replace with a zero, make
+  // sure they're all non-negative. If any of them are negative, the overall
+  // address being computed might be before the base address determined by the
+  // first non-zero index.
+  auto AllNonNegative = [&]() -> bool {
+    for (unsigned i = Idx+1, e = GEPI->getNumOperands(); i != e; ++i) {
+      bool KnownNonNegative, KnownNegative;
+      IC.ComputeSignBit(GEPI->getOperand(i), KnownNonNegative,
+                        KnownNegative, 0, MemI);
+      if (KnownNonNegative)
+        continue;
+      return false;
+    }
+
+    return true;
+  };
+
+  // FIXME: If the GEP is not inbounds, and there are extra indices after the
+  // one we'll replace, those could cause the address computation to wrap
+  // (rendering the AllNonNegative() check below insufficient). We can do
+  // better, ignoring zero indicies (and other indicies we can prove small
+  // enough not to wrap).
+  if (Idx+1 != GEPI->getNumOperands() && !GEPI->isInBounds())
+    return false;
+
+  // Note that isObjectSizeLessThanOrEq will return true only if the pointer is
+  // also known to be dereferenceable.
+  return isObjectSizeLessThanOrEq(GEPI->getOperand(0), TyAllocSize, DL) &&
+         AllNonNegative();
+}
+
+// If we're indexing into an object with a variable index for the memory
+// access, but the object has only one element, we can assume that the index
+// will always be zero. If we replace the GEP, return it.
+template <typename T>
+static Instruction *replaceGEPIdxWithZero(InstCombiner &IC, Value *Ptr,
+                                          T &MemI) {
+  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) {
+    unsigned Idx;
+    if (canReplaceGEPIdxWithZero(IC, GEPI, &MemI, Idx)) {
+      Instruction *NewGEPI = GEPI->clone();
+      NewGEPI->setOperand(Idx,
+        ConstantInt::get(GEPI->getOperand(Idx)->getType(), 0));
+      NewGEPI->insertBefore(GEPI);
+      MemI.setOperand(MemI.getPointerOperandIndex(), NewGEPI);
+      return NewGEPI;
+    }
+  }
+
+  return nullptr;
+}
+
 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
   Value *Op = LI.getOperand(0);
 
   // Try to canonicalize the loaded type.
   if (Instruction *Res = combineLoadToOperationType(*this, LI))
     return Res;
 
   // Attempt to improve the alignment.
   if (DL) {
     unsigned KnownAlign = getOrEnforceKnownAlignment(
         Op, DL->getPrefTypeAlignment(LI.getType()), DL, AC, &LI, DT);
     unsigned LoadAlign = LI.getAlignment();
     unsigned EffectiveLoadAlign = LoadAlign != 0 ? LoadAlign :
       DL->getABITypeAlignment(LI.getType());
 
     if (KnownAlign > EffectiveLoadAlign)
       LI.setAlignment(KnownAlign);
     else if (LoadAlign == 0)
       LI.setAlignment(EffectiveLoadAlign);
   }
 
+  // Replace GEP indices if possible.
+  if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Op, LI)) {
+      Worklist.Add(NewGEPI);
+      return &LI;
+  }
+
   // None of the following transforms are legal for volatile/atomic loads.
   // FIXME: Some of it is okay for atomic loads; needs refactoring.
   if (!LI.isSimple()) return nullptr;
 
   // Do really simple store-to-load forwarding and load CSE, to catch cases
   // where there are several consecutive memory accesses to the same location,
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI = &LI;
unsigned EffectiveStoreAlign = StoreAlign != 0 ? StoreAlign :
       DL->getABITypeAlignment(Val->getType());
 
     if (KnownAlign > EffectiveStoreAlign)
       SI.setAlignment(KnownAlign);
     else if (StoreAlign == 0)
       SI.setAlignment(EffectiveStoreAlign);
   }
 
+  // Replace GEP indices if possible.
+  if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) {
+      Worklist.Add(NewGEPI);
+      return &SI;
+  }
+
   // Don't hack volatile/atomic stores.
   // FIXME: Some bits are legal for atomic stores; needs refactoring.
   if (!SI.isSimple()) return nullptr;
 
   // If the RHS is an alloca with a single use, zapify the store, making the
   // alloca dead.
   if (Ptr->hasOneUse()) {
     if (isa<AllocaInst>(Ptr))
       return EraseInstFromFunction(SI);
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
       if (isa<AllocaInst>(GEP->getOperand(0))) {
         if (GEP->getOperand(0)->hasOneUse())
           return EraseInstFromFunction(SI);
       }

test/Transforms/InstCombine/load-cmp.ll

 ; P32-NEXT: ret i1
 }
 
 define i1 @test10_struct(i32 %x) {
 ; NODL-LABEL: @test10_struct(
 ; NODL: getelementptr inbounds %Foo* @GS, i32 %x, i32 0
 
 ; P32-LABEL: @test10_struct(
-; P32: getelementptr inbounds %Foo* @GS, i32 %x, i32 0
+; P32: ret i1 false
   %p = getelementptr inbounds %Foo* @GS, i32 %x, i32 0
   %q = load i32* %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_noinbounds(i32 %x) {
 ; NODL-LABEL: @test10_struct_noinbounds(

 
 ; Test that the GEP indices are converted before we ever get here
 ; Index < ptr size
 define i1 @test10_struct_i16(i16 %x){
 ; NODL-LABEL: @test10_struct_i16(
 ; NODL: getelementptr inbounds %Foo* @GS, i16 %x, i32 0
 
 ; P32-LABEL: @test10_struct_i16(
-; P32: %1 = sext i16 %x to i32
-; P32: getelementptr inbounds %Foo* @GS, i32 %1, i32 0
+; P32: ret i1 false
   %p = getelementptr inbounds %Foo* @GS, i16 %x, i32 0
   %q = load i32* %p
   %r = icmp eq i32 %q, 0
   ret i1 %r
 }
 
 ; Test that the GEP indices are converted before we ever get here
 ; Index > ptr size
 define i1 @test10_struct_i64(i64 %x){
 ; NODL-LABEL: @test10_struct_i64(
 ; NODL: getelementptr inbounds %Foo* @GS, i64 %x, i32 0
 
 ; P32-LABEL: @test10_struct_i64(
-; P32: %1 = trunc i64 %x to i32
-; P32: getelementptr inbounds %Foo* @GS, i32 %1, i32 0
+; P32: ret i1 false
   %p = getelementptr inbounds %Foo* @GS, i64 %x, i32 0
   %q = load i32* %p
   %r = icmp eq i32 %q, 0
   ret i1 %r
 }
 
 define i1 @test10_struct_noinbounds_i16(i16 %x) {
 ; NODL-LABEL: @test10_struct_noinbounds_i16(

test/Transforms/InstCombine/mem-gep-zidx.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-unknown-linux-gnu"
+
+@f.a = private unnamed_addr constant [1 x i32] [i32 12], align 4
+@f.b = private unnamed_addr constant [1 x i32] [i32 55], align 4
+
+define signext i32 @test1(i32 signext %x) #0 {
+entry:
+  %idxprom = sext i32 %x to i64
+  %arrayidx = getelementptr inbounds [1 x i32]* @f.a, i64 0, i64 %idxprom
+  %0 = load i32* %arrayidx, align 4
+  ret i32 %0
+
+; CHECK-LABEL: @test1
+; CHECK: ret i32 12
+}
+
+declare void @foo(i64* %p)
+define void @test2(i32 signext %x, i64 %v) #0 {
+entry:
+  %p = alloca i64
+  %idxprom = sext i32 %x to i64
+  %arrayidx = getelementptr inbounds i64* %p, i64 %idxprom
+  store i64 %v, i64* %arrayidx
+  call void @foo(i64* %p)
+  ret void
+
+; CHECK-LABEL: @test2
+; CHECK: %p = alloca i64
+; CHECK: store i64 %v, i64* %p
+; CHECK: ret void
+}
+
+define signext i32 @test3(i32 signext %x, i1 %y) #0 {
+entry:
+  %idxprom = sext i32 %x to i64
+  %p = select i1 %y, [1 x i32]* @f.a, [1 x i32]* @f.b
+  %arrayidx = getelementptr inbounds [1 x i32]* %p, i64 0, i64 %idxprom
+  %0 = load i32* %arrayidx, align 4
+  ret i32 %0
+
+; CHECK-LABEL: @test3
+; CHECK: getelementptr inbounds [1 x i32]* %p, i64 0, i64 0
+}
+
+attributes #0 = { nounwind readnone }
+