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 #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"
24 #include <algorithm>
25 #include <cassert>
26 #include <cstdint>
27 #include <iterator>
28 #include <map>
29 #include <utility>
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "hbr"
34 
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();
38   if (AS == S)
39     return true;
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))
43     return true;
44   // Otherwise no overlap.
45   return false;
46 }
47 
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();
53     if (AE <= E)
54       return true;
55   }
56   return false;
57 }
58 
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)
64     setStart(AS);
65   if (end() < AE || end() == IndexType::None) {
66     setEnd(AE);
67     TiedEnd = A.TiedEnd;
68   } else {
69     if (end() == AE)
70       TiedEnd |= A.TiedEnd;
71   }
72   if (A.Fixed)
73     Fixed = true;
74 }
75 
76 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
77   for (auto &R : RL)
78     if (!is_contained(*this, R))
79       push_back(R);
80 }
81 
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) {
85   if (empty())
86     return;
87 
88   llvm::sort(begin(), end());
89   iterator Iter = begin();
90 
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)) {
97       Iter->merge(*Next);
98       erase(Next);
99       continue;
100     }
101     ++Iter;
102   }
103 }
104 
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)) {
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 // 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.
145   RangeList T;
146   for (iterator Next, I = begin(); I != end(); I = Next) {
147     IndexRange &Rg = *I;
148     if (Rg.overlaps(Range)) {
149       T.addsub(Rg, Range);
150       Next = this->erase(I);
151     } else {
152       Next = std::next(I);
153     }
154   }
155   include(T);
156 }
157 
158 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
159     : Block(B) {
160   IndexType Idx = IndexType::First;
161   First = Idx;
162   for (auto &In : B) {
163     if (In.isDebugInstr())
164       continue;
165     assert(getIndex(&In) == IndexType::None && "Instruction already in map");
166     Map.insert(std::make_pair(Idx, &In));
167     ++Idx;
168   }
169   Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
170 }
171 
172 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
173   auto F = Map.find(Idx);
174   return (F != Map.end()) ? F->second : nullptr;
175 }
176 
177 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
178       MachineInstr *MI) const {
179   for (auto &I : Map)
180     if (I.second == MI)
181       return I.first;
182   return IndexType::None;
183 }
184 
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)
191     return Last;
192   if (Idx == First)
193     return IndexType::Entry;
194   return unsigned(Idx)-1;
195 }
196 
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;
205 }
206 
207 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
208       MachineInstr *NewMI) {
209   for (auto &I : Map) {
210     if (I.second != OldMI)
211       continue;
212     if (NewMI != nullptr)
213       I.second = NewMI;
214     else
215       Map.erase(I.first);
216     break;
217   }
218 }
219 
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())
227       continue;
228     for (unsigned R : *RC)
229       Reserved[R] = true;
230   }
231 }
232 
233 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
234       const MachineBasicBlock &B, const MachineRegisterInfo &MRI,
235       const TargetRegisterInfo &TRI) {
236   RegisterSet LiveIns;
237   RegisterSet Tmp;
238 
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});
243       continue;
244     }
245     for (; S.isValid(); ++S) {
246       unsigned SI = S.getSubRegIndex();
247       if ((I.LaneMask & TRI.getSubRegIndexLaneMask(SI)).any())
248         Tmp.insert({S.getSubReg(), 0});
249     }
250   }
251 
252   for (auto R : Tmp) {
253     if (!Reserved[R.Reg])
254       LiveIns.insert(R);
255     for (auto S : expandToSubRegs(R, MRI, TRI))
256       if (!Reserved[S.Reg])
257         LiveIns.insert(S);
258   }
259   return LiveIns;
260 }
261 
262 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
263       RegisterRef R, const MachineRegisterInfo &MRI,
264       const TargetRegisterInfo &TRI) {
265   RegisterSet SRs;
266 
267   if (R.Sub != 0) {
268     SRs.insert(R);
269     return SRs;
270   }
271 
272   if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
273     MCSubRegIterator I(R.Reg, &TRI);
274     if (!I.isValid())
275       SRs.insert({R.Reg, 0});
276     for (; I.isValid(); ++I)
277       SRs.insert({*I, 0});
278   } else {
279     assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
280     auto &RC = *MRI.getRegClass(R.Reg);
281     unsigned PReg = *RC.begin();
282     MCSubRegIndexIterator I(PReg, &TRI);
283     if (!I.isValid())
284       SRs.insert({R.Reg, 0});
285     for (; I.isValid(); ++I)
286       SRs.insert({R.Reg, I.getSubRegIndex()});
287   }
288   return SRs;
289 }
290 
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();
297 
298   for (auto R : getLiveIns(B, MRI, TRI))
299     LiveOnEntry.insert(R);
300 
301   for (auto R : LiveOnEntry)
302     LastDef[R] = IndexType::Entry;
303 
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;
312   };
313 
314   RegisterSet Defs, Clobbers;
315 
316   for (auto &In : B) {
317     if (In.isDebugInstr())
318       continue;
319     IndexType Index = IndexMap.getIndex(&In);
320     // Process uses first.
321     for (auto &Op : In.operands()) {
322       if (!Op.isReg() || !Op.isUse() || Op.isUndef())
323         continue;
324       RegisterRef R = { Op.getReg(), Op.getSubReg() };
325       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
326         continue;
327       bool IsKill = Op.isKill();
328       for (auto S : expandToSubRegs(R, MRI, TRI)) {
329         LastUse[S] = Index;
330         if (IsKill)
331           closeRange(S);
332       }
333     }
334     // Process defs and clobbers.
335     Defs.clear();
336     Clobbers.clear();
337     for (auto &Op : In.operands()) {
338       if (!Op.isReg() || !Op.isDef() || Op.isUndef())
339         continue;
340       RegisterRef R = { Op.getReg(), Op.getSubReg() };
341       for (auto S : expandToSubRegs(R, MRI, TRI)) {
342         if (TargetRegisterInfo::isPhysicalRegister(S.Reg) && Reserved[S.Reg])
343           continue;
344         if (Op.isDead())
345           Clobbers.insert(S);
346         else
347           Defs.insert(S);
348       }
349     }
350 
351     for (auto &Op : In.operands()) {
352       if (!Op.isRegMask())
353         continue;
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())
360           continue;
361         if (Reserved[PR])
362           continue;
363         if (BM[PR/32] & (1u << (PR%32)))
364           continue;
365         RegisterRef R = { PR, 0 };
366         if (!Defs.count(R))
367           Clobbers.insert(R);
368       }
369     }
370     // Defs and clobbers can overlap, e.g.
371     // dead %d0 = COPY %5, implicit-def %r0, implicit-def %r1
372     for (RegisterRef R : Defs)
373       Clobbers.erase(R);
374 
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)
381         closeRange(S);
382       LastDef[S] = Index;
383     }
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)
390         closeRange(S);
391       // Create a single-instruction range.
392       LastDef[S] = LastUse[S] = Index;
393       closeRange(S);
394     }
395   }
396 
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);
402 
403   for (auto R : LiveOnExit)
404     LastUse[R] = IndexType::Exit;
405 
406   // Process remaining registers.
407   RegisterSet Left;
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);
414   for (auto R : Left)
415     closeRange(R);
416 
417   // Finalize the live ranges.
418   for (auto &P : LiveMap)
419     P.second.unionize();
420 }
421 
422 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
423       InstrIndexMap &IndexMap) {
424   RegToRangeMap LiveMap;
425   LLVM_DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
426   computeInitialLiveRanges(IndexMap, LiveMap);
427   LLVM_DEBUG(dbgs() << __func__ << ": live map\n"
428                     << PrintRangeMap(LiveMap, TRI) << '\n');
429   return LiveMap;
430 }
431 
432 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
433       InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
434   RegToRangeMap DeadMap;
435 
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);
440       return;
441     }
442 
443     RangeList &RL = F->second;
444     RangeList::iterator A = RL.begin(), Z = RL.end()-1;
445 
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);
451     }
452 
453     while (A != Z) {
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);
458       ++A;
459       IndexType DE = IndexMap.getPrevIndex(A->start());
460       if (DS < DE)
461         DeadMap[R].add(DS, DE, false, false);
462     }
463 
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);
470     }
471   };
472 
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])
480         continue;
481       addDeadRanges(S);
482       Visited[S.Reg] = true;
483     }
484   }
485   for (auto &P : LiveMap)
486     if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
487       addDeadRanges(P.first);
488 
489   LLVM_DEBUG(dbgs() << __func__ << ": dead map\n"
490                     << PrintRangeMap(DeadMap, TRI) << '\n');
491   return DeadMap;
492 }
493 
494 raw_ostream &llvm::operator<<(raw_ostream &OS,
495                               HexagonBlockRanges::IndexType Idx) {
496   if (Idx == HexagonBlockRanges::IndexType::None)
497     return OS << '-';
498   if (Idx == HexagonBlockRanges::IndexType::Entry)
499     return OS << 'n';
500   if (Idx == HexagonBlockRanges::IndexType::Exit)
501     return OS << 'x';
502   return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
503 }
504 
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 ? '}' : ']');
509   if (IR.Fixed)
510     OS << '!';
511   return OS;
512 }
513 
514 raw_ostream &llvm::operator<<(raw_ostream &OS,
515                               const HexagonBlockRanges::RangeList &RL) {
516   for (auto &R : RL)
517     OS << R << " ";
518   return OS;
519 }
520 
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;
526   }
527   return OS;
528 }
529 
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";
535   }
536   return OS;
537 }
538