LLVM 24.0.0git
HexagonLiveVariables.cpp
Go to the documentation of this file.
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
21#include "llvm/CodeGen/Passes.h"
23#include "llvm/Support/Debug.h"
25
26using namespace llvm;
27
30
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;
41
43
45
46 const HexagonInstrInfo *QII;
47
48 unsigned NumRegs;
49
50 /// PhysRegInfo - Keep track of which instruction was the last def of a
51 /// physical register (possibly after a use). This is purely local to a BB.
53
54 /// PhysRegInfo - Keep track of which instruction was the last use of a
55 /// physical register (before any def). This is purely local property to a BB.
57
58 /// MBB -> (Uses, Defs)
59 /// Uses - use before any def in that MBB.
60 /// Defs - def before any uses in that MBB.
61 MBBUseDef_t MBBUseDefs;
62
63 /// MI -> (Uses, Defs)
64 MIUseDef_t MIUseDefs;
65
66 /// Live-out data for each MBB => U LiveIns (For all Successors of a MBB).
68
69 /// Each MachineBasicBlock is assigned a Distance which is
70 /// an approximation of MBB->size()*INSTR_SIZE+Some offsets.
71 /// This is helpful in quickly finding distance between
72 /// a branch and its target.
73 /// @note A pass which moves instructions should update this.
74 /// @note The data in distance map should be used carefully because
75 /// difference in the distances of two MI might not give relative distances
76 /// between them. The DistanceMap is mainly useful during pullup.
78
79 // Blocks in depth first order
81
82 /// @brief Constructs use-defs of \p MBB by analyzing each MachineOperand.
83 /// Collects relevant information so that global liveness can be updated.
85
86 /// Collects used-before-define set of registers.
87 /// A register is considered to be completely defined if
88 /// 1. The register
89 /// 2. Any of its super-reg
90 /// 3. All of its subregs
91 /// are defined. In these cases the register is not considered as
92 /// used-before-defined. In case of partial definition of a register
93 /// before its use, only the remaining subregs are included in the use-set.
94 /// @note: Assumes that a register can be completely defined, by defining
95 /// all of its sub-regs (if any).
96 void handlePhysRegUse(MachineOperand *MO, MachineInstr *MI, BitVector &Uses);
97
98 /// Collects defined-before-use set of registers. If there is any
99 /// use of register or its aliases then the register is not counted
100 /// as defined-before-use
101 /// @note: Assumes that a register can be completely defined, by defining
102 /// all of its sub-regs (if any).
103 void handlePhysRegDef(MachineOperand *MO, MachineInstr *MI, BitVector &Defs);
104
105 /// updateGlobalLiveness - wrapper around another overload
106 inline bool updateGlobalLiveness(MachineFunction &Fn);
107 bool updateGlobalLiveness(MachineBasicBlock *X, MachineBasicBlock *Y);
108
109 /// updateGlobalLiveness - updates liveness based on
110 /// livein and liveout entries.
111 bool updateGlobalLiveness(MachineBasicBlock *MBB, BitVector &Defs,
112 BitVector &LiveIns);
113
114 /// update live-ins when live-out has been calculated
115 bool updateLiveIns(MachineBasicBlock *MBB, BitVector &LiveIns,
116 const BitVector &LiveOuts);
117
118 bool updateLiveOuts(MachineBasicBlock *MBB, BitVector &LiveOuts);
119
120 /// updateLocalLiveness - update only kill flags of operands.
121 inline bool updateLocalLiveness(MachineFunction &Fn);
122
123 /// updateLocalLiveness - update only kill flags of operands.
125
126 /// incrementalUpdate - update the liveness when \p MIDelta is moved from
127 /// \p From to \p To.
128 /// @note: This is extremely fragile now. It 'assumes' that the other
129 /// successor(s) of \p To do not use Defs of MIDelta.
130 /// It deletes the live-in of the \p From MBB.
133
134 /// addNewMBB - inform the LiveVariable Analysis that new MBB has been added.
135 /// update the liveness of this new MBB.
136 /// @note MBB should be empty. If we want to add an MI, add it after calling
137 /// this function.
139
141 unsigned getNumRegs() const { return NumRegs; }
142
143 // Useful for clearing out after passes which move instructions around.
144 // e.g. GlobalScheduler.
145 void clearDistanceMap() { DistanceMap.clear(); }
146
147 /// Computes \p DistanceMap.
148 void generateDistanceMap(const MachineFunction &Fn);
149
150public:
153};
154
155//===----------------------------------------------------------------------===//
156// HexagonLiveVariables Functions
157//===----------------------------------------------------------------------===//
163
171
173 if (HLVComplete)
174 return;
175 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
176 auto &MPDT =
178 HLV->runOnMachineFunction(MF, MDT, MPDT);
179}
180
182 return HLV->updateLocalLiveness(Fn);
183}
184
186 bool updateBundle) {
187 HLV->constructUseDef(MBB); // XXX: This destroys MBBLiveOuts!
188 return HLV->updateLocalLiveness(MBB, updateBundle);
189}
190
192 MachineBasicBlock *From,
193 MachineBasicBlock *To) {
194 assert(MIDelta->getParent() == To);
195 assert(From != To);
196 return HLV->incrementalUpdate(MIDelta, From, To);
197}
198
200 assert(MBB->empty());
201 HLV->addNewMBB(MBB);
202}
203
207
209 HLV->constructUseDef(MBB);
210}
211
213 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
214 auto &MPDT =
216 HLVComplete = !HLV->runOnMachineFunction(Fn, MDT, MPDT);
217 return HLVComplete;
218}
219
221 unsigned Reg) const {
222 assert(HLVComplete && "Liveness Analysis not available");
223 auto It = HLV->MBBLiveOuts.find(MBB);
224 if (It == HLV->MBBLiveOuts.end())
225 llvm_unreachable("MBB not found in liveness map");
226 if (Reg >= It->second.size())
227 llvm_unreachable("Register index out of bounds");
228 return It->second[Reg];
229}
230
231const BitVector &
233 assert(HLVComplete && "Liveness Analysis not available");
234 auto It = HLV->MBBLiveOuts.find(MBB);
235 if (It == HLV->MBBLiveOuts.end())
236 llvm_unreachable("MBB not found in liveness map");
237 return It->second;
238}
239
240// Returns true when \p Reg is used within [MIBegin, MIEnd)
241// @note: MIBegin and MIEnd should be from same MBB
242// @note: It returns just the first use found in the range.
243// The Use is closest to MIEnd.
244// Takes care of aliases and predicated defs as well.
246 MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg,
248 SmallPtrSet<MachineInstr *, 2> *ExceptionsList) const {
249 assert(HLVComplete && "Liveness Analysis not available");
250 Use = MIEnd;
251 if (MIBegin == MIEnd) // NULL Range.
252 return false;
253 MICInstIterType MII = MIEnd;
254 do {
255 --MII;
256 if (MII->isBundle() || MII->isDebugInstr())
257 continue;
258 if (ExceptionsList && ExceptionsList->contains(&*MII))
259 continue;
260 auto It = HLV->MIUseDefs.find(&*MII);
261 assert(It != HLV->MIUseDefs.end());
262 for (MCRegAliasIterator AI(Reg, HLV->TRI, true); AI.isValid(); ++AI)
263 if (It->second.first[*AI]) {
264 Use = MII;
265 return true;
266 }
267 } while (MII != MIBegin);
268 return false;
269}
270
271// Returns true when \p Reg id defined within [MIBegin, MIEnd)
272// @note: MIBegin and MIEnd should be from same MBB
273// The Def is closest to MIEnd.
274// Takes care of aliases and predicated defs as well.
276 MICInstIterType MIEnd, unsigned Reg,
277 MICInstIterType &Def) const {
278 assert(HLVComplete && "Liveness Analysis not available");
279 Def = MIEnd;
280 if (MIBegin == MIEnd) // NULL Range.
281 return false;
282 MICInstIterType MII = MIEnd;
283 do {
284 --MII;
285 if (MII->isBundle() || MII->isDebugInstr())
286 continue;
287 auto It = HLV->MIUseDefs.find(&*MII);
288 assert(It != HLV->MIUseDefs.end());
289 for (MCRegAliasIterator AI(Reg, HLV->TRI, true); AI.isValid(); ++AI)
290 if (It->second.second[*AI]) {
291 Def = MII;
292 return true;
293 }
294 } while (MII != MIBegin);
295 return false;
296}
297
298// Returns true if any of the defs of MII is live-in in the MBB.
300 const MachineBasicBlock *MBB) const {
301 assert(HLVComplete && "Liveness Analysis not available");
302 assert(MI && "Invalid machine instruction");
303 assert(MBB && "Invalid machine basic block");
304 auto It = HLV->MIUseDefs.find(MI);
305 assert(It != HLV->MIUseDefs.end() && "Missing MI use/def information");
306 BitVector MBBLiveIns(HLV->NumRegs);
307 for (MachineBasicBlock::livein_iterator lit = MBB->livein_begin();
308 lit != MBB->livein_end(); ++lit) {
309 // Include all the aliases of reg *lit.
310 for (MCRegAliasIterator AI((*lit).PhysReg, HLV->TRI, true); AI.isValid();
311 ++AI)
312 MBBLiveIns.set(*AI);
313 }
314 // Intersect.
315 return MBBLiveIns.anyCommon(It->second.second);
316}
317
319
321
323 const MachineBasicBlock *To,
324 unsigned BufferPerMBB) const {
325 assert(HLV->DistanceMap.find(From) != HLV->DistanceMap.end());
326 assert(HLV->DistanceMap.find(To) != HLV->DistanceMap.end());
327 unsigned FromSize = HLV->DistanceMap[From];
328 if (From == To)
329 return FromSize;
330 const MachineFunction *MF = From->getParent();
332 unsigned S = BufferPerMBB;
333 bool ToFirst = false;
334 while (MBBI != MF->end()) {
335 const MachineBasicBlock *MBB = &*MBBI;
336 if (MBB == From)
337 break;
338 else if (MBB == To) {
339 ToFirst = true;
340 break;
341 }
342 ++MBBI;
343 }
344 const MachineBasicBlock *ToFind = To;
345 if (ToFirst)
346 ToFind = From;
347 while (MBBI != MF->end()) {
348 const MachineBasicBlock *MBB = &*MBBI;
349 if (MBB == ToFind)
350 break;
351 S += HLV->DistanceMap[MBB] + BufferPerMBB;
352 ++MBBI;
353 }
354 if (ToFirst) // Jump in the opposite direction.
355 S += FromSize + HLV->DistanceMap[To] + 2 * BufferPerMBB;
356 return S;
357}
358
360 HLV->clearDistanceMap();
361 HLV->generateDistanceMap(Fn);
362}
363
364//===----------------------------------------------------------------------===//
365// HexagonLiveVariablesImpl Functions
366//===----------------------------------------------------------------------===//
367bool HexagonLiveVariablesImpl::runOnMachineFunction(
370 LLVM_DEBUG(dbgs() << "\nHexagon Live Variables";);
371 Fn.RenumberBlocks();
372
373 MRI = &Fn.getRegInfo();
374 auto &ST = Fn.getSubtarget<HexagonSubtarget>();
375 TRI = ST.getRegisterInfo();
376 QII = ST.getInstrInfo();
377
378 NumRegs = TRI->getNumRegs();
379
380 MBBUseDefs.clear();
381 MIUseDefs.clear();
382 MBBLiveOuts.clear();
383
384 LLVM_DEBUG(dbgs() << "\nNumber of registers in Hexagon is:" << NumRegs);
385
386 PhysRegDef.resize(NumRegs);
387 PhysRegUse.resize(NumRegs);
388
389 for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); MBBI != E;
390 ++MBBI) {
391 constructUseDef(&*MBBI);
392 }
393 updateGlobalLiveness(Fn);
394 return false;
395}
396
397void HexagonLiveVariablesImpl::constructUseDef(MachineBasicBlock *MBB) {
398 std::fill(PhysRegDef.begin(), PhysRegDef.end(), (MachineInstr *)0);
399 std::fill(PhysRegUse.begin(), PhysRegUse.end(), (MachineInstr *)0);
400
401 // Loop over all of the instructions, processing them.
402 std::pair<BitVector, BitVector> &UseDef = MBBUseDefs[MBB];
403 // Use before any def in a BB.
404 BitVector &Uses = UseDef.first;
405 // Defs before any use in a BB.
406 BitVector &Defs = UseDef.second;
407 // Initializing the LiveOut bit vector.
408 BitVector &LiveOuts = MBBLiveOuts[MBB];
409 Uses.resize(NumRegs, false);
410 Defs.resize(NumRegs, false);
411 LiveOuts.resize(NumRegs, false);
412 // BitVector might contain set bits out of previous liveness updates.
413 Uses.reset();
414 Defs.reset();
415 LiveOuts.reset();
416 LLVM_DEBUG(dbgs() << "\nBB#" << MBB->getNumber(););
417 // MBB Number in the MSB 32 bits.
418 unsigned MBBInsSize = 0;
420 E = MBB->instr_end();
421 MII != E; ++MII) {
422 MachineInstr *MI = &*MII;
423 MBBInsSize += QII->getSize(*MI);
424 // TODO: Handle isDebugInstr
425 if (MI->isBundle() || MI->isDebugInstr())
426 continue;
427 LLVM_DEBUG(dbgs() << "\n\n" << *MI;);
428 // Clear kill and dead markers. LV will recompute them.
429 UseDef_t &MIUseDef = MIUseDefs[MI];
430 MIUseDef.first.resize(NumRegs); // Uses
431 MIUseDef.second.resize(NumRegs); // Defs
432 MIUseDef.first.reset(); // Uses
433 MIUseDef.second.reset(); // Defs
434
437 // Process all of the operands of the instruction...
438 unsigned NumOperandsToProcess = MI->getNumOperands();
439 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
440 MachineOperand &MO = MI->getOperand(i);
441 if (MO.isRegMask()) {
442 // Assuming that predicated defs are not defs, for now.
443 if (!QII->isPredicated(*MI))
444 DefRegs.push_back(&MO);
445 continue;
446 }
447 if (!MO.isReg() || MO.getReg() == 0)
448 continue;
449 unsigned Reg = MO.getReg();
450 if (MO.isUse()) {
451 // Assuming that the kill-flags on call-instructions are correct.
452 MO.setIsKill(false);
453 UseRegs.push_back(&MO);
454 MIUseDef.first.set(Reg);
455 } else /*MO.isDef()*/ {
456 assert(MO.isDef());
457 if (!QII->isPredicated(*MI) && !MI->isKill()) {
458 // Assuming that predicated defs are not defs, for now.
459 // KILL instructions are no-ops
460 MO.setIsDead(false);
461 DefRegs.push_back(&MO);
462 }
463 MIUseDef.second.set(Reg); // Set all defs (including predicated).
464 }
465 }
466 // Process all uses.
467 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i)
468 handlePhysRegUse(UseRegs[i], MI, Uses);
469 // Process all defs.
470 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i)
471 handlePhysRegDef(DefRegs[i], MI, Defs);
472 }
473 DistanceMap[MBB] = MBBInsSize;
474}
475
476void HexagonLiveVariablesImpl::handlePhysRegUse(MachineOperand *MO,
478 BitVector &Uses) {
479 unsigned Reg = MO->getReg();
480 LLVM_DEBUG(dbgs() << "\nLooking at:";);
481 // If the reg/super-reg is already defined in this MBB => return.
482 for (MCSuperRegIterator SupI(Reg, TRI, true); SupI.isValid(); ++SupI) {
483 LLVM_DEBUG(dbgs() << printReg(*SupI, TRI););
484 if (PhysRegDef[*SupI])
485 return;
486 }
487 // Handle if sub-regs are defined.
488 SmallVector<unsigned, 2> undefSubRegs;
489 bool subRegDefined = false;
490 for (MCSubRegIterator SubI(Reg, TRI); SubI.isValid(); ++SubI) {
491 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI););
492 if (PhysRegDef[*SubI])
493 subRegDefined = true;
494 else
495 undefSubRegs.push_back(*SubI);
496 }
497
498 LLVM_DEBUG(dbgs() << "\nUses:");
499 if (undefSubRegs.empty()) {
500 if (!subRegDefined) { // None of the subregs are defined.
501 // Include all subregs (including self) to the uses.
502 for (MCSubRegIterator SubI(Reg, TRI, true); SubI.isValid(); ++SubI) {
503 LLVM_DEBUG(dbgs() << printReg(*SubI, TRI));
504 PhysRegUse[*SubI] = MI;
505 Uses.set(*SubI);
506 }
507 } // All subregs defined.
508 return;
509 }
510 // Some subregs are defined.
511 for (unsigned i = 0; i < undefSubRegs.size(); ++i) {
512 LLVM_DEBUG(dbgs() << printReg(undefSubRegs[i], TRI));
513 PhysRegUse[undefSubRegs[i]] = MI;
514 Uses.set(undefSubRegs[i]);
515 }
516}
517
518// Assumes that an MI cannot have a reg and its super/sub reg as uses.
519void HexagonLiveVariablesImpl::handlePhysRegDef(MachineOperand *MO,
521 BitVector &Defs) {
522 auto SetRegDef = [&](unsigned Reg) -> void {
523 PhysRegDef[Reg] = MI;
524 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
525 if (PhysRegUse[*AI]) {
526 LLVM_DEBUG(dbgs() << "\nUsed in current BB:" << printReg(*AI, TRI));
527 return;
528 }
529 }
530 LLVM_DEBUG(dbgs() << "\nDefs:" << printReg(Reg, TRI));
531 Defs.set(Reg);
532 };
533
534 if (MO->isReg()) {
535 SetRegDef(MO->getReg());
536 } else if (MO->isRegMask()) {
537 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
538 if (MO->clobbersPhysReg(R))
539 SetRegDef(R);
540 }
541}
542
543namespace {
544struct BlockState {
545 bool SuccQueued : 1;
546 bool Done : 1;
547 BlockState() : SuccQueued(false), Done(false) {}
548};
549} // namespace
550
551// Populates 'Blocks' with basic blocks of 'Fn' in depth-first order
554 Blocks->clear();
555 Blocks->reserve(Fn.size());
556
559 WorkStack.push_back(&Fn.front());
560 while (!WorkStack.empty()) {
561 MachineBasicBlock *W = WorkStack.back();
562 BlockState &WState = State[W->getNumber()];
563 if (WState.Done) {
564 WorkStack.pop_back();
565 continue;
566 }
567 if (W->succ_empty() || WState.SuccQueued) {
568 WorkStack.pop_back();
569 Blocks->push_back(W);
570 WState.SuccQueued = true;
571 WState.Done = true;
572 continue;
573 }
574 WState.SuccQueued = true;
575 for (MachineBasicBlock::succ_iterator I = W->succ_begin(),
576 E = W->succ_end();
577 I != E; ++I) {
578 MachineBasicBlock *S = *I;
579 if (State[S->getNumber()].SuccQueued)
580 continue;
581 WorkStack.push_back(S);
582 }
583 }
584
586 dbgs() << "gatherBlocksDF: {";
588 BE = Blocks->end();
589 B != BE; ++B) { dbgs() << " BB#" << (*B)->getNumber(); } dbgs()
590 << " }\n";);
591}
592
593bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineFunction &Fn) {
594 bool Changed = false;
595 // Removing live-ins and recomputing.
596 MachineFunction::iterator I = Fn.begin(), E = Fn.end();
597 // Not touching the live-ins of entry basic block.
598 for (++I; I != E; ++I) {
599 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIn(
600 I->livein_begin(), I->livein_end());
601 for (unsigned i = 0; i < OldLiveIn.size(); ++i)
602 I->removeLiveIn(OldLiveIn[i].PhysReg);
603 }
604
605 gatherBlocksDF(Fn, &BlocksDepthFirst);
606
607 BitVector Defs;
608 BitVector LiveIns;
609 bool Repeat;
610 do {
611 Repeat = false;
613 B = BlocksDepthFirst.begin(),
614 BE = BlocksDepthFirst.end();
615 B != BE; ++B) {
616 Repeat |= updateGlobalLiveness(*B, Defs, LiveIns);
617 }
618 Changed |= Repeat;
619 } while (Repeat);
620
621 Changed |= updateLocalLiveness(Fn);
622 return Changed;
623}
624
625bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *X,
627 assert(X && "Invalid start block");
628 assert(Y && "Invalid end block");
629
630 bool Changed = false;
631 BitVector Defs;
632 BitVector LiveIns;
633
635 BlocksDepthFirst.end();
637 for (B = BlocksDepthFirst.begin(); (B != BE); ++B) {
638 if (*B == X)
639 break;
640 if (*B == Y)
641 break;
642 }
643
644 bool Repeat;
645 do {
646 Repeat = false;
647 for (; B != BE; ++B)
648 Repeat |= updateGlobalLiveness(*B, Defs, LiveIns);
649 Changed |= Repeat;
650 B = BlocksDepthFirst.begin();
651 } while (Repeat);
652
653 return Changed;
654}
655
656// Defs and LiveIns could be local variables within updateGlobalLiveness, but
657// have been pulled out to (hopefully) improve performance.
658bool HexagonLiveVariablesImpl::updateGlobalLiveness(MachineBasicBlock *MBB,
659 BitVector &Defs,
660 BitVector &LiveIns) {
661 LLVM_DEBUG(dbgs() << "\nTrying to Update Liveness MBB#" << MBB->getNumber());
662 bool Changed = false;
663 LLVM_DEBUG(dbgs() << "\nUpdating Liveness MBB#" << MBB->getNumber());
664 // Update live-outs
665 auto LiveOutIt = MBBLiveOuts.find(MBB);
666 if (LiveOutIt == MBBLiveOuts.end())
667 LiveOutIt = MBBLiveOuts.insert({MBB, BitVector(NumRegs)}).first;
668 BitVector &LiveOuts = LiveOutIt->second;
670 MBBSucc != MBB->succ_end(); ++MBBSucc) {
671 MachineBasicBlock *Succ = *MBBSucc;
672 LLVM_DEBUG(dbgs() << "\n\t\tAdding LiveOut:";);
674 LE = Succ->livein_end();
675 LI != LE; ++LI) {
676 if (!LiveOuts[(*LI).PhysReg]) {
677 LLVM_DEBUG(dbgs() << " " << printReg((*LI).PhysReg, TRI););
678 LiveOuts.set((*LI).PhysReg);
679 Changed = true;
680 }
681 }
682 }
683 LLVM_DEBUG(dbgs() << "\nUpdated Successors of MBB#" << MBB->getNumber());
684 // Update live-ins
685 Changed |= updateLiveIns(MBB, LiveIns, LiveOuts);
686
687 return Changed;
688}
689
690// update live-ins when live-out has been calculated
691bool HexagonLiveVariablesImpl::updateLiveIns(MachineBasicBlock *MBB,
692 BitVector &LiveIns,
693 const BitVector &LiveOuts) {
694 LLVM_DEBUG(dbgs() << "\n[updateLiveIns] MBB#" << MBB->getNumber());
695 bool Changed = false;
696 const std::pair<BitVector, BitVector> &UseDefs = MBBUseDefs[MBB];
697 LiveIns = LiveOuts;
698 // LiveIns = (LiveOuts - Defs) | Uses
699 // Equivalent to: LiveIns = (LiveOuts & ~Defs) | Uses
700 LiveIns.reset(UseDefs.second);
701 LiveIns |= UseDefs.first;
702 LLVM_DEBUG(dbgs() << "\n\t\tAdded LiveIn:";);
703 for (int i = LiveIns.find_first(); i >= 0; i = LiveIns.find_next(i)) {
704 // TODO: remove costly check of MBB->isLiveIn when fully functional.
705 if (!MBB->isLiveIn(i) && MRI->isAllocatable(i)) {
706 LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
707 MBB->addLiveIn(i);
708 Changed = true;
709 }
710 }
711 return Changed;
712}
713
714bool HexagonLiveVariablesImpl::updateLiveOuts(MachineBasicBlock *MBB,
715 BitVector &LiveOuts) {
716 bool Changed = false;
717 for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
718 MachineBasicBlock *SB = *SI;
719 for (auto I = SB->livein_begin(), E = SB->livein_end(); I != E; ++I) {
720 unsigned R = (*I).PhysReg;
721 if (LiveOuts[R])
722 continue;
723 LiveOuts.set(R);
724 Changed = true;
725 }
726 }
727 return Changed;
728}
729
730bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineFunction &Fn) {
731 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness]");
732 for (MachineFunction::iterator B = Fn.begin(), E = Fn.end(); B != E; ++B)
733 updateLocalLiveness(&*B, false);
734 return true;
735}
736
737bool HexagonLiveVariablesImpl::updateLocalLiveness(MachineBasicBlock *MBB,
738 bool UpdateBundle) {
739 assert(MBB && "Invalid basic block");
740 LLVM_DEBUG(dbgs() << "\n[updateLocalLiveness] MBB#" << MBB->getNumber());
741
742 BitVector &LiveOut = MBBLiveOuts[MBB];
743 updateLiveOuts(MBB, LiveOut);
744
745 BitVector Used = LiveOut;
747 // Bottom up traversal of MBB.
749 MIREnd = MBB->instr_rend();
750 MII != MIREnd; ++MII) {
751 MachineInstr *MI = &*MII;
752 // The bundle liveness is updated differently.
753 if (MI->isBundle()) {
754 if (UpdateBundle)
755 BundleHeads.push_back(MI);
756 continue;
757 }
758 if (MI->isDebugInstr()) // DBG_VALUE may have invalid reg.
759 continue;
762 for (unsigned i = 0; i < MI->getNumOperands(); ++i) {
763 MachineOperand &MO = MI->getOperand(i);
764 if (MO.isReg()) { // DBG_VALUE may have invalid reg.
765 if (MO.isUse())
766 UseRegs.push_back(&MO);
767 else { // Def
768 if (!QII->isPredicated(*MI) && !MI->isKill()) {
769 // Assuming that predicated defs are not defs, for now.
770 // KILL instructions are no-ops
771 DefRegs.push_back(&MO);
772 }
773 }
774 } else if (MO.isRegMask()) {
775 if (!QII->isPredicated(*MI))
776 DefRegs.push_back(&MO);
777 }
778 }
779 // In case of a def. remove Reg and its sub-regs from Used list
780 // such that uses in the same MI can be marked as kill.
781 auto RemoveDef = [&](unsigned Reg, bool Implicit) -> void {
782 for (MCSubRegIterator SI(Reg, TRI, true); SI.isValid(); ++SI) {
783 Used.reset(*SI);
784 if (Implicit) {
785 // For implicit defs, check if there is an implicit use of an
786 // aliased register. If so, mark the aliased reg as used.
787 for (auto *UseOp : UseRegs)
788 if (UseOp->isImplicit() && TRI->regsOverlap(*SI, UseOp->getReg()))
789 Used.set(UseOp->getReg());
790 }
791 }
792 };
793 for (unsigned i = 0; i < DefRegs.size(); ++i) {
794 MachineOperand &MO = *DefRegs[i];
795 if (MO.isReg()) {
796 RemoveDef(MO.getReg(), MO.isImplicit());
797 } else if (MO.isRegMask()) {
798 for (unsigned R = 1, NR = TRI->getNumRegs(); R != NR; ++R)
799 if (MO.clobbersPhysReg(R))
800 RemoveDef(R, true);
801 }
802 }
803 // The order is important as we are looking from right to left.
804 for (unsigned i = UseRegs.size(); i > 0;) {
805 --i;
806 unsigned UseReg = UseRegs[i]->getReg();
807 bool Killed = true;
808 for (MCRegAliasIterator AI(UseReg, TRI, true); AI.isValid(); ++AI) {
809 if (Used[*AI])
810 Killed = false;
811 }
812 Used.set(UseReg);
813 if (Killed && !UseRegs[i]->isDebug())
814 UseRegs[i]->setIsKill(true);
815 }
816 }
817 // Recreates bundle for updating liveness.
818 for (SmallVectorImpl<MachineInstr *>::iterator MII = BundleHeads.begin();
819 MII != BundleHeads.end(); ++MII) {
820 MachineInstr *MI = *MII;
821 assert(MI && "Invalid bundle head");
822 assert(MI->isBundle() && "Expected a bundle head instruction");
823 assert(MI->getParent() == MBB && "Bundle head not in expected block");
824 MachineBasicBlock::instr_iterator BS = MI->getIterator();
826 for (++BS; BS != BE; ++BS)
827 // Remove from bundle so that BUNDLE head can be erased.
828 BS->unbundleFromPred();
829
830 BS = MI->getIterator();
831 ++BS;
832 bool memShufDisabled = QII->getBundleNoShuf(*MI);
833 MI->eraseFromParent();
834 finalizeBundle(*MBB, BS, BE);
835 MachineBasicBlock::instr_iterator BundleMII = std::prev(BS);
836 if (memShufDisabled)
837 QII->setBundleNoShuf(BundleMII);
838 }
839 return true;
840}
841
842// It deletes the live-in of the \p From MBB.
843bool HexagonLiveVariablesImpl::incrementalUpdate(MICInstIterType MIDelta,
844 MachineBasicBlock *From,
845 MachineBasicBlock *To) {
846 while (!From->livein_empty())
847 From->removeLiveIn((*From->livein_begin()).PhysReg);
848 // Handle MI use-def of From.
849 constructUseDef(From);
850 // Handle MI use-def of To.
851 constructUseDef(To);
852 // Calculate live-in of From and To
853 // Reuse this by setting all MBBs except From and To as visited.
854 updateGlobalLiveness(From, To);
855 // Update local liveness of To.
856 updateLocalLiveness(From, true);
857 updateLocalLiveness(To, true);
858
859 // Do this after the liveness update because MIDelta might not be in the
860 // MIUseDefs before liveness update (since MIDelta might be newly inserted).
861 MIUseDef_t::const_iterator MIUseDef = MIUseDefs.find(&*MIDelta);
862 if (MIUseDef == MIUseDefs.end())
863 llvm_unreachable("MIDelta not found in MIUseDefs after liveness update");
864 const BitVector &Defs = MIUseDef->second.second;
865 int Reg = Defs.find_first();
866 // Adding all the defs as live-ins. This is conservative approach but we
867 // need to add them so as to avoid dealing with callee saved registers and
868 // any unwanted errors in liveness that might arise.
869 while (Reg >= 0) {
870 From->addLiveIn(Reg);
871 Reg = Defs.find_next(Reg);
872 }
873 return true;
874}
875
876void HexagonLiveVariablesImpl::addNewMBB(MachineBasicBlock *MBB) {
877 // Resize and init.
878 constructUseDef(MBB); // This is to set up some containers for MBB.
879 gatherBlocksDF(*MBB->getParent(), &BlocksDepthFirst);
880 updateGlobalLiveness(MBB, MBB);
881}
882
883// TODO: This is a slow implementation because constructUseDef destroys
884// the MBBLiveOuts which is generated again by updateGlobalLiveness.
885void HexagonLiveVariablesImpl::addNewMI(MachineInstr *MI,
887 constructUseDef(MBB); // This is to set up some containers for MBB.
888 updateGlobalLiveness(MBB, MBB);
889}
890
891void HexagonLiveVariablesImpl::generateDistanceMap(const MachineFunction &Fn) {
892 assert(DistanceMap.empty() && "DistanceMap not empty, first clear!");
893 for (MachineFunction::const_iterator MBBI = Fn.begin(), E = Fn.end();
894 MBBI != E; ++MBBI) {
895 const MachineBasicBlock *MBB = &*MBBI;
896 unsigned MBBInsSize = 0;
898 E = MBB->instr_end();
899 MII != E; ++MII) {
900 const MachineInstr *MI = &*MII;
901 MBBInsSize += QII->getSize(*MI);
902 }
903 DistanceMap[MBB] = MBBInsSize;
904 }
905}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator MBBI
Function Alias Analysis false
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static Register UseReg(const MachineOperand &MO)
static bool isDebug()
static void UpdateBundle(MachineInstr *BundleHead)
static void gatherBlocksDF(MachineFunction &Fn, SmallVectorImpl< MachineBasicBlock * > *Blocks)
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition MD5.cpp:57
Register Reg
Register const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition PassSupport.h:56
MachineRegisterInfo & MRI
Remove Loads Into Fake Uses
#define LLVM_DEBUG(...)
Definition Debug.h:119
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:280
BitVector & reset()
Reset all bits in the bitvector.
Definition BitVector.h:410
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
Definition BitVector.h:318
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
Definition BitVector.h:356
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition BitVector.h:529
BitVector & set()
Set all bits in the bitvector.
Definition BitVector.h:367
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
Definition BitVector.h:325
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
Definition DenseMap.h:679
MachineBasicBlock::const_instr_iterator MICInstIterType
void recalculate(MachineFunction &MF)
recalculate - recalculates the liveness from scratch.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void constructUseDef(MachineBasicBlock *MBB)
Constructs use-defs of MBB by analyzing each MachineOperand.
unsigned getDistanceBetween(const MachineBasicBlock *From, const MachineBasicBlock *To, unsigned BufferPerMBB=HEXAGON_INSTR_SIZE) const
Returns the linear distance (as per layout) of MI from the Function.
bool isUsedWithin(MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg, MICInstIterType &Use, SmallPtrSet< MachineInstr *, 2 > *ExceptionsList=nullptr) const
bool incrementalUpdate(MICInstIterType MIDelta, MachineBasicBlock *From, MachineBasicBlock *To)
incrementalUpdate - update the liveness when MIDelta is moved from From to To.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool updateLocalLiveness(MachineFunction &Fn)
updateLocalLiveness - update only kill flags of operands.
const BitVector & getLiveOuts(const MachineBasicBlock *MBB) const
bool isDefLiveIn(const MachineInstr *MI, const MachineBasicBlock *MBB) const
void regenerateDistanceMap(const MachineFunction &Fn)
void addNewMBB(MachineBasicBlock *MBB)
addNewMBB - inform the LiveVariable Analysis that new MBB has been added.
bool isLiveOut(const MachineBasicBlock *MBB, unsigned Reg) const
bool isDefinedWithin(MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg, MICInstIterType &Def) const
void addNewMI(MachineInstr *MI, MachineBasicBlock *MBB)
MCRegAliasIterator enumerates all registers aliasing Reg.
MCSubRegIterator enumerates all sub-registers of Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
MCSuperRegIterator enumerates all super-registers of Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
livein_iterator livein_end() const
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
LLVM_ABI void removeLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
LiveInVector::const_iterator livein_iterator
LLVM_ABI livein_iterator livein_begin() const
SmallVectorImpl< MachineBasicBlock * >::iterator succ_iterator
reverse_instr_iterator instr_rend()
Instructions::iterator instr_iterator
Instructions::const_iterator const_instr_iterator
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Instructions::reverse_iterator reverse_instr_iterator
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
BasicBlockListType::iterator iterator
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
BasicBlockListType::const_iterator const_iterator
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsDead(bool Val=true)
void setIsKill(bool Val=true)
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI void finalizeBundle(MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
finalizeBundle - Finalize a machine instruction bundle which includes a sequence of instructions star...
@ Implicit
Not emitted register (e.g. carry, or temporary result).
@ Done
Definition Threading.h:60
char & HexagonLiveVariablesID
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
DenseMap< MachineBasicBlock *, UseDef_t > MBBUseDef_t
void initializeHexagonLiveVariablesPass(PassRegistry &)
std::pair< BitVector, BitVector > UseDef_t
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
DenseMap< const MachineInstr *, UseDef_t > MIUseDef_t
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879