/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/X86/X86FixupBWInsts.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- X86FixupBWInsts.cpp - Fixup Byte or Word instructions -----------===// |
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 | | /// \file |
10 | | /// This file defines the pass that looks through the machine instructions |
11 | | /// late in the compilation, and finds byte or word instructions that |
12 | | /// can be profitably replaced with 32 bit instructions that give equivalent |
13 | | /// results for the bits of the results that are used. There are two possible |
14 | | /// reasons to do this. |
15 | | /// |
16 | | /// One reason is to avoid false-dependences on the upper portions |
17 | | /// of the registers. Only instructions that have a destination register |
18 | | /// which is not in any of the source registers can be affected by this. |
19 | | /// Any instruction where one of the source registers is also the destination |
20 | | /// register is unaffected, because it has a true dependence on the source |
21 | | /// register already. So, this consideration primarily affects load |
22 | | /// instructions and register-to-register moves. It would |
23 | | /// seem like cmov(s) would also be affected, but because of the way cmov is |
24 | | /// really implemented by most machines as reading both the destination and |
25 | | /// and source registers, and then "merging" the two based on a condition, |
26 | | /// it really already should be considered as having a true dependence on the |
27 | | /// destination register as well. |
28 | | /// |
29 | | /// The other reason to do this is for potential code size savings. Word |
30 | | /// operations need an extra override byte compared to their 32 bit |
31 | | /// versions. So this can convert many word operations to their larger |
32 | | /// size, saving a byte in encoding. This could introduce partial register |
33 | | /// dependences where none existed however. As an example take: |
34 | | /// orw ax, $0x1000 |
35 | | /// addw ax, $3 |
36 | | /// now if this were to get transformed into |
37 | | /// orw ax, $1000 |
38 | | /// addl eax, $3 |
39 | | /// because the addl encodes shorter than the addw, this would introduce |
40 | | /// a use of a register that was only partially written earlier. On older |
41 | | /// Intel processors this can be quite a performance penalty, so this should |
42 | | /// probably only be done when it can be proven that a new partial dependence |
43 | | /// wouldn't be created, or when your know a newer processor is being |
44 | | /// targeted, or when optimizing for minimum code size. |
45 | | /// |
46 | | //===----------------------------------------------------------------------===// |
47 | | |
48 | | #include "X86.h" |
49 | | #include "X86InstrInfo.h" |
50 | | #include "X86Subtarget.h" |
51 | | #include "llvm/ADT/Statistic.h" |
52 | | #include "llvm/CodeGen/LivePhysRegs.h" |
53 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
54 | | #include "llvm/CodeGen/MachineInstrBuilder.h" |
55 | | #include "llvm/CodeGen/MachineLoopInfo.h" |
56 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
57 | | #include "llvm/CodeGen/Passes.h" |
58 | | #include "llvm/Support/Debug.h" |
59 | | #include "llvm/Support/raw_ostream.h" |
60 | | #include "llvm/Target/TargetInstrInfo.h" |
61 | | using namespace llvm; |
62 | | |
63 | 7.88k | #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup" |
64 | | #define FIXUPBW_NAME "x86-fixup-bw-insts" |
65 | | |
66 | | #define DEBUG_TYPE FIXUPBW_NAME |
67 | | |
68 | | // Option to allow this optimization pass to have fine-grained control. |
69 | | static cl::opt<bool> |
70 | | FixupBWInsts("fixup-byte-word-insts", |
71 | | cl::desc("Change byte and word instructions to larger sizes"), |
72 | | cl::init(true), cl::Hidden); |
73 | | |
74 | | namespace { |
75 | | class FixupBWInstPass : public MachineFunctionPass { |
76 | | /// Loop over all of the instructions in the basic block replacing applicable |
77 | | /// byte or word instructions with better alternatives. |
78 | | void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB); |
79 | | |
80 | | /// This sets the \p SuperDestReg to the 32 bit super reg of the original |
81 | | /// destination register of the MachineInstr passed in. It returns true if |
82 | | /// that super register is dead just prior to \p OrigMI, and false if not. |
83 | | bool getSuperRegDestIfDead(MachineInstr *OrigMI, |
84 | | unsigned &SuperDestReg) const; |
85 | | |
86 | | /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit |
87 | | /// register if it is safe to do so. Return the replacement instruction if |
88 | | /// OK, otherwise return nullptr. |
89 | | MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const; |
90 | | |
91 | | /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is |
92 | | /// safe to do so. Return the replacement instruction if OK, otherwise return |
93 | | /// nullptr. |
94 | | MachineInstr *tryReplaceCopy(MachineInstr *MI) const; |
95 | | |
96 | | // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if |
97 | | // possible. Return the replacement instruction if OK, return nullptr |
98 | | // otherwise. |
99 | | MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const; |
100 | | |
101 | | public: |
102 | | static char ID; |
103 | | |
104 | 7.88k | StringRef getPassName() const override { return 7.88k FIXUPBW_DESC7.88k ; } |
105 | | |
106 | 7.89k | FixupBWInstPass() : MachineFunctionPass(ID) { |
107 | 7.89k | initializeFixupBWInstPassPass(*PassRegistry::getPassRegistry()); |
108 | 7.89k | } |
109 | | |
110 | 7.87k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
111 | 7.87k | AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to |
112 | 7.87k | // guide some heuristics. |
113 | 7.87k | MachineFunctionPass::getAnalysisUsage(AU); |
114 | 7.87k | } |
115 | | |
116 | | /// Loop over all of the basic blocks, replacing byte and word instructions by |
117 | | /// equivalent 32 bit instructions where performance or code size can be |
118 | | /// improved. |
119 | | bool runOnMachineFunction(MachineFunction &MF) override; |
120 | | |
121 | 7.87k | MachineFunctionProperties getRequiredProperties() const override { |
122 | 7.87k | return MachineFunctionProperties().set( |
123 | 7.87k | MachineFunctionProperties::Property::NoVRegs); |
124 | 7.87k | } |
125 | | |
126 | | private: |
127 | | MachineFunction *MF; |
128 | | |
129 | | /// Machine instruction info used throughout the class. |
130 | | const X86InstrInfo *TII; |
131 | | |
132 | | /// Local member for function's OptForSize attribute. |
133 | | bool OptForSize; |
134 | | |
135 | | /// Machine loop info used for guiding some heruistics. |
136 | | MachineLoopInfo *MLI; |
137 | | |
138 | | /// Register Liveness information after the current instruction. |
139 | | LivePhysRegs LiveRegs; |
140 | | }; |
141 | | char FixupBWInstPass::ID = 0; |
142 | | } |
143 | | |
144 | | INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false) |
145 | | |
146 | 7.89k | FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); } |
147 | | |
148 | 70.8k | bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) { |
149 | 70.8k | if (!FixupBWInsts || 70.8k skipFunction(*MF.getFunction())70.7k ) |
150 | 127 | return false; |
151 | 70.7k | |
152 | 70.7k | this->MF = &MF; |
153 | 70.7k | TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); |
154 | 70.7k | OptForSize = MF.getFunction()->optForSize(); |
155 | 70.7k | MLI = &getAnalysis<MachineLoopInfo>(); |
156 | 70.7k | LiveRegs.init(TII->getRegisterInfo()); |
157 | 70.7k | |
158 | 70.7k | DEBUG(dbgs() << "Start X86FixupBWInsts\n";); |
159 | 70.7k | |
160 | 70.7k | // Process all basic blocks. |
161 | 70.7k | for (auto &MBB : MF) |
162 | 132k | processBasicBlock(MF, MBB); |
163 | 70.7k | |
164 | 70.7k | DEBUG(dbgs() << "End X86FixupBWInsts\n";); |
165 | 70.8k | |
166 | 70.8k | return true; |
167 | 70.8k | } |
168 | | |
169 | | /// Check if register \p Reg is live after the \p MI. |
170 | | /// |
171 | | /// \p LiveRegs should be in a state describing liveness information in |
172 | | /// that exact place as this function tries to precise analysis made |
173 | | /// by \p LiveRegs by exploiting the information about particular |
174 | | /// instruction \p MI. \p MI is expected to be one of the MOVs handled |
175 | | /// by the x86FixupBWInsts pass. |
176 | | /// Note: similar to LivePhysRegs::contains this would state that |
177 | | /// super-register is not used if only some part of it is used. |
178 | | /// |
179 | | /// X86 backend does not have subregister liveness tracking enabled, |
180 | | /// so liveness information might be overly conservative. However, for |
181 | | /// some specific instructions (this pass only cares about MOVs) we can |
182 | | /// produce more precise results by analysing that MOV's operands. |
183 | | /// |
184 | | /// Indeed, if super-register is not live before the mov it means that it |
185 | | /// was originally <read-undef> and so we are free to modify these |
186 | | /// undef upper bits. That may happen in case where the use is in another MBB |
187 | | /// and the vreg/physreg corresponding to the move has higher width than |
188 | | /// necessary (e.g. due to register coalescing with a "truncate" copy). |
189 | | /// So, it handles pattern like this: |
190 | | /// |
191 | | /// BB#2: derived from LLVM BB %if.then |
192 | | /// Live Ins: %RDI |
193 | | /// Predecessors according to CFG: BB#0 |
194 | | /// %AX<def> = MOV16rm %RDI<kill>, 1, %noreg, 0, %noreg, %EAX<imp-def>; mem:LD2[%p] |
195 | | /// No %EAX<imp-use> |
196 | | /// Successors according to CFG: BB#3(?%) |
197 | | /// |
198 | | /// BB#3: derived from LLVM BB %if.end |
199 | | /// Live Ins: %EAX Only %AX is actually live |
200 | | /// Predecessors according to CFG: BB#2 BB#1 |
201 | | /// %AX<def> = KILL %AX, %EAX<imp-use,kill> |
202 | | /// RET 0, %AX |
203 | | static bool isLive(const MachineInstr &MI, |
204 | | const LivePhysRegs &LiveRegs, |
205 | | const TargetRegisterInfo *TRI, |
206 | 6.43k | unsigned Reg) { |
207 | 6.43k | if (!LiveRegs.contains(Reg)) |
208 | 5.52k | return false; |
209 | 910 | |
210 | 910 | unsigned Opc = MI.getOpcode(); (void)Opc; |
211 | 910 | // These are the opcodes currently handled by the pass, if something |
212 | 910 | // else will be added we need to ensure that new opcode has the same |
213 | 910 | // properties. |
214 | 910 | assert((Opc == X86::MOV8rm || Opc == X86::MOV16rm || Opc == X86::MOV8rr || |
215 | 910 | Opc == X86::MOV16rr) && |
216 | 910 | "Unexpected opcode."); |
217 | 910 | |
218 | 910 | bool IsDefined = false; |
219 | 899 | for (auto &MO: MI.implicit_operands()) { |
220 | 899 | if (!MO.isReg()) |
221 | 0 | continue; |
222 | 899 | |
223 | 899 | assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!"); |
224 | 899 | |
225 | 2.93k | for (MCSuperRegIterator Supers(Reg, TRI, true); Supers.isValid()2.93k ; ++Supers2.03k ) { |
226 | 2.08k | if (*Supers == MO.getReg()2.08k ) { |
227 | 843 | if (MO.isDef()) |
228 | 792 | IsDefined = true; |
229 | 843 | else |
230 | 51 | return true; // SuperReg Imp-used' -> live before the MI |
231 | 843 | } |
232 | 2.08k | } |
233 | 899 | } |
234 | 910 | // Reg is not Imp-def'ed -> it's live both before/after the instruction. |
235 | 859 | if (859 !IsDefined859 ) |
236 | 67 | return true; |
237 | 792 | |
238 | 792 | // Otherwise, the Reg is not live before the MI and the MOV can't |
239 | 792 | // make it really live, so it's in fact dead even after the MI. |
240 | 792 | return false; |
241 | 792 | } |
242 | | |
243 | | /// \brief Check if after \p OrigMI the only portion of super register |
244 | | /// of the destination register of \p OrigMI that is alive is that |
245 | | /// destination register. |
246 | | /// |
247 | | /// If so, return that super register in \p SuperDestReg. |
248 | | bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI, |
249 | 3.91k | unsigned &SuperDestReg) const { |
250 | 3.91k | auto *TRI = &TII->getRegisterInfo(); |
251 | 3.91k | |
252 | 3.91k | unsigned OrigDestReg = OrigMI->getOperand(0).getReg(); |
253 | 3.91k | SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32); |
254 | 3.91k | |
255 | 3.91k | const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg); |
256 | 3.91k | |
257 | 3.91k | // Make sure that the sub-register that this instruction has as its |
258 | 3.91k | // destination is the lowest order sub-register of the super-register. |
259 | 3.91k | // If it isn't, then the register isn't really dead even if the |
260 | 3.91k | // super-register is considered dead. |
261 | 3.91k | if (SubRegIdx == X86::sub_8bit_hi) |
262 | 73 | return false; |
263 | 3.83k | |
264 | 3.83k | if (3.83k isLive(*OrigMI, LiveRegs, TRI, SuperDestReg)3.83k ) |
265 | 51 | return false; |
266 | 3.78k | |
267 | 3.78k | if (3.78k SubRegIdx == X86::sub_8bit3.78k ) { |
268 | 2.60k | // In the case of byte registers, we also have to check that the upper |
269 | 2.60k | // byte register is also dead. That is considered to be independent of |
270 | 2.60k | // whether the super-register is dead. |
271 | 2.60k | unsigned UpperByteReg = |
272 | 2.60k | getX86SubSuperRegister(SuperDestReg, 8, /*High=*/true); |
273 | 2.60k | |
274 | 2.60k | if (isLive(*OrigMI, LiveRegs, TRI, UpperByteReg)) |
275 | 67 | return false; |
276 | 3.71k | } |
277 | 3.71k | |
278 | 3.71k | return true; |
279 | 3.71k | } |
280 | | |
281 | | MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode, |
282 | 1.71k | MachineInstr *MI) const { |
283 | 1.71k | unsigned NewDestReg; |
284 | 1.71k | |
285 | 1.71k | // We are going to try to rewrite this load to a larger zero-extending |
286 | 1.71k | // load. This is safe if all portions of the 32 bit super-register |
287 | 1.71k | // of the original destination register, except for the original destination |
288 | 1.71k | // register are dead. getSuperRegDestIfDead checks that. |
289 | 1.71k | if (!getSuperRegDestIfDead(MI, NewDestReg)) |
290 | 8 | return nullptr; |
291 | 1.71k | |
292 | 1.71k | // Safe to change the instruction. |
293 | 1.71k | MachineInstrBuilder MIB = |
294 | 1.71k | BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg); |
295 | 1.71k | |
296 | 1.71k | unsigned NumArgs = MI->getNumOperands(); |
297 | 10.6k | for (unsigned i = 1; i < NumArgs10.6k ; ++i8.89k ) |
298 | 8.89k | MIB.add(MI->getOperand(i)); |
299 | 1.71k | |
300 | 1.71k | MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end()); |
301 | 1.71k | |
302 | 1.71k | return MIB; |
303 | 1.71k | } |
304 | | |
305 | 2.19k | MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const { |
306 | 2.19k | assert(MI->getNumExplicitOperands() == 2); |
307 | 2.19k | auto &OldDest = MI->getOperand(0); |
308 | 2.19k | auto &OldSrc = MI->getOperand(1); |
309 | 2.19k | |
310 | 2.19k | unsigned NewDestReg; |
311 | 2.19k | if (!getSuperRegDestIfDead(MI, NewDestReg)) |
312 | 183 | return nullptr; |
313 | 2.00k | |
314 | 2.00k | unsigned NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32); |
315 | 2.00k | |
316 | 2.00k | // This is only correct if we access the same subregister index: otherwise, |
317 | 2.00k | // we could try to replace "movb %ah, %al" with "movl %eax, %eax". |
318 | 2.00k | auto *TRI = &TII->getRegisterInfo(); |
319 | 2.00k | if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) != |
320 | 2.00k | TRI->getSubRegIndex(NewDestReg, OldDest.getReg())) |
321 | 30 | return nullptr; |
322 | 1.97k | |
323 | 1.97k | // Safe to change the instruction. |
324 | 1.97k | // Don't set src flags, as we don't know if we're also killing the superreg. |
325 | 1.97k | // However, the superregister might not be defined; make it explicit that |
326 | 1.97k | // we don't care about the higher bits by reading it as Undef, and adding |
327 | 1.97k | // an imp-use on the original subregister. |
328 | 1.97k | MachineInstrBuilder MIB = |
329 | 1.97k | BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg) |
330 | 1.97k | .addReg(NewSrcReg, RegState::Undef) |
331 | 1.97k | .addReg(OldSrc.getReg(), RegState::Implicit); |
332 | 1.97k | |
333 | 1.97k | // Drop imp-defs/uses that would be redundant with the new def/use. |
334 | 1.97k | for (auto &Op : MI->implicit_operands()) |
335 | 820 | if (820 Op.getReg() != (Op.isDef() ? 820 NewDestReg264 : NewSrcReg556 )) |
336 | 101 | MIB.add(Op); |
337 | 2.19k | |
338 | 2.19k | return MIB; |
339 | 2.19k | } |
340 | | |
341 | | MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI, |
342 | 878k | MachineBasicBlock &MBB) const { |
343 | 878k | // See if this is an instruction of the type we are currently looking for. |
344 | 878k | switch (MI->getOpcode()) { |
345 | 878k | |
346 | 3.24k | case X86::MOV8rm: |
347 | 3.24k | // Only replace 8 bit loads with the zero extending versions if |
348 | 3.24k | // in an inner most loop and not optimizing for size. This takes |
349 | 3.24k | // an extra byte to encode, and provides limited performance upside. |
350 | 3.24k | if (MachineLoop *ML = MLI->getLoopFor(&MBB)) |
351 | 922 | if (922 ML->begin() == ML->end() && 922 !OptForSize802 ) |
352 | 802 | return tryReplaceLoad(X86::MOVZX32rm8, MI); |
353 | 2.44k | break; |
354 | 2.44k | |
355 | 917 | case X86::MOV16rm: |
356 | 917 | // Always try to replace 16 bit load with 32 bit zero extending. |
357 | 917 | // Code size is the same, and there is sometimes a perf advantage |
358 | 917 | // from eliminating a false dependence on the upper portion of |
359 | 917 | // the register. |
360 | 917 | return tryReplaceLoad(X86::MOVZX32rm16, MI); |
361 | 2.44k | |
362 | 2.19k | case X86::MOV8rr: |
363 | 2.19k | case X86::MOV16rr: |
364 | 2.19k | // Always try to replace 8/16 bit copies with a 32 bit copy. |
365 | 2.19k | // Code size is either less (16) or equal (8), and there is sometimes a |
366 | 2.19k | // perf advantage from eliminating a false dependence on the upper portion |
367 | 2.19k | // of the register. |
368 | 2.19k | return tryReplaceCopy(MI); |
369 | 2.19k | |
370 | 872k | default: |
371 | 872k | // nothing to do here. |
372 | 872k | break; |
373 | 874k | } |
374 | 874k | |
375 | 874k | return nullptr; |
376 | 874k | } |
377 | | |
378 | | void FixupBWInstPass::processBasicBlock(MachineFunction &MF, |
379 | 132k | MachineBasicBlock &MBB) { |
380 | 132k | |
381 | 132k | // This algorithm doesn't delete the instructions it is replacing |
382 | 132k | // right away. By leaving the existing instructions in place, the |
383 | 132k | // register liveness information doesn't change, and this makes the |
384 | 132k | // analysis that goes on be better than if the replaced instructions |
385 | 132k | // were immediately removed. |
386 | 132k | // |
387 | 132k | // This algorithm always creates a replacement instruction |
388 | 132k | // and notes that and the original in a data structure, until the |
389 | 132k | // whole BB has been analyzed. This keeps the replacement instructions |
390 | 132k | // from making it seem as if the larger register might be live. |
391 | 132k | SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements; |
392 | 132k | |
393 | 132k | // Start computing liveness for this block. We iterate from the end to be able |
394 | 132k | // to update this for each instruction. |
395 | 132k | LiveRegs.clear(); |
396 | 132k | // We run after PEI, so we need to AddPristinesAndCSRs. |
397 | 132k | LiveRegs.addLiveOuts(MBB); |
398 | 132k | |
399 | 1.01M | for (auto I = MBB.rbegin(); I != MBB.rend()1.01M ; ++I878k ) { |
400 | 878k | MachineInstr *MI = &*I; |
401 | 878k | |
402 | 878k | if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB)) |
403 | 3.68k | MIReplacements.push_back(std::make_pair(MI, NewMI)); |
404 | 878k | |
405 | 878k | // We're done with this instruction, update liveness for the next one. |
406 | 878k | LiveRegs.stepBackward(*MI); |
407 | 878k | } |
408 | 132k | |
409 | 136k | while (!MIReplacements.empty()136k ) { |
410 | 3.68k | MachineInstr *MI = MIReplacements.back().first; |
411 | 3.68k | MachineInstr *NewMI = MIReplacements.back().second; |
412 | 3.68k | MIReplacements.pop_back(); |
413 | 3.68k | MBB.insert(MI, NewMI); |
414 | 3.68k | MBB.erase(MI); |
415 | 3.68k | } |
416 | 132k | } |