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