CallGraphSCCPass.cpp Source File (original) (raw)

37#include

38#include

39#include

40#include

42using namespace llvm;

44#define DEBUG_TYPE "cgscc-passmgr"

46namespace llvm {

49}

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

58namespace {

61public:

62 static char ID;

70 using ModulePass::doInitialization;

71 using ModulePass::doFinalization;

80 Info.setPreservesAll();

81 }

92 Pass *P = getContainedPass(Index);

93 P->dumpPassStructure(Offset + 1);

95 }

96 }

98 Pass *getContainedPass(unsigned N) {

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

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

101 }

102

105 }

106

107private:

109 bool &DevirtualizedCall);

110

112 CallGraph &CG, bool &CallGraphUpToDate,

113 bool &DevirtualizedCall);

115 bool IsCheckingMode);

116};

117

118}

119

120char CGPassManager::ID = 0;

121

123 CallGraph &CG, bool &CallGraphUpToDate,

124 bool &DevirtualizedCall) {

125 bool Changed = false;

128

129 if (!PM) {

131 if (!CallGraphUpToDate) {

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

133 CallGraphUpToDate = true;

134 }

135

136 {

139 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();

141 if (EmitICRemark)

142 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);

143 Changed = CGSP->runOnSCC(CurSCC);

144

145 if (EmitICRemark) {

146

147 SCCCount = M.getInstructionCount();

148

150

151 int64_t Delta =

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

153 emitInstrCountChangedRemark(P, M, Delta, InstrCount,

154 FunctionToInstrCount);

156 }

157 }

158 }

159

160

161

162#ifndef NDEBUG

163 if (Changed)

164 RefreshCallGraph(CurSCC, CG, true);

165#endif

166

167 return Changed;

168 }

169

171 "Invalid CGPassManager member");

173

174

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

178 {

181 }

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

183 }

184 }

185

186

187

188 if (Changed && CallGraphUpToDate) {

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

190 << '\n');

191 CallGraphUpToDate = false;

192 }

193 return Changed;

194}

195

196

197

198

199

200

201

202

203

204

206 bool CheckingMode) {

208

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

210 << " nodes:\n";

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

213

214 bool MadeChange = false;

215 bool DevirtualizedCall = false;

216

217

218 unsigned FunctionNo = 0;

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

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

224

225

226

227

228

229

230 unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;

231

233

235

236

237 bool WasLast = I + 1 == CGNEnd;

239

240

241

242

243 if (WasLast)

244 return true;

245

246 CGNEnd = CGN->end();

247 return false;

248 };

249

250

252

253

254 if (->first) {

255 if (CheckingMode) {

256 ++I;

257 continue;

258 }

259 if (RemoveAndCheckForDone(I))

260 break;

261 continue;

262 }

263

264

265

266 auto *Call = dyn_cast_or_null(*I->first);

267 if (!Call ||

268

269

270

271 Calls.count(Call)) {

272 assert(!CheckingMode &&

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

274

275

276 if (->second->getFunction())

277 ++NumIndirectRemoved;

278 else

279 ++NumDirectRemoved;

280

281 if (RemoveAndCheckForDone(I))

282 break;

283 continue;

284 }

285

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

287

288 if (Call) {

290

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

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

293 }

294 ++I;

295 }

296

297

298

299 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;

300

303 auto *Call = dyn_cast(&I);

304 if (!Call)

305 continue;

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

308 continue;

309

310

311

312

313 if (!CheckingMode) {

316 });

317 }

318

319

320

322 Calls.find(Call);

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

324 CallGraphNode *ExistingNode = ExistingIt->second;

325

326

327 Calls.erase(ExistingIt);

328

329

330 if (ExistingNode->getFunction() == Call->getCalledFunction())

331 continue;

332

333

334

335

336

337

338 if (CheckingMode && Call->getCalledFunction() &&

340 continue;

341

342 assert(!CheckingMode &&

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

344

345

346

348 if (Function *Callee = Call->getCalledFunction()) {

350

351

353 DevirtualizedCall = true;

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

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

356 }

357 } else {

359 }

360

361

363 MadeChange = true;

364 continue;

365 }

366

367 assert(!CheckingMode &&

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

369

370

372 if (Function *Callee = Call->getCalledFunction()) {

374 ++NumDirectAdded;

375 } else {

377 ++NumIndirectAdded;

378 }

379

381 MadeChange = true;

382 }

383

384

385

386

387

388

389

390

391

392

393

394 if (NumIndirectRemoved > NumIndirectAdded &&

395 NumDirectRemoved < NumDirectAdded)

396 DevirtualizedCall = true;

397

398

399

400

401

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

403

404

405

406 if ((FunctionNo & 15) == 15)

408 }

409

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

414 if (DevirtualizedCall)

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

416 } else {

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

418 });

419 (void)MadeChange;

420

421 return DevirtualizedCall;

422}

423

424

425

426

428 bool &DevirtualizedCall) {

429 bool Changed = false;

430

431

432

433

434

435

436

437

438 bool CallGraphUpToDate = true;

439

440

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

442 PassNo != e; ++PassNo) {

443 Pass *P = getContainedPass(PassNo);

444

445

446

447 if (isPassDebuggingExecutionsOrMore()) {

448 std::string Functions;

449 #ifndef NDEBUG

451 ListSeparator LS;

455 }

456 #endif

458 }

459 dumpRequiredSet(P);

460

461 initializeAnalysisImpl(P);

462

463#ifdef EXPENSIVE_CHECKS

465#endif

466

467

468 bool LocalChanged =

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

470

471 Changed |= LocalChanged;

472

473#ifdef EXPENSIVE_CHECKS

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

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

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

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

478 }

479#endif

480 if (LocalChanged)

482 dumpPreservedSet(P);

483

484 verifyPreservedAnalysis(P);

485 if (LocalChanged)

486 removeNotPreservedAnalysis(P);

487 recordAvailableAnalysis(P);

489 }

490

491

492

493 if (!CallGraphUpToDate)

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

495 return Changed;

496}

497

498

499

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

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

502 bool Changed = doInitialization(CG);

503

504

506

509

510

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

512 CurSCC.initialize(NodeVec);

513 ++CGI;

514

515

516

517

518

519

520

521

522

523

524

525

526

527 unsigned Iteration = 0;

528 bool DevirtualizedCall = false;

529 do {

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

532 << '\n');

533 DevirtualizedCall = false;

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

536

537 if (DevirtualizedCall)

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

539 << Iteration

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

541

542 MaxSCCIterations.updateMax(Iteration);

543 }

544 Changed |= doFinalization(CG);

545 return Changed;

546}

547

548

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

550 bool Changed = false;

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

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

554 "Invalid CGPassManager member");

556 } else {

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

558 }

559 }

560 return Changed;

561}

562

563

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

565 bool Changed = false;

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

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

569 "Invalid CGPassManager member");

571 } else {

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

573 }

574 }

575 return Changed;

576}

577

578

579

580

581

582

583

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

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

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

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

589 if (New)

590 Nodes[i] = New;

591 else

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

593 break;

594 }

595

596

597

600}

601

604}

605

606

607

608

609

610

613

614 while (!PMS.empty() &&

616 PMS.pop();

617

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

619 CGPassManager *CGP;

620

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

623 else {

624

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

627

628

629 CGP = new CGPassManager();

630

631

634

635

636

639

640

641 PMS.push(CGP);

642 }

643

644 CGP->add(this);

645}

646

647

648

649

653}

654

655

656

657

658

659namespace {

660

661

662

664 std::string Banner;

666

667 public:

668 static char ID;

669

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

672

673 void getAnalysisUsage(AnalysisUsage &AU) const override {

675 }

676

678 bool BannerPrinted = false;

679 auto PrintBannerOnce = [&]() {

680 if (BannerPrinted)

681 return;

682 OS << Banner;

683 BannerPrinted = true;

684 };

685

688 PrintBannerOnce();

689 OS << "\n";

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

691 return false;

692 }

693 bool FoundFunction = false;

697 FoundFunction = true;

698 if (!NeedModule) {

699 PrintBannerOnce();

700 F->print(OS);

701 }

702 }

704 PrintBannerOnce();

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

706 }

707 }

708 if (NeedModule && FoundFunction) {

709 PrintBannerOnce();

710 OS << "\n";

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

712 }

713 return false;

714 }

715

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

717 };

718

719}

720

721char PrintCallGraphPass::ID = 0;

722

724 const std::string &Banner) const {

725 return new PrintCallGraphPass(Banner, OS);

726}

727

729 std::string Desc = "SCC (";

730 ListSeparator LS;

734 if (F)

735 Desc += F->getName();

736 else

737 Desc += "<>";

738 }

741}

742

745 SCC.getCallGraph().getModule().getContext().getOptPassGate();

748}

749

751

753 false)

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

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

Analysis containing CSE Info

static std::string getDescription(const CallGraphSCC &SCC)

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.

This file declares the interface for bisecting optimizations.

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

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)

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.

LLVM Basic Block Representation.

A node in the call graph for a module.

void print(raw_ostream &OS) const

void addCalledFunction(CallBase *Call, CallGraphNode *M)

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

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

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

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.

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.

bool skipSCC(CallGraphSCC &SCC) const

Optional passes call this function to check whether the pass should be skipped.

void assignPassManager(PMStack &PMS, PassManagerType PMT) override

Assign pass manager to manager this pass.

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

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

void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)

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

void DeleteNode(CallGraphNode *Old)

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

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.

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.

FPPassManager manages BBPassManagers and FunctionPasses.

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

virtual bool runOnModule(Module &M)=0

runOnModule - Virtual method overriden by subclasses to process the module being operated on.

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

Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...

virtual bool isEnabled() const

isEnabled() should return true before calling shouldRunPass().

virtual bool shouldRunPass(const StringRef PassName, StringRef IRDescription)

IRDescription is a textual description of the IR unit the pass is running over.

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

void dumpLastUses(Pass *P, unsigned Offset) const

virtual Pass * getAsPass()=0

PMTopLevelManager * getTopLevelManager()

unsigned getNumContainedPasses() const

virtual PassManagerType getPassManagerType() const

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

PMDataManager * top() const

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

virtual PMDataManager * getAsPMDataManager()

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

virtual bool doInitialization(Module &)

doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...

virtual bool doFinalization(Module &)

doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...

virtual void dumpPassStructure(unsigned Offset=0)

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...

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

The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...

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.

A raw_ostream that writes to an std::string.

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()

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.

Timer * getPassTimer(Pass *)

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

raw_ostream & dbgs()

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

bool isFunctionInPrintList(StringRef FunctionName)

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

Description of the encoding of one expression Op.