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