1//===- ControlFlowUtils.cpp - Control Flow Utilities -----------------------==//
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
7//===----------------------------------------------------------------------===//
9// Utilities to manipulate the CFG and restore SSA for the new control flow.
11//===----------------------------------------------------------------------===//
22 #define DEBUG_TYPE "control-flow-hub"
29// Redirects the terminator of the incoming block to the first guard block in
30// the hub. Returns the branch condition from `BB` if it exits.
31// - If only one of Succ0 or Succ1 is not null, the corresponding branch
32// successor is redirected to the FirstGuardBlock.
33// - Else both are not null, and branch is replaced with an unconditional
34// branch to the FirstGuardBlock.
38 "Only support branch terminator.");
40 auto *Condition = Branch->isConditional() ? Branch->getCondition() :
nullptr;
44 if (Branch->isUnconditional()) {
45 assert(Succ0 == Branch->getSuccessor(0));
47 Branch->setSuccessor(0, FirstGuardBlock);
49 assert(!Succ1 || Succ1 == Branch->getSuccessor(1));
50 if (Succ0 && !Succ1) {
51 Branch->setSuccessor(0, FirstGuardBlock);
52 }
else if (Succ1 && !Succ0) {
53 Branch->setSuccessor(1, FirstGuardBlock);
55 Branch->eraseFromParent();
63// Setup the branch instructions for guard blocks.
65// Each guard block terminates in a conditional branch that transfers
66// control to the corresponding outgoing block or the next guard
67// block. The last guard block has two outgoing blocks as successors.
74 for (
int E = GuardBlocks.
size() - 1;
I !=
E; ++
I) {
84// Assign an index to each outgoing block. At the corresponding guard
85// block, compute the branch condition by comparing this index.
97 for (
auto [BB, Succ0, Succ1] : Branches) {
99 Value *IncomingId =
nullptr;
100 if (Succ0 && Succ1) {
101 auto Succ0Iter =
find(Outgoing, Succ0);
102 auto Succ1Iter =
find(Outgoing, Succ1);
104 ConstantInt::get(
Int32Ty, std::distance(Outgoing.
begin(), Succ0Iter));
106 ConstantInt::get(
Int32Ty, std::distance(Outgoing.
begin(), Succ1Iter));
108 BB->getTerminator()->getIterator());
110 // Get the index of the non-null successor.
111 auto SuccIter = Succ0 ?
find(Outgoing, Succ0) :
find(Outgoing, Succ1);
113 ConstantInt::get(
Int32Ty, std::distance(Outgoing.
begin(), SuccIter));
115 Phi->addIncoming(IncomingId, BB);
118 for (
int I = 0,
E = Outgoing.
size() - 1;
I !=
E; ++
I) {
124 Out->
getName() +
".predicate", GuardBlocks[
I]);
125 GuardPredicates[Out] = Cmp;
129// Determine the branch condition to be used at each guard block from the
130// original boolean values.
140 // The predicate for the last outgoing is trivially true, and so we
141 // process only the first N-1 successors.
142 for (
int I = 0,
E = Outgoing.
size() - 1;
I !=
E; ++
I) {
150 GuardPredicates[Out] = Phi;
153 for (
auto [BB, Succ0, Succ1] : Branches) {
156 // Optimization: Consider an incoming block A with both successors
157 // Succ0 and Succ1 in the set of outgoing blocks. The predicates
158 // for Succ0 and Succ1 complement each other. If Succ0 is visited
159 // first in the loop below, control will branch to Succ0 using the
160 // corresponding predicate. But if that branch is not taken, then
161 // control must reach Succ1, which means that the incoming value of
162 // the predicate from `BB` is true for Succ1.
163 bool OneSuccessorDone =
false;
164 for (
int I = 0,
E = Outgoing.
size() - 1;
I !=
E; ++
I) {
167 if (Out != Succ0 && Out != Succ1) {
168 Phi->addIncoming(BoolFalse, BB);
169 }
else if (!Succ0 || !Succ1 || OneSuccessorDone) {
170 // Optimization: When only one successor is an outgoing block,
171 // the incoming predicate from `BB` is always true.
172 Phi->addIncoming(BoolTrue, BB);
176 Phi->addIncoming(Condition, BB);
180 Phi->addIncoming(Inverted, BB);
182 OneSuccessorDone =
true;
188// Capture the existing control flow as guard predicates, and redirect
189// control flow from \p Incoming block through the \p GuardBlocks to the
190// \p Outgoing blocks.
192// There is one guard predicate for each outgoing block OutBB. The
193// predicate represents whether the hub should transfer control flow
194// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates
195// them in the same order as the Outgoing set-vector, and control
196// branches to the first outgoing block whose predicate evaluates to true.
198// The last guard block has two outgoing blocks as successors since the
199// condition for the final outgoing block is trivially true. So we create one
200// less block (including the first guard block) than the number of outgoing
206 std::optional<unsigned> MaxControlFlowBooleans) {
210 for (
int I = 0,
E = Outgoing.
size() - 1;
I !=
E; ++
I)
214 // When we are using an integer to record which target block to jump to, we
215 // are creating less live values, actually we are using one single integer to
216 // store the index of the target block. When we are using booleans to store
217 // the branching information, we need (N-1) boolean values, where N is the
218 // number of outgoing block.
219 if (!MaxControlFlowBooleans || Outgoing.
size() <= *MaxControlFlowBooleans)
228// After creating a control flow hub, the operands of PHINodes in an outgoing
229// block Out no longer match the predecessors of that block. Predecessors of Out
230// that are incoming blocks to the hub are now replaced by just one edge from
231// the hub. To match this new control flow, the corresponding values from each
232// PHINode must now be moved a new PHINode in the first guard block of the hub.
234// This operation cannot be performed with SSAUpdater, because it involves one
235// new use: If the block Out is in the list of Incoming blocks, then the newly
236// created PHI in the Hub will use itself along that edge from Out to Hub.
245 Phi->getName() +
".moved", FirstGuardBlock->
begin());
246 bool AllUndef =
true;
247 for (
auto [BB, Succ0, Succ1] :
Incoming) {
249 if (Phi->getBasicBlockIndex(BB) != -1) {
250 V = Phi->removeIncomingValue(BB,
false);
257 NewPhi->addIncoming(V, BB);
260 Value *NewV = NewPhi;
262 NewPhi->eraseFromParent();
265 if (Phi->getNumOperands() == 0) {
266 Phi->replaceAllUsesWith(NewV);
267 I = Phi->eraseFromParent();
270 Phi->addIncoming(NewV, GuardBlock);
277 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
283 for (
auto [BB, Succ0, Succ1] :
Branches) {
287 "Duplicate entry for incoming block.");
295 if (Outgoing.
size() < 2)
296 return {Outgoing.
front(),
false};
300 for (
auto [BB, Succ0, Succ1] :
Branches) {
310 DeletionCandidates, Prefix, MaxControlFlowBooleans);
313 // Update the PHINodes in each outgoing block to match the new control flow.
314 for (
int I = 0, E = GuardBlocks.
size();
I != E; ++
I)
316 // Process the Nth (last) outgoing block with the (N-1)th (last) guard block.
320 int NumGuards = GuardBlocks.
size();
322 for (
auto [BB, Succ0, Succ1] :
Branches)
325 for (
int I = 0;
I != NumGuards - 1; ++
I) {
330 // The second successor of the last guard block is an outgoing block instead
331 // of having a "next" guard block.
333 Outgoing[NumGuards - 1]});
335 Outgoing[NumGuards]});
339 for (
auto I : DeletionCandidates) {
342 Inst->eraseFromParent();
345 return {FirstGuardBlock,
true};
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void calcPredicateUsingBooleans(ArrayRef< EdgeDescriptor > Branches, ArrayRef< BasicBlock * > Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates)
static void setupBranchForGuard(ArrayRef< BasicBlock * > GuardBlocks, ArrayRef< BasicBlock * > Outgoing, BBPredicates &GuardPredicates)
static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, ArrayRef< EdgeDescriptor > Incoming, BasicBlock *FirstGuardBlock)
static void calcPredicateUsingInteger(ArrayRef< EdgeDescriptor > Branches, ArrayRef< BasicBlock * > Outgoing, ArrayRef< BasicBlock * > GuardBlocks, BBPredicates &GuardPredicates)
DenseMap< BasicBlock *, Instruction * > BBPredicates
static Value * redirectToHub(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1, BasicBlock *FirstGuardBlock)
static void convertToGuardPredicates(ArrayRef< EdgeDescriptor > Branches, ArrayRef< BasicBlock * > Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, SmallVectorImpl< WeakVH > &DeletionCandidates, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans)
ControlFlowHub::BranchDescriptor EdgeDescriptor
This file implements a set that has insertion order iteration characteristics.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
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...
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
static LLVM_ABI CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
This is an important class for using LLVM in a threaded context.
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 PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)
A vector that has set insertion semantics.
ArrayRef< value_type > getArrayRef() const
size_type size() const
Determine the number of elements in the SetVector.
const value_type & front() const
Return the first element of the SetVector.
const value_type & back() const
Return the last element of the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
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.
StringRef - Represent a constant reference to a string, i.e.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
LLVM Value Representation.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty
auto dyn_cast_or_null(const Y &Val)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
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.
SmallVector< BranchDescriptor > Branches
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...