[ConstantFold] Fix defect in constant folding computation for GEP

[javed.absar]

Summary

When the array indexes are all determined by GVN to be constants,
a call is made to constant-folding to optimize/simplify the address
computation.
The constant-folding, however, makes a mistake in that it sometimes reads
back stale Idxs instead of NewIdxs, that it re-computed in previous iteration.
This leads to incorrect addresses coming out of constant-folding to GEP.

A test case is included. The error is only triggered when indexes have particular
patterns that the stale/new index updates interplay matters.

[• dberlin]

Is there a reason to split NewIdx and Idx at all?
I don't see it in this code and context.

That would solve your problem without introducing yet another array.
It also would be a step on fixing the N^2'dness of this function (since it restarts itself on the changed indices, which is silly)

[javed.absar]

Yes makes sense if it can be done without breaking some corner case. I will wait a bit for the original author of this algorithm, who I believe are on the review-list, to comment on why originally two arrays, Idxs and NewIdxs, was thought best to have.
Best Regards
Javed

[javed.absar]

Hi:
Here is a simpler fix for that same defect.

On the point of removing NewIdxs completely, I did give it a try, but then found (a) Idxs is passed as constant reference and so it is not a good idea to modify it; (b) the algorithm is not really N^2 as the indexes are re-computed only once.

Hope this patch with the fix for that specific original problem (stale data reading) is acceptable.
Best Regards
Javed

[• dberlin]

In D30642#695286, @javed.absar wrote:

Hi:
Here is a simpler fix for that same defect.

On the point of removing NewIdxs completely, I did give it a try, but then found (a) Idxs is passed as constant reference and so it is not a good idea to modify it;

Ugh. Unless this code is going to do a thing to them that is bad, that seems silly, but ...
yeah, not gonna make you fix it.

(b) the algorithm is not really N^2 as the indexes are re-computed only once.

Once per GEP in the tree, you mean

// If we did any factoring, start over with the adjusted indices.
if (!NewIdxs.empty()) {
  for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
    if (!NewIdxs[i]) NewIdxs[i] = cast<Constant>(Idxs[i]);
  return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds,
                                        InRangeIndex);

This will call this function, and that call could also adjust and recurse.
all the way up the tree.

So if you constant folded a gep tree like this:

1=GEP 0
2=GEP 1
3=GEP 2
..

Imagine constant folding only fails at the last second for some reason:

calling constant fold on 1 will call it on 0
calling constant fold on 2 will call it on 1 which will call it on 0
calling constant fold on 3 will call it on 2 which will call it on 1 which will call it on 0.

So yes, the function itself is not N^2, but pretty much any normal usage will be.

Hope this patch with the fix for that specific original problem (stale data reading) is acceptable.
Best Regards
Javed

[javed.absar]

Hi Daniel:

Agree with you that the ConstantFolding algorithm seems to need improvement. I will try to improve it and send you a new patch.
But I also think this defect fix need not be gated on it.

Best Regards
Javed

[• dberlin]

In D30642#695419, @javed.absar wrote:

Hi Daniel:

Agree with you that the ConstantFolding algorithm seems to need improvement. I will try to improve it and send you a new patch.
But I also think this defect fix need not be gated on it.

Sorry, thought i already accepted this.
I was just responding to your comment that it only does things once :)

lib/IR/ConstantFold.cpp

if (CE->isCast() && Idxs.size() > 1 && Idx0->isNullValue()) {
       }
     }
   }
 
   // Check to see if any array indices are not within the corresponding
   // notional array or vector bounds. If so, try to determine if they can be
   // factored out into preceding dimensions.
   SmallVector<Constant *, 8> NewIdxs;
+  SmallVector<bool,8> IdxsChanged(Idxs.size(),false);
   Type *Ty = PointeeTy;
   Type *Prev = C->getType();
   bool Unknown = !isa<ConstantInt>(Idxs[0]);
   for (unsigned i = 1, e = Idxs.size(); i != e;
        Prev = Ty, Ty = cast<CompositeType>(Ty)->getTypeAtIndex(Idxs[i]), ++i) {
     auto *CI = dyn_cast<ConstantInt>(Idxs[i]);
     if (!CI) {
       // We don't know if it's in range or not.
for (unsigned i = 1, e = Idxs.size(); i != e;
     // It's out of range, but we can factor it into the prior
     // dimension.
     NewIdxs.resize(Idxs.size());
     // Determine the number of elements in our sequential type.
     uint64_t NumElements = STy->getArrayNumElements();
 
     ConstantInt *Factor = ConstantInt::get(CI->getType(), NumElements);
     NewIdxs[i] = ConstantExpr::getSRem(CI, Factor);
+    IdxsChanged[i] = true;
 
-    Constant *PrevIdx = cast<Constant>(Idxs[i - 1]);
+    Constant *PrevIdx = (IdxsChanged[i-1]) ? NewIdxs[i-1] :
+                           cast<Constant>(Idxs[i - 1]);
     Constant *Div = ConstantExpr::getSDiv(CI, Factor);
 
     unsigned CommonExtendedWidth =
         std::max(PrevIdx->getType()->getIntegerBitWidth(),
                  Div->getType()->getIntegerBitWidth());
     CommonExtendedWidth = std::max(CommonExtendedWidth, 64U);
 
     // Before adding, extend both operands to i64 to avoid
     // overflow trouble.
     if (!PrevIdx->getType()->isIntegerTy(CommonExtendedWidth))
       PrevIdx = ConstantExpr::getSExt(
           PrevIdx, Type::getIntNTy(Div->getContext(), CommonExtendedWidth));
     if (!Div->getType()->isIntegerTy(CommonExtendedWidth))
       Div = ConstantExpr::getSExt(
           Div, Type::getIntNTy(Div->getContext(), CommonExtendedWidth));
 
     NewIdxs[i - 1] = ConstantExpr::getAdd(PrevIdx, Div);
+    IdxsChanged[i-1] = true;
   }
 
   // If we did any factoring, start over with the adjusted indices.
   if (!NewIdxs.empty()) {
     for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
       if (!NewIdxs[i]) NewIdxs[i] = cast<Constant>(Idxs[i]);
     return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds,
                                           InRangeIndex);

test/Analysis/ConstantFolding/gep-constanfolding-error.ll

+; RUN: opt -gvn -S -o - %s | FileCheck %s
+; RUN: opt -newgvn -S -o - %s | FileCheck %s
+; Test that the constantfolding getelementptr computation results in
+; j[5][4][1] (j+239)
+; and not [1][4][4][1] (#449) which is an incorrect out-of-range error
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7-none-eabi"
+
+@f = local_unnamed_addr global i32 2, align 4
+@t6 = local_unnamed_addr global i32 1, align 4
+@j = local_unnamed_addr global [6 x [6 x [7 x i8]]] [[6 x [7 x i8]] [[7 x i8] c"\06\00\00\00\00\00\00", [7 x i8] zeroinitializer, [7 x i8] zeroinitializer, [7 x i8] zeroinitializer, [7 x i8] zeroinitializer, [7 x i8] zeroinitializer], [6 x [7 x i8]] zeroinitializer, [6 x [7 x i8]] zeroinitializer, [6 x [7 x i8]] zeroinitializer, [6 x [7 x i8]] zeroinitializer, [6 x [7 x i8]] zeroinitializer], align 1
+@p = internal global i64 0, align 8
+@y = local_unnamed_addr global i64* @p, align 4
+@b = internal unnamed_addr global i32 0, align 4
+@h = common local_unnamed_addr global i16 0, align 2
+@a = common local_unnamed_addr global i32 0, align 4
+@k = common local_unnamed_addr global i32 0, align 4
+@t11 = common local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: nounwind
+define i32 @main() local_unnamed_addr {
+entry:
+  %0 = load i32, i32* @t6, align 4
+  %inc = add nsw i32 %0, 1
+  store i32 %inc, i32* @t6, align 4
+  store i16 4, i16* @h, align 2
+  %1 = load i32, i32* @a, align 4
+  %conv = trunc i32 %1 to i8
+  store i32 1, i32* @f, align 4
+  %2 = load i64, i64* @p, align 8
+  %cmp4 = icmp slt i64 %2, 2
+  %conv6 = zext i1 %cmp4 to i8
+  %3 = load i16, i16* @h, align 2
+  %conv7 = sext i16 %3 to i32
+  %add = add nsw i32 %conv7, 1
+  %f.promoted = load i32, i32* @f, align 4
+  %4 = mul i32 %conv7, 7
+  %5 = add i32 %4, 5
+  %6 = sub i32 -1, %f.promoted
+  %7 = icmp sgt i32 %6, -2
+  %smax = select i1 %7, i32 %6, i32 -2
+  %8 = sub i32 6, %smax
+  %scevgep = getelementptr [6 x [6 x [7 x i8]]], [6 x [6 x [7 x i8]]]* @j, i32 0, i32 0, i32 %5, i32 %8
+  %9 = add i32 %f.promoted, %smax
+  %10 = add i32 %9, 2
+  call void @llvm.memset.p0i8.i32(i8* %scevgep, i8 %conv6, i32 %10, i32 1, i1 false)
+; CHECK:  call void @llvm.memset.p0i8.i32(i8* getelementptr inbounds ([6 x [6 x [7 x i8]]], [6 x [6 x [7 x i8]]]* @j, i32 0, i64 5, i64 4, i32 1), i8 %conv6, i32 1, i32 1, i1 false)
+; CHECK-NOT: call void @llvm.memset.p0i8.i32(i8* getelementptr ([6 x [6 x [7 x i8]]], [6 x [6 x [7 x i8]]]* @j, i64 1, i64 4, i64 4, i32 1)
+  ret i32 0
+}
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i32, i1)