[CallSiteSplitting] Support splitting of blocks with instrs before call.

[fhahn]

Summary

For basic blocks with instructions between the beginning of the block
and a call we have to duplicate the instructions before the call in all
split blocks and add PHI nodes for uses of the duplicated instructions
after the call.

Currently, the threshold for the number of instructions before a call
is quite low, to keep the impact on binary size low.

[fhahn]

Added test case test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

[fhahn]

Rebased after committing rL322599

[fhahn]

ping

[junbuml]

Do you have any result for performance and size ?

lib/Transforms/Scalar/CallSiteSplitting.cpp

79

Why don't we make it a command line option? It will be good to run a correctness test without being limited in the current default value.

312

CurrentI might point a new PHI created below (line 309) during the iteration as it iterate reversely.

test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

104 ↗

(On Diff #130039)

We need more test to see if PHIs are created properly for cloned instructions used after callsite split.

[fhahn]

Update code to insert new PHIs at the beginning of TailBB and delete instructions up to the original first instruction. This way, remove unnecessary existing PHI nodes, while not deleting newly created ones.

I hope I can post benchmark numbers with the new version of the patch tomorrow.

[fhahn]

I've run spec2006, spec2000 and the test-suite on Cortex-A57. Slight improvement in the geomean speedup, no perf regressions, not size regressions.

[fhahn]

ping

[junbuml]

Overall LGTM, but I want someone else also look at this.

lib/Transforms/Scalar/CallSiteSplitting.cpp

292

Isn't it possible to hold space for ValueToValueMapTy for each predecessor and pass its reference to DuplicateInstructionsInSplitBetween.

For example, as we only support 2 predecessors for now, we can define Remaps as a fixed size array which has ValueToValueMapTy as its element, and then we can pass the reference of each array element to DuplicateInstructionsInSplitBetween for each predecessor.

314

Instead of '2', it will be good to use the number of pred of TailBB. Or at least we need assert before using '2' directly here.

test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

158 ↗

(On Diff #130951)

I think it should be %i, instead of %0. Or did you intend [[V1]] ?

[fhahn]

Thanks for having a look! I've updated the patch to use a fixed size array for ValueToValueMapTys, used Preds.size() when creating the PHI node and updated the remaining tests.

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

292

I've changed it to use a fixed size array. I am not entirely happy with it, but it's definitely nicer than the duplication :)

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

191–193

Here we assume that the duplication costs of instructions are all same. However, I believe this assumption is not always true because each instruction here will end up differently after lowering. For example, if there is another call before the call we are trying to split, the cost for such call should be more expensive than other simple instructions (e.g., add or trunc ). If such call duplicated is inlined, the code size could be significantly impacted. I think we should consider using getUserCost(), instead of number of instructions ?

317

If CurrnetI is PHI, "Mapping[CurrentI])->getParent()" may not point the new SplitBlock becasue DuplicateInstructionsInSplitBetween map a PHI with its original incoming value. Isn't it okay to skip doing this if CurrnetI is PHI?

Based on your test_remove_unused_phi(), we should add a test case something like this :

define void @test_no_remove_used_phi(i32* %ptrarg, i32* %ptrarg2, i32 %i, i32 %i2) {
Header:
  %l1 = load i32, i32* undef, align 16
  %tobool = icmp ne i32* %ptrarg, null
  br i1 %tobool, label %TBB, label %CallSite

TBB:                                    ; preds = %Header
  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
  %0 = load i32, i32* %arrayidx, align 4
  %l2 = load i32, i32* undef, align 16
  %tobool1 = icmp ne i32 %0, 0
  br i1 %tobool1, label %CallSite, label %End

CallSite:                                          ; preds = %TBB, %Header
  %l = phi i32 [ %l1, %Header ], [ %l2, %TBB ]
  call void @bar(i32* %ptrarg, i32 %l)
  call void @bari(i32 %l)                   <------------ %l is used here, so it will hit the case I mentioned.
  br label %End

End:                                           ; preds = %CallSite, %TBB
  ret void
}

[fhahn]

Thanks Jun!
Update the patch to use getInstructionCost(i, TCK_CodeSize) to decide whether it is worth to perform call site splitting. Also avoid creating PHI nodes for existing PHI nodes unnecessarily.

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

191–193

I've updated the code to use getInstructionCost with TCK_CodeSize. Per default it uses getUserCost, which seems OK, although in some cases, the cost it returns might be too high for our case (e.g. sdiv has a high cost although it might be lowered to a single instruction)

317

Thanks, there is indeed no need to re-create the PHI node there. I've added your test case. The incoming basic blocks in the PHI node are updated to use the split blocks. I assume this is done when splitting. Not sure if it would be better to use the original basic blocks. But I think that should be follow up patch if we want to change it ;)

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

84

Considering that TCC_Basic is 1, don't you think 50 is too aggressive? For me, the conservative enough default should be TCC_Expensive.

[junbuml]

I've updated the code to use getInstructionCost with TCK_CodeSize. Per default it uses getUserCost, which seems OK, although in some cases,
the cost it returns might be too high for our case (e.g. sdiv has a high cost although it might be lowered to a single instruction)

If getUserCost is supposed to represent only the code size (I believe so), then we may need to introduce a new target hook to handle sdiv properly in getOperationCost(). @hfinkel might have better idea about it.

[fhahn]

Fix default threshold.

[fhahn]

If getUserCost is supposed to represent only the code size (I believe so), then we may need to introduce a new target hook to handle sdiv properly in getOperationCost(). @hfinkel might have better idea about it.

I am not entirely sure, but it looks like for most instructions, getUserCost delegates to getOperationCost, which per default marks sdiv & co as expensive. In any case, the patch uses

TTI.getInstructionCost(&InstBeforeCall,
                                   TargetTransformInfo::TCK_CodeSize);

so in case the code size cost becomes more accurate, we should pick it up.

lib/Transforms/Scalar/CallSiteSplitting.cpp

84

Yeah, that was left over from testing, sorry about that!

[junbuml]

LGTM, but I may want to hold it for sometime to let other reviewers take a chance to look at this as well.

lib/Transforms/Scalar/CallSiteSplitting.cpp

193

when there the CodeSize -> when the CodeSize

[fhahn]

Thanks @junbuml ! I'll wait with committing until the middle of next week or so

[fhahn]

Reverted again in rL325009, as memsan was not happy with the array of the ValueToValueMaps. I'll look into how to resolve this.

lib/Transforms/Scalar/CallSiteSplitting.cpp

 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "callsite-splitting"
 
 STATISTIC(NumCallSiteSplit, "Number of call-site split");
 
+/// Allow up to DuplicationThreshold instructions before call instructions.
+/// Those instructions need to be duplicated in all split blocks.
+static unsigned DuplicationThreshold = 5;
+
 static void addNonNullAttribute(Instruction *CallI, Instruction *NewCallI,
                                 Value *Op) {
   CallSite CS(NewCallI);
   unsigned ArgNo = 0;
   for (auto &I : CS.args()) {
     if (&*I == Op)
       CS.addParamAttr(ArgNo, Attribute::NonNull);
     ++ArgNo;
   }
 }
 
 static void setConstantInArgument(Instruction *CallI, Instruction *NewCallI,

 
 static bool canSplitCallSite(CallSite CS) {
   // FIXME: As of now we handle only CallInst. InvokeInst could be handled
   // without too much effort.
   Instruction *Instr = CS.getInstruction();
   if (!isa<CallInst>(Instr))
     return false;
 
-  // Allow splitting a call-site only when there is no instruction before the
-  // call-site in the basic block. Based on this constraint, we only clone the
-  // call instruction, and we do not move a call-site across any other
-  // instruction.
+  // Allow splitting a call-site only when there are less than
+  // DuplicationThreshold instructions before the call. The instructions
+  // before the call will be duplicated in the split blocks and corresponding
+  // uses will be updated.
   BasicBlock *CallSiteBB = Instr->getParent();
-  if (Instr != CallSiteBB->getFirstNonPHIOrDbg())
+  if (std::distance(CallSiteBB->getFirstNonPHIOrDbg()->getIterator(),
+                    Instr->getIterator()) >= DuplicationThreshold)
     return false;
 
   // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
   SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
   if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
       isa<IndirectBrInst>(Preds[1]->getTerminator()))
     return false;
 
   return CallSiteBB->canSplitPredecessors();
 }
 
 struct SplitInfo {
   BasicBlock *BB;
   Instruction *CallInst;
+  DenseMap<const Value *, Value *> Mapping;
 };
 
 /// Return true if the CS is split into its new predecessors.
 ///
 /// For each (predecessor, conditions from predecessors) pair, it will split the
 /// basic block containing the call site, hook it up to the predecessor and
 /// replace the call instruction with new call instructions, which contain
 /// constraints based on the conditions from their predecessors.
static void splitCallSite(
     const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds) {
   Instruction *Instr = CS.getInstruction();
   BasicBlock *TailBB = Instr->getParent();
 
   DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
   SmallVector<SplitInfo, 2> Splits;
   for (const auto &P : Preds) {
     BasicBlock *PredBB = P.first;
-    BasicBlock *SplitBlock =
-        SplitBlockPredecessors(TailBB, PredBB, ".predBB.split");
+    ValueToValueMapTy Remap;
+    BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween(
+                TailBB, PredBB, &*std::next(Instr->getIterator()), Remap);
     assert(SplitBlock && "Unexpected new basic block split.");
 
-    Instruction *NewCI = Instr->clone();
+    Instruction *NewCI = &*std::prev(SplitBlock->getTerminator()->getIterator());
     addConditions(CS, NewCI, P.second);
-    NewCI->insertBefore(&*SplitBlock->getFirstInsertionPt());
     CallSite NewCS(NewCI);
 
     // Handle PHIs used as arguments in the call-site.
     for (PHINode &PN : TailBB->phis()) {
       unsigned ArgNo = 0;
       for (auto &CI : CS.args()) {
         if (&*CI == &PN) {
           NewCS.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock));
         }
         ++ArgNo;
       }
     }
+
     DEBUG(dbgs() << "    " << *NewCI << " in " << SplitBlock->getName()
                  << "\n");
-    Splits.push_back({SplitBlock, NewCI});
+    SplitInfo SI;
+    SI.CallInst = NewCI;
+    SI.BB = SplitBlock;
+    for (const auto &KV : Remap) {
+      SI.Mapping[KV.first] = KV.second;
+    }
+    Splits.push_back(SI);
   }
 
   // Replace users of the original call with a PHI mering call-sites split.
   if (Instr->getNumUses()) {
     PHINode *CallPN = PHINode::Create(Instr->getType(), 2, "phi.call",
                                       TailBB->getFirstNonPHI());
 
     for (auto P : Splits)
       CallPN->addIncoming(P.CallInst, P.BB);
     Instr->replaceAllUsesWith(CallPN);
   }
-  Instr->eraseFromParent();
+
+  // Remove instructions moved to split blocks from TailBB, from the duplicated
+  // call instruction to the beginning of the basic block. If an instruction
+  // has any uses, add a new PHI node to combine the values coming from the
+  // split blocks. By using reverse-order, we do not introduce unnecessary PHI
+  // nodes for def-use chains from the call instruction to the beginning of the
+  // block.
+  auto I = Instr->getReverseIterator();
+  auto End = std::next(TailBB->getFirstNonPHIOrDbg()->getReverseIterator());
+  while (I != End) {
+   Instruction *CurrentI = &*I++;
+   if (!CurrentI->use_empty()) {
+     PHINode *NewPN = PHINode::Create(CurrentI->getType(), 2);
+     for (auto &SI: Splits)
+       NewPN->addIncoming(SI.Mapping[CurrentI], SI.BB);
+     NewPN->insertBefore(&*TailBB->getFirstInsertionPt());
+     CurrentI->replaceAllUsesWith(NewPN);
+    }
+    CurrentI->eraseFromParent();
+  }
   NumCallSiteSplit++;
 }
 
 // Return true if the call-site has an argument which is a PHI with only
 // constant incoming values.
 static bool isPredicatedOnPHI(CallSite CS) {
   Instruction *Instr = CS.getInstruction();
   BasicBlock *Parent = Instr->getParent();

test/Transforms/CallSiteSplitting/callsite-no-or-structure.ll

 ; RUN: opt < %s -callsite-splitting -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting)' -S | FileCheck %s
 
 ; CHECK-LABEL: @test_simple
 ; CHECK-LABEL: Header:
-; CHECK-NEXT: br i1 undef, label %Tail.predBB.split
-; CHECK-LABEL: TBB:
-; CHECK: br i1 %cmp, label %Tail.predBB.split1
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK-NEXT: br i1 undef, label %Header.split
+; CHECK-LABEL: Header.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 %p)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB:
+; CHECK: br i1 %cmp, label %TBB.split
+; CHECK-LABEL: TBB.split:
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 %p)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_simple(i32* %a, i32 %v, i32 %p) {
 Header:
   br i1 undef, label %Tail, label %End
 
 TBB:
   %cmp = icmp eq i32* %a, null
   br i1 %cmp, label %Tail, label %End
 
 Tail:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ; CHECK-LABEL: @test_eq_eq_eq_untaken
 ; CHECK-LABEL: Header:
-; CHECK: br i1 %tobool1, label %TBB1, label %Tail.predBB.split
-; CHECK-LABEL: TBB2:
-; CHECK: br i1 %cmp2, label %Tail.predBB.split1, label %End
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK: br i1 %tobool1, label %TBB1, label %Header.split
+; CHECK-LABEL: Header.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB2:
+; CHECK: br i1 %cmp2, label %TBB2.split, label %End
+; CHECK-LABEL: TBB2.split:
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 1, i32 99)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB2.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_eq_eq_untaken2(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB1, label %Tail
 
 TBB1:
   %cmp1 = icmp eq i32 %v, 1
   br i1 %cmp1, label %TBB2, label %End
 
 TBB2:
   %cmp2 = icmp eq i32 %p, 99
   br i1 %cmp2, label %Tail, label %End
 
 Tail:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ; CHECK-LABEL: @test_eq_ne_eq_untaken
 ; CHECK-LABEL: Header:
-; CHECK: br i1 %tobool1, label %TBB1, label %Tail.predBB.split
-; CHECK-LABEL: TBB2:
-; CHECK: br i1 %cmp2, label %Tail.predBB.split1, label %End
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK: br i1 %tobool1, label %TBB1, label %Header.split
+; CHECK-LABEL: Header.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB2:
+; CHECK: br i1 %cmp2, label %TBB2.split, label %End
+; CHECK-LABEL: TBB2.split:
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 99)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB2.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_ne_eq_untaken(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB1, label %Tail
 
 TBB1:
   %cmp1 = icmp ne i32 %v, 1
   br i1 %cmp1, label %TBB2, label %End
 
 TBB2:
   %cmp2 = icmp eq i32 %p, 99
   br i1 %cmp2, label %Tail, label %End
 
 Tail:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ; CHECK-LABEL: @test_header_header2_tbb
 ; CHECK: Header2:
-; CHECK:br i1 %tobool2, label %Tail.predBB.split, label %TBB1
-; CHECK-LABEL: TBB2:
-; CHECK: br i1 %cmp2, label %Tail.predBB.split1, label %End
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK:br i1 %tobool2, label %Header2.split, label %TBB1
+; CHECK-LABEL: Header2.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 10)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB2:
+; CHECK: br i1 %cmp2, label %TBB2.split, label %End
+; CHECK-LABEL: TBB2.split:
 ; NOTE: CallSiteSplitting cannot infer that %a is null here, as it currently
 ;       only supports recording conditions along a single predecessor path.
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 1, i32 99)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB2.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_header_header2_tbb(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB1, label %Header2
 
 Header2:
   %tobool2 = icmp eq i32 %p, 10

test/Transforms/CallSiteSplitting/callsite-split-debug.ll

 !6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, unit: !0)
 !7 = !DILocalVariable(name: "c", scope: !6, line: 5, type: !5)
 !8 = !DILocation(line: 5, column: 7, scope: !6)
 
 ; The optimization should trigger even in the presence of the dbg.value in
 ; CallSiteBB.
 
 ; CHECK-LABEL: @foo
-; CHECK-LABEL: CallsiteBB.predBB.split:
-; CHECK: [[TMP1:%[0-9]+]] = call i16 @bar(i16 1, i16 5)
-; CHECK-LABEL: CallsiteBB.predBB.split1:
-; CHECK: [[TMP2:%[0-9]+]] = call i16 @bar(i16 0, i16 5)
+; CHECK-LABEL: bb1.split:
+; CHECK: [[TMP1:%[0-9]+]] = call i16 @bar(i16 0, i16 5)
+; CHECK-LABEL: bb2.split:
+; CHECK: [[TMP2:%[0-9]+]] = call i16 @bar(i16 1, i16 5)
 ; CHECK-LABEL: CallsiteBB
-; CHECK: %phi.call = phi i16 [ [[TMP1]], %CallsiteBB.predBB.split ], [ [[TMP2]], %CallsiteBB.predBB.split1
-
+; CHECK: %phi.call = phi i16 [ [[TMP2]], %bb2.split ], [ [[TMP1]], %bb1.split

test/Transforms/CallSiteSplitting/callsite-split.ll

 ; RUN: opt < %s -callsite-splitting -inline -instcombine -jump-threading -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting),cgscc(inline),function(instcombine,jump-threading)' -S | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-linaro-linux-gnueabi"
 
 %struct.bitmap = type { i32, %struct.bitmap* }
 
 ;CHECK-LABEL: @caller
 ;CHECK-LABEL: NextCond:
 ;CHECK: br {{.*}} label %callee.exit
-;CHECK-LABEL: CallSiteBB.predBB.split:
+;CHECK-LABEL: NextCond.split:
 ;CHECK: call void @callee(%struct.bitmap* null, %struct.bitmap* null, %struct.bitmap* %b_elt, i1 false)
 ;CHECK-LABEL: callee.exit:
 ;CHECK: call void @dummy2(%struct.bitmap* %a_elt)
 
 define void @caller(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt) {
 entry:
   br label %Top