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 #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"
25 #include <algorithm>
26 #include <cassert>
27 #include <iterator>
28 #include <map>
29 
30 using namespace llvm;
31 
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();
35   if (AS == S)
36     return true;
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))
40     return true;
41   // Otherwise no overlap.
42   return false;
43 }
44 
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();
50     if (AE <= E)
51       return true;
52   }
53   return false;
54 }
55 
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 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
74   for (auto &R : RL)
75     if (!is_contained(*this, R))
76       push_back(R);
77 }
78 
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) {
82   if (empty())
83     return;
84 
85   std::sort(begin(), end());
86   iterator Iter = begin();
87 
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)) {
94       Iter->merge(*Next);
95       erase(Next);
96       continue;
97     }
98     ++Iter;
99   }
100 }
101 
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)) {
108     // A - B = A.
109     add(A);
110     return;
111   }
112 
113   IndexType AS = A.start(), AE = A.end();
114   IndexType BS = B.start(), BE = B.end();
115 
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)
119     return;
120 
121   if (AS < BS) {
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);
127   }
128 
129   if (BE < AE) {
130     // BE cannot be Exit here.
131     if (BE == IndexType::None)
132       add(BS, AE, A.Fixed, false);
133     else
134       add(BE, AE, A.Fixed, false);
135   }
136 }
137 
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.
142   RangeList T;
143   for (iterator Next, I = begin(); I != end(); I = Next) {
144     IndexRange &Rg = *I;
145     if (Rg.overlaps(Range)) {
146       T.addsub(Rg, Range);
147       Next = this->erase(I);
148     } else {
149       Next = std::next(I);
150     }
151   }
152   include(T);
153 }
154 
155 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
156     : Block(B) {
157   IndexType Idx = IndexType::First;
158   First = Idx;
159   for (auto &In : B) {
160     if (In.isDebugValue())
161       continue;
162     assert(getIndex(&In) == IndexType::None && "Instruction already in map");
163     Map.insert(std::make_pair(Idx, &In));
164     ++Idx;
165   }
166   Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
167 }
168 
169 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
170   auto F = Map.find(Idx);
171   return (F != Map.end()) ? F->second : nullptr;
172 }
173 
174 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
175       MachineInstr *MI) const {
176   for (auto &I : Map)
177     if (I.second == MI)
178       return I.first;
179   return IndexType::None;
180 }
181 
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)
188     return Last;
189   if (Idx == First)
190     return IndexType::Entry;
191   return unsigned(Idx)-1;
192 }
193 
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;
202 }
203 
204 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
205       MachineInstr *NewMI) {
206   for (auto &I : Map) {
207     if (I.second != OldMI)
208       continue;
209     if (NewMI != nullptr)
210       I.second = NewMI;
211     else
212       Map.erase(I.first);
213     break;
214   }
215 }
216 
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 (const TargetRegisterClass *RC : TRI.regclasses()) {
223     if (RC->isAllocatable())
224       continue;
225     for (unsigned R : *RC)
226       Reserved[R] = true;
227   }
228 }
229 
230 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
231       const MachineBasicBlock &B, const MachineRegisterInfo &MRI,
232       const TargetRegisterInfo &TRI) {
233   RegisterSet LiveIns;
234   RegisterSet Tmp;
235 
236   for (auto I : B.liveins()) {
237     MCSubRegIndexIterator S(I.PhysReg, &TRI);
238     if (I.LaneMask.all() || (I.LaneMask.any() && !S.isValid())) {
239       Tmp.insert({I.PhysReg, 0});
240       continue;
241     }
242     for (; S.isValid(); ++S) {
243       unsigned SI = S.getSubRegIndex();
244       if ((I.LaneMask & TRI.getSubRegIndexLaneMask(SI)).any())
245         Tmp.insert({S.getSubReg(), 0});
246     }
247   }
248 
249   for (auto R : Tmp) {
250     if (!Reserved[R.Reg])
251       LiveIns.insert(R);
252     for (auto S : expandToSubRegs(R, MRI, TRI))
253       if (!Reserved[S.Reg])
254         LiveIns.insert(S);
255   }
256   return LiveIns;
257 }
258 
259 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
260       RegisterRef R, const MachineRegisterInfo &MRI,
261       const TargetRegisterInfo &TRI) {
262   RegisterSet SRs;
263 
264   if (R.Sub != 0) {
265     SRs.insert(R);
266     return SRs;
267   }
268 
269   if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
270     MCSubRegIterator I(R.Reg, &TRI);
271     if (!I.isValid())
272       SRs.insert({R.Reg, 0});
273     for (; I.isValid(); ++I)
274       SRs.insert({*I, 0});
275   } else {
276     assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
277     auto &RC = *MRI.getRegClass(R.Reg);
278     unsigned PReg = *RC.begin();
279     MCSubRegIndexIterator I(PReg, &TRI);
280     if (!I.isValid())
281       SRs.insert({R.Reg, 0});
282     for (; I.isValid(); ++I)
283       SRs.insert({R.Reg, I.getSubRegIndex()});
284   }
285   return SRs;
286 }
287 
288 void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
289       RegToRangeMap &LiveMap) {
290   std::map<RegisterRef,IndexType> LastDef, LastUse;
291   RegisterSet LiveOnEntry;
292   MachineBasicBlock &B = IndexMap.getBlock();
293   MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
294 
295   for (auto R : getLiveIns(B, MRI, TRI))
296     LiveOnEntry.insert(R);
297 
298   for (auto R : LiveOnEntry)
299     LastDef[R] = IndexType::Entry;
300 
301   auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
302     auto LD = LastDef[R], LU = LastUse[R];
303     if (LD == IndexType::None)
304       LD = IndexType::Entry;
305     if (LU == IndexType::None)
306       LU = IndexType::Exit;
307     LiveMap[R].add(LD, LU, false, false);
308     LastUse[R] = LastDef[R] = IndexType::None;
309   };
310 
311   RegisterSet Defs, Clobbers;
312 
313   for (auto &In : B) {
314     if (In.isDebugValue())
315       continue;
316     IndexType Index = IndexMap.getIndex(&In);
317     // Process uses first.
318     for (auto &Op : In.operands()) {
319       if (!Op.isReg() || !Op.isUse() || Op.isUndef())
320         continue;
321       RegisterRef R = { Op.getReg(), Op.getSubReg() };
322       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
323         continue;
324       bool IsKill = Op.isKill();
325       for (auto S : expandToSubRegs(R, MRI, TRI)) {
326         LastUse[S] = Index;
327         if (IsKill)
328           closeRange(S);
329       }
330     }
331     // Process defs and clobbers.
332     Defs.clear();
333     Clobbers.clear();
334     for (auto &Op : In.operands()) {
335       if (!Op.isReg() || !Op.isDef() || Op.isUndef())
336         continue;
337       RegisterRef R = { Op.getReg(), Op.getSubReg() };
338       for (auto S : expandToSubRegs(R, MRI, TRI)) {
339         if (TargetRegisterInfo::isPhysicalRegister(S.Reg) && Reserved[S.Reg])
340           continue;
341         if (Op.isDead())
342           Clobbers.insert(S);
343         else
344           Defs.insert(S);
345       }
346     }
347 
348     for (auto &Op : In.operands()) {
349       if (!Op.isRegMask())
350         continue;
351       const uint32_t *BM = Op.getRegMask();
352       for (unsigned PR = 1, N = TRI.getNumRegs(); PR != N; ++PR) {
353         // Skip registers that have subregisters. A register is preserved
354         // iff its bit is set in the regmask, so if R1:0 was preserved, both
355         // R1 and R0 would also be present.
356         if (MCSubRegIterator(PR, &TRI, false).isValid())
357           continue;
358         if (Reserved[PR])
359           continue;
360         if (BM[PR/32] & (1u << (PR%32)))
361           continue;
362         RegisterRef R = { PR, 0 };
363         if (!Defs.count(R))
364           Clobbers.insert(R);
365       }
366     }
367     // Defs and clobbers can overlap, e.g.
368     // %D0<def,dead> = COPY %vreg5, %R0<imp-def>, %R1<imp-def>
369     for (RegisterRef R : Defs)
370       Clobbers.erase(R);
371 
372     // Update maps for defs.
373     for (RegisterRef S : Defs) {
374       // Defs should already be expanded into subregs.
375       assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) ||
376              !MCSubRegIterator(S.Reg, &TRI, false).isValid());
377       if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
378         closeRange(S);
379       LastDef[S] = Index;
380     }
381     // Update maps for clobbers.
382     for (RegisterRef S : Clobbers) {
383       // Clobbers should already be expanded into subregs.
384       assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) ||
385              !MCSubRegIterator(S.Reg, &TRI, false).isValid());
386       if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
387         closeRange(S);
388       // Create a single-instruction range.
389       LastDef[S] = LastUse[S] = Index;
390       closeRange(S);
391     }
392   }
393 
394   // Collect live-on-exit.
395   RegisterSet LiveOnExit;
396   for (auto *SB : B.successors())
397     for (auto R : getLiveIns(*SB, MRI, TRI))
398       LiveOnExit.insert(R);
399 
400   for (auto R : LiveOnExit)
401     LastUse[R] = IndexType::Exit;
402 
403   // Process remaining registers.
404   RegisterSet Left;
405   for (auto &I : LastUse)
406     if (I.second != IndexType::None)
407       Left.insert(I.first);
408   for (auto &I : LastDef)
409     if (I.second != IndexType::None)
410       Left.insert(I.first);
411   for (auto R : Left)
412     closeRange(R);
413 
414   // Finalize the live ranges.
415   for (auto &P : LiveMap)
416     P.second.unionize();
417 }
418 
419 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
420       InstrIndexMap &IndexMap) {
421   RegToRangeMap LiveMap;
422   DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
423   computeInitialLiveRanges(IndexMap, LiveMap);
424   DEBUG(dbgs() << __func__ << ": live map\n"
425                << PrintRangeMap(LiveMap, TRI) << '\n');
426   return LiveMap;
427 }
428 
429 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
430       InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
431   RegToRangeMap DeadMap;
432 
433   auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void {
434     auto F = LiveMap.find(R);
435     if (F == LiveMap.end() || F->second.empty()) {
436       DeadMap[R].add(IndexType::Entry, IndexType::Exit, false, false);
437       return;
438     }
439 
440     RangeList &RL = F->second;
441     RangeList::iterator A = RL.begin(), Z = RL.end()-1;
442 
443     // Try to create the initial range.
444     if (A->start() != IndexType::Entry) {
445       IndexType DE = IndexMap.getPrevIndex(A->start());
446       if (DE != IndexType::Entry)
447         DeadMap[R].add(IndexType::Entry, DE, false, false);
448     }
449 
450     while (A != Z) {
451       // Creating a dead range that follows A.  Pay attention to empty
452       // ranges (i.e. those ending with "None").
453       IndexType AE = (A->end() == IndexType::None) ? A->start() : A->end();
454       IndexType DS = IndexMap.getNextIndex(AE);
455       ++A;
456       IndexType DE = IndexMap.getPrevIndex(A->start());
457       if (DS < DE)
458         DeadMap[R].add(DS, DE, false, false);
459     }
460 
461     // Try to create the final range.
462     if (Z->end() != IndexType::Exit) {
463       IndexType ZE = (Z->end() == IndexType::None) ? Z->start() : Z->end();
464       IndexType DS = IndexMap.getNextIndex(ZE);
465       if (DS < IndexType::Exit)
466         DeadMap[R].add(DS, IndexType::Exit, false, false);
467     }
468   };
469 
470   MachineFunction &MF = *IndexMap.getBlock().getParent();
471   auto &MRI = MF.getRegInfo();
472   unsigned NumRegs = TRI.getNumRegs();
473   BitVector Visited(NumRegs);
474   for (unsigned R = 1; R < NumRegs; ++R) {
475     for (auto S : expandToSubRegs({R,0}, MRI, TRI)) {
476       if (Reserved[S.Reg] || Visited[S.Reg])
477         continue;
478       addDeadRanges(S);
479       Visited[S.Reg] = true;
480     }
481   }
482   for (auto &P : LiveMap)
483     if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
484       addDeadRanges(P.first);
485 
486   DEBUG(dbgs() << __func__ << ": dead map\n"
487                << PrintRangeMap(DeadMap, TRI) << '\n');
488   return DeadMap;
489 }
490 
491 raw_ostream &llvm::operator<<(raw_ostream &OS,
492                               HexagonBlockRanges::IndexType Idx) {
493   if (Idx == HexagonBlockRanges::IndexType::None)
494     return OS << '-';
495   if (Idx == HexagonBlockRanges::IndexType::Entry)
496     return OS << 'n';
497   if (Idx == HexagonBlockRanges::IndexType::Exit)
498     return OS << 'x';
499   return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
500 }
501 
502 // A mapping to translate between instructions and their indices.
503 raw_ostream &llvm::operator<<(raw_ostream &OS,
504                               const HexagonBlockRanges::IndexRange &IR) {
505   OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
506   if (IR.Fixed)
507     OS << '!';
508   return OS;
509 }
510 
511 raw_ostream &llvm::operator<<(raw_ostream &OS,
512                               const HexagonBlockRanges::RangeList &RL) {
513   for (auto &R : RL)
514     OS << R << " ";
515   return OS;
516 }
517 
518 raw_ostream &llvm::operator<<(raw_ostream &OS,
519                               const HexagonBlockRanges::InstrIndexMap &M) {
520   for (auto &In : M.Block) {
521     HexagonBlockRanges::IndexType Idx = M.getIndex(&In);
522     OS << Idx << (Idx == M.Last ? ". " : "  ") << In;
523   }
524   return OS;
525 }
526 
527 raw_ostream &llvm::operator<<(raw_ostream &OS,
528                               const HexagonBlockRanges::PrintRangeMap &P) {
529   for (auto &I : P.Map) {
530     const HexagonBlockRanges::RangeList &RL = I.second;
531     OS << PrintReg(I.first.Reg, &P.TRI, I.first.Sub) << " -> " << RL << "\n";
532   }
533   return OS;
534 }
535