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 /// SimpleLog2 - Compute and return Log2 of the input, valid only for inputs 1,
 147 /// 2, 4, & 8.  Used to convert operand size into dense classes.
 148 ///
 149 static inline unsigned SimpleLog2(unsigned N) {
 150   switch (N) {
 151   case 1: return 0;
 152   case 2: return 1;
 153   case 4: return 2;
 154   case 8: return 3;
 155   default: assert(0 && "Invalid operand to SimpleLog2!");
 156   }
 157   return 0;  // not reached
 158 }
 159
 160 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
 161 /// for constant immediate shift values, and for constant immediate
 162 /// shift values equal to 1. Even the general case is sort of special,
 163 /// because the shift amount has to be in CL, not just any old register.
 164 ///
 165 void
 166 ISel::visitShiftInst (ShiftInst & I)
 167 {
 168   unsigned Op0r = getReg (I.getOperand (0));
 169   unsigned DestReg = getReg (I);
 170   bool isRightShift = (I.getOpcode () == Instruction::Shr);
 171   bool isOperandUnsigned = I.getType ()->isUnsigned ();
 172   unsigned OperandClass = SimpleLog2(I.getType()->getPrimitiveSize());
 173
 174   if (ConstantUInt *CUI = dyn_cast <ConstantUInt> (I.getOperand (1)))
 175     {
 176       // The shift amount is constant, guaranteed to be a ubyte. Get its value.
 177       assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
 178       unsigned char shAmt = CUI->getValue();
 179
 180       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 181       if (isRightShift)
 182         {
 183           if (isOperandUnsigned)
 184             {
 185               // This is a shift right logical (SHR).
 186               switch (OperandClass)
 187                 {
 188                 case 0:
 189                   BuildMI (BB, X86::SHRir8, 2,
 190                            DestReg).addReg (Op0r).addZImm (shAmt);
 191                   break;
 192                 case 1:
 193                   BuildMI (BB, X86::SHRir16, 2,
 194                            DestReg).addReg (Op0r).addZImm (shAmt);
 195                   break;
 196                 case 2:
 197                   BuildMI (BB, X86::SHRir32, 2,
 198                            DestReg).addReg (Op0r).addZImm (shAmt);
 199                   break;
 200                 case 3:
 201                 default:
 202                   visitInstruction (I);
 203                   break;
 204                 }
 205             }
 206           else
 207             {
 208               // This is a shift right arithmetic (SAR).
 209               switch (OperandClass)
 210                 {
 211                 case 0:
 212                   BuildMI (BB, X86::SARir8, 2,
 213                            DestReg).addReg (Op0r).addZImm (shAmt);
 214                   break;
 215                 case 1:
 216                   BuildMI (BB, X86::SARir16, 2,
 217                            DestReg).addReg (Op0r).addZImm (shAmt);
 218                   break;
 219                 case 2:
 220                   BuildMI (BB, X86::SARir32, 2,
 221                            DestReg).addReg (Op0r).addZImm (shAmt);
 222                   break;
 223                 case 3:
 224                 default:
 225                   visitInstruction (I);
 226                   break;
 227                 }
 228             }
 229         }
 230       else
 231         {
 232           // This is a left shift (SHL).
 233           switch (OperandClass)
 234             {
 235             case 0:
 236               BuildMI (BB, X86::SHLir8, 2,
 237                        DestReg).addReg (Op0r).addZImm (shAmt);
 238               break;
 239             case 1:
 240               BuildMI (BB, X86::SHLir16, 2,
 241                        DestReg).addReg (Op0r).addZImm (shAmt);
 242               break;
 243             case 2:
 244               BuildMI (BB, X86::SHLir32, 2,
 245                        DestReg).addReg (Op0r).addZImm (shAmt);
 246               break;
 247             case 3:
 248             default:
 249               visitInstruction (I);
 250               break;
 251             }
 252         }
 253     }
 254   else
 255     {
 256       // The shift amount is non-constant.
 257       //
 258       // In fact, you can only shift with a variable shift amount if
 259       // that amount is already in the CL register, so we have to put it
 260       // there first.
 261       //
 262       // Get it from the register it's in.
 263       unsigned Op1r = getReg (I.getOperand (1));
 264       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 265       BuildMI (BB, X86::MOVrr8, 2, X86::CL).addReg (Op1r);
 266       // Emit: <insn> reg, cl       (shift-by-CL opcode; "rr" form.)
 267       if (isRightShift)
 268         {
 269           if (OperandClass)
 270             {
 271               // This is a shift right logical (SHR).
 272               switch (OperandClass)
 273                 {
 274                 case 0:
 275                   BuildMI (BB, X86::SHRrr8, 2,
 276                            DestReg).addReg (Op0r).addReg (X86::CL);
 277                   break;
 278                 case 1:
 279                   BuildMI (BB, X86::SHRrr16, 2,
 280                            DestReg).addReg (Op0r).addReg (X86::CL);
 281                   break;
 282                 case 2:
 283                   BuildMI (BB, X86::SHRrr32, 2,
 284                            DestReg).addReg (Op0r).addReg (X86::CL);
 285                   break;
 286                 case 3:
 287                 default:
 288                   visitInstruction (I);
 289                   break;
 290                 }
 291             }
 292           else
 293             {
 294               // This is a shift right arithmetic (SAR).
 295               switch (OperandClass)
 296                 {
 297                 case 0:
 298                   BuildMI (BB, X86::SARrr8, 2,
 299                            DestReg).addReg (Op0r).addReg (X86::CL);
 300                   break;
 301                 case 1:
 302                   BuildMI (BB, X86::SARrr16, 2,
 303                            DestReg).addReg (Op0r).addReg (X86::CL);
 304                   break;
 305                 case 2:
 306                   BuildMI (BB, X86::SARrr32, 2,
 307                            DestReg).addReg (Op0r).addReg (X86::CL);
 308                   break;
 309                 case 3:
 310                 default:
 311                   visitInstruction (I);
 312                   break;
 313                 }
 314             }
 315         }
 316       else
 317         {
 318           // This is a left shift (SHL).
 319           switch (OperandClass)
 320             {
 321             case 0:
 322               BuildMI (BB, X86::SHLrr8, 2,
 323                        DestReg).addReg (Op0r).addReg (X86::CL);
 324               break;
 325             case 1:
 326               BuildMI (BB, X86::SHLrr16, 2,
 327                        DestReg).addReg (Op0r).addReg (X86::CL);
 328               break;
 329             case 2:
 330               BuildMI (BB, X86::SHLrr32, 2,
 331                        DestReg).addReg (Op0r).addReg (X86::CL);
 332               break;
 333             case 3:
 334             default:
 335               visitInstruction (I);
 336               break;
 337             }
 338         }
 339     }
 340 }
 341
 342
 343 /// 'add' instruction - Simply turn this into an x86 reg,reg add instruction.
 344 void ISel::visitAdd(BinaryOperator &B) {
 345   unsigned Op0r = getReg(B.getOperand(0)), Op1r = getReg(B.getOperand(1));
 346   unsigned DestReg = getReg(B);
 347
 348   switch (B.getType()->getPrimitiveSize()) {
 349   case 1:   // UByte, SByte
 350     BuildMI(BB, X86::ADDrr8, 2, DestReg).addReg(Op0r).addReg(Op1r);
 351     break;
 352   case 2:   // UShort, Short
 353     BuildMI(BB, X86::ADDrr16, 2, DestReg).addReg(Op0r).addReg(Op1r);
 354     break;
 355   case 4:   // UInt, Int
 356     BuildMI(BB, X86::ADDrr32, 2, DestReg).addReg(Op0r).addReg(Op1r);
 357     break;
 358   case 8:   // ULong, Long
 359     // Here we have a pair of operands each occupying a pair of registers.
 360     // We need to do an ADDrr32 of the least-significant pair immediately
 361     // followed by an ADCrr32 (Add with Carry) of the most-significant pair.
 362     // I don't know how we are representing these multi-register arguments.
 363   default:
 364     visitInstruction(B);  // abort
 365   }
 366 }
 367
 368
 369
 370 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
 371 /// into a machine code representation is a very simple peep-hole fashion.  The
 372 /// generated code sucks but the implementation is nice and simple.
 373 ///
 374 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
 375   return new ISel(TM);
 376 }