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
  94 /// copyConstantToRegister - Output the instructions required to put the
  95 /// specified constant into the specified register.
  96 ///
  97 void ISel::copyConstantToRegister(Constant *C, unsigned R) {
  98   assert (!isa<ConstantExpr>(C) && "Constant expressions not yet handled!\n");
  99
 100   switch (C->getType()->getPrimitiveID()) {
 101   case Type::SByteTyID:
 102     BuildMI(BB, X86::MOVir8, 1, R).addSImm(cast<ConstantSInt>(C)->getValue());
 103     break;
 104   case Type::UByteTyID:
 105     BuildMI(BB, X86::MOVir8, 1, R).addZImm(cast<ConstantUInt>(C)->getValue());
 106     break;
 107   case Type::ShortTyID:
 108     BuildMI(BB, X86::MOVir16, 1, R).addSImm(cast<ConstantSInt>(C)->getValue());
 109     break;
 110   case Type::UShortTyID:
 111     BuildMI(BB, X86::MOVir16, 1, R).addZImm(cast<ConstantUInt>(C)->getValue());
 112     break;
 113   case Type::IntTyID:
 114     BuildMI(BB, X86::MOVir32, 1, R).addSImm(cast<ConstantSInt>(C)->getValue());
 115     break;
 116   case Type::UIntTyID:
 117     BuildMI(BB, X86::MOVir32, 1, R).addZImm(cast<ConstantUInt>(C)->getValue());
 118     break;
 119   default: assert(0 && "Type not handled yet!");
 120   }
 121 }
 122
 123
 124 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 125 /// we have the following possibilities:
 126 ///
 127 ///   ret void: No return value, simply emit a 'ret' instruction
 128 ///   ret sbyte, ubyte : Extend value into EAX and return
 129 ///   ret short, ushort: Extend value into EAX and return
 130 ///   ret int, uint    : Move value into EAX and return
 131 ///   ret pointer      : Move value into EAX and return
 132 ///   ret long, ulong  : Move value into EAX/EDX (?) and return
 133 ///   ret float/double : ?  Top of FP stack?  XMM0?
 134 ///
 135 void ISel::visitReturnInst(ReturnInst &I) {
 136   if (I.getNumOperands() != 0) {  // Not 'ret void'?
 137     // Move result into a hard register... then emit a ret
 138     visitInstruction(I);  // abort
 139   }
 140
 141   // Emit a simple 'ret' instruction... appending it to the end of the basic
 142   // block
 143   BuildMI(BB, X86::RET, 0);
 144 }
 145
 146 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
 147 /// for constant immediate shift values, and for constant immediate
 148 /// shift values equal to 1. Even the general case is sort of special,
 149 /// because the shift amount has to be in CL, not just any old register.
 150 ///
 151 void
 152 ISel::visitShiftInst (ShiftInst & I)
 153 {
 154   unsigned Op0r = getReg (I.getOperand (0));
 155   unsigned DestReg = getReg (I);
 156   unsigned operandSize = I.getType ()->getPrimitiveSize ();
 157   bool isRightShift = (I.getOpcode () == Instruction::Shr);
 158   bool isOperandUnsigned = I.getType ()->isUnsigned ();
 159
 160   if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
 161     {
 162       // The shift amount is constant, guaranteed to be a ubyte. Get its value.
 163       assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
 164       unsigned char shAmt = CUI->getValue();
 165
 166       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 167       if (isRightShift)
 168         {
 169           if (isOperandUnsigned)
 170             {
 171               // This is a shift right logical (SHR).
 172               switch (operandSize)
 173                 {
 174                 case 1:
 175                   BuildMI (BB, X86::SHRir8, 2,
 176                            DestReg).addReg (Op0r).addZImm (shAmt);
 177                   break;
 178                 case 2:
 179                   BuildMI (BB, X86::SHRir16, 2,
 180                            DestReg).addReg (Op0r).addZImm (shAmt);
 181                   break;
 182                 case 4:
 183                   BuildMI (BB, X86::SHRir32, 2,
 184                            DestReg).addReg (Op0r).addZImm (shAmt);
 185                   break;
 186                 case 8:
 187                 default:
 188                   visitInstruction (I);
 189                   break;
 190                 }
 191             }
 192           else
 193             {
 194               // This is a shift right arithmetic (SAR).
 195               switch (operandSize)
 196                 {
 197                 case 1:
 198                   BuildMI (BB, X86::SARir8, 2,
 199                            DestReg).addReg (Op0r).addZImm (shAmt);
 200                   break;
 201                 case 2:
 202                   BuildMI (BB, X86::SARir16, 2,
 203                            DestReg).addReg (Op0r).addZImm (shAmt);
 204                   break;
 205                 case 4:
 206                   BuildMI (BB, X86::SARir32, 2,
 207                            DestReg).addReg (Op0r).addZImm (shAmt);
 208                   break;
 209                 case 8:
 210                 default:
 211                   visitInstruction (I);
 212                   break;
 213                 }
 214             }
 215         }
 216       else
 217         {
 218           // This is a left shift (SHL).
 219           switch (operandSize)
 220             {
 221             case 1:
 222               BuildMI (BB, X86::SHLir8, 2,
 223                        DestReg).addReg (Op0r).addZImm (shAmt);
 224               break;
 225             case 2:
 226               BuildMI (BB, X86::SHLir16, 2,
 227                        DestReg).addReg (Op0r).addZImm (shAmt);
 228               break;
 229             case 4:
 230               BuildMI (BB, X86::SHLir32, 2,
 231                        DestReg).addReg (Op0r).addZImm (shAmt);
 232               break;
 233             case 8:
 234             default:
 235               visitInstruction (I);
 236               break;
 237             }
 238         }
 239     }
 240   else
 241     {
 242       // The shift amount is non-constant.
 243       //
 244       // In fact, you can only shift with a variable shift amount if
 245       // that amount is already in the CL register, so we have to put it
 246       // there first.
 247       //
 248       // Get it from the register it's in.
 249       unsigned Op1r = getReg (I.getOperand (1));
 250       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 251       BuildMI (BB, X86::MOVrr8, 2, X86::CL).addReg (Op1r);
 252       // Emit: <insn> reg, cl       (shift-by-CL opcode; "rr" form.)
 253       if (isRightShift)
 254         {
 255           if (isOperandUnsigned)
 256             {
 257               // This is a shift right logical (SHR).
 258               switch (operandSize)
 259                 {
 260                 case 1:
 261                   BuildMI (BB, X86::SHRrr8, 2,
 262                            DestReg).addReg (Op0r).addReg (X86::CL);
 263                   break;
 264                 case 2:
 265                   BuildMI (BB, X86::SHRrr16, 2,
 266                            DestReg).addReg (Op0r).addReg (X86::CL);
 267                   break;
 268                 case 4:
 269                   BuildMI (BB, X86::SHRrr32, 2,
 270                            DestReg).addReg (Op0r).addReg (X86::CL);
 271                   break;
 272                 case 8:
 273                 default:
 274                   visitInstruction (I);
 275                   break;
 276                 }
 277             }
 278           else
 279             {
 280               // This is a shift right arithmetic (SAR).
 281               switch (operandSize)
 282                 {
 283                 case 1:
 284                   BuildMI (BB, X86::SARrr8, 2,
 285                            DestReg).addReg (Op0r).addReg (X86::CL);
 286                   break;
 287                 case 2:
 288                   BuildMI (BB, X86::SARrr16, 2,
 289                            DestReg).addReg (Op0r).addReg (X86::CL);
 290                   break;
 291                 case 4:
 292                   BuildMI (BB, X86::SARrr32, 2,
 293                            DestReg).addReg (Op0r).addReg (X86::CL);
 294                   break;
 295                 case 8:
 296                 default:
 297                   visitInstruction (I);
 298                   break;
 299                 }
 300             }
 301         }
 302       else
 303         {
 304           // This is a left shift (SHL).
 305           switch (operandSize)
 306             {
 307             case 1:
 308               BuildMI (BB, X86::SHLrr8, 2,
 309                        DestReg).addReg (Op0r).addReg (X86::CL);
 310               break;
 311             case 2:
 312               BuildMI (BB, X86::SHLrr16, 2,
 313                        DestReg).addReg (Op0r).addReg (X86::CL);
 314               break;
 315             case 4:
 316               BuildMI (BB, X86::SHLrr32, 2,
 317                        DestReg).addReg (Op0r).addReg (X86::CL);
 318               break;
 319             case 8:
 320             default:
 321               visitInstruction (I);
 322               break;
 323             }
 324         }
 325     }
 326 }
 327
 328
 329 /// 'add' instruction - Simply turn this into an x86 reg,reg add instruction.
 330 void ISel::visitAdd(BinaryOperator &B) {
 331   unsigned Op0r = getReg(B.getOperand(0)), Op1r = getReg(B.getOperand(1));
 332   unsigned DestReg = getReg(B);
 333
 334   switch (B.getType()->getPrimitiveSize()) {
 335   case 1:   // UByte, SByte
 336     BuildMI(BB, X86::ADDrr8, 2, DestReg).addReg(Op0r).addReg(Op1r);
 337     break;
 338   case 2:   // UShort, Short
 339     BuildMI(BB, X86::ADDrr16, 2, DestReg).addReg(Op0r).addReg(Op1r);
 340     break;
 341   case 4:   // UInt, Int
 342     BuildMI(BB, X86::ADDrr32, 2, DestReg).addReg(Op0r).addReg(Op1r);
 343     break;
 344   case 8:   // ULong, Long
 345     // Here we have a pair of operands each occupying a pair of registers.
 346     // We need to do an ADDrr32 of the least-significant pair immediately
 347     // followed by an ADCrr32 (Add with Carry) of the most-significant pair.
 348     // I don't know how we are representing these multi-register arguments.
 349   default:
 350     visitInstruction(B);  // abort
 351   }
 352 }
 353
 354
 355
 356 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
 357 /// into a machine code representation is a very simple peep-hole fashion.  The
 358 /// generated code sucks but the implementation is nice and simple.
 359 ///
 360 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
 361   return new ISel(TM);
 362 }