lib/Target/X86/InstSelectSimple.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 visitPHINode(PHINode &I);
  59     void visitReturnInst(ReturnInst &RI);
  60     void visitBranchInst(BranchInst &BI);
  61     void visitAdd(BinaryOperator &B);
  62     void visitShiftInst(ShiftInst &I);
  63
  64     void visitInstruction(Instruction &I) {
  65       std::cerr << "Cannot instruction select: " << I;
  66       abort();
  67     }
  68
  69
  70     /// copyConstantToRegister - Output the instructions required to put the
  71     /// specified constant into the specified register.
  72     ///
  73     void copyConstantToRegister(Constant *C, unsigned Reg);
  74
  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.
  78     ///
  79     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
  80     unsigned getReg(Value *V) {
  81       unsigned &Reg = RegMap[V];
  82       if (Reg == 0)
  83         Reg = CurReg++;
  84
  85       // If this operand is a constant, emit the code to copy the constant into
  86       // the register here...
  87       //
  88       if (Constant *C = dyn_cast<Constant>(V))
  89         copyConstantToRegister(C, Reg);
  90
  91       return Reg;
  92     }
  93   };
  94 }
  95
  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.
  98 ///
  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
 105   case Type::IntTyID:
 106   case Type::UIntTyID:
 107   case Type::PointerTyID: return 2;          // Int's and pointers are class #2
 108
 109   case Type::LongTyID:
 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
 113   default:
 114     assert(0 && "Invalid type to getClass!");
 115     return 0;  // not reached
 116   }
 117 }
 118
 119 /// copyConstantToRegister - Output the instructions required to put the
 120 /// specified constant into the specified register.
 121 ///
 122 void ISel::copyConstantToRegister(Constant *C, unsigned R) {
 123   assert (!isa<ConstantExpr>(C) && "Constant expressions not yet handled!\n");
 124
 125   if (C->getType()->isIntegral()) {
 126     unsigned Class = getClass(C->getType());
 127     assert(Class != 3 && "Type not handled yet!");
 128
 129     static const unsigned IntegralOpcodeTab[] = {
 130       X86::MOVir8, X86::MOVir16, X86::MOVir32
 131     };
 132
 133     if (C->getType()->isSigned()) {
 134       ConstantSInt *CSI = cast<ConstantSInt>(C);
 135       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addSImm(CSI->getValue());
 136     } else {
 137       ConstantUInt *CUI = cast<ConstantUInt>(C);
 138       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
 139     }
 140   } else {
 141     assert(0 && "Type not handled yet!");
 142   }
 143 }
 144
 145 /// visitPHINode - Turn an LLVM PHI node into an X86 PHI node...
 146 ///
 147 void ISel::visitPHINode(PHINode &PN) {
 148   MachineInstr *MI = BuildMI(BB, X86::PHI, PN.getNumOperands(), getReg(PN));
 149
 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.
 153     //
 154     MI->addRegOperand(getReg(PN.getIncomingValue(i)));
 155     MI->addPCDispOperand(PN.getIncomingBlock(i));
 156   }
 157 }
 158
 159
 160 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 161 /// we have the following possibilities:
 162 ///
 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?
 170 ///
 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
 175   }
 176
 177   // Emit a simple 'ret' instruction... appending it to the end of the basic
 178   // block
 179   BuildMI(BB, X86::RET, 0);
 180 }
 181
 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).
 186 ///
 187 void ISel::visitBranchInst(BranchInst &BI) {
 188   if (BI.isConditional())   // Only handles unconditional branches so far...
 189     visitInstruction(BI);
 190
 191   BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 192 }
 193
 194
 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.
 199 ///
 200 void
 201 ISel::visitShiftInst (ShiftInst & I)
 202 {
 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());
 208
 209   if (OperandClass > 2)
 210     visitInstruction(I); // Can't handle longs yet!
 211
 212   if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
 213     {
 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();
 217
 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
 223       };
 224
 225       const unsigned *OpTab = // Figure out the operand table to use
 226         ConstantOperand[isLeftShift*2+isOperandSigned];
 227
 228       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 229       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addZImm(shAmt);
 230     }
 231   else
 232     {
 233       // The shift amount is non-constant.
 234       //
 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
 237       // there first.
 238       //
 239
 240       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 241       BuildMI (BB, X86::MOVrr8, 2, X86::CL).addReg(getReg(I.getOperand(1)));
 242
 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
 249       };
 250
 251       const unsigned *OpTab = // Figure out the operand table to use
 252         NonConstantOperand[isLeftShift*2+isOperandSigned];
 253
 254       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addReg(X86::CL);
 255     }
 256 }
 257
 258
 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());
 264
 265   static const unsigned Opcodes[] = { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32 };
 266
 267   if (Class >= sizeof(Opcodes)/sizeof(Opcodes[0]))
 268     visitInstruction(B);  // Not handled class yet...
 269
 270   BuildMI(BB, Opcodes[Class], 2, DestReg).addReg(Op0r).addReg(Op1r);
 271
 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.
 276 }
 277
 278
 279
 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.
 283 ///
 284 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
 285   return new ISel(TM);
 286 }