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 #define DEBUG_TYPE "hbr"
12 #include "HexagonBlockRanges.h"
13 #include "HexagonInstrInfo.h"
14 #include "HexagonSubtarget.h"
15 #include "llvm/ADT/BitVector.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/CodeGen/MachineBasicBlock.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "llvm/CodeGen/MachineInstr.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/MC/MCRegisterInfo.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Target/TargetRegisterInfo.h"
32 bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const {
33 // If A contains start(), or "this" contains A.start(), then overlap.
34 IndexType S = start(), E = end(), AS = A.start(), AE = A.end();
37 bool SbAE = (S < AE) || (S == AE && A.TiedEnd); // S-before-AE.
38 bool ASbE = (AS < E) || (AS == E && TiedEnd); // AS-before-E.
39 if ((AS < S && SbAE) || (S < AS && ASbE))
41 // Otherwise no overlap.
45 bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const {
46 if (start() <= A.start()) {
47 // Treat "None" in the range end as equal to the range start.
48 IndexType E = (end() != IndexType::None) ? end() : start();
49 IndexType AE = (A.end() != IndexType::None) ? A.end() : A.start();
56 void HexagonBlockRanges::IndexRange::merge(const IndexRange &A) {
57 // Allow merging adjacent ranges.
58 assert(end() == A.start() || overlaps(A));
59 IndexType AS = A.start(), AE = A.end();
60 if (AS < start() || start() == IndexType::None)
62 if (end() < AE || end() == IndexType::None) {
73 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
75 if (!is_contained(*this, R))
79 // Merge all overlapping ranges in the list, so that all that remains
80 // is a list of disjoint ranges.
81 void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
85 std::sort(begin(), end());
86 iterator Iter = begin();
88 while (Iter != end()-1) {
89 iterator Next = std::next(Iter);
90 // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
91 // This allows merging dead ranges, but is not valid for live ranges.
92 bool Merge = MergeAdjacent && (Iter->end() == Next->start());
93 if (Merge || Iter->overlaps(*Next)) {
102 // Compute a range A-B and add it to the list.
103 void HexagonBlockRanges::RangeList::addsub(const IndexRange &A,
104 const IndexRange &B) {
105 // Exclusion of non-overlapping ranges makes some checks simpler
106 // later in this function.
107 if (!A.overlaps(B)) {
113 IndexType AS = A.start(), AE = A.end();
114 IndexType BS = B.start(), BE = B.end();
116 // If AE is None, then A is included in B, since A and B overlap.
117 // The result of subtraction if empty, so just return.
118 if (AE == IndexType::None)
122 // A starts before B.
123 // AE cannot be None since A and B overlap.
124 assert(AE != IndexType::None);
125 // Add the part of A that extends on the "less" side of B.
126 add(AS, BS, A.Fixed, false);
130 // BE cannot be Exit here.
131 if (BE == IndexType::None)
132 add(BS, AE, A.Fixed, false);
134 add(BE, AE, A.Fixed, false);
138 // Subtract a given range from each element in the list.
139 void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) {
140 // Cannot assume that the list is unionized (i.e. contains only non-
141 // overlapping ranges.
143 for (iterator Next, I = begin(); I != end(); I = Next) {
145 if (Rg.overlaps(Range)) {
147 Next = this->erase(I);
155 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
157 IndexType Idx = IndexType::First;
160 if (In.isDebugValue())
162 assert(getIndex(&In) == IndexType::None && "Instruction already in map");
163 Map.insert(std::make_pair(Idx, &In));
166 Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
169 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
170 auto F = Map.find(Idx);
171 return (F != Map.end()) ? F->second : nullptr;
174 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
175 MachineInstr *MI) const {
179 return IndexType::None;
182 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex(
183 IndexType Idx) const {
184 assert (Idx != IndexType::None);
185 if (Idx == IndexType::Entry)
186 return IndexType::None;
187 if (Idx == IndexType::Exit)
190 return IndexType::Entry;
191 return unsigned(Idx)-1;
194 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex(
195 IndexType Idx) const {
196 assert (Idx != IndexType::None);
197 if (Idx == IndexType::Entry)
198 return IndexType::First;
199 if (Idx == IndexType::Exit || Idx == Last)
200 return IndexType::None;
201 return unsigned(Idx)+1;
204 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
205 MachineInstr *NewMI) {
206 for (auto &I : Map) {
207 if (I.second != OldMI)
209 if (NewMI != nullptr)
217 HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf)
218 : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()),
219 TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()),
220 Reserved(TRI.getReservedRegs(mf)) {
221 // Consider all non-allocatable registers as reserved.
222 for (auto I = TRI.regclass_begin(), E = TRI.regclass_end(); I != E; ++I) {
224 if (RC->isAllocatable())
226 for (unsigned R : *RC)
231 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
232 const MachineBasicBlock &B, const MachineRegisterInfo &MRI,
233 const TargetRegisterInfo &TRI) {
236 for (auto I : B.liveins()) {
237 if (I.LaneMask.all()) {
238 Tmp.insert({I.PhysReg,0});
241 for (MCSubRegIndexIterator S(I.PhysReg, &TRI); S.isValid(); ++S) {
242 LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex());
243 if ((M & I.LaneMask).any())
244 Tmp.insert({S.getSubReg(), 0});
249 if (!Reserved[R.Reg])
251 for (auto S : expandToSubRegs(R, MRI, TRI))
252 if (!Reserved[S.Reg])
258 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
259 RegisterRef R, const MachineRegisterInfo &MRI,
260 const TargetRegisterInfo &TRI) {
268 if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
269 MCSubRegIterator I(R.Reg, &TRI);
271 SRs.insert({R.Reg, 0});
272 for (; I.isValid(); ++I)
275 assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
276 auto &RC = *MRI.getRegClass(R.Reg);
277 unsigned PReg = *RC.begin();
278 MCSubRegIndexIterator I(PReg, &TRI);
280 SRs.insert({R.Reg, 0});
281 for (; I.isValid(); ++I)
282 SRs.insert({R.Reg, I.getSubRegIndex()});
287 void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
288 RegToRangeMap &LiveMap) {
289 std::map<RegisterRef,IndexType> LastDef, LastUse;
290 RegisterSet LiveOnEntry;
291 MachineBasicBlock &B = IndexMap.getBlock();
292 MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
294 for (auto R : getLiveIns(B, MRI, TRI))
295 LiveOnEntry.insert(R);
297 for (auto R : LiveOnEntry)
298 LastDef[R] = IndexType::Entry;
300 auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
301 auto LD = LastDef[R], LU = LastUse[R];
302 if (LD == IndexType::None)
303 LD = IndexType::Entry;
304 if (LU == IndexType::None)
305 LU = IndexType::Exit;
306 LiveMap[R].add(LD, LU, false, false);
307 LastUse[R] = LastDef[R] = IndexType::None;
311 if (In.isDebugValue())
313 IndexType Index = IndexMap.getIndex(&In);
314 // Process uses first.
315 for (auto &Op : In.operands()) {
316 if (!Op.isReg() || !Op.isUse() || Op.isUndef())
318 RegisterRef R = { Op.getReg(), Op.getSubReg() };
319 if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
321 bool IsKill = Op.isKill();
322 for (auto S : expandToSubRegs(R, MRI, TRI)) {
329 for (auto &Op : In.operands()) {
330 if (!Op.isReg() || !Op.isDef() || Op.isUndef())
332 RegisterRef R = { Op.getReg(), Op.getSubReg() };
333 if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
335 for (auto S : expandToSubRegs(R, MRI, TRI)) {
336 if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
343 // Collect live-on-exit.
344 RegisterSet LiveOnExit;
345 for (auto *SB : B.successors())
346 for (auto R : getLiveIns(*SB, MRI, TRI))
347 LiveOnExit.insert(R);
349 for (auto R : LiveOnExit)
350 LastUse[R] = IndexType::Exit;
352 // Process remaining registers.
354 for (auto &I : LastUse)
355 if (I.second != IndexType::None)
356 Left.insert(I.first);
357 for (auto &I : LastDef)
358 if (I.second != IndexType::None)
359 Left.insert(I.first);
363 // Finalize the live ranges.
364 for (auto &P : LiveMap)
368 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
369 InstrIndexMap &IndexMap) {
370 RegToRangeMap LiveMap;
371 DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
372 computeInitialLiveRanges(IndexMap, LiveMap);
373 DEBUG(dbgs() << __func__ << ": live map\n"
374 << PrintRangeMap(LiveMap, TRI) << '\n');
378 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
379 InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
380 RegToRangeMap DeadMap;
382 auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void {
383 auto F = LiveMap.find(R);
384 if (F == LiveMap.end() || F->second.empty()) {
385 DeadMap[R].add(IndexType::Entry, IndexType::Exit, false, false);
389 RangeList &RL = F->second;
390 RangeList::iterator A = RL.begin(), Z = RL.end()-1;
392 // Try to create the initial range.
393 if (A->start() != IndexType::Entry) {
394 IndexType DE = IndexMap.getPrevIndex(A->start());
395 if (DE != IndexType::Entry)
396 DeadMap[R].add(IndexType::Entry, DE, false, false);
400 // Creating a dead range that follows A. Pay attention to empty
401 // ranges (i.e. those ending with "None").
402 IndexType AE = (A->end() == IndexType::None) ? A->start() : A->end();
403 IndexType DS = IndexMap.getNextIndex(AE);
405 IndexType DE = IndexMap.getPrevIndex(A->start());
407 DeadMap[R].add(DS, DE, false, false);
410 // Try to create the final range.
411 if (Z->end() != IndexType::Exit) {
412 IndexType ZE = (Z->end() == IndexType::None) ? Z->start() : Z->end();
413 IndexType DS = IndexMap.getNextIndex(ZE);
414 if (DS < IndexType::Exit)
415 DeadMap[R].add(DS, IndexType::Exit, false, false);
419 MachineFunction &MF = *IndexMap.getBlock().getParent();
420 auto &MRI = MF.getRegInfo();
421 unsigned NumRegs = TRI.getNumRegs();
422 BitVector Visited(NumRegs);
423 for (unsigned R = 1; R < NumRegs; ++R) {
424 for (auto S : expandToSubRegs({R,0}, MRI, TRI)) {
425 if (Reserved[S.Reg] || Visited[S.Reg])
428 Visited[S.Reg] = true;
431 for (auto &P : LiveMap)
432 if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
433 addDeadRanges(P.first);
435 DEBUG(dbgs() << __func__ << ": dead map\n"
436 << PrintRangeMap(DeadMap, TRI) << '\n');
440 raw_ostream &llvm::operator<<(raw_ostream &OS,
441 HexagonBlockRanges::IndexType Idx) {
442 if (Idx == HexagonBlockRanges::IndexType::None)
444 if (Idx == HexagonBlockRanges::IndexType::Entry)
446 if (Idx == HexagonBlockRanges::IndexType::Exit)
448 return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
451 // A mapping to translate between instructions and their indices.
452 raw_ostream &llvm::operator<<(raw_ostream &OS,
453 const HexagonBlockRanges::IndexRange &IR) {
454 OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
460 raw_ostream &llvm::operator<<(raw_ostream &OS,
461 const HexagonBlockRanges::RangeList &RL) {
467 raw_ostream &llvm::operator<<(raw_ostream &OS,
468 const HexagonBlockRanges::InstrIndexMap &M) {
469 for (auto &In : M.Block) {
470 HexagonBlockRanges::IndexType Idx = M.getIndex(&In);
471 OS << Idx << (Idx == M.Last ? ". " : " ") << In;
476 raw_ostream &llvm::operator<<(raw_ostream &OS,
477 const HexagonBlockRanges::PrintRangeMap &P) {
478 for (auto &I : P.Map) {
479 const HexagonBlockRanges::RangeList &RL = I.second;
480 OS << PrintReg(I.first.Reg, &P.TRI, I.first.Sub) << " -> " << RL << "\n";