• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- HexagonBlockRanges.cpp -------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #define DEBUG_TYPE "hbr"
11 
12 #include "HexagonBlockRanges.h"
13 #include "HexagonInstrInfo.h"
14 #include "HexagonSubtarget.h"
15 
16 #include "llvm/ADT/BitVector.h"
17 #include "llvm/CodeGen/MachineBasicBlock.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Target/TargetRegisterInfo.h"
25 
26 #include <map>
27 
28 using namespace llvm;
29 
overlaps(const IndexRange & A) const30 bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const {
31   // If A contains start(), or "this" contains A.start(), then overlap.
32   IndexType S = start(), E = end(), AS = A.start(), AE = A.end();
33   if (AS == S)
34     return true;
35   bool SbAE = (S < AE) || (S == AE && A.TiedEnd);  // S-before-AE.
36   bool ASbE = (AS < E) || (AS == E && TiedEnd);    // AS-before-E.
37   if ((AS < S && SbAE) || (S < AS && ASbE))
38     return true;
39   // Otherwise no overlap.
40   return false;
41 }
42 
43 
contains(const IndexRange & A) const44 bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const {
45   if (start() <= A.start()) {
46     // Treat "None" in the range end as equal to the range start.
47     IndexType E = (end() != IndexType::None) ? end() : start();
48     IndexType AE = (A.end() != IndexType::None) ? A.end() : A.start();
49     if (AE <= E)
50       return true;
51   }
52   return false;
53 }
54 
55 
merge(const IndexRange & A)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)
61     setStart(AS);
62   if (end() < AE || end() == IndexType::None) {
63     setEnd(AE);
64     TiedEnd = A.TiedEnd;
65   } else {
66     if (end() == AE)
67       TiedEnd |= A.TiedEnd;
68   }
69   if (A.Fixed)
70     Fixed = true;
71 }
72 
73 
include(const RangeList & RL)74 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
75   for (auto &R : RL)
76     if (std::find(begin(), end(), R) == end())
77       push_back(R);
78 }
79 
80 
81 // Merge all overlapping ranges in the list, so that all that remains
82 // is a list of disjoint ranges.
unionize(bool MergeAdjacent)83 void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
84   if (empty())
85     return;
86 
87   std::sort(begin(), end());
88   iterator Iter = begin();
89 
90   while (Iter != end()-1) {
91     iterator Next = std::next(Iter);
92     // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
93     // This allows merging dead ranges, but is not valid for live ranges.
94     bool Merge = MergeAdjacent && (Iter->end() == Next->start());
95     if (Merge || Iter->overlaps(*Next)) {
96       Iter->merge(*Next);
97       erase(Next);
98       continue;
99     }
100     ++Iter;
101   }
102 }
103 
104 
105 // Compute a range A-B and add it to the list.
addsub(const IndexRange & A,const IndexRange & B)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)) {
111     // A - B = A.
112     add(A);
113     return;
114   }
115 
116   IndexType AS = A.start(), AE = A.end();
117   IndexType BS = B.start(), BE = B.end();
118 
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)
122     return;
123 
124   if (AS < BS) {
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);
130   }
131 
132   if (BE < AE) {
133     // BE cannot be Exit here.
134     if (BE == IndexType::None)
135       add(BS, AE, A.Fixed, false);
136     else
137       add(BE, AE, A.Fixed, false);
138   }
139 }
140 
141 
142 // Subtract a given range from each element in the list.
subtract(const IndexRange & Range)143 void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) {
144   // Cannot assume that the list is unionized (i.e. contains only non-
145   // overlapping ranges.
146   RangeList T;
147   for (iterator Next, I = begin(); I != end(); I = Next) {
148     IndexRange &Rg = *I;
149     if (Rg.overlaps(Range)) {
150       T.addsub(Rg, Range);
151       Next = this->erase(I);
152     } else {
153       Next = std::next(I);
154     }
155   }
156   include(T);
157 }
158 
159 
InstrIndexMap(MachineBasicBlock & B)160 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
161     : Block(B) {
162   IndexType Idx = IndexType::First;
163   First = Idx;
164   for (auto &In : B) {
165     if (In.isDebugValue())
166       continue;
167     assert(getIndex(&In) == IndexType::None && "Instruction already in map");
168     Map.insert(std::make_pair(Idx, &In));
169     ++Idx;
170   }
171   Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
172 }
173 
174 
getInstr(IndexType Idx) const175 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
176   auto F = Map.find(Idx);
177   return (F != Map.end()) ? F->second : 0;
178 }
179 
180 
getIndex(MachineInstr * MI) const181 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
182       MachineInstr *MI) const {
183   for (auto &I : Map)
184     if (I.second == MI)
185       return I.first;
186   return IndexType::None;
187 }
188 
189 
getPrevIndex(IndexType Idx) const190 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex(
191       IndexType Idx) const {
192   assert (Idx != IndexType::None);
193   if (Idx == IndexType::Entry)
194     return IndexType::None;
195   if (Idx == IndexType::Exit)
196     return Last;
197   if (Idx == First)
198     return IndexType::Entry;
199   return unsigned(Idx)-1;
200 }
201 
202 
getNextIndex(IndexType Idx) const203 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex(
204       IndexType Idx) const {
205   assert (Idx != IndexType::None);
206   if (Idx == IndexType::Entry)
207     return IndexType::First;
208   if (Idx == IndexType::Exit || Idx == Last)
209     return IndexType::None;
210   return unsigned(Idx)+1;
211 }
212 
213 
replaceInstr(MachineInstr * OldMI,MachineInstr * NewMI)214 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
215       MachineInstr *NewMI) {
216   for (auto &I : Map) {
217     if (I.second != OldMI)
218       continue;
219     if (NewMI != nullptr)
220       I.second = NewMI;
221     else
222       Map.erase(I.first);
223     break;
224   }
225 }
226 
227 
HexagonBlockRanges(MachineFunction & mf)228 HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf)
229   : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()),
230     TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()),
231     Reserved(TRI.getReservedRegs(mf)) {
232   // Consider all non-allocatable registers as reserved.
233   for (auto I = TRI.regclass_begin(), E = TRI.regclass_end(); I != E; ++I) {
234     auto *RC = *I;
235     if (RC->isAllocatable())
236       continue;
237     for (unsigned R : *RC)
238       Reserved[R] = true;
239   }
240 }
241 
242 
getLiveIns(const MachineBasicBlock & B)243 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
244       const MachineBasicBlock &B) {
245   RegisterSet LiveIns;
246   for (auto I : B.liveins())
247     if (!Reserved[I.PhysReg])
248       LiveIns.insert({I.PhysReg, 0});
249   return LiveIns;
250 }
251 
252 
expandToSubRegs(RegisterRef R,const MachineRegisterInfo & MRI,const TargetRegisterInfo & TRI)253 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
254       RegisterRef R, const MachineRegisterInfo &MRI,
255       const TargetRegisterInfo &TRI) {
256   RegisterSet SRs;
257 
258   if (R.Sub != 0) {
259     SRs.insert(R);
260     return SRs;
261   }
262 
263   if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
264     MCSubRegIterator I(R.Reg, &TRI);
265     if (!I.isValid())
266       SRs.insert({R.Reg, 0});
267     for (; I.isValid(); ++I)
268       SRs.insert({*I, 0});
269   } else {
270     assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
271     auto &RC = *MRI.getRegClass(R.Reg);
272     unsigned PReg = *RC.begin();
273     MCSubRegIndexIterator I(PReg, &TRI);
274     if (!I.isValid())
275       SRs.insert({R.Reg, 0});
276     for (; I.isValid(); ++I)
277       SRs.insert({R.Reg, I.getSubRegIndex()});
278   }
279   return SRs;
280 }
281 
282 
computeInitialLiveRanges(InstrIndexMap & IndexMap,RegToRangeMap & LiveMap)283 void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
284       RegToRangeMap &LiveMap) {
285   std::map<RegisterRef,IndexType> LastDef, LastUse;
286   RegisterSet LiveOnEntry;
287   MachineBasicBlock &B = IndexMap.getBlock();
288   MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
289 
290   for (auto R : getLiveIns(B))
291     for (auto S : expandToSubRegs(R, MRI, TRI))
292       LiveOnEntry.insert(S);
293 
294   for (auto R : LiveOnEntry)
295     LastDef[R] = IndexType::Entry;
296 
297   auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
298     auto LD = LastDef[R], LU = LastUse[R];
299     if (LD == IndexType::None)
300       LD = IndexType::Entry;
301     if (LU == IndexType::None)
302       LU = IndexType::Exit;
303     LiveMap[R].add(LD, LU, false, false);
304     LastUse[R] = LastDef[R] = IndexType::None;
305   };
306 
307   for (auto &In : B) {
308     if (In.isDebugValue())
309       continue;
310     IndexType Index = IndexMap.getIndex(&In);
311     // Process uses first.
312     for (auto &Op : In.operands()) {
313       if (!Op.isReg() || !Op.isUse() || Op.isUndef())
314         continue;
315       RegisterRef R = { Op.getReg(), Op.getSubReg() };
316       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
317         continue;
318       bool IsKill = Op.isKill();
319       for (auto S : expandToSubRegs(R, MRI, TRI)) {
320         LastUse[S] = Index;
321         if (IsKill)
322           closeRange(S);
323       }
324     }
325     // Process defs.
326     for (auto &Op : In.operands()) {
327       if (!Op.isReg() || !Op.isDef() || Op.isUndef())
328         continue;
329       RegisterRef R = { Op.getReg(), Op.getSubReg() };
330       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
331         continue;
332       for (auto S : expandToSubRegs(R, MRI, TRI)) {
333         if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
334           closeRange(S);
335         LastDef[S] = Index;
336       }
337     }
338   }
339 
340   // Collect live-on-exit.
341   RegisterSet LiveOnExit;
342   for (auto *SB : B.successors())
343     for (auto R : getLiveIns(*SB))
344       for (auto S : expandToSubRegs(R, MRI, TRI))
345         LiveOnExit.insert(S);
346 
347   for (auto R : LiveOnExit)
348     LastUse[R] = IndexType::Exit;
349 
350   // Process remaining registers.
351   RegisterSet Left;
352   for (auto &I : LastUse)
353     if (I.second != IndexType::None)
354       Left.insert(I.first);
355   for (auto &I : LastDef)
356     if (I.second != IndexType::None)
357       Left.insert(I.first);
358   for (auto R : Left)
359     closeRange(R);
360 
361   // Finalize the live ranges.
362   for (auto &P : LiveMap)
363     P.second.unionize();
364 }
365 
366 
computeLiveMap(InstrIndexMap & IndexMap)367 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
368       InstrIndexMap &IndexMap) {
369   RegToRangeMap LiveMap;
370   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": index map\n" << IndexMap << '\n');
371   computeInitialLiveRanges(IndexMap, LiveMap);
372   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": live map\n"
373                << PrintRangeMap(LiveMap, TRI) << '\n');
374   return LiveMap;
375 }
376 
377 
computeDeadMap(InstrIndexMap & IndexMap,RegToRangeMap & LiveMap)378 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
379       InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
380   RegToRangeMap DeadMap;
381 
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);
386       return;
387     }
388 
389     RangeList &RL = F->second;
390     RangeList::iterator A = RL.begin(), Z = RL.end()-1;
391 
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);
397     }
398 
399     while (A != Z) {
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);
404       ++A;
405       IndexType DE = IndexMap.getPrevIndex(A->start());
406       if (DS < DE)
407         DeadMap[R].add(DS, DE, false, false);
408     }
409 
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);
416     }
417   };
418 
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])
426         continue;
427       addDeadRanges(S);
428       Visited[S.Reg] = true;
429     }
430   }
431   for (auto &P : LiveMap)
432     if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
433       addDeadRanges(P.first);
434 
435   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": dead map\n"
436                << PrintRangeMap(DeadMap, TRI) << '\n');
437   return DeadMap;
438 }
439 
operator <<(raw_ostream & OS,HexagonBlockRanges::IndexType Idx)440 raw_ostream &llvm::operator<<(raw_ostream &OS,
441                               HexagonBlockRanges::IndexType Idx) {
442   if (Idx == HexagonBlockRanges::IndexType::None)
443     return OS << '-';
444   if (Idx == HexagonBlockRanges::IndexType::Entry)
445     return OS << 'n';
446   if (Idx == HexagonBlockRanges::IndexType::Exit)
447     return OS << 'x';
448   return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
449 }
450 
451 // A mapping to translate between instructions and their indices.
operator <<(raw_ostream & OS,const HexagonBlockRanges::IndexRange & IR)452 raw_ostream &llvm::operator<<(raw_ostream &OS,
453                               const HexagonBlockRanges::IndexRange &IR) {
454   OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
455   if (IR.Fixed)
456     OS << '!';
457   return OS;
458 }
459 
operator <<(raw_ostream & OS,const HexagonBlockRanges::RangeList & RL)460 raw_ostream &llvm::operator<<(raw_ostream &OS,
461                               const HexagonBlockRanges::RangeList &RL) {
462   for (auto &R : RL)
463     OS << R << " ";
464   return OS;
465 }
466 
operator <<(raw_ostream & OS,const HexagonBlockRanges::InstrIndexMap & M)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;
472   }
473   return OS;
474 }
475 
operator <<(raw_ostream & OS,const HexagonBlockRanges::PrintRangeMap & P)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";
481   }
482   return OS;
483 }
484