[ARM] MVE integer min and max
[llvm-complete.git] / lib / Target / X86 / X86FixupBWInsts.cpp
blobbf541d933790913c0050c05a20f8b11ea39312ed
1 //===-- X86FixupBWInsts.cpp - Fixup Byte or Word instructions -----------===//
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 /// \file
9 /// This file defines the pass that looks through the machine instructions
10 /// late in the compilation, and finds byte or word instructions that
11 /// can be profitably replaced with 32 bit instructions that give equivalent
12 /// results for the bits of the results that are used. There are two possible
13 /// reasons to do this.
14 ///
15 /// One reason is to avoid false-dependences on the upper portions
16 /// of the registers. Only instructions that have a destination register
17 /// which is not in any of the source registers can be affected by this.
18 /// Any instruction where one of the source registers is also the destination
19 /// register is unaffected, because it has a true dependence on the source
20 /// register already. So, this consideration primarily affects load
21 /// instructions and register-to-register moves. It would
22 /// seem like cmov(s) would also be affected, but because of the way cmov is
23 /// really implemented by most machines as reading both the destination and
24 /// and source registers, and then "merging" the two based on a condition,
25 /// it really already should be considered as having a true dependence on the
26 /// destination register as well.
27 ///
28 /// The other reason to do this is for potential code size savings. Word
29 /// operations need an extra override byte compared to their 32 bit
30 /// versions. So this can convert many word operations to their larger
31 /// size, saving a byte in encoding. This could introduce partial register
32 /// dependences where none existed however. As an example take:
33 /// orw ax, $0x1000
34 /// addw ax, $3
35 /// now if this were to get transformed into
36 /// orw ax, $1000
37 /// addl eax, $3
38 /// because the addl encodes shorter than the addw, this would introduce
39 /// a use of a register that was only partially written earlier. On older
40 /// Intel processors this can be quite a performance penalty, so this should
41 /// probably only be done when it can be proven that a new partial dependence
42 /// wouldn't be created, or when your know a newer processor is being
43 /// targeted, or when optimizing for minimum code size.
44 ///
45 //===----------------------------------------------------------------------===//
47 #include "X86.h"
48 #include "X86InstrInfo.h"
49 #include "X86Subtarget.h"
50 #include "llvm/ADT/Statistic.h"
51 #include "llvm/CodeGen/LivePhysRegs.h"
52 #include "llvm/CodeGen/MachineFunctionPass.h"
53 #include "llvm/CodeGen/MachineInstrBuilder.h"
54 #include "llvm/CodeGen/MachineLoopInfo.h"
55 #include "llvm/CodeGen/MachineRegisterInfo.h"
56 #include "llvm/CodeGen/Passes.h"
57 #include "llvm/CodeGen/TargetInstrInfo.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/raw_ostream.h"
60 using namespace llvm;
62 #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup"
63 #define FIXUPBW_NAME "x86-fixup-bw-insts"
65 #define DEBUG_TYPE FIXUPBW_NAME
67 // Option to allow this optimization pass to have fine-grained control.
68 static cl::opt<bool>
69 FixupBWInsts("fixup-byte-word-insts",
70 cl::desc("Change byte and word instructions to larger sizes"),
71 cl::init(true), cl::Hidden);
73 namespace {
74 class FixupBWInstPass : public MachineFunctionPass {
75 /// Loop over all of the instructions in the basic block replacing applicable
76 /// byte or word instructions with better alternatives.
77 void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);
79 /// This sets the \p SuperDestReg to the 32 bit super reg of the original
80 /// destination register of the MachineInstr passed in. It returns true if
81 /// that super register is dead just prior to \p OrigMI, and false if not.
82 bool getSuperRegDestIfDead(MachineInstr *OrigMI,
83 unsigned &SuperDestReg) const;
85 /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit
86 /// register if it is safe to do so. Return the replacement instruction if
87 /// OK, otherwise return nullptr.
88 MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const;
90 /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is
91 /// safe to do so. Return the replacement instruction if OK, otherwise return
92 /// nullptr.
93 MachineInstr *tryReplaceCopy(MachineInstr *MI) const;
95 // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if
96 // possible. Return the replacement instruction if OK, return nullptr
97 // otherwise.
98 MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const;
100 public:
101 static char ID;
103 StringRef getPassName() const override { return FIXUPBW_DESC; }
105 FixupBWInstPass() : MachineFunctionPass(ID) { }
107 void getAnalysisUsage(AnalysisUsage &AU) const override {
108 AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to
109 // guide some heuristics.
110 MachineFunctionPass::getAnalysisUsage(AU);
113 /// Loop over all of the basic blocks, replacing byte and word instructions by
114 /// equivalent 32 bit instructions where performance or code size can be
115 /// improved.
116 bool runOnMachineFunction(MachineFunction &MF) override;
118 MachineFunctionProperties getRequiredProperties() const override {
119 return MachineFunctionProperties().set(
120 MachineFunctionProperties::Property::NoVRegs);
123 private:
124 MachineFunction *MF;
126 /// Machine instruction info used throughout the class.
127 const X86InstrInfo *TII;
129 /// Local member for function's OptForSize attribute.
130 bool OptForSize;
132 /// Machine loop info used for guiding some heruistics.
133 MachineLoopInfo *MLI;
135 /// Register Liveness information after the current instruction.
136 LivePhysRegs LiveRegs;
138 char FixupBWInstPass::ID = 0;
141 INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false)
143 FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }
145 bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) {
146 if (!FixupBWInsts || skipFunction(MF.getFunction()))
147 return false;
149 this->MF = &MF;
150 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
151 OptForSize = MF.getFunction().hasOptSize();
152 MLI = &getAnalysis<MachineLoopInfo>();
153 LiveRegs.init(TII->getRegisterInfo());
155 LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n";);
157 // Process all basic blocks.
158 for (auto &MBB : MF)
159 processBasicBlock(MF, MBB);
161 LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n";);
163 return true;
166 /// Check if after \p OrigMI the only portion of super register
167 /// of the destination register of \p OrigMI that is alive is that
168 /// destination register.
170 /// If so, return that super register in \p SuperDestReg.
171 bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI,
172 unsigned &SuperDestReg) const {
173 auto *TRI = &TII->getRegisterInfo();
175 unsigned OrigDestReg = OrigMI->getOperand(0).getReg();
176 SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32);
178 const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg);
180 // Make sure that the sub-register that this instruction has as its
181 // destination is the lowest order sub-register of the super-register.
182 // If it isn't, then the register isn't really dead even if the
183 // super-register is considered dead.
184 if (SubRegIdx == X86::sub_8bit_hi)
185 return false;
187 // If neither the destination-super register nor any applicable subregisters
188 // are live after this instruction, then the super register is safe to use.
189 if (!LiveRegs.contains(SuperDestReg)) {
190 // If the original destination register was not the low 8-bit subregister
191 // then the super register check is sufficient.
192 if (SubRegIdx != X86::sub_8bit)
193 return true;
194 // If the original destination register was the low 8-bit subregister and
195 // we also need to check the 16-bit subregister and the high 8-bit
196 // subregister.
197 if (!LiveRegs.contains(getX86SubSuperRegister(OrigDestReg, 16)) &&
198 !LiveRegs.contains(getX86SubSuperRegister(SuperDestReg, 8,
199 /*High=*/true)))
200 return true;
201 // Otherwise, we have a little more checking to do.
204 // If we get here, the super-register destination (or some part of it) is
205 // marked as live after the original instruction.
207 // The X86 backend does not have subregister liveness tracking enabled,
208 // so liveness information might be overly conservative. Specifically, the
209 // super register might be marked as live because it is implicitly defined
210 // by the instruction we are examining.
212 // However, for some specific instructions (this pass only cares about MOVs)
213 // we can produce more precise results by analysing that MOV's operands.
215 // Indeed, if super-register is not live before the mov it means that it
216 // was originally <read-undef> and so we are free to modify these
217 // undef upper bits. That may happen in case where the use is in another MBB
218 // and the vreg/physreg corresponding to the move has higher width than
219 // necessary (e.g. due to register coalescing with a "truncate" copy).
220 // So, we would like to handle patterns like this:
222 // %bb.2: derived from LLVM BB %if.then
223 // Live Ins: %rdi
224 // Predecessors according to CFG: %bb.0
225 // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax
226 // ; No implicit %eax
227 // Successors according to CFG: %bb.3(?%)
229 // %bb.3: derived from LLVM BB %if.end
230 // Live Ins: %eax Only %ax is actually live
231 // Predecessors according to CFG: %bb.2 %bb.1
232 // %ax = KILL %ax, implicit killed %eax
233 // RET 0, %ax
234 unsigned Opc = OrigMI->getOpcode(); (void)Opc;
235 // These are the opcodes currently handled by the pass, if something
236 // else will be added we need to ensure that new opcode has the same
237 // properties.
238 assert((Opc == X86::MOV8rm || Opc == X86::MOV16rm || Opc == X86::MOV8rr ||
239 Opc == X86::MOV16rr) &&
240 "Unexpected opcode.");
242 bool IsDefined = false;
243 for (auto &MO: OrigMI->implicit_operands()) {
244 if (!MO.isReg())
245 continue;
247 assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!");
249 if (MO.isDef() && TRI->isSuperRegisterEq(OrigDestReg, MO.getReg()))
250 IsDefined = true;
252 // If MO is a use of any part of the destination register but is not equal
253 // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg.
254 // For example, if OrigDestReg is %al then an implicit use of %ah, %ax,
255 // %eax, or %rax will prevent us from using the %eax register.
256 if (MO.isUse() && !TRI->isSubRegisterEq(OrigDestReg, MO.getReg()) &&
257 TRI->regsOverlap(SuperDestReg, MO.getReg()))
258 return false;
260 // Reg is not Imp-def'ed -> it's live both before/after the instruction.
261 if (!IsDefined)
262 return false;
264 // Otherwise, the Reg is not live before the MI and the MOV can't
265 // make it really live, so it's in fact dead even after the MI.
266 return true;
269 MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode,
270 MachineInstr *MI) const {
271 unsigned NewDestReg;
273 // We are going to try to rewrite this load to a larger zero-extending
274 // load. This is safe if all portions of the 32 bit super-register
275 // of the original destination register, except for the original destination
276 // register are dead. getSuperRegDestIfDead checks that.
277 if (!getSuperRegDestIfDead(MI, NewDestReg))
278 return nullptr;
280 // Safe to change the instruction.
281 MachineInstrBuilder MIB =
282 BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg);
284 unsigned NumArgs = MI->getNumOperands();
285 for (unsigned i = 1; i < NumArgs; ++i)
286 MIB.add(MI->getOperand(i));
288 MIB.setMemRefs(MI->memoperands());
290 return MIB;
293 MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {
294 assert(MI->getNumExplicitOperands() == 2);
295 auto &OldDest = MI->getOperand(0);
296 auto &OldSrc = MI->getOperand(1);
298 unsigned NewDestReg;
299 if (!getSuperRegDestIfDead(MI, NewDestReg))
300 return nullptr;
302 unsigned NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32);
304 // This is only correct if we access the same subregister index: otherwise,
305 // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
306 auto *TRI = &TII->getRegisterInfo();
307 if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) !=
308 TRI->getSubRegIndex(NewDestReg, OldDest.getReg()))
309 return nullptr;
311 // Safe to change the instruction.
312 // Don't set src flags, as we don't know if we're also killing the superreg.
313 // However, the superregister might not be defined; make it explicit that
314 // we don't care about the higher bits by reading it as Undef, and adding
315 // an imp-use on the original subregister.
316 MachineInstrBuilder MIB =
317 BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg)
318 .addReg(NewSrcReg, RegState::Undef)
319 .addReg(OldSrc.getReg(), RegState::Implicit);
321 // Drop imp-defs/uses that would be redundant with the new def/use.
322 for (auto &Op : MI->implicit_operands())
323 if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg))
324 MIB.add(Op);
326 return MIB;
329 MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI,
330 MachineBasicBlock &MBB) const {
331 // See if this is an instruction of the type we are currently looking for.
332 switch (MI->getOpcode()) {
334 case X86::MOV8rm:
335 // Only replace 8 bit loads with the zero extending versions if
336 // in an inner most loop and not optimizing for size. This takes
337 // an extra byte to encode, and provides limited performance upside.
338 if (MachineLoop *ML = MLI->getLoopFor(&MBB))
339 if (ML->begin() == ML->end() && !OptForSize)
340 return tryReplaceLoad(X86::MOVZX32rm8, MI);
341 break;
343 case X86::MOV16rm:
344 // Always try to replace 16 bit load with 32 bit zero extending.
345 // Code size is the same, and there is sometimes a perf advantage
346 // from eliminating a false dependence on the upper portion of
347 // the register.
348 return tryReplaceLoad(X86::MOVZX32rm16, MI);
350 case X86::MOV8rr:
351 case X86::MOV16rr:
352 // Always try to replace 8/16 bit copies with a 32 bit copy.
353 // Code size is either less (16) or equal (8), and there is sometimes a
354 // perf advantage from eliminating a false dependence on the upper portion
355 // of the register.
356 return tryReplaceCopy(MI);
358 default:
359 // nothing to do here.
360 break;
363 return nullptr;
366 void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
367 MachineBasicBlock &MBB) {
369 // This algorithm doesn't delete the instructions it is replacing
370 // right away. By leaving the existing instructions in place, the
371 // register liveness information doesn't change, and this makes the
372 // analysis that goes on be better than if the replaced instructions
373 // were immediately removed.
375 // This algorithm always creates a replacement instruction
376 // and notes that and the original in a data structure, until the
377 // whole BB has been analyzed. This keeps the replacement instructions
378 // from making it seem as if the larger register might be live.
379 SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements;
381 // Start computing liveness for this block. We iterate from the end to be able
382 // to update this for each instruction.
383 LiveRegs.clear();
384 // We run after PEI, so we need to AddPristinesAndCSRs.
385 LiveRegs.addLiveOuts(MBB);
387 for (auto I = MBB.rbegin(); I != MBB.rend(); ++I) {
388 MachineInstr *MI = &*I;
390 if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB))
391 MIReplacements.push_back(std::make_pair(MI, NewMI));
393 // We're done with this instruction, update liveness for the next one.
394 LiveRegs.stepBackward(*MI);
397 while (!MIReplacements.empty()) {
398 MachineInstr *MI = MIReplacements.back().first;
399 MachineInstr *NewMI = MIReplacements.back().second;
400 MIReplacements.pop_back();
401 MBB.insert(MI, NewMI);
402 MBB.erase(MI);