UnifyLoopExits.cpp Source File (original) (raw)

35#define DEBUG_TYPE "unify-loop-exits"

37using namespace llvm;

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

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

44namespace {

45struct UnifyLoopExitsLegacyPass : public FunctionPass {

46 static char ID;

49 }

51 void getAnalysisUsage(AnalysisUsage &AU) const override {

53 AU.addRequired();

56 }

59};

60}

62char UnifyLoopExitsLegacyPass::ID = 0;

65 return new UnifyLoopExitsLegacyPass();

66}

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

70 false , false )

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

75 false , false )

98 IIMap ExternalUsers;

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

100 for (auto &I : *BB) {

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

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

103 auto UserBlock = UserInst->getParent();

104 if (UserBlock == LoopExitBlock)

105 continue;

106 if (L->contains(UserBlock))

107 continue;

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

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

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

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

112 << "\n");

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

114 }

115 }

116 }

117

118 for (const auto &II : ExternalUsers) {

119

120

121

122

123 auto Def = II.first;

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

125 auto NewPhi =

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

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

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

132 NewPhi->addIncoming(Def, In);

133 } else {

136 }

137 }

138

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

142 U->replaceUsesOfWith(Def, NewPhi);

143 }

145 }

146}

147

149

150

151

152

153

155 L->getExitingBlocks(ExitingBlocks);

156

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

159

162

163 for (unsigned I = 0; I < ExitingBlocks.size(); ++I) {

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

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

168

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

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

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

173

177 << '\n');

179 for (unsigned J = 0; J < CallBr->getNumSuccessors(); ++J) {

180 BasicBlock *Succ = CallBr->getSuccessor(J);

181 if (L->contains(Succ))

182 continue;

183 bool UpdatedLI = false;

185 SplitCallBrEdge(BB, Succ, J, &DTU, nullptr, &LI, &UpdatedLI);

186

187

188

190

191

192 if (!UpdatedLI)

193 CallBrTargetBlocksToFix.push_back(NewSucc);

194

195

196

197

198

199 ExitingBlocks[I] = NewSucc;

204 }

205 } else {

207 }

208 }

209

212 bool ChangedCFG;

213 std::tie(LoopExitBlock, ChangedCFG) = CHub.finalize(

216 if (!ChangedCFG)

217 return false;

218

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

220

221#if defined(EXPENSIVE_CHECKS)

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

223#else

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

225#endif

226 L->verifyLoop();

227

228

229

230

231

232

233

234

235

236 if (auto *ParentLoop = L->getParentLoop()) {

237 for (auto *G : GuardBlocks) {

238 ParentLoop->addBasicBlockToLoop(G, LI);

239 }

240 for (auto *C : CallBrTargetBlocksToFix) {

241 ParentLoop->addBasicBlockToLoop(C, LI);

242 }

243 ParentLoop->verifyLoop();

244 }

245

246#if defined(EXPENSIVE_CHECKS)

248#endif

249

250 return true;

251}

252

254

257 for (auto *L : Loops) {

260 }

262}

263

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

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

266 << "\n");

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

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

269

271}

272

273namespace llvm {

274

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

278 << "\n");

281

287 return PA;

288}

289}

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

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

static bool runOnFunction(Function &F, bool PostInlining)

static bool runImpl(Function &F, const TargetLowering &TLI, const LibcallLoweringInfo &Libcalls, AssumptionCache *AC)

This file implements a map that provides insertion order iteration.

uint64_t IntrinsicInst * II

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

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

Definition UnifyLoopExits.cpp:148

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)

Definition UnifyLoopExits.cpp:93

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)

Definition UnifyLoopExits.cpp:253

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

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

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

LLVM Basic Block Representation.

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

Conditional or Unconditional Branch instruction.

CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...

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.

FunctionPass class - This class is used to implement most global optimizations.

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 LLVM_ABI PassRegistry * getPassRegistry()

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

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

PreservedAnalyses & preserve()

Mark an analysis as preserved.

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

void push_back(const T &Elt)

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition UnifyLoopExits.cpp:275

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

@ C

The default llvm calling convention, compatible with C.

initializer< Ty > init(const Ty &Val)

NodeAddr< DefNode * > Def

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &)

LLVM_ABI BasicBlock * SplitCallBrEdge(BasicBlock *CallBrBlock, BasicBlock *Succ, unsigned SuccIdx, DomTreeUpdater *DTU=nullptr, CycleInfo *CI=nullptr, LoopInfo *LI=nullptr, bool *UpdatedLI=nullptr)

Create a new intermediate target block for a callbr edge.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI FunctionPass * createUnifyLoopExitsPass()

Definition UnifyLoopExits.cpp:64

LLVM_ABI Printable printBasicBlock(const BasicBlock *BB)

Print BasicBlock BB as an operand or print "" if BB is a nullptr.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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

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

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

Return the unified loop exit block and a flag indicating if the CFG was changed at all.

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