Movatterモバイル変換

Go to the documentation of this file.

1//===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file implements the DomTreeUpdater class, which provides a uniform way

10// to update dominator tree related data structures.

11//

12//===----------------------------------------------------------------------===//

14#include "llvm/Analysis/DomTreeUpdater.h"

15#include "llvm/Analysis/GenericDomTreeUpdaterImpl.h"

16#include "llvm/Analysis/PostDominators.h"

17#include "llvm/IR/Constants.h"

18#include "llvm/IR/Instructions.h"

19#include "llvm/Support/GenericDomTree.h"

20#include <functional>

22namespacellvm {

24templateclassGenericDomTreeUpdater<DomTreeUpdater, DominatorTree,

25 PostDominatorTree>;

27templatevoid

28GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,

29 PostDominatorTree>::recalculate(Function &F);

31templatevoid

32GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>::

33 applyUpdatesImpl</*IsForward=*/true>();

34templatevoid

35GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>::

36 applyUpdatesImpl</*IsForward=*/false>();

38bool DomTreeUpdater::forceFlushDeletedBB() {

39if (DeletedBBs.empty())

40returnfalse;

42for (auto *BB :DeletedBBs) {

43// After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,

44// validateDeleteBB() removes all instructions of DelBB and adds an

45// UnreachableInst as its terminator. So we check whether the BasicBlock to

46// delete only has an UnreachableInst inside.

47assert(BB->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) &&

48"DelBB has been modified while awaiting deletion.");

49eraseDelBBNode(BB);

50 BB->eraseFromParent();

51 }

52DeletedBBs.clear();

53 Callbacks.clear();

54returntrue;

55}

57// The DT and PDT require the nodes related to updates

58// are not deleted when update functions are called.

59// So BasicBlock deletions must be pended when the

60// UpdateStrategy is Lazy. When the UpdateStrategy is

61// Eager, the BasicBlock will be deleted immediately.

62voidDomTreeUpdater::deleteBB(BasicBlock *DelBB) {

63 validateDeleteBB(DelBB);

64if (Strategy == UpdateStrategy::Lazy) {

65DeletedBBs.insert(DelBB);

66return;

67 }

69eraseDelBBNode(DelBB);

70 DelBB->eraseFromParent();

71}

73voidDomTreeUpdater::callbackDeleteBB(

74BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {

75 validateDeleteBB(DelBB);

76if (Strategy == UpdateStrategy::Lazy) {

77 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));

78DeletedBBs.insert(DelBB);

79return;

80 }

82eraseDelBBNode(DelBB);

83 DelBB->removeFromParent();

84 Callback(DelBB);

85delete DelBB;

86}

88void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {

89assert(DelBB &&"Invalid push_back of nullptr DelBB.");

90assert(pred_empty(DelBB) &&"DelBB has one or more predecessors.");

91// DelBB is unreachable and all its instructions are dead.

92while (!DelBB->empty()) {

93Instruction &I = DelBB->back();

94// Replace used instructions with an arbitrary value (poison).

95if (!I.use_empty())

96I.replaceAllUsesWith(PoisonValue::get(I.getType()));

97 DelBB->back().eraseFromParent();

98 }

99// Make sure DelBB has a valid terminator instruction. As long as DelBB is a

100// Child of Function F it must contain valid IR.

101new UnreachableInst(DelBB->getContext(), DelBB);

102}

103

104LLVM_DUMP_METHOD

105voidDomTreeUpdater::dump() const{

106Base::dump();

107#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

108raw_ostream &OS =dbgs();

109OS <<"Pending Callbacks:\n";

110intIndex = 0;

111for (constauto &BB : Callbacks) {

112OS <<" " <<Index <<" : ";

113 ++Index;

114if (BB->hasName())

115OS << BB->getName() <<"(";

116else

117OS <<"(no_name)(";

118OS << BB <<")\n";

119 }

120#endif

121}

122

123}// namespace llvm

LLVM_DUMP_METHOD

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Definition:Compiler.h:622

Constants.h

This file contains the declarations for the subclasses of Constant, which represent the different fla...

DomTreeUpdater.h

Index

uint32_t Index

Definition:ELFObjHandler.cpp:83

GenericDomTreeUpdaterImpl.h

GenericDomTree.h

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

Instructions.h

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

PostDominators.h

assert

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

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::BasicBlock::empty

bool empty() const

Definition:BasicBlock.h:473

llvm::BasicBlock::removeFromParent

void removeFromParent()

Unlink 'this' from the containing function, but do not delete it.

Definition:BasicBlock.cpp:275

llvm::BasicBlock::eraseFromParent

SymbolTableList< BasicBlock >::iterator eraseFromParent()

Unlink 'this' from the containing function and delete it.

Definition:BasicBlock.cpp:279

llvm::BasicBlock::getContext

LLVMContext & getContext() const

Get the context in which this basic block lives.

Definition:BasicBlock.cpp:168

llvm::BasicBlock::back

const Instruction & back() const

Definition:BasicBlock.h:476

llvm::DomTreeUpdater::dump

LLVM_DUMP_METHOD void dump() const

Debug method to help view the internal state of this class.

Definition:DomTreeUpdater.cpp:105

llvm::DomTreeUpdater::callbackDeleteBB

void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)

Delete DelBB.

Definition:DomTreeUpdater.cpp:73

llvm::DomTreeUpdater::deleteBB

void deleteBB(BasicBlock *DelBB)

Delete DelBB.

Definition:DomTreeUpdater.cpp:62

llvm::GenericDomTreeUpdater< DomTreeUpdater, DominatorTree, PostDominatorTree >::DeletedBBs

SmallPtrSet< BasicBlockT *, 8 > DeletedBBs

Definition:GenericDomTreeUpdater.h:238

llvm::GenericDomTreeUpdater< DomTreeUpdater, DominatorTree, PostDominatorTree >::eraseDelBBNode

void eraseDelBBNode(BasicBlockT *DelBB)

Erase Basic Block node before it is unlinked from Function in the DomTree and PostDomTree.

Definition:GenericDomTreeUpdaterImpl.h:331

llvm::GenericDomTreeUpdater< DomTreeUpdater, DominatorTree, PostDominatorTree >::Strategy

const UpdateStrategy Strategy

Definition:GenericDomTreeUpdater.h:237

llvm::GenericDomTreeUpdater< DomTreeUpdater, DominatorTree, PostDominatorTree >::dump

LLVM_DUMP_METHOD void dump() const

Debug method to help view the internal state of this class.

Definition:GenericDomTreeUpdaterImpl.h:171

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::eraseFromParent

InstListType::iterator eraseFromParent()

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

Definition:Instruction.cpp:94

llvm::PoisonValue::get

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Definition:Constants.cpp:1878

llvm::SmallPtrSetImplBase::clear

void clear()

Definition:SmallPtrSet.h:97

llvm::SmallPtrSetImplBase::empty

bool empty() const

Definition:SmallPtrSet.h:93

llvm::SmallPtrSetImpl::insert

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

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

Definition:SmallPtrSet.h:384

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::pred_empty

bool pred_empty(const BasicBlock *BB)

Definition:CFG.h:118