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