LLVM  6.0.0svn
HexagonBlockRanges.cpp
Go to the documentation of this file.
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"
21 #include "llvm/MC/MCRegisterInfo.h"
22 #include "llvm/Support/Debug.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 
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 
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 
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 
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  std::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.
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 
159  : Block(B) {
161  First = Idx;
162  for (auto &In : B) {
163  if (In.isDebugValue())
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 
173  auto F = Map.find(Idx);
174  return (F != Map.end()) ? F->second : nullptr;
175 }
176 
178  MachineInstr *MI) const {
179  for (auto &I : Map)
180  if (I.second == MI)
181  return I.first;
182  return IndexType::None;
183 }
184 
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 
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 
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 
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 
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 
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 {
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();
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)
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.isDebugValue())
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  // %D0<def,dead> = COPY %vreg5, %R0<imp-def>, %R1<imp-def>
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.
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.
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.
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 
423  InstrIndexMap &IndexMap) {
424  RegToRangeMap LiveMap;
425  DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
426  computeInitialLiveRanges(IndexMap, LiveMap);
427  DEBUG(dbgs() << __func__ << ": live map\n"
428  << PrintRangeMap(LiveMap, TRI) << '\n');
429  return LiveMap;
430 }
431 
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)
487  addDeadRanges(P.first);
488 
489  DEBUG(dbgs() << __func__ << ": dead map\n"
490  << PrintRangeMap(DeadMap, TRI) << '\n');
491  return DeadMap;
492 }
493 
497  return OS << '-';
499  return OS << 'n';
501  return OS << 'x';
503 }
504 
505 // A mapping to translate between instructions and their indices.
508  OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
509  if (IR.Fixed)
510  OS << '!';
511  return OS;
512 }
513 
515  const HexagonBlockRanges::RangeList &RL) {
516  for (auto &R : RL)
517  OS << R << " ";
518  return OS;
519 }
520 
523  for (auto &In : M.Block) {
525  OS << Idx << (Idx == M.Last ? ". " : " ") << In;
526  }
527  return OS;
528 }
529 
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 }
MachineInstr * getInstr(IndexType Idx) const
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:235
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator begin() const
begin/end - Return all of the registers in this class.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
static RegisterSet expandToSubRegs(RegisterRef R, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI)
F(f)
std::set< RegisterRef > RegisterSet
std::map< RegisterRef, RangeList > RegToRangeMap
const HexagonInstrInfo * TII
bool overlaps(const IndexRange &A) const
iterator_range< regclass_iterator > regclasses() const
zlib-gnu style compression
#define T
unsigned getSubRegIndex() const
Returns sub-register index of the current sub-register.
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
IndexType getNextIndex(IndexType Idx) const
#define P(N)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
R600 Clause Merge
const AMDGPUAS & AS
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
IndexType getIndex(MachineInstr *MI) const
void subtract(const IndexRange &Range)
bool isValid() const
Returns true if this iterator is not yet at the end.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx. ...
IndexType getPrevIndex(IndexType Idx) const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
HexagonBlockRanges(MachineFunction &MF)
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:59
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap)
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap)
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
iterator_range< livein_iterator > liveins() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void unionize(bool MergeAdjacent=false)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI)
bool contains(const IndexRange &A) const
Statically lint checks LLVM IR
Definition: Lint.cpp:193
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:867