[ConstantFolding] fold integers whose bitwidth is greater than 64.

[khei4]

Summary

This patch tries to fold integers whose bit width is greater than 64.
motivated by https://reviews.llvm.org/D146622 landing failure

Depends on https://reviews.llvm.org/D150515

[nikic]

(how can I confirm the correctness of not multiplies of 8 integers?)

We currently don't specify the precise memory contents for non-byte-sized integers, so it's not really possible to fold such cases now. (We only specify what happens if you store an i4 and load i4, but for example not what happens if you store i4 and then load i8.)

llvm/lib/Analysis/ConstantFolding.cpp

435

This is going to assert if the value inside the i128 is larger than 64-bit. It's necessary to work on the APInt representation instead.

[khei4]

@nikic Thank you for your review!

We currently don't specify the precise memory contents for non-byte-sized integers, so it's not really possible to fold such cases now. (We only specify what happens if you store an i4 and load i4, but for example not what happens if you store i4 and then load i8.)

So, does it mean loading by different bit-width is undefined behavior? It sounds like we can fold it by the value by assuming a non-byte-size integer is allocated with a bigger byte-sized type! (but does it break something?

[khei4]

apply feedback and fold all integers tentatively.
(at least will be rebased after https://reviews.llvm.org/D146622 safely landed

llvm/lib/Analysis/ConstantFolding.cpp

435

Thank you!! I was careless!

[RKSimon]

llvm/lib/Analysis/ConstantFolding.cpp

433

I'd be surprised if non-byte sized widths work at all - moving to APInt from uint64_t will allow you to remove the 64 bit limit however, so maybe just work on that first?

[RKSimon]

llvm/lib/Analysis/ConstantFolding.cpp

435

const APInt &Val

443

Val.extractBits(8, n * 8).getZextValue()

[khei4]

@RKSimon Thank you for the review!

I'd be surprised if non-byte sized widths work at all - moving to APInt from uint64_t will allow you to remove the 64 bit limit however, so maybe just work on that first?

Yeah, I now find current byte-based folding is broken for well-defined loading for non-byte-size integers... I'll focus on only the removal of a 64-bit limit for this revision:)

Edit: sign bit handling needed

[khei4]

llvm/lib/Analysis/ConstantFolding.cpp

443

Thank you! This causes test failure caused by allocsize of vector size mismatching! It will be fixed in https://reviews.llvm.org/D150515

[khei4]

focus on byte-sized integers.
currently, some tests failed. This will be handled at https://reviews.llvm.org/D150515#inline-1454185

[khei4]

remove obsolete test changes

[nikic]

llvm/lib/Analysis/ConstantFolding.cpp

432–433

435

llvm/test/Transforms/InstCombine/constant-fold.ll

2 ↗

(On Diff #522049)

This test can be moved to InstSimplify (shouldn't need InstCombine). There probably already is some load.ll or so file there.

[khei4]

apply feedbacks

[khei4]

@nikic Thank you for the good catches!

llvm/lib/Analysis/ConstantFolding.cpp

435

Thanks!

llvm/test/Transforms/InstCombine/constant-fold.ll

2 ↗

(On Diff #522049)

Thanks! and about following case

define i125 @load-125bit(){
; CHECK-LABEL: define i125 @load-125bit() {
; CHECK-NEXT:    ret i125 1125899906842625
;
  %1 = load i125, ptr @global125, align 4
  ret i125 %1
}

InstSimplify somehow fold this on the current released opt https://llvm.godbolt.org/z/o5cz6ds99

so by changing the condition slightly, load 128-bit integer as 43-bit integer(I am not so sure why this happens.

define i43 @load-43bit(){
; CHECK-LABEL: @load-43bit(
; CHECK-NEXT:    [[TMP1:%.*]] = load i43, ptr @global128, align 4
; CHECK-NEXT:    ret i43 [[TMP1]]
;
  %1 = load i43, ptr @global128, align 4
  ret i43 %1
}

[nikic]

It looks like the @load-43bit test case fails in pre-merge checks. Note that for the non-byte-sized check the important part is that the integer in the global has non-byte-size, not the type used to load from it.

[khei4]

@nikic Thanks! Sorry, for that failure, it seems I just uploaded a broken test.

Further checking find that current behavior seems to properly fold the non-byte-sized integer by
https://github.com/llvm/llvm-project/blob/7c1fb94150449db33f2df4567207387710e515b9/llvm/lib/Analysis/ConstantFolding.cpp#L348-L353

if it's loaded with the same type. So I decided to remove the TODO comment and non-byte-integers tests!

BTW, if non-byte-integers loading by a different size integer type is undefined, language reference seems to say nothing about it, at least integer and load sections. Is this a room to add a note? or I missed some related sections?

[khei4]

remove non-byte-integer related todo and tests

[nikic]

LGTM

[ConstantFolding] fold integers whose bitwidth is greater than 63.

This should say 64.

In D150422#4344395, @khei4 wrote:

BTW, if non-byte-integers loading by a different size integer type is undefined, language reference seems to say nothing about it, at least integer and load sections. Is this a room to add a note? or I missed some related sections?

This is specified in https://llvm.org/docs/LangRef.html#id209 and https://llvm.org/docs/LangRef.html#id214. But current semantics are not really clear/inconsistent, see also discussion on D123991.

[khei4]

@nikic Thank you! I'll fix the descriptions!

This is specified in https://llvm.org/docs/LangRef.html#id209 and https://llvm.org/docs/LangRef.html#id214. But current semantics are not really clear/inconsistent, see also discussion on D123991.

Ah, I missed the load semantics section... Thank you for sharing!

llvm/lib/Analysis/ConstantFolding.cpp

assert(ByteOffset <= DL.getTypeAllocSize(C->getType()) &&
          "Out of range access");
 
   // If this element is zero or undefined, we can just return since *CurPtr is
   // zero initialized.
   if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C))
     return true;
 
   if (auto *CI = dyn_cast<ConstantInt>(C)) {
-    if (CI->getBitWidth() > 64 ||
-        (CI->getBitWidth() & 7) != 0)
+    // TODO: Support non-byte-sized integers.
+    if ((CI->getBitWidth() & 7) != 0)
       return false;
-
-    uint64_t Val = CI->getZExtValue();
+    const APInt &Val = CI->getValue();
     unsigned IntBytes = unsigned(CI->getBitWidth()/8);
 
     for (unsigned i = 0; i != BytesLeft && ByteOffset != IntBytes; ++i) {
-      int n = ByteOffset;
+      unsigned n = ByteOffset;
       if (!DL.isLittleEndian())
         n = IntBytes - n - 1;
-      CurPtr[i] = (unsigned char)(Val >> (n * 8));
+      CurPtr[i] = Val.extractBits(8, n * 8).getZExtValue();
       ++ByteOffset;
     }
     return true;
   }
 
   if (auto *CFP = dyn_cast<ConstantFP>(C)) {
     if (CFP->getType()->isDoubleTy()) {
       C = FoldBitCast(C, Type::getInt64Ty(C->getContext()), DL);
       return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, DL);

llvm/test/Transforms/InstSimplify/ConstProp/loads.ll

 
 define i8 @load_i8_from_i1() {
 ; CHECK-LABEL: @load_i8_from_i1(
 ; CHECK-NEXT:    ret i8 -1
 ;
   %v = load i8, ptr @g_i1
   ret i8 %v
 }
+
+@global128 = internal constant i128 1125899906842625
+define i128 @load-128bit(){
+; CHECK-LABEL: @load-128bit(
+; CHECK-NEXT:    ret i128 1125899906842625
+;
+  %1 = load i128, ptr @global128, align 4
+  ret i128 %1
+}
+
+; TODO: Current ReadDataFromGlobal assumes only byte-sized integer
+define i43 @load-43bit(){
+; CHECK-LABEL: @load-43bit(
+; CHECK-NEXT:    [[TMP1:%.*]] = load i43, ptr @global128, align 4
+; CHECK-NEXT:    ret i43 [[TMP1]]
+;
+  %1 = load i43, ptr @global128, align 4
+  ret i43 %1
+}