1 //===- HexagonBlockRanges.cpp ---------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "HexagonBlockRanges.h"
11 #include "HexagonInstrInfo.h"
12 #include "HexagonSubtarget.h"
13 #include "llvm/ADT/BitVector.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/CodeGen/MachineBasicBlock.h"
16 #include "llvm/CodeGen/MachineFunction.h"
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "llvm/CodeGen/MachineOperand.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetRegisterInfo.h"
21 #include "llvm/MC/MCRegisterInfo.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
33 #define DEBUG_TYPE "hbr"
35 bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const {
36 // If A contains start(), or "this" contains A.start(), then overlap.
37 IndexType S = start(), E = end(), AS = A.start(), AE = A.end();
40 bool SbAE = (S < AE) || (S == AE && A.TiedEnd); // S-before-AE.
41 bool ASbE = (AS < E) || (AS == E && TiedEnd); // AS-before-E.
42 if ((AS < S && SbAE) || (S < AS && ASbE))
44 // Otherwise no overlap.
48 bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const {
49 if (start() <= A.start()) {
50 // Treat "None" in the range end as equal to the range start.
51 IndexType E = (end() != IndexType::None) ? end() : start();
52 IndexType AE = (A.end() != IndexType::None) ? A.end() : A.start();
59 void HexagonBlockRanges::IndexRange::merge(const IndexRange &A) {
60 // Allow merging adjacent ranges.
61 assert(end() == A.start() || overlaps(A));
62 IndexType AS = A.start(), AE = A.end();
63 if (AS < start() || start() == IndexType::None)
65 if (end() < AE || end() == IndexType::None) {
76 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
78 if (!is_contained(*this, R))
82 // Merge all overlapping ranges in the list, so that all that remains
83 // is a list of disjoint ranges.
84 void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
88 std::sort(begin(), end());
89 iterator Iter = begin();
91 while (Iter != end()-1) {
92 iterator Next = std::next(Iter);
93 // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
94 // This allows merging dead ranges, but is not valid for live ranges.
95 bool Merge = MergeAdjacent && (Iter->end() == Next->start());
96 if (Merge || Iter->overlaps(*Next)) {
105 // Compute a range A-B and add it to the list.
106 void HexagonBlockRanges::RangeList::addsub(const IndexRange &A,
107 const IndexRange &B) {
108 // Exclusion of non-overlapping ranges makes some checks simpler
109 // later in this function.
110 if (!A.overlaps(B)) {
116 IndexType AS = A.start(), AE = A.end();
117 IndexType BS = B.start(), BE = B.end();
119 // If AE is None, then A is included in B, since A and B overlap.
120 // The result of subtraction if empty, so just return.
121 if (AE == IndexType::None)
125 // A starts before B.
126 // AE cannot be None since A and B overlap.
127 assert(AE != IndexType::None);
128 // Add the part of A that extends on the "less" side of B.
129 add(AS, BS, A.Fixed, false);
133 // BE cannot be Exit here.
134 if (BE == IndexType::None)
135 add(BS, AE, A.Fixed, false);
137 add(BE, AE, A.Fixed, false);
141 // Subtract a given range from each element in the list.
142 void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) {
143 // Cannot assume that the list is unionized (i.e. contains only non-
144 // overlapping ranges.
146 for (iterator Next, I = begin(); I != end(); I = Next) {
148 if (Rg.overlaps(Range)) {
150 Next = this->erase(I);
158 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
160 IndexType Idx = IndexType::First;
163 if (In.isDebugValue())
165 assert(getIndex(&In) == IndexType::None && "Instruction already in map");
166 Map.insert(std::make_pair(Idx, &In));
169 Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
172 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
173 auto F = Map.find(Idx);
174 return (F != Map.end()) ? F->second : nullptr;
177 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
178 MachineInstr *MI) const {
182 return IndexType::None;
185 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex(
186 IndexType Idx) const {
187 assert (Idx != IndexType::None);
188 if (Idx == IndexType::Entry)
189 return IndexType::None;
190 if (Idx == IndexType::Exit)
193 return IndexType::Entry;
194 return unsigned(Idx)-1;
197 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex(
198 IndexType Idx) const {
199 assert (Idx != IndexType::None);
200 if (Idx == IndexType::Entry)
201 return IndexType::First;
202 if (Idx == IndexType::Exit || Idx == Last)
203 return IndexType::None;
204 return unsigned(Idx)+1;
207 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
208 MachineInstr *NewMI) {
209 for (auto &I : Map) {
210 if (I.second != OldMI)
212 if (NewMI != nullptr)
220 HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf)
221 : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()),
222 TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()),
223 Reserved(TRI.getReservedRegs(mf)) {
224 // Consider all non-allocatable registers as reserved.
225 for (const TargetRegisterClass *RC : TRI.regclasses()) {
226 if (RC->isAllocatable())
228 for (unsigned R : *RC)
233 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
234 const MachineBasicBlock &B, const MachineRegisterInfo &MRI,
235 const TargetRegisterInfo &TRI) {
239 for (auto I : B.liveins()) {
240 MCSubRegIndexIterator S(I.PhysReg, &TRI);
241 if (I.LaneMask.all() || (I.LaneMask.any() && !S.isValid())) {
242 Tmp.insert({I.PhysReg, 0});
245 for (; S.isValid(); ++S) {
246 unsigned SI = S.getSubRegIndex();
247 if ((I.LaneMask & TRI.getSubRegIndexLaneMask(SI)).any())
248 Tmp.insert({S.getSubReg(), 0});
253 if (!Reserved[R.Reg])
255 for (auto S : expandToSubRegs(R, MRI, TRI))
256 if (!Reserved[S.Reg])
262 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
263 RegisterRef R, const MachineRegisterInfo &MRI,
264 const TargetRegisterInfo &TRI) {
272 if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
273 MCSubRegIterator I(R.Reg, &TRI);
275 SRs.insert({R.Reg, 0});
276 for (; I.isValid(); ++I)
279 assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
280 auto &RC = *MRI.getRegClass(R.Reg);
281 unsigned PReg = *RC.begin();
282 MCSubRegIndexIterator I(PReg, &TRI);
284 SRs.insert({R.Reg, 0});
285 for (; I.isValid(); ++I)
286 SRs.insert({R.Reg, I.getSubRegIndex()});
291 void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
292 RegToRangeMap &LiveMap) {
293 std::map<RegisterRef,IndexType> LastDef, LastUse;
294 RegisterSet LiveOnEntry;
295 MachineBasicBlock &B = IndexMap.getBlock();
296 MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
298 for (auto R : getLiveIns(B, MRI, TRI))
299 LiveOnEntry.insert(R);
301 for (auto R : LiveOnEntry)
302 LastDef[R] = IndexType::Entry;
304 auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
305 auto LD = LastDef[R], LU = LastUse[R];
306 if (LD == IndexType::None)
307 LD = IndexType::Entry;
308 if (LU == IndexType::None)
309 LU = IndexType::Exit;
310 LiveMap[R].add(LD, LU, false, false);
311 LastUse[R] = LastDef[R] = IndexType::None;
314 RegisterSet Defs, Clobbers;
317 if (In.isDebugValue())
319 IndexType Index = IndexMap.getIndex(&In);
320 // Process uses first.
321 for (auto &Op : In.operands()) {
322 if (!Op.isReg() || !Op.isUse() || Op.isUndef())
324 RegisterRef R = { Op.getReg(), Op.getSubReg() };
325 if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
327 bool IsKill = Op.isKill();
328 for (auto S : expandToSubRegs(R, MRI, TRI)) {
334 // Process defs and clobbers.
337 for (auto &Op : In.operands()) {
338 if (!Op.isReg() || !Op.isDef() || Op.isUndef())
340 RegisterRef R = { Op.getReg(), Op.getSubReg() };
341 for (auto S : expandToSubRegs(R, MRI, TRI)) {
342 if (TargetRegisterInfo::isPhysicalRegister(S.Reg) && Reserved[S.Reg])
351 for (auto &Op : In.operands()) {
354 const uint32_t *BM = Op.getRegMask();
355 for (unsigned PR = 1, N = TRI.getNumRegs(); PR != N; ++PR) {
356 // Skip registers that have subregisters. A register is preserved
357 // iff its bit is set in the regmask, so if R1:0 was preserved, both
358 // R1 and R0 would also be present.
359 if (MCSubRegIterator(PR, &TRI, false).isValid())
363 if (BM[PR/32] & (1u << (PR%32)))
365 RegisterRef R = { PR, 0 };
370 // Defs and clobbers can overlap, e.g.
371 // dead %d0 = COPY %5, implicit-def %r0, implicit-def %r1
372 for (RegisterRef R : Defs)
375 // Update maps for defs.
376 for (RegisterRef S : Defs) {
377 // Defs should already be expanded into subregs.
378 assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) ||
379 !MCSubRegIterator(S.Reg, &TRI, false).isValid());
380 if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
384 // Update maps for clobbers.
385 for (RegisterRef S : Clobbers) {
386 // Clobbers should already be expanded into subregs.
387 assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) ||
388 !MCSubRegIterator(S.Reg, &TRI, false).isValid());
389 if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
391 // Create a single-instruction range.
392 LastDef[S] = LastUse[S] = Index;
397 // Collect live-on-exit.
398 RegisterSet LiveOnExit;
399 for (auto *SB : B.successors())
400 for (auto R : getLiveIns(*SB, MRI, TRI))
401 LiveOnExit.insert(R);
403 for (auto R : LiveOnExit)
404 LastUse[R] = IndexType::Exit;
406 // Process remaining registers.
408 for (auto &I : LastUse)
409 if (I.second != IndexType::None)
410 Left.insert(I.first);
411 for (auto &I : LastDef)
412 if (I.second != IndexType::None)
413 Left.insert(I.first);
417 // Finalize the live ranges.
418 for (auto &P : LiveMap)
422 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
423 InstrIndexMap &IndexMap) {
424 RegToRangeMap LiveMap;
425 DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
426 computeInitialLiveRanges(IndexMap, LiveMap);
427 DEBUG(dbgs() << __func__ << ": live map\n"
428 << PrintRangeMap(LiveMap, TRI) << '\n');
432 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
433 InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
434 RegToRangeMap DeadMap;
436 auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void {
437 auto F = LiveMap.find(R);
438 if (F == LiveMap.end() || F->second.empty()) {
439 DeadMap[R].add(IndexType::Entry, IndexType::Exit, false, false);
443 RangeList &RL = F->second;
444 RangeList::iterator A = RL.begin(), Z = RL.end()-1;
446 // Try to create the initial range.
447 if (A->start() != IndexType::Entry) {
448 IndexType DE = IndexMap.getPrevIndex(A->start());
449 if (DE != IndexType::Entry)
450 DeadMap[R].add(IndexType::Entry, DE, false, false);
454 // Creating a dead range that follows A. Pay attention to empty
455 // ranges (i.e. those ending with "None").
456 IndexType AE = (A->end() == IndexType::None) ? A->start() : A->end();
457 IndexType DS = IndexMap.getNextIndex(AE);
459 IndexType DE = IndexMap.getPrevIndex(A->start());
461 DeadMap[R].add(DS, DE, false, false);
464 // Try to create the final range.
465 if (Z->end() != IndexType::Exit) {
466 IndexType ZE = (Z->end() == IndexType::None) ? Z->start() : Z->end();
467 IndexType DS = IndexMap.getNextIndex(ZE);
468 if (DS < IndexType::Exit)
469 DeadMap[R].add(DS, IndexType::Exit, false, false);
473 MachineFunction &MF = *IndexMap.getBlock().getParent();
474 auto &MRI = MF.getRegInfo();
475 unsigned NumRegs = TRI.getNumRegs();
476 BitVector Visited(NumRegs);
477 for (unsigned R = 1; R < NumRegs; ++R) {
478 for (auto S : expandToSubRegs({R,0}, MRI, TRI)) {
479 if (Reserved[S.Reg] || Visited[S.Reg])
482 Visited[S.Reg] = true;
485 for (auto &P : LiveMap)
486 if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
487 addDeadRanges(P.first);
489 DEBUG(dbgs() << __func__ << ": dead map\n"
490 << PrintRangeMap(DeadMap, TRI) << '\n');
494 raw_ostream &llvm::operator<<(raw_ostream &OS,
495 HexagonBlockRanges::IndexType Idx) {
496 if (Idx == HexagonBlockRanges::IndexType::None)
498 if (Idx == HexagonBlockRanges::IndexType::Entry)
500 if (Idx == HexagonBlockRanges::IndexType::Exit)
502 return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
505 // A mapping to translate between instructions and their indices.
506 raw_ostream &llvm::operator<<(raw_ostream &OS,
507 const HexagonBlockRanges::IndexRange &IR) {
508 OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
514 raw_ostream &llvm::operator<<(raw_ostream &OS,
515 const HexagonBlockRanges::RangeList &RL) {
521 raw_ostream &llvm::operator<<(raw_ostream &OS,
522 const HexagonBlockRanges::InstrIndexMap &M) {
523 for (auto &In : M.Block) {
524 HexagonBlockRanges::IndexType Idx = M.getIndex(&In);
525 OS << Idx << (Idx == M.Last ? ". " : " ") << In;
530 raw_ostream &llvm::operator<<(raw_ostream &OS,
531 const HexagonBlockRanges::PrintRangeMap &P) {
532 for (auto &I : P.Map) {
533 const HexagonBlockRanges::RangeList &RL = I.second;
534 OS << printReg(I.first.Reg, &P.TRI, I.first.Sub) << " -> " << RL << "\n";