lib/Target/X86/X86ISelSimple.cpp

   1 //===-- InstSelectSimple.cpp - A simple instruction selector for x86 ------===//
   2 //
   3 // This file defines a simple peephole instruction selector for the x86 platform
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "X86.h"
   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"
  19 #include <map>
  20
  21 namespace {
  22   struct ISel : public FunctionPass, InstVisitor<ISel> {
  23     TargetMachine &TM;
  24     MachineFunction *F;                    // The function we are compiling into
  25     MachineBasicBlock *BB;                 // The current MBB we are compiling
  26
  27     unsigned CurReg;
  28     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  29
  30     ISel(TargetMachine &tm)
  31       : TM(tm), F(0), BB(0), CurReg(MRegisterInfo::FirstVirtualRegister) {}
  32
  33     /// runOnFunction - Top level implementation of instruction selection for
  34     /// the entire function.
  35     ///
  36     bool runOnFunction(Function &Fn) {
  37       F = &MachineFunction::construct(&Fn, TM);
  38       visit(Fn);
  39       RegMap.clear();
  40       F = 0;
  41       return false;  // We never modify the LLVM itself.
  42     }
  43
  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.
  48     ///
  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);
  53     }
  54
  55     // Visitation methods for various instructions.  These methods simply emit
  56     // fixed X86 code for each instruction.
  57     //
  58     void visitReturnInst(ReturnInst &RI);
  59     void visitBranchInst(BranchInst &BI);
  60
  61     // Arithmetic operators
  62     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
  63     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
  64     void visitMul(BinaryOperator &B);
  65
  66     // Bitwise operators
  67     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
  68     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
  69     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
  70     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
  71
  72     // Binary comparison operators
  73
  74     // Other operators
  75     void visitShiftInst(ShiftInst &I);
  76     void visitPHINode(PHINode &I);
  77
  78     void visitInstruction(Instruction &I) {
  79       std::cerr << "Cannot instruction select: " << I;
  80       abort();
  81     }
  82
  83
  84     /// copyConstantToRegister - Output the instructions required to put the
  85     /// specified constant into the specified register.
  86     ///
  87     void copyConstantToRegister(Constant *C, unsigned Reg);
  88
  89     /// getReg - This method turns an LLVM value into a register number.  This
  90     /// is guaranteed to produce the same register number for a particular value
  91     /// every time it is queried.
  92     ///
  93     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
  94     unsigned getReg(Value *V) {
  95       unsigned &Reg = RegMap[V];
  96       if (Reg == 0)
  97         Reg = CurReg++;
  98
  99       // If this operand is a constant, emit the code to copy the constant into
 100       // the register here...
 101       //
 102       if (Constant *C = dyn_cast<Constant>(V))
 103         copyConstantToRegister(C, Reg);
 104
 105       return Reg;
 106     }
 107   };
 108 }
 109
 110 /// getClass - Turn a primitive type into a "class" number which is based on the
 111 /// size of the type, and whether or not it is floating point.
 112 ///
 113 static inline unsigned getClass(const Type *Ty) {
 114   switch (Ty->getPrimitiveID()) {
 115   case Type::SByteTyID:
 116   case Type::UByteTyID:   return 0;          // Byte operands are class #0
 117   case Type::ShortTyID:
 118   case Type::UShortTyID:  return 1;          // Short operands are class #1
 119   case Type::IntTyID:
 120   case Type::UIntTyID:
 121   case Type::PointerTyID: return 2;          // Int's and pointers are class #2
 122
 123   case Type::LongTyID:
 124   case Type::ULongTyID:   return 3;          // Longs are class #3
 125   case Type::FloatTyID:   return 4;          // Float is class #4
 126   case Type::DoubleTyID:  return 5;          // Doubles are class #5
 127   default:
 128     assert(0 && "Invalid type to getClass!");
 129     return 0;  // not reached
 130   }
 131 }
 132
 133 /// copyConstantToRegister - Output the instructions required to put the
 134 /// specified constant into the specified register.
 135 ///
 136 void ISel::copyConstantToRegister(Constant *C, unsigned R) {
 137   assert (!isa<ConstantExpr>(C) && "Constant expressions not yet handled!\n");
 138
 139   if (C->getType()->isIntegral()) {
 140     unsigned Class = getClass(C->getType());
 141     assert(Class != 3 && "Type not handled yet!");
 142
 143     static const unsigned IntegralOpcodeTab[] = {
 144       X86::MOVir8, X86::MOVir16, X86::MOVir32
 145     };
 146
 147     if (C->getType()->isSigned()) {
 148       ConstantSInt *CSI = cast<ConstantSInt>(C);
 149       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addSImm(CSI->getValue());
 150     } else {
 151       ConstantUInt *CUI = cast<ConstantUInt>(C);
 152       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
 153     }
 154   } else {
 155     assert(0 && "Type not handled yet!");
 156   }
 157 }
 158
 159
 160
 161 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 162 /// we have the following possibilities:
 163 ///
 164 ///   ret void: No return value, simply emit a 'ret' instruction
 165 ///   ret sbyte, ubyte : Extend value into EAX and return
 166 ///   ret short, ushort: Extend value into EAX and return
 167 ///   ret int, uint    : Move value into EAX and return
 168 ///   ret pointer      : Move value into EAX and return
 169 ///   ret long, ulong  : Move value into EAX/EDX (?) and return
 170 ///   ret float/double : ?  Top of FP stack?  XMM0?
 171 ///
 172 void ISel::visitReturnInst(ReturnInst &I) {
 173   if (I.getNumOperands() != 0) {  // Not 'ret void'?
 174     // Move result into a hard register... then emit a ret
 175     visitInstruction(I);  // abort
 176   }
 177
 178   // Emit a simple 'ret' instruction... appending it to the end of the basic
 179   // block
 180   BuildMI(BB, X86::RET, 0);
 181 }
 182
 183 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
 184 /// that since code layout is frozen at this point, that if we are trying to
 185 /// jump to a block that is the immediate successor of the current block, we can
 186 /// just make a fall-through. (but we don't currently).
 187 ///
 188 void ISel::visitBranchInst(BranchInst &BI) {
 189   if (BI.isConditional())   // Only handles unconditional branches so far...
 190     visitInstruction(BI);
 191
 192   BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 193 }
 194
 195
 196 /// visitSimpleBinary - Implement simple binary operators for integral types...
 197 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or,
 198 /// 4 for Xor.
 199 ///
 200 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
 201   if (B.getType() == Type::BoolTy)  // FIXME: Handle bools for logicals
 202     visitInstruction(B);
 203
 204   unsigned Class = getClass(B.getType());
 205   if (Class > 2)  // FIXME: Handle longs
 206     visitInstruction(B);
 207
 208   static const unsigned OpcodeTab[][4] = {
 209     // Arithmetic operators
 210     { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32, 0 },  // ADD
 211     { X86::SUBrr8, X86::SUBrr16, X86::SUBrr32, 0 },  // SUB
 212
 213     // Bitwise operators
 214     { X86::ANDrr8, X86::ANDrr16, X86::ANDrr32, 0 },  // AND
 215     { X86:: ORrr8, X86:: ORrr16, X86:: ORrr32, 0 },  // OR
 216     { X86::XORrr8, X86::XORrr16, X86::XORrr32, 0 },  // XOR
 217   };
 218
 219   unsigned Opcode = OpcodeTab[OperatorClass][Class];
 220   unsigned Op0r = getReg(B.getOperand(0));
 221   unsigned Op1r = getReg(B.getOperand(1));
 222   BuildMI(BB, Opcode, 2, getReg(B)).addReg(Op0r).addReg(Op1r);
 223 }
 224
 225 /// visitMul - Multiplies are not simple binary operators because they must deal
 226 /// with the EAX register explicitly.
 227 ///
 228 void ISel::visitMul(BinaryOperator &I) {
 229   unsigned Class = getClass(I.getType());
 230   if (Class > 2)  // FIXME: Handle longs
 231     visitInstruction(I);
 232
 233   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
 234   static const unsigned MulOpcode[]={ X86::MULrr8, X86::MULrr16, X86::MULrr32 };
 235   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
 236
 237   unsigned Reg = Regs[Class];
 238   unsigned Op0Reg = getReg(I.getOperand(1));
 239   unsigned Op1Reg = getReg(I.getOperand(1));
 240
 241   // Put the first operand into one of the A registers...
 242   BuildMI(BB, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
 243
 244   // Emit the appropriate multiple instruction...
 245   // FIXME: We need to mark that this modified AH, DX, or EDX also!!
 246   BuildMI(BB, MulOpcode[Class], 2, Reg).addReg(Reg).addReg(Op1Reg);
 247
 248   // Put the result into the destination register...
 249   BuildMI(BB, MovOpcode[Class], 1, getReg(I)).addReg(Reg);
 250
 251 }
 252
 253 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
 254 /// for constant immediate shift values, and for constant immediate
 255 /// shift values equal to 1. Even the general case is sort of special,
 256 /// because the shift amount has to be in CL, not just any old register.
 257 ///
 258 void
 259 ISel::visitShiftInst (ShiftInst & I)
 260 {
 261   unsigned Op0r = getReg (I.getOperand (0));
 262   unsigned DestReg = getReg (I);
 263   bool isLeftShift = I.getOpcode() == Instruction::Shl;
 264   bool isOperandSigned = I.getType()->isUnsigned();
 265   unsigned OperandClass = getClass(I.getType());
 266
 267   if (OperandClass > 2)
 268     visitInstruction(I); // Can't handle longs yet!
 269
 270   if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
 271     {
 272       // The shift amount is constant, guaranteed to be a ubyte. Get its value.
 273       assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
 274       unsigned char shAmt = CUI->getValue();
 275
 276       static const unsigned ConstantOperand[][4] = {
 277         { X86::SHRir8, X86::SHRir16, X86::SHRir32, 0 },  // SHR
 278         { X86::SARir8, X86::SARir16, X86::SARir32, 0 },  // SAR
 279         { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 },  // SHL
 280         { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 },  // SAL = SHL
 281       };
 282
 283       const unsigned *OpTab = // Figure out the operand table to use
 284         ConstantOperand[isLeftShift*2+isOperandSigned];
 285
 286       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 287       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addZImm(shAmt);
 288     }
 289   else
 290     {
 291       // The shift amount is non-constant.
 292       //
 293       // In fact, you can only shift with a variable shift amount if
 294       // that amount is already in the CL register, so we have to put it
 295       // there first.
 296       //
 297
 298       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 299       BuildMI(BB, X86::MOVrr8, 1, X86::CL).addReg(getReg(I.getOperand(1)));
 300
 301       // This is a shift right (SHR).
 302       static const unsigned NonConstantOperand[][4] = {
 303         { X86::SHRrr8, X86::SHRrr16, X86::SHRrr32, 0 },  // SHR
 304         { X86::SARrr8, X86::SARrr16, X86::SARrr32, 0 },  // SAR
 305         { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 },  // SHL
 306         { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 },  // SAL = SHL
 307       };
 308
 309       const unsigned *OpTab = // Figure out the operand table to use
 310         NonConstantOperand[isLeftShift*2+isOperandSigned];
 311
 312       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addReg(X86::CL);
 313     }
 314 }
 315
 316 /// visitPHINode - Turn an LLVM PHI node into an X86 PHI node...
 317 ///
 318 void ISel::visitPHINode(PHINode &PN) {
 319   MachineInstr *MI = BuildMI(BB, X86::PHI, PN.getNumOperands(), getReg(PN));
 320
 321   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 322     // FIXME: This will put constants after the PHI nodes in the block, which
 323     // is invalid.  They should be put inline into the PHI node eventually.
 324     //
 325     MI->addRegOperand(getReg(PN.getIncomingValue(i)));
 326     MI->addPCDispOperand(PN.getIncomingBlock(i));
 327   }
 328 }
 329
 330
 331 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
 332 /// into a machine code representation is a very simple peep-hole fashion.  The
 333 /// generated code sucks but the implementation is nice and simple.
 334 ///
 335 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
 336   return new ISel(TM);
 337 }