PlaceSafepoints.cpp Source File (original) (raw)

72using namespace llvm;

74#define DEBUG_TYPE "place-safepoints"

76 STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");

77 STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");

80 "Number of loops without safepoints due to calls in loop");

82 "Number of loops without safepoints finite execution");

100

101namespace {

102

103

104class PlaceBackedgeSafepointsLegacyPass : public FunctionPass {

105public:

106 static char ID;

107

108

109

110 std::vector<Instruction *> PollLocations;

111

112

113

114 bool CallSafepointsEnabled;

115

116 PlaceBackedgeSafepointsLegacyPass(bool CallSafepoints = false)

117 : FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) {

120 }

121

122 bool runOnLoop(Loop *);

123

124 void runOnLoopAndSubLoops(Loop *L) {

125

126 for (Loop *I : *L)

127 runOnLoopAndSubLoops(I);

128 runOnLoop(L);

129 }

130

132 SE = &getAnalysis().getSE();

133 DT = &getAnalysis().getDomTree();

134 LI = &getAnalysis().getLoopInfo();

135 TLI = &getAnalysis().getTLI(F);

136 for (Loop *I : *LI) {

137 runOnLoopAndSubLoops(I);

138 }

139 return false;

140 }

141

142 void getAnalysisUsage(AnalysisUsage &AU) const override {

143 AU.addRequired();

144 AU.addRequired();

146 AU.addRequired();

147

148

150 }

151

152private:

153 ScalarEvolution *SE = nullptr;

154 DominatorTree *DT = nullptr;

155 LoopInfo *LI = nullptr;

156 TargetLibraryInfo *TLI = nullptr;

157};

158}

159

163

164char PlaceBackedgeSafepointsLegacyPass::ID = 0;

165

167 "place-backedge-safepoints-impl",

168 "Place Backedge Safepoints", false, false)

173 "place-backedge-safepoints-impl",

175

180

183

186

192

193static void

195 std::vector<CallBase *> &ParsePointsNeeded ,

197

198bool PlaceBackedgeSafepointsLegacyPass::runOnLoop(Loop *L) {

199

200

201

202

203

206 L->getLoopLatches(LoopLatches);

207 for (BasicBlock *Pred : LoopLatches) {

208 assert(L->contains(Pred));

209

210

211

212

215 LLVM_DEBUG(dbgs() << "skipping safepoint placement in finite loop\n");

216 FiniteExecution++;

217 continue;

218 }

219 if (CallSafepointsEnabled &&

221

222

223

226 << "skipping safepoint placement due to unconditional call\n");

227 CallInLoop++;

228 continue;

229 }

230 }

231

232

233

234

235

236

237

238

239

240 Instruction *Term = Pred->getTerminator();

241

242 LLVM_DEBUG(dbgs() << "[LSP] terminator instruction: " << *Term);

243

244 PollLocations.push_back(Term);

245 }

246

247 return false;

248}

249

251 if (F.isDeclaration() || F.empty()) {

252

253

254 return false;

255 }

256

258

259

260

261 return false;

262 }

263

265 return false;

266

268

269

270

271

272

274

275

276

277

278

281

283 std::vector<CallBase *> ParsePointNeeded;

284

286

287

288

289

292

294 auto *PBS = new PlaceBackedgeSafepointsLegacyPass(CanAssumeCallSafepoints);

295 FPM.add(PBS);

297

298

299

301

302 auto &PollLocations = PBS->PollLocations;

303

305 return a->getParent()->getName() < b->getParent()->getName();

306 };

307

308

309 llvm::sort(PollLocations, OrderByBBName);

310

311

312

313

314 PollLocations.erase(llvm::unique(PollLocations), PollLocations.end());

315

316

317

318 for (Instruction *Term : PollLocations) {

319

321

323

324

325

326

327

328

329

330

331

332

335 if (DT.dominates(Succ, Term->getParent()))

336 Headers.insert(Succ);

337 assert(!Headers.empty() && "poll location is not a loop latch?");

338

339

340

341

345 NumBackedgeSafepoints++;

346 }

347 } else {

348

350 NumBackedgeSafepoints++;

351 }

352 }

353 }

354

359 NumEntrySafepoints++;

360 }

361

362

363 }

364

365

366

367 for (Instruction *PollLocation : PollsNeeded) {

368 std::vector<CallBase *> RuntimeCalls;

371 }

372

374}

375

386

389 return false;

391 if (CI->isInlineAsm())

392 return false;

393 }

394

397}

398

399

400

401

402

407

408

409

410

411

412

413

414

415

416

417 assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");

418

420 while (true) {

423

424

425

426

427

428

430 return true;

431 }

432

433 if (Current == Header)

434 break;

436 }

437

438 return false;

439}

440

441

442

443

444

447

452 return true;

453

454

455

456

457 if (L->isLoopExiting(Pred)) {

458

459

464 return true;

465 }

466

467 return false;

468}

469

471 std::vector<CallInst *> &Calls,

473 std::vector<BasicBlock *> &Worklist) {

476 BBI != BBE0 && BBI != BBE1; BBI++) {

478 Calls.push_back(CI);

479

480

482 "support for invokes in poll code needed");

483

484

485

486 if (BBI->isTerminator()) {

489 if (Seen.insert(Succ).second) {

490 Worklist.push_back(Succ);

491 }

492 }

493 }

494 }

495}

496

498 std::vector<CallInst *> &Calls,

500 Calls.clear();

501 std::vector<BasicBlock *> Worklist;

502 Seen.insert(Start->getParent());

503 scanOneBB(Start, End, Calls, Seen, Worklist);

504 while (!Worklist.empty()) {

506 Worklist.pop_back();

507 scanOneBB(&*BB->begin(), End, Calls, Seen, Worklist);

508 }

509}

510

511

512

515 switch (II->getIntrinsicID()) {

516 case Intrinsic::experimental_gc_statepoint:

517 case Intrinsic::experimental_patchpoint_void:

518 case Intrinsic::experimental_patchpoint:

519

520

521 return false;

522 default:

523

524

525

526

527

528

529

530 return true;

531 }

532 }

533 return false;

534}

535

538

539

540

541

542

543

544

545

546

547

548 auto HasNextInstruction = [](Instruction *I) {

549 if (->isTerminator())

550 return true;

551

552 BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();

554 };

555

557 assert(HasNextInstruction(I) &&

558 "first check if there is a next instruction!");

559

560 if (I->isTerminator())

561 return &I->getParent()->getUniqueSuccessor()->front();

562 return &*++I->getIterator();

563 };

564

566 for (Cursor = &F.getEntryBlock().front(); HasNextInstruction(Cursor);

567 Cursor = NextInstruction(Cursor)) {

568

569

570

571

572

573

574

575

578 continue;

579 break;

580 }

581 }

582

583 assert((HasNextInstruction(Cursor) || Cursor->isTerminator()) &&

584 "either we stopped because of a call, or because of terminator");

585

586 return Cursor;

587}

588

590

594

595

596

597

599

600 if (F.hasGC()) {

601 const auto &FunctionGCName = F.getGC();

602 const StringRef StatepointExampleName("statepoint-example");

603 const StringRef CoreCLRName("coreclr");

604 return (StatepointExampleName == FunctionGCName) ||

605 (CoreCLRName == FunctionGCName);

606 } else

607 return false;

608}

609

610

611

615

616

617

618

619static void

621 std::vector<CallBase *> &ParsePointsNeeded ,

624 Module *M = InsertBefore->getModule();

625 assert(M && "must be part of a module");

626

627

628

629

630

632 assert(F && "gc.safepoint_poll function is missing");

633 assert(F->getValueType() ==

635 "gc.safepoint_poll declared with wrong type");

636 assert(->empty() && "gc.safepoint_poll must be a non-empty function");

638

639

641 bool IsBegin = false;

642 if (Before == OrigBB->begin())

643 IsBegin = true;

644 else

645 Before--;

646

647 After++;

648 assert(After != OrigBB->end() && "must have successor");

649

650

653 assert(InlineStatus && "inline must succeed");

654 (void)InlineStatus;

655

656

658

659 std::vector<CallInst *> Calls;

661

662

663

665

666

667

669 "malformed poll function");

670

672 assert(!Calls.empty() && "slow path not found for safepoint poll");

673

674

675

676

677

678 assert(ParsePointsNeeded.empty());

679 for (auto *CI : Calls) {

680

682 continue;

683

684

685

686 ParsePointsNeeded.push_back(CI);

687 }

688 assert(ParsePointsNeeded.size() <= Calls.size());

689}

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

static bool runOnFunction(Function &F, bool PostInlining)

Module.h This file contains the declarations for the Module class.

uint64_t IntrinsicInst * II

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

static void InsertSafepointPoll(BasicBlock::iterator InsertBefore, std::vector< CallBase * > &ParsePointsNeeded, const TargetLibraryInfo &TLI)

Definition PlaceSafepoints.cpp:620

const char GCSafepointPollName[]

Definition PlaceSafepoints.cpp:589

static cl::opt< bool > AllBackedges("spp-all-backedges", cl::Hidden, cl::init(false))

static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE, BasicBlock *Pred)

Returns true if this loop is known to terminate in a finite number of iterations.

Definition PlaceSafepoints.cpp:445

static bool enableCallSafepoints(Function &F)

Definition PlaceSafepoints.cpp:614

static bool enableEntrySafepoints(Function &F)

Definition PlaceSafepoints.cpp:612

static cl::opt< bool > NoEntry("spp-no-entry", cl::Hidden, cl::init(false))

static bool isGCSafepointPoll(Function &F)

Definition PlaceSafepoints.cpp:591

static bool shouldRewriteFunction(Function &F)

Returns true if this function should be rewritten to include safepoint polls and parseable call sites...

Definition PlaceSafepoints.cpp:598

static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI)

Definition PlaceSafepoints.cpp:387

static void scanInlinedCode(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen)

Definition PlaceSafepoints.cpp:497

static Instruction * findLocationForEntrySafepoint(Function &F, DominatorTree &DT)

Definition PlaceSafepoints.cpp:536

static cl::opt< bool > SplitBackedge("spp-split-backedge", cl::Hidden, cl::init(false))

place backedge safepoints Place Backedge static false bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header, BasicBlock *Pred, DominatorTree &DT, const TargetLibraryInfo &TLI)

Returns true if this loop is known to contain a call safepoint which must unconditionally execute on ...

Definition PlaceSafepoints.cpp:403

static bool doesNotRequireEntrySafepointBefore(CallBase *Call)

Returns true if an entry safepoint is not required before this callsite in the caller function.

Definition PlaceSafepoints.cpp:513

static cl::opt< bool > NoCall("spp-no-call", cl::Hidden, cl::init(false))

static cl::opt< bool > NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false))

static bool enableBackedgeSafepoints(Function &F)

Definition PlaceSafepoints.cpp:613

static cl::opt< int > CountedLoopTripWidth("spp-counted-loop-trip-width", cl::Hidden, cl::init(32))

How narrow does the trip count of a loop have to be to have to be considered "counted"?

static void scanOneBB(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen, std::vector< BasicBlock * > &Worklist)

Definition PlaceSafepoints.cpp:470

This file implements a set that has insertion order iteration characteristics.

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

#define STATISTIC(VARNAME, DESC)

bool isIntN(unsigned N) const

Check if this APInt has an N-bits unsigned integer value.

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

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

AnalysisUsage & addRequired()

void setPreservesAll()

Set by analyses that do not transform their input at all.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI const BasicBlock * getUniquePredecessor() const

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

InstListType::iterator iterator

Instruction iterators...

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

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

This class represents a function call, abstracting a target machine's calling convention.

static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

LLVM_ABI APInt getUnsignedMax() const

Return the largest unsigned value contained in the ConstantRange.

Implements a dense probed hash-table based set.

DomTreeNodeBase * getIDom() const

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

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

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

Legacy analysis pass which computes a DominatorTree.

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

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

FunctionPass class - This class is used to implement most global optimizations.

static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)

This static method is the primary way of constructing a FunctionType.

This class captures the data input to the InlineFunction call, and records the auxiliary results prod...

SmallVector< AllocaInst *, 4 > StaticAllocas

InlineFunction fills this in with all static allocas that get copied into the caller.

A wrapper class for inspecting calls to intrinsic functions.

The legacy pass manager's analysis pass to compute loop information.

Represents a single loop in the control flow graph.

A Module instance is used to store all the information related to an LLVM module.

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition PlaceSafepoints.cpp:376

bool runImpl(Function &F, const TargetLibraryInfo &TLI)

Definition PlaceSafepoints.cpp:250

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

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

This class represents an analyzed expression in the program.

The main scalar evolution driver.

const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)

When successful, this returns a SCEVConstant that is greater than or equal to (i.e.

ConstantRange getUnsignedRange(const SCEV *S)

Determine the unsigned range for a particular SCEV.

LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)

Return the number of times the backedge executes before the given exit would be taken; if not exactly...

A vector that has set insertion semantics.

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

Analysis pass providing the TargetLibraryInfo.

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

static LLVM_ABI Type * getVoidTy(LLVMContext &C)

std::pair< iterator, bool > insert(const ValueT &V)

const ParentTy * getParent() const

FunctionPassManager manages FunctionPasses.

bool run(Function &F)

run - Execute all of the passes scheduled for execution.

void add(Pass *P) override

Add a pass to the queue of passes to run.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI InlineResult InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, bool MergeAttributes=false, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true, Function *ForwardVarArgsTo=nullptr, OptimizationRemarkEmitter *ORE=nullptr)

This function inlines the called function into the basic block of the caller.

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

LLVM_ABI void initializePlaceBackedgeSafepointsLegacyPassPass(PassRegistry &)

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

auto unique(Range &&R, Predicate P)

void sort(IteratorTy Start, IteratorTy End)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")

Split the edge connecting the specified blocks, and return the newly created basic block between From...

LLVM_ABI bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Remove all blocks that can not be reached from the function's entry.

LLVM_ABI bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)

Return true if this call calls a gc leaf function.

LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)

Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...

Implement std::hash so that hash_code can be used in STL containers.