LLVM  8.0.0svn
HexagonRDFOpt.cpp
Go to the documentation of this file.
1 //===- HexagonRDFOpt.cpp --------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "HexagonInstrInfo.h"
11 #include "HexagonSubtarget.h"
13 #include "RDFCopy.h"
14 #include "RDFDeadCode.h"
15 #include "RDFGraph.h"
16 #include "RDFLiveness.h"
17 #include "RDFRegisters.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
28 #include "llvm/Pass.h"
30 #include "llvm/Support/Compiler.h"
31 #include "llvm/Support/Debug.h"
34 #include <cassert>
35 #include <limits>
36 #include <utility>
37 
38 using namespace llvm;
39 using namespace rdf;
40 
41 namespace llvm {
42 
45 
46 } // end namespace llvm
47 
48 static unsigned RDFCount = 0;
49 
50 static cl::opt<unsigned> RDFLimit("rdf-limit",
52 static cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
53 
54 namespace {
55 
56  class HexagonRDFOpt : public MachineFunctionPass {
57  public:
58  HexagonRDFOpt() : MachineFunctionPass(ID) {}
59 
60  void getAnalysisUsage(AnalysisUsage &AU) const override {
63  AU.setPreservesAll();
65  }
66 
67  StringRef getPassName() const override {
68  return "Hexagon RDF optimizations";
69  }
70 
71  bool runOnMachineFunction(MachineFunction &MF) override;
72 
73  MachineFunctionProperties getRequiredProperties() const override {
76  }
77 
78  static char ID;
79 
80  private:
83  };
84 
85 struct HexagonCP : public CopyPropagation {
86  HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
87 
88  bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
89 };
90 
91 struct HexagonDCE : public DeadCodeElimination {
92  HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
93  : DeadCodeElimination(G, MRI) {}
94 
95  bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
96  void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
97 
98  bool run();
99 };
100 
101 } // end anonymous namespace
102 
103 char HexagonRDFOpt::ID = 0;
104 
105 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
106  "Hexagon RDF optimizations", false, false)
109 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
110  "Hexagon RDF optimizations", false, false)
111 
112 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
113  auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
114  EM.insert(std::make_pair(DstR, SrcR));
115  };
116 
117  DataFlowGraph &DFG = getDFG();
118  unsigned Opc = MI->getOpcode();
119  switch (Opc) {
120  case Hexagon::A2_combinew: {
121  const MachineOperand &DstOp = MI->getOperand(0);
122  const MachineOperand &HiOp = MI->getOperand(1);
123  const MachineOperand &LoOp = MI->getOperand(2);
124  assert(DstOp.getSubReg() == 0 && "Unexpected subregister");
125  mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
126  DFG.makeRegRef(HiOp.getReg(), HiOp.getSubReg()));
127  mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
128  DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
129  return true;
130  }
131  case Hexagon::A2_addi: {
132  const MachineOperand &A = MI->getOperand(2);
133  if (!A.isImm() || A.getImm() != 0)
134  return false;
136  }
137  case Hexagon::A2_tfr: {
138  const MachineOperand &DstOp = MI->getOperand(0);
139  const MachineOperand &SrcOp = MI->getOperand(1);
140  mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
141  DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
142  return true;
143  }
144  }
145 
146  return CopyPropagation::interpretAsCopy(MI, EM);
147 }
148 
149 bool HexagonDCE::run() {
150  bool Collected = collect();
151  if (!Collected)
152  return false;
153 
154  const SetVector<NodeId> &DeadNodes = getDeadNodes();
155  const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
156 
157  using RefToInstrMap = DenseMap<NodeId, NodeId>;
158 
159  RefToInstrMap R2I;
160  SetVector<NodeId> PartlyDead;
161  DataFlowGraph &DFG = getDFG();
162 
163  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
164  for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
165  NodeAddr<StmtNode*> SA = TA;
166  for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
167  R2I.insert(std::make_pair(RA.Id, SA.Id));
168  if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
169  if (!DeadInstrs.count(SA.Id))
170  PartlyDead.insert(SA.Id);
171  }
172  }
173  }
174 
175  // Nodes to remove.
176  SetVector<NodeId> Remove = DeadInstrs;
177 
178  bool Changed = false;
179  for (NodeId N : PartlyDead) {
180  auto SA = DFG.addr<StmtNode*>(N);
181  if (trace())
182  dbgs() << "Partly dead: " << *SA.Addr->getCode();
183  Changed |= rewrite(SA, Remove);
184  }
185 
186  return erase(Remove) || Changed;
187 }
188 
189 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
190  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
191 
192  auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
193  for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
194  if (&MI->getOperand(i) == &Op)
195  return i;
196  llvm_unreachable("Invalid operand");
197  };
199  DataFlowGraph &DFG = getDFG();
200  NodeList Refs = IA.Addr->members(DFG);
201  for (NodeAddr<RefNode*> RA : Refs)
202  OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
203 
204  MI->RemoveOperand(OpNum);
205 
206  for (NodeAddr<RefNode*> RA : Refs) {
207  unsigned N = OpMap[RA.Id];
208  if (N < OpNum)
209  RA.Addr->setRegRef(&MI->getOperand(N), DFG);
210  else if (N > OpNum)
211  RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
212  }
213 }
214 
215 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
216  if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
217  return false;
218  DataFlowGraph &DFG = getDFG();
219  MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
220  auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
221  if (HII.getAddrMode(MI) != HexagonII::PostInc)
222  return false;
223  unsigned Opc = MI.getOpcode();
224  unsigned OpNum, NewOpc;
225  switch (Opc) {
226  case Hexagon::L2_loadri_pi:
227  NewOpc = Hexagon::L2_loadri_io;
228  OpNum = 1;
229  break;
230  case Hexagon::L2_loadrd_pi:
231  NewOpc = Hexagon::L2_loadrd_io;
232  OpNum = 1;
233  break;
234  case Hexagon::V6_vL32b_pi:
235  NewOpc = Hexagon::V6_vL32b_ai;
236  OpNum = 1;
237  break;
238  case Hexagon::S2_storeri_pi:
239  NewOpc = Hexagon::S2_storeri_io;
240  OpNum = 0;
241  break;
242  case Hexagon::S2_storerd_pi:
243  NewOpc = Hexagon::S2_storerd_io;
244  OpNum = 0;
245  break;
246  case Hexagon::V6_vS32b_pi:
247  NewOpc = Hexagon::V6_vS32b_ai;
248  OpNum = 0;
249  break;
250  default:
251  return false;
252  }
253  auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
254  return getDeadNodes().count(DA.Id);
255  };
256  NodeList Defs;
257  MachineOperand &Op = MI.getOperand(OpNum);
258  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
259  if (&DA.Addr->getOp() != &Op)
260  continue;
261  Defs = DFG.getRelatedRefs(IA, DA);
262  if (!llvm::all_of(Defs, IsDead))
263  return false;
264  break;
265  }
266 
267  // Mark all nodes in Defs for removal.
268  for (auto D : Defs)
269  Remove.insert(D.Id);
270 
271  if (trace())
272  dbgs() << "Rewriting: " << MI;
273  MI.setDesc(HII.get(NewOpc));
274  MI.getOperand(OpNum+2).setImm(0);
275  removeOperand(IA, OpNum);
276  if (trace())
277  dbgs() << " to: " << MI;
278 
279  return true;
280 }
281 
282 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
283  if (skipFunction(MF.getFunction()))
284  return false;
285 
286  if (RDFLimit.getPosition()) {
287  if (RDFCount >= RDFLimit)
288  return false;
289  RDFCount++;
290  }
291 
292  MDT = &getAnalysis<MachineDominatorTree>();
293  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
294  const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
295  const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
296  MRI = &MF.getRegInfo();
297  bool Changed;
298 
299  if (RDFDump)
300  MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
301 
302  TargetOperandInfo TOI(HII);
303  DataFlowGraph G(MF, HII, HRI, *MDT, MDF, TOI);
304  // Dead phi nodes are necessary for copy propagation: we can add a use
305  // of a register in a block where it would need a phi node, but which
306  // was dead (and removed) during the graph build time.
308 
309  if (RDFDump)
310  dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
311  << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
312  HexagonCP CP(G);
313  CP.trace(RDFDump);
314  Changed = CP.run();
315 
316  if (RDFDump)
317  dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
318  << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
319  HexagonDCE DCE(G, *MRI);
320  DCE.trace(RDFDump);
321  Changed |= DCE.run();
322 
323  if (Changed) {
324  if (RDFDump)
325  dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n';
326  Liveness LV(*MRI, G);
327  LV.trace(RDFDump);
328  LV.computeLiveIns();
329  LV.resetLiveIns();
330  LV.resetKills();
331  }
332 
333  if (RDFDump)
334  MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
335 
336  return false;
337 }
338 
340  return new HexagonRDFOpt();
341 }
void initializeHexagonRDFOptPass(PassRegistry &)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool IsDead
This class represents lattice values for constants.
Definition: AllocatorList.h:24
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
unsigned getReg() const
getReg - Returns the register number.
unsigned getSubReg() const
uint32_t NodeId
Definition: RDFGraph.h:261
INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt", "Hexagon RDF optimizations", false, false) INITIALIZE_PASS_END(HexagonRDFOpt
hexagon rdf opt
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1186
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static cl::opt< unsigned > RDFLimit("rdf-limit", cl::init(std::numeric_limits< unsigned >::max()))
const TargetInstrInfo & getTII() const
Definition: RDFGraph.h:663
SI optimize exec mask operations pre RA
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:661
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:412
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
void trace(bool T)
Definition: RDFLiveness.h:98
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:983
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
static unsigned RDFCount
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:657
Represent the analysis usage information of a pass.
NodeList getRelatedRefs(NodeAddr< InstrNode *> IA, NodeAddr< RefNode *> RA) const
Definition: RDFGraph.cpp:1147
void setImm(int64_t immVal)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:914
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:546
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#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:41
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
FunctionPass * createHexagonRDFOpt()
static cl::opt< bool > RDFDump("rdf-dump", cl::init(false))
MachineOperand class - Representation of each machine instruction operand.
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
hexagon rdf Hexagon RDF optimizations
int64_t getImm() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void setPreservesAll()
Set by analyses that do not transform their input at all.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define N
void build(unsigned Options=BuildOptions::None)
Definition: RDFGraph.cpp:885
static bool IsCode(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:793
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
A vector that has set insertion semantics.
Definition: SetVector.h:41
static bool IsDef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:798
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
void RemoveOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Properties which a MachineFunction may have at a given point in time.