UnifyLoopExits.cpp Source File (original) (raw)

31#define DEBUG_TYPE "unify-loop-exits"

33using namespace llvm;

37 cl::desc("Set the maximum number of outgoing blocks for using a boolean "

38 "value to record the exiting block in the ControlFlowHub."));

40namespace {

41struct UnifyLoopExitsLegacyPass : public FunctionPass {

42 static char ID;

45 }

52 }

55};

56}

58char UnifyLoopExitsLegacyPass::ID = 0;

61 return new UnifyLoopExitsLegacyPass();

62}

65 "Fixup each natural loop to have a single exit block",

66 false , false )

70 "Fixup each natural loop to have a single exit block",

71 false , false )

94 IIMap ExternalUsers;

95 for (auto *BB : L->blocks()) {

96 for (auto &I : *BB) {

97 for (auto &U : I.uses()) {

98 auto UserInst = cast(U.getUser());

99 auto UserBlock = UserInst->getParent();

100 if (UserBlock == LoopExitBlock)

101 continue;

102 if (L->contains(UserBlock))

103 continue;

104 LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("

105 << BB->getName() << ")"

106 << ": " << UserInst->getName() << "("

107 << UserBlock->getName() << ")"

108 << "\n");

109 ExternalUsers[&I].push_back(UserInst);

110 }

111 }

112 }

113

114 for (const auto &II : ExternalUsers) {

115

116

117

118

119 auto Def = II.first;

120 LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");

121 auto NewPhi =

123 Def->getName() + ".moved", LoopExitBlock->begin());

125 LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");

126 if (Def->getParent() == In || DT.dominates(Def, In)) {

128 NewPhi->addIncoming(Def, In);

129 } else {

132 }

133 }

134

136 for (auto *U : II.second) {

138 U->replaceUsesOfWith(Def, NewPhi);

139 }

141 }

142}

143

145

146

147

148

149

151 L->getExitingBlocks(ExitingBlocks);

152

153

155 for (auto *BB : ExitingBlocks) {

156 auto *Branch = cast(BB->getTerminator());

157 BasicBlock *Succ0 = Branch->getSuccessor(0);

158 Succ0 = L->contains(Succ0) ? nullptr : Succ0;

159

161 Branch->isUnconditional() ? nullptr : Branch->getSuccessor(1);

162 Succ1 = L->contains(Succ1) ? nullptr : Succ1;

163 CHub.addBranch(BB, Succ0, Succ1);

164

165 LLVM_DEBUG(dbgs() << "Added exiting branch: " << BB->getName() << " -> {"

166 << (Succ0 ? Succ0->getName() : "") << ", "

167 << (Succ1 ? Succ1->getName() : "") << "}\n");

168 }

169

171 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

174

175 restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);

176

177#if defined(EXPENSIVE_CHECKS)

178 assert(DT.verify(DominatorTree::VerificationLevel::Full));

179#else

180 assert(DT.verify(DominatorTree::VerificationLevel::Fast));

181#endif

182 L->verifyLoop();

183

184

185

186 if (auto ParentLoop = L->getParentLoop()) {

187 for (auto *G : GuardBlocks) {

188 ParentLoop->addBasicBlockToLoop(G, LI);

189 }

190 ParentLoop->verifyLoop();

191 }

192

193#if defined(EXPENSIVE_CHECKS)

195#endif

196

197 return true;

198}

199

201

202 bool Changed = false;

204 for (auto *L : Loops) {

207 }

208 return Changed;

209}

210

211bool UnifyLoopExitsLegacyPass::runOnFunction(Function &F) {

212 LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()

213 << "\n");

214 auto &LI = getAnalysis().getLoopInfo();

215 auto &DT = getAnalysis().getDomTree();

216

218

220}

221

222namespace llvm {

223

226 LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()

227 << "\n");

230

236 return PA;

237}

238}

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

static bool runImpl(Function &F, const TargetLowering &TLI)

This file implements a map that provides insertion order iteration.

uint64_t IntrinsicInst * II

PowerPC TLS Dynamic Call Fixup

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

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

unify loop Fixup each natural loop to have a single exit block

static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L)

unify loop Fixup each natural loop to have a single exit static false void restoreSSA(const DominatorTree &DT, const Loop *L, SmallVectorImpl< BasicBlock * > &Incoming, BasicBlock *LoopExitBlock)

static cl::opt< unsigned > MaxBooleansInControlFlowHub("max-booleans-in-control-flow-hub", cl::init(32), cl::Hidden, cl::desc("Set the maximum number of outgoing blocks for using a boolean " "value to record the exiting block in the ControlFlowHub."))

static bool runImpl(LoopInfo &LI, DominatorTree &DT)

A container for analyses that lazily runs them and caches their results.

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

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

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.

LLVM Basic Block Representation.

Analysis pass which computes a DominatorTree.

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

Legacy analysis pass which computes a DominatorTree.

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

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.

virtual bool runOnFunction(Function &F)=0

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Analysis pass that exposes the LoopInfo for a function.

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

SmallVector< LoopT *, 4 > getLoopsInPreorder() const

Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...

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

Represents a single loop in the control flow graph.

This class implements a map that also provides access to all stored values in a deterministic order.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static PassRegistry * getPassRegistry()

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

virtual void getAnalysisUsage(AnalysisUsage &) const

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

static PoisonValue * get(Type *T)

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

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.

void preserve()

Mark an analysis as preserved.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

StringRef getName() const

Return a constant reference to the value's name.

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 hasOnlySimpleTerminator(const Function &F)

void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)

raw_ostream & dbgs()

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

FunctionPass * createUnifyLoopExitsPass()

Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such that the control flow from ...

BasicBlock * finalize(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)

void addBranch(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1)

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...