1//===- MachineIDFSSAUpdater.cpp - Unstructured SSA Update Tool ------------===//
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// This file implements the MachineIDFSSAUpdater class, which provides an
10// efficient SSA form maintenance utility for machine-level IR. It uses the
11// iterated dominance frontier (IDF) algorithm via MachineForwardIDFCalculator
12// to compute phi-function placement, offering better performance than the
13// incremental MachineSSAUpdater approach. The updater requires a single call
14// to calculate() after all definitions and uses have been registered.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/MachineIDFSSAUpdater.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/Analysis/IteratedDominanceFrontier.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineDominators.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/MachineInstrBuilder.h"
26#include "llvm/CodeGen/MachineOperand.h"
27#include "llvm/CodeGen/MachineRegisterInfo.h"
28#include "llvm/CodeGen/TargetInstrInfo.h"
29#include "llvm/CodeGen/TargetOpcodes.h"
30#include "llvm/IR/DebugLoc.h"
31#include "llvm/Support/Debug.h"
32
33namespace llvm {
34
35template <bool IsPostDom>
36class MachineIDFCalculator final
37 : public IDFCalculatorBase<MachineBasicBlock, IsPostDom> {
38public:
39 using IDFCalculatorBase =
40 typename llvm::IDFCalculatorBase<MachineBasicBlock, IsPostDom>;
41 using ChildrenGetterTy = typename IDFCalculatorBase::ChildrenGetterTy;
42
43 MachineIDFCalculator(DominatorTreeBase<MachineBasicBlock, IsPostDom> &DT)
44 : IDFCalculatorBase(DT) {}
45};
46
47using MachineForwardIDFCalculator = MachineIDFCalculator<false>;
48using MachineReverseIDFCalculator = MachineIDFCalculator<true>;
49
50} // namespace llvm
51
52using namespace llvm;
53
54/// Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks.
55/// This is basically a subgraph limited by DefBlocks and UsingBlocks.
56static void
57computeLiveInBlocks(const SmallPtrSetImpl<MachineBasicBlock *> &UsingBlocks,
58 const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,
59 SmallPtrSetImpl<MachineBasicBlock *> &LiveInBlocks) {
60 // To determine liveness, we must iterate through the predecessors of blocks
61 // where the def is live. Blocks are added to the worklist if we need to
62 // check their predecessors. Start with all the using blocks.
63 SmallVector<MachineBasicBlock *, 64> LiveInBlockWorklist(UsingBlocks.begin(),
64 UsingBlocks.end());
65
66 // Now that we have a set of blocks where the phi is live-in, recursively add
67 // their predecessors until we find the full region the value is live.
68 while (!LiveInBlockWorklist.empty()) {
69 MachineBasicBlock *BB = LiveInBlockWorklist.pop_back_val();
70
71 // The block really is live in here, insert it into the set. If already in
72 // the set, then it has already been processed.
73 if (!LiveInBlocks.insert(Ptr: BB).second)
74 continue;
75
76 // Since the value is live into BB, it is either defined in a predecessor or
77 // live into it to. Add the preds to the worklist unless they are a
78 // defining block.
79 for (MachineBasicBlock *P : BB->predecessors()) {
80 // The value is not live into a predecessor if it defines the value.
81 if (DefBlocks.count(Ptr: P))
82 continue;
83
84 // Otherwise it is, add to the worklist.
85 LiveInBlockWorklist.push_back(Elt: P);
86 }
87 }
88}
89
90MachineInstrBuilder
91MachineIDFSSAUpdater::createInst(unsigned Opc, MachineBasicBlock *BB,
92 MachineBasicBlock::iterator I) {
93 return BuildMI(BB&: *BB, I, MIMD: DebugLoc(), MCID: TII.get(Opcode: Opc),
94 DestReg: MRI.createVirtualRegister(RegAttr: RegAttrs));
95}
96
97// IsLiveOut indicates whether we are computing live-out values (true) or
98// live-in values (false).
99Register MachineIDFSSAUpdater::computeValue(MachineBasicBlock *BB,
100 bool IsLiveOut) {
101 BBValueInfo *BBInfo = &BBInfos[BB];
102
103 if (IsLiveOut && BBInfo->LiveOutValue)
104 return BBInfo->LiveOutValue;
105
106 if (BBInfo->LiveInValue)
107 return BBInfo->LiveInValue;
108
109 SmallVector<BBValueInfo *, 4> DomPath = {BBInfo};
110 MachineBasicBlock *DomBB = BB, *TopDomBB = BB;
111 Register V;
112
113 while (DT.isReachableFromEntry(A: DomBB) && !DomBB->pred_empty() &&
114 (DomBB = DT.getNode(BB: DomBB)->getIDom()->getBlock())) {
115 BBInfo = &BBInfos[DomBB];
116 if (BBInfo->LiveOutValue) {
117 V = BBInfo->LiveOutValue;
118 break;
119 }
120 if (BBInfo->LiveInValue) {
121 V = BBInfo->LiveInValue;
122 break;
123 }
124 TopDomBB = DomBB;
125 DomPath.emplace_back(Args&: BBInfo);
126 }
127
128 if (!V) {
129 V = createInst(Opc: TargetOpcode::IMPLICIT_DEF, BB: TopDomBB,
130 I: TopDomBB->getFirstNonPHI())
131 .getReg(Idx: 0);
132 }
133
134 for (BBValueInfo *BBInfo : DomPath) {
135 // Loop above can insert new entries into the BBInfos map: assume the
136 // map shouldn't grow as the caller should have been allocated enough
137 // buckets, see [1].
138 BBInfo->LiveInValue = V;
139 }
140
141 return V;
142}
143
144/// Perform all the necessary updates, including new PHI-nodes insertion and the
145/// requested uses update.
146void MachineIDFSSAUpdater::calculate() {
147 MachineForwardIDFCalculator IDF(DT);
148
149 SmallPtrSet<MachineBasicBlock *, 2> DefBlocks;
150 for (auto [BB, V] : Defines)
151 DefBlocks.insert(Ptr: BB);
152 IDF.setDefiningBlocks(DefBlocks);
153
154 SmallPtrSet<MachineBasicBlock *, 2> UsingBlocks(UseBlocks.begin(),
155 UseBlocks.end());
156 SmallVector<MachineBasicBlock *, 4> IDFBlocks;
157 SmallPtrSet<MachineBasicBlock *, 4> LiveInBlocks;
158 computeLiveInBlocks(UsingBlocks, DefBlocks, LiveInBlocks);
159 IDF.setLiveInBlocks(LiveInBlocks);
160 IDF.calculate(IDFBlocks);
161
162 // Reserve sufficient buckets to prevent map growth. [1]
163 BBInfos.reserve(NumEntries: LiveInBlocks.size() + DefBlocks.size());
164
165 for (auto [BB, V] : Defines)
166 BBInfos[BB].LiveOutValue = V;
167
168 for (MachineBasicBlock *FrontierBB : IDFBlocks) {
169 Register NewVR =
170 createInst(Opc: TargetOpcode::PHI, BB: FrontierBB, I: FrontierBB->begin())
171 .getReg(Idx: 0);
172 BBInfos[FrontierBB].LiveInValue = NewVR;
173 }
174
175 for (MachineBasicBlock *BB : IDFBlocks) {
176 auto *PHI = &BB->front();
177 assert(PHI->isPHI());
178 MachineInstrBuilder MIB(*BB->getParent(), PHI);
179 for (MachineBasicBlock *Pred : BB->predecessors())
180 MIB.addReg(RegNo: computeValue(BB: Pred, /*IsLiveOut=*/true)).addMBB(MBB: Pred);
181 }
182}
183
184Register MachineIDFSSAUpdater::getValueInMiddleOfBlock(MachineBasicBlock *BB) {
185 return computeValue(BB, /*IsLiveOut=*/false);
186}
187