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