EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2026-05-10 08:44:42
0001 //===- Transforms/Utils/ControlFlowUtils.h --------------------*- C++ -*---===// 0002 // 0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 0004 // See https://llvm.org/LICENSE.txt for license information. 0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 0006 // 0007 //===----------------------------------------------------------------------===// 0008 // 0009 // Utilities to manipulate the CFG and restore SSA for the new control flow. 0010 // 0011 //===----------------------------------------------------------------------===// 0012 0013 #ifndef LLVM_TRANSFORMS_UTILS_CONTROLFLOWUTILS_H 0014 #define LLVM_TRANSFORMS_UTILS_CONTROLFLOWUTILS_H 0015 0016 #include "llvm/ADT/SmallVector.h" 0017 #include "llvm/ADT/StringRef.h" 0018 0019 namespace llvm { 0020 0021 class BasicBlock; 0022 class DomTreeUpdater; 0023 0024 /// Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such 0025 /// that the control flow from each BB to a successor is now split into two 0026 /// edges, one from BB to the hub and another from the hub to the successor. The 0027 /// hub consists of a series of guard blocks, one for each outgoing block. Each 0028 /// guard block conditionally branches to the corresponding outgoing block, or 0029 /// the next guard block in the chain. These guard blocks are returned in the 0030 /// argument vector. 0031 /// 0032 /// This also updates any PHINodes in the successor. For each such PHINode, the 0033 /// operands corresponding to incoming blocks are moved to a new PHINode in the 0034 /// hub, and the hub is made an operand of the original PHINode. 0035 /// 0036 /// Note that for some block BB with a conditional branch, it is not necessary 0037 /// that both successors are rerouted. The client specifies this by setting 0038 /// either Succ0 or Succ1 to nullptr, in which case, the corresponding successor 0039 /// is not rerouted. 0040 /// 0041 /// Input CFG: 0042 /// ---------- 0043 /// 0044 /// Def 0045 /// | 0046 /// v 0047 /// In1 In2 0048 /// | | 0049 /// | | 0050 /// v v 0051 /// Foo ---> Out1 Out2 0052 /// | 0053 /// v 0054 /// Use 0055 /// 0056 /// 0057 /// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2} 0058 /// ---------------------------------------------------------- 0059 /// 0060 /// Def 0061 /// | 0062 /// v 0063 /// In1 In2 Foo 0064 /// | Hub | | 0065 /// | + - - | - - + | 0066 /// | ' v ' V 0067 /// +------> Guard1 -----> Out1 0068 /// ' | ' 0069 /// ' v ' 0070 /// ' Guard2 -----> Out2 0071 /// ' ' | 0072 /// + - - - - - + | 0073 /// v 0074 /// Use 0075 /// 0076 /// Limitations: 0077 /// ----------- 0078 /// 1. This assumes that all terminators in the CFG are direct branches (the 0079 /// "br" instruction). The presence of any other control flow such as 0080 /// indirectbr, switch or callbr will cause an assert. 0081 /// 0082 /// 2. The updates to the PHINodes are not sufficient to restore SSA 0083 /// form. Consider a definition Def, its use Use, incoming block In2 and 0084 /// outgoing block Out2, such that: 0085 /// a. In2 is reachable from D or contains D. 0086 /// b. U is reachable from Out2 or is contained in Out2. 0087 /// c. U is not a PHINode if U is contained in Out2. 0088 /// 0089 /// Clearly, Def dominates Out2 since the program is valid SSA. But when the 0090 /// hub is introduced, there is a new path through the hub along which Use is 0091 /// reachable from entry without passing through Def, and SSA is no longer 0092 /// valid. To fix this, we need to look at all the blocks post-dominated by 0093 /// the hub on the one hand, and dominated by Out2 on the other. This is left 0094 /// for the caller to accomplish, since each specific use of this function 0095 /// may have additional information which simplifies this fixup. For example, 0096 /// see restoreSSA() in the UnifyLoopExits pass. 0097 struct ControlFlowHub { 0098 struct BranchDescriptor { 0099 BasicBlock *BB; 0100 BasicBlock *Succ0; 0101 BasicBlock *Succ1; 0102 0103 BranchDescriptor(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1) 0104 : BB(BB), Succ0(Succ0), Succ1(Succ1) {} 0105 }; 0106 0107 void addBranch(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1) { 0108 assert(BB); 0109 assert(Succ0 || Succ1); 0110 Branches.emplace_back(BB, Succ0, Succ1); 0111 } 0112 0113 BasicBlock * 0114 finalize(DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks, 0115 const StringRef Prefix, 0116 std::optional<unsigned> MaxControlFlowBooleans = std::nullopt); 0117 0118 SmallVector<BranchDescriptor> Branches; 0119 }; 0120 0121 } // end namespace llvm 0122 0123 #endif // LLVM_TRANSFORMS_UTILS_CONTROLFLOWUTILS_H
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|