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 // Process all of the operands of the instruction...
441 unsigned NumOperandsToProcess = MI->getNumOperands();
442 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
443 MachineOperand &MO = MI->getOperand(i);
444 if (MO.isRegMask()) {
445 // Assuming that predicated defs are not defs, for now.
446 if (!QII->isPredicated(MI: *MI))
447 DefRegs.push_back(Elt: &MO);
448 continue;
449 }
450 if (!MO.isReg() || MO.getReg() == 0)
451 continue;
452 unsigned Reg = MO.getReg();
453 if (MO.isUse()) {
454 // Assuming that the kill-flags on call-instructions are correct.
455 MO.setIsKill(false);
456 UseRegs.push_back(Elt: &MO);
457 MIUseDef.first.set(Reg);
458 } else /*MO.isDef()*/ {
459 assert(MO.isDef());
460 if (!QII->isPredicated(MI: *MI) && !MI->isKill()) {
461 // Assuming that predicated defs are not defs, for now.
462 // KILL instructions are no-ops
463 MO.setIsDead(false);
464 DefRegs.push_back(Elt: &MO);
465 }
466 MIUseDef.second.set(Reg); // Set all defs (including predicated).
467 }
468 }
469 // Process all uses.
470 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i)
471 handlePhysRegUse(MO: UseRegs[i], MI, Uses);
472 // Process all defs.
473 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i)
474 handlePhysRegDef(MO: DefRegs[i], MI, Defs);
475 }
476 DistanceMap[MBB] = MBBInsSize;
477}
478
479void HexagonLiveVariablesImpl::handlePhysRegUse(MachineOperand *MO,
480 MachineInstr *MI,
481 BitVector &Uses) {
482 unsigned Reg = MO->getReg();
483 LLVM_DEBUG(dbgs() << "\nLooking at:";);
484 // If the reg/super-reg is already defined in this MBB => return.
485 for (MCSuperRegIterator SupI(Reg, TRI, true); SupI.isValid(); ++SupI) {
486 LLVM_DEBUG(dbgs() << printReg(*SupI, TRI););
487 if (PhysRegDef[*SupI])
488 return;
489 }
490 // Handle if sub-regs are defined.
491 SmallVector<unsigned, 2> undefSubRegs;
492 bool subRegDefined = false;
493 for (MCSubRegIterator SubI(Reg, TRI); SubI.isValid(); ++SubI) {
494 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI););
495 if (PhysRegDef[*SubI])
496 subRegDefined = true;
497 else
498 undefSubRegs.push_back(Elt: *SubI);
499 }
500
501 LLVM_DEBUG(dbgs() << "\nUses:");
502 if (undefSubRegs.empty()) {
503 if (!subRegDefined) { // None of the subregs are defined.
504 // Include all subregs (including self) to the uses.
505 for (MCSubRegIterator SubI(Reg, TRI, true); SubI.isValid(); ++SubI) {
506 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI));
507 PhysRegUse[*SubI] = MI;
508 Uses.set(*SubI);
509 }
510 } // All subregs defined.
511 return;
512 }
513 // Some subregs are defined.
514 for (unsigned i = 0; i < undefSubRegs.size(); ++i) {
515 LLVM_DEBUG(dbgs() << printReg(undefSubRegs[i], TRI));
516 PhysRegUse[undefSubRegs[i]] = MI;
517 Uses.set(undefSubRegs[i]);
518 }
519}
520
521// Assumes that an MI cannot have a reg and its super/sub reg as uses.
522void HexagonLiveVariablesImpl::handlePhysRegDef(MachineOperand *MO,
523 MachineInstr *MI,
524 BitVector &Defs) {
525 auto SetRegDef = [&](unsigned Reg) -> void {
526 PhysRegDef[Reg] = MI;
527 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
528 if (PhysRegUse[*AI]) {
529 LLVM_DEBUG(dbgs() << "\nUsed in current BB:" << printReg(*AI, TRI));
530 return;
531 }
532 }
533 LLVM_DEBUG(dbgs() << "\nDefs:" << printReg(Reg, TRI));
534 Defs.set(Reg);
535 };
536
537 if (MO->isReg()) {
538 SetRegDef(MO->getReg());
539 } else if (MO->isRegMask()) {
540 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
541 if (MO->clobbersPhysReg(PhysReg: R))
542 SetRegDef(R);
543 }
544}
545
546namespace {
547struct BlockState {
548 bool SuccQueued : 1;
549 bool Done : 1;
550 BlockState() : SuccQueued(false), Done(false) {}
551};
552} // namespace
553
554// Populates 'Blocks' with basic blocks of 'Fn' in depth-first order
555static void gatherBlocksDF(MachineFunction &Fn,
556 SmallVectorImpl<MachineBasicBlock *> *Blocks) {
557 Blocks->clear();
558 Blocks->reserve(N: Fn.size());
559
560 SmallVector<BlockState, 16> State(Fn.size());
561 SmallVector<MachineBasicBlock *, 16> WorkStack;
562 WorkStack.push_back(Elt: &Fn.front());
563 while (!WorkStack.empty()) {
564 MachineBasicBlock *W = WorkStack.back();
565 BlockState &WState = State[W->getNumber()];
566 if (WState.Done) {
567 WorkStack.pop_back();
568 continue;
569 }
570 if (W->succ_empty() || WState.SuccQueued) {
571 WorkStack.pop_back();
572 Blocks->push_back(Elt: W);
573 WState.SuccQueued = true;
574 WState.Done = true;
575 continue;
576 }
577 WState.SuccQueued = true;
578 for (MachineBasicBlock::succ_iterator I = W->succ_begin(),
579 E = W->succ_end();
580 I != E; ++I) {
581 MachineBasicBlock *S = *I;
582 if (State[S->getNumber()].SuccQueued)
583 continue;
584 WorkStack.push_back(Elt: S);
585 }
586 }
587
588 LLVM_DEBUG(
589 dbgs() << "gatherBlocksDF: {";
590 for (SmallVectorImpl<MachineBasicBlock *>::iterator B = Blocks->begin(),
591 BE = Blocks->end();
592 B != BE; ++B) { dbgs() << " BB#" << (*B)->getNumber(); } dbgs()
593 << " }\n";);
594}
595
596bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineFunction &Fn) {
597 bool Changed = false;
598 // Removing live-ins and recomputing.
599 MachineFunction::iterator I = Fn.begin(), E = Fn.end();
600 // Not touching the live-ins of entry basic block.
601 for (++I; I != E; ++I) {
602 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIn(
603 I->livein_begin(), I->livein_end());
604 for (unsigned i = 0; i < OldLiveIn.size(); ++i)
605 I->removeLiveIn(Reg: OldLiveIn[i].PhysReg);
606 }
607
608 gatherBlocksDF(Fn, Blocks: &BlocksDepthFirst);
609
610 BitVector Defs;
611 BitVector LiveIns;
612 bool Repeat;
613 do {
614 Repeat = false;
615 for (SmallVectorImpl<MachineBasicBlock *>::iterator
616 B = BlocksDepthFirst.begin(),
617 BE = BlocksDepthFirst.end();
618 B != BE; ++B) {
619 Repeat |= updateGlobalLiveness(MBB: *B, Defs, LiveIns);
620 }
621 Changed |= Repeat;
622 } while (Repeat);
623
624 Changed |= updateLocalLiveness(Fn);
625 return Changed;
626}
627
628bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *X,
629 MachineBasicBlock *Y) {
630 assert(X && "Invalid start block");
631 assert(Y && "Invalid end block");
632
633 bool Changed = false;
634 BitVector Defs;
635 BitVector LiveIns;
636
637 const SmallVectorImpl<MachineBasicBlock *>::iterator BE =
638 BlocksDepthFirst.end();
639 SmallVectorImpl<MachineBasicBlock *>::iterator B;
640 for (B = BlocksDepthFirst.begin(); (B != BE); ++B) {
641 if (*B == X)
642 break;
643 if (*B == Y)
644 break;
645 }
646
647 bool Repeat;
648 do {
649 Repeat = false;
650 for (; B != BE; ++B)
651 Repeat |= updateGlobalLiveness(MBB: *B, Defs, LiveIns);
652 Changed |= Repeat;
653 B = BlocksDepthFirst.begin();
654 } while (Repeat);
655
656 return Changed;
657}
658
659// Defs and LiveIns could be local variables within updateGlobalLiveness, but
660// have been pulled out to (hopefully) improve performance.
661bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *MBB,
662 BitVector &Defs,
663 BitVector &LiveIns) {
664 LLVM_DEBUG(dbgs() << "\nTrying to Update Liveness MBB#" << MBB->getNumber());
665 bool Changed = false;
666 LLVM_DEBUG(dbgs() << "\nUpdating Liveness MBB#" << MBB->getNumber());
667 // Update live-outs
668 auto LiveOutIt = MBBLiveOuts.find(Val: MBB);
669 if (LiveOutIt == MBBLiveOuts.end())
670 LiveOutIt = MBBLiveOuts.insert(KV: {MBB, BitVector(NumRegs)}).first;
671 BitVector &LiveOuts = LiveOutIt->second;
672 for (MachineBasicBlock::succ_iterator MBBSucc = MBB->succ_begin();
673 MBBSucc != MBB->succ_end(); ++MBBSucc) {
674 MachineBasicBlock *Succ = *MBBSucc;
675 LLVM_DEBUG(dbgs() << "\n\t\tAdding LiveOut:";);
676 for (MachineBasicBlock::livein_iterator LI = Succ->livein_begin(),
677 LE = Succ->livein_end();
678 LI != LE; ++LI) {
679 if (!LiveOuts[(*LI).PhysReg]) {
680 LLVM_DEBUG(dbgs() << " " << printReg((*LI).PhysReg, TRI););
681 LiveOuts.set((*LI).PhysReg);
682 Changed = true;
683 }
684 }
685 }
686 LLVM_DEBUG(dbgs() << "\nUpdated Successors of MBB#" << MBB->getNumber());
687 // Update live-ins
688 Changed |= updateLiveIns(MBB, LiveIns, LiveOuts);
689
690 return Changed;
691}
692
693// update live-ins when live-out has been calculated
694bool HexagonLiveVariablesImpl::updateLiveIns(MachineBasicBlock *MBB,
695 BitVector &LiveIns,
696 const BitVector &LiveOuts) {
697 LLVM_DEBUG(dbgs() << "\n[updateLiveIns] MBB#" << MBB->getNumber());
698 bool Changed = false;
699 const std::pair<BitVector, BitVector> &UseDefs = MBBUseDefs[MBB];
700 LiveIns = LiveOuts;
701 // LiveIns = (LiveOuts - Defs) | Uses
702 // Equivalent to: LiveIns = (LiveOuts & ~Defs) | Uses
703 LiveIns.reset(RHS: UseDefs.second);
704 LiveIns |= UseDefs.first;
705 LLVM_DEBUG(dbgs() << "\n\t\tAdded LiveIn:";);
706 for (int i = LiveIns.find_first(); i >= 0; i = LiveIns.find_next(Prev: i)) {
707 // TODO: remove costly check of MBB->isLiveIn when fully functional.
708 if (!MBB->isLiveIn(Reg: i) && MRI->isAllocatable(PhysReg: i)) {
709 LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
710 MBB->addLiveIn(PhysReg: i);
711 Changed = true;
712 }
713 }
714 return Changed;
715}
716
717bool HexagonLiveVariablesImpl::updateLiveOuts(MachineBasicBlock *MBB,
718 BitVector &LiveOuts) {
719 bool Changed = false;
720 for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
721 MachineBasicBlock *SB = *SI;
722 for (auto I = SB->livein_begin(), E = SB->livein_end(); I != E; ++I) {
723 unsigned R = (*I).PhysReg;
724 if (LiveOuts[R])
725 continue;
726 LiveOuts.set(R);
727 Changed = true;
728 }
729 }
730 return Changed;
731}
732
733bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineFunction &Fn) {
734 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness]");
735 for (MachineFunction::iterator B = Fn.begin(), E = Fn.end(); B != E; ++B)
736 updateLocalLiveness(MBB: &*B, UpdateBundle: false);
737 return true;
738}
739
740bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineBasicBlock *MBB,
741 bool UpdateBundle) {
742 assert(MBB && "Invalid basic block");
743 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness] MBB#" << MBB->getNumber());
744
745 BitVector &LiveOut = MBBLiveOuts[MBB];
746 updateLiveOuts(MBB, LiveOuts&: LiveOut);
747
748 BitVector Used = LiveOut;
749 SmallVector<MachineInstr *, 2> BundleHeads;
750 // Bottom up traversal of MBB.
751 for (MachineBasicBlock::reverse_instr_iterator MII = MBB->instr_rbegin(),
752 MIREnd = MBB->instr_rend();
753 MII != MIREnd; ++MII) {
754 MachineInstr *MI = &*MII;
755 // The bundle liveness is updated differently.
756 if (MI->isBundle()) {
757 if (UpdateBundle)
758 BundleHeads.push_back(Elt: MI);
759 continue;
760 }
761 if (MI->isDebugInstr()) // DBG_VALUE may have invalid reg.
762 continue;
763 SmallVector<MachineOperand *, 4> UseRegs;
764 SmallVector<MachineOperand *, 2> DefRegs;
765 for (unsigned i = 0; i < MI->getNumOperands(); ++i) {
766 MachineOperand &MO = MI->getOperand(i);
767 if (MO.isReg()) { // DBG_VALUE may have invalid reg.
768 if (MO.isUse())
769 UseRegs.push_back(Elt: &MO);
770 else { // Def
771 if (!QII->isPredicated(MI: *MI) && !MI->isKill()) {
772 // Assuming that predicated defs are not defs, for now.
773 // KILL instructions are no-ops
774 DefRegs.push_back(Elt: &MO);
775 }
776 }
777 } else if (MO.isRegMask()) {
778 if (!QII->isPredicated(MI: *MI))
779 DefRegs.push_back(Elt: &MO);
780 }
781 }
782 // In case of a def. remove Reg and its sub-regs from Used list
783 // such that uses in the same MI can be marked as kill.
784 auto RemoveDef = [&](unsigned Reg, bool Implicit) -> void {
785 for (MCSubRegIterator SI(Reg, TRI, true); SI.isValid(); ++SI) {
786 Used.reset(Idx: *SI);
787 if (Implicit) {
788 // For implicit defs, check if there is an implicit use of an
789 // aliased register. If so, mark the aliased reg as used.
790 for (auto *UseOp : UseRegs)
791 if (UseOp->isImplicit() && TRI->regsOverlap(RegA: *SI, RegB: UseOp->getReg()))
792 Used.set(UseOp->getReg());
793 }
794 }
795 };
796 for (unsigned i = 0; i < DefRegs.size(); ++i) {
797 MachineOperand &MO = *DefRegs[i];
798 if (MO.isReg()) {
799 RemoveDef(MO.getReg(), MO.isImplicit());
800 } else if (MO.isRegMask()) {
801 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
802 if (MO.clobbersPhysReg(PhysReg: R))
803 RemoveDef(R, true);
804 }
805 }
806 // The order is important as we are looking from right to left.
807 for (unsigned i = UseRegs.size(); i > 0;) {
808 --i;
809 unsigned UseReg = UseRegs[i]->getReg();
810 bool Killed = true;
811 for (MCRegAliasIterator AI(UseReg, TRI, true); AI.isValid(); ++AI) {
812 if (Used[*AI])
813 Killed = false;
814 }
815 Used.set(UseReg);
816 if (Killed && !UseRegs[i]->isDebug())
817 UseRegs[i]->setIsKill(true);
818 }
819 }
820 // Recreates bundle for updating liveness.
821 for (SmallVectorImpl<MachineInstr *>::iterator MII = BundleHeads.begin();
822 MII != BundleHeads.end(); ++MII) {
823 MachineInstr *MI = *MII;
824 assert(MI && "Invalid bundle head");
825 assert(MI->isBundle() && "Expected a bundle head instruction");
826 assert(MI->getParent() == MBB && "Bundle head not in expected block");
827 MachineBasicBlock::instr_iterator BS = MI->getIterator();
828 MachineBasicBlock::instr_iterator BE = getBundleEnd(I: BS);
829 for (++BS; BS != BE; ++BS)
830 // Remove from bundle so that BUNDLE head can be erased.
831 BS->unbundleFromPred();
832
833 BS = MI->getIterator();
834 ++BS;
835 bool memShufDisabled = QII->getBundleNoShuf(MIB: *MI);
836 MI->eraseFromParent();
837 finalizeBundle(MBB&: *MBB, FirstMI: BS, LastMI: BE);
838 MachineBasicBlock::instr_iterator BundleMII = std::prev(x: BS);
839 if (memShufDisabled)
840 QII->setBundleNoShuf(BundleMII);
841 }
842 return true;
843}
844
845// It deletes the live-in of the \p From MBB.
846bool HexagonLiveVariablesImpl::incrementalUpdate(MICInstIterType MIDelta,
847 MachineBasicBlock *From,
848 MachineBasicBlock *To) {
849 while (!From->livein_empty())
850 From->removeLiveIn(Reg: (*From->livein_begin()).PhysReg);
851 // Handle MI use-def of From.
852 constructUseDef(MBB: From);
853 // Handle MI use-def of To.
854 constructUseDef(MBB: To);
855 // Calculate live-in of From and To
856 // Reuse this by setting all MBBs except From and To as visited.
857 updateGlobalLiveness(X: From, Y: To);
858 // Update local liveness of To.
859 updateLocalLiveness(MBB: From, UpdateBundle: true);
860 updateLocalLiveness(MBB: To, UpdateBundle: true);
861
862 // Do this after the liveness update because MIDelta might not be in the
863 // MIUseDefs before liveness update (since MIDelta might be newly inserted).
864 MIUseDef_t::const_iterator MIUseDef = MIUseDefs.find(Val: &*MIDelta);
865 if (MIUseDef == MIUseDefs.end())
866 llvm_unreachable("MIDelta not found in MIUseDefs after liveness update");
867 const BitVector &Defs = MIUseDef->second.second;
868 int Reg = Defs.find_first();
869 // Adding all the defs as live-ins. This is conservative approach but we
870 // need to add them so as to avoid dealing with callee saved registers and
871 // any unwanted errors in liveness that might arise.
872 while (Reg >= 0) {
873 From->addLiveIn(PhysReg: Reg);
874 Reg = Defs.find_next(Prev: Reg);
875 }
876 return true;
877}
878
879void HexagonLiveVariablesImpl::addNewMBB(MachineBasicBlock *MBB) {
880 // Resize and init.
881 constructUseDef(MBB); // This is to set up some containers for MBB.
882 gatherBlocksDF(Fn&: *MBB->getParent(), Blocks: &BlocksDepthFirst);
883 updateGlobalLiveness(X: MBB, Y: MBB);
884}
885
886// TODO: This is a slow implementation because constructUseDef destroys
887// the MBBLiveOuts which is generated again by updateGlobalLiveness.
888void HexagonLiveVariablesImpl::addNewMI(MachineInstr *MI,
889 MachineBasicBlock *MBB) {
890 constructUseDef(MBB); // This is to set up some containers for MBB.
891 updateGlobalLiveness(X: MBB, Y: MBB);
892}
893
894void HexagonLiveVariablesImpl::generateDistanceMap(const MachineFunction &Fn) {
895 assert(DistanceMap.empty() && "DistanceMap not empty, first clear!");
896 for (MachineFunction::const_iterator MBBI = Fn.begin(), E = Fn.end();
897 MBBI != E; ++MBBI) {
898 const MachineBasicBlock *MBB = &*MBBI;
899 unsigned MBBInsSize = 0;
900 for (MachineBasicBlock::const_instr_iterator MII = MBB->instr_begin(),
901 E = MBB->instr_end();
902 MII != E; ++MII) {
903 const MachineInstr *MI = &*MII;
904 MBBInsSize += QII->getSize(MI: *MI);
905 }
906 DistanceMap[MBB] = MBBInsSize;
907 }
908}
909