LLVM  14.0.0git
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"
18 #include "llvm/CodeGen/RDFGraph.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) !=
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;
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;
94  assert(RA.Addr->getKind() == NodeAttrs::Use);
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 }
llvm::rdf::Print
Definition: RDFGraph.h:924
llvm::rdf::DataFlowGraph::getMF
MachineFunction & getMF() const
Definition: RDFGraph.h:661
llvm::rdf::RefNode::getSibling
NodeId getSibling() const
Definition: RDFGraph.h:535
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
MachineInstr.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::rdf::RegisterRef::Reg
RegisterId Reg
Definition: RDFRegisters.h:72
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::MCSubRegIndexIterator
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
Definition: MCRegisterInfo.h:607
llvm::rdf::NodeAttrs::Fixed
@ Fixed
Definition: RDFGraph.h:288
llvm::rdf::CodeNode::members_if
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:909
RDFCopy.h
llvm::rdf::InstrNode
Definition: RDFGraph.h:610
llvm::rdf::CopyPropagation::interpretAsCopy
virtual bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM)
Definition: RDFCopy.cpp:40
ErrorHandling.h
R600_InstFlag::FC
@ FC
Definition: R600Defines.h:32
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::rdf::DataFlowGraph::unlinkUse
void unlinkUse(NodeAddr< UseNode * > UA, bool RemoveFromOwner)
Definition: RDFGraph.h:768
llvm::rdf::Liveness::getNearestAliasedRef
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...
Definition: RDFLiveness.cpp:362
CpCount
static unsigned CpCount
Definition: RDFCopy.cpp:37
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
RDFRegisters.h
llvm::rdf::RegisterRef
Definition: RDFRegisters.h:71
F
#define F(x, y, z)
Definition: MD5.cpp:56
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
RDFLiveness.h
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:820
llvm::TargetRegisterInfo::getSubRegIndexLaneMask
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
Definition: TargetRegisterInfo.h:377
llvm::rdf::NodeAddr
Definition: RDFGraph.h:334
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
TargetOpcodes.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::rdf::NodeId
uint32_t NodeId
Definition: RDFGraph.h:260
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
llvm::rdf::DataFlowGraph::IsDef
static bool IsDef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:793
llvm::rdf::NodeAddr::Addr
T Addr
Definition: RDFGraph.h:351
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::rdf::DataFlowGraph::makeRegRef
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:966
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::rdf::DataFlowGraph::IsCode
static bool IsCode(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:788
llvm::TargetRegisterClass::LaneMask
const LaneBitmask LaneMask
Definition: TargetRegisterInfo.h:56
llvm::rdf::DataFlowGraph::addr
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:656
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::rdf::DataFlowGraph::getTRI
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:663
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::rdf::CodeNode::members
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:527
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:169
llvm::rdf::UseNode
Definition: RDFGraph.h:575
llvm::rdf::NodeAttrs::Def
@ Def
Definition: RDFGraph.h:275
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
MCRegisterInfo.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
RDFGraph.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::rdf::StmtNode
Definition: RDFGraph.h:620
uint32_t
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::rdf::NodeAttrs::Use
@ Use
Definition: RDFGraph.h:276
llvm::rdf::CopyPropagation::trace
bool trace() const
Definition: RDFCopy.h:35
uint16_t
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::rdf::CopyPropagation::run
bool run()
Definition: RDFCopy.cpp:101
llvm::X86AS::FS
@ FS
Definition: X86.h:188
llvm::rdf::DefNode
Definition: RDFGraph.h:558
llvm::rdf::StmtNode::getCode
MachineInstr * getCode() const
Definition: RDFGraph.h:621
llvm::rdf::NodeAddr::Id
NodeId Id
Definition: RDFGraph.h:352
llvm::rdf::NodeAttrs::PhiRef
@ PhiRef
Definition: RDFGraph.h:286
CpLimit
static cl::opt< unsigned > CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden)
llvm::rdf::NodeAttrs::Stmt
@ Stmt
Definition: RDFGraph.h:278
N
#define N
MachineOperand.h
llvm::rdf::CopyPropagation::EqualityMap
std::map< RegisterRef, RegisterRef > EqualityMap
Definition: RDFCopy.h:38
llvm::TargetRegisterInfo::getMinimalPhysRegClass
const TargetRegisterClass * getMinimalPhysRegClass(MCRegister Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
Definition: TargetRegisterInfo.cpp:211
raw_ostream.h
llvm::rdf::DataFlowGraph::findBlock
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:764
TargetRegisterInfo.h
Debug.h
MachineDominators.h
llvm::rdf::InstrNode::getOwner
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:533