/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/RDFCopy.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- RDFCopy.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 | | // RDF-based copy propagation. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "RDFCopy.h" |
15 | | #include "RDFGraph.h" |
16 | | #include "RDFLiveness.h" |
17 | | #include "RDFRegisters.h" |
18 | | #include "llvm/CodeGen/MachineDominators.h" |
19 | | #include "llvm/CodeGen/MachineInstr.h" |
20 | | #include "llvm/CodeGen/MachineOperand.h" |
21 | | #include "llvm/MC/MCRegisterInfo.h" |
22 | | #include "llvm/Support/CommandLine.h" |
23 | | #include "llvm/Support/Debug.h" |
24 | | #include "llvm/Support/ErrorHandling.h" |
25 | | #include "llvm/Support/raw_ostream.h" |
26 | | #include "llvm/Target/TargetOpcodes.h" |
27 | | #include "llvm/Target/TargetRegisterInfo.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 | | |
40 | 11.3k | bool CopyPropagation::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) { |
41 | 11.3k | unsigned Opc = MI->getOpcode(); |
42 | 11.3k | switch (Opc) { |
43 | 370 | case TargetOpcode::COPY: { |
44 | 370 | const MachineOperand &Dst = MI->getOperand(0); |
45 | 370 | const MachineOperand &Src = MI->getOperand(1); |
46 | 370 | RegisterRef DstR = DFG.makeRegRef(Dst.getReg(), Dst.getSubReg()); |
47 | 370 | RegisterRef SrcR = DFG.makeRegRef(Src.getReg(), Src.getSubReg()); |
48 | 370 | assert(TargetRegisterInfo::isPhysicalRegister(DstR.Reg)); |
49 | 370 | assert(TargetRegisterInfo::isPhysicalRegister(SrcR.Reg)); |
50 | 370 | const TargetRegisterInfo &TRI = DFG.getTRI(); |
51 | 370 | if (TRI.getMinimalPhysRegClass(DstR.Reg) != |
52 | 370 | TRI.getMinimalPhysRegClass(SrcR.Reg)) |
53 | 198 | return false; |
54 | 172 | EM.insert(std::make_pair(DstR, SrcR)); |
55 | 172 | return true; |
56 | 172 | } |
57 | 0 | case TargetOpcode::REG_SEQUENCE: |
58 | 0 | llvm_unreachable("Unexpected REG_SEQUENCE"); |
59 | 10.9k | } |
60 | 10.9k | return false; |
61 | 10.9k | } |
62 | | |
63 | 173 | void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) { |
64 | 173 | CopyMap.insert(std::make_pair(SA.Id, EM)); |
65 | 173 | Copies.push_back(SA.Id); |
66 | 173 | } |
67 | | |
68 | 2.05k | bool CopyPropagation::scanBlock(MachineBasicBlock *B) { |
69 | 2.05k | bool Changed = false; |
70 | 2.05k | NodeAddr<BlockNode*> BA = DFG.findBlock(B); |
71 | 2.05k | |
72 | 15.8k | for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { |
73 | 15.8k | if (DFG.IsCode<NodeAttrs::Stmt>(IA)15.8k ) { |
74 | 11.7k | NodeAddr<StmtNode*> SA = IA; |
75 | 11.7k | EqualityMap EM; |
76 | 11.7k | if (interpretAsCopy(SA.Addr->getCode(), EM)) |
77 | 173 | recordCopy(SA, EM); |
78 | 11.7k | } |
79 | 15.8k | } |
80 | 2.05k | |
81 | 2.05k | MachineDomTreeNode *N = MDT.getNode(B); |
82 | 2.05k | for (auto I : *N) |
83 | 1.19k | Changed |= scanBlock(I->getBlock()); |
84 | 2.05k | |
85 | 2.05k | return Changed; |
86 | 2.05k | } |
87 | | |
88 | | NodeId CopyPropagation::getLocalReachingDef(RegisterRef RefRR, |
89 | 304 | NodeAddr<InstrNode*> IA) { |
90 | 304 | NodeAddr<RefNode*> RA = L.getNearestAliasedRef(RefRR, IA); |
91 | 304 | if (RA.Id != 0304 ) { |
92 | 304 | if (RA.Addr->getKind() == NodeAttrs::Def) |
93 | 216 | return RA.Id; |
94 | 304 | assert(RA.Addr->getKind() == NodeAttrs::Use); |
95 | 88 | if (NodeId RD = RA.Addr->getReachingDef()) |
96 | 88 | return RD; |
97 | 0 | } |
98 | 0 | return 0; |
99 | 0 | } |
100 | | |
101 | 859 | bool CopyPropagation::run() { |
102 | 859 | scanBlock(&DFG.getMF().front()); |
103 | 859 | |
104 | 859 | if (trace()859 ) { |
105 | 0 | dbgs() << "Copies:\n"; |
106 | 0 | for (auto I : Copies) { |
107 | 0 | dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode(); |
108 | 0 | dbgs() << " eq: {"; |
109 | 0 | for (auto J : CopyMap[I]) |
110 | 0 | dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '=' |
111 | 0 | << Print<RegisterRef>(J.second, DFG); |
112 | 0 | dbgs() << " }\n"; |
113 | 0 | } |
114 | 0 | } |
115 | 859 | |
116 | 859 | bool Changed = false; |
117 | | #ifndef NDEBUG |
118 | | bool HasLimit = CpLimit.getNumOccurrences() > 0; |
119 | | #endif |
120 | | |
121 | 23 | auto MinPhysReg = [this] (RegisterRef RR) -> unsigned { |
122 | 23 | const TargetRegisterInfo &TRI = DFG.getTRI(); |
123 | 23 | const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Reg); |
124 | 23 | if ((RC.LaneMask & RR.Mask) == RC.LaneMask) |
125 | 23 | return RR.Reg; |
126 | 0 | for (MCSubRegIndexIterator S(RR.Reg, &TRI); 0 S.isValid()0 ; ++S0 ) |
127 | 0 | if (0 RR.Mask == TRI.getSubRegIndexLaneMask(S.getSubRegIndex())0 ) |
128 | 0 | return S.getSubReg(); |
129 | 0 | llvm_unreachable0 ("Should have found a register"); |
130 | 0 | return 0; |
131 | 23 | }; |
132 | 859 | |
133 | 173 | for (auto C : Copies) { |
134 | | #ifndef NDEBUG |
135 | | if (HasLimit && CpCount >= CpLimit) |
136 | | break; |
137 | | #endif |
138 | | auto SA = DFG.addr<InstrNode*>(C); |
139 | 173 | auto FS = CopyMap.find(SA.Id); |
140 | 173 | if (FS == CopyMap.end()) |
141 | 0 | continue; |
142 | 173 | |
143 | 173 | EqualityMap &EM = FS->second; |
144 | 183 | for (NodeAddr<DefNode*> DA : SA.Addr->members_if(DFG.IsDef, DFG)) { |
145 | 183 | RegisterRef DR = DA.Addr->getRegRef(DFG); |
146 | 183 | auto FR = EM.find(DR); |
147 | 183 | if (FR == EM.end()) |
148 | 2 | continue; |
149 | 181 | RegisterRef SR = FR->second; |
150 | 181 | if (DR == SR) |
151 | 0 | continue; |
152 | 181 | |
153 | 181 | NodeId AtCopy = getLocalReachingDef(SR, SA); |
154 | 181 | |
155 | 439 | for (NodeId N = DA.Addr->getReachedUse(), NextN; N439 ; N = NextN258 ) { |
156 | 258 | auto UA = DFG.addr<UseNode*>(N); |
157 | 258 | NextN = UA.Addr->getSibling(); |
158 | 258 | uint16_t F = UA.Addr->getFlags(); |
159 | 258 | if ((F & NodeAttrs::PhiRef) || 258 (F & NodeAttrs::Fixed)186 ) |
160 | 105 | continue; |
161 | 153 | if (153 UA.Addr->getRegRef(DFG) != DR153 ) |
162 | 30 | continue; |
163 | 123 | |
164 | 123 | NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG); |
165 | 123 | assert(DFG.IsCode<NodeAttrs::Stmt>(IA)); |
166 | 123 | NodeId AtUse = getLocalReachingDef(SR, IA); |
167 | 123 | if (AtCopy != AtUse) |
168 | 78 | continue; |
169 | 45 | |
170 | 45 | MachineOperand &Op = UA.Addr->getOp(); |
171 | 45 | if (Op.isTied()) |
172 | 22 | continue; |
173 | 23 | if (23 trace()23 ) { |
174 | 0 | dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG) |
175 | 0 | << " with " << Print<RegisterRef>(SR, DFG) << " in " |
176 | 0 | << *NodeAddr<StmtNode*>(IA).Addr->getCode(); |
177 | 0 | } |
178 | 23 | |
179 | 23 | unsigned NewReg = MinPhysReg(SR); |
180 | 23 | Op.setReg(NewReg); |
181 | 23 | Op.setSubReg(0); |
182 | 23 | DFG.unlinkUse(UA, false); |
183 | 23 | if (AtCopy != 023 ) { |
184 | 23 | UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(AtCopy)); |
185 | 23 | } else { |
186 | 0 | UA.Addr->setReachingDef(0); |
187 | 0 | UA.Addr->setSibling(0); |
188 | 0 | } |
189 | 23 | |
190 | 23 | Changed = true; |
191 | | #ifndef NDEBUG |
192 | | if (HasLimit && CpCount >= CpLimit) |
193 | | break; |
194 | | CpCount++; |
195 | | #endif |
196 | | |
197 | 23 | auto FC = CopyMap.find(IA.Id); |
198 | 23 | if (FC != CopyMap.end()23 ) { |
199 | 0 | // Update the EM map in the copy's entry. |
200 | 0 | auto &M = FC->second; |
201 | 0 | for (auto &J : M) { |
202 | 0 | if (J.second != DR) |
203 | 0 | continue; |
204 | 0 | J.second = SR; |
205 | 0 | break; |
206 | 0 | } |
207 | 0 | } |
208 | 258 | } // for (N in reached-uses) |
209 | 183 | } // for (DA in defs) |
210 | 173 | } // for (C in Copies) |
211 | 859 | |
212 | 859 | return Changed; |
213 | 859 | } |