CallSiteSplitting.cpp Source File (original) (raw)

70using namespace llvm;

73#define DEBUG_TYPE "callsite-splitting"

75 STATISTIC(NumCallSiteSplit, "Number of call-site split");

82 cl::desc("Only allow instructions before a call, if "

83 "their cost is below DuplicationThreshold"),

87 unsigned ArgNo = 0;

88 for (auto &I : CB.args()) {

89 if (&*I == Op)

91 ++ArgNo;

92 }

93}

97 unsigned ArgNo = 0;

98 for (auto &I : CB.args()) {

99 if (&*I == Op) {

100

101

104 }

105 ++ArgNo;

106 }

107}

108

110 assert(isa(Cmp->getOperand(1)) && "Expected a constant operand.");

111 Value *Op0 = Cmp->getOperand(0);

112 unsigned ArgNo = 0;

114

116 continue;

117

118 if (*I == Op0)

119 return true;

120 }

121 return false;

122}

123

124using ConditionTy = std::pair<ICmpInst *, unsigned>;

126

127

128

132 if (!BI || !BI->isConditional())

133 return;

134

136 Value *Cond = BI->getCondition();

138 return;

139

144 ? Pred

145 : Cmp->getInverseCmpPredicate()});

146}

147

148

149

150

151

160 Visited.insert(From);

161 To = From;

162 }

163}

164

166 for (const auto &Cond : Conditions) {

167 Value *Arg = Cond.first->getOperand(0);

174 }

175 }

176}

177

180 assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");

181 return Preds;

182}

183

186 return false;

187

188

189

191 return false;

192

194

198 return false;

199

200

201

203 return false;

204

205

206

207

208

210 for (auto &InstBeforeCall :

212 Cost += TTI.getInstructionCost(&InstBeforeCall,

215 return false;

216 }

217

218 return true;

219}

220

224 Copy->setName(I->getName());

225 Copy->insertBefore(Before);

226 if (V)

227 Copy->setOperand(0, V);

228 return Copy;

229}

230

231

232

233

234

235

236

237

238

243

245 if (BCI)

246 ++II;

247

249 assert(RI && "`musttail` call must be followed by `ret` instruction");

250

252 Value *V = NewCI;

253 if (BCI)

256

257

258

259}

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

303 ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,

307

308 PHINode *CallPN = nullptr;

309

310

311

312

313 if (!IsMustTailCall && !CB.use_empty()) {

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

322

324 for (unsigned i = 0; i < Preds.size(); i++) {

327 TailBB, PredBB, &*std::next(CB.getIterator()), ValueToValueMaps[i],

328 DTU);

330

331 auto *NewCI =

334

335

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 }

346 << "\n");

347 if (CallPN)

349

350

351 if (IsMustTailCall)

353 }

354

355 NumCallSiteSplit++;

356

357

358 if (IsMustTailCall) {

359

360

361

362

364 assert(Splits.size() == 2 && "Expected exactly 2 splits!");

366 BB->getTerminator()->eraseFromParent();

368 }

369

370

372 return;

373 }

374

376

377 if (CallPN) {

378 CallPN->insertBefore(*TailBB, OriginalBegin);

380 }

381

382

383

384

385

386

387

388

390 Instruction *OriginalBeginInst = &*OriginalBegin;

391 while (I != TailBB->rend()) {

394

395

397 continue;

400 for (auto &Mapping : ValueToValueMaps) {

401 Value *V = Mapping[CurrentI];

403 }

406 }

409

410 if (CurrentI == OriginalBeginInst)

411 break;

412 }

413}

414

415

416

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;

434 return true;

435 }

436 }

437 return false;

438}

439

441

442

443

446 return {};

447

449 return {{Preds[0], {}}, {Preds[1], {}}};

450}

451

452

453

454

458 if (Preds[0] == Preds[1])

459 return {};

460

461

462

463

464

465 assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");

467 BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;

468

472

474

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

489

491 return false;

492

494 if (PredsWithConds.empty())

496 if (PredsWithConds.empty())

497 return false;

498

500 return true;

501}

502

505

506 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);

509 auto II = BB.getFirstNonPHIOrDbg()->getIterator();

510 auto IE = BB.getTerminator()->getIterator();

511

512

513

514

515 while (II != IE && &*II != BB.getTerminator()) {

518 continue;

519

521 if (!Callee || Callee->isDeclaration())

522 continue;

523

524

525

527

529

530

531

532 if (IsMustTail)

533 break;

534 }

535 }

537}

538

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static const Function * getParent(const Value *V)

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static void addConditions(CallBase &CB, const ConditionsTy &Conditions)

Definition CallSiteSplitting.cpp:165

static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI, Instruction *NewCI)

Copy mandatory musttail return sequence that follows original CI, and link it up to NewCI value inste...

Definition CallSiteSplitting.cpp:239

SmallVector< ConditionTy, 2 > ConditionsTy

Definition CallSiteSplitting.cpp:125

static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallBase &CB)

Definition CallSiteSplitting.cpp:109

SmallVector< std::pair< BasicBlock *, ConditionsTy >, 2 > PredsWithCondsTy

Definition CallSiteSplitting.cpp:440

static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)

Definition CallSiteSplitting.cpp:503

static void recordConditions(CallBase &CB, BasicBlock *Pred, ConditionsTy &Conditions, BasicBlock *StopAt)

Record ICmp conditions relevant to any argument in CB following Pred's single predecessors.

Definition CallSiteSplitting.cpp:152

static bool isPredicatedOnPHI(CallBase &CB)

Definition CallSiteSplitting.cpp:417

static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB, DomTreeUpdater &DTU)

Definition CallSiteSplitting.cpp:455

static void addNonNullAttribute(CallBase &CB, Value *Op)

Definition CallSiteSplitting.cpp:86

static void setConstantInArgument(CallBase &CB, Value *Op, Constant *ConstValue)

Definition CallSiteSplitting.cpp:95

static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI)

Definition CallSiteSplitting.cpp:184

static Instruction * cloneInstForMustTail(Instruction *I, BasicBlock::iterator Before, Value *V)

Definition CallSiteSplitting.cpp:222

static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI, DomTreeUpdater &DTU)

Definition CallSiteSplitting.cpp:487

static void recordCondition(CallBase &CB, BasicBlock *From, BasicBlock *To, ConditionsTy &Conditions)

If From has a conditional jump to To, add the condition to Conditions, if it is relevant to any argum...

Definition CallSiteSplitting.cpp:129

static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB)

Definition CallSiteSplitting.cpp:444

static SmallVector< BasicBlock *, 2 > getTwoPredecessors(BasicBlock *BB)

Definition CallSiteSplitting.cpp:178

static cl::opt< unsigned > DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden, cl::desc("Only allow instructions before a call, if " "their cost is below DuplicationThreshold"), cl::init(5))

Only allow instructions before a call, if their CodeSize cost is below DuplicationThreshold.

static void splitCallSite(CallBase &CB, ArrayRef< std::pair< BasicBlock *, ConditionsTy > > Preds, DomTreeUpdater &DTU)

For each (predecessor, conditions from predecessors) pair, it will split the basic block containing t...

Definition CallSiteSplitting.cpp:302

uint64_t IntrinsicInst * II

const SmallVectorImpl< MachineOperand > & Cond

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This pass exposes codegen information to IR-level passes.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

InstListType::iterator iterator

Instruction iterators...

bool isEHPad() const

Return true if this basic block is an exception handling block.

LLVM_ABI bool canSplitPredecessors() const

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

This class represents a no-op cast from one type to another.

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)

Removes the attribute from the given argument.

Function * getCalledFunction() const

Returns the function called, or null if this is an indirect function invocation or the function signa...

bool cannotDuplicate() const

Determine if the invoke cannot be duplicated.

LLVM_ABI bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const

Determine whether the argument or parameter has the given attribute.

User::op_iterator arg_begin()

Return the iterator pointing to the beginning of the argument list.

LLVM_ABI bool isMustTailCall() const

Tests if this call site must be tail call optimized.

void setArgOperand(unsigned i, Value *v)

User::op_iterator arg_end()

Return the iterator pointing to the end of the argument list.

bool isConvergent() const

Determine if the invoke is convergent.

iterator_range< User::op_iterator > args()

Iteration adapter for range-for loops.

unsigned arg_size() const

void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)

Adds the attribute to the indicated argument.

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

This is an important base class in LLVM.

LLVM_ABI bool isNullValue() const

Return true if this is the value that would be returned by getNullValue.

LLVM_ABI void deleteBB(BasicBlock *DelBB)

Delete DelBB.

Analysis pass which computes a DominatorTree.

static constexpr UpdateKind Delete

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Type * getReturnType() const

Returns the type of the ret val.

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

bool hasDomTree() const

Returns true if it holds a DomTreeT.

This instruction compares its operands according to the predicate given to the constructor.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI void dropDbgRecords()

Erase any DbgRecords attached to this instruction.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

Return a value (possibly void), from a function.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Analysis pass providing the TargetTransformInfo.

Analysis pass providing the TargetLibraryInfo.

Provides information about what library functions are available for the current target.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

@ TCK_CodeSize

Instruction code size.

bool isPointerTy() const

True if this is an instance of PointerType.

bool isVoidTy() const

Return true if this is 'void'.

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

const ParentTy * getParent() const

reverse_self_iterator getReverseIterator()

self_iterator getIterator()

class_match< Constant > m_Constant()

Match an arbitrary Constant and ignore it.

bool match(Val *V, const Pattern &P)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

static cl::opt< unsigned long > StopAt("sbvec-stop-at", cl::init(StopAtDisabled), cl::Hidden, cl::desc("Vectorize if the invocation count is < than this. 0 " "disables vectorization."))

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

LLVM_ABI BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)

Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...

LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

DWARFExpression::Operation Op

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

auto predecessors(const MachineBasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

Definition CallSiteSplitting.cpp:539