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 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
  65     // Bitwise operators
  66     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
  67     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
  68     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
  69     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
  70
  71     // Binary comparison operators
  72
  73     // Other operators
  74     void visitShiftInst(ShiftInst &I);
  75     void visitPHINode(PHINode &I);
  76
  77     void visitInstruction(Instruction &I) {
  78       std::cerr << "Cannot instruction select: " << I;
  79       abort();
  80     }
  81
  82
  83     /// copyConstantToRegister - Output the instructions required to put the
  84     /// specified constant into the specified register.
  85     ///
  86     void copyConstantToRegister(Constant *C, unsigned Reg);
  87
  88     /// getReg - This method turns an LLVM value into a register number.  This
  89     /// is guaranteed to produce the same register number for a particular value
  90     /// every time it is queried.
  91     ///
  92     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
  93     unsigned getReg(Value *V) {
  94       unsigned &Reg = RegMap[V];
  95       if (Reg == 0)
  96         Reg = CurReg++;
  97
  98       // If this operand is a constant, emit the code to copy the constant into
  99       // the register here...
 100       //
 101       if (Constant *C = dyn_cast<Constant>(V))
 102         copyConstantToRegister(C, Reg);
 103
 104       return Reg;
 105     }
 106   };
 107 }
 108
 109 /// getClass - Turn a primitive type into a "class" number which is based on the
 110 /// size of the type, and whether or not it is floating point.
 111 ///
 112 static inline unsigned getClass(const Type *Ty) {
 113   switch (Ty->getPrimitiveID()) {
 114   case Type::SByteTyID:
 115   case Type::UByteTyID:   return 0;          // Byte operands are class #0
 116   case Type::ShortTyID:
 117   case Type::UShortTyID:  return 1;          // Short operands are class #1
 118   case Type::IntTyID:
 119   case Type::UIntTyID:
 120   case Type::PointerTyID: return 2;          // Int's and pointers are class #2
 121
 122   case Type::LongTyID:
 123   case Type::ULongTyID:   return 3;          // Longs are class #3
 124   case Type::FloatTyID:   return 4;          // Float is class #4
 125   case Type::DoubleTyID:  return 5;          // Doubles are class #5
 126   default:
 127     assert(0 && "Invalid type to getClass!");
 128     return 0;  // not reached
 129   }
 130 }
 131
 132 /// copyConstantToRegister - Output the instructions required to put the
 133 /// specified constant into the specified register.
 134 ///
 135 void ISel::copyConstantToRegister(Constant *C, unsigned R) {
 136   assert (!isa<ConstantExpr>(C) && "Constant expressions not yet handled!\n");
 137
 138   if (C->getType()->isIntegral()) {
 139     unsigned Class = getClass(C->getType());
 140     assert(Class != 3 && "Type not handled yet!");
 141
 142     static const unsigned IntegralOpcodeTab[] = {
 143       X86::MOVir8, X86::MOVir16, X86::MOVir32
 144     };
 145
 146     if (C->getType()->isSigned()) {
 147       ConstantSInt *CSI = cast<ConstantSInt>(C);
 148       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addSImm(CSI->getValue());
 149     } else {
 150       ConstantUInt *CUI = cast<ConstantUInt>(C);
 151       BuildMI(BB, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
 152     }
 153   } else {
 154     assert(0 && "Type not handled yet!");
 155   }
 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 /// visitSimpleBinary - Implement simple binary operators for integral types...
 196 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or,
 197 /// 4 for Xor.
 198 ///
 199 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
 200   if (B.getType() == Type::BoolTy)  // FIXME: Handle bools for logicals
 201     visitInstruction(B);
 202
 203   unsigned Class = getClass(B.getType());
 204   if (Class > 2)  // FIXME: Handle longs
 205     visitInstruction(B);
 206
 207   static const unsigned OpcodeTab[][4] = {
 208     // Arithmetic operators
 209     { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32, 0 },  // ADD
 210     { X86::SUBrr8, X86::SUBrr16, X86::SUBrr32, 0 },  // SUB
 211
 212     // Bitwise operators
 213     { X86::ANDrr8, X86::ANDrr16, X86::ANDrr32, 0 },  // AND
 214     { X86:: ORrr8, X86:: ORrr16, X86:: ORrr32, 0 },  // OR
 215     { X86::XORrr8, X86::XORrr16, X86::XORrr32, 0 },  // XOR
 216   };
 217
 218   unsigned Opcode = OpcodeTab[OperatorClass][Class];
 219   unsigned Op0r = getReg(B.getOperand(0));
 220   unsigned Op1r = getReg(B.getOperand(1));
 221   BuildMI(BB, Opcode, 2, getReg(B)).addReg(Op0r).addReg(Op1r);
 222 }
 223
 224
 225
 226 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
 227 /// for constant immediate shift values, and for constant immediate
 228 /// shift values equal to 1. Even the general case is sort of special,
 229 /// because the shift amount has to be in CL, not just any old register.
 230 ///
 231 void
 232 ISel::visitShiftInst (ShiftInst & I)
 233 {
 234   unsigned Op0r = getReg (I.getOperand (0));
 235   unsigned DestReg = getReg (I);
 236   bool isLeftShift = I.getOpcode() == Instruction::Shl;
 237   bool isOperandSigned = I.getType()->isUnsigned();
 238   unsigned OperandClass = getClass(I.getType());
 239
 240   if (OperandClass > 2)
 241     visitInstruction(I); // Can't handle longs yet!
 242
 243   if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
 244     {
 245       // The shift amount is constant, guaranteed to be a ubyte. Get its value.
 246       assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
 247       unsigned char shAmt = CUI->getValue();
 248
 249       static const unsigned ConstantOperand[][4] = {
 250         { X86::SHRir8, X86::SHRir16, X86::SHRir32, 0 },  // SHR
 251         { X86::SARir8, X86::SARir16, X86::SARir32, 0 },  // SAR
 252         { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 },  // SHL
 253         { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 },  // SAL = SHL
 254       };
 255
 256       const unsigned *OpTab = // Figure out the operand table to use
 257         ConstantOperand[isLeftShift*2+isOperandSigned];
 258
 259       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 260       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addZImm(shAmt);
 261     }
 262   else
 263     {
 264       // The shift amount is non-constant.
 265       //
 266       // In fact, you can only shift with a variable shift amount if
 267       // that amount is already in the CL register, so we have to put it
 268       // there first.
 269       //
 270
 271       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 272       BuildMI (BB, X86::MOVrr8, 2, X86::CL).addReg(getReg(I.getOperand(1)));
 273
 274       // This is a shift right (SHR).
 275       static const unsigned NonConstantOperand[][4] = {
 276         { X86::SHRrr8, X86::SHRrr16, X86::SHRrr32, 0 },  // SHR
 277         { X86::SARrr8, X86::SARrr16, X86::SARrr32, 0 },  // SAR
 278         { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 },  // SHL
 279         { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 },  // SAL = SHL
 280       };
 281
 282       const unsigned *OpTab = // Figure out the operand table to use
 283         NonConstantOperand[isLeftShift*2+isOperandSigned];
 284
 285       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addReg(X86::CL);
 286     }
 287 }
 288
 289 /// visitPHINode - Turn an LLVM PHI node into an X86 PHI node...
 290 ///
 291 void ISel::visitPHINode(PHINode &PN) {
 292   MachineInstr *MI = BuildMI(BB, X86::PHI, PN.getNumOperands(), getReg(PN));
 293
 294   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 295     // FIXME: This will put constants after the PHI nodes in the block, which
 296     // is invalid.  They should be put inline into the PHI node eventually.
 297     //
 298     MI->addRegOperand(getReg(PN.getIncomingValue(i)));
 299     MI->addPCDispOperand(PN.getIncomingBlock(i));
 300   }
 301 }
 302
 303
 304 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
 305 /// into a machine code representation is a very simple peep-hole fashion.  The
 306 /// generated code sucks but the implementation is nice and simple.
 307 ///
 308 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
 309   return new ISel(TM);
 310 }