Consider isLegalAddressingImm in Constant Hoisting

[zzheng]

Summary

In Thumb1, legal imm range is [0, 255] for ADD/SUB instructions. However, the
legal imm range for LD/ST in (R+Imm) addressing mode is [0, 127]. Imms in
[128, 255] are materialized by mov R, #imm, and LD/STs use them in (R+R)
addressing mode.

This patch checks if a constant is used as offset in (R+Imm), if so, it checks
isLegalAddressingMode passing the constant value as BaseOffset.

[zzheng]

ping?

[efriedma]

Please upload patches with full context (http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface).

This could probably use a few more tests to show the correct type is getting passed to isLegalAddressingMode (e.g. on Thumb1, an i8 load only supports offsets 0-31, but an i32 load supports offsets 0-124.)

[zzheng]

Updated test case as Eli suggested.

[zzheng]

ping...

[efriedma]

lib/Transforms/Scalar/ConstantHoisting.cpp

594

Oh, oops, should have spotted the issue here sooner.

This is checking that the use is a store instruction, but it isn't checking that the value is being used as an address. So it'll do the wrong thing for an instruction like store i32* inttoptr (i32 805874688 to i16*), i32** %foo.

610

I think HasBaseReg should be true; the base is the hoisted constant. Not sure that actually makes a difference in practice; the ARM backend, at least, doesn't check HasBaseReg when the Scale is zero.

[zzheng]

Updated as Eli suggested.

[zzheng]

lib/Transforms/Scalar/ConstantHoisting.cpp

594

Nice catch.

[zzheng]

Previous version mistakenly checks MinValItr->ConstInst rather than CC->ConstInst against StoreInst User's pointer operand.

[efriedma]

lib/Transforms/Scalar/ConstantHoisting.cpp

598

The break should be inside the if statement, I think?

I guess more broadly, it's not clear what we should do if there are mixed address and non-address uses... but the current behavior is reasonable.

[zzheng]

Moved 'break;' under proper if statement.

[efriedma]

lib/Transforms/Scalar/ConstantHoisting.cpp

596

Looking again, this doesn't work. ConstInt is a ConstantInt, SI->getPointerOperand() is a pointer.

ConstantUser has a member OpndIdx which might be helpful here. And more test coverage for stores would be nice.

[efriedma]

LGTM

lib/Transforms/Scalar/ConstantHoisting.cpp

void ConstantHoistingPass::findBaseConstants() {
   });
 
   // Simple linear scan through the sorted constant candidate vector for viable
   // merge candidates.
   auto MinValItr = ConstCandVec.begin();
   for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
        CC != E; ++CC) {
     if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
+      Type *MemUseValTy = nullptr;
+      for (auto &U : CC->Uses) {
+        auto *UI = U.Inst;
+        if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
+          MemUseValTy = LI->getType();
+          break;
+        } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
+          // Make sure the constant is used as pointer operand of the StoreInst.
+          if (SI->getPointerOperand() == CC->ConstInt)
+            MemUseValTy = SI->getValueOperand()->getType();
+          break;
+        }
+      }
+
       // Check if the constant is in range of an add with immediate.
       APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
       if ((Diff.getBitWidth() <= 64) &&
-          TTI->isLegalAddImmediate(Diff.getSExtValue()))
+          TTI->isLegalAddImmediate(Diff.getSExtValue()) &&
+          // Check if Diff can be used as offset in addressing mode of the user
+          // memory instruction.
+          (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
+           /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
+           /*HasBaseReg*/true, /*Scale*/0)))
         continue;
     }
     // We either have now a different constant type or the constant is not in
     // range of an add with immediate anymore.
     findAndMakeBaseConstant(MinValItr, CC);
     // Start a new base constant search.
     MinValItr = CC;
   }

test/Transforms/ConstantHoisting/ARM/is-legal-addressing-imm.ll

+; RUN: opt -consthoist -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"
+
+; Check that for i8 type, the maximum legal offset is 31.
+; Also check that an constant used as value to be stored rather than
+; pointer in a store instruction is hoisted.
+; CHECK: foo_i8
+; CHECK-DAG:  %[[C1:const[0-9]?]] = bitcast i32 805874720 to i32
+; CHECK-DAG:  %[[C2:const[0-9]?]] = bitcast i32 805874688 to i32
+; CHECK:  %0 = inttoptr i32 %const to i8*
+; CHECK-NEXT:  %1 = load volatile i8, i8* %0
+; CHECK-NEXT:  %[[M1:const_mat[0-9]?]] = add i32 %[[C2]], 4
+; CHECK-NEXT:  %2 = inttoptr i32 %[[M1]] to i8*
+; CHECK-NEXT:  %3 = load volatile i8, i8* %2
+; CHECK-NEXT:  %[[M2:const_mat[0-9]?]] = add i32 %[[C2]], 31
+; CHECK-NEXT:  %4 = inttoptr i32 %[[M2]] to i8*
+; CHECK-NEXT:  %5 = load volatile i8, i8* %4
+; CHECK-NEXT:  %6 = inttoptr i32 %[[C1]] to i8*
+; CHECK-NEXT:  %7 = load volatile i8, i8* %6
+; CHECK-NEXT:  %[[M3:const_mat[0-9]?]] = add i32 %[[C1]], 7
+; CHECK-NEXT:  %8 = inttoptr i32 %[[M3]] to i8*
+; CHECK-NEXT:  %9 = load volatile i8, i8* %8
+; CHECK-NEXT:  %[[M4:const_mat[0-9]?]] = add i32 %[[C1]], 80
+; CHECK-NEXT:  %10 = inttoptr i32 %[[M4]] to i8*
+; CHECK-NEXT:  store i8* %10, i8** @goo
+
+@goo = global i8* undef
+
+define void @foo_i8() {
+entry:
+  %0 = load volatile i8, i8* inttoptr (i32 805874688 to i8*)
+  %1 = load volatile i8, i8* inttoptr (i32 805874692 to i8*)
+  %2 = load volatile i8, i8* inttoptr (i32 805874719 to i8*)
+  %3 = load volatile i8, i8* inttoptr (i32 805874720 to i8*)
+  %4 = load volatile i8, i8* inttoptr (i32 805874727 to i8*)
+  store i8* inttoptr(i32 805874800 to i8*), i8** @goo
+  ret void
+}
+
+; Check that for i16 type, the maximum legal offset is 62.
+; CHECK: foo_i16
+; CHECK-DAG: %[[C1:const[0-9]?]] = bitcast i32 805874752 to i32
+; CHECK-DAG: %[[C2:const[0-9]?]] = bitcast i32 805874688 to i32
+; CHECK: %0 = inttoptr i32 %[[C2]] to i16*
+; CHECK-NEXT: %1 = load volatile i16, i16* %0, align 2
+; CHECK-NEXT: %[[M1:const_mat[0-9]?]] = add i32 %[[C2]], 4
+; CHECK-NEXT: %2 = inttoptr i32 %[[M1]] to i16*
+; CHECK-NEXT: %3 = load volatile i16, i16* %2, align 2
+; CHECK-NEXT: %[[M2:const_mat[0-9]?]] = add i32 %[[C2]], 32
+; CHECK-NEXT: %4 = inttoptr i32 %[[M2]] to i16*
+; CHECK-NEXT: %5 = load volatile i16, i16* %4, align 2
+; CHECK-NEXT: %[[M3:const_mat[0-9]?]] = add i32 %[[C2]], 62
+; CHECK-NEXT: %6 = inttoptr i32 %[[M3]] to i16*
+; CHECK-NEXT: %7 = load volatile i16, i16* %6, align 2
+; CHECK-NEXT: %8 = inttoptr i32 %[[C1]] to i16*
+; CHECK-NEXT: %9 = load volatile i16, i16* %8, align 2
+; CHECK-NEXT: %[[M4:const_mat[0-9]?]] = add i32 %[[C1]], 22
+; CHECK-NEXT: %10 = inttoptr i32 %[[M4]] to i16*
+; CHECK-NEXT: %11 = load volatile i16, i16* %10, align 2
+
+define void @foo_i16() {
+entry:
+  %0 = load volatile i16, i16* inttoptr (i32 805874688 to i16*), align 2
+  %1 = load volatile i16, i16* inttoptr (i32 805874692 to i16*), align 2
+  %2 = load volatile i16, i16* inttoptr (i32 805874720 to i16*), align 2
+  %3 = load volatile i16, i16* inttoptr (i32 805874750 to i16*), align 2
+  %4 = load volatile i16, i16* inttoptr (i32 805874752 to i16*), align 2
+  %5 = load volatile i16, i16* inttoptr (i32 805874774 to i16*), align 2
+  ret void
+}
+
+; Check that for i32 type, the maximum legal offset is 124.
+; CHECK: foo_i32
+; CHECK-DAG:  %[[C1:const[0-9]?]] = bitcast i32 805874816 to i32
+; CHECK-DAG:  %[[C2:const[0-9]?]] = bitcast i32 805874688 to i32
+; CHECK:  %0 = inttoptr i32 %[[C2]] to i32*
+; CHECK-NEXT:  %1 = load volatile i32, i32* %0, align 4
+; CHECK-NEXT:  %[[M1:const_mat[0-9]?]] = add i32 %[[C2]], 4
+; CHECK-NEXT:  %2 = inttoptr i32 %[[M1]] to i32*
+; CHECK-NEXT:  %3 = load volatile i32, i32* %2, align 4
+; CHECK-NEXT:  %[[M2:const_mat[0-9]?]] = add i32 %[[C2]], 124
+; CHECK-NEXT:  %4 = inttoptr i32 %[[M2]] to i32*
+; CHECK-NEXT:  %5 = load volatile i32, i32* %4, align 4
+; CHECK-NEXT:  %6 = inttoptr i32 %[[C1]] to i32*
+; CHECK-NEXT:  %7 = load volatile i32, i32* %6, align 4
+; CHECK-NEXT:  %[[M3:const_mat[0-9]?]] = add i32 %[[C1]], 8
+; CHECK-NEXT:  %8 = inttoptr i32 %[[M3]] to i32*
+; CHECK-NEXT:  %9 = load volatile i32, i32* %8, align 4
+; CHECK-NEXT:  %[[M4:const_mat[0-9]?]] = add i32 %[[C1]], 12
+; CHECK-NEXT:  %10 = inttoptr i32 %[[M4]] to i32*
+; CHECK-NEXT:  %11 = load volatile i32, i32* %10, align 4
+
+define void @foo_i32() {
+entry:
+  %0 = load volatile i32, i32* inttoptr (i32 805874688 to i32*), align 4
+  %1 = load volatile i32, i32* inttoptr (i32 805874692 to i32*), align 4
+  %2 = load volatile i32, i32* inttoptr (i32 805874812 to i32*), align 4
+  %3 = load volatile i32, i32* inttoptr (i32 805874816 to i32*), align 4
+  %4 = load volatile i32, i32* inttoptr (i32 805874824 to i32*), align 4
+  %5 = load volatile i32, i32* inttoptr (i32 805874828 to i32*), align 4
+  ret void
+}
+