CallGraphSCCPass.cpp Source File (original) (raw)

36#include

37#include

38#include

39#include

41using namespace llvm;

43#define DEBUG_TYPE "cgscc-passmgr"

45namespace llvm {

48}

50 STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");

57namespace {

60public:

61 static char ID;

67 bool runOnModule(Module &M) override;

69 using ModulePass::doInitialization;

70 using ModulePass::doFinalization;

72 bool doInitialization(CallGraph &CG);

73 bool doFinalization(CallGraph &CG);

76 void getAnalysisUsage(AnalysisUsage &Info) const override {

78 Info.addRequired();

79 Info.setPreservesAll();

80 }

82 StringRef getPassName() const override { return "CallGraph Pass Manager"; }

84 PMDataManager *getAsPMDataManager() override { return this; }

85 Pass *getAsPass() override { return this; }

88 void dumpPassStructure(unsigned Offset) override {

90 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

91 Pass *P = getContainedPass(Index);

92 P->dumpPassStructure(Offset + 1);

93 dumpLastUses(P, Offset+1);

94 }

95 }

97 Pass *getContainedPass(unsigned N) {

98 assert(N < PassVector.size() && "Pass number out of range!");

99 return static_cast<Pass *>(PassVector[N]);

100 }

101

104 }

105

106private:

107 bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,

108 bool &DevirtualizedCall);

109

110 bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,

111 CallGraph &CG, bool &CallGraphUpToDate,

112 bool &DevirtualizedCall);

113 bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,

114 bool IsCheckingMode);

115};

116

117}

118

119char CGPassManager::ID = 0;

120

122 CallGraph &CG, bool &CallGraphUpToDate,

123 bool &DevirtualizedCall) {

125 PMDataManager *PM = P->getAsPMDataManager();

127

128 if (!PM) {

129 CallGraphSCCPass *CGSP = (CallGraphSCCPass *)P;

130 if (!CallGraphUpToDate) {

131 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);

132 CallGraphUpToDate = true;

133 }

134

135 {

137 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;

138 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();

140 if (EmitICRemark)

141 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);

143

144 if (EmitICRemark) {

145

146 SCCCount = M.getInstructionCount();

147

149

150 int64_t Delta =

151 static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);

152 emitInstrCountChangedRemark(P, M, Delta, InstrCount,

153 FunctionToInstrCount);

155 }

156 }

157 }

158

159

160

161#ifndef NDEBUG

163 RefreshCallGraph(CurSCC, CG, true);

164#endif

165

167 }

168

170 "Invalid CGPassManager member");

171 FPPassManager *FPP = (FPPassManager*)P;

172

173

174 for (CallGraphNode *CGN : CurSCC) {

175 if (Function *F = CGN->getFunction()) {

177 {

180 }

181 F->getContext().yield();

182 }

183 }

184

185

186

187 if (Changed && CallGraphUpToDate) {

188 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()

189 << '\n');

190 CallGraphUpToDate = false;

191 }

193}

194

195

196

197

198

199

200

201

202

203

204bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,

205 bool CheckingMode) {

206 DenseMap<Value *, CallGraphNode *> Calls;

207

208 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()

209 << " nodes:\n";

210 for (CallGraphNode *CGN

211 : CurSCC) CGN->dump(););

212

213 bool MadeChange = false;

214 bool DevirtualizedCall = false;

215

216

217 unsigned FunctionNo = 0;

219 SCCIdx != E; ++SCCIdx, ++FunctionNo) {

220 CallGraphNode *CGN = *SCCIdx;

222 if ( || F->isDeclaration()) continue;

223

224

225

226

227

228

229 unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;

230

232

234

235

236 bool WasLast = I + 1 == CGNEnd;

238

239

240

241

242 if (WasLast)

243 return true;

244

245 CGNEnd = CGN->end();

246 return false;

247 };

248

249

251

252

253 if (->first) {

254 if (CheckingMode) {

255 ++I;

256 continue;

257 }

258 if (RemoveAndCheckForDone(I))

259 break;

260 continue;

261 }

262

263

264

267

268

269

271 assert(!CheckingMode &&

272 "CallGraphSCCPass did not update the CallGraph correctly!");

273

274

275 if (->second->getFunction())

276 ++NumIndirectRemoved;

277 else

278 ++NumDirectRemoved;

279

280 if (RemoveAndCheckForDone(I))

281 break;

282 continue;

283 }

284

285 assert(!Calls.count(Call) && "Call site occurs in node multiple times");

286

289

290 if (!Callee || !(Callee->isIntrinsic()))

291 Calls.insert(std::make_pair(Call, I->second));

292 }

293 ++I;

294 }

295

296

297

298 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;

299

300 for (BasicBlock &BB : *F)

301 for (Instruction &I : BB) {

304 continue;

306 if (Callee && Callee->isIntrinsic())

307 continue;

308

309

310

311

312 if (!CheckingMode) {

315 });

316 }

317

318

319

320 DenseMap<Value *, CallGraphNode *>::iterator ExistingIt =

322 if (ExistingIt != Calls.end()) {

323 CallGraphNode *ExistingNode = ExistingIt->second;

324

325

326 Calls.erase(ExistingIt);

327

328

330 continue;

331

332

333

334

335

336

339 continue;

340

341 assert(!CheckingMode &&

342 "CallGraphSCCPass did not update the CallGraph correctly!");

343

344

345

346 CallGraphNode *CalleeNode;

349

350

352 DevirtualizedCall = true;

353 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"

354 << Callee->getName() << "'\n");

355 }

356 } else {

358 }

359

360

362 MadeChange = true;

363 continue;

364 }

365

366 assert(!CheckingMode &&

367 "CallGraphSCCPass did not update the CallGraph correctly!");

368

369

370 CallGraphNode *CalleeNode;

373 ++NumDirectAdded;

374 } else {

376 ++NumIndirectAdded;

377 }

378

380 MadeChange = true;

381 }

382

383

384

385

386

387

388

389

390

391

392

393 if (NumIndirectRemoved > NumIndirectAdded &&

394 NumDirectRemoved < NumDirectAdded)

395 DevirtualizedCall = true;

396

397

398

399

400

401 assert(Calls.empty() && "Dangling pointers found in call sites map");

402

403

404

405 if ((FunctionNo & 15) == 15)

407 }

408

410 dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";

411 for (CallGraphNode *CGN : CurSCC)

413 if (DevirtualizedCall)

414 dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";

415 } else {

416 dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";

417 });

418 (void)MadeChange;

419

420 return DevirtualizedCall;

421}

422

423

424

425

426bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,

427 bool &DevirtualizedCall) {

429

430

431

432

433

434

435

436

437 bool CallGraphUpToDate = true;

438

439

440 for (unsigned PassNo = 0, e = getNumContainedPasses();

441 PassNo != e; ++PassNo) {

442 Pass *P = getContainedPass(PassNo);

443

444

445

446 if (isPassDebuggingExecutionsOrMore()) {

447 std::string Functions;

448 #ifndef NDEBUG

449 raw_string_ostream OS(Functions);

450 ListSeparator LS;

451 for (const CallGraphNode *CGN : CurSCC) {

452 OS << LS;

454 }

455 #endif

457 }

458 dumpRequiredSet(P);

459

460 initializeAnalysisImpl(P);

461

462#ifdef EXPENSIVE_CHECKS

463 uint64_t RefHash = P->structuralHash(CG.getModule());

464#endif

465

466

467 bool LocalChanged =

468 RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);

469

471

472#ifdef EXPENSIVE_CHECKS

473 if (!LocalChanged && (RefHash != P->structuralHash(CG.getModule()))) {

474 llvm::errs() << "Pass modifies its input and doesn't report it: "

475 << P->getPassName() << "\n";

476 llvm_unreachable("Pass modifies its input and doesn't report it");

477 }

478#endif

479 if (LocalChanged)

481 dumpPreservedSet(P);

482

483 verifyPreservedAnalysis(P);

484 if (LocalChanged)

485 removeNotPreservedAnalysis(P);

486 recordAvailableAnalysis(P);

488 }

489

490

491

492 if (!CallGraphUpToDate)

493 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);

495}

496

497

498

499bool CGPassManager::runOnModule(Module &M) {

500 CallGraph &CG = getAnalysis().getCallGraph();

501 bool Changed = doInitialization(CG);

502

503

504 scc_iterator<CallGraph*> CGI = scc_begin(&CG);

505

506 CallGraphSCC CurSCC(CG, &CGI);

508

509

510 const std::vector<CallGraphNode *> &NodeVec = *CGI;

511 CurSCC.initialize(NodeVec);

512 ++CGI;

513

514

515

516

517

518

519

520

521

522

523

524

525

526 unsigned Iteration = 0;

527 bool DevirtualizedCall = false;

528 do {

530 << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration

531 << '\n');

532 DevirtualizedCall = false;

533 Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);

535

536 if (DevirtualizedCall)

537 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "

538 << Iteration

539 << " times, due to -max-devirt-iterations\n");

540

541 MaxSCCIterations.updateMax(Iteration);

542 }

543 Changed |= doFinalization(CG);

545}

546

547

548bool CGPassManager::doInitialization(CallGraph &CG) {

550 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {

551 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {

553 "Invalid CGPassManager member");

554 Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());

555 } else {

556 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);

557 }

558 }

560}

561

562

563bool CGPassManager::doFinalization(CallGraph &CG) {

565 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {

566 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {

568 "Invalid CGPassManager member");

569 Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());

570 } else {

571 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);

572 }

573 }

575}

576

577

578

579

580

581

582

584 assert(Old != New && "Should not replace node with self");

585 for (unsigned i = 0; ; ++i) {

586 assert(i != Nodes.size() && "Node not in SCC");

587 if (Nodes[i] != Old) continue;

588 if (New)

589 Nodes[i] = New;

590 else

591 Nodes.erase(Nodes.begin() + i);

592 break;

593 }

594

595

596

599}

600

604

605

606

607

608

609

612

613 while (!PMS.empty() &&

615 PMS.pop();

616

617 assert(!PMS.empty() && "Unable to handle Call Graph Pass");

618 CGPassManager *CGP;

619

621 CGP = (CGPassManager*)PMS.top();

622 else {

623

624 assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");

626

627

628 CGP = new CGPassManager();

629

630

633

634

635

638

639

640 PMS.push(CGP);

641 }

642

643 CGP->add(this);

644}

645

646

647

648

653

654

655

656

657

658namespace {

659

660

661

663 std::string Banner;

664 raw_ostream &OS;

665

666 public:

667 static char ID;

668

669 PrintCallGraphPass(const std::string &B, raw_ostream &OS)

671

672 void getAnalysisUsage(AnalysisUsage &AU) const override {

674 }

675

676 bool runOnSCC(CallGraphSCC &SCC) override {

677 bool BannerPrinted = false;

678 auto PrintBannerOnce = [&]() {

679 if (BannerPrinted)

680 return;

681 OS << Banner;

682 BannerPrinted = true;

683 };

684

687 PrintBannerOnce();

688 OS << "\n";

689 SCC.getCallGraph().getModule().print(OS, nullptr);

690 return false;

691 }

692 bool FoundFunction = false;

693 for (CallGraphNode *CGN : SCC) {

696 FoundFunction = true;

697 if (!NeedModule) {

698 PrintBannerOnce();

699 F->print(OS);

700 }

701 }

703 PrintBannerOnce();

704 OS << "\nPrinting Function\n";

705 }

706 }

707 if (NeedModule && FoundFunction) {

708 PrintBannerOnce();

709 OS << "\n";

710 SCC.getCallGraph().getModule().print(OS, nullptr);

711 }

712 return false;

713 }

714

715 StringRef getPassName() const override { return "Print CallGraph IR"; }

716 };

717

718}

719

720char PrintCallGraphPass::ID = 0;

721

723 const std::string &Banner) const {

724 return new PrintCallGraphPass(Banner, OS);

725}

726

728

730 false)

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

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

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

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Analysis containing CSE Info

This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...

static unsigned InstrCount

This file defines the DenseMap class.

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

print mir2vec MIR2Vec Vocabulary Printer Pass

Machine Check Debug Module

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

This header defines classes/functions to handle pass execution timing information with interfaces for...

This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...

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

#define STATISTIC(VARNAME, DESC)

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

void setPreservesAll()

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

Function * getCalledFunction() const

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

A node in the call graph for a module.

LLVM_ABI void print(raw_ostream &OS) const

void addCalledFunction(CallBase *Call, CallGraphNode *M)

Adds a function to the list of functions called by this one.

LLVM_ABI void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)

Replaces the edge in the node for the specified call site with a new one.

LLVM_ABI void dump() const

Print out this call graph node.

Function * getFunction() const

Returns the function that this call graph node represents.

std::vector< CallRecord >::iterator iterator

void removeCallEdge(iterator I)

Pass * createPrinterPass(raw_ostream &OS, const std::string &Banner) const override

createPrinterPass - Get a pass that prints the Module corresponding to a CallGraph.

Definition CallGraphSCCPass.cpp:722

virtual bool runOnSCC(CallGraphSCC &SCC)=0

runOnSCC - This method should be implemented by the subclass to perform whatever action is necessary ...

void getAnalysisUsage(AnalysisUsage &Info) const override

getAnalysisUsage - For this class, we declare that we require and preserve the call graph.

Definition CallGraphSCCPass.cpp:649

void assignPassManager(PMStack &PMS, PassManagerType PMT) override

Assign pass manager to manager this pass.

Definition CallGraphSCCPass.cpp:610

CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.

std::vector< CallGraphNode * >::const_iterator iterator

LLVM_ABI void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)

ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...

Definition CallGraphSCCPass.cpp:583

LLVM_ABI void DeleteNode(CallGraphNode *Old)

DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.

Definition CallGraphSCCPass.cpp:601

The ModulePass which wraps up a CallGraph and the logic to build it.

The basic data container for the call graph of a Module of IR.

LLVM_ABI CallGraphNode * getOrInsertFunction(const Function *F)

Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.

CallGraphNode * getCallsExternalNode() const

Module & getModule() const

Returns the module the call graph corresponds to.

iterator find(const_arg_type_t< KeyT > Val)

bool erase(const KeyT &Val)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

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

This pass is required by interprocedural register allocation.

bool runOnFunction(Function &F)

run - Execute all of the passes scheduled for execution.

ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...

PMDataManager provides the common place to manage the analysis data used by pass managers.

PMTopLevelManager * getTopLevelManager()

virtual PassManagerType getPassManagerType() const

PMStack - This class implements a stack data structure of PMDataManager pointers.

PMDataManager * top() const

LLVM_ABI void push(PMDataManager *PM)

PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.

void addIndirectPassManager(PMDataManager *Manager)

void schedulePass(Pass *P)

Schedule pass P for execution.

Pass interface - Implemented by all 'passes'.

Pass(PassKind K, char &pid)

This class implements an extremely fast bulk output stream that can only output to a stream.

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.

bool isAtEnd() const

Direct loop termination test which is more efficient than comparison with end().

void ReplaceNode(NodeRef Old, NodeRef New)

This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in ...

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

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.

bool forcePrintModuleIR()

decltype(auto) dyn_cast(const From &Val)

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

PassManagerType

Different types of internal pass managers.

@ PMT_CallGraphPassManager

CGPassManager.

@ PMT_FunctionPassManager

FPPassManager.

scc_iterator< T > scc_begin(const T &G)

Construct the begin iterator for a deduced graph type T.

auto dyn_cast_or_null(const Y &Val)

LLVM_ABI Timer * getPassTimer(Pass *)

Request the timer for this legacy-pass-manager's pass instance.

LLVM_ABI raw_ostream & dbgs()

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

bool isFunctionInPrintList(StringRef FunctionName)

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

void forEachCallbackFunction(const CallBase &CB, UnaryFunction Func)

Apply function Func to each CB's callback function.

cl::opt< unsigned > MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, cl::init(4))