/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonGenMux.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- HexagonGenMux.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 | | // During instruction selection, MUX instructions are generated for |
10 | | // conditional assignments. Since such assignments often present an |
11 | | // opportunity to predicate instructions, HexagonExpandCondsets |
12 | | // expands MUXes into pairs of conditional transfers, and then proceeds |
13 | | // with predication of the producers/consumers of the registers involved. |
14 | | // This happens after exiting from the SSA form, but before the machine |
15 | | // instruction scheduler. After the scheduler and after the register |
16 | | // allocation there can be cases of pairs of conditional transfers |
17 | | // resulting from a MUX where neither of them was further predicated. If |
18 | | // these transfers are now placed far enough from the instruction defining |
19 | | // the predicate register, they cannot use the .new form. In such cases it |
20 | | // is better to collapse them back to a single MUX instruction. |
21 | | |
22 | | #define DEBUG_TYPE "hexmux" |
23 | | |
24 | | #include "HexagonInstrInfo.h" |
25 | | #include "HexagonRegisterInfo.h" |
26 | | #include "HexagonSubtarget.h" |
27 | | #include "llvm/ADT/BitVector.h" |
28 | | #include "llvm/ADT/DenseMap.h" |
29 | | #include "llvm/ADT/SmallVector.h" |
30 | | #include "llvm/ADT/StringRef.h" |
31 | | #include "llvm/CodeGen/LivePhysRegs.h" |
32 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
33 | | #include "llvm/CodeGen/MachineFunction.h" |
34 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
35 | | #include "llvm/CodeGen/MachineInstr.h" |
36 | | #include "llvm/CodeGen/MachineInstrBuilder.h" |
37 | | #include "llvm/CodeGen/MachineOperand.h" |
38 | | #include "llvm/IR/DebugLoc.h" |
39 | | #include "llvm/MC/MCInstrDesc.h" |
40 | | #include "llvm/MC/MCRegisterInfo.h" |
41 | | #include "llvm/Pass.h" |
42 | | #include "llvm/Support/CommandLine.h" |
43 | | #include "llvm/Support/MathExtras.h" |
44 | | #include <algorithm> |
45 | | #include <cassert> |
46 | | #include <iterator> |
47 | | #include <limits> |
48 | | #include <utility> |
49 | | |
50 | | using namespace llvm; |
51 | | |
52 | | namespace llvm { |
53 | | |
54 | | FunctionPass *createHexagonGenMux(); |
55 | | void initializeHexagonGenMuxPass(PassRegistry& Registry); |
56 | | |
57 | | } // end namespace llvm |
58 | | |
59 | | // Initialize this to 0 to always prefer generating mux by default. |
60 | | static cl::opt<unsigned> MinPredDist("hexagon-gen-mux-threshold", cl::Hidden, |
61 | | cl::init(0), cl::desc("Minimum distance between predicate definition and " |
62 | | "farther of the two predicated uses")); |
63 | | |
64 | | namespace { |
65 | | |
66 | | class HexagonGenMux : public MachineFunctionPass { |
67 | | public: |
68 | | static char ID; |
69 | | |
70 | 865 | HexagonGenMux() : MachineFunctionPass(ID) {} |
71 | | |
72 | 4.22k | StringRef getPassName() const override { |
73 | 4.22k | return "Hexagon generate mux instructions"; |
74 | 4.22k | } |
75 | | |
76 | 861 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
77 | 861 | MachineFunctionPass::getAnalysisUsage(AU); |
78 | 861 | } |
79 | | |
80 | | bool runOnMachineFunction(MachineFunction &MF) override; |
81 | | |
82 | 861 | MachineFunctionProperties getRequiredProperties() const override { |
83 | 861 | return MachineFunctionProperties().set( |
84 | 861 | MachineFunctionProperties::Property::NoVRegs); |
85 | 861 | } |
86 | | |
87 | | private: |
88 | | const HexagonInstrInfo *HII = nullptr; |
89 | | const HexagonRegisterInfo *HRI = nullptr; |
90 | | |
91 | | struct CondsetInfo { |
92 | | unsigned PredR = 0; |
93 | | unsigned TrueX = std::numeric_limits<unsigned>::max(); |
94 | | unsigned FalseX = std::numeric_limits<unsigned>::max(); |
95 | | |
96 | 314 | CondsetInfo() = default; |
97 | | }; |
98 | | |
99 | | struct DefUseInfo { |
100 | | BitVector Defs, Uses; |
101 | | |
102 | 0 | DefUseInfo() = default; |
103 | 28.1k | DefUseInfo(const BitVector &D, const BitVector &U) : Defs(D), Uses(U) {} |
104 | | }; |
105 | | |
106 | | struct MuxInfo { |
107 | | MachineBasicBlock::iterator At; |
108 | | unsigned DefR, PredR; |
109 | | MachineOperand *SrcT, *SrcF; |
110 | | MachineInstr *Def1, *Def2; |
111 | | |
112 | | MuxInfo(MachineBasicBlock::iterator It, unsigned DR, unsigned PR, |
113 | | MachineOperand *TOp, MachineOperand *FOp, MachineInstr &D1, |
114 | | MachineInstr &D2) |
115 | | : At(It), DefR(DR), PredR(PR), SrcT(TOp), SrcF(FOp), Def1(&D1), |
116 | 140 | Def2(&D2) {} |
117 | | }; |
118 | | |
119 | | using InstrIndexMap = DenseMap<MachineInstr *, unsigned>; |
120 | | using DefUseInfoMap = DenseMap<unsigned, DefUseInfo>; |
121 | | using MuxInfoList = SmallVector<MuxInfo, 4>; |
122 | | |
123 | 67.0k | bool isRegPair(unsigned Reg) const { |
124 | 67.0k | return Hexagon::DoubleRegsRegClass.contains(Reg); |
125 | 67.0k | } |
126 | | |
127 | | void getSubRegs(unsigned Reg, BitVector &SRs) const; |
128 | | void expandReg(unsigned Reg, BitVector &Set) const; |
129 | | void getDefsUses(const MachineInstr *MI, BitVector &Defs, |
130 | | BitVector &Uses) const; |
131 | | void buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X, |
132 | | DefUseInfoMap &DUM); |
133 | | bool isCondTransfer(unsigned Opc) const; |
134 | | unsigned getMuxOpcode(const MachineOperand &Src1, |
135 | | const MachineOperand &Src2) const; |
136 | | bool genMuxInBlock(MachineBasicBlock &B); |
137 | | }; |
138 | | |
139 | | } // end anonymous namespace |
140 | | |
141 | | char HexagonGenMux::ID = 0; |
142 | | |
143 | | INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux", |
144 | | "Hexagon generate mux instructions", false, false) |
145 | | |
146 | 4.68k | void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const { |
147 | 14.0k | for (MCSubRegIterator I(Reg, HRI); I.isValid(); ++I9.36k ) |
148 | 9.36k | SRs[*I] = true; |
149 | 4.68k | } |
150 | | |
151 | 66.5k | void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const { |
152 | 66.5k | if (isRegPair(Reg)) |
153 | 4.68k | getSubRegs(Reg, Set); |
154 | 61.8k | else |
155 | 61.8k | Set[Reg] = true; |
156 | 66.5k | } |
157 | | |
158 | | void HexagonGenMux::getDefsUses(const MachineInstr *MI, BitVector &Defs, |
159 | 28.1k | BitVector &Uses) const { |
160 | 28.1k | // First, get the implicit defs and uses for this instruction. |
161 | 28.1k | unsigned Opc = MI->getOpcode(); |
162 | 28.1k | const MCInstrDesc &D = HII->get(Opc); |
163 | 28.1k | if (const MCPhysReg *R = D.ImplicitDefs) |
164 | 13.3k | while (5.84k *R) |
165 | 7.46k | expandReg(*R++, Defs); |
166 | 28.1k | if (const MCPhysReg *R = D.ImplicitUses) |
167 | 5.42k | while (2.15k *R) |
168 | 3.27k | expandReg(*R++, Uses); |
169 | 28.1k | |
170 | 28.1k | // Look over all operands, and collect explicit defs and uses. |
171 | 90.2k | for (const MachineOperand &MO : MI->operands()) { |
172 | 90.2k | if (!MO.isReg() || MO.isImplicit()72.3k ) |
173 | 34.4k | continue; |
174 | 55.7k | unsigned R = MO.getReg(); |
175 | 55.7k | BitVector &Set = MO.isDef() ? Defs20.1k : Uses35.5k ; |
176 | 55.7k | expandReg(R, Set); |
177 | 55.7k | } |
178 | 28.1k | } |
179 | | |
180 | | void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X, |
181 | 5.00k | DefUseInfoMap &DUM) { |
182 | 5.00k | unsigned Index = 0; |
183 | 5.00k | unsigned NR = HRI->getNumRegs(); |
184 | 5.00k | BitVector Defs(NR), Uses(NR); |
185 | 5.00k | |
186 | 33.1k | for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I28.1k ) { |
187 | 28.1k | MachineInstr *MI = &*I; |
188 | 28.1k | I2X.insert(std::make_pair(MI, Index)); |
189 | 28.1k | Defs.reset(); |
190 | 28.1k | Uses.reset(); |
191 | 28.1k | getDefsUses(MI, Defs, Uses); |
192 | 28.1k | DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses))); |
193 | 28.1k | Index++; |
194 | 28.1k | } |
195 | 5.00k | } |
196 | | |
197 | 28.1k | bool HexagonGenMux::isCondTransfer(unsigned Opc) const { |
198 | 28.1k | switch (Opc) { |
199 | 28.1k | case Hexagon::A2_tfrt: |
200 | 510 | case Hexagon::A2_tfrf: |
201 | 510 | case Hexagon::C2_cmoveit: |
202 | 510 | case Hexagon::C2_cmoveif: |
203 | 510 | return true; |
204 | 27.6k | } |
205 | 27.6k | return false; |
206 | 27.6k | } |
207 | | |
208 | | unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1, |
209 | 140 | const MachineOperand &Src2) const { |
210 | 140 | bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg(); |
211 | 140 | if (IsReg1) |
212 | 59 | return IsReg2 ? Hexagon::C2_mux12 : Hexagon::C2_muxir47 ; |
213 | 81 | if (IsReg2) |
214 | 11 | return Hexagon::C2_muxri; |
215 | 70 | |
216 | 70 | // Neither is a register. The first source is extendable, but the second |
217 | 70 | // is not (s8). |
218 | 70 | if (Src2.isImm() && isInt<8>(Src2.getImm())) |
219 | 66 | return Hexagon::C2_muxii; |
220 | 4 | |
221 | 4 | return 0; |
222 | 4 | } |
223 | | |
224 | 5.00k | bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) { |
225 | 5.00k | bool Changed = false; |
226 | 5.00k | InstrIndexMap I2X; |
227 | 5.00k | DefUseInfoMap DUM; |
228 | 5.00k | buildMaps(B, I2X, DUM); |
229 | 5.00k | |
230 | 5.00k | using CondsetMap = DenseMap<unsigned, CondsetInfo>; |
231 | 5.00k | |
232 | 5.00k | CondsetMap CM; |
233 | 5.00k | MuxInfoList ML; |
234 | 5.00k | |
235 | 5.00k | MachineBasicBlock::iterator NextI, End = B.end(); |
236 | 33.1k | for (MachineBasicBlock::iterator I = B.begin(); I != End; I = NextI28.1k ) { |
237 | 28.1k | MachineInstr *MI = &*I; |
238 | 28.1k | NextI = std::next(I); |
239 | 28.1k | unsigned Opc = MI->getOpcode(); |
240 | 28.1k | if (!isCondTransfer(Opc)) |
241 | 27.6k | continue; |
242 | 510 | unsigned DR = MI->getOperand(0).getReg(); |
243 | 510 | if (isRegPair(DR)) |
244 | 0 | continue; |
245 | 510 | MachineOperand &PredOp = MI->getOperand(1); |
246 | 510 | if (PredOp.isUndef()) |
247 | 3 | continue; |
248 | 507 | |
249 | 507 | unsigned PR = PredOp.getReg(); |
250 | 507 | unsigned Idx = I2X.lookup(MI); |
251 | 507 | CondsetMap::iterator F = CM.find(DR); |
252 | 507 | bool IfTrue = HII->isPredicatedTrue(Opc); |
253 | 507 | |
254 | 507 | // If there is no record of a conditional transfer for this register, |
255 | 507 | // or the predicate register differs, create a new record for it. |
256 | 507 | if (F != CM.end() && F->second.PredR != PR262 ) { |
257 | 69 | CM.erase(F); |
258 | 69 | F = CM.end(); |
259 | 69 | } |
260 | 507 | if (F == CM.end()) { |
261 | 314 | auto It = CM.insert(std::make_pair(DR, CondsetInfo())); |
262 | 314 | F = It.first; |
263 | 314 | F->second.PredR = PR; |
264 | 314 | } |
265 | 507 | CondsetInfo &CI = F->second; |
266 | 507 | if (IfTrue) |
267 | 227 | CI.TrueX = Idx; |
268 | 280 | else |
269 | 280 | CI.FalseX = Idx; |
270 | 507 | if (CI.TrueX == std::numeric_limits<unsigned>::max() || |
271 | 507 | CI.FalseX == std::numeric_limits<unsigned>::max()396 ) |
272 | 318 | continue; |
273 | 189 | |
274 | 189 | // There is now a complete definition of DR, i.e. we have the predicate |
275 | 189 | // register, the definition if-true, and definition if-false. |
276 | 189 | |
277 | 189 | // First, check if the definitions are far enough from the definition |
278 | 189 | // of the predicate register. |
279 | 189 | unsigned MinX = std::min(CI.TrueX, CI.FalseX); |
280 | 189 | unsigned MaxX = std::max(CI.TrueX, CI.FalseX); |
281 | 189 | // Specifically, check if the predicate definition is within a prescribed |
282 | 189 | // distance from the farther of the two predicated instructions. |
283 | 189 | unsigned SearchX = (MaxX >= MinPredDist) ? MaxX-MinPredDist168 : 021 ; |
284 | 189 | bool NearDef = false; |
285 | 193 | for (unsigned X = SearchX; X < MaxX; ++X4 ) { |
286 | 25 | const DefUseInfo &DU = DUM.lookup(X); |
287 | 25 | if (!DU.Defs[PR]) |
288 | 4 | continue; |
289 | 21 | NearDef = true; |
290 | 21 | break; |
291 | 21 | } |
292 | 189 | if (NearDef) |
293 | 21 | continue; |
294 | 168 | |
295 | 168 | // The predicate register is not defined in the last few instructions. |
296 | 168 | // Check if the conversion to MUX is possible (either "up", i.e. at the |
297 | 168 | // place of the earlier partial definition, or "down", where the later |
298 | 168 | // definition is located). Examine all defs and uses between these two |
299 | 168 | // definitions. |
300 | 168 | // SR1, SR2 - source registers from the first and the second definition. |
301 | 168 | MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin(); |
302 | 168 | std::advance(It1, MinX); |
303 | 168 | std::advance(It2, MaxX); |
304 | 168 | MachineInstr &Def1 = *It1, &Def2 = *It2; |
305 | 168 | MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2); |
306 | 168 | Register SR1 = Src1->isReg() ? Src1->getReg()62 : Register()106 ; |
307 | 168 | Register SR2 = Src2->isReg() ? Src2->getReg()38 : Register()130 ; |
308 | 168 | bool Failure = false, CanUp = true, CanDown = true; |
309 | 437 | for (unsigned X = MinX+1; X < MaxX; X++269 ) { |
310 | 296 | const DefUseInfo &DU = DUM.lookup(X); |
311 | 296 | if (DU.Defs[PR] || DU.Defs[DR]284 || DU.Uses[DR]277 ) { |
312 | 27 | Failure = true; |
313 | 27 | break; |
314 | 27 | } |
315 | 269 | if (CanDown && DU.Defs[SR1]265 ) |
316 | 10 | CanDown = false; |
317 | 269 | if (CanUp && DU.Defs[SR2]265 ) |
318 | 3 | CanUp = false; |
319 | 269 | } |
320 | 168 | if (Failure || (141 !CanUp141 && !CanDown1 )) |
321 | 28 | continue; |
322 | 140 | |
323 | 140 | MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src20 ; |
324 | 140 | MachineOperand *SrcF = (MinX == CI.FalseX) ? Src10 : Src2; |
325 | 140 | // Prefer "down", since this will move the MUX farther away from the |
326 | 140 | // predicate definition. |
327 | 140 | MachineBasicBlock::iterator At = CanDown ? Def2131 : Def19 ; |
328 | 140 | ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2)); |
329 | 140 | } |
330 | 5.00k | |
331 | 5.00k | for (MuxInfo &MX : ML) { |
332 | 140 | unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF); |
333 | 140 | if (!MxOpc) |
334 | 4 | continue; |
335 | 136 | MachineBasicBlock &B = *MX.At->getParent(); |
336 | 136 | const DebugLoc &DL = B.findDebugLoc(MX.At); |
337 | 136 | auto NewMux = BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR) |
338 | 136 | .addReg(MX.PredR) |
339 | 136 | .add(*MX.SrcT) |
340 | 136 | .add(*MX.SrcF); |
341 | 136 | NewMux->clearKillInfo(); |
342 | 136 | B.erase(MX.Def1); |
343 | 136 | B.erase(MX.Def2); |
344 | 136 | Changed = true; |
345 | 136 | } |
346 | 5.00k | |
347 | 5.00k | // Fix up kill flags. |
348 | 5.00k | |
349 | 5.00k | LivePhysRegs LPR(*HRI); |
350 | 5.00k | LPR.addLiveOuts(B); |
351 | 42.7k | auto IsLive = [&LPR,this] (unsigned Reg) -> bool { |
352 | 71.6k | for (MCSubRegIterator S(Reg, HRI, true); S.isValid(); ++S28.8k ) |
353 | 48.8k | if (LPR.contains(*S)) |
354 | 20.0k | return true; |
355 | 42.7k | return false22.7k ; |
356 | 42.7k | }; |
357 | 33.0k | for (auto I = B.rbegin(), E = B.rend(); I != E; ++I28.0k ) { |
358 | 28.0k | if (I->isDebugInstr()) |
359 | 21 | continue; |
360 | 27.9k | // This isn't 100% accurate, but it's safe. |
361 | 27.9k | // It won't detect (as a kill) a case like this |
362 | 27.9k | // r0 = add r0, 1 <-- r0 should be "killed" |
363 | 27.9k | // ... = r0 |
364 | 89.7k | for (MachineOperand &Op : I->operands())27.9k { |
365 | 89.7k | if (!Op.isReg() || !Op.isUse()71.9k ) |
366 | 46.9k | continue; |
367 | 42.7k | assert(Op.getSubReg() == 0 && "Should have physical registers only"); |
368 | 42.7k | bool Live = IsLive(Op.getReg()); |
369 | 42.7k | Op.setIsKill(!Live); |
370 | 42.7k | } |
371 | 27.9k | LPR.stepBackward(*I); |
372 | 27.9k | } |
373 | 5.00k | |
374 | 5.00k | return Changed; |
375 | 5.00k | } |
376 | | |
377 | 3.36k | bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) { |
378 | 3.36k | if (skipFunction(MF.getFunction())) |
379 | 10 | return false; |
380 | 3.35k | HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); |
381 | 3.35k | HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo(); |
382 | 3.35k | bool Changed = false; |
383 | 3.35k | for (auto &I : MF) |
384 | 5.00k | Changed |= genMuxInBlock(I); |
385 | 3.35k | return Changed; |
386 | 3.35k | } |
387 | | |
388 | 862 | FunctionPass *llvm::createHexagonGenMux() { |
389 | 862 | return new HexagonGenMux(); |
390 | 862 | } |