Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such that the control flow from each BB to a successor is now split into two edges, one from BB to the hub and another from the hub to the successor. More...

#include "llvm/Transforms/Utils/ControlFlowUtils.h"

Classes
struct	BranchDescriptor

Public Member Functions
void	addBranch (BasicBlock BB, BasicBlock Succ0, BasicBlock *Succ1)

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

Public Attributes
SmallVector< BranchDescriptor >	Branches

Detailed Description

Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such that the control flow from each BB to a successor is now split into two edges, one from BB to the hub and another from the hub to the successor.

The hub consists of a series of guard blocks, one for each outgoing block. Each guard block conditionally branches to the corresponding outgoing block, or the next guard block in the chain. These guard blocks are returned in the argument vector.

This also updates any PHINodes in the successor. For each such PHINode, the operands corresponding to incoming blocks are moved to a new PHINode in the hub, and the hub is made an operand of the original PHINode.

Note that for some block BB with a conditional branch, it is not necessary that both successors are rerouted. The client specifies this by setting either Succ0 or Succ1 to nullptr, in which case, the corresponding successor is not rerouted.

Input CFG:

               Def
                |
                v
      In1      In2
       |        |
       |        |
       v        v

Foo —> Out1 Out2 | v Use

Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2}

        Def
         |
         v

In1 In2 Foo | Hub | | | + - - | - - + | | ' v ' V +---—> Guard1 --—> Out1 ' | ' ' v ' ' Guard2 --—> Out2 ' ' |

- - - - - + | v Use

Limitations:

This assumes that all terminators in the CFG are direct branches (the "br" instruction). The presence of any other control flow such as indirectbr, switch or callbr will cause an assert.
The updates to the PHINodes are not sufficient to restore SSA form. Consider a definition Def, its use Use, incoming block In2 and outgoing block Out2, such that: a. In2 is reachable from D or contains D. b. U is reachable from Out2 or is contained in Out2. c. U is not a PHINode if U is contained in Out2.

Clearly, Def dominates Out2 since the program is valid SSA. But when the hub is introduced, there is a new path through the hub along which Use is reachable from entry without passing through Def, and SSA is no longer valid. To fix this, we need to look at all the blocks post-dominated by the hub on the one hand, and dominated by Out2 on the other. This is left for the caller to accomplish, since each specific use of this function may have additional information which simplifies this fixup. For example, see restoreSSA() in the UnifyLoopExits pass.

Definition at line 97 of file ControlFlowUtils.h.

Member Function Documentation

◆ addBranch()

void llvm::ControlFlowHub::addBranch	(	BasicBlock *	BB,
		BasicBlock *	Succ0,
		BasicBlock *	Succ1
	)

inline

Definition at line 107 of file ControlFlowUtils.h.

References assert(), and Branches.

Referenced by fixIrreducible(), and unifyLoopExits().

◆ finalize()

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

Member Data Documentation

◆ Branches

SmallVector<BranchDescriptor> llvm::ControlFlowHub::Branches

Definition at line 118 of file ControlFlowUtils.h.

Referenced by addBranch(), and finalize().

The documentation for this struct was generated from the following files:

include/llvm/Transforms/Utils/ControlFlowUtils.h
lib/Transforms/Utils/ControlFlowUtils.cpp

Classes

Public Member Functions

Public Attributes