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<MachineDominatorTreeWrapperPass>();
171 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();
172 AU.addPreserved(Arg: "packets");
173 MachineFunctionPass::getAnalysisUsage(AU);
174}
175
176void HexagonLiveVariables::recalculate(MachineFunction &MF) {
177 if (HLVComplete)
178 return;
179 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
180 auto &MPDT =
181 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
182 HLV->runOnMachineFunction(Fn&: MF, MDT, MPDT);
183}
184
185bool HexagonLiveVariables::updateLocalLiveness(MachineFunction &Fn) {
186 return HLV->updateLocalLiveness(Fn);
187}
188
189bool HexagonLiveVariables::updateLocalLiveness(MachineBasicBlock *MBB,
190 bool updateBundle) {
191 HLV->constructUseDef(MBB); // XXX: This destroys MBBLiveOuts!
192 return HLV->updateLocalLiveness(MBB, UpdateBundle: updateBundle);
193}
194
195bool HexagonLiveVariables::incrementalUpdate(MICInstIterType MIDelta,
196 MachineBasicBlock *From,
197 MachineBasicBlock *To) {
198 assert(MIDelta->getParent() == To);
199 assert(From != To);
200 return HLV->incrementalUpdate(MIDelta, From, To);
201}
202
203void HexagonLiveVariables::addNewMBB(MachineBasicBlock *MBB) {
204 assert(MBB->empty());
205 HLV->addNewMBB(MBB);
206}
207
208void HexagonLiveVariables::addNewMI(MachineInstr *MI, MachineBasicBlock *MBB) {
209 HLV->addNewMI(MI, MBB);
210}
211
212void HexagonLiveVariables::constructUseDef(MachineBasicBlock *MBB) {
213 HLV->constructUseDef(MBB);
214}
215
216bool HexagonLiveVariables::runOnMachineFunction(MachineFunction &Fn) {
217 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
218 auto &MPDT =
219 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
220 HLVComplete = !HLV->runOnMachineFunction(Fn, MDT, MPDT);
221 return HLVComplete;
222}
223
224bool HexagonLiveVariables::isLiveOut(const MachineBasicBlock *MBB,
225 unsigned Reg) const {
226 assert(HLVComplete && "Liveness Analysis not available");
227 auto It = HLV->MBBLiveOuts.find(Val: MBB);
228 if (It == HLV->MBBLiveOuts.end())
229 llvm_unreachable("MBB not found in liveness map");
230 if (Reg >= It->second.size())
231 llvm_unreachable("Register index out of bounds");
232 return It->second[Reg];
233}
234
235const BitVector &
236HexagonLiveVariables::getLiveOuts(const MachineBasicBlock *MBB) const {
237 assert(HLVComplete && "Liveness Analysis not available");
238 auto It = HLV->MBBLiveOuts.find(Val: MBB);
239 if (It == HLV->MBBLiveOuts.end())
240 llvm_unreachable("MBB not found in liveness map");
241 return It->second;
242}
243
244// Returns true when \p Reg is used within [MIBegin, MIEnd)
245// @note: MIBegin and MIEnd should be from same MBB
246// @note: It returns just the first use found in the range.
247// The Use is closest to MIEnd.
248// Takes care of aliases and predicated defs as well.
249bool HexagonLiveVariables::isUsedWithin(
250 MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg,
251 MICInstIterType &Use,
252 SmallPtrSet<MachineInstr *, 2> *ExceptionsList) const {
253 assert(HLVComplete && "Liveness Analysis not available");
254 Use = MIEnd;
255 if (MIBegin == MIEnd) // NULL Range.
256 return false;
257 MICInstIterType MII = MIEnd;
258 do {
259 --MII;
260 if (MII->isBundle() || MII->isDebugInstr())
261 continue;
262 if (ExceptionsList && ExceptionsList->contains(Ptr: &*MII))
263 continue;
264 auto It = HLV->MIUseDefs.find(Val: &*MII);
265 assert(It != HLV->MIUseDefs.end());
266 for (MCRegAliasIterator AI(Reg, HLV->TRI, true); AI.isValid(); ++AI)
267 if (It->second.first[*AI]) {
268 Use = MII;
269 return true;
270 }
271 } while (MII != MIBegin);
272 return false;
273}
274
275// Returns true when \p Reg id defined within [MIBegin, MIEnd)
276// @note: MIBegin and MIEnd should be from same MBB
277// The Def is closest to MIEnd.
278// Takes care of aliases and predicated defs as well.
279bool HexagonLiveVariables::isDefinedWithin(MICInstIterType MIBegin,
280 MICInstIterType MIEnd, unsigned Reg,
281 MICInstIterType &Def) const {
282 assert(HLVComplete && "Liveness Analysis not available");
283 Def = MIEnd;
284 if (MIBegin == MIEnd) // NULL Range.
285 return false;
286 MICInstIterType MII = MIEnd;
287 do {
288 --MII;
289 if (MII->isBundle() || MII->isDebugInstr())
290 continue;
291 auto It = HLV->MIUseDefs.find(Val: &*MII);
292 assert(It != HLV->MIUseDefs.end());
293 for (MCRegAliasIterator AI(Reg, HLV->TRI, true); AI.isValid(); ++AI)
294 if (It->second.second[*AI]) {
295 Def = MII;
296 return true;
297 }
298 } while (MII != MIBegin);
299 return false;
300}
301
302// Returns true if any of the defs of MII is live-in in the MBB.
303bool HexagonLiveVariables::isDefLiveIn(const MachineInstr *MI,
304 const MachineBasicBlock *MBB) const {
305 assert(HLVComplete && "Liveness Analysis not available");
306 assert(MI && "Invalid machine instruction");
307 assert(MBB && "Invalid machine basic block");
308 auto It = HLV->MIUseDefs.find(Val: MI);
309 assert(It != HLV->MIUseDefs.end() && "Missing MI use/def information");
310 BitVector MBBLiveIns(HLV->NumRegs);
311 for (MachineBasicBlock::livein_iterator lit = MBB->livein_begin();
312 lit != MBB->livein_end(); ++lit) {
313 // Include all the aliases of reg *lit.
314 for (MCRegAliasIterator AI((*lit).PhysReg, HLV->TRI, true); AI.isValid();
315 ++AI)
316 MBBLiveIns.set(*AI);
317 }
318 // Intersect.
319 return MBBLiveIns.anyCommon(RHS: It->second.second);
320}
321
322MBBUseDef_t &HexagonLiveVariables::getMBBUseDefs() { return HLV->MBBUseDefs; }
323
324MIUseDef_t &HexagonLiveVariables::getMIUseDefs() { return HLV->MIUseDefs; }
325
326unsigned HexagonLiveVariables::getDistanceBetween(const MachineBasicBlock *From,
327 const MachineBasicBlock *To,
328 unsigned BufferPerMBB) const {
329 assert(HLV->DistanceMap.find(From) != HLV->DistanceMap.end());
330 assert(HLV->DistanceMap.find(To) != HLV->DistanceMap.end());
331 unsigned FromSize = HLV->DistanceMap[From];
332 if (From == To)
333 return FromSize;
334 const MachineFunction *MF = From->getParent();
335 MachineFunction::const_iterator MBBI = MF->begin();
336 unsigned S = BufferPerMBB;
337 bool ToFirst = false;
338 while (MBBI != MF->end()) {
339 const MachineBasicBlock *MBB = &*MBBI;
340 if (MBB == From)
341 break;
342 else if (MBB == To) {
343 ToFirst = true;
344 break;
345 }
346 ++MBBI;
347 }
348 const MachineBasicBlock *ToFind = To;
349 if (ToFirst)
350 ToFind = From;
351 while (MBBI != MF->end()) {
352 const MachineBasicBlock *MBB = &*MBBI;
353 if (MBB == ToFind)
354 break;
355 S += HLV->DistanceMap[MBB] + BufferPerMBB;
356 ++MBBI;
357 }
358 if (ToFirst) // Jump in the opposite direction.
359 S += FromSize + HLV->DistanceMap[To] + 2 * BufferPerMBB;
360 return S;
361}
362
363void HexagonLiveVariables::regenerateDistanceMap(const MachineFunction &Fn) {
364 HLV->clearDistanceMap();
365 HLV->generateDistanceMap(Fn);
366}
367
368//===----------------------------------------------------------------------===//
369// HexagonLiveVariablesImpl Functions
370//===----------------------------------------------------------------------===//
371bool HexagonLiveVariablesImpl::runOnMachineFunction(
372 MachineFunction &Fn, MachineDominatorTree &MDT,
373 MachinePostDominatorTree &MPDT) {
374 LLVM_DEBUG(dbgs() << "\nHexagon Live Variables";);
375 Fn.RenumberBlocks();
376 // Update the block numbers in the dominator tree since we preserve it.
377 MDT.updateBlockNumbers();
378 MPDT.updateBlockNumbers();
379
380 MF = &Fn;
381 MRI = &Fn.getRegInfo();
382 auto &ST = Fn.getSubtarget<HexagonSubtarget>();
383 TRI = ST.getRegisterInfo();
384 QII = ST.getInstrInfo();
385
386 NumRegs = TRI->getNumRegs();
387
388 MBBUseDefs.clear();
389 MIUseDefs.clear();
390 MBBLiveOuts.clear();
391
392 LLVM_DEBUG(dbgs() << "\nNumber of registers in Hexagon is:" << NumRegs);
393
394 PhysRegDef.resize(N: NumRegs);
395 PhysRegUse.resize(N: NumRegs);
396
397 for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); MBBI != E;
398 ++MBBI) {
399 constructUseDef(MBB: &*MBBI);
400 }
401 updateGlobalLiveness(Fn);
402 return false;
403}
404
405void HexagonLiveVariablesImpl::constructUseDef(MachineBasicBlock *MBB) {
406 std::fill(first: PhysRegDef.begin(), last: PhysRegDef.end(), value: (MachineInstr *)0);
407 std::fill(first: PhysRegUse.begin(), last: PhysRegUse.end(), value: (MachineInstr *)0);
408
409 // Loop over all of the instructions, processing them.
410 std::pair<BitVector, BitVector> &UseDef = MBBUseDefs[MBB];
411 // Use before any def in a BB.
412 BitVector &Uses = UseDef.first;
413 // Defs before any use in a BB.
414 BitVector &Defs = UseDef.second;
415 // Initializing the LiveOut bit vector.
416 BitVector &LiveOuts = MBBLiveOuts[MBB];
417 Uses.resize(N: NumRegs, t: false);
418 Defs.resize(N: NumRegs, t: false);
419 LiveOuts.resize(N: NumRegs, t: false);
420 // BitVector might contain set bits out of previous liveness updates.
421 Uses.reset();
422 Defs.reset();
423 LiveOuts.reset();
424 LLVM_DEBUG(dbgs() << "\nBB#" << MBB->getNumber(););
425 // MBB Number in the MSB 32 bits.
426 unsigned MBBInsSize = 0;
427 for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
428 E = MBB->instr_end();
429 MII != E; ++MII) {
430 MachineInstr *MI = &*MII;
431 MBBInsSize += QII->getSize(MI: *MI);
432 // TODO: Handle isDebugInstr
433 if (MI->isBundle() || MI->isDebugInstr())
434 continue;
435 LLVM_DEBUG(dbgs() << "\n\n" << *MI;);
436 // Clear kill and dead markers. LV will recompute them.
437 UseDef_t &MIUseDef = MIUseDefs[MI];
438 MIUseDef.first.resize(N: NumRegs); // Uses
439 MIUseDef.second.resize(N: NumRegs); // Defs
440 MIUseDef.first.reset(); // Uses
441 MIUseDef.second.reset(); // Defs
442
443 SmallVector<MachineOperand *, 4> UseRegs;
444 SmallVector<MachineOperand *, 4> DefRegs;
445 SmallVector<unsigned, 1> RegMasks;
446 // Process all of the operands of the instruction...
447 unsigned NumOperandsToProcess = MI->getNumOperands();
448 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
449 MachineOperand &MO = MI->getOperand(i);
450 if (MO.isRegMask()) {
451 // Assuming that predicated defs are not defs, for now.
452 if (!QII->isPredicated(MI: *MI))
453 DefRegs.push_back(Elt: &MO);
454 continue;
455 }
456 if (!MO.isReg() || MO.getReg() == 0)
457 continue;
458 unsigned Reg = MO.getReg();
459 if (MO.isUse()) {
460 // Assuming that the kill-flags on call-instructions are correct.
461 MO.setIsKill(false);
462 UseRegs.push_back(Elt: &MO);
463 MIUseDef.first.set(Reg);
464 } else /*MO.isDef()*/ {
465 assert(MO.isDef());
466 if (!QII->isPredicated(MI: *MI) && !MI->isKill()) {
467 // Assuming that predicated defs are not defs, for now.
468 // KILL instructions are no-ops
469 MO.setIsDead(false);
470 DefRegs.push_back(Elt: &MO);
471 }
472 MIUseDef.second.set(Reg); // Set all defs (including predicated).
473 }
474 }
475 // Process all uses.
476 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i)
477 handlePhysRegUse(MO: UseRegs[i], MI, Uses);
478 // Process all defs.
479 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i)
480 handlePhysRegDef(MO: DefRegs[i], MI, Defs);
481 }
482 DistanceMap[MBB] = MBBInsSize;
483}
484
485void HexagonLiveVariablesImpl::handlePhysRegUse(MachineOperand *MO,
486 MachineInstr *MI,
487 BitVector &Uses) {
488 unsigned Reg = MO->getReg();
489 LLVM_DEBUG(dbgs() << "\nLooking at:";);
490 // If the reg/super-reg is already defined in this MBB => return.
491 for (MCSuperRegIterator SupI(Reg, TRI, true); SupI.isValid(); ++SupI) {
492 LLVM_DEBUG(dbgs() << printReg(*SupI, TRI););
493 if (PhysRegDef[*SupI])
494 return;
495 }
496 // Handle if sub-regs are defined.
497 SmallVector<unsigned, 2> undefSubRegs;
498 bool subRegDefined = false;
499 for (MCSubRegIterator SubI(Reg, TRI); SubI.isValid(); ++SubI) {
500 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI););
501 if (PhysRegDef[*SubI])
502 subRegDefined = true;
503 else
504 undefSubRegs.push_back(Elt: *SubI);
505 }
506
507 LLVM_DEBUG(dbgs() << "\nUses:");
508 if (undefSubRegs.empty()) {
509 if (!subRegDefined) { // None of the subregs are defined.
510 // Include all subregs (including self) to the uses.
511 for (MCSubRegIterator SubI(Reg, TRI, true); SubI.isValid(); ++SubI) {
512 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI));
513 PhysRegUse[*SubI] = MI;
514 Uses.set(*SubI);
515 }
516 } // All subregs defined.
517 return;
518 }
519 // Some subregs are defined.
520 for (unsigned i = 0; i < undefSubRegs.size(); ++i) {
521 LLVM_DEBUG(dbgs() << printReg(undefSubRegs[i], TRI));
522 PhysRegUse[undefSubRegs[i]] = MI;
523 Uses.set(undefSubRegs[i]);
524 }
525}
526
527// Assumes that an MI cannot have a reg and its super/sub reg as uses.
528void HexagonLiveVariablesImpl::handlePhysRegDef(MachineOperand *MO,
529 MachineInstr *MI,
530 BitVector &Defs) {
531 auto SetRegDef = [&](unsigned Reg) -> void {
532 PhysRegDef[Reg] = MI;
533 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
534 if (PhysRegUse[*AI]) {
535 LLVM_DEBUG(dbgs() << "\nUsed in current BB:" << printReg(*AI, TRI));
536 return;
537 }
538 }
539 LLVM_DEBUG(dbgs() << "\nDefs:" << printReg(Reg, TRI));
540 Defs.set(Reg);
541 };
542
543 if (MO->isReg()) {
544 SetRegDef(MO->getReg());
545 } else if (MO->isRegMask()) {
546 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
547 if (MO->clobbersPhysReg(PhysReg: R))
548 SetRegDef(R);
549 }
550}
551
552namespace {
553struct BlockState {
554 bool SuccQueued : 1;
555 bool Done : 1;
556 BlockState() : SuccQueued(false), Done(false) {}
557};
558} // namespace
559
560// Populates 'Blocks' with basic blocks of 'Fn' in depth-first order
561static void gatherBlocksDF(MachineFunction &Fn,
562 SmallVectorImpl<MachineBasicBlock *> *Blocks) {
563 Blocks->clear();
564 Blocks->reserve(N: Fn.size());
565
566 SmallVector<BlockState, 16> State(Fn.size());
567 SmallVector<MachineBasicBlock *, 16> WorkStack;
568 WorkStack.push_back(Elt: &Fn.front());
569 while (!WorkStack.empty()) {
570 MachineBasicBlock *W = WorkStack.back();
571 BlockState &WState = State[W->getNumber()];
572 if (WState.Done) {
573 WorkStack.pop_back();
574 continue;
575 }
576 if (W->succ_empty() || WState.SuccQueued) {
577 WorkStack.pop_back();
578 Blocks->push_back(Elt: W);
579 WState.SuccQueued = true;
580 WState.Done = true;
581 continue;
582 }
583 WState.SuccQueued = true;
584 for (MachineBasicBlock::succ_iterator I = W->succ_begin(),
585 E = W->succ_end();
586 I != E; ++I) {
587 MachineBasicBlock *S = *I;
588 if (State[S->getNumber()].SuccQueued)
589 continue;
590 WorkStack.push_back(Elt: S);
591 }
592 }
593
594 LLVM_DEBUG(
595 dbgs() << "gatherBlocksDF: {";
596 for (SmallVectorImpl<MachineBasicBlock *>::iterator B = Blocks->begin(),
597 BE = Blocks->end();
598 B != BE; ++B) { dbgs() << " BB#" << (*B)->getNumber(); } dbgs()
599 << " }\n";);
600}
601
602bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineFunction &Fn) {
603 bool Changed = false;
604 // Removing live-ins and recomputing.
605 MachineFunction::iterator I = Fn.begin(), E = Fn.end();
606 // Not touching the live-ins of entry basic block.
607 for (++I; I != E; ++I) {
608 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIn(
609 I->livein_begin(), I->livein_end());
610 for (unsigned i = 0; i < OldLiveIn.size(); ++i)
611 I->removeLiveIn(Reg: OldLiveIn[i].PhysReg);
612 }
613
614 gatherBlocksDF(Fn, Blocks: &BlocksDepthFirst);
615
616 BitVector Defs;
617 BitVector LiveIns;
618 bool Repeat;
619 do {
620 Repeat = false;
621 for (SmallVectorImpl<MachineBasicBlock *>::iterator
622 B = BlocksDepthFirst.begin(),
623 BE = BlocksDepthFirst.end();
624 B != BE; ++B) {
625 Repeat |= updateGlobalLiveness(MBB: *B, Defs, LiveIns);
626 }
627 Changed |= Repeat;
628 } while (Repeat);
629
630 Changed |= updateLocalLiveness(Fn);
631 return Changed;
632}
633
634bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *X,
635 MachineBasicBlock *Y) {
636 assert(X && "Invalid start block");
637 assert(Y && "Invalid end block");
638
639 bool Changed = false;
640 BitVector Defs;
641 BitVector LiveIns;
642
643 const SmallVectorImpl<MachineBasicBlock *>::iterator BE =
644 BlocksDepthFirst.end();
645 SmallVectorImpl<MachineBasicBlock *>::iterator B;
646 for (B = BlocksDepthFirst.begin(); (B != BE); ++B) {
647 if (*B == X)
648 break;
649 if (*B == Y)
650 break;
651 }
652
653 bool Repeat;
654 do {
655 Repeat = false;
656 for (; B != BE; ++B)
657 Repeat |= updateGlobalLiveness(MBB: *B, Defs, LiveIns);
658 Changed |= Repeat;
659 B = BlocksDepthFirst.begin();
660 } while (Repeat);
661
662 return Changed;
663}
664
665// Defs and LiveIns could be local variables within updateGlobalLiveness, but
666// have been pulled out to (hopefully) improve performance.
667bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *MBB,
668 BitVector &Defs,
669 BitVector &LiveIns) {
670 LLVM_DEBUG(dbgs() << "\nTrying to Update Liveness MBB#" << MBB->getNumber());
671 bool Changed = false;
672 LLVM_DEBUG(dbgs() << "\nUpdating Liveness MBB#" << MBB->getNumber());
673 // Update live-outs
674 auto LiveOutIt = MBBLiveOuts.find(Val: MBB);
675 if (LiveOutIt == MBBLiveOuts.end())
676 LiveOutIt = MBBLiveOuts.insert(KV: {MBB, BitVector(NumRegs)}).first;
677 BitVector &LiveOuts = LiveOutIt->second;
678 for (MachineBasicBlock::succ_iterator MBBSucc = MBB->succ_begin();
679 MBBSucc != MBB->succ_end(); ++MBBSucc) {
680 MachineBasicBlock *Succ = *MBBSucc;
681 LLVM_DEBUG(dbgs() << "\n\t\tAdding LiveOut:";);
682 for (MachineBasicBlock::livein_iterator LI = Succ->livein_begin(),
683 LE = Succ->livein_end();
684 LI != LE; ++LI) {
685 if (!LiveOuts[(*LI).PhysReg]) {
686 LLVM_DEBUG(dbgs() << " " << printReg((*LI).PhysReg, TRI););
687 LiveOuts.set((*LI).PhysReg);
688 Changed = true;
689 }
690 }
691 }
692 LLVM_DEBUG(dbgs() << "\nUpdated Successors of MBB#" << MBB->getNumber());
693 // Update live-ins
694 Changed |= updateLiveIns(MBB, LiveIns, LiveOuts);
695
696 return Changed;
697}
698
699// update live-ins when live-out has been calculated
700bool HexagonLiveVariablesImpl::updateLiveIns(MachineBasicBlock *MBB,
701 BitVector &LiveIns,
702 const BitVector &LiveOuts) {
703 LLVM_DEBUG(dbgs() << "\n[updateLiveIns] MBB#" << MBB->getNumber());
704 bool Changed = false;
705 const std::pair<BitVector, BitVector> &UseDefs = MBBUseDefs[MBB];
706 LiveIns = LiveOuts;
707 // LiveIns = (LiveOuts - Defs) | Uses
708 // Equivalent to: LiveIns = (LiveOuts & ~Defs) | Uses
709 LiveIns.reset(RHS: UseDefs.second);
710 LiveIns |= UseDefs.first;
711 LLVM_DEBUG(dbgs() << "\n\t\tAdded LiveIn:";);
712 for (int i = LiveIns.find_first(); i >= 0; i = LiveIns.find_next(Prev: i)) {
713 // TODO: remove costly check of MBB->isLiveIn when fully functional.
714 if (!MBB->isLiveIn(Reg: i) && MRI->isAllocatable(PhysReg: i)) {
715 LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
716 MBB->addLiveIn(PhysReg: i);
717 Changed = true;
718 }
719 }
720 return Changed;
721}
722
723bool HexagonLiveVariablesImpl::updateLiveOuts(MachineBasicBlock *MBB,
724 BitVector &LiveOuts) {
725 bool Changed = false;
726 for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
727 MachineBasicBlock *SB = *SI;
728 for (auto I = SB->livein_begin(), E = SB->livein_end(); I != E; ++I) {
729 unsigned R = (*I).PhysReg;
730 if (LiveOuts[R])
731 continue;
732 LiveOuts.set(R);
733 Changed = true;
734 }
735 }
736 return Changed;
737}
738
739bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineFunction &Fn) {
740 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness]");
741 for (MachineFunction::iterator B = Fn.begin(), E = Fn.end(); B != E; ++B)
742 updateLocalLiveness(MBB: &*B, UpdateBundle: false);
743 return true;
744}
745
746bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineBasicBlock *MBB,
747 bool UpdateBundle) {
748 assert(MBB && "Invalid basic block");
749 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness] MBB#" << MBB->getNumber());
750
751 BitVector &LiveOut = MBBLiveOuts[MBB];
752 updateLiveOuts(MBB, LiveOuts&: LiveOut);
753
754 BitVector Used = LiveOut;
755 SmallVector<MachineInstr *, 2> BundleHeads;
756 // Bottom up traversal of MBB.
757 for (MachineBasicBlock::reverse_instr_iterator MII = MBB->instr_rbegin(),
758 MIREnd = MBB->instr_rend();
759 MII != MIREnd; ++MII) {
760 MachineInstr *MI = &*MII;
761 // The bundle liveness is updated differently.
762 if (MI->isBundle()) {
763 if (UpdateBundle)
764 BundleHeads.push_back(Elt: MI);
765 continue;
766 }
767 if (MI->isDebugInstr()) // DBG_VALUE may have invalid reg.
768 continue;
769 SmallVector<MachineOperand *, 4> UseRegs;
770 SmallVector<MachineOperand *, 2> DefRegs;
771 for (unsigned i = 0; i < MI->getNumOperands(); ++i) {
772 MachineOperand &MO = MI->getOperand(i);
773 if (MO.isReg()) { // DBG_VALUE may have invalid reg.
774 if (MO.isUse())
775 UseRegs.push_back(Elt: &MO);
776 else { // Def
777 if (!QII->isPredicated(MI: *MI) && !MI->isKill()) {
778 // Assuming that predicated defs are not defs, for now.
779 // KILL instructions are no-ops
780 DefRegs.push_back(Elt: &MO);
781 }
782 }
783 } else if (MO.isRegMask()) {
784 if (!QII->isPredicated(MI: *MI))
785 DefRegs.push_back(Elt: &MO);
786 }
787 }
788 // In case of a def. remove Reg and its sub-regs from Used list
789 // such that uses in the same MI can be marked as kill.
790 auto RemoveDef = [&](unsigned Reg, bool Implicit) -> void {
791 for (MCSubRegIterator SI(Reg, TRI, true); SI.isValid(); ++SI) {
792 Used.reset(Idx: *SI);
793 if (Implicit) {
794 // For implicit defs, check if there is an implicit use of an
795 // aliased register. If so, mark the aliased reg as used.
796 for (auto *UseOp : UseRegs)
797 if (UseOp->isImplicit() && TRI->regsOverlap(RegA: *SI, RegB: UseOp->getReg()))
798 Used.set(UseOp->getReg());
799 }
800 }
801 };
802 for (unsigned i = 0; i < DefRegs.size(); ++i) {
803 MachineOperand &MO = *DefRegs[i];
804 if (MO.isReg()) {
805 RemoveDef(MO.getReg(), MO.isImplicit());
806 } else if (MO.isRegMask()) {
807 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
808 if (MO.clobbersPhysReg(PhysReg: R))
809 RemoveDef(R, true);
810 }
811 }
812 // The order is important as we are looking from right to left.
813 for (unsigned i = UseRegs.size(); i > 0;) {
814 --i;
815 unsigned UseReg = UseRegs[i]->getReg();
816 bool Killed = true;
817 for (MCRegAliasIterator AI(UseReg, TRI, true); AI.isValid(); ++AI) {
818 if (Used[*AI])
819 Killed = false;
820 }
821 Used.set(UseReg);
822 if (Killed && !UseRegs[i]->isDebug())
823 UseRegs[i]->setIsKill(true);
824 }
825 }
826 // Recreates bundle for updating liveness.
827 for (SmallVectorImpl<MachineInstr *>::iterator MII = BundleHeads.begin();
828 MII != BundleHeads.end(); ++MII) {
829 MachineInstr *MI = *MII;
830 assert(MI && "Invalid bundle head");
831 assert(MI->isBundle() && "Expected a bundle head instruction");
832 assert(MI->getParent() == MBB && "Bundle head not in expected block");
833 MachineBasicBlock::instr_iterator BS = MI->getIterator();
834 MachineBasicBlock::instr_iterator BE = getBundleEnd(I: BS);
835 for (++BS; BS != BE; ++BS)
836 // Remove from bundle so that BUNDLE head can be erased.
837 BS->unbundleFromPred();
838
839 BS = MI->getIterator();
840 ++BS;
841 bool memShufDisabled = QII->getBundleNoShuf(MIB: *MI);
842 MI->eraseFromParent();
843 finalizeBundle(MBB&: *MBB, FirstMI: BS, LastMI: BE);
844 MachineBasicBlock::instr_iterator BundleMII = std::prev(x: BS);
845 if (memShufDisabled)
846 QII->setBundleNoShuf(BundleMII);
847 }
848 return true;
849}
850
851// It deletes the live-in of the \p From MBB.
852bool HexagonLiveVariablesImpl::incrementalUpdate(MICInstIterType MIDelta,
853 MachineBasicBlock *From,
854 MachineBasicBlock *To) {
855 while (!From->livein_empty())
856 From->removeLiveIn(Reg: (*From->livein_begin()).PhysReg);
857 // Handle MI use-def of From.
858 constructUseDef(MBB: From);
859 // Handle MI use-def of To.
860 constructUseDef(MBB: To);
861 // Calculate live-in of From and To
862 // Reuse this by setting all MBBs except From and To as visited.
863 updateGlobalLiveness(X: From, Y: To);
864 // Update local liveness of To.
865 updateLocalLiveness(MBB: From, UpdateBundle: true);
866 updateLocalLiveness(MBB: To, UpdateBundle: true);
867
868 // Do this after the liveness update because MIDelta might not be in the
869 // MIUseDefs before liveness update (since MIDelta might be newly inserted).
870 MIUseDef_t::const_iterator MIUseDef = MIUseDefs.find(Val: &*MIDelta);
871 if (MIUseDef == MIUseDefs.end())
872 llvm_unreachable("MIDelta not found in MIUseDefs after liveness update");
873 const BitVector &Defs = MIUseDef->second.second;
874 int Reg = Defs.find_first();
875 // Adding all the defs as live-ins. This is conservative approach but we
876 // need to add them so as to avoid dealing with callee saved registers and
877 // any unwanted errors in liveness that might arise.
878 while (Reg >= 0) {
879 From->addLiveIn(PhysReg: Reg);
880 Reg = Defs.find_next(Prev: Reg);
881 }
882 return true;
883}
884
885void HexagonLiveVariablesImpl::addNewMBB(MachineBasicBlock *MBB) {
886 // Resize and init.
887 constructUseDef(MBB); // This is to set up some containers for MBB.
888 gatherBlocksDF(Fn&: *MBB->getParent(), Blocks: &BlocksDepthFirst);
889 updateGlobalLiveness(X: MBB, Y: MBB);
890}
891
892// TODO: This is a slow implementation because constructUseDef destroys
893// the MBBLiveOuts which is generated again by updateGlobalLiveness.
894void HexagonLiveVariablesImpl::addNewMI(MachineInstr *MI,
895 MachineBasicBlock *MBB) {
896 constructUseDef(MBB); // This is to set up some containers for MBB.
897 updateGlobalLiveness(X: MBB, Y: MBB);
898}
899
900void HexagonLiveVariablesImpl::generateDistanceMap(const MachineFunction &Fn) {
901 assert(DistanceMap.empty() && "DistanceMap not empty, first clear!");
902 for (MachineFunction::const_iterator MBBI = Fn.begin(), E = Fn.end();
903 MBBI != E; ++MBBI) {
904 const MachineBasicBlock *MBB = &*MBBI;
905 unsigned MBBInsSize = 0;
906 for (MachineBasicBlock::const_instr_iterator MII = MBB->instr_begin(),
907 E = MBB->instr_end();
908 MII != E; ++MII) {
909 const MachineInstr *MI = &*MII;
910 MBBInsSize += QII->getSize(MI: *MI);
911 }
912 DistanceMap[MBB] = MBBInsSize;
913 }
914}
915