CallSiteSplitting.cpp Source File (original) (raw)

70using namespace llvm;

71using namespace PatternMatch;

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

115 if (isa(*I) || CB.paramHasAttr(ArgNo, Attribute::NonNull))

116 continue;

117

118 if (*I == Op0)

119 return true;

120 }

121 return false;

122}

123

126

127

128

131 auto *BI = dyn_cast(From->getTerminator());

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

133 return;

134

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

138 return;

139

141 if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)

143 Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To

144 ? Pred

145 : Cmp->getInverseCmpPredicate()});

146}

147

148

149

150

151

157 while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&

158 (From = From->getSinglePredecessor())) {

162 }

163}

164

166 for (const auto &Cond : Conditions) {

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

168 Constant *ConstVal = cast(Cond.first->getOperand(1));

169 if (Cond.second == ICmpInst::ICMP_EQ)

172 assert(Cond.second == ICmpInst::ICMP_NE);

174 }

175 }

176}

177

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

181 return Preds;

182}

183

186 return false;

187

188

189

190 if (!isa(CB))

191 return false;

192

194

196 if (Preds.size() != 2 || isa(Preds[0]->getTerminator()) ||

197 isa(Preds[1]->getTerminator()))

198 return false;

199

200

201

203 return false;

204

205

206

207

208

210 for (auto &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

396 if (isa(CurrentI))

397 continue;

400 for (auto &Mapping : ValueToValueMaps)

402 cast(Mapping[CurrentI])->getParent());

404 CurrentI->replaceAllUsesWith(NewPN);

405 }

408

409 if (CurrentI == OriginalBeginInst)

410 break;

411 }

412}

413

414

415

419 return false;

420

421 for (auto &PN : Parent->phis()) {

422 for (auto &Arg : CB.args()) {

423 if (&*Arg != &PN)

424 continue;

425 assert(PN.getNumIncomingValues() == 2 &&

426 "Unexpected number of incoming values");

427 if (PN.getIncomingBlock(0) == PN.getIncomingBlock(1))

428 return false;

429 if (PN.getIncomingValue(0) == PN.getIncomingValue(1))

430 continue;

431 if (isa(PN.getIncomingValue(0)) &&

432 isa(PN.getIncomingValue(1)))

433 return true;

434 }

435 }

436 return false;

437}

438

440

441

442

445 return {};

446

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

449}

450

451

452

453

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

458 return {};

459

460

461

462

463

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

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

467

471

473

475 PredsCS.push_back({Pred, Conditions});

476 }

477

478 if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {

479 return P.second.empty();

480 }))

481 return {};

482

483 return PredsCS;

484}

485

488

490 return false;

491

493 if (PredsWithConds.empty())

495 if (PredsWithConds.empty())

496 return false;

497

499 return true;

500}

501

504

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

506 bool Changed = false;

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

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

510

511

512

513

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

515 CallBase *CB = dyn_cast(&*II++);

517 continue;

518

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

521 continue;

522

523

524

526

528

529

530

531 if (IsMustTail)

532 break;

533 }

534 }

535 return Changed;

536}

537

543

548 return PA;

549}

static const Function * getParent(const Value *V)

BlockVerifier::State From

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

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...

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

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

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.

static bool isPredicatedOnPHI(CallBase &CB)

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

static Instruction * cloneInstForMustTail(Instruction *I, Instruction *Before, Value *V)

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

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

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

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

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...

static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB)

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

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.

std::pair< ICmpInst *, unsigned > ConditionTy

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...

uint64_t IntrinsicInst * II

const SmallVectorImpl< MachineOperand > & Cond

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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.

A container for analyses that lazily runs them and caches their results.

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.

const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

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

InstListType::iterator iterator

Instruction iterators...

bool isEHPad() const

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

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...

bool canSplitPredecessors() const

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.

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.

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.

bool isNullValue() const

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

This class represents an Operation in the Expression.

void deleteBB(BasicBlock *DelBB)

Delete DelBB.

Analysis pass which computes a DominatorTree.

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.

void insertBefore(Instruction *InsertPos)

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

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

InstListType::iterator eraseFromParent()

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

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

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.

void 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.

InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const

Estimate the cost of a given IR user when lowered.

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.

void replaceAllUsesWith(Value *V)

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

StringRef getName() const

Return a constant reference to the value's name.

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.

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...

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...

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)

raw_ostream & dbgs()

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

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)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.