LLVM  6.0.0svn
RDFLiveness.cpp
Go to the documentation of this file.
1 //===- RDFLiveness.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 // Computation of the liveness information from the data-flow graph.
11 //
12 // The main functionality of this code is to compute block live-in
13 // information. With the live-in information in place, the placement
14 // of kill flags can also be recalculated.
15 //
16 // The block live-in calculation is based on the ideas from the following
17 // publication:
18 //
19 // Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin.
20 // "Efficient Liveness Computation Using Merge Sets and DJ-Graphs."
21 // ACM Transactions on Architecture and Code Optimization, Association for
22 // Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance
23 // and Embedded Architectures and Compilers", 8 (4),
24 // <10.1145/2086696.2086706>. <hal-00647369>
25 //
26 #include "RDFLiveness.h"
27 #include "RDFGraph.h"
28 #include "RDFRegisters.h"
29 #include "llvm/ADT/BitVector.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SetVector.h"
38 #include "llvm/MC/LaneBitmask.h"
39 #include "llvm/MC/MCRegisterInfo.h"
41 #include "llvm/Support/Debug.h"
44 #include <algorithm>
45 #include <cassert>
46 #include <cstdint>
47 #include <iterator>
48 #include <map>
49 #include <utility>
50 #include <vector>
51 
52 using namespace llvm;
53 using namespace rdf;
54 
55 static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25),
56  cl::Hidden, cl::desc("Maximum recursion level"));
57 
58 namespace llvm {
59 namespace rdf {
60 
61  template<>
62  raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) {
63  OS << '{';
64  for (auto &I : P.Obj) {
65  OS << ' ' << printReg(I.first, &P.G.getTRI()) << '{';
66  for (auto J = I.second.begin(), E = I.second.end(); J != E; ) {
67  OS << Print<NodeId>(J->first, P.G) << PrintLaneMaskOpt(J->second);
68  if (++J != E)
69  OS << ',';
70  }
71  OS << '}';
72  }
73  OS << " }";
74  return OS;
75  }
76 
77 } // end namespace rdf
78 } // end namespace llvm
79 
80 // The order in the returned sequence is the order of reaching defs in the
81 // upward traversal: the first def is the closest to the given reference RefA,
82 // the next one is further up, and so on.
83 // The list ends at a reaching phi def, or when the reference from RefA is
84 // covered by the defs in the list (see FullChain).
85 // This function provides two modes of operation:
86 // (1) Returning the sequence of reaching defs for a particular reference
87 // node. This sequence will terminate at the first phi node [1].
88 // (2) Returning a partial sequence of reaching defs, where the final goal
89 // is to traverse past phi nodes to the actual defs arising from the code
90 // itself.
91 // In mode (2), the register reference for which the search was started
92 // may be different from the reference node RefA, for which this call was
93 // made, hence the argument RefRR, which holds the original register.
94 // Also, some definitions may have already been encountered in a previous
95 // call that will influence register covering. The register references
96 // already defined are passed in through DefRRs.
97 // In mode (1), the "continuation" considerations do not apply, and the
98 // RefRR is the same as the register in RefA, and the set DefRRs is empty.
99 //
100 // [1] It is possible for multiple phi nodes to be included in the returned
101 // sequence:
102 // SubA = phi ...
103 // SubB = phi ...
104 // ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB)
105 // However, these phi nodes are independent from one another in terms of
106 // the data-flow.
107 
109  NodeAddr<RefNode*> RefA, bool TopShadows, bool FullChain,
110  const RegisterAggr &DefRRs) {
111  NodeList RDefs; // Return value.
112  SetVector<NodeId> DefQ;
113  SetVector<NodeId> Owners;
114 
115  // Dead defs will be treated as if they were live, since they are actually
116  // on the data-flow path. They cannot be ignored because even though they
117  // do not generate meaningful values, they still modify registers.
118 
119  // If the reference is undefined, there is nothing to do.
120  if (RefA.Addr->getFlags() & NodeAttrs::Undef)
121  return RDefs;
122 
123  // The initial queue should not have reaching defs for shadows. The
124  // whole point of a shadow is that it will have a reaching def that
125  // is not aliased to the reaching defs of the related shadows.
126  NodeId Start = RefA.Id;
127  auto SNA = DFG.addr<RefNode*>(Start);
128  if (NodeId RD = SNA.Addr->getReachingDef())
129  DefQ.insert(RD);
130  if (TopShadows) {
131  for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA))
132  if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef())
133  DefQ.insert(RD);
134  }
135 
136  // Collect all the reaching defs, going up until a phi node is encountered,
137  // or there are no more reaching defs. From this set, the actual set of
138  // reaching defs will be selected.
139  // The traversal upwards must go on until a covering def is encountered.
140  // It is possible that a collection of non-covering (individually) defs
141  // will be sufficient, but keep going until a covering one is found.
142  for (unsigned i = 0; i < DefQ.size(); ++i) {
143  auto TA = DFG.addr<DefNode*>(DefQ[i]);
144  if (TA.Addr->getFlags() & NodeAttrs::PhiRef)
145  continue;
146  // Stop at the covering/overwriting def of the initial register reference.
147  RegisterRef RR = TA.Addr->getRegRef(DFG);
148  if (!DFG.IsPreservingDef(TA))
149  if (RegisterAggr::isCoverOf(RR, RefRR, PRI))
150  continue;
151  // Get the next level of reaching defs. This will include multiple
152  // reaching defs for shadows.
153  for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA))
154  if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef())
155  DefQ.insert(RD);
156  }
157 
158  // Remove all non-phi defs that are not aliased to RefRR, and collect
159  // the owners of the remaining defs.
160  SetVector<NodeId> Defs;
161  for (NodeId N : DefQ) {
162  auto TA = DFG.addr<DefNode*>(N);
163  bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef;
164  if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG)))
165  continue;
166  Defs.insert(TA.Id);
167  Owners.insert(TA.Addr->getOwner(DFG).Id);
168  }
169 
170  // Return the MachineBasicBlock containing a given instruction.
171  auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* {
172  if (IA.Addr->getKind() == NodeAttrs::Stmt)
173  return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent();
174  assert(IA.Addr->getKind() == NodeAttrs::Phi);
175  NodeAddr<PhiNode*> PA = IA;
176  NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG);
177  return BA.Addr->getCode();
178  };
179  // Less(A,B) iff instruction A is further down in the dominator tree than B.
180  auto Less = [&Block,this] (NodeId A, NodeId B) -> bool {
181  if (A == B)
182  return false;
183  auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B);
184  MachineBasicBlock *BA = Block(OA), *BB = Block(OB);
185  if (BA != BB)
186  return MDT.dominates(BB, BA);
187  // They are in the same block.
188  bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt;
189  bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt;
190  if (StmtA) {
191  if (!StmtB) // OB is a phi and phis dominate statements.
192  return true;
193  MachineInstr *CA = NodeAddr<StmtNode*>(OA).Addr->getCode();
194  MachineInstr *CB = NodeAddr<StmtNode*>(OB).Addr->getCode();
195  // The order must be linear, so tie-break such equalities.
196  if (CA == CB)
197  return A < B;
198  return MDT.dominates(CB, CA);
199  } else {
200  // OA is a phi.
201  if (StmtB)
202  return false;
203  // Both are phis. There is no ordering between phis (in terms of
204  // the data-flow), so tie-break this via node id comparison.
205  return A < B;
206  }
207  };
208 
209  std::vector<NodeId> Tmp(Owners.begin(), Owners.end());
210  std::sort(Tmp.begin(), Tmp.end(), Less);
211 
212  // The vector is a list of instructions, so that defs coming from
213  // the same instruction don't need to be artificially ordered.
214  // Then, when computing the initial segment, and iterating over an
215  // instruction, pick the defs that contribute to the covering (i.e. is
216  // not covered by previously added defs). Check the defs individually,
217  // i.e. first check each def if is covered or not (without adding them
218  // to the tracking set), and then add all the selected ones.
219 
220  // The reason for this is this example:
221  // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes).
222  // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be
223  // covered if we added A first, and A would be covered
224  // if we added B first.
225 
226  RegisterAggr RRs(DefRRs);
227 
228  auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool {
229  return TA.Addr->getKind() == NodeAttrs::Def &&
230  Defs.count(TA.Id);
231  };
232  for (NodeId T : Tmp) {
233  if (!FullChain && RRs.hasCoverOf(RefRR))
234  break;
235  auto TA = DFG.addr<InstrNode*>(T);
236  bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA);
237  NodeList Ds;
238  for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) {
239  RegisterRef QR = DA.Addr->getRegRef(DFG);
240  // Add phi defs even if they are covered by subsequent defs. This is
241  // for cases where the reached use is not covered by any of the defs
242  // encountered so far: the phi def is needed to expose the liveness
243  // of that use to the entry of the block.
244  // Example:
245  // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2.
246  // d2<R3>(d1,,u3), ...
247  // ..., u3<D1>(d2) This use needs to be live on entry.
248  if (FullChain || IsPhi || !RRs.hasCoverOf(QR))
249  Ds.push_back(DA);
250  }
251  RDefs.insert(RDefs.end(), Ds.begin(), Ds.end());
252  for (NodeAddr<DefNode*> DA : Ds) {
253  // When collecting a full chain of definitions, do not consider phi
254  // defs to actually define a register.
255  uint16_t Flags = DA.Addr->getFlags();
256  if (!FullChain || !(Flags & NodeAttrs::PhiRef))
257  if (!(Flags & NodeAttrs::Preserving)) // Don't care about Undef here.
258  RRs.insert(DA.Addr->getRegRef(DFG));
259  }
260  }
261 
262  auto DeadP = [](const NodeAddr<DefNode*> DA) -> bool {
263  return DA.Addr->getFlags() & NodeAttrs::Dead;
264  };
265  RDefs.resize(std::distance(RDefs.begin(), llvm::remove_if(RDefs, DeadP)));
266 
267  return RDefs;
268 }
269 
270 std::pair<NodeSet,bool>
272  NodeSet &Visited, const NodeSet &Defs) {
273  return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0, MaxRecNest);
274 }
275 
276 std::pair<NodeSet,bool>
277 Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode*> RefA,
278  NodeSet &Visited, const NodeSet &Defs, unsigned Nest, unsigned MaxNest) {
279  if (Nest > MaxNest)
280  return { NodeSet(), false };
281  // Collect all defined registers. Do not consider phis to be defining
282  // anything, only collect "real" definitions.
283  RegisterAggr DefRRs(PRI);
284  for (NodeId D : Defs) {
285  const auto DA = DFG.addr<const DefNode*>(D);
286  if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
287  DefRRs.insert(DA.Addr->getRegRef(DFG));
288  }
289 
290  NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs);
291  if (RDs.empty())
292  return { Defs, true };
293 
294  // Make a copy of the preexisting definitions and add the newly found ones.
295  NodeSet TmpDefs = Defs;
296  for (NodeAddr<NodeBase*> R : RDs)
297  TmpDefs.insert(R.Id);
298 
299  NodeSet Result = Defs;
300 
301  for (NodeAddr<DefNode*> DA : RDs) {
302  Result.insert(DA.Id);
303  if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
304  continue;
305  NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG);
306  if (Visited.count(PA.Id))
307  continue;
308  Visited.insert(PA.Id);
309  // Go over all phi uses and get the reaching defs for each use.
310  for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
311  const auto &T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs,
312  Nest+1, MaxNest);
313  if (!T.second)
314  return { T.first, false };
315  Result.insert(T.first.begin(), T.first.end());
316  }
317  }
318 
319  return { Result, true };
320 }
321 
322 /// Find the nearest ref node aliased to RefRR, going upwards in the data
323 /// flow, starting from the instruction immediately preceding Inst.
326  NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
327  NodeList Ins = BA.Addr->members(DFG);
328  NodeId FindId = IA.Id;
329  auto E = Ins.rend();
330  auto B = std::find_if(Ins.rbegin(), E,
331  [FindId] (const NodeAddr<InstrNode*> T) {
332  return T.Id == FindId;
333  });
334  // Do not scan IA (which is what B would point to).
335  if (B != E)
336  ++B;
337 
338  do {
339  // Process the range of instructions from B to E.
340  for (NodeAddr<InstrNode*> I : make_range(B, E)) {
341  NodeList Refs = I.Addr->members(DFG);
342  NodeAddr<RefNode*> Clob, Use;
343  // Scan all the refs in I aliased to RefRR, and return the one that
344  // is the closest to the output of I, i.e. def > clobber > use.
345  for (NodeAddr<RefNode*> R : Refs) {
346  if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR))
347  continue;
348  if (DFG.IsDef(R)) {
349  // If it's a non-clobbering def, just return it.
350  if (!(R.Addr->getFlags() & NodeAttrs::Clobbering))
351  return R;
352  Clob = R;
353  } else {
354  Use = R;
355  }
356  }
357  if (Clob.Id != 0)
358  return Clob;
359  if (Use.Id != 0)
360  return Use;
361  }
362 
363  // Go up to the immediate dominator, if any.
364  MachineBasicBlock *BB = BA.Addr->getCode();
365  BA = NodeAddr<BlockNode*>();
366  if (MachineDomTreeNode *N = MDT.getNode(BB)) {
367  if ((N = N->getIDom()))
368  BA = DFG.findBlock(N->getBlock());
369  }
370  if (!BA.Id)
371  break;
372 
373  Ins = BA.Addr->members(DFG);
374  B = Ins.rbegin();
375  E = Ins.rend();
376  } while (true);
377 
378  return NodeAddr<RefNode*>();
379 }
380 
382  NodeAddr<DefNode*> DefA, const RegisterAggr &DefRRs) {
383  NodeSet Uses;
384 
385  // If the original register is already covered by all the intervening
386  // defs, no more uses can be reached.
387  if (DefRRs.hasCoverOf(RefRR))
388  return Uses;
389 
390  // Add all directly reached uses.
391  // If the def is dead, it does not provide a value for any use.
392  bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead;
393  NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0;
394  while (U != 0) {
395  auto UA = DFG.addr<UseNode*>(U);
396  if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) {
397  RegisterRef UR = UA.Addr->getRegRef(DFG);
398  if (PRI.alias(RefRR, UR) && !DefRRs.hasCoverOf(UR))
399  Uses.insert(U);
400  }
401  U = UA.Addr->getSibling();
402  }
403 
404  // Traverse all reached defs. This time dead defs cannot be ignored.
405  for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) {
406  auto DA = DFG.addr<DefNode*>(D);
407  NextD = DA.Addr->getSibling();
408  RegisterRef DR = DA.Addr->getRegRef(DFG);
409  // If this def is already covered, it cannot reach anything new.
410  // Similarly, skip it if it is not aliased to the interesting register.
411  if (DefRRs.hasCoverOf(DR) || !PRI.alias(RefRR, DR))
412  continue;
413  NodeSet T;
414  if (DFG.IsPreservingDef(DA)) {
415  // If it is a preserving def, do not update the set of intervening defs.
416  T = getAllReachedUses(RefRR, DA, DefRRs);
417  } else {
418  RegisterAggr NewDefRRs = DefRRs;
419  NewDefRRs.insert(DR);
420  T = getAllReachedUses(RefRR, DA, NewDefRRs);
421  }
422  Uses.insert(T.begin(), T.end());
423  }
424  return Uses;
425 }
426 
428  RealUseMap.clear();
429 
430  NodeList Phis;
431  NodeAddr<FuncNode*> FA = DFG.getFunc();
432  NodeList Blocks = FA.Addr->members(DFG);
433  for (NodeAddr<BlockNode*> BA : Blocks) {
434  auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
435  Phis.insert(Phis.end(), Ps.begin(), Ps.end());
436  }
437 
438  // phi use -> (map: reaching phi -> set of registers defined in between)
439  std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp;
440  std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation.
441  std::map<NodeId,RegisterAggr> PhiDRs; // Phi -> registers defined by it.
442 
443  // Go over all phis.
444  for (NodeAddr<PhiNode*> PhiA : Phis) {
445  // Go over all defs and collect the reached uses that are non-phi uses
446  // (i.e. the "real uses").
447  RefMap &RealUses = RealUseMap[PhiA.Id];
448  NodeList PhiRefs = PhiA.Addr->members(DFG);
449 
450  // Have a work queue of defs whose reached uses need to be found.
451  // For each def, add to the queue all reached (non-phi) defs.
452  SetVector<NodeId> DefQ;
453  NodeSet PhiDefs;
454  RegisterAggr DRs(PRI);
455  for (NodeAddr<RefNode*> R : PhiRefs) {
456  if (!DFG.IsRef<NodeAttrs::Def>(R))
457  continue;
458  DRs.insert(R.Addr->getRegRef(DFG));
459  DefQ.insert(R.Id);
460  PhiDefs.insert(R.Id);
461  }
462  PhiDRs.insert(std::make_pair(PhiA.Id, DRs));
463 
464  // Collect the super-set of all possible reached uses. This set will
465  // contain all uses reached from this phi, either directly from the
466  // phi defs, or (recursively) via non-phi defs reached by the phi defs.
467  // This set of uses will later be trimmed to only contain these uses that
468  // are actually reached by the phi defs.
469  for (unsigned i = 0; i < DefQ.size(); ++i) {
470  NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]);
471  // Visit all reached uses. Phi defs should not really have the "dead"
472  // flag set, but check it anyway for consistency.
473  bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead;
474  NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0;
475  while (UN != 0) {
476  NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN);
477  uint16_t F = A.Addr->getFlags();
478  if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) {
479  RegisterRef R = PRI.normalize(A.Addr->getRegRef(DFG));
480  RealUses[R.Reg].insert({A.Id,R.Mask});
481  }
482  UN = A.Addr->getSibling();
483  }
484  // Visit all reached defs, and add them to the queue. These defs may
485  // override some of the uses collected here, but that will be handled
486  // later.
487  NodeId DN = DA.Addr->getReachedDef();
488  while (DN != 0) {
489  NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN);
490  for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) {
491  uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags();
492  // Must traverse the reached-def chain. Consider:
493  // def(D0) -> def(R0) -> def(R0) -> use(D0)
494  // The reachable use of D0 passes through a def of R0.
495  if (!(Flags & NodeAttrs::PhiRef))
496  DefQ.insert(T.Id);
497  }
498  DN = A.Addr->getSibling();
499  }
500  }
501  // Filter out these uses that appear to be reachable, but really
502  // are not. For example:
503  //
504  // R1:0 = d1
505  // = R1:0 u2 Reached by d1.
506  // R0 = d3
507  // = R1:0 u4 Still reached by d1: indirectly through
508  // the def d3.
509  // R1 = d5
510  // = R1:0 u6 Not reached by d1 (covered collectively
511  // by d3 and d5), but following reached
512  // defs and uses from d1 will lead here.
513  for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) {
514  // For each reached register UI->first, there is a set UI->second, of
515  // uses of it. For each such use, check if it is reached by this phi,
516  // i.e. check if the set of its reaching uses intersects the set of
517  // this phi's defs.
518  NodeRefSet Uses = UI->second;
519  UI->second.clear();
520  for (std::pair<NodeId,LaneBitmask> I : Uses) {
521  auto UA = DFG.addr<UseNode*>(I.first);
522  // Undef flag is checked above.
523  assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0);
524  RegisterRef R(UI->first, I.second);
525  // Calculate the exposed part of the reached use.
526  RegisterAggr Covered(PRI);
527  for (NodeAddr<DefNode*> DA : getAllReachingDefs(R, UA)) {
528  if (PhiDefs.count(DA.Id))
529  break;
530  Covered.insert(DA.Addr->getRegRef(DFG));
531  }
532  if (RegisterRef RC = Covered.clearIn(R)) {
533  // We are updating the map for register UI->first, so we need
534  // to map RC to be expressed in terms of that register.
535  RegisterRef S = PRI.mapTo(RC, UI->first);
536  UI->second.insert({I.first, S.Mask});
537  }
538  }
539  UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI);
540  }
541 
542  // If this phi reaches some "real" uses, add it to the queue for upward
543  // propagation.
544  if (!RealUses.empty())
545  PhiUQ.push_back(PhiA.Id);
546 
547  // Go over all phi uses and check if the reaching def is another phi.
548  // Collect the phis that are among the reaching defs of these uses.
549  // While traversing the list of reaching defs for each phi use, accumulate
550  // the set of registers defined between this phi (PhiA) and the owner phi
551  // of the reaching def.
552  NodeSet SeenUses;
553 
554  for (auto I : PhiRefs) {
555  if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id))
556  continue;
557  NodeAddr<PhiUseNode*> PUA = I;
558  if (PUA.Addr->getReachingDef() == 0)
559  continue;
560 
561  RegisterRef UR = PUA.Addr->getRegRef(DFG);
562  NodeList Ds = getAllReachingDefs(UR, PUA, true, false, NoRegs);
563  RegisterAggr DefRRs(PRI);
564 
565  for (NodeAddr<DefNode*> D : Ds) {
566  if (D.Addr->getFlags() & NodeAttrs::PhiRef) {
567  NodeId RP = D.Addr->getOwner(DFG).Id;
568  std::map<NodeId,RegisterAggr> &M = PhiUp[PUA.Id];
569  auto F = M.find(RP);
570  if (F == M.end())
571  M.insert(std::make_pair(RP, DefRRs));
572  else
573  F->second.insert(DefRRs);
574  }
575  DefRRs.insert(D.Addr->getRegRef(DFG));
576  }
577 
578  for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PhiA, PUA))
579  SeenUses.insert(T.Id);
580  }
581  }
582 
583  if (Trace) {
584  dbgs() << "Phi-up-to-phi map with intervening defs:\n";
585  for (auto I : PhiUp) {
586  dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {";
587  for (auto R : I.second)
588  dbgs() << ' ' << Print<NodeId>(R.first, DFG)
589  << Print<RegisterAggr>(R.second, DFG);
590  dbgs() << " }\n";
591  }
592  }
593 
594  // Propagate the reached registers up in the phi chain.
595  //
596  // The following type of situation needs careful handling:
597  //
598  // phi d1<R1:0> (1)
599  // |
600  // ... d2<R1>
601  // |
602  // phi u3<R1:0> (2)
603  // |
604  // ... u4<R1>
605  //
606  // The phi node (2) defines a register pair R1:0, and reaches a "real"
607  // use u4 of just R1. The same phi node is also known to reach (upwards)
608  // the phi node (1). However, the use u4 is not reached by phi (1),
609  // because of the intervening definition d2 of R1. The data flow between
610  // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0.
611  //
612  // When propagating uses up the phi chains, get the all reaching defs
613  // for a given phi use, and traverse the list until the propagated ref
614  // is covered, or until reaching the final phi. Only assume that the
615  // reference reaches the phi in the latter case.
616 
617  for (unsigned i = 0; i < PhiUQ.size(); ++i) {
618  auto PA = DFG.addr<PhiNode*>(PhiUQ[i]);
619  NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG);
620  RefMap &RUM = RealUseMap[PA.Id];
621 
622  for (NodeAddr<UseNode*> UA : PUs) {
623  std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id];
624  RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG));
625  for (const std::pair<NodeId,RegisterAggr> &P : PUM) {
626  bool Changed = false;
627  const RegisterAggr &MidDefs = P.second;
628 
629  // Collect the set PropUp of uses that are reached by the current
630  // phi PA, and are not covered by any intervening def between the
631  // currently visited use UA and the the upward phi P.
632 
633  if (MidDefs.hasCoverOf(UR))
634  continue;
635 
636  // General algorithm:
637  // for each (R,U) : U is use node of R, U is reached by PA
638  // if MidDefs does not cover (R,U)
639  // then add (R-MidDefs,U) to RealUseMap[P]
640  //
641  for (const std::pair<RegisterId,NodeRefSet> &T : RUM) {
642  RegisterRef R(T.first);
643  // The current phi (PA) could be a phi for a regmask. It could
644  // reach a whole variety of uses that are not related to the
645  // specific upward phi (P.first).
646  const RegisterAggr &DRs = PhiDRs.at(P.first);
647  if (!DRs.hasAliasOf(R))
648  continue;
649  R = PRI.mapTo(DRs.intersectWith(R), T.first);
650  for (std::pair<NodeId,LaneBitmask> V : T.second) {
651  LaneBitmask M = R.Mask & V.second;
652  if (M.none())
653  continue;
654  if (RegisterRef SS = MidDefs.clearIn(RegisterRef(R.Reg, M))) {
655  NodeRefSet &RS = RealUseMap[P.first][SS.Reg];
656  Changed |= RS.insert({V.first,SS.Mask}).second;
657  }
658  }
659  }
660 
661  if (Changed)
662  PhiUQ.push_back(P.first);
663  }
664  }
665  }
666 
667  if (Trace) {
668  dbgs() << "Real use map:\n";
669  for (auto I : RealUseMap) {
670  dbgs() << "phi " << Print<NodeId>(I.first, DFG);
671  NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first);
672  NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG);
673  if (!Ds.empty()) {
674  RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(DFG);
675  dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>';
676  } else {
677  dbgs() << "<noreg>";
678  }
679  dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n';
680  }
681  }
682 }
683 
685  // Populate the node-to-block map. This speeds up the calculations
686  // significantly.
687  NBMap.clear();
688  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
689  MachineBasicBlock *BB = BA.Addr->getCode();
690  for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
691  for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
692  NBMap.insert(std::make_pair(RA.Id, BB));
693  NBMap.insert(std::make_pair(IA.Id, BB));
694  }
695  }
696 
697  MachineFunction &MF = DFG.getMF();
698 
699  // Compute IDF first, then the inverse.
700  decltype(IIDF) IDF;
701  for (MachineBasicBlock &B : MF) {
702  auto F1 = MDF.find(&B);
703  if (F1 == MDF.end())
704  continue;
705  SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end());
706  for (unsigned i = 0; i < IDFB.size(); ++i) {
707  auto F2 = MDF.find(IDFB[i]);
708  if (F2 != MDF.end())
709  IDFB.insert(F2->second.begin(), F2->second.end());
710  }
711  // Add B to the IDF(B). This will put B in the IIDF(B).
712  IDFB.insert(&B);
713  IDF[&B].insert(IDFB.begin(), IDFB.end());
714  }
715 
716  for (auto I : IDF)
717  for (auto S : I.second)
718  IIDF[S].insert(I.first);
719 
720  computePhiInfo();
721 
722  NodeAddr<FuncNode*> FA = DFG.getFunc();
723  NodeList Blocks = FA.Addr->members(DFG);
724 
725  // Build the phi live-on-entry map.
726  for (NodeAddr<BlockNode*> BA : Blocks) {
727  MachineBasicBlock *MB = BA.Addr->getCode();
728  RefMap &LON = PhiLON[MB];
729  for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG))
730  for (const RefMap::value_type &S : RealUseMap[P.Id])
731  LON[S.first].insert(S.second.begin(), S.second.end());
732  }
733 
734  if (Trace) {
735  dbgs() << "Phi live-on-entry map:\n";
736  for (auto &I : PhiLON)
737  dbgs() << "block #" << I.first->getNumber() << " -> "
738  << Print<RefMap>(I.second, DFG) << '\n';
739  }
740 
741  // Build the phi live-on-exit map. Each phi node has some set of reached
742  // "real" uses. Propagate this set backwards into the block predecessors
743  // through the reaching defs of the corresponding phi uses.
744  for (NodeAddr<BlockNode*> BA : Blocks) {
745  NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
746  for (NodeAddr<PhiNode*> PA : Phis) {
747  RefMap &RUs = RealUseMap[PA.Id];
748  if (RUs.empty())
749  continue;
750 
751  NodeSet SeenUses;
752  for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
753  if (!SeenUses.insert(U.Id).second)
754  continue;
755  NodeAddr<PhiUseNode*> PUA = U;
756  if (PUA.Addr->getReachingDef() == 0)
757  continue;
758 
759  // Each phi has some set (possibly empty) of reached "real" uses,
760  // that is, uses that are part of the compiled program. Such a use
761  // may be located in some farther block, but following a chain of
762  // reaching defs will eventually lead to this phi.
763  // Any chain of reaching defs may fork at a phi node, but there
764  // will be a path upwards that will lead to this phi. Now, this
765  // chain will need to fork at this phi, since some of the reached
766  // uses may have definitions joining in from multiple predecessors.
767  // For each reached "real" use, identify the set of reaching defs
768  // coming from each predecessor P, and add them to PhiLOX[P].
769  //
770  auto PrA = DFG.addr<BlockNode*>(PUA.Addr->getPredecessor());
771  RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
772 
773  for (const std::pair<RegisterId,NodeRefSet> &RS : RUs) {
774  // We need to visit each individual use.
775  for (std::pair<NodeId,LaneBitmask> P : RS.second) {
776  // Create a register ref corresponding to the use, and find
777  // all reaching defs starting from the phi use, and treating
778  // all related shadows as a single use cluster.
779  RegisterRef S(RS.first, P.second);
780  NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs);
781  for (NodeAddr<DefNode*> D : Ds) {
782  // Calculate the mask corresponding to the visited def.
783  RegisterAggr TA(PRI);
784  TA.insert(D.Addr->getRegRef(DFG)).intersect(S);
785  LaneBitmask TM = TA.makeRegRef().Mask;
786  LOX[S.Reg].insert({D.Id, TM});
787  }
788  }
789  }
790 
791  for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PA, PUA))
792  SeenUses.insert(T.Id);
793  } // for U : phi uses
794  } // for P : Phis
795  } // for B : Blocks
796 
797  if (Trace) {
798  dbgs() << "Phi live-on-exit map:\n";
799  for (auto &I : PhiLOX)
800  dbgs() << "block #" << I.first->getNumber() << " -> "
801  << Print<RefMap>(I.second, DFG) << '\n';
802  }
803 
804  RefMap LiveIn;
805  traverse(&MF.front(), LiveIn);
806 
807  // Add function live-ins to the live-in set of the function entry block.
808  LiveMap[&MF.front()].insert(DFG.getLiveIns());
809 
810  if (Trace) {
811  // Dump the liveness map
812  for (MachineBasicBlock &B : MF) {
813  std::vector<RegisterRef> LV;
814  for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
815  LV.push_back(RegisterRef(I->PhysReg, I->LaneMask));
816  std::sort(LV.begin(), LV.end());
817  dbgs() << printMBBReference(B) << "\t rec = {";
818  for (auto I : LV)
819  dbgs() << ' ' << Print<RegisterRef>(I, DFG);
820  dbgs() << " }\n";
821  //dbgs() << "\tcomp = " << Print<RegisterAggr>(LiveMap[&B], DFG) << '\n';
822 
823  LV.clear();
824  const RegisterAggr &LG = LiveMap[&B];
825  for (auto I = LG.rr_begin(), E = LG.rr_end(); I != E; ++I)
826  LV.push_back(*I);
827  std::sort(LV.begin(), LV.end());
828  dbgs() << "\tcomp = {";
829  for (auto I : LV)
830  dbgs() << ' ' << Print<RegisterRef>(I, DFG);
831  dbgs() << " }\n";
832 
833  }
834  }
835 }
836 
838  for (auto &B : DFG.getMF()) {
839  // Remove all live-ins.
840  std::vector<unsigned> T;
841  for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
842  T.push_back(I->PhysReg);
843  for (auto I : T)
844  B.removeLiveIn(I);
845  // Add the newly computed live-ins.
846  const RegisterAggr &LiveIns = LiveMap[&B];
847  for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) {
848  RegisterRef R = *I;
849  B.addLiveIn({MCPhysReg(R.Reg), R.Mask});
850  }
851  }
852 }
853 
855  for (auto &B : DFG.getMF())
856  resetKills(&B);
857 }
858 
860  auto CopyLiveIns = [this] (MachineBasicBlock *B, BitVector &LV) -> void {
861  for (auto I : B->liveins()) {
862  MCSubRegIndexIterator S(I.PhysReg, &TRI);
863  if (!S.isValid()) {
864  LV.set(I.PhysReg);
865  continue;
866  }
867  do {
868  LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex());
869  if ((M & I.LaneMask).any())
870  LV.set(S.getSubReg());
871  ++S;
872  } while (S.isValid());
873  }
874  };
875 
876  BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs());
877  CopyLiveIns(B, LiveIn);
878  for (auto SI : B->successors())
879  CopyLiveIns(SI, Live);
880 
881  for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) {
882  MachineInstr *MI = &*I;
883  if (MI->isDebugValue())
884  continue;
885 
886  MI->clearKillInfo();
887  for (auto &Op : MI->operands()) {
888  // An implicit def of a super-register may not necessarily start a
889  // live range of it, since an implicit use could be used to keep parts
890  // of it live. Instead of analyzing the implicit operands, ignore
891  // implicit defs.
892  if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
893  continue;
894  unsigned R = Op.getReg();
896  continue;
897  for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR)
898  Live.reset(*SR);
899  }
900  for (auto &Op : MI->operands()) {
901  if (!Op.isReg() || !Op.isUse() || Op.isUndef())
902  continue;
903  unsigned R = Op.getReg();
905  continue;
906  bool IsLive = false;
907  for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) {
908  if (!Live[*AR])
909  continue;
910  IsLive = true;
911  break;
912  }
913  if (!IsLive)
914  Op.setIsKill(true);
915  for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR)
916  Live.set(*SR);
917  }
918  }
919 }
920 
921 // Helper function to obtain the basic block containing the reaching def
922 // of the given use.
923 MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const {
924  auto F = NBMap.find(RN);
925  if (F != NBMap.end())
926  return F->second;
927  llvm_unreachable("Node id not in map");
928 }
929 
930 void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
931  // The LiveIn map, for each (physical) register, contains the set of live
932  // reaching defs of that register that are live on entry to the associated
933  // block.
934 
935  // The summary of the traversal algorithm:
936  //
937  // R is live-in in B, if there exists a U(R), such that rdef(R) dom B
938  // and (U \in IDF(B) or B dom U).
939  //
940  // for (C : children) {
941  // LU = {}
942  // traverse(C, LU)
943  // LiveUses += LU
944  // }
945  //
946  // LiveUses -= Defs(B);
947  // LiveUses += UpwardExposedUses(B);
948  // for (C : IIDF[B])
949  // for (U : LiveUses)
950  // if (Rdef(U) dom C)
951  // C.addLiveIn(U)
952  //
953 
954  // Go up the dominator tree (depth-first).
955  MachineDomTreeNode *N = MDT.getNode(B);
956  for (auto I : *N) {
957  RefMap L;
958  MachineBasicBlock *SB = I->getBlock();
959  traverse(SB, L);
960 
961  for (auto S : L)
962  LiveIn[S.first].insert(S.second.begin(), S.second.end());
963  }
964 
965  if (Trace) {
966  dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__
967  << " after recursion into: {";
968  for (auto I : *N)
969  dbgs() << ' ' << I->getBlock()->getNumber();
970  dbgs() << " }\n";
971  dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
972  dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
973  }
974 
975  // Add reaching defs of phi uses that are live on exit from this block.
976  RefMap &PUs = PhiLOX[B];
977  for (auto &S : PUs)
978  LiveIn[S.first].insert(S.second.begin(), S.second.end());
979 
980  if (Trace) {
981  dbgs() << "after LOX\n";
982  dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
983  dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
984  }
985 
986  // The LiveIn map at this point has all defs that are live-on-exit from B,
987  // as if they were live-on-entry to B. First, we need to filter out all
988  // defs that are present in this block. Then we will add reaching defs of
989  // all upward-exposed uses.
990 
991  // To filter out the defs, first make a copy of LiveIn, and then re-populate
992  // LiveIn with the defs that should remain.
993  RefMap LiveInCopy = LiveIn;
994  LiveIn.clear();
995 
996  for (const std::pair<RegisterId,NodeRefSet> &LE : LiveInCopy) {
997  RegisterRef LRef(LE.first);
998  NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled.
999  const NodeRefSet &OldDefs = LE.second;
1000  for (NodeRef OR : OldDefs) {
1001  // R is a def node that was live-on-exit
1002  auto DA = DFG.addr<DefNode*>(OR.first);
1003  NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
1004  NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
1005  if (B != BA.Addr->getCode()) {
1006  // Defs from a different block need to be preserved. Defs from this
1007  // block will need to be processed further, except for phi defs, the
1008  // liveness of which is handled through the PhiLON/PhiLOX maps.
1009  NewDefs.insert(OR);
1010  continue;
1011  }
1012 
1013  // Defs from this block need to stop the liveness from being
1014  // propagated upwards. This only applies to non-preserving defs,
1015  // and to the parts of the register actually covered by those defs.
1016  // (Note that phi defs should always be preserving.)
1017  RegisterAggr RRs(PRI);
1018  LRef.Mask = OR.second;
1019 
1020  if (!DFG.IsPreservingDef(DA)) {
1021  assert(!(IA.Addr->getFlags() & NodeAttrs::Phi));
1022  // DA is a non-phi def that is live-on-exit from this block, and
1023  // that is also located in this block. LRef is a register ref
1024  // whose use this def reaches. If DA covers LRef, then no part
1025  // of LRef is exposed upwards.A
1026  if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
1027  continue;
1028  }
1029 
1030  // DA itself was not sufficient to cover LRef. In general, it is
1031  // the last in a chain of aliased defs before the exit from this block.
1032  // There could be other defs in this block that are a part of that
1033  // chain. Check that now: accumulate the registers from these defs,
1034  // and if they all together cover LRef, it is not live-on-entry.
1035  for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) {
1036  // DefNode -> InstrNode -> BlockNode.
1037  NodeAddr<InstrNode*> ITA = TA.Addr->getOwner(DFG);
1038  NodeAddr<BlockNode*> BTA = ITA.Addr->getOwner(DFG);
1039  // Reaching defs are ordered in the upward direction.
1040  if (BTA.Addr->getCode() != B) {
1041  // We have reached past the beginning of B, and the accumulated
1042  // registers are not covering LRef. The first def from the
1043  // upward chain will be live.
1044  // Subtract all accumulated defs (RRs) from LRef.
1045  RegisterRef T = RRs.clearIn(LRef);
1046  assert(T);
1047  NewDefs.insert({TA.Id,T.Mask});
1048  break;
1049  }
1050 
1051  // TA is in B. Only add this def to the accumulated cover if it is
1052  // not preserving.
1053  if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
1054  RRs.insert(TA.Addr->getRegRef(DFG));
1055  // If this is enough to cover LRef, then stop.
1056  if (RRs.hasCoverOf(LRef))
1057  break;
1058  }
1059  }
1060  }
1061 
1062  emptify(LiveIn);
1063 
1064  if (Trace) {
1065  dbgs() << "after defs in block\n";
1066  dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
1067  dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
1068  }
1069 
1070  // Scan the block for upward-exposed uses and add them to the tracking set.
1071  for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) {
1072  NodeAddr<InstrNode*> IA = I;
1073  if (IA.Addr->getKind() != NodeAttrs::Stmt)
1074  continue;
1075  for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
1076  if (UA.Addr->getFlags() & NodeAttrs::Undef)
1077  continue;
1078  RegisterRef RR = PRI.normalize(UA.Addr->getRegRef(DFG));
1079  for (NodeAddr<DefNode*> D : getAllReachingDefs(UA))
1080  if (getBlockWithRef(D.Id) != B)
1081  LiveIn[RR.Reg].insert({D.Id,RR.Mask});
1082  }
1083  }
1084 
1085  if (Trace) {
1086  dbgs() << "after uses in block\n";
1087  dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
1088  dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
1089  }
1090 
1091  // Phi uses should not be propagated up the dominator tree, since they
1092  // are not dominated by their corresponding reaching defs.
1093  RegisterAggr &Local = LiveMap[B];
1094  RefMap &LON = PhiLON[B];
1095  for (auto &R : LON) {
1096  LaneBitmask M;
1097  for (auto P : R.second)
1098  M |= P.second;
1099  Local.insert(RegisterRef(R.first,M));
1100  }
1101 
1102  if (Trace) {
1103  dbgs() << "after phi uses in block\n";
1104  dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
1105  dbgs() << " Local: " << Print<RegisterAggr>(Local, DFG) << '\n';
1106  }
1107 
1108  for (auto C : IIDF[B]) {
1109  RegisterAggr &LiveC = LiveMap[C];
1110  for (const std::pair<RegisterId,NodeRefSet> &S : LiveIn)
1111  for (auto R : S.second)
1112  if (MDT.properlyDominates(getBlockWithRef(R.first), C))
1113  LiveC.insert(RegisterRef(S.first, R.second));
1114  }
1115 }
1116 
1117 void Liveness::emptify(RefMap &M) {
1118  for (auto I = M.begin(), E = M.end(); I != E; )
1119  I = I->second.empty() ? M.erase(I) : std::next(I);
1120 }
bool hasCoverOf(RegisterRef RR) const
uint64_t CallInst * C
NodeId getReachedUse() const
Definition: RDFGraph.h:566
A common definition of LaneBitmask for use in TableGen and CodeGen.
uint16_t getFlags() const
Definition: RDFGraph.h:457
static cl::opt< unsigned > MaxRecNest("rdf-liveness-max-rec", cl::init(25), cl::Hidden, cl::desc("Maximum recursion level"))
bool IsDead
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
bool hasAliasOf(RegisterRef RR) const
unsigned second
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode *> RefA, NodeSet &Visited, const NodeSet &Defs)
F(f)
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:333
RegisterRef intersectWith(RegisterRef RR) const
rr_iterator rr_begin() const
Definition: RDFRegisters.h:218
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:93
RegisterRef clearIn(RegisterRef RR) const
iterator_range< succ_iterator > successors()
SI optimize exec mask operations pre RA
void clearKillInfo()
Clears kill flags on all operands.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
RegisterRef getRegRef(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:427
NodeAddr< RefNode * > getNearestAliasedRef(RegisterRef RefRR, NodeAddr< InstrNode *> IA)
Find the nearest ref node aliased to RefRR, going upwards in the data flow, starting from the instruc...
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
#define T
unsigned getSubRegIndex() const
Returns sub-register index of the current sub-register.
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:83
Base class for the actual dominator tree node.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
reverse_iterator rend()
reverse_iterator rbegin()
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:552
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned getSubReg() const
Returns current sub-register.
rr_iterator rr_end() const
Definition: RDFRegisters.h:221
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
static ManagedStatic< OptionRegistry > OR
Definition: Options.cpp:31
MCRegAliasIterator enumerates all registers aliasing Reg.
uint16_t getKind() const
Definition: RDFGraph.h:456
RegisterRef makeRegRef() const
constexpr bool none() const
Definition: LaneBitmask.h:52
NodeId getPredecessor() const
Definition: RDFGraph.h:581
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:841
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:853
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:914
MCSubRegIterator enumerates all sub-registers of Reg.
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:546
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
RegisterAggr & insert(RegisterRef RR)
bool isValid() const
Returns true if this iterator is not yet at the end.
bool isDebugValue() const
Definition: MachineInstr.h:817
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode *> RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:50
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
std::map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:53
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
NodeId getReachedDef() const
Definition: RDFGraph.h:560
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
std::set< NodeId > NodeSet
Definition: RDFGraph.h:514
Representation of each machine instruction.
Definition: MachineInstr.h:60
NodeId getReachingDef() const
Definition: RDFGraph.h:529
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:453
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
std::set< NodeRef > NodeRefSet
Definition: RDFLiveness.h:51
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode *> DefA, const RegisterAggr &DefRRs)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
iterator_range< livein_iterator > liveins() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)
Definition: RDFRegisters.h:167
A vector that has set insertion semantics.
Definition: SetVector.h:41
MachineBasicBlock * getCode() const
Definition: RDFGraph.h:628
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
IRTranslator LLVM IR MI
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
NodeId getSibling() const
Definition: RDFGraph.h:536
void resize(size_type N)
Definition: SmallVector.h:355