551 lines · cpp
1//===- CallSiteSplitting.cpp ----------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a transformation that tries to split a call-site to pass10// more constrained arguments if its argument is predicated in the control flow11// so that we can expose better context to the later passes (e.g, inliner, jump12// threading, or IPA-CP based function cloning, etc.).13// As of now we support two cases :14//15// 1) Try to a split call-site with constrained arguments, if any constraints16// on any argument can be found by following the single predecessors of the17// all site's predecessors. Currently this pass only handles call-sites with 218// predecessors. For example, in the code below, we try to split the call-site19// since we can predicate the argument(ptr) based on the OR condition.20//21// Split from :22// if (!ptr || c)23// callee(ptr);24// to :25// if (!ptr)26// callee(null) // set the known constant value27// else if (c)28// callee(nonnull ptr) // set non-null attribute in the argument29//30// 2) We can also split a call-site based on constant incoming values of a PHI31// For example,32// from :33// Header:34// %c = icmp eq i32 %i1, %i235// br i1 %c, label %Tail, label %TBB36// TBB:37// br label Tail%38// Tail:39// %p = phi i32 [ 0, %Header], [ 1, %TBB]40// call void @bar(i32 %p)41// to42// Header:43// %c = icmp eq i32 %i1, %i244// br i1 %c, label %Tail-split0, label %TBB45// TBB:46// br label %Tail-split147// Tail-split0:48// call void @bar(i32 0)49// br label %Tail50// Tail-split1:51// call void @bar(i32 1)52// br label %Tail53// Tail:54// %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ]55//56//===----------------------------------------------------------------------===//57 58#include "llvm/Transforms/Scalar/CallSiteSplitting.h"59#include "llvm/ADT/Statistic.h"60#include "llvm/Analysis/DomTreeUpdater.h"61#include "llvm/Analysis/TargetLibraryInfo.h"62#include "llvm/Analysis/TargetTransformInfo.h"63#include "llvm/IR/IntrinsicInst.h"64#include "llvm/IR/PatternMatch.h"65#include "llvm/Support/CommandLine.h"66#include "llvm/Support/Debug.h"67#include "llvm/Transforms/Utils/Cloning.h"68#include "llvm/Transforms/Utils/Local.h"69 70using namespace llvm;71using namespace PatternMatch;72 73#define DEBUG_TYPE "callsite-splitting"74 75STATISTIC(NumCallSiteSplit, "Number of call-site split");76 77/// Only allow instructions before a call, if their CodeSize cost is below78/// DuplicationThreshold. Those instructions need to be duplicated in all79/// split blocks.80static cl::opt<unsigned>81 DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,82 cl::desc("Only allow instructions before a call, if "83 "their cost is below DuplicationThreshold"),84 cl::init(5));85 86static void addNonNullAttribute(CallBase &CB, Value *Op) {87 unsigned ArgNo = 0;88 for (auto &I : CB.args()) {89 if (&*I == Op)90 CB.addParamAttr(ArgNo, Attribute::NonNull);91 ++ArgNo;92 }93}94 95static void setConstantInArgument(CallBase &CB, Value *Op,96 Constant *ConstValue) {97 unsigned ArgNo = 0;98 for (auto &I : CB.args()) {99 if (&*I == Op) {100 // It is possible we have already added the non-null attribute to the101 // parameter by using an earlier constraining condition.102 CB.removeParamAttr(ArgNo, Attribute::NonNull);103 CB.setArgOperand(ArgNo, ConstValue);104 }105 ++ArgNo;106 }107}108 109static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallBase &CB) {110 assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");111 Value *Op0 = Cmp->getOperand(0);112 unsigned ArgNo = 0;113 for (auto I = CB.arg_begin(), E = CB.arg_end(); I != E; ++I, ++ArgNo) {114 // Don't consider constant or arguments that are already known non-null.115 if (isa<Constant>(*I) || CB.paramHasAttr(ArgNo, Attribute::NonNull))116 continue;117 118 if (*I == Op0)119 return true;120 }121 return false;122}123 124using ConditionTy = std::pair<ICmpInst *, unsigned>;125using ConditionsTy = SmallVector<ConditionTy, 2>;126 127/// If From has a conditional jump to To, add the condition to Conditions,128/// if it is relevant to any argument at CB.129static void recordCondition(CallBase &CB, BasicBlock *From, BasicBlock *To,130 ConditionsTy &Conditions) {131 auto *BI = dyn_cast<BranchInst>(From->getTerminator());132 if (!BI || !BI->isConditional())133 return;134 135 CmpPredicate Pred;136 Value *Cond = BI->getCondition();137 if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant())))138 return;139 140 ICmpInst *Cmp = cast<ICmpInst>(Cond);141 if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)142 if (isCondRelevantToAnyCallArgument(Cmp, CB))143 Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To144 ? Pred145 : Cmp->getInverseCmpPredicate()});146}147 148/// Record ICmp conditions relevant to any argument in CB following Pred's149/// single predecessors. If there are conflicting conditions along a path, like150/// x == 1 and x == 0, the first condition will be used. We stop once we reach151/// an edge to StopAt.152static void recordConditions(CallBase &CB, BasicBlock *Pred,153 ConditionsTy &Conditions, BasicBlock *StopAt) {154 BasicBlock *From = Pred;155 BasicBlock *To = Pred;156 SmallPtrSet<BasicBlock *, 4> Visited;157 while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&158 (From = From->getSinglePredecessor())) {159 recordCondition(CB, From, To, Conditions);160 Visited.insert(From);161 To = From;162 }163}164 165static void addConditions(CallBase &CB, const ConditionsTy &Conditions) {166 for (const auto &Cond : Conditions) {167 Value *Arg = Cond.first->getOperand(0);168 Constant *ConstVal = cast<Constant>(Cond.first->getOperand(1));169 if (Cond.second == ICmpInst::ICMP_EQ)170 setConstantInArgument(CB, Arg, ConstVal);171 else if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue()) {172 assert(Cond.second == ICmpInst::ICMP_NE);173 addNonNullAttribute(CB, Arg);174 }175 }176}177 178static SmallVector<BasicBlock *, 2> getTwoPredecessors(BasicBlock *BB) {179 SmallVector<BasicBlock *, 2> Preds(predecessors((BB)));180 assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");181 return Preds;182}183 184static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI) {185 if (CB.isConvergent() || CB.cannotDuplicate())186 return false;187 188 // FIXME: As of now we handle only CallInst. InvokeInst could be handled189 // without too much effort.190 if (!isa<CallInst>(CB))191 return false;192 193 BasicBlock *CallSiteBB = CB.getParent();194 // Need 2 predecessors and cannot split an edge from an IndirectBrInst.195 SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));196 if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||197 isa<IndirectBrInst>(Preds[1]->getTerminator()))198 return false;199 200 // BasicBlock::canSplitPredecessors is more aggressive, so checking for201 // BasicBlock::isEHPad as well.202 if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())203 return false;204 205 // Allow splitting a call-site only when the CodeSize cost of the206 // instructions before the call is less then DuplicationThreshold. The207 // instructions before the call will be duplicated in the split blocks and208 // corresponding uses will be updated.209 InstructionCost Cost = 0;210 for (auto &InstBeforeCall :211 llvm::make_range(CallSiteBB->begin(), CB.getIterator())) {212 Cost += TTI.getInstructionCost(&InstBeforeCall,213 TargetTransformInfo::TCK_CodeSize);214 if (Cost >= DuplicationThreshold)215 return false;216 }217 218 return true;219}220 221static Instruction *222cloneInstForMustTail(Instruction *I, BasicBlock::iterator Before, Value *V) {223 Instruction *Copy = I->clone();224 Copy->setName(I->getName());225 Copy->insertBefore(Before);226 if (V)227 Copy->setOperand(0, V);228 return Copy;229}230 231/// Copy mandatory `musttail` return sequence that follows original `CI`, and232/// link it up to `NewCI` value instead:233///234/// * (optional) `bitcast NewCI to ...`235/// * `ret bitcast or NewCI`236///237/// Insert this sequence right before `SplitBB`'s terminator, which will be238/// cleaned up later in `splitCallSite` below.239static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,240 Instruction *NewCI) {241 bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();242 auto II = std::next(CI->getIterator());243 244 BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);245 if (BCI)246 ++II;247 248 ReturnInst* RI = dyn_cast<ReturnInst>(&*II);249 assert(RI && "`musttail` call must be followed by `ret` instruction");250 251 Instruction *TI = SplitBB->getTerminator();252 Value *V = NewCI;253 if (BCI)254 V = cloneInstForMustTail(BCI, TI->getIterator(), V);255 cloneInstForMustTail(RI, TI->getIterator(), IsVoid ? nullptr : V);256 257 // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug258 // that prevents doing this now.259}260 261/// For each (predecessor, conditions from predecessors) pair, it will split the262/// basic block containing the call site, hook it up to the predecessor and263/// replace the call instruction with new call instructions, which contain264/// constraints based on the conditions from their predecessors.265/// For example, in the IR below with an OR condition, the call-site can266/// be split. In this case, Preds for Tail is [(Header, a == null),267/// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing268/// CallInst1, which has constraints based on the conditions from Head and269/// CallInst2, which has constraints based on the conditions coming from TBB.270///271/// From :272///273/// Header:274/// %c = icmp eq i32* %a, null275/// br i1 %c %Tail, %TBB276/// TBB:277/// %c2 = icmp eq i32* %b, null278/// br i1 %c %Tail, %End279/// Tail:280/// %ca = call i1 @callee (i32* %a, i32* %b)281///282/// to :283///284/// Header: // PredBB1 is Header285/// %c = icmp eq i32* %a, null286/// br i1 %c %Tail-split1, %TBB287/// TBB: // PredBB2 is TBB288/// %c2 = icmp eq i32* %b, null289/// br i1 %c %Tail-split2, %End290/// Tail-split1:291/// %ca1 = call @callee (i32* null, i32* %b) // CallInst1292/// br %Tail293/// Tail-split2:294/// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2295/// br %Tail296/// Tail:297/// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]298///299/// Note that in case any arguments at the call-site are constrained by its300/// predecessors, new call-sites with more constrained arguments will be301/// created in createCallSitesOnPredicatedArgument().302static void splitCallSite(CallBase &CB,303 ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,304 DomTreeUpdater &DTU) {305 BasicBlock *TailBB = CB.getParent();306 bool IsMustTailCall = CB.isMustTailCall();307 308 PHINode *CallPN = nullptr;309 310 // `musttail` calls must be followed by optional `bitcast`, and `ret`. The311 // split blocks will be terminated right after that so there're no users for312 // this phi in a `TailBB`.313 if (!IsMustTailCall && !CB.use_empty()) {314 CallPN = PHINode::Create(CB.getType(), Preds.size(), "phi.call");315 CallPN->setDebugLoc(CB.getDebugLoc());316 }317 318 LLVM_DEBUG(dbgs() << "split call-site : " << CB << " into \n");319 320 assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");321 // ValueToValueMapTy is neither copy nor moveable, so we use a simple array322 // here.323 ValueToValueMapTy ValueToValueMaps[2];324 for (unsigned i = 0; i < Preds.size(); i++) {325 BasicBlock *PredBB = Preds[i].first;326 BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween(327 TailBB, PredBB, &*std::next(CB.getIterator()), ValueToValueMaps[i],328 DTU);329 assert(SplitBlock && "Unexpected new basic block split.");330 331 auto *NewCI =332 cast<CallBase>(&*std::prev(SplitBlock->getTerminator()->getIterator()));333 addConditions(*NewCI, Preds[i].second);334 335 // Handle PHIs used as arguments in the call-site.336 for (PHINode &PN : TailBB->phis()) {337 unsigned ArgNo = 0;338 for (auto &CI : CB.args()) {339 if (&*CI == &PN) {340 NewCI->setArgOperand(ArgNo, PN.getIncomingValueForBlock(SplitBlock));341 }342 ++ArgNo;343 }344 }345 LLVM_DEBUG(dbgs() << " " << *NewCI << " in " << SplitBlock->getName()346 << "\n");347 if (CallPN)348 CallPN->addIncoming(NewCI, SplitBlock);349 350 // Clone and place bitcast and return instructions before `TI`351 if (IsMustTailCall)352 copyMustTailReturn(SplitBlock, &CB, NewCI);353 }354 355 NumCallSiteSplit++;356 357 // FIXME: remove TI in `copyMustTailReturn`358 if (IsMustTailCall) {359 // Remove superfluous `br` terminators from the end of the Split blocks360 // NOTE: Removing terminator removes the SplitBlock from the TailBB's361 // predecessors. Therefore we must get complete list of Splits before362 // attempting removal.363 SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));364 assert(Splits.size() == 2 && "Expected exactly 2 splits!");365 for (BasicBlock *BB : Splits) {366 BB->getTerminator()->eraseFromParent();367 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, TailBB}});368 }369 370 // Erase the tail block once done with musttail patching371 DTU.deleteBB(TailBB);372 return;373 }374 375 BasicBlock::iterator OriginalBegin = TailBB->begin();376 // Replace users of the original call with a PHI mering call-sites split.377 if (CallPN) {378 CallPN->insertBefore(*TailBB, OriginalBegin);379 CB.replaceAllUsesWith(CallPN);380 }381 382 // Remove instructions moved to split blocks from TailBB, from the duplicated383 // call instruction to the beginning of the basic block. If an instruction384 // has any uses, add a new PHI node to combine the values coming from the385 // split blocks. The new PHI nodes are placed before the first original386 // instruction, so we do not end up deleting them. By using reverse-order, we387 // do not introduce unnecessary PHI nodes for def-use chains from the call388 // instruction to the beginning of the block.389 auto I = CB.getReverseIterator();390 Instruction *OriginalBeginInst = &*OriginalBegin;391 while (I != TailBB->rend()) {392 Instruction *CurrentI = &*I++;393 if (!CurrentI->use_empty()) {394 // If an existing PHI has users after the call, there is no need to create395 // a new one.396 if (isa<PHINode>(CurrentI))397 continue;398 PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());399 NewPN->setDebugLoc(CurrentI->getDebugLoc());400 for (auto &Mapping : ValueToValueMaps) {401 Value *V = Mapping[CurrentI];402 NewPN->addIncoming(V, cast<Instruction>(V)->getParent());403 }404 NewPN->insertBefore(*TailBB, TailBB->begin());405 CurrentI->replaceAllUsesWith(NewPN);406 }407 CurrentI->dropDbgRecords();408 CurrentI->eraseFromParent();409 // We are done once we handled the first original instruction in TailBB.410 if (CurrentI == OriginalBeginInst)411 break;412 }413}414 415// Return true if the call-site has an argument which is a PHI with only416// constant incoming values.417static bool isPredicatedOnPHI(CallBase &CB) {418 BasicBlock *Parent = CB.getParent();419 if (&CB != &*Parent->getFirstNonPHIOrDbg())420 return false;421 422 for (auto &PN : Parent->phis()) {423 for (auto &Arg : CB.args()) {424 if (&*Arg != &PN)425 continue;426 assert(PN.getNumIncomingValues() == 2 &&427 "Unexpected number of incoming values");428 if (PN.getIncomingBlock(0) == PN.getIncomingBlock(1))429 return false;430 if (PN.getIncomingValue(0) == PN.getIncomingValue(1))431 continue;432 if (isa<Constant>(PN.getIncomingValue(0)) &&433 isa<Constant>(PN.getIncomingValue(1)))434 return true;435 }436 }437 return false;438}439 440using PredsWithCondsTy = SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2>;441 442// Check if any of the arguments in CS are predicated on a PHI node and return443// the set of predecessors we should use for splitting.444static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB) {445 if (!isPredicatedOnPHI(CB))446 return {};447 448 auto Preds = getTwoPredecessors(CB.getParent());449 return {{Preds[0], {}}, {Preds[1], {}}};450}451 452// Checks if any of the arguments in CS are predicated in a predecessor and453// returns a list of predecessors with the conditions that hold on their edges454// to CS.455static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB,456 DomTreeUpdater &DTU) {457 auto Preds = getTwoPredecessors(CB.getParent());458 if (Preds[0] == Preds[1])459 return {};460 461 // We can stop recording conditions once we reached the immediate dominator462 // for the block containing the call site. Conditions in predecessors of the463 // that node will be the same for all paths to the call site and splitting464 // is not beneficial.465 assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");466 auto *CSDTNode = DTU.getDomTree().getNode(CB.getParent());467 BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;468 469 SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2> PredsCS;470 for (auto *Pred : llvm::reverse(Preds)) {471 ConditionsTy Conditions;472 // Record condition on edge BB(CS) <- Pred473 recordCondition(CB, Pred, CB.getParent(), Conditions);474 // Record conditions following Pred's single predecessors.475 recordConditions(CB, Pred, Conditions, StopAt);476 PredsCS.push_back({Pred, Conditions});477 }478 479 if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {480 return P.second.empty();481 }))482 return {};483 484 return PredsCS;485}486 487static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI,488 DomTreeUpdater &DTU) {489 // Check if we can split the call site.490 if (!CB.arg_size() || !canSplitCallSite(CB, TTI))491 return false;492 493 auto PredsWithConds = shouldSplitOnPredicatedArgument(CB, DTU);494 if (PredsWithConds.empty())495 PredsWithConds = shouldSplitOnPHIPredicatedArgument(CB);496 if (PredsWithConds.empty())497 return false;498 499 splitCallSite(CB, PredsWithConds, DTU);500 return true;501}502 503static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI,504 TargetTransformInfo &TTI, DominatorTree &DT) {505 506 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);507 bool Changed = false;508 for (BasicBlock &BB : llvm::make_early_inc_range(F)) {509 auto II = BB.getFirstNonPHIOrDbg()->getIterator();510 auto IE = BB.getTerminator()->getIterator();511 // Iterate until we reach the terminator instruction. tryToSplitCallSite512 // can replace BB's terminator in case BB is a successor of itself. In that513 // case, IE will be invalidated and we also have to check the current514 // terminator.515 while (II != IE && &*II != BB.getTerminator()) {516 CallBase *CB = dyn_cast<CallBase>(&*II++);517 if (!CB || isa<IntrinsicInst>(CB) || isInstructionTriviallyDead(CB, &TLI))518 continue;519 520 Function *Callee = CB->getCalledFunction();521 if (!Callee || Callee->isDeclaration())522 continue;523 524 // Successful musttail call-site splits result in erased CI and erased BB.525 // Check if such path is possible before attempting the splitting.526 bool IsMustTail = CB->isMustTailCall();527 528 Changed |= tryToSplitCallSite(*CB, TTI, DTU);529 530 // There're no interesting instructions after this. The call site531 // itself might have been erased on splitting.532 if (IsMustTail)533 break;534 }535 }536 return Changed;537}538 539PreservedAnalyses CallSiteSplittingPass::run(Function &F,540 FunctionAnalysisManager &AM) {541 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);542 auto &TTI = AM.getResult<TargetIRAnalysis>(F);543 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);544 545 if (!doCallSiteSplitting(F, TLI, TTI, DT))546 return PreservedAnalyses::all();547 PreservedAnalyses PA;548 PA.preserve<DominatorTreeAnalysis>();549 return PA;550}551