1 //===- Transforms/Utils/ControlFlowUtils.h --------------------*- C++ -*---===// 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 #ifndef LLVM_TRANSFORMS_UTILS_CONTROLFLOWUTILS_H 14 #define LLVM_TRANSFORMS_UTILS_CONTROLFLOWUTILS_H 15 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ADT/StringRef.h" 18 19 namespace llvm { 20 21 class BasicBlock; 22 class DomTreeUpdater; 23 24 /// Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such 25 /// that the control flow from each BB to a successor is now split into two 26 /// edges, one from BB to the hub and another from the hub to the successor. The 27 /// hub consists of a series of guard blocks, one for each outgoing block. Each 28 /// guard block conditionally branches to the corresponding outgoing block, or 29 /// the next guard block in the chain. These guard blocks are returned in the 30 /// argument vector. 31 /// 32 /// This also updates any PHINodes in the successor. For each such PHINode, the 33 /// operands corresponding to incoming blocks are moved to a new PHINode in the 34 /// hub, and the hub is made an operand of the original PHINode. 35 /// 36 /// Note that for some block BB with a conditional branch, it is not necessary 37 /// that both successors are rerouted. The client specifies this by setting 38 /// either Succ0 or Succ1 to nullptr, in which case, the corresponding successor 39 /// is not rerouted. 40 /// 41 /// Input CFG: 42 /// ---------- 43 /// 44 /// Def 45 /// | 46 /// v 47 /// In1 In2 48 /// | | 49 /// | | 50 /// v v 51 /// Foo ---> Out1 Out2 52 /// | 53 /// v 54 /// Use 55 /// 56 /// 57 /// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2} 58 /// ---------------------------------------------------------- 59 /// 60 /// Def 61 /// | 62 /// v 63 /// In1 In2 Foo 64 /// | Hub | | 65 /// | + - - | - - + | 66 /// | ' v ' V 67 /// +------> Guard1 -----> Out1 68 /// ' | ' 69 /// ' v ' 70 /// ' Guard2 -----> Out2 71 /// ' ' | 72 /// + - - - - - + | 73 /// v 74 /// Use 75 /// 76 /// Limitations: 77 /// ----------- 78 /// 1. This assumes that all terminators in the CFG are direct branches (the 79 /// "br" instruction). The presence of any other control flow such as 80 /// indirectbr, switch or callbr will cause an assert. 81 /// 82 /// 2. The updates to the PHINodes are not sufficient to restore SSA 83 /// form. Consider a definition Def, its use Use, incoming block In2 and 84 /// outgoing block Out2, such that: 85 /// a. In2 is reachable from D or contains D. 86 /// b. U is reachable from Out2 or is contained in Out2. 87 /// c. U is not a PHINode if U is contained in Out2. 88 /// 89 /// Clearly, Def dominates Out2 since the program is valid SSA. But when the 90 /// hub is introduced, there is a new path through the hub along which Use is 91 /// reachable from entry without passing through Def, and SSA is no longer 92 /// valid. To fix this, we need to look at all the blocks post-dominated by 93 /// the hub on the one hand, and dominated by Out2 on the other. This is left 94 /// for the caller to accomplish, since each specific use of this function 95 /// may have additional information which simplifies this fixup. For example, 96 /// see restoreSSA() in the UnifyLoopExits pass. 97 struct ControlFlowHub { 98 struct BranchDescriptor { 99 BasicBlock *BB; 100 BasicBlock *Succ0; 101 BasicBlock *Succ1; 102 BranchDescriptorControlFlowHub::BranchDescriptor103 BranchDescriptor(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1) 104 : BB(BB), Succ0(Succ0), Succ1(Succ1) {} 105 }; 106 addBranchControlFlowHub107 void addBranch(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1) { 108 assert(BB); 109 assert(Succ0 || Succ1); 110 Branches.emplace_back(BB, Succ0, Succ1); 111 } 112 113 BasicBlock * 114 finalize(DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks, 115 const StringRef Prefix, 116 std::optional<unsigned> MaxControlFlowBooleans = std::nullopt); 117 118 SmallVector<BranchDescriptor> Branches; 119 }; 120 121 } // end namespace llvm 122 123 #endif // LLVM_TRANSFORMS_UTILS_CONTROLFLOWUTILS_H 124