1 //===--- RDFCopy.cpp ------------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Simplistic RDF-based copy propagation.
14 #include "llvm/CodeGen/MachineBasicBlock.h"
15 #include "llvm/CodeGen/MachineDominators.h"
16 #include "llvm/CodeGen/MachineInstr.h"
17 #include "llvm/Support/CommandLine.h"
22 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
23 static unsigned CpCount = 0;
29 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, MachineInstr *MI) {
30 assert(MI->getOpcode() == TargetOpcode::COPY);
31 const MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
32 RegisterRef DstR = { Op0.getReg(), Op0.getSubReg() };
33 RegisterRef SrcR = { Op1.getReg(), Op1.getSubReg() };
34 auto FS = DefM.find(SrcR);
35 if (FS == DefM.end() || FS->second.empty())
37 Copies.push_back(SA.Id);
38 RDefMap[SrcR][SA.Id] = FS->second.top()->Id;
39 // Insert DstR into the map.
44 void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
46 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
47 RRs.insert(RA.Addr->getRegRef());
49 for (auto &R : RDefMap) {
50 if (!RRs.count(R.first))
58 for (auto &R : RDefMap) {
59 if (!RRs.count(R.first))
61 auto F = DefM.find(R.first);
62 if (F == DefM.end() || F->second.empty())
64 R.second[IA.Id] = F->second.top()->Id;
69 bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
71 auto BA = DFG.getFunc().Addr->findBlock(B, DFG);
72 DFG.markBlock(BA.Id, DefM);
74 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
75 if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
76 NodeAddr<StmtNode*> SA = IA;
77 MachineInstr *MI = SA.Addr->getCode();
83 DFG.pushDefs(IA, DefM);
86 MachineDomTreeNode *N = MDT.getNode(B);
88 Changed |= scanBlock(I->getBlock());
90 DFG.releaseBlock(BA.Id, DefM);
95 bool CopyPropagation::run() {
96 scanBlock(&DFG.getMF().front());
99 dbgs() << "Copies:\n";
100 for (auto I : Copies)
101 dbgs() << *DFG.addr<StmtNode*>(I).Addr->getCode();
102 dbgs() << "\nRDef map:\n";
103 for (auto R : RDefMap) {
104 dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
105 for (auto &M : R.second)
106 dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
107 << Print<NodeId>(M.second, DFG);
112 bool Changed = false;
115 bool HasLimit = CpLimit.getNumOccurrences() > 0;
118 for (auto I : Copies) {
120 if (HasLimit && CpCount >= CpLimit)
123 if (Deleted.count(I))
125 auto SA = DFG.addr<InstrNode*>(I);
126 NodeList Ds = SA.Addr->members_if(DFG.IsDef, DFG);
129 NodeAddr<DefNode*> DA = Ds[0];
130 RegisterRef DR0 = DA.Addr->getRegRef();
131 NodeList Us = SA.Addr->members_if(DFG.IsUse, DFG);
134 NodeAddr<UseNode*> UA0 = Us[0];
135 RegisterRef UR0 = UA0.Addr->getRegRef();
136 NodeId RD0 = UA0.Addr->getReachingDef();
138 for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
139 auto UA = DFG.addr<UseNode*>(N);
140 NextN = UA.Addr->getSibling();
141 uint16_t F = UA.Addr->getFlags();
142 if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
144 if (UA.Addr->getRegRef() != DR0)
146 NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
147 assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
148 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
149 if (RDefMap[UR0][IA.Id] != RD0)
151 MachineOperand &Op = UA.Addr->getOp();
155 dbgs() << "can replace " << Print<RegisterRef>(DR0, DFG)
156 << " with " << Print<RegisterRef>(UR0, DFG) << " in "
157 << *NodeAddr<StmtNode*>(IA).Addr->getCode();
161 Op.setSubReg(UR0.Sub);
164 if (HasLimit && CpCount >= CpLimit)
170 MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
171 if (Op0.getReg() == Op1.getReg() && Op0.getSubReg() == Op1.getSubReg())
172 MI->eraseFromParent();
173 Deleted.insert(IA.Id);