LLVM  10.0.0svn
RDFCopy.cpp
Go to the documentation of this file.
1 //===- RDFCopy.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 // RDF-based copy propagation.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "RDFCopy.h"
14 #include "RDFGraph.h"
15 #include "RDFLiveness.h"
16 #include "RDFRegisters.h"
23 #include "llvm/MC/MCRegisterInfo.h"
25 #include "llvm/Support/Debug.h"
28 #include <cassert>
29 #include <cstdint>
30 #include <utility>
31 
32 using namespace llvm;
33 using namespace rdf;
34 
35 #ifndef NDEBUG
36 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
37 static unsigned CpCount = 0;
38 #endif
39 
41  unsigned Opc = MI->getOpcode();
42  switch (Opc) {
43  case TargetOpcode::COPY: {
44  const MachineOperand &Dst = MI->getOperand(0);
45  const MachineOperand &Src = MI->getOperand(1);
46  RegisterRef DstR = DFG.makeRegRef(Dst.getReg(), Dst.getSubReg());
47  RegisterRef SrcR = DFG.makeRegRef(Src.getReg(), Src.getSubReg());
50  const TargetRegisterInfo &TRI = DFG.getTRI();
51  if (TRI.getMinimalPhysRegClass(DstR.Reg) !=
52  TRI.getMinimalPhysRegClass(SrcR.Reg))
53  return false;
54  EM.insert(std::make_pair(DstR, SrcR));
55  return true;
56  }
57  case TargetOpcode::REG_SEQUENCE:
58  llvm_unreachable("Unexpected REG_SEQUENCE");
59  }
60  return false;
61 }
62 
63 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
64  CopyMap.insert(std::make_pair(SA.Id, EM));
65  Copies.push_back(SA.Id);
66 }
67 
68 bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
69  bool Changed = false;
70  NodeAddr<BlockNode*> BA = DFG.findBlock(B);
71 
72  for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
73  if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
74  NodeAddr<StmtNode*> SA = IA;
75  EqualityMap EM;
76  if (interpretAsCopy(SA.Addr->getCode(), EM))
77  recordCopy(SA, EM);
78  }
79  }
80 
81  MachineDomTreeNode *N = MDT.getNode(B);
82  for (auto I : *N)
83  Changed |= scanBlock(I->getBlock());
84 
85  return Changed;
86 }
87 
88 NodeId CopyPropagation::getLocalReachingDef(RegisterRef RefRR,
91  if (RA.Id != 0) {
92  if (RA.Addr->getKind() == NodeAttrs::Def)
93  return RA.Id;
95  if (NodeId RD = RA.Addr->getReachingDef())
96  return RD;
97  }
98  return 0;
99 }
100 
102  scanBlock(&DFG.getMF().front());
103 
104  if (trace()) {
105  dbgs() << "Copies:\n";
106  for (NodeId I : Copies) {
107  dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode();
108  dbgs() << " eq: {";
109  for (auto J : CopyMap[I])
110  dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='
111  << Print<RegisterRef>(J.second, DFG);
112  dbgs() << " }\n";
113  }
114  }
115 
116  bool Changed = false;
117 #ifndef NDEBUG
118  bool HasLimit = CpLimit.getNumOccurrences() > 0;
119 #endif
120 
121  auto MinPhysReg = [this] (RegisterRef RR) -> unsigned {
122  const TargetRegisterInfo &TRI = DFG.getTRI();
123  const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Reg);
124  if ((RC.LaneMask & RR.Mask) == RC.LaneMask)
125  return RR.Reg;
126  for (MCSubRegIndexIterator S(RR.Reg, &TRI); S.isValid(); ++S)
127  if (RR.Mask == TRI.getSubRegIndexLaneMask(S.getSubRegIndex()))
128  return S.getSubReg();
129  llvm_unreachable("Should have found a register");
130  return 0;
131  };
132 
133  for (NodeId C : Copies) {
134 #ifndef NDEBUG
135  if (HasLimit && CpCount >= CpLimit)
136  break;
137 #endif
138  auto SA = DFG.addr<InstrNode*>(C);
139  auto FS = CopyMap.find(SA.Id);
140  if (FS == CopyMap.end())
141  continue;
142 
143  EqualityMap &EM = FS->second;
144  for (NodeAddr<DefNode*> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {
145  RegisterRef DR = DA.Addr->getRegRef(DFG);
146  auto FR = EM.find(DR);
147  if (FR == EM.end())
148  continue;
149  RegisterRef SR = FR->second;
150  if (DR == SR)
151  continue;
152 
153  NodeId AtCopy = getLocalReachingDef(SR, SA);
154 
155  for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
156  auto UA = DFG.addr<UseNode*>(N);
157  NextN = UA.Addr->getSibling();
158  uint16_t F = UA.Addr->getFlags();
159  if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
160  continue;
161  if (UA.Addr->getRegRef(DFG) != DR)
162  continue;
163 
164  NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
165  assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
166  NodeId AtUse = getLocalReachingDef(SR, IA);
167  if (AtCopy != AtUse)
168  continue;
169 
170  MachineOperand &Op = UA.Addr->getOp();
171  if (Op.isTied())
172  continue;
173  if (trace()) {
174  dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG)
175  << " with " << Print<RegisterRef>(SR, DFG) << " in "
176  << *NodeAddr<StmtNode*>(IA).Addr->getCode();
177  }
178 
179  unsigned NewReg = MinPhysReg(SR);
180  Op.setReg(NewReg);
181  Op.setSubReg(0);
182  DFG.unlinkUse(UA, false);
183  if (AtCopy != 0) {
184  UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(AtCopy));
185  } else {
186  UA.Addr->setReachingDef(0);
187  UA.Addr->setSibling(0);
188  }
189 
190  Changed = true;
191  #ifndef NDEBUG
192  if (HasLimit && CpCount >= CpLimit)
193  break;
194  CpCount++;
195  #endif
196 
197  auto FC = CopyMap.find(IA.Id);
198  if (FC != CopyMap.end()) {
199  // Update the EM map in the copy's entry.
200  auto &M = FC->second;
201  for (auto &J : M) {
202  if (J.second != DR)
203  continue;
204  J.second = SR;
205  break;
206  }
207  }
208  } // for (N in reached-uses)
209  } // for (DA in defs)
210  } // for (C in Copies)
211 
212  return Changed;
213 }
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:768
uint64_t CallInst * C
MachineFunction & getMF() const
Definition: RDFGraph.h:661
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static cl::opt< unsigned > CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden)
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
unsigned getSubReg() const
unsigned const TargetRegisterInfo * TRI
F(f)
SI optimize exec mask operations pre RA
bool trace() const
Definition: RDFCopy.h:35
static unsigned CpCount
Definition: RDFCopy.cpp:37
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...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
void unlinkUse(NodeAddr< UseNode *> UA, bool RemoveFromOwner)
Definition: RDFGraph.h:772
Base class for the actual dominator tree node.
void setReg(Register Reg)
Change the register this operand corresponds to.
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:964
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:533
std::map< RegisterRef, RegisterRef > EqualityMap
Definition: RDFCopy.h:38
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:656
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices...
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:663
uint16_t getKind() const
Definition: RDFGraph.h:455
MachineInstr * getCode() const
Definition: RDFGraph.h:621
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:913
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
const MachineBasicBlock & front() 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.
virtual bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM)
Definition: RDFCopy.cpp:40
bool isValid() const
Returns true if this iterator is not yet at the end.
MachineOperand class - Representation of each machine instruction operand.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx. ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Representation of each machine instruction.
Definition: MachineInstr.h:64
NodeId getReachingDef() const
Definition: RDFGraph.h:528
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void setSubReg(unsigned subReg)
static bool IsCode(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:792
const TargetRegisterClass * getMinimalPhysRegClass(unsigned Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool IsDef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:797
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
NodeId getSibling() const
Definition: RDFGraph.h:535