• Home
  • History
  • Annotate
  • 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