[ConstHoist] Do not rebase single (or few) dependent constant

[zzheng]

Summary

If an instance (InsertionPoint or IP) of Base constant A has only one or few rebased constants depending on it, do NOT rebase. One extra ADD instruction is required to materialize each rebased constant, assuming A and the rebased have the same materialization cost.

[zzheng]

ping...

[dmgreen]

This does seem, from the tests I ran, to reduce codesize on average. Especially on Thumb1.

lib/Transforms/Scalar/ConstantHoisting.cpp

873

Can you change this around so we don't speculatively make the Base? That seems to be the way of doing things in LLVM.

test/CodeGen/Thumb/consthoist-single-dependent.ll

2

Would these tests make more sense as opt tests? That way they can just test this specific pass, not the entire backend.

124

Clean up tests please.

[dmgreen]

test/CodeGen/Thumb/consthoist-single-dependent.ll

2

Perhaps as-well-as, not instead-of? If you still want to test this behaviour too.

[zzheng]

Cleaned up test case.
Added opt tests.
Opt tests was put in the same test file to avoid duplication and maintenance burden.

[zzheng]

lib/Transforms/Scalar/ConstantHoisting.cpp

873

Here Base is not the base constant, but an instance (insertion point) of it. A base constant can have multiple insertion points. The existing algorithm first finds the insertion points, then looks for rebased uses dominated by each insertion point.

If I understand your comments correctly, it's desirable to not to have Base at the first place so no need to erase it later. But we need the number of rebased uses to determine if we'll rewrite such uses. To get this number we need Base.

I can remove the statement:

Base->eraseFromParent();

Since Base has no use, it'll be trivially removed by DCE.

[zzheng]

In D52243#1241540, @dmgreen wrote:

This does seem, from the tests I ran, to reduce codesize on average. Especially on Thumb1.

Yes, we're trying to reduce code size on Thumb1 for an internal workload.

[dmgreen]

lib/Transforms/Scalar/ConstantHoisting.cpp

873

(I think) because we are inserting Base at IP, Base->getParent will just be IP->getParent, and if we use that we can move the code to create Base (and the debug message after) to after this check.

Unless findMatInsertPt is doing something I don't expect and requiring that Base has been created? Make sure that works, and all the tests are passing.

test/CodeGen/Thumb/consthoist-single-dependent.ll

14

Can you add the bb these are expected to be in, like in "carla" below. I think thats good at makes the intent a lot clearer.

[zzheng]

Moved collecting dependent rebased and checking size of ToBeRebased prior to emitting bitcast of base constants
Added bb labels to check in the test case.

[zzheng]

lib/Transforms/Scalar/ConstantHoisting.cpp

873

Ah, didn't see this. Thanks.

[dmgreen]

LGTM, with one minor Nit.

test/CodeGen/Thumb/consthoist-single-dependent.ll

61

You can remove this phab reference, or point to the test added there.

lib/Transforms/Scalar/ConstantHoisting.cpp

static cl::opt<bool> ConstHoistWithBlockFrequency(
     cl::desc("Enable the use of the block frequency analysis to reduce the "
              "chance to execute const materialization more frequently than "
              "without hoisting."));
 
 static cl::opt<bool> ConstHoistGEP(
     "consthoist-gep", cl::init(false), cl::Hidden,
     cl::desc("Try hoisting constant gep expressions"));
 
+static cl::opt<unsigned>
+MinNumOfDependentToRebase("consthoist-min-num-to-rebase",
+    cl::desc("Do not rebase if number of dependent constants of a Base is less "
+             "than this number."),
+    cl::init(2), cl::Hidden);
+
 namespace {
 
 /// The constant hoisting pass.
 class ConstantHoistingLegacyPass : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
 
   ConstantHoistingLegacyPass() : FunctionPass(ID) {
bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
   SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec =
       BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
   for (auto const &ConstInfo : ConstInfoVec) {
     SmallPtrSet<Instruction *, 8> IPSet = findConstantInsertionPoint(ConstInfo);
     assert(!IPSet.empty() && "IPSet is empty");
 
     unsigned UsesNum = 0;
     unsigned ReBasesNum = 0;
+    unsigned NotRebasedNum = 0;
     for (Instruction *IP : IPSet) {
       Instruction *Base = nullptr;
       // Hoist and hide the base constant behind a bitcast.
       if (ConstInfo.BaseExpr) {
         assert(BaseGV && "A base constant expression must have an base GV");
         Type *Ty = ConstInfo.BaseExpr->getType();
         Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
       } else {
         IntegerType *Ty = ConstInfo.BaseInt->getType();
         Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
       }
 
       Base->setDebugLoc(IP->getDebugLoc());
 
       LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
                         << ") to BB " << IP->getParent()->getName() << '\n'
                         << *Base << '\n');
 
       // Emit materialization code for all rebased constants.
       unsigned Uses = 0;
+      // First, collect dependent constants of Base.
+      using RebasedUse = std::tuple<Constant *, Type *, ConstantUser>;
+      SmallVector<RebasedUse, 4> ToBeRebased;
       for (auto const &RCI : ConstInfo.RebasedConstants) {
         for (auto const &U : RCI.Uses) {
           Uses++;
           BasicBlock *OrigMatInsertBB =
               findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
           // If Base constant is to be inserted in multiple places,
           // generate rebase for U using the Base dominating U.
           if (IPSet.size() == 1 ||
-              DT->dominates(Base->getParent(), OrigMatInsertBB)) {
-            emitBaseConstants(Base, RCI.Offset, RCI.Ty, U);
-            ReBasesNum++;
-          }
-
-          Base->setDebugLoc(DILocation::getMergedLocation(
-              Base->getDebugLoc(), U.Inst->getDebugLoc()));
+              DT->dominates(Base->getParent(), OrigMatInsertBB))
+            ToBeRebased.push_back(RebasedUse(RCI.Offset, RCI.Ty, U));
         }
       }
       UsesNum = Uses;
 
+      // If there is few constants depend on Base, skip rebasing, assuming
+      // Base and the rebased have the same materialization cost.
+      // Remove Base as well since it's not needed, anymore.
+      if (ToBeRebased.size() < MinNumOfDependentToRebase) {
+        Base->eraseFromParent();
+        NotRebasedNum += ToBeRebased.size();
+        continue;
+      }
+
+      // ToBeRebased.size() >= 2, rebase the constants.
+      for (auto const &R : ToBeRebased) {
+        Constant *Off = std::get<0>(R);
+        Type *Ty = std::get<1>(R);
+        ConstantUser U = std::get<2>(R);
+        emitBaseConstants(Base, Off, Ty, U);
+        ReBasesNum++;
         // Use the same debug location as the last user of the constant.
+        Base->setDebugLoc(DILocation::getMergedLocation(
+            Base->getDebugLoc(), U.Inst->getDebugLoc()));
+      }
       assert(!Base->use_empty() && "The use list is empty!?");
       assert(isa<Instruction>(Base->user_back()) &&
              "All uses should be instructions.");
     }
     (void)UsesNum;
     (void)ReBasesNum;
+    (void)NotRebasedNum;
     // Expect all uses are rebased after rebase is done.
-    assert(UsesNum == ReBasesNum && "Not all uses are rebased");
+    assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
+           "Not all uses are rebased");
 
     NumConstantsHoisted++;
 
     // Base constant is also included in ConstInfo.RebasedConstants, so
     // deduct 1 from ConstInfo.RebasedConstants.size().
     NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
 
     MadeChange = true;

test/CodeGen/Thumb/consthoist-single-dependent.ll

+; RUN: opt -consthoist -S %s -o - | FileCheck %s --check-prefix=OPT
+; RUN: opt -consthoist -S -consthoist-min-num-to-rebase=1 %s -o - | FileCheck %s --check-prefix=OPT --check-prefix=OPT-1
+; RUN: opt -consthoist -S -consthoist-min-num-to-rebase=2 %s -o - | FileCheck %s --check-prefix=OPT --check-prefix=OPT-2
+; RUN: opt -consthoist -S -consthoist-min-num-to-rebase=3 %s -o - | FileCheck %s --check-prefix=OPT --check-prefix=OPT-3
+
+; RUN: llc %s -o - | FileCheck %s --check-prefix=LLC
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv6m-none-unknown-musleabi"
+
+; Test that constant 0 and 1 of i1 type is NOT hoisted due low
+; materializing cost.
+
+; OPT-LABEL: avalon
+; OPT: store i1 true
+; OPT: store i1 false
+; OPT: store i1 false
+; OPT: store i1 false
+; OPT-NOT: add
+
+; LLC-LABEL: avalon
+; LLC-DAG: movs r{{[0-9]+}}, #0
+; LLC-DAG: movs r{{[0-9]+}}, #0
+; LLC-DAG: movs r{{[0-9]+}}, #1
+; LLC-NOT: add
+
+@global = local_unnamed_addr global i1 undef, align 1
+@global.0 = local_unnamed_addr global i1 undef, align 1
+
+define void @avalon() #0 {
+bb:
+  switch i8 undef, label %bb5 [
+    i8 0, label %bb1
+    i8 -1, label %bb2
+    i8 1, label %bb3
+  ]
+
+bb1:
+  store i1 1, i1* @global, align 1
+  unreachable
+
+bb2:
+  store i1 0, i1* @global, align 1
+  unreachable
+
+bb3:
+  store i1 0, i1* @global.0, align 1
+  store i1 0, i1* @global, align 1
+  unreachable
+
+bb5:
+  ret void
+}
+
+; Test that for i8 type, constant -1 is not rebased since it's the only
+; dependent of base constant -2.
+; This test is also covered by https://reviews.llvm.org/D52257.
+
+; OPT-LABEL: barney
+; OPT: store i8 -1
+; OPT: store i8 -2
+; OPT: store i8 -2
+; OPT: store i8 -2
+; OPT-NOT: add
+
+; LLC-LABEL: barney
+; LLC-DAG: movs r{{[0-9]+}}, #254
+; LLC-DAG: movs r{{[0-9]+}}, #255
+; LLC-NOT: mvn
+; LLC-NOT: add
+
+@global.1 = local_unnamed_addr global i8 undef, align 1
+@global.2 = local_unnamed_addr global i8 undef, align 1
+
+define void @barney() #0 {
+bb:
+  switch i8 undef, label %bb5 [
+    i8 0, label %bb1
+    i8 -1, label %bb2
+    i8 1, label %bb3
+  ]
+
+bb1:                                              ; preds = %bb
+  store i8 -1, i8* @global.1, align 1
+  unreachable
+
+bb2:                                              ; preds = %bb
+  store i8 -2, i8* @global.1, align 1
+  unreachable
+
+bb3:                                              ; preds = %bb
+  store i8 -2, i8* @global.2, align 1
+  store i8 -2, i8* @global.1, align 1
+  unreachable
+
+bb5:                                              ; preds = %bb
+  ret void
+}
+
+; Test that for i16 type constant 65532 is not rebased if it's the only
+; dependent of base constant 65531. Cost would be the same if rebased.
+; If rebased, 3 two-byte instructions:
+;   movs    r0, #4
+;   mvns    r0, r0
+;   adds    r0, r0, #1
+; If NOT rebased, 1 two-byte instruction plus 1 four-byte CP entry:
+;           ldr     r1, .LCPI2_3
+;           ...
+;   .LCPI2_3:
+;           .long   65532
+
+; OPT-LABEL: carla
+
+; -consthoist-min-num-to-rebase=1, check that 65532 and single use of 65531
+; in bb2 is rebased
+; OPT-1: bb1:
+; OPT-1: %[[C1:const[0-9]?]] = bitcast i16 -5 to i16
+; OPT-1-NEXT: %const_mat = add i16 %[[C1]], 1
+; OPT-1-NEXT: store i16 %const_mat, i16* @global.3, align 1
+; OPT-1: bb2:
+; OPT-1-NEXT: %[[C2:const[0-9]?]] = bitcast i16 -5 to i16
+; OPT-1-NEXT: store i16 %[[C2]], i16* @global.3, align 1
+; OPT-1: bb3:
+; OPT-1-NEXT: %[[C3:const[0-9]?]] = bitcast i16 -5 to i16
+; OPT-1-NEXT: store i16 %[[C3]], i16* @global.4, align 1
+; OPT-1-NEXT: store i16 %[[C3]], i16* @global.3, align 1
+
+; -consthoist-min-num-to-rebase=2, check that 65532 and single use of 65531
+; in bb2 is not rebased
+; OPT-2: bb1:
+; OPT-2-NEXT: store i16 -4, i16* @global.3, align 1
+; OPT-2: bb2:
+; OPT-2-NEXT: store i16 -5, i16* @global.3, align 1
+; OPT-2: bb3:
+; OPT-2-NEXT:   %[[C4:const[0-9]?]] = bitcast i16 -5 to i16
+; OPT-2-NEXT:   store i16 %[[C4]], i16* @global.4, align 1
+; OPT-2-NEXT:   store i16 %[[C4]], i16* @global.3, align 1
+; OPT-2-NOT: add
+
+; -consthoist-min-num-to-rebase=3, check that dual uses of 65531 in bb3 are
+; not rebase
+; OPT-3: bb1:
+; OPT-3-NEXT: store i16 -4, i16* @global.3, align 1
+; OPT-3: bb2:
+; OPT-3-NEXT: store i16 -5, i16* @global.3, align 1
+; OPT-3: bb3:
+; OPT-3-NEXT:   store i16 -5, i16* @global.4, align 1
+; OPT-3-NEXT:   store i16 -5, i16* @global.3, align 1
+; OPT-3-NOT: add
+; OPT-3-NOT: bitcast
+
+; LLC-LABEL: carla
+; LLC-DAG: ldr r{{[0-9]+}}, .LCPI2_1
+; LLC-DAG: ldr r{{[0-9]+}}, .LCPI2_3
+; LLC-NOT: mvn
+; LLC-NOT: add
+
+@global.3 = local_unnamed_addr global i16 undef, align 2
+@global.4 = local_unnamed_addr global i16 undef, align 2
+
+define void @carla() {
+bb:
+  switch i8 undef, label %bb5 [
+    i8 0, label %bb1
+    i8 -1, label %bb2
+    i8 1, label %bb3
+  ]
+
+bb1:                                              ; preds = %bb
+  store i16 65532, i16* @global.3, align 1
+  unreachable
+
+bb2:                                              ; preds = %bb
+  store i16 65531, i16* @global.3, align 1
+  unreachable
+
+bb3:                                              ; preds = %bb
+  store i16 65531, i16* @global.4, align 1
+  store i16 65531, i16* @global.3, align 1
+  unreachable
+
+bb5:                                              ; preds = %bb
+  ret void
+}