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
28using namespace llvm;
29
30bool 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
44bool 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
56void 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
74void 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.
83void 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.
106void 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.
143void 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
160HexagonBlockRanges::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
175MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
176  auto F = Map.find(Idx);
177  return (F != Map.end()) ? F->second : 0;
178}
179
180
181HexagonBlockRanges::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
190HexagonBlockRanges::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
203HexagonBlockRanges::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
214void 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
228HexagonBlockRanges::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
243HexagonBlockRanges::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
253HexagonBlockRanges::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
283void 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
367HexagonBlockRanges::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
378HexagonBlockRanges::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
440raw_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.
452raw_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
460raw_ostream &llvm::operator<<(raw_ostream &OS,
461                              const HexagonBlockRanges::RangeList &RL) {
462  for (auto &R : RL)
463    OS << R << " ";
464  return OS;
465}
466
467raw_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
476raw_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