ADCE.cpp Source File (original) (raw)

52#include

53#include

54#include

56using namespace llvm;

58#define DEBUG_TYPE "adce"

60 STATISTIC(NumRemoved, "Number of instructions removed");

61 STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");

73namespace {

76struct InstInfoType {

78 bool Live = false;

81 struct BlockInfoType *Block = nullptr;

82};

85struct BlockInfoType {

87 bool Live = false;

90 bool UnconditionalBranch = false;

93 bool HasLivePhiNodes = false;

96 bool CFLive = false;

100 InstInfoType *TerminatorLiveInfo = nullptr;

101

102

104

105

107

108

109 unsigned PostOrder;

110

111 bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }

112};

113

114struct ADCEChanged {

115 bool ChangedAnything = false;

116 bool ChangedNonDebugInstr = false;

117 bool ChangedControlFlow = false;

118};

119

120class AggressiveDeadCodeElimination {

122

123

124

125 DominatorTree *DT;

126 PostDominatorTree &PDT;

127

128

129

130 MapVector<BasicBlock *, BlockInfoType> BlockInfo;

131 bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }

132

133

134 DenseMap<Instruction *, InstInfoType> InstInfo;

135 bool isLive(Instruction *I) { return InstInfo[I].Live; }

136

137

138

140

141

142 SmallPtrSet<const Metadata *, 32> AliveScopes;

143

144

145 SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators;

146

147

148

149

150 SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;

151

152

153

155

156

158

159

160 bool isInstrumentsConstant(Instruction &I);

161

162

163 void markLiveInstructions();

164

165

166 void markLive(Instruction *I);

167

168

169 void markLive(BlockInfoType &BB);

170 void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); }

171

172

173 void markPhiLive(PHINode *PN);

174

175

176 void collectLiveScopes(const DILocalScope &LS);

177 void collectLiveScopes(const DILocation &DL);

178

179

180

181

182 void markLiveBranchesFromControlDependences();

183

184

185

186 ADCEChanged removeDeadInstructions();

187

188

189

190 bool updateDeadRegions();

191

192

193

194 void computeReversePostOrder();

195

196

197 void makeUnconditional(BasicBlock *BB, BasicBlock *Target);

198

199public:

200 AggressiveDeadCodeElimination(Function &F, DominatorTree *DT,

201 PostDominatorTree &PDT)

202 : F(F), DT(DT), PDT(PDT) {}

203

204 ADCEChanged performDeadCodeElimination();

205};

206

207}

208

209ADCEChanged AggressiveDeadCodeElimination::performDeadCodeElimination() {

211 markLiveInstructions();

212 return removeDeadInstructions();

213}

214

217 return BR && BR->isUnconditional();

218}

219

220void AggressiveDeadCodeElimination::initialize() {

221 auto NumBlocks = F.size();

222

223

224

225 BlockInfo.reserve(NumBlocks);

226 size_t NumInsts = 0;

227

228

229

230 for (auto &BB : F) {

231 NumInsts += BB.size();

232 auto &Info = BlockInfo[&BB];

233 Info.BB = &BB;

234 Info.Terminator = BB.getTerminator();

236 }

237

238

239 InstInfo.reserve(NumInsts);

240 for (auto &BBInfo : BlockInfo)

241 for (Instruction &I : *BBInfo.second.BB)

242 InstInfo[&I].Block = &BBInfo.second;

243

244

245

246 for (auto &BBInfo : BlockInfo)

247 BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];

248

249

252 markLive(&I);

253

255 return;

256

258

259

260

261

262 using StatusMap = DenseMap<BasicBlock *, bool>;

263

264 class DFState : public StatusMap {

265 public:

266 std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) {

267 return StatusMap::insert(std::make_pair(BB, true));

268 }

269

270

271 void completed(BasicBlock *BB) { (*this)[BB] = false; }

272

273

274

275 bool onStack(BasicBlock *BB) {

276 auto Iter = find(BB);

277 return Iter != end() && Iter->second;

278 }

279 } State;

280

281 State.reserve(F.size());

282

283

284

287 if (isLive(Term))

288 continue;

289

291 if (State.onStack(Succ)) {

292

293 markLive(Term);

294 break;

295 }

296 }

297 }

298

299

300

301

302

304 auto *BB = PDTChild->getBlock();

305 auto &Info = BlockInfo[BB];

306

308 LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()

309 << '\n';);

310 continue;

311 }

312

313

314 for (auto *DFNode : depth_first(PDTChild))

315 markLive(BlockInfo[DFNode->getBlock()].Terminator);

316 }

317

318

319 auto *BB = &F.getEntryBlock();

320 auto &EntryInfo = BlockInfo[BB];

321 EntryInfo.Live = true;

322 if (EntryInfo.UnconditionalBranch)

323 markLive(EntryInfo.Terminator);

324

325

326 for (auto &BBInfo : BlockInfo)

327 if (!BBInfo.second.terminatorIsLive())

328 BlocksWithDeadTerminators.insert(BBInfo.second.BB);

329}

330

331bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) {

332

333 if (I.isEHPad() || I.mayHaveSideEffects()) {

334

335

336 if (isInstrumentsConstant(I))

337 return false;

338 return true;

339 }

340 if (.isTerminator())

341 return false;

343 return false;

344 return true;

345}

346

347

348

349bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) {

350

352 if (Function *Callee = CI->getCalledFunction())

355 return true;

356 return false;

357}

358

359void AggressiveDeadCodeElimination::markLiveInstructions() {

360

361 do {

362

363

364 while (!Worklist.empty()) {

365 Instruction *LiveInst = Worklist.pop_back_val();

367

368 for (Use &OI : LiveInst->operands())

370 markLive(Inst);

371

373 markPhiLive(PN);

374 }

375

376

377

378 markLiveBranchesFromControlDependences();

379

380 } while (!Worklist.empty());

381}

382

383void AggressiveDeadCodeElimination::markLive(Instruction *I) {

384 auto &Info = InstInfo[I];

385 if (Info.Live)

386 return;

387

389 Info.Live = true;

390 Worklist.push_back(I);

391

392

393 if (const DILocation *DL = I->getDebugLoc())

394 collectLiveScopes(*DL);

395

396

397 auto &BBInfo = *Info.Block;

398 if (BBInfo.Terminator == I) {

399 BlocksWithDeadTerminators.remove(BBInfo.BB);

400

401

402 if (!BBInfo.UnconditionalBranch)

403 for (auto *BB : successors(I->getParent()))

404 markLive(BB);

405 }

406 markLive(BBInfo);

407}

408

409void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {

410 if (BBInfo.Live)

411 return;

413 BBInfo.Live = true;

414 if (!BBInfo.CFLive) {

415 BBInfo.CFLive = true;

416 NewLiveBlocks.insert(BBInfo.BB);

417 }

418

419

420

421 if (BBInfo.UnconditionalBranch)

422 markLive(BBInfo.Terminator);

423}

424

425void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {

426 if (!AliveScopes.insert(&LS).second)

427 return;

428

430 return;

431

432

434}

435

436void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {

437

438

439 if (!AliveScopes.insert(&DL).second)

440 return;

441

442

443 collectLiveScopes(*DL.getScope());

444

445

446 if (const DILocation *IA = DL.getInlinedAt())

447 collectLiveScopes(*IA);

448}

449

450void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) {

452

453 if (Info.HasLivePhiNodes)

454 return;

455 Info.HasLivePhiNodes = true;

456

457

458

459

461 auto &Info = BlockInfo[PredBB];

462 if ( Info .CFLive) {

463 Info.CFLive = true;

464 NewLiveBlocks.insert(PredBB);

465 }

466 }

467}

468

469void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {

470 if (BlocksWithDeadTerminators.empty())

471 return;

472

474 dbgs() << "new live blocks:\n";

475 for (auto *BB : NewLiveBlocks)

476 dbgs() << "\t" << BB->getName() << '\n';

477 dbgs() << "dead terminator blocks:\n";

478 for (auto *BB : BlocksWithDeadTerminators)

479 dbgs() << "\t" << BB->getName() << '\n';

480 });

481

482

483

484

485

486

487

489 BlocksWithDeadTerminators);

492 IDFs.setDefiningBlocks(NewLiveBlocks);

493 IDFs.setLiveInBlocks(BWDT);

494 IDFs.calculate(IDFBlocks);

495 NewLiveBlocks.clear();

496

497

498 for (auto *BB : IDFBlocks) {

499 LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');

500 markLive(BB->getTerminator());

501 }

502}

503

504

505

506

507

508

509ADCEChanged AggressiveDeadCodeElimination::removeDeadInstructions() {

511

512 Changed.ChangedControlFlow = updateDeadRegions();

513

516

517 if (isLive(&I))

518 continue;

519

521

522 if (AliveScopes.count(DII->getDebugLoc()->getScope()))

523 continue;

524

525

526

527

528 for (Value *V : DII->location_ops()) {

530 if (isLive(II)) {

531 dbgs() << "Dropping debug info for " << *DII << "\n";

532 break;

533 }

534 }

535 }

536 }

537 }

538 });

539

540

541

542

543

545

546

547

548

550

551

553 DVR && DVR->isDbgAssign())

555 continue;

556 if (AliveScopes.count(DR.getDebugLoc()->getScope()))

557 continue;

558 I.dropOneDbgRecord(&DR);

559 }

560

561

562 if (isLive(&I))

563 continue;

564

565 Changed.ChangedNonDebugInstr = true;

566

567

568 Worklist.push_back(&I);

570 }

571

572 for (Instruction *&I : Worklist)

573 I->dropAllReferences();

574

575 for (Instruction *&I : Worklist) {

576 ++NumRemoved;

577 I->eraseFromParent();

578 }

579

580 Changed.ChangedAnything = Changed.ChangedControlFlow || !Worklist.empty();

581

583}

584

585

586bool AggressiveDeadCodeElimination::updateDeadRegions() {

588 dbgs() << "final dead terminator blocks: " << '\n';

589 for (auto *BB : BlocksWithDeadTerminators)

590 dbgs() << '\t' << BB->getName()

591 << (BlockInfo[BB].Live ? " LIVE\n" : "\n");

592 });

593

594

595 bool HavePostOrder = false;

598

599 for (auto *BB : BlocksWithDeadTerminators) {

600 auto &Info = BlockInfo[BB];

601 if (Info.UnconditionalBranch) {

602 InstInfo[Info.Terminator].Live = true;

603 continue;

604 }

605

606 if (!HavePostOrder) {

607 computeReversePostOrder();

608 HavePostOrder = true;

609 }

610

611

612

613

614 BlockInfoType *PreferredSucc = nullptr;

616 auto *Info = &BlockInfo[Succ];

617 if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)

618 PreferredSucc = Info;

619 }

620 assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&

621 "Failed to find safe successor for dead branch");

622

623

624 SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;

625 bool First = true;

627 if ( First || Succ != PreferredSucc->BB) {

628 Succ->removePredecessor(BB);

629 RemovedSuccessors.insert(Succ);

630 } else

632 }

633 makeUnconditional(BB, PreferredSucc->BB);

634

635

636 for (auto *Succ : RemovedSuccessors) {

637

638

639 if (Succ != PreferredSucc->BB) {

640 LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"

641 << BB->getName() << " -> " << Succ->getName()

642 << "\n");

643 DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});

644 }

645 }

646

647 NumBranchesRemoved += 1;

649 }

650

651 if (!DeletedEdges.empty())

652 DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)

653 .applyUpdates(DeletedEdges);

654

656}

657

658

659void AggressiveDeadCodeElimination::computeReversePostOrder() {

660

661

662

663

664

665

666

667 SmallPtrSet<BasicBlock*, 16> Visited;

668 unsigned PostOrder = 0;

669 for (auto &BB : F) {

671 continue;

673 BlockInfo[Block].PostOrder = PostOrder++;

674 }

675}

676

677void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,

678 BasicBlock *Target) {

680

681 if (const DILocation *DL = PredTerm->getDebugLoc())

682 collectLiveScopes(*DL);

683

684

687 InstInfo[PredTerm].Live = true;

688 return;

689 }

691 NumBranchesRemoved += 1;

693 auto *NewTerm = Builder.CreateBr(Target);

694 InstInfo[NewTerm].Live = true;

695 if (const DILocation *DL = PredTerm->getDebugLoc())

696 NewTerm->setDebugLoc(DL);

697

698 InstInfo.erase(PredTerm);

700}

701

702

703

704

705

706

708

709

713 AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination();

714 if ( Changed .ChangedAnything)

716

718 if ( Changed .ChangedControlFlow) {

720 if ( Changed .ChangedNonDebugInstr) {

721

722

723

724

725

727 }

728 }

731

732 return PA;

733}

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

static bool isUnconditionalBranch(Instruction *Term)

Definition ADCE.cpp:215

static cl::opt< bool > RemoveLoops("adce-remove-loops", cl::init(false), cl::Hidden)

static cl::opt< bool > RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden)

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

Analysis containing CSE Info

static bool isAlwaysLive(Instruction *I)

This file defines the DenseMap class.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

This is the interface for a simple mod/ref and alias analysis over globals.

This file defines the little GraphTraits template class that should be specialized by classes that...

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This header defines various interfaces for pass management in LLVM.

This defines the Use class.

This file implements a map that provides insertion order iteration.

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

uint64_t IntrinsicInst * II

FunctionAnalysisManager FAM

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

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

#define STATISTIC(VARNAME, DESC)

static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)

Initialize the set of available library functions based on the specified target triple.

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

Represents analyses that only rely on functions' control flow.

Analysis pass which computes a DominatorTree.

DomTreeNodeBase< NodeT > * getRootNode()

getRootNode - This returns the entry node for the CFG of the function.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI InstListType::iterator eraseFromParent()

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

LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

An analysis that produces MemorySSA for a function.

Analysis pass which computes a PostDominatorTree.

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

Mark an analysis set as preserved.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

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

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

void push_back(const T &Elt)

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void dump() const

Support for debugging, callable in GDB: V->dump()

const ParentTy * getParent() const

@ BasicBlock

Various leaf nodes.

LLVM_ABI AssignmentInstRange getAssignmentInsts(DIAssignID *ID)

Return a range of instructions (typically just one) that have ID as an attachment.

initializer< Ty > init(const Ty &Val)

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)

FunctionAddr VTableAddr Value

auto find(R &&Range, const T &Val)

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

bool succ_empty(const Instruction *I)

iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)

Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...

auto successors(const MachineBasicBlock *BB)

constexpr from_range_t from_range

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

auto reverse(ContainerTy &&C)

IDFCalculator< true > ReverseIDFCalculator

LLVM_ABI raw_ostream & dbgs()

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

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

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

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

decltype(auto) cast(const From &Val)

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

auto predecessors(const MachineBasicBlock *BB)

StringRef getInstrProfValueProfFuncName()

Return the name profile runtime entry point to do value profiling for a given site.

iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)

iterator_range< df_iterator< T > > depth_first(const T &G)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Definition ADCE.cpp:707