1//===- ControlFlowUtils.cpp - Control Flow Utilities -----------------------==//
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// Utilities to manipulate the CFG and restore SSA for the new control flow.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Utils/ControlFlowUtils.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/Analysis/DomTreeUpdater.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/Instructions.h"
19#include "llvm/IR/ProfDataUtils.h"
20#include "llvm/IR/ValueHandle.h"
21#include "llvm/Transforms/Utils/Local.h"
22
23#define DEBUG_TYPE "control-flow-hub"
24
25using namespace llvm;
26
27using BBPredicates = DenseMap<BasicBlock *, Instruction *>;
28using EdgeDescriptor = ControlFlowHub::BranchDescriptor;
29
30// Redirects the terminator of the incoming block to the first guard block in
31// the hub. Returns the branch condition from `BB` if it exits.
32// - If only one of Succ0 or Succ1 is not null, the corresponding branch
33// successor is redirected to the FirstGuardBlock.
34// - Else both are not null, and branch is replaced with an unconditional
35// branch to the FirstGuardBlock.
36static Value *redirectToHub(BasicBlock *BB, BasicBlock *Succ0,
37 BasicBlock *Succ1, BasicBlock *FirstGuardBlock) {
38 if (auto *Branch = dyn_cast<UncondBrInst>(Val: BB->getTerminator())) {
39 assert(Succ0 == Branch->getSuccessor(0));
40 assert(!Succ1);
41 Branch->setSuccessor(FirstGuardBlock);
42 return nullptr;
43 }
44
45 auto *Branch = cast<CondBrInst>(Val: BB->getTerminator());
46 auto *Condition = Branch->getCondition();
47
48 assert(Succ0 || Succ1);
49 assert(!Succ1 || Succ1 == Branch->getSuccessor(1));
50 if (Succ0 && !Succ1) {
51 Branch->setSuccessor(idx: 0, NewSucc: FirstGuardBlock);
52 } else if (Succ1 && !Succ0) {
53 Branch->setSuccessor(idx: 1, NewSucc: FirstGuardBlock);
54 } else {
55 Branch->eraseFromParent();
56 UncondBrInst::Create(Target: FirstGuardBlock, InsertBefore: BB);
57 }
58
59 return Condition;
60}
61
62// Setup the branch instructions for guard blocks.
63//
64// Each guard block terminates in a conditional branch that transfers
65// control to the corresponding outgoing block or the next guard
66// block. The last guard block has two outgoing blocks as successors.
67static void setupBranchForGuard(ArrayRef<BasicBlock *> GuardBlocks,
68 ArrayRef<BasicBlock *> Outgoing,
69 BBPredicates &GuardPredicates) {
70 assert(Outgoing.size() > 1);
71 assert(GuardBlocks.size() == Outgoing.size() - 1);
72 // The guard predicates are PHIs merging values from all the incoming blocks,
73 // so the probability of each guard branch cannot be derived locally.
74 int I = 0;
75 for (int E = GuardBlocks.size() - 1; I != E; ++I) {
76 BasicBlock *Out = Outgoing[I];
77 auto *Br = CondBrInst::Create(Cond: GuardPredicates[Out], IfTrue: Out, IfFalse: GuardBlocks[I + 1],
78 InsertBefore: GuardBlocks[I]);
79 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *Br, DEBUG_TYPE);
80 }
81 BasicBlock *Out = Outgoing[I];
82 auto *Br = CondBrInst::Create(Cond: GuardPredicates[Out], IfTrue: Out, IfFalse: Outgoing[I + 1],
83 InsertBefore: GuardBlocks[I]);
84 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *Br, DEBUG_TYPE);
85}
86
87// Assign an index to each outgoing block. At the corresponding guard
88// block, compute the branch condition by comparing this index.
89static void calcPredicateUsingInteger(ArrayRef<EdgeDescriptor> Branches,
90 ArrayRef<BasicBlock *> Outgoing,
91 ArrayRef<BasicBlock *> GuardBlocks,
92 BBPredicates &GuardPredicates) {
93 LLVMContext &Context = GuardBlocks.front()->getContext();
94 BasicBlock *FirstGuardBlock = GuardBlocks.front();
95 Type *Int32Ty = Type::getInt32Ty(C&: Context);
96
97 auto *Phi = PHINode::Create(Ty: Int32Ty, NumReservedValues: Branches.size(), NameStr: "merged.bb.idx",
98 InsertBefore: FirstGuardBlock);
99
100 for (auto [BB, Succ0, Succ1] : Branches) {
101 Value *Condition = redirectToHub(BB, Succ0, Succ1, FirstGuardBlock);
102 Value *IncomingId = nullptr;
103 if (Succ0 && Succ1 && Succ0 != Succ1) {
104 auto Succ0Iter = find(Range&: Outgoing, Val: Succ0);
105 auto Succ1Iter = find(Range&: Outgoing, Val: Succ1);
106 Value *Id0 =
107 ConstantInt::get(Ty: Int32Ty, V: std::distance(first: Outgoing.begin(), last: Succ0Iter));
108 Value *Id1 =
109 ConstantInt::get(Ty: Int32Ty, V: std::distance(first: Outgoing.begin(), last: Succ1Iter));
110 IncomingId = SelectInst::Create(C: Condition, S1: Id0, S2: Id1, NameStr: "target.bb.idx",
111 InsertBefore: BB->getTerminator()->getIterator());
112 } else {
113 // Get the index of the non-null successor, or when both successors
114 // are the same block, use that block's index directly.
115 auto SuccIter = Succ0 ? find(Range&: Outgoing, Val: Succ0) : find(Range&: Outgoing, Val: Succ1);
116 IncomingId =
117 ConstantInt::get(Ty: Int32Ty, V: std::distance(first: Outgoing.begin(), last: SuccIter));
118 }
119 Phi->addIncoming(V: IncomingId, BB);
120 }
121
122 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {
123 BasicBlock *Out = Outgoing[I];
124 LLVM_DEBUG(dbgs() << "Creating integer guard for " << Out->getName()
125 << "\n");
126 auto *Cmp = ICmpInst::Create(Op: Instruction::ICmp, Pred: ICmpInst::ICMP_EQ, S1: Phi,
127 S2: ConstantInt::get(Ty: Int32Ty, V: I),
128 Name: Out->getName() + ".predicate", InsertBefore: GuardBlocks[I]);
129 GuardPredicates[Out] = Cmp;
130 }
131}
132
133// Determine the branch condition to be used at each guard block from the
134// original boolean values.
135static void calcPredicateUsingBooleans(
136 ArrayRef<EdgeDescriptor> Branches, ArrayRef<BasicBlock *> Outgoing,
137 SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates,
138 SmallVectorImpl<WeakVH> &DeletionCandidates) {
139 LLVMContext &Context = GuardBlocks.front()->getContext();
140 auto *BoolTrue = ConstantInt::getTrue(Context);
141 auto *BoolFalse = ConstantInt::getFalse(Context);
142 BasicBlock *FirstGuardBlock = GuardBlocks.front();
143
144 // The predicate for the last outgoing is trivially true, and so we
145 // process only the first N-1 successors.
146 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {
147 BasicBlock *Out = Outgoing[I];
148 LLVM_DEBUG(dbgs() << "Creating boolean guard for " << Out->getName()
149 << "\n");
150
151 auto *Phi =
152 PHINode::Create(Ty: Type::getInt1Ty(C&: Context), NumReservedValues: Branches.size(),
153 NameStr: StringRef("Guard.") + Out->getName(), InsertBefore: FirstGuardBlock);
154 GuardPredicates[Out] = Phi;
155 }
156
157 for (auto [BB, Succ0, Succ1] : Branches) {
158 Value *Condition = redirectToHub(BB, Succ0, Succ1, FirstGuardBlock);
159
160 // Optimization: Consider an incoming block A with both successors
161 // Succ0 and Succ1 in the set of outgoing blocks. The predicates
162 // for Succ0 and Succ1 complement each other. If Succ0 is visited
163 // first in the loop below, control will branch to Succ0 using the
164 // corresponding predicate. But if that branch is not taken, then
165 // control must reach Succ1, which means that the incoming value of
166 // the predicate from `BB` is true for Succ1.
167 bool OneSuccessorDone = false;
168 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {
169 BasicBlock *Out = Outgoing[I];
170 PHINode *Phi = cast<PHINode>(Val: GuardPredicates[Out]);
171 if (Out != Succ0 && Out != Succ1) {
172 Phi->addIncoming(V: BoolFalse, BB);
173 } else if (!Succ0 || !Succ1 || Succ0 == Succ1 || OneSuccessorDone) {
174 // Optimization: When only one successor is an outgoing block,
175 // or both successors are the same block, the incoming predicate
176 // from `BB` is always true.
177 Phi->addIncoming(V: BoolTrue, BB);
178 } else {
179 assert(Succ0 && Succ1);
180 if (Out == Succ0) {
181 Phi->addIncoming(V: Condition, BB);
182 } else {
183 Value *Inverted = invertCondition(Condition);
184 DeletionCandidates.push_back(Elt: Condition);
185 Phi->addIncoming(V: Inverted, BB);
186 }
187 OneSuccessorDone = true;
188 }
189 }
190 }
191}
192
193// Capture the existing control flow as guard predicates, and redirect
194// control flow from \p Incoming block through the \p GuardBlocks to the
195// \p Outgoing blocks.
196//
197// There is one guard predicate for each outgoing block OutBB. The
198// predicate represents whether the hub should transfer control flow
199// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates
200// them in the same order as the Outgoing set-vector, and control
201// branches to the first outgoing block whose predicate evaluates to true.
202//
203// The last guard block has two outgoing blocks as successors since the
204// condition for the final outgoing block is trivially true. So we create one
205// less block (including the first guard block) than the number of outgoing
206// blocks.
207static void convertToGuardPredicates(
208 ArrayRef<EdgeDescriptor> Branches, ArrayRef<BasicBlock *> Outgoing,
209 SmallVectorImpl<BasicBlock *> &GuardBlocks,
210 SmallVectorImpl<WeakVH> &DeletionCandidates, const StringRef Prefix,
211 std::optional<unsigned> MaxControlFlowBooleans) {
212 BBPredicates GuardPredicates;
213 Function *F = Outgoing.front()->getParent();
214
215 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I)
216 GuardBlocks.push_back(
217 Elt: BasicBlock::Create(Context&: F->getContext(), Name: Prefix + ".guard", Parent: F));
218
219 // When we are using an integer to record which target block to jump to, we
220 // are creating less live values, actually we are using one single integer to
221 // store the index of the target block. When we are using booleans to store
222 // the branching information, we need (N-1) boolean values, where N is the
223 // number of outgoing block.
224 if (!MaxControlFlowBooleans || Outgoing.size() <= *MaxControlFlowBooleans)
225 calcPredicateUsingBooleans(Branches, Outgoing, GuardBlocks, GuardPredicates,
226 DeletionCandidates);
227 else
228 calcPredicateUsingInteger(Branches, Outgoing, GuardBlocks, GuardPredicates);
229
230 setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates);
231}
232
233// After creating a control flow hub, the operands of PHINodes in an outgoing
234// block Out no longer match the predecessors of that block. The edges to Out
235// that are redirected through the hub are now replaced by just one edge from
236// the hub; other edges to Out, even from incoming blocks of the hub, are kept.
237// To match this new control flow, the values for the redirected edges are
238// moved from each PHINode to a new PHINode in the first guard block of the hub.
239//
240// If Out is itself an incoming block of the hub (a self-loop that is
241// redirected through the hub), the new PHINode receives the value that the
242// original PHINode received along the self-loop. If that value is the original
243// PHINode itself, it becomes the new PHINode when the original is replaced.
244static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
245 ArrayRef<EdgeDescriptor> Incoming,
246 BasicBlock *FirstGuardBlock) {
247 auto I = Out->begin();
248 while (I != Out->end() && isa<PHINode>(Val: I)) {
249 auto *Phi = cast<PHINode>(Val&: I);
250 auto *NewPhi =
251 PHINode::Create(Ty: Phi->getType(), NumReservedValues: Incoming.size(),
252 NameStr: Phi->getName() + ".moved", InsertBefore: FirstGuardBlock->begin());
253 bool AllUndef = true;
254 bool AllPoison = true;
255 for (auto [BB, Succ0, Succ1] : Incoming) {
256 Value *V = PoisonValue::get(T: Phi->getType());
257 // Only edges from BB to Out that go through the hub move their value.
258 // BB may have another edge to Out that is not redirected.
259 if ((Succ0 == Out || Succ1 == Out) && Phi->getBasicBlockIndex(BB) != -1) {
260 V = Phi->removeIncomingValue(BB, DeletePHIIfEmpty: false);
261 // When both successors are the same (Succ0 == Succ1), there are two
262 // edges from BB to Out, so we need to remove the second PHI entry too.
263 if (Succ0 && Succ1 && Succ0 == Succ1 &&
264 Phi->getBasicBlockIndex(BB) != -1)
265 Phi->removeIncomingValue(BB, DeletePHIIfEmpty: false);
266 AllUndef &= isa<UndefValue>(Val: V);
267 AllPoison &= isa<PoisonValue>(Val: V);
268 }
269
270 NewPhi->addIncoming(V, BB);
271 }
272 assert(NewPhi->getNumIncomingValues() == Incoming.size());
273 Value *NewV = NewPhi;
274 // If all moved values are undef or poison, use that instead of a PHI. Only
275 // use poison if they are all poison: replacing undef with poison would make
276 // the program less defined.
277 if (AllUndef) {
278 NewPhi->eraseFromParent();
279 NewV = AllPoison ? PoisonValue::get(T: Phi->getType())
280 : UndefValue::get(T: Phi->getType());
281 }
282 if (Phi->getNumOperands() == 0) {
283 Phi->replaceAllUsesWith(V: NewV);
284 I = Phi->eraseFromParent();
285 continue;
286 }
287 Phi->addIncoming(V: NewV, BB: GuardBlock);
288 ++I;
289 }
290}
291
292std::pair<BasicBlock *, bool> ControlFlowHub::finalize(
293 DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
294 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
295#ifndef NDEBUG
296 SmallPtrSet<BasicBlock *, 8> Incoming;
297#endif
298 SetVector<BasicBlock *> Outgoing;
299
300 for (auto [BB, Succ0, Succ1] : Branches) {
301#ifndef NDEBUG
302 assert(
303 (Incoming.insert(BB).second || isa<CallBrInst>(BB->getTerminator())) &&
304 "Duplicate entry for incoming block.");
305#endif
306 if (Succ0)
307 Outgoing.insert(X: Succ0);
308 if (Succ1)
309 Outgoing.insert(X: Succ1);
310 }
311
312 assert(Outgoing.size() && "No outgoing edges");
313
314 if (Outgoing.size() < 2)
315 return {Outgoing.front(), false};
316
317 SmallVector<DominatorTree::UpdateType, 16> Updates;
318 if (DTU) {
319 for (auto [BB, Succ0, Succ1] : Branches) {
320 if (Succ0)
321 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ0});
322 // Only add Succ1 if it's different from Succ0 to avoid duplicate updates
323 if (Succ1 && Succ1 != Succ0)
324 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ1});
325 }
326 }
327
328 SmallVector<WeakVH, 8> DeletionCandidates;
329 convertToGuardPredicates(Branches, Outgoing: Outgoing.getArrayRef(), GuardBlocks,
330 DeletionCandidates, Prefix, MaxControlFlowBooleans);
331 BasicBlock *FirstGuardBlock = GuardBlocks.front();
332
333 // Update the PHINodes in each outgoing block to match the new control flow.
334 for (int I = 0, E = GuardBlocks.size(); I != E; ++I)
335 reconnectPhis(Out: Outgoing[I], GuardBlock: GuardBlocks[I], Incoming: Branches, FirstGuardBlock);
336 // Process the Nth (last) outgoing block with the (N-1)th (last) guard block.
337 reconnectPhis(Out: Outgoing.back(), GuardBlock: GuardBlocks.back(), Incoming: Branches, FirstGuardBlock);
338
339 if (DTU) {
340 int NumGuards = GuardBlocks.size();
341
342 for (auto [BB, Succ0, Succ1] : Branches)
343 Updates.push_back(Elt: {DominatorTree::Insert, BB, FirstGuardBlock});
344
345 for (int I = 0; I != NumGuards - 1; ++I) {
346 Updates.push_back(Elt: {DominatorTree::Insert, GuardBlocks[I], Outgoing[I]});
347 Updates.push_back(
348 Elt: {DominatorTree::Insert, GuardBlocks[I], GuardBlocks[I + 1]});
349 }
350 // The second successor of the last guard block is an outgoing block instead
351 // of having a "next" guard block.
352 Updates.push_back(Elt: {DominatorTree::Insert, GuardBlocks[NumGuards - 1],
353 Outgoing[NumGuards - 1]});
354 Updates.push_back(Elt: {DominatorTree::Insert, GuardBlocks[NumGuards - 1],
355 Outgoing[NumGuards]});
356 DTU->applyUpdates(Updates);
357 }
358
359 for (auto &I : DeletionCandidates) {
360 if (auto *Inst = dyn_cast_if_present<Instruction>(Val&: I)) {
361 if (Inst->use_empty())
362 Inst->eraseFromParent();
363 }
364 }
365
366 return {FirstGuardBlock, true};
367}
368