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