106f32e7eSjoerg //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg
9*da58b97aSjoerg #include "llvm/ADT/SmallSet.h"
10*da58b97aSjoerg #include "llvm/ADT/SetOperations.h"
11*da58b97aSjoerg #include "llvm/CodeGen/LivePhysRegs.h"
1206f32e7eSjoerg #include "llvm/CodeGen/ReachingDefAnalysis.h"
1306f32e7eSjoerg #include "llvm/CodeGen/TargetRegisterInfo.h"
1406f32e7eSjoerg #include "llvm/CodeGen/TargetSubtargetInfo.h"
1506f32e7eSjoerg #include "llvm/Support/Debug.h"
1606f32e7eSjoerg
1706f32e7eSjoerg using namespace llvm;
1806f32e7eSjoerg
1906f32e7eSjoerg #define DEBUG_TYPE "reaching-deps-analysis"
2006f32e7eSjoerg
2106f32e7eSjoerg char ReachingDefAnalysis::ID = 0;
2206f32e7eSjoerg INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
2306f32e7eSjoerg true)
2406f32e7eSjoerg
isValidReg(const MachineOperand & MO)25*da58b97aSjoerg static bool isValidReg(const MachineOperand &MO) {
26*da58b97aSjoerg return MO.isReg() && MO.getReg();
27*da58b97aSjoerg }
2806f32e7eSjoerg
isValidRegUse(const MachineOperand & MO)29*da58b97aSjoerg static bool isValidRegUse(const MachineOperand &MO) {
30*da58b97aSjoerg return isValidReg(MO) && MO.isUse();
31*da58b97aSjoerg }
32*da58b97aSjoerg
isValidRegUseOf(const MachineOperand & MO,MCRegister PhysReg)33*da58b97aSjoerg static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg) {
34*da58b97aSjoerg return isValidRegUse(MO) && MO.getReg() == PhysReg;
35*da58b97aSjoerg }
36*da58b97aSjoerg
isValidRegDef(const MachineOperand & MO)37*da58b97aSjoerg static bool isValidRegDef(const MachineOperand &MO) {
38*da58b97aSjoerg return isValidReg(MO) && MO.isDef();
39*da58b97aSjoerg }
40*da58b97aSjoerg
isValidRegDefOf(const MachineOperand & MO,MCRegister PhysReg)41*da58b97aSjoerg static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg) {
42*da58b97aSjoerg return isValidRegDef(MO) && MO.getReg() == PhysReg;
43*da58b97aSjoerg }
44*da58b97aSjoerg
enterBasicBlock(MachineBasicBlock * MBB)45*da58b97aSjoerg void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) {
4606f32e7eSjoerg unsigned MBBNumber = MBB->getNumber();
4706f32e7eSjoerg assert(MBBNumber < MBBReachingDefs.size() &&
4806f32e7eSjoerg "Unexpected basic block number.");
4906f32e7eSjoerg MBBReachingDefs[MBBNumber].resize(NumRegUnits);
5006f32e7eSjoerg
5106f32e7eSjoerg // Reset instruction counter in each basic block.
5206f32e7eSjoerg CurInstr = 0;
5306f32e7eSjoerg
5406f32e7eSjoerg // Set up LiveRegs to represent registers entering MBB.
5506f32e7eSjoerg // Default values are 'nothing happened a long time ago'.
5606f32e7eSjoerg if (LiveRegs.empty())
5706f32e7eSjoerg LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
5806f32e7eSjoerg
5906f32e7eSjoerg // This is the entry block.
6006f32e7eSjoerg if (MBB->pred_empty()) {
6106f32e7eSjoerg for (const auto &LI : MBB->liveins()) {
6206f32e7eSjoerg for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
6306f32e7eSjoerg // Treat function live-ins as if they were defined just before the first
6406f32e7eSjoerg // instruction. Usually, function arguments are set up immediately
6506f32e7eSjoerg // before the call.
66*da58b97aSjoerg if (LiveRegs[*Unit] != -1) {
6706f32e7eSjoerg LiveRegs[*Unit] = -1;
68*da58b97aSjoerg MBBReachingDefs[MBBNumber][*Unit].push_back(-1);
69*da58b97aSjoerg }
7006f32e7eSjoerg }
7106f32e7eSjoerg }
7206f32e7eSjoerg LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
7306f32e7eSjoerg return;
7406f32e7eSjoerg }
7506f32e7eSjoerg
7606f32e7eSjoerg // Try to coalesce live-out registers from predecessors.
7706f32e7eSjoerg for (MachineBasicBlock *pred : MBB->predecessors()) {
7806f32e7eSjoerg assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
7906f32e7eSjoerg "Should have pre-allocated MBBInfos for all MBBs");
8006f32e7eSjoerg const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
8106f32e7eSjoerg // Incoming is null if this is a backedge from a BB
8206f32e7eSjoerg // we haven't processed yet
8306f32e7eSjoerg if (Incoming.empty())
8406f32e7eSjoerg continue;
8506f32e7eSjoerg
86*da58b97aSjoerg // Find the most recent reaching definition from a predecessor.
87*da58b97aSjoerg for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
8806f32e7eSjoerg LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
89*da58b97aSjoerg }
90*da58b97aSjoerg
91*da58b97aSjoerg // Insert the most recent reaching definition we found.
92*da58b97aSjoerg for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
93*da58b97aSjoerg if (LiveRegs[Unit] != ReachingDefDefaultVal)
9406f32e7eSjoerg MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
9506f32e7eSjoerg }
9606f32e7eSjoerg
leaveBasicBlock(MachineBasicBlock * MBB)97*da58b97aSjoerg void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) {
9806f32e7eSjoerg assert(!LiveRegs.empty() && "Must enter basic block first.");
99*da58b97aSjoerg unsigned MBBNumber = MBB->getNumber();
10006f32e7eSjoerg assert(MBBNumber < MBBOutRegsInfos.size() &&
10106f32e7eSjoerg "Unexpected basic block number.");
10206f32e7eSjoerg // Save register clearances at end of MBB - used by enterBasicBlock().
10306f32e7eSjoerg MBBOutRegsInfos[MBBNumber] = LiveRegs;
10406f32e7eSjoerg
10506f32e7eSjoerg // While processing the basic block, we kept `Def` relative to the start
10606f32e7eSjoerg // of the basic block for convenience. However, future use of this information
10706f32e7eSjoerg // only cares about the clearance from the end of the block, so adjust
10806f32e7eSjoerg // everything to be relative to the end of the basic block.
10906f32e7eSjoerg for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
110*da58b97aSjoerg if (OutLiveReg != ReachingDefDefaultVal)
11106f32e7eSjoerg OutLiveReg -= CurInstr;
11206f32e7eSjoerg LiveRegs.clear();
11306f32e7eSjoerg }
11406f32e7eSjoerg
processDefs(MachineInstr * MI)11506f32e7eSjoerg void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
11606f32e7eSjoerg assert(!MI->isDebugInstr() && "Won't process debug instructions");
11706f32e7eSjoerg
11806f32e7eSjoerg unsigned MBBNumber = MI->getParent()->getNumber();
11906f32e7eSjoerg assert(MBBNumber < MBBReachingDefs.size() &&
12006f32e7eSjoerg "Unexpected basic block number.");
121*da58b97aSjoerg
122*da58b97aSjoerg for (auto &MO : MI->operands()) {
123*da58b97aSjoerg if (!isValidRegDef(MO))
12406f32e7eSjoerg continue;
125*da58b97aSjoerg for (MCRegUnitIterator Unit(MO.getReg().asMCReg(), TRI); Unit.isValid();
126*da58b97aSjoerg ++Unit) {
12706f32e7eSjoerg // This instruction explicitly defines the current reg unit.
128*da58b97aSjoerg LLVM_DEBUG(dbgs() << printRegUnit(*Unit, TRI) << ":\t" << CurInstr
12906f32e7eSjoerg << '\t' << *MI);
13006f32e7eSjoerg
13106f32e7eSjoerg // How many instructions since this reg unit was last written?
132*da58b97aSjoerg if (LiveRegs[*Unit] != CurInstr) {
13306f32e7eSjoerg LiveRegs[*Unit] = CurInstr;
13406f32e7eSjoerg MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
13506f32e7eSjoerg }
13606f32e7eSjoerg }
137*da58b97aSjoerg }
13806f32e7eSjoerg InstIds[MI] = CurInstr;
13906f32e7eSjoerg ++CurInstr;
14006f32e7eSjoerg }
14106f32e7eSjoerg
reprocessBasicBlock(MachineBasicBlock * MBB)142*da58b97aSjoerg void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
143*da58b97aSjoerg unsigned MBBNumber = MBB->getNumber();
144*da58b97aSjoerg assert(MBBNumber < MBBReachingDefs.size() &&
145*da58b97aSjoerg "Unexpected basic block number.");
146*da58b97aSjoerg
147*da58b97aSjoerg // Count number of non-debug instructions for end of block adjustment.
148*da58b97aSjoerg auto NonDbgInsts =
149*da58b97aSjoerg instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end());
150*da58b97aSjoerg int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
151*da58b97aSjoerg
152*da58b97aSjoerg // When reprocessing a block, the only thing we need to do is check whether
153*da58b97aSjoerg // there is now a more recent incoming reaching definition from a predecessor.
154*da58b97aSjoerg for (MachineBasicBlock *pred : MBB->predecessors()) {
155*da58b97aSjoerg assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
156*da58b97aSjoerg "Should have pre-allocated MBBInfos for all MBBs");
157*da58b97aSjoerg const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
158*da58b97aSjoerg // Incoming may be empty for dead predecessors.
159*da58b97aSjoerg if (Incoming.empty())
160*da58b97aSjoerg continue;
161*da58b97aSjoerg
162*da58b97aSjoerg for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
163*da58b97aSjoerg int Def = Incoming[Unit];
164*da58b97aSjoerg if (Def == ReachingDefDefaultVal)
165*da58b97aSjoerg continue;
166*da58b97aSjoerg
167*da58b97aSjoerg auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
168*da58b97aSjoerg if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
169*da58b97aSjoerg if (*Start >= Def)
170*da58b97aSjoerg continue;
171*da58b97aSjoerg
172*da58b97aSjoerg // Update existing reaching def from predecessor to a more recent one.
173*da58b97aSjoerg *Start = Def;
174*da58b97aSjoerg } else {
175*da58b97aSjoerg // Insert new reaching def from predecessor.
176*da58b97aSjoerg MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
177*da58b97aSjoerg }
178*da58b97aSjoerg
179*da58b97aSjoerg // Update reaching def at end of of BB. Keep in mind that these are
180*da58b97aSjoerg // adjusted relative to the end of the basic block.
181*da58b97aSjoerg if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
182*da58b97aSjoerg MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
183*da58b97aSjoerg }
184*da58b97aSjoerg }
185*da58b97aSjoerg }
186*da58b97aSjoerg
processBasicBlock(const LoopTraversal::TraversedMBBInfo & TraversedMBB)18706f32e7eSjoerg void ReachingDefAnalysis::processBasicBlock(
18806f32e7eSjoerg const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
189*da58b97aSjoerg MachineBasicBlock *MBB = TraversedMBB.MBB;
190*da58b97aSjoerg LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
191*da58b97aSjoerg << (!TraversedMBB.IsDone ? ": incomplete\n"
192*da58b97aSjoerg : ": all preds known\n"));
193*da58b97aSjoerg
194*da58b97aSjoerg if (!TraversedMBB.PrimaryPass) {
195*da58b97aSjoerg // Reprocess MBB that is part of a loop.
196*da58b97aSjoerg reprocessBasicBlock(MBB);
197*da58b97aSjoerg return;
19806f32e7eSjoerg }
199*da58b97aSjoerg
200*da58b97aSjoerg enterBasicBlock(MBB);
201*da58b97aSjoerg for (MachineInstr &MI :
202*da58b97aSjoerg instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end()))
203*da58b97aSjoerg processDefs(&MI);
204*da58b97aSjoerg leaveBasicBlock(MBB);
20506f32e7eSjoerg }
20606f32e7eSjoerg
runOnMachineFunction(MachineFunction & mf)20706f32e7eSjoerg bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
20806f32e7eSjoerg MF = &mf;
20906f32e7eSjoerg TRI = MF->getSubtarget().getRegisterInfo();
21006f32e7eSjoerg LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
211*da58b97aSjoerg init();
212*da58b97aSjoerg traverse();
21306f32e7eSjoerg return false;
21406f32e7eSjoerg }
21506f32e7eSjoerg
releaseMemory()21606f32e7eSjoerg void ReachingDefAnalysis::releaseMemory() {
21706f32e7eSjoerg // Clear the internal vectors.
21806f32e7eSjoerg MBBOutRegsInfos.clear();
21906f32e7eSjoerg MBBReachingDefs.clear();
22006f32e7eSjoerg InstIds.clear();
221*da58b97aSjoerg LiveRegs.clear();
22206f32e7eSjoerg }
22306f32e7eSjoerg
reset()224*da58b97aSjoerg void ReachingDefAnalysis::reset() {
225*da58b97aSjoerg releaseMemory();
226*da58b97aSjoerg init();
227*da58b97aSjoerg traverse();
228*da58b97aSjoerg }
229*da58b97aSjoerg
init()230*da58b97aSjoerg void ReachingDefAnalysis::init() {
231*da58b97aSjoerg NumRegUnits = TRI->getNumRegUnits();
232*da58b97aSjoerg MBBReachingDefs.resize(MF->getNumBlockIDs());
233*da58b97aSjoerg // Initialize the MBBOutRegsInfos
234*da58b97aSjoerg MBBOutRegsInfos.resize(MF->getNumBlockIDs());
235*da58b97aSjoerg LoopTraversal Traversal;
236*da58b97aSjoerg TraversedMBBOrder = Traversal.traverse(*MF);
237*da58b97aSjoerg }
238*da58b97aSjoerg
traverse()239*da58b97aSjoerg void ReachingDefAnalysis::traverse() {
240*da58b97aSjoerg // Traverse the basic blocks.
241*da58b97aSjoerg for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
242*da58b97aSjoerg processBasicBlock(TraversedMBB);
243*da58b97aSjoerg #ifndef NDEBUG
244*da58b97aSjoerg // Make sure reaching defs are sorted and unique.
245*da58b97aSjoerg for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
246*da58b97aSjoerg for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
247*da58b97aSjoerg int LastDef = ReachingDefDefaultVal;
248*da58b97aSjoerg for (int Def : RegUnitDefs) {
249*da58b97aSjoerg assert(Def > LastDef && "Defs must be sorted and unique");
250*da58b97aSjoerg LastDef = Def;
251*da58b97aSjoerg }
252*da58b97aSjoerg }
253*da58b97aSjoerg }
254*da58b97aSjoerg #endif
255*da58b97aSjoerg }
256*da58b97aSjoerg
getReachingDef(MachineInstr * MI,MCRegister PhysReg) const257*da58b97aSjoerg int ReachingDefAnalysis::getReachingDef(MachineInstr *MI,
258*da58b97aSjoerg MCRegister PhysReg) const {
25906f32e7eSjoerg assert(InstIds.count(MI) && "Unexpected machine instuction.");
260*da58b97aSjoerg int InstId = InstIds.lookup(MI);
26106f32e7eSjoerg int DefRes = ReachingDefDefaultVal;
26206f32e7eSjoerg unsigned MBBNumber = MI->getParent()->getNumber();
26306f32e7eSjoerg assert(MBBNumber < MBBReachingDefs.size() &&
26406f32e7eSjoerg "Unexpected basic block number.");
26506f32e7eSjoerg int LatestDef = ReachingDefDefaultVal;
26606f32e7eSjoerg for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
26706f32e7eSjoerg for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
26806f32e7eSjoerg if (Def >= InstId)
26906f32e7eSjoerg break;
27006f32e7eSjoerg DefRes = Def;
27106f32e7eSjoerg }
27206f32e7eSjoerg LatestDef = std::max(LatestDef, DefRes);
27306f32e7eSjoerg }
27406f32e7eSjoerg return LatestDef;
27506f32e7eSjoerg }
27606f32e7eSjoerg
277*da58b97aSjoerg MachineInstr *
getReachingLocalMIDef(MachineInstr * MI,MCRegister PhysReg) const278*da58b97aSjoerg ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
279*da58b97aSjoerg MCRegister PhysReg) const {
280*da58b97aSjoerg return hasLocalDefBefore(MI, PhysReg)
281*da58b97aSjoerg ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg))
282*da58b97aSjoerg : nullptr;
283*da58b97aSjoerg }
284*da58b97aSjoerg
hasSameReachingDef(MachineInstr * A,MachineInstr * B,MCRegister PhysReg) const285*da58b97aSjoerg bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
286*da58b97aSjoerg MCRegister PhysReg) const {
287*da58b97aSjoerg MachineBasicBlock *ParentA = A->getParent();
288*da58b97aSjoerg MachineBasicBlock *ParentB = B->getParent();
289*da58b97aSjoerg if (ParentA != ParentB)
290*da58b97aSjoerg return false;
291*da58b97aSjoerg
292*da58b97aSjoerg return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
293*da58b97aSjoerg }
294*da58b97aSjoerg
getInstFromId(MachineBasicBlock * MBB,int InstId) const295*da58b97aSjoerg MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
296*da58b97aSjoerg int InstId) const {
297*da58b97aSjoerg assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
298*da58b97aSjoerg "Unexpected basic block number.");
299*da58b97aSjoerg assert(InstId < static_cast<int>(MBB->size()) &&
300*da58b97aSjoerg "Unexpected instruction id.");
301*da58b97aSjoerg
302*da58b97aSjoerg if (InstId < 0)
303*da58b97aSjoerg return nullptr;
304*da58b97aSjoerg
305*da58b97aSjoerg for (auto &MI : *MBB) {
306*da58b97aSjoerg auto F = InstIds.find(&MI);
307*da58b97aSjoerg if (F != InstIds.end() && F->second == InstId)
308*da58b97aSjoerg return &MI;
309*da58b97aSjoerg }
310*da58b97aSjoerg
311*da58b97aSjoerg return nullptr;
312*da58b97aSjoerg }
313*da58b97aSjoerg
getClearance(MachineInstr * MI,MCRegister PhysReg) const314*da58b97aSjoerg int ReachingDefAnalysis::getClearance(MachineInstr *MI,
315*da58b97aSjoerg MCRegister PhysReg) const {
31606f32e7eSjoerg assert(InstIds.count(MI) && "Unexpected machine instuction.");
317*da58b97aSjoerg return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
318*da58b97aSjoerg }
319*da58b97aSjoerg
hasLocalDefBefore(MachineInstr * MI,MCRegister PhysReg) const320*da58b97aSjoerg bool ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI,
321*da58b97aSjoerg MCRegister PhysReg) const {
322*da58b97aSjoerg return getReachingDef(MI, PhysReg) >= 0;
323*da58b97aSjoerg }
324*da58b97aSjoerg
getReachingLocalUses(MachineInstr * Def,MCRegister PhysReg,InstSet & Uses) const325*da58b97aSjoerg void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def,
326*da58b97aSjoerg MCRegister PhysReg,
327*da58b97aSjoerg InstSet &Uses) const {
328*da58b97aSjoerg MachineBasicBlock *MBB = Def->getParent();
329*da58b97aSjoerg MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
330*da58b97aSjoerg while (++MI != MBB->end()) {
331*da58b97aSjoerg if (MI->isDebugInstr())
332*da58b97aSjoerg continue;
333*da58b97aSjoerg
334*da58b97aSjoerg // If/when we find a new reaching def, we know that there's no more uses
335*da58b97aSjoerg // of 'Def'.
336*da58b97aSjoerg if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
337*da58b97aSjoerg return;
338*da58b97aSjoerg
339*da58b97aSjoerg for (auto &MO : MI->operands()) {
340*da58b97aSjoerg if (!isValidRegUseOf(MO, PhysReg))
341*da58b97aSjoerg continue;
342*da58b97aSjoerg
343*da58b97aSjoerg Uses.insert(&*MI);
344*da58b97aSjoerg if (MO.isKill())
345*da58b97aSjoerg return;
346*da58b97aSjoerg }
347*da58b97aSjoerg }
348*da58b97aSjoerg }
349*da58b97aSjoerg
getLiveInUses(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Uses) const350*da58b97aSjoerg bool ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB,
351*da58b97aSjoerg MCRegister PhysReg,
352*da58b97aSjoerg InstSet &Uses) const {
353*da58b97aSjoerg for (MachineInstr &MI :
354*da58b97aSjoerg instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end())) {
355*da58b97aSjoerg for (auto &MO : MI.operands()) {
356*da58b97aSjoerg if (!isValidRegUseOf(MO, PhysReg))
357*da58b97aSjoerg continue;
358*da58b97aSjoerg if (getReachingDef(&MI, PhysReg) >= 0)
359*da58b97aSjoerg return false;
360*da58b97aSjoerg Uses.insert(&MI);
361*da58b97aSjoerg }
362*da58b97aSjoerg }
363*da58b97aSjoerg auto Last = MBB->getLastNonDebugInstr();
364*da58b97aSjoerg if (Last == MBB->end())
365*da58b97aSjoerg return true;
366*da58b97aSjoerg return isReachingDefLiveOut(&*Last, PhysReg);
367*da58b97aSjoerg }
368*da58b97aSjoerg
getGlobalUses(MachineInstr * MI,MCRegister PhysReg,InstSet & Uses) const369*da58b97aSjoerg void ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, MCRegister PhysReg,
370*da58b97aSjoerg InstSet &Uses) const {
371*da58b97aSjoerg MachineBasicBlock *MBB = MI->getParent();
372*da58b97aSjoerg
373*da58b97aSjoerg // Collect the uses that each def touches within the block.
374*da58b97aSjoerg getReachingLocalUses(MI, PhysReg, Uses);
375*da58b97aSjoerg
376*da58b97aSjoerg // Handle live-out values.
377*da58b97aSjoerg if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
378*da58b97aSjoerg if (LiveOut != MI)
379*da58b97aSjoerg return;
380*da58b97aSjoerg
381*da58b97aSjoerg SmallVector<MachineBasicBlock *, 4> ToVisit(MBB->successors());
382*da58b97aSjoerg SmallPtrSet<MachineBasicBlock*, 4>Visited;
383*da58b97aSjoerg while (!ToVisit.empty()) {
384*da58b97aSjoerg MachineBasicBlock *MBB = ToVisit.back();
385*da58b97aSjoerg ToVisit.pop_back();
386*da58b97aSjoerg if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
387*da58b97aSjoerg continue;
388*da58b97aSjoerg if (getLiveInUses(MBB, PhysReg, Uses))
389*da58b97aSjoerg llvm::append_range(ToVisit, MBB->successors());
390*da58b97aSjoerg Visited.insert(MBB);
391*da58b97aSjoerg }
392*da58b97aSjoerg }
393*da58b97aSjoerg }
394*da58b97aSjoerg
getGlobalReachingDefs(MachineInstr * MI,MCRegister PhysReg,InstSet & Defs) const395*da58b97aSjoerg void ReachingDefAnalysis::getGlobalReachingDefs(MachineInstr *MI,
396*da58b97aSjoerg MCRegister PhysReg,
397*da58b97aSjoerg InstSet &Defs) const {
398*da58b97aSjoerg if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
399*da58b97aSjoerg Defs.insert(Def);
400*da58b97aSjoerg return;
401*da58b97aSjoerg }
402*da58b97aSjoerg
403*da58b97aSjoerg for (auto *MBB : MI->getParent()->predecessors())
404*da58b97aSjoerg getLiveOuts(MBB, PhysReg, Defs);
405*da58b97aSjoerg }
406*da58b97aSjoerg
getLiveOuts(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Defs) const407*da58b97aSjoerg void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
408*da58b97aSjoerg MCRegister PhysReg, InstSet &Defs) const {
409*da58b97aSjoerg SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
410*da58b97aSjoerg getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
411*da58b97aSjoerg }
412*da58b97aSjoerg
getLiveOuts(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Defs,BlockSet & VisitedBBs) const413*da58b97aSjoerg void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
414*da58b97aSjoerg MCRegister PhysReg, InstSet &Defs,
415*da58b97aSjoerg BlockSet &VisitedBBs) const {
416*da58b97aSjoerg if (VisitedBBs.count(MBB))
417*da58b97aSjoerg return;
418*da58b97aSjoerg
419*da58b97aSjoerg VisitedBBs.insert(MBB);
420*da58b97aSjoerg LivePhysRegs LiveRegs(*TRI);
421*da58b97aSjoerg LiveRegs.addLiveOuts(*MBB);
422*da58b97aSjoerg if (!LiveRegs.contains(PhysReg))
423*da58b97aSjoerg return;
424*da58b97aSjoerg
425*da58b97aSjoerg if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
426*da58b97aSjoerg Defs.insert(Def);
427*da58b97aSjoerg else
428*da58b97aSjoerg for (auto *Pred : MBB->predecessors())
429*da58b97aSjoerg getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
430*da58b97aSjoerg }
431*da58b97aSjoerg
432*da58b97aSjoerg MachineInstr *
getUniqueReachingMIDef(MachineInstr * MI,MCRegister PhysReg) const433*da58b97aSjoerg ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
434*da58b97aSjoerg MCRegister PhysReg) const {
435*da58b97aSjoerg // If there's a local def before MI, return it.
436*da58b97aSjoerg MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
437*da58b97aSjoerg if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
438*da58b97aSjoerg return LocalDef;
439*da58b97aSjoerg
440*da58b97aSjoerg SmallPtrSet<MachineInstr*, 2> Incoming;
441*da58b97aSjoerg MachineBasicBlock *Parent = MI->getParent();
442*da58b97aSjoerg for (auto *Pred : Parent->predecessors())
443*da58b97aSjoerg getLiveOuts(Pred, PhysReg, Incoming);
444*da58b97aSjoerg
445*da58b97aSjoerg // Check that we have a single incoming value and that it does not
446*da58b97aSjoerg // come from the same block as MI - since it would mean that the def
447*da58b97aSjoerg // is executed after MI.
448*da58b97aSjoerg if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
449*da58b97aSjoerg return *Incoming.begin();
450*da58b97aSjoerg return nullptr;
451*da58b97aSjoerg }
452*da58b97aSjoerg
getMIOperand(MachineInstr * MI,unsigned Idx) const453*da58b97aSjoerg MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
454*da58b97aSjoerg unsigned Idx) const {
455*da58b97aSjoerg assert(MI->getOperand(Idx).isReg() && "Expected register operand");
456*da58b97aSjoerg return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
457*da58b97aSjoerg }
458*da58b97aSjoerg
getMIOperand(MachineInstr * MI,MachineOperand & MO) const459*da58b97aSjoerg MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
460*da58b97aSjoerg MachineOperand &MO) const {
461*da58b97aSjoerg assert(MO.isReg() && "Expected register operand");
462*da58b97aSjoerg return getUniqueReachingMIDef(MI, MO.getReg());
463*da58b97aSjoerg }
464*da58b97aSjoerg
isRegUsedAfter(MachineInstr * MI,MCRegister PhysReg) const465*da58b97aSjoerg bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI,
466*da58b97aSjoerg MCRegister PhysReg) const {
467*da58b97aSjoerg MachineBasicBlock *MBB = MI->getParent();
468*da58b97aSjoerg LivePhysRegs LiveRegs(*TRI);
469*da58b97aSjoerg LiveRegs.addLiveOuts(*MBB);
470*da58b97aSjoerg
471*da58b97aSjoerg // Yes if the register is live out of the basic block.
472*da58b97aSjoerg if (LiveRegs.contains(PhysReg))
473*da58b97aSjoerg return true;
474*da58b97aSjoerg
475*da58b97aSjoerg // Walk backwards through the block to see if the register is live at some
476*da58b97aSjoerg // point.
477*da58b97aSjoerg for (MachineInstr &Last :
478*da58b97aSjoerg instructionsWithoutDebug(MBB->instr_rbegin(), MBB->instr_rend())) {
479*da58b97aSjoerg LiveRegs.stepBackward(Last);
480*da58b97aSjoerg if (LiveRegs.contains(PhysReg))
481*da58b97aSjoerg return InstIds.lookup(&Last) > InstIds.lookup(MI);
482*da58b97aSjoerg }
483*da58b97aSjoerg return false;
484*da58b97aSjoerg }
485*da58b97aSjoerg
isRegDefinedAfter(MachineInstr * MI,MCRegister PhysReg) const486*da58b97aSjoerg bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
487*da58b97aSjoerg MCRegister PhysReg) const {
488*da58b97aSjoerg MachineBasicBlock *MBB = MI->getParent();
489*da58b97aSjoerg auto Last = MBB->getLastNonDebugInstr();
490*da58b97aSjoerg if (Last != MBB->end() &&
491*da58b97aSjoerg getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
492*da58b97aSjoerg return true;
493*da58b97aSjoerg
494*da58b97aSjoerg if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
495*da58b97aSjoerg return Def == getReachingLocalMIDef(MI, PhysReg);
496*da58b97aSjoerg
497*da58b97aSjoerg return false;
498*da58b97aSjoerg }
499*da58b97aSjoerg
isReachingDefLiveOut(MachineInstr * MI,MCRegister PhysReg) const500*da58b97aSjoerg bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI,
501*da58b97aSjoerg MCRegister PhysReg) const {
502*da58b97aSjoerg MachineBasicBlock *MBB = MI->getParent();
503*da58b97aSjoerg LivePhysRegs LiveRegs(*TRI);
504*da58b97aSjoerg LiveRegs.addLiveOuts(*MBB);
505*da58b97aSjoerg if (!LiveRegs.contains(PhysReg))
506*da58b97aSjoerg return false;
507*da58b97aSjoerg
508*da58b97aSjoerg auto Last = MBB->getLastNonDebugInstr();
509*da58b97aSjoerg int Def = getReachingDef(MI, PhysReg);
510*da58b97aSjoerg if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
511*da58b97aSjoerg return false;
512*da58b97aSjoerg
513*da58b97aSjoerg // Finally check that the last instruction doesn't redefine the register.
514*da58b97aSjoerg for (auto &MO : Last->operands())
515*da58b97aSjoerg if (isValidRegDefOf(MO, PhysReg))
516*da58b97aSjoerg return false;
517*da58b97aSjoerg
518*da58b97aSjoerg return true;
519*da58b97aSjoerg }
520*da58b97aSjoerg
521*da58b97aSjoerg MachineInstr *
getLocalLiveOutMIDef(MachineBasicBlock * MBB,MCRegister PhysReg) const522*da58b97aSjoerg ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
523*da58b97aSjoerg MCRegister PhysReg) const {
524*da58b97aSjoerg LivePhysRegs LiveRegs(*TRI);
525*da58b97aSjoerg LiveRegs.addLiveOuts(*MBB);
526*da58b97aSjoerg if (!LiveRegs.contains(PhysReg))
527*da58b97aSjoerg return nullptr;
528*da58b97aSjoerg
529*da58b97aSjoerg auto Last = MBB->getLastNonDebugInstr();
530*da58b97aSjoerg if (Last == MBB->end())
531*da58b97aSjoerg return nullptr;
532*da58b97aSjoerg
533*da58b97aSjoerg int Def = getReachingDef(&*Last, PhysReg);
534*da58b97aSjoerg for (auto &MO : Last->operands())
535*da58b97aSjoerg if (isValidRegDefOf(MO, PhysReg))
536*da58b97aSjoerg return &*Last;
537*da58b97aSjoerg
538*da58b97aSjoerg return Def < 0 ? nullptr : getInstFromId(MBB, Def);
539*da58b97aSjoerg }
540*da58b97aSjoerg
mayHaveSideEffects(MachineInstr & MI)541*da58b97aSjoerg static bool mayHaveSideEffects(MachineInstr &MI) {
542*da58b97aSjoerg return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
543*da58b97aSjoerg MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
544*da58b97aSjoerg MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
545*da58b97aSjoerg }
546*da58b97aSjoerg
547*da58b97aSjoerg // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
548*da58b97aSjoerg // not define a register that is used by any instructions, after and including,
549*da58b97aSjoerg // 'To'. These instructions also must not redefine any of Froms operands.
550*da58b97aSjoerg template<typename Iterator>
isSafeToMove(MachineInstr * From,MachineInstr * To) const551*da58b97aSjoerg bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
552*da58b97aSjoerg MachineInstr *To) const {
553*da58b97aSjoerg if (From->getParent() != To->getParent() || From == To)
554*da58b97aSjoerg return false;
555*da58b97aSjoerg
556*da58b97aSjoerg SmallSet<int, 2> Defs;
557*da58b97aSjoerg // First check that From would compute the same value if moved.
558*da58b97aSjoerg for (auto &MO : From->operands()) {
559*da58b97aSjoerg if (!isValidReg(MO))
560*da58b97aSjoerg continue;
561*da58b97aSjoerg if (MO.isDef())
562*da58b97aSjoerg Defs.insert(MO.getReg());
563*da58b97aSjoerg else if (!hasSameReachingDef(From, To, MO.getReg()))
564*da58b97aSjoerg return false;
565*da58b97aSjoerg }
566*da58b97aSjoerg
567*da58b97aSjoerg // Now walk checking that the rest of the instructions will compute the same
568*da58b97aSjoerg // value and that we're not overwriting anything. Don't move the instruction
569*da58b97aSjoerg // past any memory, control-flow or other ambiguous instructions.
570*da58b97aSjoerg for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
571*da58b97aSjoerg if (mayHaveSideEffects(*I))
572*da58b97aSjoerg return false;
573*da58b97aSjoerg for (auto &MO : I->operands())
574*da58b97aSjoerg if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
575*da58b97aSjoerg return false;
576*da58b97aSjoerg }
577*da58b97aSjoerg return true;
578*da58b97aSjoerg }
579*da58b97aSjoerg
isSafeToMoveForwards(MachineInstr * From,MachineInstr * To) const580*da58b97aSjoerg bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
581*da58b97aSjoerg MachineInstr *To) const {
582*da58b97aSjoerg using Iterator = MachineBasicBlock::iterator;
583*da58b97aSjoerg // Walk forwards until we find the instruction.
584*da58b97aSjoerg for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
585*da58b97aSjoerg if (&*I == To)
586*da58b97aSjoerg return isSafeToMove<Iterator>(From, To);
587*da58b97aSjoerg return false;
588*da58b97aSjoerg }
589*da58b97aSjoerg
isSafeToMoveBackwards(MachineInstr * From,MachineInstr * To) const590*da58b97aSjoerg bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
591*da58b97aSjoerg MachineInstr *To) const {
592*da58b97aSjoerg using Iterator = MachineBasicBlock::reverse_iterator;
593*da58b97aSjoerg // Walk backwards until we find the instruction.
594*da58b97aSjoerg for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
595*da58b97aSjoerg if (&*I == To)
596*da58b97aSjoerg return isSafeToMove<Iterator>(From, To);
597*da58b97aSjoerg return false;
598*da58b97aSjoerg }
599*da58b97aSjoerg
isSafeToRemove(MachineInstr * MI,InstSet & ToRemove) const600*da58b97aSjoerg bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
601*da58b97aSjoerg InstSet &ToRemove) const {
602*da58b97aSjoerg SmallPtrSet<MachineInstr*, 1> Ignore;
603*da58b97aSjoerg SmallPtrSet<MachineInstr*, 2> Visited;
604*da58b97aSjoerg return isSafeToRemove(MI, Visited, ToRemove, Ignore);
605*da58b97aSjoerg }
606*da58b97aSjoerg
607*da58b97aSjoerg bool
isSafeToRemove(MachineInstr * MI,InstSet & ToRemove,InstSet & Ignore) const608*da58b97aSjoerg ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
609*da58b97aSjoerg InstSet &Ignore) const {
610*da58b97aSjoerg SmallPtrSet<MachineInstr*, 2> Visited;
611*da58b97aSjoerg return isSafeToRemove(MI, Visited, ToRemove, Ignore);
612*da58b97aSjoerg }
613*da58b97aSjoerg
614*da58b97aSjoerg bool
isSafeToRemove(MachineInstr * MI,InstSet & Visited,InstSet & ToRemove,InstSet & Ignore) const615*da58b97aSjoerg ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
616*da58b97aSjoerg InstSet &ToRemove, InstSet &Ignore) const {
617*da58b97aSjoerg if (Visited.count(MI) || Ignore.count(MI))
618*da58b97aSjoerg return true;
619*da58b97aSjoerg else if (mayHaveSideEffects(*MI)) {
620*da58b97aSjoerg // Unless told to ignore the instruction, don't remove anything which has
621*da58b97aSjoerg // side effects.
622*da58b97aSjoerg return false;
623*da58b97aSjoerg }
624*da58b97aSjoerg
625*da58b97aSjoerg Visited.insert(MI);
626*da58b97aSjoerg for (auto &MO : MI->operands()) {
627*da58b97aSjoerg if (!isValidRegDef(MO))
628*da58b97aSjoerg continue;
629*da58b97aSjoerg
630*da58b97aSjoerg SmallPtrSet<MachineInstr*, 4> Uses;
631*da58b97aSjoerg getGlobalUses(MI, MO.getReg(), Uses);
632*da58b97aSjoerg
633*da58b97aSjoerg for (auto I : Uses) {
634*da58b97aSjoerg if (Ignore.count(I) || ToRemove.count(I))
635*da58b97aSjoerg continue;
636*da58b97aSjoerg if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
637*da58b97aSjoerg return false;
638*da58b97aSjoerg }
639*da58b97aSjoerg }
640*da58b97aSjoerg ToRemove.insert(MI);
641*da58b97aSjoerg return true;
642*da58b97aSjoerg }
643*da58b97aSjoerg
collectKilledOperands(MachineInstr * MI,InstSet & Dead) const644*da58b97aSjoerg void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
645*da58b97aSjoerg InstSet &Dead) const {
646*da58b97aSjoerg Dead.insert(MI);
647*da58b97aSjoerg auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
648*da58b97aSjoerg if (mayHaveSideEffects(*Def))
649*da58b97aSjoerg return false;
650*da58b97aSjoerg
651*da58b97aSjoerg unsigned LiveDefs = 0;
652*da58b97aSjoerg for (auto &MO : Def->operands()) {
653*da58b97aSjoerg if (!isValidRegDef(MO))
654*da58b97aSjoerg continue;
655*da58b97aSjoerg if (!MO.isDead())
656*da58b97aSjoerg ++LiveDefs;
657*da58b97aSjoerg }
658*da58b97aSjoerg
659*da58b97aSjoerg if (LiveDefs > 1)
660*da58b97aSjoerg return false;
661*da58b97aSjoerg
662*da58b97aSjoerg SmallPtrSet<MachineInstr*, 4> Uses;
663*da58b97aSjoerg getGlobalUses(Def, PhysReg, Uses);
664*da58b97aSjoerg return llvm::set_is_subset(Uses, Dead);
665*da58b97aSjoerg };
666*da58b97aSjoerg
667*da58b97aSjoerg for (auto &MO : MI->operands()) {
668*da58b97aSjoerg if (!isValidRegUse(MO))
669*da58b97aSjoerg continue;
670*da58b97aSjoerg if (MachineInstr *Def = getMIOperand(MI, MO))
671*da58b97aSjoerg if (IsDead(Def, MO.getReg()))
672*da58b97aSjoerg collectKilledOperands(Def, Dead);
673*da58b97aSjoerg }
674*da58b97aSjoerg }
675*da58b97aSjoerg
isSafeToDefRegAt(MachineInstr * MI,MCRegister PhysReg) const676*da58b97aSjoerg bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
677*da58b97aSjoerg MCRegister PhysReg) const {
678*da58b97aSjoerg SmallPtrSet<MachineInstr*, 1> Ignore;
679*da58b97aSjoerg return isSafeToDefRegAt(MI, PhysReg, Ignore);
680*da58b97aSjoerg }
681*da58b97aSjoerg
isSafeToDefRegAt(MachineInstr * MI,MCRegister PhysReg,InstSet & Ignore) const682*da58b97aSjoerg bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg,
683*da58b97aSjoerg InstSet &Ignore) const {
684*da58b97aSjoerg // Check for any uses of the register after MI.
685*da58b97aSjoerg if (isRegUsedAfter(MI, PhysReg)) {
686*da58b97aSjoerg if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
687*da58b97aSjoerg SmallPtrSet<MachineInstr*, 2> Uses;
688*da58b97aSjoerg getGlobalUses(Def, PhysReg, Uses);
689*da58b97aSjoerg if (!llvm::set_is_subset(Uses, Ignore))
690*da58b97aSjoerg return false;
691*da58b97aSjoerg } else
692*da58b97aSjoerg return false;
693*da58b97aSjoerg }
694*da58b97aSjoerg
695*da58b97aSjoerg MachineBasicBlock *MBB = MI->getParent();
696*da58b97aSjoerg // Check for any defs after MI.
697*da58b97aSjoerg if (isRegDefinedAfter(MI, PhysReg)) {
698*da58b97aSjoerg auto I = MachineBasicBlock::iterator(MI);
699*da58b97aSjoerg for (auto E = MBB->end(); I != E; ++I) {
700*da58b97aSjoerg if (Ignore.count(&*I))
701*da58b97aSjoerg continue;
702*da58b97aSjoerg for (auto &MO : I->operands())
703*da58b97aSjoerg if (isValidRegDefOf(MO, PhysReg))
704*da58b97aSjoerg return false;
705*da58b97aSjoerg }
706*da58b97aSjoerg }
707*da58b97aSjoerg return true;
70806f32e7eSjoerg }
709