1 //===-- InstSelectSimple.cpp - A simple instruction selector for x86 ------===//
3 // This file defines a simple peephole instruction selector for the x86 platform
5 //===----------------------------------------------------------------------===//
8 #include "X86InstrInfo.h"
9 #include "llvm/Function.h"
10 #include "llvm/iTerminators.h"
11 #include "llvm/iOther.h"
12 #include "llvm/iPHINode.h"
13 #include "llvm/Type.h"
14 #include "llvm/Constants.h"
15 #include "llvm/Pass.h"
16 #include "llvm/CodeGen/MachineFunction.h"
17 #include "llvm/CodeGen/MachineInstrBuilder.h"
18 #include "llvm/Support/InstVisitor.h"
22 struct ISel : public FunctionPass, InstVisitor<ISel> {
24 MachineFunction *F; // The function we are compiling into
25 MachineBasicBlock *BB; // The current MBB we are compiling
28 std::map<Value*, unsigned> RegMap; // Mapping between Val's and SSA Regs
30 ISel(TargetMachine &tm)
31 : TM(tm), F(0), BB(0), CurReg(MRegisterInfo::FirstVirtualRegister) {}
33 /// runOnFunction - Top level implementation of instruction selection for
34 /// the entire function.
36 bool runOnFunction(Function &Fn) {
37 F = &MachineFunction::construct(&Fn, TM);
41 return false; // We never modify the LLVM itself.
44 /// visitBasicBlock - This method is called when we are visiting a new basic
45 /// block. This simply creates a new MachineBasicBlock to emit code into
46 /// and adds it to the current MachineFunction. Subsequent visit* for
47 /// instructions will be invoked for all instructions in the basic block.
49 void visitBasicBlock(BasicBlock &LLVM_BB) {
50 BB = new MachineBasicBlock(&LLVM_BB);
51 // FIXME: Use the auto-insert form when it's available
52 F->getBasicBlockList().push_back(BB);
55 // Visitation methods for various instructions. These methods simply emit
56 // fixed X86 code for each instruction.
58 void visitPHINode(PHINode &I);
59 void visitReturnInst(ReturnInst &RI);
60 void visitBranchInst(BranchInst &BI);
61 void visitAdd(BinaryOperator &B);
62 void visitShiftInst(ShiftInst &I);
64 void visitInstruction(Instruction &I) {
65 std::cerr << "Cannot instruction select: " << I;
70 /// copyConstantToRegister - Output the instructions required to put the
71 /// specified constant into the specified register.
73 void copyConstantToRegister(Constant *C, unsigned Reg);
75 /// getReg - This method turns an LLVM value into a register number. This
76 /// is guaranteed to produce the same register number for a particular value
77 /// every time it is queried.
79 unsigned getReg(Value &V) { return getReg(&V); } // Allow references
80 unsigned getReg(Value *V) {
81 unsigned &Reg = RegMap[V];
85 // If this operand is a constant, emit the code to copy the constant into
86 // the register here...
88 if (Constant *C = dyn_cast<Constant>(V))
89 copyConstantToRegister(C, Reg);
96 /// getClass - Turn a primitive type into a "class" number which is based on the
97 /// size of the type, and whether or not it is floating point.
99 static inline unsigned getClass(const Type *Ty) {
100 switch (Ty->getPrimitiveID()) {
101 case Type::SByteTyID:
102 case Type::UByteTyID: return 0; // Byte operands are class #0
103 case Type::ShortTyID:
104 case Type::UShortTyID: return 1; // Short operands are class #1
107 case Type::PointerTyID: return 2; // Int's and pointers are class #2
110 case Type::ULongTyID: return 3; // Longs are class #3
111 case Type::FloatTyID: return 4; // Float is class #4
112 case Type::DoubleTyID: return 5; // Doubles are class #5
114 assert(0 && "Invalid type to getClass!");
115 return 0; // not reached
119 /// copyConstantToRegister - Output the instructions required to put the
120 /// specified constant into the specified register.
122 void ISel::copyConstantToRegister(Constant *C, unsigned R) {
123 assert (!isa<ConstantExpr>(C) && "Constant expressions not yet handled!\n");
125 if (C->getType()->isIntegral()) {
126 unsigned Class = getClass(C->getType());
127 assert(Class != 3 && "Type not handled yet!");
129 static const unsigned IntegralOpcodeTab[] = {
130 X86::MOVir8, X86::MOVir16, X86::MOVir32
133 if (C->getType()->isSigned()) {
134 ConstantSInt *CSI = cast<ConstantSInt>(C);
135 BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addSImm(CSI->getValue());
137 ConstantUInt *CUI = cast<ConstantUInt>(C);
138 BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
141 assert(0 && "Type not handled yet!");
145 /// visitPHINode - Turn an LLVM PHI node into an X86 PHI node...
147 void ISel::visitPHINode(PHINode &PN) {
148 MachineInstr *MI = BuildMI(BB, X86::PHI, PN.getNumOperands(), getReg(PN));
150 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
151 // FIXME: This will put constants after the PHI nodes in the block, which
152 // is invalid. They should be put inline into the PHI node eventually.
154 MI->addRegOperand(getReg(PN.getIncomingValue(i)));
155 MI->addPCDispOperand(PN.getIncomingBlock(i));
160 /// 'ret' instruction - Here we are interested in meeting the x86 ABI. As such,
161 /// we have the following possibilities:
163 /// ret void: No return value, simply emit a 'ret' instruction
164 /// ret sbyte, ubyte : Extend value into EAX and return
165 /// ret short, ushort: Extend value into EAX and return
166 /// ret int, uint : Move value into EAX and return
167 /// ret pointer : Move value into EAX and return
168 /// ret long, ulong : Move value into EAX/EDX (?) and return
169 /// ret float/double : ? Top of FP stack? XMM0?
171 void ISel::visitReturnInst(ReturnInst &I) {
172 if (I.getNumOperands() != 0) { // Not 'ret void'?
173 // Move result into a hard register... then emit a ret
174 visitInstruction(I); // abort
177 // Emit a simple 'ret' instruction... appending it to the end of the basic
179 BuildMI(BB, X86::RET, 0);
182 /// visitBranchInst - Handle conditional and unconditional branches here. Note
183 /// that since code layout is frozen at this point, that if we are trying to
184 /// jump to a block that is the immediate successor of the current block, we can
185 /// just make a fall-through. (but we don't currently).
187 void ISel::visitBranchInst(BranchInst &BI) {
188 if (BI.isConditional()) // Only handles unconditional branches so far...
189 visitInstruction(BI);
191 BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
195 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
196 /// for constant immediate shift values, and for constant immediate
197 /// shift values equal to 1. Even the general case is sort of special,
198 /// because the shift amount has to be in CL, not just any old register.
201 ISel::visitShiftInst (ShiftInst & I)
203 unsigned Op0r = getReg (I.getOperand (0));
204 unsigned DestReg = getReg (I);
205 bool isLeftShift = I.getOpcode() == Instruction::Shl;
206 bool isOperandSigned = I.getType()->isUnsigned();
207 unsigned OperandClass = getClass(I.getType());
209 if (OperandClass > 2)
210 visitInstruction(I); // Can't handle longs yet!
212 if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
214 // The shift amount is constant, guaranteed to be a ubyte. Get its value.
215 assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
216 unsigned char shAmt = CUI->getValue();
218 static const unsigned ConstantOperand[][4] = {
219 { X86::SHRir8, X86::SHRir16, X86::SHRir32, 0 }, // SHR
220 { X86::SARir8, X86::SARir16, X86::SARir32, 0 }, // SAR
221 { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 }, // SHL
222 { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 }, // SAL = SHL
225 const unsigned *OpTab = // Figure out the operand table to use
226 ConstantOperand[isLeftShift*2+isOperandSigned];
228 // Emit: <insn> reg, shamt (shift-by-immediate opcode "ir" form.)
229 BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addZImm(shAmt);
233 // The shift amount is non-constant.
235 // In fact, you can only shift with a variable shift amount if
236 // that amount is already in the CL register, so we have to put it
240 // Emit: move cl, shiftAmount (put the shift amount in CL.)
241 BuildMI (BB, X86::MOVrr8, 2, X86::CL).addReg(getReg(I.getOperand(1)));
243 // This is a shift right (SHR).
244 static const unsigned NonConstantOperand[][4] = {
245 { X86::SHRrr8, X86::SHRrr16, X86::SHRrr32, 0 }, // SHR
246 { X86::SARrr8, X86::SARrr16, X86::SARrr32, 0 }, // SAR
247 { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 }, // SHL
248 { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 }, // SAL = SHL
251 const unsigned *OpTab = // Figure out the operand table to use
252 NonConstantOperand[isLeftShift*2+isOperandSigned];
254 BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addReg(X86::CL);
259 /// 'add' instruction - Simply turn this into an x86 reg,reg add instruction.
260 void ISel::visitAdd(BinaryOperator &B) {
261 unsigned Op0r = getReg(B.getOperand(0)), Op1r = getReg(B.getOperand(1));
262 unsigned DestReg = getReg(B);
263 unsigned Class = getClass(B.getType());
265 static const unsigned Opcodes[] = { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32 };
267 if (Class >= sizeof(Opcodes)/sizeof(Opcodes[0]))
268 visitInstruction(B); // Not handled class yet...
270 BuildMI(BB, Opcodes[Class], 2, DestReg).addReg(Op0r).addReg(Op1r);
272 // For Longs: Here we have a pair of operands each occupying a pair of
273 // registers. We need to do an ADDrr32 of the least-significant pair
274 // immediately followed by an ADCrr32 (Add with Carry) of the most-significant
275 // pair. I don't know how we are representing these multi-register arguments.
280 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
281 /// into a machine code representation is a very simple peep-hole fashion. The
282 /// generated code sucks but the implementation is nice and simple.
284 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {