1
2//===----------------- HexagonLiveVariables.cpp ---------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9// Hexagon Live Variable Analysis
10// This file implements the Hexagon specific LiveVariables analysis pass.
11// This pass recomputes physical register liveness and updates live-ins for
12// non-entry blocks based on use/def information.
13//===----------------------------------------------------------------------===//
14#define DEBUG_TYPE "hexagon_live_vars"
15
16#include "HexagonLiveVariables.h"
17#include "HexagonTargetMachine.h"
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/CodeGen/MachinePostDominators.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/CodeGen/Passes.h"
22#include "llvm/InitializePasses.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/ErrorHandling.h"
25
26using namespace llvm;
27
28char HexagonLiveVariables::ID = 0;
29char &llvm::HexagonLiveVariablesID = HexagonLiveVariables::ID;
30
31INITIALIZE_PASS(HexagonLiveVariables, "hexagon-live-vars",
32 "Hexagon Live Variable Analysis", false, false)
33
34// TODO: Establish a protocol to handle liveness of predicated instructions.
35// Liveness for predicated instruction is a little convoluted.
36// TODO: In PhysRegDef and PhysRegUse, use a bit vector instead of 126 elems.
37class HexagonLiveVariablesImpl {
38 // Intermediate data structures
39 friend class llvm::HexagonLiveVariables;
40 typedef MachineBasicBlock::const_instr_iterator MICInstIterType;
41
42 MachineFunction *MF;
43
44 MachineRegisterInfo *MRI;
45
46 const TargetRegisterInfo *TRI;
47
48 const HexagonInstrInfo *QII;
49
50 unsigned NumRegs;
51
52 /// PhysRegInfo - Keep track of which instruction was the last def of a
53 /// physical register (possibly after a use). This is purely local to a BB.
54 SmallVector<MachineInstr *, 0> PhysRegDef;
55
56 /// PhysRegInfo - Keep track of which instruction was the last use of a
57 /// physical register (before any def). This is purely local property to a BB.
58 SmallVector<MachineInstr *, 0> PhysRegUse;
59
60 /// MBB -> (Uses, Defs)
61 /// Uses - use before any def in that MBB.
62 /// Defs - def before any uses in that MBB.
63 MBBUseDef_t MBBUseDefs;
64
65 /// MI -> (Uses, Defs)
66 MIUseDef_t MIUseDefs;
67
68 /// Live-out data for each MBB => U LiveIns (For all Successors of a MBB).
69 DenseMap<const MachineBasicBlock *, BitVector> MBBLiveOuts;
70
71 /// Each MachineBasicBlock is assigned a Distance which is
72 /// an approximation of MBB->size()*INSTR_SIZE+Some offsets.
73 /// This is helpful in quickly finding distance between
74 /// a branch and its target.
75 /// @note A pass which moves instructions should update this.
76 /// @note The data in distance map should be used carefully because
77 /// difference in the distances of two MI might not give relative distances
78 /// between them. The DistanceMap is mainly useful during pullup.
79 DenseMap<const MachineBasicBlock *, unsigned> DistanceMap;
80
81 // Blocks in depth first order
82 SmallVector<MachineBasicBlock *, 16> BlocksDepthFirst;
83
84 /// @brief Constructs use-defs of \p MBB by analyzing each MachineOperand.
85 /// Collects relevant information so that global liveness can be updated.
86 void constructUseDef(MachineBasicBlock *MBB);
87
88 /// Collects used-before-define set of registers.
89 /// A register is considered to be completely defined if
90 /// 1. The register
91 /// 2. Any of its super-reg
92 /// 3. All of its subregs
93 /// are defined. In these cases the register is not considered as
94 /// used-before-defined. In case of partial definition of a register
95 /// before its use, only the remaining subregs are included in the use-set.
96 /// @note: Assumes that a register can be completely defined, by defining
97 /// all of its sub-regs (if any).
98 void handlePhysRegUse(MachineOperand *MO, MachineInstr *MI, BitVector &Uses);
99
100 /// Collects defined-before-use set of registers. If there is any
101 /// use of register or its aliases then the register is not counted
102 /// as defined-before-use
103 /// @note: Assumes that a register can be completely defined, by defining
104 /// all of its sub-regs (if any).
105 void handlePhysRegDef(MachineOperand *MO, MachineInstr *MI, BitVector &Defs);
106
107 /// updateGlobalLiveness - wrapper around another overload
108 inline bool updateGlobalLiveness(MachineFunction &Fn);
109 bool updateGlobalLiveness(MachineBasicBlock *X, MachineBasicBlock *Y);
110
111 /// updateGlobalLiveness - updates liveness based on
112 /// livein and liveout entries.
113 bool updateGlobalLiveness(MachineBasicBlock *MBB, BitVector &Defs,
114 BitVector &LiveIns);
115
116 /// update live-ins when live-out has been calculated
117 bool updateLiveIns(MachineBasicBlock *MBB, BitVector &LiveIns,
118 const BitVector &LiveOuts);
119
120 bool updateLiveOuts(MachineBasicBlock *MBB, BitVector &LiveOuts);
121
122 /// updateLocalLiveness - update only kill flags of operands.
123 inline bool updateLocalLiveness(MachineFunction &Fn);
124
125 /// updateLocalLiveness - update only kill flags of operands.
126 bool updateLocalLiveness(MachineBasicBlock *MBB, bool UpdateBundle);
127
128 /// incrementalUpdate - update the liveness when \p MIDelta is moved from
129 /// \p From to \p To.
130 /// @note: This is extremely fragile now. It 'assumes' that the other
131 /// successor(s) of \p To do not use Defs of MIDelta.
132 /// It deletes the live-in of the \p From MBB.
133 bool incrementalUpdate(MICInstIterType MIDelta, MachineBasicBlock *From,
134 MachineBasicBlock *To);
135
136 /// addNewMBB - inform the LiveVariable Analysis that new MBB has been added.
137 /// update the liveness of this new MBB.
138 /// @note MBB should be empty. If we want to add an MI, add it after calling
139 /// this function.
140 void addNewMBB(MachineBasicBlock *MBB);
141
142 void addNewMI(MachineInstr *MI, MachineBasicBlock *MBB);
143 unsigned getNumRegs() const { return NumRegs; }
144
145 // Useful for clearing out after passes which move instructions around.
146 // e.g. GlobalScheduler.
147 void clearDistanceMap() { DistanceMap.clear(); }
148
149 /// Computes \p DistanceMap.
150 void generateDistanceMap(const MachineFunction &Fn);
151
152public:
153 bool runOnMachineFunction(MachineFunction &Fn, MachineDominatorTree &MDT,
154 MachinePostDominatorTree &MPDT);
155};
156
157//===----------------------------------------------------------------------===//
158// HexagonLiveVariables Functions
159//===----------------------------------------------------------------------===//
160HexagonLiveVariables::HexagonLiveVariables()
161 : MachineFunctionPass(ID), HLVComplete(false),
162 HLV(std::make_unique<HexagonLiveVariablesImpl>()) {
163 initializeHexagonLiveVariablesPass(Registry&: *PassRegistry::getPassRegistry());
164}
165
166void HexagonLiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
167 AU.setPreservesCFG();
168 AU.addRequired<MachineDominatorTreeWrapperPass>();
169 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
170 AU.addPreserved(Arg: "packets");
171 MachineFunctionPass::getAnalysisUsage(AU);
172}
173
174void HexagonLiveVariables::recalculate(MachineFunction &MF) {
175 if (HLVComplete)
176 return;
177 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
178 auto &MPDT =
179 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
180 HLV->runOnMachineFunction(Fn&: MF, MDT, MPDT);
181}
182
183bool HexagonLiveVariables::updateLocalLiveness(MachineFunction &Fn) {
184 return HLV->updateLocalLiveness(Fn);
185}
186
187bool HexagonLiveVariables::updateLocalLiveness(MachineBasicBlock *MBB,
188 bool updateBundle) {
189 HLV->constructUseDef(MBB); // XXX: This destroys MBBLiveOuts!
190 return HLV->updateLocalLiveness(MBB, UpdateBundle: updateBundle);
191}
192
193bool HexagonLiveVariables::incrementalUpdate(MICInstIterType MIDelta,
194 MachineBasicBlock *From,
195 MachineBasicBlock *To) {
196 assert(MIDelta->getParent() == To);
197 assert(From != To);
198 return HLV->incrementalUpdate(MIDelta, From, To);
199}
200
201void HexagonLiveVariables::addNewMBB(MachineBasicBlock *MBB) {
202 assert(MBB->empty());
203 HLV->addNewMBB(MBB);
204}
205
206void HexagonLiveVariables::addNewMI(MachineInstr *MI, MachineBasicBlock *MBB) {
207 HLV->addNewMI(MI, MBB);
208}
209
210void HexagonLiveVariables::constructUseDef(MachineBasicBlock *MBB) {
211 HLV->constructUseDef(MBB);
212}
213
214bool HexagonLiveVariables::runOnMachineFunction(MachineFunction &Fn) {
215 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
216 auto &MPDT =
217 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
218 HLVComplete = !HLV->runOnMachineFunction(Fn, MDT, MPDT);
219 return HLVComplete;
220}
221
222bool HexagonLiveVariables::isLiveOut(const MachineBasicBlock *MBB,
223 unsigned Reg) const {
224 assert(HLVComplete && "Liveness Analysis not available");
225 auto It = HLV->MBBLiveOuts.find(Val: MBB);
226 if (It == HLV->MBBLiveOuts.end())
227 llvm_unreachable("MBB not found in liveness map");
228 if (Reg >= It->second.size())
229 llvm_unreachable("Register index out of bounds");
230 return It->second[Reg];
231}
232
233const BitVector &
234HexagonLiveVariables::getLiveOuts(const MachineBasicBlock *MBB) const {
235 assert(HLVComplete && "Liveness Analysis not available");
236 auto It = HLV->MBBLiveOuts.find(Val: MBB);
237 if (It == HLV->MBBLiveOuts.end())
238 llvm_unreachable("MBB not found in liveness map");
239 return It->second;
240}
241
242// Returns true when \p Reg is used within [MIBegin, MIEnd)
243// @note: MIBegin and MIEnd should be from same MBB
244// @note: It returns just the first use found in the range.
245// The Use is closest to MIEnd.
246// Takes care of aliases and predicated defs as well.
247bool HexagonLiveVariables::isUsedWithin(
248 MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg,
249 MICInstIterType &Use,
250 SmallPtrSet<MachineInstr *, 2> *ExceptionsList) const {
251 assert(HLVComplete && "Liveness Analysis not available");
252 Use = MIEnd;
253 if (MIBegin == MIEnd) // NULL Range.
254 return false;
255 MICInstIterType MII = MIEnd;
256 do {
257 --MII;
258 if (MII->isBundle() || MII->isDebugInstr())
259 continue;
260 if (ExceptionsList && ExceptionsList->contains(Ptr: &*MII))
261 continue;
262 auto It = HLV->MIUseDefs.find(Val: &*MII);
263 assert(It != HLV->MIUseDefs.end());
264 for (MCRegAliasIterator AI(Reg, HLV->TRI, true); AI.isValid(); ++AI)
265 if (It->second.first[*AI]) {
266 Use = MII;
267 return true;
268 }
269 } while (MII != MIBegin);
270 return false;
271}
272
273// Returns true when \p Reg id defined within [MIBegin, MIEnd)
274// @note: MIBegin and MIEnd should be from same MBB
275// The Def is closest to MIEnd.
276// Takes care of aliases and predicated defs as well.
277bool HexagonLiveVariables::isDefinedWithin(MICInstIterType MIBegin,
278 MICInstIterType MIEnd, unsigned Reg,
279 MICInstIterType &Def) const {
280 assert(HLVComplete && "Liveness Analysis not available");
281 Def = MIEnd;
282 if (MIBegin == MIEnd) // NULL Range.
283 return false;
284 MICInstIterType MII = MIEnd;
285 do {
286 --MII;
287 if (MII->isBundle() || MII->isDebugInstr())
288 continue;
289 auto It = HLV->MIUseDefs.find(Val: &*MII);
290 assert(It != HLV->MIUseDefs.end());
291 for (MCRegAliasIterator AI(Reg, HLV->TRI, true); AI.isValid(); ++AI)
292 if (It->second.second[*AI]) {
293 Def = MII;
294 return true;
295 }
296 } while (MII != MIBegin);
297 return false;
298}
299
300// Returns true if any of the defs of MII is live-in in the MBB.
301bool HexagonLiveVariables::isDefLiveIn(const MachineInstr *MI,
302 const MachineBasicBlock *MBB) const {
303 assert(HLVComplete && "Liveness Analysis not available");
304 assert(MI && "Invalid machine instruction");
305 assert(MBB && "Invalid machine basic block");
306 auto It = HLV->MIUseDefs.find(Val: MI);
307 assert(It != HLV->MIUseDefs.end() && "Missing MI use/def information");
308 BitVector MBBLiveIns(HLV->NumRegs);
309 for (MachineBasicBlock::livein_iterator lit = MBB->livein_begin();
310 lit != MBB->livein_end(); ++lit) {
311 // Include all the aliases of reg *lit.
312 for (MCRegAliasIterator AI((*lit).PhysReg, HLV->TRI, true); AI.isValid();
313 ++AI)
314 MBBLiveIns.set(*AI);
315 }
316 // Intersect.
317 return MBBLiveIns.anyCommon(RHS: It->second.second);
318}
319
320MBBUseDef_t &HexagonLiveVariables::getMBBUseDefs() { return HLV->MBBUseDefs; }
321
322MIUseDef_t &HexagonLiveVariables::getMIUseDefs() { return HLV->MIUseDefs; }
323
324unsigned HexagonLiveVariables::getDistanceBetween(const MachineBasicBlock *From,
325 const MachineBasicBlock *To,
326 unsigned BufferPerMBB) const {
327 assert(HLV->DistanceMap.find(From) != HLV->DistanceMap.end());
328 assert(HLV->DistanceMap.find(To) != HLV->DistanceMap.end());
329 unsigned FromSize = HLV->DistanceMap[From];
330 if (From == To)
331 return FromSize;
332 const MachineFunction *MF = From->getParent();
333 MachineFunction::const_iterator MBBI = MF->begin();
334 unsigned S = BufferPerMBB;
335 bool ToFirst = false;
336 while (MBBI != MF->end()) {
337 const MachineBasicBlock *MBB = &*MBBI;
338 if (MBB == From)
339 break;
340 else if (MBB == To) {
341 ToFirst = true;
342 break;
343 }
344 ++MBBI;
345 }
346 const MachineBasicBlock *ToFind = To;
347 if (ToFirst)
348 ToFind = From;
349 while (MBBI != MF->end()) {
350 const MachineBasicBlock *MBB = &*MBBI;
351 if (MBB == ToFind)
352 break;
353 S += HLV->DistanceMap[MBB] + BufferPerMBB;
354 ++MBBI;
355 }
356 if (ToFirst) // Jump in the opposite direction.
357 S += FromSize + HLV->DistanceMap[To] + 2 * BufferPerMBB;
358 return S;
359}
360
361void HexagonLiveVariables::regenerateDistanceMap(const MachineFunction &Fn) {
362 HLV->clearDistanceMap();
363 HLV->generateDistanceMap(Fn);
364}
365
366//===----------------------------------------------------------------------===//
367// HexagonLiveVariablesImpl Functions
368//===----------------------------------------------------------------------===//
369bool HexagonLiveVariablesImpl::runOnMachineFunction(
370 MachineFunction &Fn, MachineDominatorTree &MDT,
371 MachinePostDominatorTree &MPDT) {
372 LLVM_DEBUG(dbgs() << "\nHexagon Live Variables";);
373 Fn.RenumberBlocks();
374
375 MF = &Fn;
376 MRI = &Fn.getRegInfo();
377 auto &ST = Fn.getSubtarget<HexagonSubtarget>();
378 TRI = ST.getRegisterInfo();
379 QII = ST.getInstrInfo();
380
381 NumRegs = TRI->getNumRegs();
382
383 MBBUseDefs.clear();
384 MIUseDefs.clear();
385 MBBLiveOuts.clear();
386
387 LLVM_DEBUG(dbgs() << "\nNumber of registers in Hexagon is:" << NumRegs);
388
389 PhysRegDef.resize(N: NumRegs);
390 PhysRegUse.resize(N: NumRegs);
391
392 for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); MBBI != E;
393 ++MBBI) {
394 constructUseDef(MBB: &*MBBI);
395 }
396 updateGlobalLiveness(Fn);
397 return false;
398}
399
400void HexagonLiveVariablesImpl::constructUseDef(MachineBasicBlock *MBB) {
401 std::fill(first: PhysRegDef.begin(), last: PhysRegDef.end(), value: (MachineInstr *)0);
402 std::fill(first: PhysRegUse.begin(), last: PhysRegUse.end(), value: (MachineInstr *)0);
403
404 // Loop over all of the instructions, processing them.
405 std::pair<BitVector, BitVector> &UseDef = MBBUseDefs[MBB];
406 // Use before any def in a BB.
407 BitVector &Uses = UseDef.first;
408 // Defs before any use in a BB.
409 BitVector &Defs = UseDef.second;
410 // Initializing the LiveOut bit vector.
411 BitVector &LiveOuts = MBBLiveOuts[MBB];
412 Uses.resize(N: NumRegs, t: false);
413 Defs.resize(N: NumRegs, t: false);
414 LiveOuts.resize(N: NumRegs, t: false);
415 // BitVector might contain set bits out of previous liveness updates.
416 Uses.reset();
417 Defs.reset();
418 LiveOuts.reset();
419 LLVM_DEBUG(dbgs() << "\nBB#" << MBB->getNumber(););
420 // MBB Number in the MSB 32 bits.
421 unsigned MBBInsSize = 0;
422 for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
423 E = MBB->instr_end();
424 MII != E; ++MII) {
425 MachineInstr *MI = &*MII;
426 MBBInsSize += QII->getSize(MI: *MI);
427 // TODO: Handle isDebugInstr
428 if (MI->isBundle() || MI->isDebugInstr())
429 continue;
430 LLVM_DEBUG(dbgs() << "\n\n" << *MI;);
431 // Clear kill and dead markers. LV will recompute them.
432 UseDef_t &MIUseDef = MIUseDefs[MI];
433 MIUseDef.first.resize(N: NumRegs); // Uses
434 MIUseDef.second.resize(N: NumRegs); // Defs
435 MIUseDef.first.reset(); // Uses
436 MIUseDef.second.reset(); // Defs
437
438 SmallVector<MachineOperand *, 4> UseRegs;
439 SmallVector<MachineOperand *, 4> DefRegs;
440 SmallVector<unsigned, 1> RegMasks;
441 // Process all of the operands of the instruction...
442 unsigned NumOperandsToProcess = MI->getNumOperands();
443 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
444 MachineOperand &MO = MI->getOperand(i);
445 if (MO.isRegMask()) {
446 // Assuming that predicated defs are not defs, for now.
447 if (!QII->isPredicated(MI: *MI))
448 DefRegs.push_back(Elt: &MO);
449 continue;
450 }
451 if (!MO.isReg() || MO.getReg() == 0)
452 continue;
453 unsigned Reg = MO.getReg();
454 if (MO.isUse()) {
455 // Assuming that the kill-flags on call-instructions are correct.
456 MO.setIsKill(false);
457 UseRegs.push_back(Elt: &MO);
458 MIUseDef.first.set(Reg);
459 } else /*MO.isDef()*/ {
460 assert(MO.isDef());
461 if (!QII->isPredicated(MI: *MI) && !MI->isKill()) {
462 // Assuming that predicated defs are not defs, for now.
463 // KILL instructions are no-ops
464 MO.setIsDead(false);
465 DefRegs.push_back(Elt: &MO);
466 }
467 MIUseDef.second.set(Reg); // Set all defs (including predicated).
468 }
469 }
470 // Process all uses.
471 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i)
472 handlePhysRegUse(MO: UseRegs[i], MI, Uses);
473 // Process all defs.
474 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i)
475 handlePhysRegDef(MO: DefRegs[i], MI, Defs);
476 }
477 DistanceMap[MBB] = MBBInsSize;
478}
479
480void HexagonLiveVariablesImpl::handlePhysRegUse(MachineOperand *MO,
481 MachineInstr *MI,
482 BitVector &Uses) {
483 unsigned Reg = MO->getReg();
484 LLVM_DEBUG(dbgs() << "\nLooking at:";);
485 // If the reg/super-reg is already defined in this MBB => return.
486 for (MCSuperRegIterator SupI(Reg, TRI, true); SupI.isValid(); ++SupI) {
487 LLVM_DEBUG(dbgs() << printReg(*SupI, TRI););
488 if (PhysRegDef[*SupI])
489 return;
490 }
491 // Handle if sub-regs are defined.
492 SmallVector<unsigned, 2> undefSubRegs;
493 bool subRegDefined = false;
494 for (MCSubRegIterator SubI(Reg, TRI); SubI.isValid(); ++SubI) {
495 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI););
496 if (PhysRegDef[*SubI])
497 subRegDefined = true;
498 else
499 undefSubRegs.push_back(Elt: *SubI);
500 }
501
502 LLVM_DEBUG(dbgs() << "\nUses:");
503 if (undefSubRegs.empty()) {
504 if (!subRegDefined) { // None of the subregs are defined.
505 // Include all subregs (including self) to the uses.
506 for (MCSubRegIterator SubI(Reg, TRI, true); SubI.isValid(); ++SubI) {
507 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI));
508 PhysRegUse[*SubI] = MI;
509 Uses.set(*SubI);
510 }
511 } // All subregs defined.
512 return;
513 }
514 // Some subregs are defined.
515 for (unsigned i = 0; i < undefSubRegs.size(); ++i) {
516 LLVM_DEBUG(dbgs() << printReg(undefSubRegs[i], TRI));
517 PhysRegUse[undefSubRegs[i]] = MI;
518 Uses.set(undefSubRegs[i]);
519 }
520}
521
522// Assumes that an MI cannot have a reg and its super/sub reg as uses.
523void HexagonLiveVariablesImpl::handlePhysRegDef(MachineOperand *MO,
524 MachineInstr *MI,
525 BitVector &Defs) {
526 auto SetRegDef = [&](unsigned Reg) -> void {
527 PhysRegDef[Reg] = MI;
528 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
529 if (PhysRegUse[*AI]) {
530 LLVM_DEBUG(dbgs() << "\nUsed in current BB:" << printReg(*AI, TRI));
531 return;
532 }
533 }
534 LLVM_DEBUG(dbgs() << "\nDefs:" << printReg(Reg, TRI));
535 Defs.set(Reg);
536 };
537
538 if (MO->isReg()) {
539 SetRegDef(MO->getReg());
540 } else if (MO->isRegMask()) {
541 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
542 if (MO->clobbersPhysReg(PhysReg: R))
543 SetRegDef(R);
544 }
545}
546
547namespace {
548struct BlockState {
549 bool SuccQueued : 1;
550 bool Done : 1;
551 BlockState() : SuccQueued(false), Done(false) {}
552};
553} // namespace
554
555// Populates 'Blocks' with basic blocks of 'Fn' in depth-first order
556static void gatherBlocksDF(MachineFunction &Fn,
557 SmallVectorImpl<MachineBasicBlock *> *Blocks) {
558 Blocks->clear();
559 Blocks->reserve(N: Fn.size());
560
561 SmallVector<BlockState, 16> State(Fn.size());
562 SmallVector<MachineBasicBlock *, 16> WorkStack;
563 WorkStack.push_back(Elt: &Fn.front());
564 while (!WorkStack.empty()) {
565 MachineBasicBlock *W = WorkStack.back();
566 BlockState &WState = State[W->getNumber()];
567 if (WState.Done) {
568 WorkStack.pop_back();
569 continue;
570 }
571 if (W->succ_empty() || WState.SuccQueued) {
572 WorkStack.pop_back();
573 Blocks->push_back(Elt: W);
574 WState.SuccQueued = true;
575 WState.Done = true;
576 continue;
577 }
578 WState.SuccQueued = true;
579 for (MachineBasicBlock::succ_iterator I = W->succ_begin(),
580 E = W->succ_end();
581 I != E; ++I) {
582 MachineBasicBlock *S = *I;
583 if (State[S->getNumber()].SuccQueued)
584 continue;
585 WorkStack.push_back(Elt: S);
586 }
587 }
588
589 LLVM_DEBUG(
590 dbgs() << "gatherBlocksDF: {";
591 for (SmallVectorImpl<MachineBasicBlock *>::iterator B = Blocks->begin(),
592 BE = Blocks->end();
593 B != BE; ++B) { dbgs() << " BB#" << (*B)->getNumber(); } dbgs()
594 << " }\n";);
595}
596
597bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineFunction &Fn) {
598 bool Changed = false;
599 // Removing live-ins and recomputing.
600 MachineFunction::iterator I = Fn.begin(), E = Fn.end();
601 // Not touching the live-ins of entry basic block.
602 for (++I; I != E; ++I) {
603 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIn(
604 I->livein_begin(), I->livein_end());
605 for (unsigned i = 0; i < OldLiveIn.size(); ++i)
606 I->removeLiveIn(Reg: OldLiveIn[i].PhysReg);
607 }
608
609 gatherBlocksDF(Fn, Blocks: &BlocksDepthFirst);
610
611 BitVector Defs;
612 BitVector LiveIns;
613 bool Repeat;
614 do {
615 Repeat = false;
616 for (SmallVectorImpl<MachineBasicBlock *>::iterator
617 B = BlocksDepthFirst.begin(),
618 BE = BlocksDepthFirst.end();
619 B != BE; ++B) {
620 Repeat |= updateGlobalLiveness(MBB: *B, Defs, LiveIns);
621 }
622 Changed |= Repeat;
623 } while (Repeat);
624
625 Changed |= updateLocalLiveness(Fn);
626 return Changed;
627}
628
629bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *X,
630 MachineBasicBlock *Y) {
631 assert(X && "Invalid start block");
632 assert(Y && "Invalid end block");
633
634 bool Changed = false;
635 BitVector Defs;
636 BitVector LiveIns;
637
638 const SmallVectorImpl<MachineBasicBlock *>::iterator BE =
639 BlocksDepthFirst.end();
640 SmallVectorImpl<MachineBasicBlock *>::iterator B;
641 for (B = BlocksDepthFirst.begin(); (B != BE); ++B) {
642 if (*B == X)
643 break;
644 if (*B == Y)
645 break;
646 }
647
648 bool Repeat;
649 do {
650 Repeat = false;
651 for (; B != BE; ++B)
652 Repeat |= updateGlobalLiveness(MBB: *B, Defs, LiveIns);
653 Changed |= Repeat;
654 B = BlocksDepthFirst.begin();
655 } while (Repeat);
656
657 return Changed;
658}
659
660// Defs and LiveIns could be local variables within updateGlobalLiveness, but
661// have been pulled out to (hopefully) improve performance.
662bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *MBB,
663 BitVector &Defs,
664 BitVector &LiveIns) {
665 LLVM_DEBUG(dbgs() << "\nTrying to Update Liveness MBB#" << MBB->getNumber());
666 bool Changed = false;
667 LLVM_DEBUG(dbgs() << "\nUpdating Liveness MBB#" << MBB->getNumber());
668 // Update live-outs
669 auto LiveOutIt = MBBLiveOuts.find(Val: MBB);
670 if (LiveOutIt == MBBLiveOuts.end())
671 LiveOutIt = MBBLiveOuts.insert(KV: {MBB, BitVector(NumRegs)}).first;
672 BitVector &LiveOuts = LiveOutIt->second;
673 for (MachineBasicBlock::succ_iterator MBBSucc = MBB->succ_begin();
674 MBBSucc != MBB->succ_end(); ++MBBSucc) {
675 MachineBasicBlock *Succ = *MBBSucc;
676 LLVM_DEBUG(dbgs() << "\n\t\tAdding LiveOut:";);
677 for (MachineBasicBlock::livein_iterator LI = Succ->livein_begin(),
678 LE = Succ->livein_end();
679 LI != LE; ++LI) {
680 if (!LiveOuts[(*LI).PhysReg]) {
681 LLVM_DEBUG(dbgs() << " " << printReg((*LI).PhysReg, TRI););
682 LiveOuts.set((*LI).PhysReg);
683 Changed = true;
684 }
685 }
686 }
687 LLVM_DEBUG(dbgs() << "\nUpdated Successors of MBB#" << MBB->getNumber());
688 // Update live-ins
689 Changed |= updateLiveIns(MBB, LiveIns, LiveOuts);
690
691 return Changed;
692}
693
694// update live-ins when live-out has been calculated
695bool HexagonLiveVariablesImpl::updateLiveIns(MachineBasicBlock *MBB,
696 BitVector &LiveIns,
697 const BitVector &LiveOuts) {
698 LLVM_DEBUG(dbgs() << "\n[updateLiveIns] MBB#" << MBB->getNumber());
699 bool Changed = false;
700 const std::pair<BitVector, BitVector> &UseDefs = MBBUseDefs[MBB];
701 LiveIns = LiveOuts;
702 // LiveIns = (LiveOuts - Defs) | Uses
703 // Equivalent to: LiveIns = (LiveOuts & ~Defs) | Uses
704 LiveIns.reset(RHS: UseDefs.second);
705 LiveIns |= UseDefs.first;
706 LLVM_DEBUG(dbgs() << "\n\t\tAdded LiveIn:";);
707 for (int i = LiveIns.find_first(); i >= 0; i = LiveIns.find_next(Prev: i)) {
708 // TODO: remove costly check of MBB->isLiveIn when fully functional.
709 if (!MBB->isLiveIn(Reg: i) && MRI->isAllocatable(PhysReg: i)) {
710 LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
711 MBB->addLiveIn(PhysReg: i);
712 Changed = true;
713 }
714 }
715 return Changed;
716}
717
718bool HexagonLiveVariablesImpl::updateLiveOuts(MachineBasicBlock *MBB,
719 BitVector &LiveOuts) {
720 bool Changed = false;
721 for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
722 MachineBasicBlock *SB = *SI;
723 for (auto I = SB->livein_begin(), E = SB->livein_end(); I != E; ++I) {
724 unsigned R = (*I).PhysReg;
725 if (LiveOuts[R])
726 continue;
727 LiveOuts.set(R);
728 Changed = true;
729 }
730 }
731 return Changed;
732}
733
734bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineFunction &Fn) {
735 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness]");
736 for (MachineFunction::iterator B = Fn.begin(), E = Fn.end(); B != E; ++B)
737 updateLocalLiveness(MBB: &*B, UpdateBundle: false);
738 return true;
739}
740
741bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineBasicBlock *MBB,
742 bool UpdateBundle) {
743 assert(MBB && "Invalid basic block");
744 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness] MBB#" << MBB->getNumber());
745
746 BitVector &LiveOut = MBBLiveOuts[MBB];
747 updateLiveOuts(MBB, LiveOuts&: LiveOut);
748
749 BitVector Used = LiveOut;
750 SmallVector<MachineInstr *, 2> BundleHeads;
751 // Bottom up traversal of MBB.
752 for (MachineBasicBlock::reverse_instr_iterator MII = MBB->instr_rbegin(),
753 MIREnd = MBB->instr_rend();
754 MII != MIREnd; ++MII) {
755 MachineInstr *MI = &*MII;
756 // The bundle liveness is updated differently.
757 if (MI->isBundle()) {
758 if (UpdateBundle)
759 BundleHeads.push_back(Elt: MI);
760 continue;
761 }
762 if (MI->isDebugInstr()) // DBG_VALUE may have invalid reg.
763 continue;
764 SmallVector<MachineOperand *, 4> UseRegs;
765 SmallVector<MachineOperand *, 2> DefRegs;
766 for (unsigned i = 0; i < MI->getNumOperands(); ++i) {
767 MachineOperand &MO = MI->getOperand(i);
768 if (MO.isReg()) { // DBG_VALUE may have invalid reg.
769 if (MO.isUse())
770 UseRegs.push_back(Elt: &MO);
771 else { // Def
772 if (!QII->isPredicated(MI: *MI) && !MI->isKill()) {
773 // Assuming that predicated defs are not defs, for now.
774 // KILL instructions are no-ops
775 DefRegs.push_back(Elt: &MO);
776 }
777 }
778 } else if (MO.isRegMask()) {
779 if (!QII->isPredicated(MI: *MI))
780 DefRegs.push_back(Elt: &MO);
781 }
782 }
783 // In case of a def. remove Reg and its sub-regs from Used list
784 // such that uses in the same MI can be marked as kill.
785 auto RemoveDef = [&](unsigned Reg, bool Implicit) -> void {
786 for (MCSubRegIterator SI(Reg, TRI, true); SI.isValid(); ++SI) {
787 Used.reset(Idx: *SI);
788 if (Implicit) {
789 // For implicit defs, check if there is an implicit use of an
790 // aliased register. If so, mark the aliased reg as used.
791 for (auto *UseOp : UseRegs)
792 if (UseOp->isImplicit() && TRI->regsOverlap(RegA: *SI, RegB: UseOp->getReg()))
793 Used.set(UseOp->getReg());
794 }
795 }
796 };
797 for (unsigned i = 0; i < DefRegs.size(); ++i) {
798 MachineOperand &MO = *DefRegs[i];
799 if (MO.isReg()) {
800 RemoveDef(MO.getReg(), MO.isImplicit());
801 } else if (MO.isRegMask()) {
802 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
803 if (MO.clobbersPhysReg(PhysReg: R))
804 RemoveDef(R, true);
805 }
806 }
807 // The order is important as we are looking from right to left.
808 for (unsigned i = UseRegs.size(); i > 0;) {
809 --i;
810 unsigned UseReg = UseRegs[i]->getReg();
811 bool Killed = true;
812 for (MCRegAliasIterator AI(UseReg, TRI, true); AI.isValid(); ++AI) {
813 if (Used[*AI])
814 Killed = false;
815 }
816 Used.set(UseReg);
817 if (Killed && !UseRegs[i]->isDebug())
818 UseRegs[i]->setIsKill(true);
819 }
820 }
821 // Recreates bundle for updating liveness.
822 for (SmallVectorImpl<MachineInstr *>::iterator MII = BundleHeads.begin();
823 MII != BundleHeads.end(); ++MII) {
824 MachineInstr *MI = *MII;
825 assert(MI && "Invalid bundle head");
826 assert(MI->isBundle() && "Expected a bundle head instruction");
827 assert(MI->getParent() == MBB && "Bundle head not in expected block");
828 MachineBasicBlock::instr_iterator BS = MI->getIterator();
829 MachineBasicBlock::instr_iterator BE = getBundleEnd(I: BS);
830 for (++BS; BS != BE; ++BS)
831 // Remove from bundle so that BUNDLE head can be erased.
832 BS->unbundleFromPred();
833
834 BS = MI->getIterator();
835 ++BS;
836 bool memShufDisabled = QII->getBundleNoShuf(MIB: *MI);
837 MI->eraseFromParent();
838 finalizeBundle(MBB&: *MBB, FirstMI: BS, LastMI: BE);
839 MachineBasicBlock::instr_iterator BundleMII = std::prev(x: BS);
840 if (memShufDisabled)
841 QII->setBundleNoShuf(BundleMII);
842 }
843 return true;
844}
845
846// It deletes the live-in of the \p From MBB.
847bool HexagonLiveVariablesImpl::incrementalUpdate(MICInstIterType MIDelta,
848 MachineBasicBlock *From,
849 MachineBasicBlock *To) {
850 while (!From->livein_empty())
851 From->removeLiveIn(Reg: (*From->livein_begin()).PhysReg);
852 // Handle MI use-def of From.
853 constructUseDef(MBB: From);
854 // Handle MI use-def of To.
855 constructUseDef(MBB: To);
856 // Calculate live-in of From and To
857 // Reuse this by setting all MBBs except From and To as visited.
858 updateGlobalLiveness(X: From, Y: To);
859 // Update local liveness of To.
860 updateLocalLiveness(MBB: From, UpdateBundle: true);
861 updateLocalLiveness(MBB: To, UpdateBundle: true);
862
863 // Do this after the liveness update because MIDelta might not be in the
864 // MIUseDefs before liveness update (since MIDelta might be newly inserted).
865 MIUseDef_t::const_iterator MIUseDef = MIUseDefs.find(Val: &*MIDelta);
866 if (MIUseDef == MIUseDefs.end())
867 llvm_unreachable("MIDelta not found in MIUseDefs after liveness update");
868 const BitVector &Defs = MIUseDef->second.second;
869 int Reg = Defs.find_first();
870 // Adding all the defs as live-ins. This is conservative approach but we
871 // need to add them so as to avoid dealing with callee saved registers and
872 // any unwanted errors in liveness that might arise.
873 while (Reg >= 0) {
874 From->addLiveIn(PhysReg: Reg);
875 Reg = Defs.find_next(Prev: Reg);
876 }
877 return true;
878}
879
880void HexagonLiveVariablesImpl::addNewMBB(MachineBasicBlock *MBB) {
881 // Resize and init.
882 constructUseDef(MBB); // This is to set up some containers for MBB.
883 gatherBlocksDF(Fn&: *MBB->getParent(), Blocks: &BlocksDepthFirst);
884 updateGlobalLiveness(X: MBB, Y: MBB);
885}
886
887// TODO: This is a slow implementation because constructUseDef destroys
888// the MBBLiveOuts which is generated again by updateGlobalLiveness.
889void HexagonLiveVariablesImpl::addNewMI(MachineInstr *MI,
890 MachineBasicBlock *MBB) {
891 constructUseDef(MBB); // This is to set up some containers for MBB.
892 updateGlobalLiveness(X: MBB, Y: MBB);
893}
894
895void HexagonLiveVariablesImpl::generateDistanceMap(const MachineFunction &Fn) {
896 assert(DistanceMap.empty() && "DistanceMap not empty, first clear!");
897 for (MachineFunction::const_iterator MBBI = Fn.begin(), E = Fn.end();
898 MBBI != E; ++MBBI) {
899 const MachineBasicBlock *MBB = &*MBBI;
900 unsigned MBBInsSize = 0;
901 for (MachineBasicBlock::const_instr_iterator MII = MBB->instr_begin(),
902 E = MBB->instr_end();
903 MII != E; ++MII) {
904 const MachineInstr *MI = &*MII;
905 MBBInsSize += QII->getSize(MI: *MI);
906 }
907 DistanceMap[MBB] = MBBInsSize;
908 }
909}
910