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.");
40auto *Condition = Branch->isConditional() ? Branch->getCondition() :
nullptr;
44if (Branch->isUnconditional()) {
45assert(Succ0 == Branch->getSuccessor(0));
47 Branch->setSuccessor(0, FirstGuardBlock);
49assert(!Succ1 || Succ1 == Branch->getSuccessor(1));
51 Branch->setSuccessor(0, FirstGuardBlock);
52 }
elseif (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. 74for (
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. 97for (
auto [BB, Succ0, Succ1] : Branches) {
99Value *IncomingId =
nullptr;
101auto Succ0Iter =
find(Outgoing, Succ0);
102auto 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. 111auto SuccIter = Succ0 ?
find(Outgoing, Succ0) :
find(Outgoing, Succ1);
113 ConstantInt::get(Int32Ty, std::distance(Outgoing.
begin(), SuccIter));
115 Phi->addIncoming(IncomingId, BB);
118for (
intI = 0, E = Outgoing.
size() - 1;
I != E; ++
I) {
122auto *Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,
123 ConstantInt::get(Int32Ty,
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. 142for (
intI = 0, E = Outgoing.
size() - 1;
I != E; ++
I) {
150 GuardPredicates[Out] = Phi;
153for (
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. 163bool OneSuccessorDone =
false;
164for (
intI = 0, E = Outgoing.
size() - 1;
I != E; ++
I) {
166PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);
167if (Out != Succ0 && Out != Succ1) {
168 Phi->addIncoming(BoolFalse, BB);
169 }
elseif (!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) {
210for (
intI = 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. 219if (!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. 241while (
I != Out->
end() && isa<PHINode>(
I)) {
242auto *Phi = cast<PHINode>(
I);
245 Phi->getName() +
".moved", FirstGuardBlock->
begin());
247for (
auto [BB, Succ0, Succ1] :
Incoming) {
251 }
elseif (Phi->getBasicBlockIndex(BB) != -1) {
252 V = Phi->removeIncomingValue(BB,
false);
253 AllUndef &= isa<UndefValue>(V);
255 NewPhi->addIncoming(V, BB);
260 NewPhi->eraseFromParent();
263if (Phi->getNumOperands() == 0) {
264 Phi->replaceAllUsesWith(NewV);
265I = Phi->eraseFromParent();
268 Phi->addIncoming(NewV, GuardBlock);
275constStringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
281for (
auto [BB, Succ0, Succ1] :
Branches) {
283assert(
Incoming.insert(BB).second &&
"Duplicate entry for incoming block.");
291if (Outgoing.
size() < 2)
292return Outgoing.
front();
296for (
auto [BB, Succ0, Succ1] :
Branches) {
306 DeletionCandidates, Prefix, MaxControlFlowBooleans);
309// Update the PHINodes in each outgoing block to match the new control flow. 310for (
intI = 0, E = GuardBlocks.
size();
I != E; ++
I)
312// Process the Nth (last) outgoing block with the (N-1)th (last) guard block. 316int NumGuards = GuardBlocks.
size();
318for (
auto [BB, Succ0, Succ1] :
Branches)
321for (
intI = 0;
I != NumGuards - 1; ++
I) {
326// The second successor of the last guard block is an outgoing block instead 327// of having a "next" guard block. 329 Outgoing[NumGuards - 1]});
331 Outgoing[NumGuards]});
335for (
autoI : DeletionCandidates) {
337if (
auto *Inst = dyn_cast_or_null<Instruction>(
I))
338 Inst->eraseFromParent();
341return FirstGuardBlock;
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)
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)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
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 ConstantInt * getTrue(LLVMContext &Context)
static 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 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, 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.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
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 IntegerType * getInt1Ty(LLVMContext &C)
static IntegerType * getInt32Ty(LLVMContext &C)
LLVM Value Representation.
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
BasicBlock * finalize(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)
SmallVector< BranchDescriptor > Branches
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
