1 //===---- X86FixupSetCC.cpp - optimize usage of LEA 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 //
9 // This file defines a pass that fixes zero-extension of setcc patterns.
10 // X86 setcc instructions are modeled to have no input arguments, and a single
11 // GR8 output argument. This is consistent with other similar instructions
12 // (e.g. movb), but means it is impossible to directly generate a setcc into
13 // the lower GR8 of a specified GR32.
14 // This means that ISel must select (zext (setcc)) into something like
15 // seta %al; movzbl %al, %eax.
16 // Unfortunately, this can cause a stall due to the partial register write
17 // performed by the setcc. Instead, we can use:
18 // xor %eax, %eax; seta %al
19 // This both avoids the stall, and encodes shorter.
20 //===----------------------------------------------------------------------===//
21 
22 #include "X86.h"
23 #include "X86InstrInfo.h"
24 #include "X86Subtarget.h"
25 #include "llvm/ADT/Statistic.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "x86-fixup-setcc"
33 
34 STATISTIC(NumSubstZexts, "Number of setcc + zext pairs substituted");
35 
36 namespace {
37 class X86FixupSetCCPass : public MachineFunctionPass {
38 public:
39   X86FixupSetCCPass() : MachineFunctionPass(ID) {}
40 
41   StringRef getPassName() const override { return "X86 Fixup SetCC"; }
42 
43   bool runOnMachineFunction(MachineFunction &MF) override;
44 
45 private:
46   // Find the preceding instruction that imp-defs eflags.
47   MachineInstr *findFlagsImpDef(MachineBasicBlock *MBB,
48                                 MachineBasicBlock::reverse_iterator MI);
49 
50   // Return true if MI imp-uses eflags.
51   bool impUsesFlags(MachineInstr *MI);
52 
53   // Return true if this is the opcode of a SetCC instruction with a register
54   // output.
55   bool isSetCCr(unsigned Opode);
56 
57   MachineRegisterInfo *MRI;
58   const X86InstrInfo *TII;
59 
60   enum { SearchBound = 16 };
61 
62   static char ID;
63 };
64 
65 char X86FixupSetCCPass::ID = 0;
66 }
67 
68 FunctionPass *llvm::createX86FixupSetCC() { return new X86FixupSetCCPass(); }
69 
70 bool X86FixupSetCCPass::isSetCCr(unsigned Opcode) {
71   switch (Opcode) {
72   default:
73     return false;
74   case X86::SETOr:
75   case X86::SETNOr:
76   case X86::SETBr:
77   case X86::SETAEr:
78   case X86::SETEr:
79   case X86::SETNEr:
80   case X86::SETBEr:
81   case X86::SETAr:
82   case X86::SETSr:
83   case X86::SETNSr:
84   case X86::SETPr:
85   case X86::SETNPr:
86   case X86::SETLr:
87   case X86::SETGEr:
88   case X86::SETLEr:
89   case X86::SETGr:
90     return true;
91   }
92 }
93 
94 // We expect the instruction *immediately* before the setcc to imp-def
95 // EFLAGS (because of scheduling glue). To make this less brittle w.r.t
96 // scheduling, look backwards until we hit the beginning of the
97 // basic-block, or a small bound (to avoid quadratic behavior).
98 MachineInstr *
99 X86FixupSetCCPass::findFlagsImpDef(MachineBasicBlock *MBB,
100                                    MachineBasicBlock::reverse_iterator MI) {
101   // FIXME: Should this be instr_rend(), and MI be reverse_instr_iterator?
102   auto MBBStart = MBB->rend();
103   for (int i = 0; (i < SearchBound) && (MI != MBBStart); ++i, ++MI)
104     for (auto &Op : MI->implicit_operands())
105       if (Op.isReg() && (Op.getReg() == X86::EFLAGS) && Op.isDef())
106         return &*MI;
107 
108   return nullptr;
109 }
110 
111 bool X86FixupSetCCPass::impUsesFlags(MachineInstr *MI) {
112   for (auto &Op : MI->implicit_operands())
113     if (Op.isReg() && (Op.getReg() == X86::EFLAGS) && Op.isUse())
114       return true;
115 
116   return false;
117 }
118 
119 bool X86FixupSetCCPass::runOnMachineFunction(MachineFunction &MF) {
120   bool Changed = false;
121   MRI = &MF.getRegInfo();
122   TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
123 
124   SmallVector<MachineInstr*, 4> ToErase;
125 
126   for (auto &MBB : MF) {
127     for (auto &MI : MBB) {
128       // Find a setcc that is used by a zext.
129       // This doesn't have to be the only use, the transformation is safe
130       // regardless.
131       if (!isSetCCr(MI.getOpcode()))
132         continue;
133 
134       MachineInstr *ZExt = nullptr;
135       for (auto &Use : MRI->use_instructions(MI.getOperand(0).getReg()))
136         if (Use.getOpcode() == X86::MOVZX32rr8)
137           ZExt = &Use;
138 
139       if (!ZExt)
140         continue;
141 
142       // Find the preceding instruction that imp-defs eflags.
143       MachineInstr *FlagsDefMI = findFlagsImpDef(
144           MI.getParent(), MachineBasicBlock::reverse_iterator(&MI));
145       if (!FlagsDefMI)
146         continue;
147 
148       // We'd like to put something that clobbers eflags directly before
149       // FlagsDefMI. This can't hurt anything after FlagsDefMI, because
150       // it, itself, by definition, clobbers eflags. But it may happen that
151       // FlagsDefMI also *uses* eflags, in which case the transformation is
152       // invalid.
153       if (impUsesFlags(FlagsDefMI))
154         continue;
155 
156       ++NumSubstZexts;
157       Changed = true;
158 
159       // On 32-bit, we need to be careful to force an ABCD register.
160       const TargetRegisterClass *RC = MF.getSubtarget<X86Subtarget>().is64Bit()
161                                           ? &X86::GR32RegClass
162                                           : &X86::GR32_ABCDRegClass;
163       unsigned ZeroReg = MRI->createVirtualRegister(RC);
164       unsigned InsertReg = MRI->createVirtualRegister(RC);
165 
166       // Initialize a register with 0. This must go before the eflags def
167       BuildMI(MBB, FlagsDefMI, MI.getDebugLoc(), TII->get(X86::MOV32r0),
168               ZeroReg);
169 
170       // X86 setcc only takes an output GR8, so fake a GR32 input by inserting
171       // the setcc result into the low byte of the zeroed register.
172       BuildMI(*ZExt->getParent(), ZExt, ZExt->getDebugLoc(),
173               TII->get(X86::INSERT_SUBREG), InsertReg)
174           .addReg(ZeroReg)
175           .addReg(MI.getOperand(0).getReg())
176           .addImm(X86::sub_8bit);
177       MRI->replaceRegWith(ZExt->getOperand(0).getReg(), InsertReg);
178       ToErase.push_back(ZExt);
179     }
180   }
181 
182   for (auto &I : ToErase)
183     I->eraseFromParent();
184 
185   return Changed;
186 }
187