[ConstantHoist] Remove check for notional overindexing

[nikic]

Summary

ConstantHoist currently only hoists GEPs if there is no notional overindexing. However, I don't see in what way overindexing is supposed to be relevant to this transform. I believe the only part it cares about is that the GEP has constant indices (which is already checked by accumulateConstantOffset).

In the attached test case this makes ConstantHoist apply to the GEP with trailing 10 index, which is nominally out of bounds. (The corresponding store may not even be UB, though even if it were there is no reason why this transform should care.)

[efriedma]

There are a few different properties isGEPWithNoNotionalOverIndexing checks for:

1. We have a GEP constant expression.
2. All the operands beyond the first are undef or ConstantInt.
3. All the integer indexes are in bounds.

The replacement checks:

1. We have a GEP constant expression.
2. All the operands beyond the first are ConstantInt.

So basically, this is just removing the third condition.

accumulateConstantOffset already checks that all the operands are ConstantInt, so the second condition is redundant; should be fine to just check isa<GEPOperator>, I think.

If we stop checking for over-indexing, do we need to worry about "inbounds" markings? Before this patch, all the transformed GEPs were effectively inbounds, but with this patch they aren't.

[nikic]

Drop all constant check, leave it to accumulateConstantOffset().

[nikic]

In D117201#3241570, @efriedma wrote:

There are a few different properties isGEPWithNoNotionalOverIndexing checks for:

1. We have a GEP constant expression.
2. All the operands beyond the first are undef or ConstantInt.
3. All the integer indexes are in bounds.

The replacement checks:

1. We have a GEP constant expression.
2. All the operands beyond the first are ConstantInt.

So basically, this is just removing the third condition.

accumulateConstantOffset already checks that all the operands are ConstantInt, so the second condition is redundant; should be fine to just check isa<GEPOperator>, I think.

Right, done.

If we stop checking for over-indexing, do we need to worry about "inbounds" markings? Before this patch, all the transformed GEPs were effectively inbounds, but with this patch they aren't.

I don't think so. We're just hoisting address arithmetic here, it should not matter whether it is inbounds or not.

[efriedma]

In D117201#3243101, @nikic wrote:

If we stop checking for over-indexing, do we need to worry about "inbounds" markings? Before this patch, all the transformed GEPs were effectively inbounds, but with this patch they aren't.

I don't think so. We're just hoisting address arithmetic here, it should not matter whether it is inbounds or not.

I'm not saying the transformation inherently cares about "inbounds".

The case I'm worried about is the case where we choose an "inbounds" GEP as the base, but it's poison because it's out of bounds. We do the transform, then all the other transformed GEPs are poisoned. I think we could solve this by generating a new constant expression for the base that isn't marked "inbounds". Currently, we just reuse the existing constant expression.

[nikic]

Okay, I see what you mean now. I've updated the implementation to perform an explicit inbounds check.

As the code requires a GlobalVariable base pointer, the notional overindexing check did effectively guarantee that it is inbounds, because there would be a bitcast sitting in between otherwise -- of course, this is not true anymore with opaque pointers, as the GEP type is entirely independent of the global type in that case.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/ConstantHoisting.cpp

void ConstantHoistingPass::collectConstantCandidates(
   if (!BaseGV)
     return;
 
   // Get offset from the base GV.
   PointerType *GVPtrTy = cast<PointerType>(BaseGV->getType());
   IntegerType *PtrIntTy = DL->getIntPtrType(*Ctx, GVPtrTy->getAddressSpace());
   APInt Offset(DL->getTypeSizeInBits(PtrIntTy), /*val*/0, /*isSigned*/true);
   auto *GEPO = cast<GEPOperator>(ConstExpr);
+
+  // TODO: If we have a mix of inbounds and non-inbounds GEPs, then basing a
+  // non-inbounds GEP on an inbounds GEP is potentially incorrect. Restrict to
+  // inbounds GEP for now -- alternatively, we could drop inbounds from the
+  // constant expression,
+  if (!GEPO->isInBounds())
+    return;
+
   if (!GEPO->accumulateConstantOffset(*DL, Offset))
     return;
 
   if (!Offset.isIntN(32))
     return;
 
   // A constant GEP expression that has a GlobalVariable as base pointer is
   // usually lowered to a load from constant pool. Such operation is unlikely
if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
       return;
     }
   }
 
   // Visit constant expressions that have constant integers.
   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
     // Handle constant gep expressions.
-    if (ConstHoistGEP && ConstExpr->isGEPWithNoNotionalOverIndexing())
+    if (ConstHoistGEP && isa<GEPOperator>(ConstExpr))
       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
 
     // Only visit constant cast expressions.
     if (!ConstExpr->isCast())
       return;
 
     if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
       // Pretend the constant is directly used by the instruction and ignore
if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
     LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
     updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
     LLVM_DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
     return;
   }
 
   // Visit constant expression.
   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
-    if (ConstExpr->isGEPWithNoNotionalOverIndexing()) {
+    if (isa<GEPOperator>(ConstExpr)) {
       // Operand is a ConstantGEP, replace it.
       updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat);
       return;
     }
 
     // Aside from constant GEPs, only constant cast expressions are collected.
     assert(ConstExpr->isCast() && "ConstExpr should be a cast");
     Instruction *ConstExprInst = ConstExpr->getAsInstruction(

llvm/test/Transforms/ConstantHoisting/ARM/const-hoist-gep-overindexing.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -consthoist -consthoist-gep -S -o - %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv6m-none--musleabi"
+
+%0 = type { [10 x i32], [10 x i16] }
+
+@global = external local_unnamed_addr global %0, align 4
+
+define void @test_inbounds() {
+; CHECK-LABEL: @test_inbounds(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[CONST:%.*]] = bitcast i16* getelementptr inbounds ([[TMP0:%.*]], %0* @global, i32 0, i32 1, i32 0) to i16*
+; CHECK-NEXT:    store i16 undef, i16* [[CONST]], align 2
+; CHECK-NEXT:    [[BASE_BITCAST:%.*]] = bitcast i16* [[CONST]] to i8*
+; CHECK-NEXT:    [[MAT_GEP:%.*]] = getelementptr i8, i8* [[BASE_BITCAST]], i32 2
+; CHECK-NEXT:    [[MAT_BITCAST:%.*]] = bitcast i8* [[MAT_GEP]] to i16*
+; CHECK-NEXT:    store i16 undef, i16* [[MAT_BITCAST]], align 2
+; CHECK-NEXT:    [[BASE_BITCAST1:%.*]] = bitcast i16* [[CONST]] to i8*
+; CHECK-NEXT:    [[MAT_GEP2:%.*]] = getelementptr i8, i8* [[BASE_BITCAST1]], i32 20
+; CHECK-NEXT:    [[MAT_BITCAST3:%.*]] = bitcast i8* [[MAT_GEP2]] to i16*
+; CHECK-NEXT:    store i16 undef, i16* [[MAT_BITCAST3]], align 2
+; CHECK-NEXT:    ret void
+;
+bb:
+  store i16 undef, i16* getelementptr inbounds (%0, %0* @global, i32 0, i32 1, i32 0)
+  store i16 undef, i16* getelementptr inbounds (%0, %0* @global, i32 0, i32 1, i32 1)
+  store i16 undef, i16* getelementptr inbounds (%0, %0* @global, i32 0, i32 1, i32 10)
+  ret void
+}
+
+define dso_local void @test_non_inbounds() {
+; CHECK-LABEL: @test_non_inbounds(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    store i16 undef, i16* getelementptr inbounds ([[TMP0:%.*]], %0* @global, i32 0, i32 1, i32 11), align 2
+; CHECK-NEXT:    store i16 undef, i16* getelementptr ([[TMP0]], %0* @global, i32 0, i32 1, i32 12), align 2
+; CHECK-NEXT:    ret void
+;
+bb:
+  store i16 undef, i16* getelementptr inbounds (%0, %0* @global, i32 0, i32 1, i32 11)
+  store i16 undef, i16* getelementptr (%0, %0* @global, i32 0, i32 1, i32 12)
+  ret void
+}
+