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/Type.h"
  13 #include "llvm/Constants.h"
  14 #include "llvm/Pass.h"
  15 #include "llvm/CodeGen/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineInstrBuilder.h"
  17 #include "llvm/Support/InstVisitor.h"
  18 #include <map>
  19
  20 namespace {
  21   struct ISel : public FunctionPass, InstVisitor<ISel> {
  22     TargetMachine &TM;
  23     MachineFunction *F;                    // The function we are compiling into
  24     MachineBasicBlock *BB;                 // The current MBB we are compiling
  25
  26     unsigned CurReg;
  27     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  28
  29     ISel(TargetMachine &tm)
  30       : TM(tm), F(0), BB(0), CurReg(MRegisterInfo::FirstVirtualRegister) {}
  31
  32     /// runOnFunction - Top level implementation of instruction selection for
  33     /// the entire function.
  34     ///
  35     bool runOnFunction(Function &Fn) {
  36       F = &MachineFunction::construct(&Fn, TM);
  37       visit(Fn);
  38       RegMap.clear();
  39       F = 0;
  40       return false;  // We never modify the LLVM itself.
  41     }
  42
  43     /// visitBasicBlock - This method is called when we are visiting a new basic
  44     /// block.  This simply creates a new MachineBasicBlock to emit code into
  45     /// and adds it to the current MachineFunction.  Subsequent visit* for
  46     /// instructions will be invoked for all instructions in the basic block.
  47     ///
  48     void visitBasicBlock(BasicBlock &LLVM_BB) {
  49       BB = new MachineBasicBlock(&LLVM_BB);
  50       // FIXME: Use the auto-insert form when it's available
  51       F->getBasicBlockList().push_back(BB);
  52     }
  53
  54     // Visitation methods for various instructions.  These methods simply emit
  55     // fixed X86 code for each instruction.
  56     //
  57     void visitReturnInst(ReturnInst &RI);
  58     void visitAdd(BinaryOperator &B);
  59     void visitShiftInst(ShiftInst &I);
  60
  61     void visitInstruction(Instruction &I) {
  62       std::cerr << "Cannot instruction select: " << I;
  63       abort();
  64     }
  65
  66
  67     /// copyConstantToRegister - Output the instructions required to put the
  68     /// specified constant into the specified register.
  69     ///
  70     void copyConstantToRegister(Constant *C, unsigned Reg);
  71
  72     /// getReg - This method turns an LLVM value into a register number.  This
  73     /// is guaranteed to produce the same register number for a particular value
  74     /// every time it is queried.
  75     ///
  76     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
  77     unsigned getReg(Value *V) {
  78       unsigned &Reg = RegMap[V];
  79       if (Reg == 0)
  80         Reg = CurReg++;
  81
  82       // If this operand is a constant, emit the code to copy the constant into
  83       // the register here...
  84       //
  85       if (Constant *C = dyn_cast<Constant>(V))
  86         copyConstantToRegister(C, Reg);
  87
  88       return Reg;
  89     }
  90   };
  91 }
  92
  93 /// getClass - Turn a primitive type into a "class" number which is based on the
  94 /// size of the type, and whether or not it is floating point.
  95 ///
  96 static inline unsigned getClass(const Type *Ty) {
  97   switch (Ty->getPrimitiveID()) {
  98   case Type::SByteTyID:
  99   case Type::UByteTyID:   return 0;          // Byte operands are class #0
 100   case Type::ShortTyID:
 101   case Type::UShortTyID:  return 1;          // Short operands are class #1
 102   case Type::IntTyID:
 103   case Type::UIntTyID:
 104   case Type::PointerTyID: return 2;          // Int's and pointers are class #2
 105
 106   case Type::LongTyID:
 107   case Type::ULongTyID:   return 3;          // Longs are class #3
 108   case Type::FloatTyID:   return 4;          // Float is class #4
 109   case Type::DoubleTyID:  return 5;          // Doubles are class #5
 110   default:
 111     assert(0 && "Invalid type to getClass!");
 112     return 0;  // not reached
 113   }
 114 }
 115
 116 /// copyConstantToRegister - Output the instructions required to put the
 117 /// specified constant into the specified register.
 118 ///
 119 void ISel::copyConstantToRegister(Constant *C, unsigned R) {
 120   assert (!isa<ConstantExpr>(C) && "Constant expressions not yet handled!\n");
 121
 122   if (C->getType()->isIntegral()) {
 123     unsigned Class = getClass(C->getType());
 124     assert(Class != 3 && "Type not handled yet!");
 125
 126     static const unsigned IntegralOpcodeTab[] = {
 127       X86::MOVir8, X86::MOVir16, X86::MOVir32
 128     };
 129
 130     if (C->getType()->isSigned()) {
 131       ConstantSInt *CSI = cast<ConstantSInt>(C);
 132       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addSImm(CSI->getValue());
 133     } else {
 134       ConstantUInt *CUI = cast<ConstantUInt>(C);
 135       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
 136     }
 137   } else {
 138     assert(0 && "Type not handled yet!");
 139   }
 140 }
 141
 142
 143 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 144 /// we have the following possibilities:
 145 ///
 146 ///   ret void: No return value, simply emit a 'ret' instruction
 147 ///   ret sbyte, ubyte : Extend value into EAX and return
 148 ///   ret short, ushort: Extend value into EAX and return
 149 ///   ret int, uint    : Move value into EAX and return
 150 ///   ret pointer      : Move value into EAX and return
 151 ///   ret long, ulong  : Move value into EAX/EDX (?) and return
 152 ///   ret float/double : ?  Top of FP stack?  XMM0?
 153 ///
 154 void ISel::visitReturnInst(ReturnInst &I) {
 155   if (I.getNumOperands() != 0) {  // Not 'ret void'?
 156     // Move result into a hard register... then emit a ret
 157     visitInstruction(I);  // abort
 158   }
 159
 160   // Emit a simple 'ret' instruction... appending it to the end of the basic
 161   // block
 162   BuildMI(BB, X86::RET, 0);
 163 }
 164
 165 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
 166 /// for constant immediate shift values, and for constant immediate
 167 /// shift values equal to 1. Even the general case is sort of special,
 168 /// because the shift amount has to be in CL, not just any old register.
 169 ///
 170 void
 171 ISel::visitShiftInst (ShiftInst & I)
 172 {
 173   unsigned Op0r = getReg (I.getOperand (0));
 174   unsigned DestReg = getReg (I);
 175   bool isRightShift = (I.getOpcode () == Instruction::Shr);
 176   bool isOperandUnsigned = I.getType ()->isUnsigned ();
 177   unsigned OperandClass = getClass(I.getType());
 178
 179   if (OperandClass > 2)
 180     visitInstruction(I); // Can't handle longs yet!
 181
 182   if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
 183     {
 184       // The shift amount is constant, guaranteed to be a ubyte. Get its value.
 185       assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
 186       unsigned char shAmt = CUI->getValue();
 187
 188       // This is a shift right (SHR).
 189       static const unsigned SHRUnsignedConstantOperand[] = {
 190         X86::SHRir8, X86::SHRir16, X86::SHRir32
 191       };
 192
 193       // This is a shift right arithmetic (SAR).
 194       static const unsigned SHRSignedConstantOperand[] = {
 195         X86::SARir8, X86::SARir16, X86::SARir32
 196       };
 197
 198       // This is a shift left (SHL).
 199       static const unsigned SHLConstantOperand[] = {
 200         X86::SHLir8, X86::SHLir16, X86::SHLir32
 201       };
 202
 203       const unsigned *OpTab = 0;  // Figure out the operand table to use
 204       if (isRightShift) {
 205         if (isOperandUnsigned)
 206           OpTab = SHRUnsignedConstantOperand;
 207         else
 208           OpTab = SHRSignedConstantOperand;
 209       } else {
 210         // This is a left shift (SHL).
 211         OpTab = SHLConstantOperand;
 212       }
 213
 214       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 215       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addZImm(shAmt);
 216     }
 217   else
 218     {
 219       // The shift amount is non-constant.
 220       //
 221       // In fact, you can only shift with a variable shift amount if
 222       // that amount is already in the CL register, so we have to put it
 223       // there first.
 224       //
 225       // Get it from the register it's in.
 226       unsigned Op1r = getReg (I.getOperand (1));
 227       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 228       BuildMI (BB, X86::MOVrr8, 2, X86::CL).addReg (Op1r);
 229
 230       // This is a shift right (SHR).
 231       static const unsigned SHRUnsignedOperand[] = {
 232         X86::SHRrr8, X86::SHRrr16, X86::SHRrr32
 233       };
 234
 235       // This is a shift right arithmetic (SAR).
 236       static const unsigned SHRSignedOperand[] = {
 237         X86::SARrr8, X86::SARrr16, X86::SARrr32
 238       };
 239
 240       // This is a shift left (SHL).
 241       static const unsigned SHLOperand[] = {
 242         X86::SHLrr8, X86::SHLrr16, X86::SHLrr32
 243       };
 244
 245       // Emit: <insn> reg, cl       (shift-by-CL opcode; "rr" form.)
 246       const unsigned *OpTab = 0;  // Figure out the operand table to use
 247       if (isRightShift) {
 248         if (isOperandUnsigned)
 249           OpTab = SHRUnsignedOperand;
 250         else
 251           OpTab = SHRSignedOperand;
 252       } else {
 253         // This is a left shift (SHL).
 254         OpTab = SHLOperand;
 255       }
 256
 257
 258       BuildMI (BB, X86::SHLrr32, 2,
 259                DestReg).addReg (Op0r).addReg (X86::CL);
 260     }
 261 }
 262
 263
 264 /// 'add' instruction - Simply turn this into an x86 reg,reg add instruction.
 265 void ISel::visitAdd(BinaryOperator &B) {
 266   unsigned Op0r = getReg(B.getOperand(0)), Op1r = getReg(B.getOperand(1));
 267   unsigned DestReg = getReg(B);
 268   unsigned Class = getClass(B.getType());
 269
 270   static const unsigned Opcodes[] = { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32 };
 271
 272   if (Class >= sizeof(Opcodes)/sizeof(Opcodes[0]))
 273     visitInstruction(B);  // Not handled class yet...
 274
 275   BuildMI(BB, Opcodes[Class], 2, DestReg).addReg(Op0r).addReg(Op1r);
 276
 277   // For Longs: Here we have a pair of operands each occupying a pair of
 278   // registers.  We need to do an ADDrr32 of the least-significant pair
 279   // immediately followed by an ADCrr32 (Add with Carry) of the most-significant
 280   // pair.  I don't know how we are representing these multi-register arguments.
 281 }
 282
 283
 284
 285 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
 286 /// into a machine code representation is a very simple peep-hole fashion.  The
 287 /// generated code sucks but the implementation is nice and simple.
 288 ///
 289 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
 290   return new ISel(TM);
 291 }