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 "X86InstrBuilder.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/iTerminators.h"
  12 #include "llvm/iOperators.h"
  13 #include "llvm/iOther.h"
  14 #include "llvm/iPHINode.h"
  15 #include "llvm/iMemory.h"
  16 #include "llvm/Type.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/SSARegMap.h"
  23 #include "llvm/CodeGen/FunctionFrameInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Support/InstVisitor.h"
  26 #include "llvm/Target/MRegisterInfo.h"
  27 #include <map>
  28
  29 /// BMI - A special BuildMI variant that takes an iterator to insert the
  30 /// instruction at as well as a basic block.
  31 /// this is the version for when you have a destination register in mind.
  32 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  33                                       MachineBasicBlock::iterator &I,
  34                                       MachineOpCode Opcode,
  35                                       unsigned NumOperands,
  36                                       unsigned DestReg) {
  37   assert(I >= MBB->begin() && I <= MBB->end() && "Bad iterator!");
  38   MachineInstr *MI = new MachineInstr(Opcode, NumOperands+1, true, true);
  39   I = MBB->insert(I, MI)+1;
  40   return MachineInstrBuilder(MI).addReg(DestReg, MOTy::Def);
  41 }
  42
  43 /// BMI - A special BuildMI variant that takes an iterator to insert the
  44 /// instruction at as well as a basic block.
  45 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  46                                       MachineBasicBlock::iterator &I,
  47                                       MachineOpCode Opcode,
  48                                       unsigned NumOperands) {
  49   assert(I > MBB->begin() && I <= MBB->end() && "Bad iterator!");
  50   MachineInstr *MI = new MachineInstr(Opcode, NumOperands, true, true);
  51   I = MBB->insert(I, MI)+1;
  52   return MachineInstrBuilder(MI);
  53 }
  54
  55
  56 namespace {
  57   struct ISel : public FunctionPass, InstVisitor<ISel> {
  58     TargetMachine &TM;
  59     MachineFunction *F;                    // The function we are compiling into
  60     MachineBasicBlock *BB;                 // The current MBB we are compiling
  61
  62     unsigned CurReg;
  63     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  64
  65     // MBBMap - Mapping between LLVM BB -> Machine BB
  66     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  67
  68     ISel(TargetMachine &tm)
  69       : TM(tm), F(0), BB(0), CurReg(MRegisterInfo::FirstVirtualRegister) {}
  70
  71     /// runOnFunction - Top level implementation of instruction selection for
  72     /// the entire function.
  73     ///
  74     bool runOnFunction(Function &Fn) {
  75       F = &MachineFunction::construct(&Fn, TM);
  76
  77       // Create all of the machine basic blocks for the function...
  78       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  79         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
  80
  81       BB = &F->front();
  82       LoadArgumentsToVirtualRegs(Fn);
  83
  84       // Instruction select everything except PHI nodes
  85       visit(Fn);
  86
  87       // Select the PHI nodes
  88       SelectPHINodes();
  89
  90       RegMap.clear();
  91       MBBMap.clear();
  92       CurReg = MRegisterInfo::FirstVirtualRegister;
  93       F = 0;
  94       return false;  // We never modify the LLVM itself.
  95     }
  96
  97     virtual const char *getPassName() const {
  98       return "X86 Simple Instruction Selection";
  99     }
 100
 101     /// visitBasicBlock - This method is called when we are visiting a new basic
 102     /// block.  This simply creates a new MachineBasicBlock to emit code into
 103     /// and adds it to the current MachineFunction.  Subsequent visit* for
 104     /// instructions will be invoked for all instructions in the basic block.
 105     ///
 106     void visitBasicBlock(BasicBlock &LLVM_BB) {
 107       BB = MBBMap[&LLVM_BB];
 108     }
 109
 110     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 111     /// from the stack into virtual registers.
 112     ///
 113     void LoadArgumentsToVirtualRegs(Function &F);
 114
 115     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 116     /// because we have to generate our sources into the source basic blocks,
 117     /// not the current one.
 118     ///
 119     void SelectPHINodes();
 120
 121     // Visitation methods for various instructions.  These methods simply emit
 122     // fixed X86 code for each instruction.
 123     //
 124
 125     // Control flow operators
 126     void visitReturnInst(ReturnInst &RI);
 127     void visitBranchInst(BranchInst &BI);
 128     void visitCallInst(CallInst &I);
 129
 130     // Arithmetic operators
 131     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 132     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 133     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 134     void doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI,
 135                     unsigned destReg, const Type *resultType,
 136                     unsigned op0Reg, unsigned op1Reg);
 137     void visitMul(BinaryOperator &B);
 138
 139     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 140     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 141     void visitDivRem(BinaryOperator &B);
 142
 143     // Bitwise operators
 144     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 145     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 146     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 147
 148     // Binary comparison operators
 149     void visitSetCCInst(SetCondInst &I, unsigned OpNum);
 150     void visitSetEQ(SetCondInst &I) { visitSetCCInst(I, 0); }
 151     void visitSetNE(SetCondInst &I) { visitSetCCInst(I, 1); }
 152     void visitSetLT(SetCondInst &I) { visitSetCCInst(I, 2); }
 153     void visitSetGT(SetCondInst &I) { visitSetCCInst(I, 3); }
 154     void visitSetLE(SetCondInst &I) { visitSetCCInst(I, 4); }
 155     void visitSetGE(SetCondInst &I) { visitSetCCInst(I, 5); }
 156
 157     // Memory Instructions
 158     void visitLoadInst(LoadInst &I);
 159     void visitStoreInst(StoreInst &I);
 160     void visitGetElementPtrInst(GetElementPtrInst &I);
 161     void visitAllocaInst(AllocaInst &I);
 162
 163     // We assume that by this point, malloc instructions have been
 164     // lowered to calls, and dlsym will magically find malloc for us.
 165     void visitMallocInst(MallocInst &I) { visitInstruction (I); }
 166     void visitFreeInst(FreeInst &I) { visitInstruction(I); }
 167
 168     // Other operators
 169     void visitShiftInst(ShiftInst &I);
 170     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 171     void visitCastInst(CastInst &I);
 172
 173     void visitInstruction(Instruction &I) {
 174       std::cerr << "Cannot instruction select: " << I;
 175       abort();
 176     }
 177
 178     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 179     void promote32 (const unsigned targetReg, Value *v);
 180
 181     // emitGEPOperation - Common code shared between visitGetElementPtrInst and
 182     // constant expression GEP support.
 183     //
 184     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator&IP,
 185                           Value *Src, User::op_iterator IdxBegin,
 186                           User::op_iterator IdxEnd, unsigned TargetReg);
 187
 188     /// copyConstantToRegister - Output the instructions required to put the
 189     /// specified constant into the specified register.
 190     ///
 191     void copyConstantToRegister(MachineBasicBlock *MBB,
 192                                 MachineBasicBlock::iterator &MBBI,
 193                                 Constant *C, unsigned Reg);
 194
 195     /// makeAnotherReg - This method returns the next register number
 196     /// we haven't yet used.
 197     unsigned makeAnotherReg(const Type *Ty) {
 198       // Add the mapping of regnumber => reg class to MachineFunction
 199       const TargetRegisterClass *RC =
 200         TM.getRegisterInfo()->getRegClassForType(Ty);
 201       F->getSSARegMap()->addRegMap(CurReg, RC);
 202       return CurReg++;
 203     }
 204
 205     /// getReg - This method turns an LLVM value into a register number.  This
 206     /// is guaranteed to produce the same register number for a particular value
 207     /// every time it is queried.
 208     ///
 209     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 210     unsigned getReg(Value *V) {
 211       // Just append to the end of the current bb.
 212       MachineBasicBlock::iterator It = BB->end();
 213       return getReg(V, BB, It);
 214     }
 215     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 216                     MachineBasicBlock::iterator &IPt) {
 217       unsigned &Reg = RegMap[V];
 218       if (Reg == 0) {
 219         Reg = makeAnotherReg(V->getType());
 220         RegMap[V] = Reg;
 221       }
 222
 223       // If this operand is a constant, emit the code to copy the constant into
 224       // the register here...
 225       //
 226       if (Constant *C = dyn_cast<Constant>(V)) {
 227         copyConstantToRegister(MBB, IPt, C, Reg);
 228         RegMap.erase(V);  // Assign a new name to this constant if ref'd again
 229       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 230         // Move the address of the global into the register
 231         BMI(MBB, IPt, X86::MOVir32, 1, Reg).addReg(GV);
 232         RegMap.erase(V);  // Assign a new name to this address if ref'd again
 233       }
 234
 235       return Reg;
 236     }
 237   };
 238 }
 239
 240 /// TypeClass - Used by the X86 backend to group LLVM types by their basic X86
 241 /// Representation.
 242 ///
 243 enum TypeClass {
 244   cByte, cShort, cInt, cFP, cLong
 245 };
 246
 247 /// getClass - Turn a primitive type into a "class" number which is based on the
 248 /// size of the type, and whether or not it is floating point.
 249 ///
 250 static inline TypeClass getClass(const Type *Ty) {
 251   switch (Ty->getPrimitiveID()) {
 252   case Type::SByteTyID:
 253   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
 254   case Type::ShortTyID:
 255   case Type::UShortTyID:  return cShort;     // Short operands are class #1
 256   case Type::IntTyID:
 257   case Type::UIntTyID:
 258   case Type::PointerTyID: return cInt;       // Int's and pointers are class #2
 259
 260   case Type::FloatTyID:
 261   case Type::DoubleTyID:  return cFP;        // Floating Point is #3
 262   case Type::LongTyID:
 263   case Type::ULongTyID:   //return cLong;      // Longs are class #3
 264     return cInt;          // FIXME: LONGS ARE TREATED AS INTS!
 265   default:
 266     assert(0 && "Invalid type to getClass!");
 267     return cByte;  // not reached
 268   }
 269 }
 270
 271 // getClassB - Just like getClass, but treat boolean values as bytes.
 272 static inline TypeClass getClassB(const Type *Ty) {
 273   if (Ty == Type::BoolTy) return cByte;
 274   return getClass(Ty);
 275 }
 276
 277
 278 /// copyConstantToRegister - Output the instructions required to put the
 279 /// specified constant into the specified register.
 280 ///
 281 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 282                                   MachineBasicBlock::iterator &IP,
 283                                   Constant *C, unsigned R) {
 284   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 285     if (CE->getOpcode() == Instruction::GetElementPtr) {
 286       emitGEPOperation(MBB, IP, CE->getOperand(0),
 287                        CE->op_begin()+1, CE->op_end(), R);
 288       return;
 289     }
 290
 291     std::cerr << "Offending expr: " << C << "\n";
 292     assert(0 && "Constant expressions not yet handled!\n");
 293   }
 294
 295   if (C->getType()->isIntegral()) {
 296     unsigned Class = getClassB(C->getType());
 297     assert(Class <= cInt && "Type not handled yet!");
 298
 299     static const unsigned IntegralOpcodeTab[] = {
 300       X86::MOVir8, X86::MOVir16, X86::MOVir32
 301     };
 302
 303     if (C->getType() == Type::BoolTy) {
 304       BMI(MBB, IP, X86::MOVir8, 1, R).addZImm(C == ConstantBool::True);
 305     } else if (C->getType()->isSigned()) {
 306       ConstantSInt *CSI = cast<ConstantSInt>(C);
 307       BMI(MBB, IP, IntegralOpcodeTab[Class], 1, R).addSImm(CSI->getValue());
 308     } else {
 309       ConstantUInt *CUI = cast<ConstantUInt>(C);
 310       BMI(MBB, IP, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
 311     }
 312   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 313     double Value = CFP->getValue();
 314     if (Value == +0.0)
 315       BMI(MBB, IP, X86::FLD0, 0, R);
 316     else if (Value == +1.0)
 317       BMI(MBB, IP, X86::FLD1, 0, R);
 318     else {
 319       std::cerr << "Cannot load constant '" << Value << "'!\n";
 320       assert(0);
 321     }
 322
 323   } else if (isa<ConstantPointerNull>(C)) {
 324     // Copy zero (null pointer) to the register.
 325     BMI(MBB, IP, X86::MOVir32, 1, R).addZImm(0);
 326   } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 327     unsigned SrcReg = getReg(CPR->getValue(), MBB, IP);
 328     BMI(MBB, IP, X86::MOVrr32, 1, R).addReg(SrcReg);
 329   } else {
 330     std::cerr << "Offending constant: " << C << "\n";
 331     assert(0 && "Type not handled yet!");
 332   }
 333 }
 334
 335 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 336 /// the stack into virtual registers.
 337 ///
 338 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 339   // Emit instructions to load the arguments...  On entry to a function on the
 340   // X86, the stack frame looks like this:
 341   //
 342   // [ESP] -- return address
 343   // [ESP + 4] -- first argument (leftmost lexically) if four bytes in size
 344   // [ESP + 8] -- second argument, if four bytes in size
 345   //    ...
 346   //
 347   unsigned ArgOffset = 0;
 348   FunctionFrameInfo *FFI = F->getFrameInfo();
 349
 350   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 351     unsigned Reg = getReg(*I);
 352
 353     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 354     int FI;          // Frame object index
 355
 356     switch (getClassB(I->getType())) {
 357     case cByte:
 358       FI = FFI->CreateFixedObject(1, ArgOffset);
 359       addFrameReference(BuildMI(BB, X86::MOVmr8, 4, Reg), FI);
 360       break;
 361     case cShort:
 362       FI = FFI->CreateFixedObject(2, ArgOffset);
 363       addFrameReference(BuildMI(BB, X86::MOVmr16, 4, Reg), FI);
 364       break;
 365     case cInt:
 366       FI = FFI->CreateFixedObject(4, ArgOffset);
 367       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg), FI);
 368       break;
 369     case cFP:
 370       unsigned Opcode;
 371       if (I->getType() == Type::FloatTy) {
 372         Opcode = X86::FLDr32;
 373         FI = FFI->CreateFixedObject(4, ArgOffset);
 374       } else {
 375         Opcode = X86::FLDr64;
 376         ArgOffset += 4;   // doubles require 4 additional bytes
 377         FI = FFI->CreateFixedObject(8, ArgOffset);
 378       }
 379       addFrameReference(BuildMI(BB, Opcode, 4, Reg), FI);
 380       break;
 381     default:
 382       assert(0 && "Unhandled argument type!");
 383     }
 384   }
 385 }
 386
 387
 388 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 389 /// because we have to generate our sources into the source basic blocks, not
 390 /// the current one.
 391 ///
 392 void ISel::SelectPHINodes() {
 393   const Function &LF = *F->getFunction();  // The LLVM function...
 394   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 395     const BasicBlock *BB = I;
 396     MachineBasicBlock *MBB = MBBMap[I];
 397
 398     // Loop over all of the PHI nodes in the LLVM basic block...
 399     unsigned NumPHIs = 0;
 400     for (BasicBlock::const_iterator I = BB->begin();
 401          PHINode *PN = (PHINode*)dyn_cast<PHINode>(&*I); ++I) {
 402       // Create a new machine instr PHI node, and insert it.
 403       MachineInstr *MI = BuildMI(X86::PHI, PN->getNumOperands(), getReg(*PN));
 404       MBB->insert(MBB->begin()+NumPHIs++, MI); // Insert it at the top of the BB
 405
 406       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 407         MachineBasicBlock *PredMBB = MBBMap[PN->getIncomingBlock(i)];
 408
 409         // Get the incoming value into a virtual register.  If it is not already
 410         // available in a virtual register, insert the computation code into
 411         // PredMBB
 412         //
 413         // FIXME: This should insert the code into the BOTTOM of the block, not
 414         // the top of the block.  This just makes for huge live ranges...
 415         MachineBasicBlock::iterator PI = PredMBB->begin();
 416         while ((*PI)->getOpcode() == X86::PHI) ++PI;
 417
 418         MI->addRegOperand(getReg(PN->getIncomingValue(i), PredMBB, PI));
 419         MI->addMachineBasicBlockOperand(PredMBB);
 420       }
 421     }
 422   }
 423 }
 424
 425
 426
 427 /// SetCC instructions - Here we just emit boilerplate code to set a byte-sized
 428 /// register, then move it to wherever the result should be.
 429 /// We handle FP setcc instructions by pushing them, doing a
 430 /// compare-and-pop-twice, and then copying the concodes to the main
 431 /// processor's concodes (I didn't make this up, it's in the Intel manual)
 432 ///
 433 void ISel::visitSetCCInst(SetCondInst &I, unsigned OpNum) {
 434   // The arguments are already supposed to be of the same type.
 435   const Type *CompTy = I.getOperand(0)->getType();
 436   unsigned reg1 = getReg(I.getOperand(0));
 437   unsigned reg2 = getReg(I.getOperand(1));
 438
 439   unsigned Class = getClass(CompTy);
 440   switch (Class) {
 441     // Emit: cmp <var1>, <var2> (do the comparison).  We can
 442     // compare 8-bit with 8-bit, 16-bit with 16-bit, 32-bit with
 443     // 32-bit.
 444   case cByte:
 445     BuildMI (BB, X86::CMPrr8, 2).addReg (reg1).addReg (reg2);
 446     break;
 447   case cShort:
 448     BuildMI (BB, X86::CMPrr16, 2).addReg (reg1).addReg (reg2);
 449     break;
 450   case cInt:
 451     BuildMI (BB, X86::CMPrr32, 2).addReg (reg1).addReg (reg2);
 452     break;
 453
 454 #if 0
 455     // Push the variables on the stack with fldl opcodes.
 456     // FIXME: assuming var1, var2 are in memory, if not, spill to
 457     // stack first
 458   case cFP:  // Floats
 459     BuildMI (BB, X86::FLDr32, 1).addReg (reg1);
 460     BuildMI (BB, X86::FLDr32, 1).addReg (reg2);
 461     break;
 462   case cFP (doubles):  // Doubles
 463     BuildMI (BB, X86::FLDr64, 1).addReg (reg1);
 464     BuildMI (BB, X86::FLDr64, 1).addReg (reg2);
 465     break;
 466 #endif
 467   case cLong:
 468   default:
 469     visitInstruction(I);
 470   }
 471
 472 #if 0
 473   if (CompTy->isFloatingPoint()) {
 474     // (Non-trapping) compare and pop twice.
 475     BuildMI (BB, X86::FUCOMPP, 0);
 476     // Move fp status word (concodes) to ax.
 477     BuildMI (BB, X86::FNSTSWr8, 1, X86::AX);
 478     // Load real concodes from ax.
 479     BuildMI (BB, X86::SAHF, 1).addReg(X86::AH);
 480   }
 481 #endif
 482
 483   // Emit setOp instruction (extract concode; clobbers ax),
 484   // using the following mapping:
 485   // LLVM  -> X86 signed  X86 unsigned
 486   // -----    -----       -----
 487   // seteq -> sete        sete
 488   // setne -> setne       setne
 489   // setlt -> setl        setb
 490   // setgt -> setg        seta
 491   // setle -> setle       setbe
 492   // setge -> setge       setae
 493
 494   static const unsigned OpcodeTab[2][6] = {
 495     {X86::SETEr, X86::SETNEr, X86::SETBr, X86::SETAr, X86::SETBEr, X86::SETAEr},
 496     {X86::SETEr, X86::SETNEr, X86::SETLr, X86::SETGr, X86::SETLEr, X86::SETGEr},
 497   };
 498
 499   BuildMI(BB, OpcodeTab[CompTy->isSigned()][OpNum], 0, getReg(I));
 500 }
 501
 502 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
 503 /// operand, in the specified target register.
 504 void ISel::promote32 (unsigned targetReg, Value *v) {
 505   unsigned vReg = getReg(v);
 506   bool isUnsigned = v->getType()->isUnsigned();
 507   switch (getClass(v->getType())) {
 508   case cByte:
 509     // Extend value into target register (8->32)
 510     if (isUnsigned)
 511       BuildMI(BB, X86::MOVZXr32r8, 1, targetReg).addReg(vReg);
 512     else
 513       BuildMI(BB, X86::MOVSXr32r8, 1, targetReg).addReg(vReg);
 514     break;
 515   case cShort:
 516     // Extend value into target register (16->32)
 517     if (isUnsigned)
 518       BuildMI(BB, X86::MOVZXr32r16, 1, targetReg).addReg(vReg);
 519     else
 520       BuildMI(BB, X86::MOVSXr32r16, 1, targetReg).addReg(vReg);
 521     break;
 522   case cInt:
 523     // Move value into target register (32->32)
 524     BuildMI(BB, X86::MOVrr32, 1, targetReg).addReg(vReg);
 525     break;
 526   default:
 527     assert(0 && "Unpromotable operand class in promote32");
 528   }
 529 }
 530
 531 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 532 /// we have the following possibilities:
 533 ///
 534 ///   ret void: No return value, simply emit a 'ret' instruction
 535 ///   ret sbyte, ubyte : Extend value into EAX and return
 536 ///   ret short, ushort: Extend value into EAX and return
 537 ///   ret int, uint    : Move value into EAX and return
 538 ///   ret pointer      : Move value into EAX and return
 539 ///   ret long, ulong  : Move value into EAX/EDX and return
 540 ///   ret float/double : Top of FP stack
 541 ///
 542 void ISel::visitReturnInst (ReturnInst &I) {
 543   if (I.getNumOperands() == 0) {
 544     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
 545     return;
 546   }
 547
 548   Value *RetVal = I.getOperand(0);
 549   switch (getClass(RetVal->getType())) {
 550   case cByte:   // integral return values: extend or move into EAX and return
 551   case cShort:
 552   case cInt:
 553     promote32(X86::EAX, RetVal);
 554     break;
 555   case cFP:                   // Floats & Doubles: Return in ST(0)
 556     BuildMI(BB, X86::FpMOV, 1, X86::ST0).addReg(getReg(RetVal));
 557     break;
 558   case cLong:
 559     // ret long: use EAX(least significant 32 bits)/EDX (most
 560     // significant 32)...
 561   default:
 562     visitInstruction (I);
 563   }
 564   // Emit a 'ret' instruction
 565   BuildMI(BB, X86::RET, 0);
 566 }
 567
 568 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
 569 /// that since code layout is frozen at this point, that if we are trying to
 570 /// jump to a block that is the immediate successor of the current block, we can
 571 /// just make a fall-through. (but we don't currently).
 572 ///
 573 void ISel::visitBranchInst(BranchInst &BI) {
 574   if (BI.isConditional()) {
 575     BasicBlock *ifTrue  = BI.getSuccessor(0);
 576     BasicBlock *ifFalse = BI.getSuccessor(1);
 577
 578     // Compare condition with zero, followed by jump-if-equal to ifFalse, and
 579     // jump-if-nonequal to ifTrue
 580     unsigned condReg = getReg(BI.getCondition());
 581     BuildMI(BB, X86::CMPri8, 2).addReg(condReg).addZImm(0);
 582     BuildMI(BB, X86::JNE, 1).addPCDisp(BI.getSuccessor(0));
 583     BuildMI(BB, X86::JE, 1).addPCDisp(BI.getSuccessor(1));
 584   } else { // unconditional branch
 585     BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 586   }
 587 }
 588
 589 /// visitCallInst - Push args on stack and do a procedure call instruction.
 590 void ISel::visitCallInst(CallInst &CI) {
 591   // Count how many bytes are to be pushed on the stack...
 592   unsigned NumBytes = 0;
 593
 594   if (CI.getNumOperands() > 1) {
 595     for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
 596       switch (getClass(CI.getOperand(i)->getType())) {
 597       case cByte: case cShort: case cInt:
 598         NumBytes += 4;
 599         break;
 600       case cLong:
 601         NumBytes += 8;
 602         break;
 603       case cFP:
 604         NumBytes += CI.getOperand(i)->getType() == Type::FloatTy ? 4 : 8;
 605         break;
 606       default: assert(0 && "Unknown class!");
 607       }
 608
 609     // Adjust the stack pointer for the new arguments...
 610     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(NumBytes);
 611
 612     // Arguments go on the stack in reverse order, as specified by the ABI.
 613     unsigned ArgOffset = 0;
 614     for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i) {
 615       Value *Arg = CI.getOperand(i);
 616       switch (getClass(Arg->getType())) {
 617       case cByte:
 618       case cShort: {
 619         // Promote arg to 32 bits wide into a temporary register...
 620         unsigned R = makeAnotherReg(Type::UIntTy);
 621         promote32(R, Arg);
 622         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 623                      X86::ESP, ArgOffset).addReg(R);
 624         break;
 625       }
 626       case cInt:
 627         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 628                      X86::ESP, ArgOffset).addReg(getReg(Arg));
 629         break;
 630
 631       case cFP:
 632         if (Arg->getType() == Type::FloatTy) {
 633           addRegOffset(BuildMI(BB, X86::FSTr32, 5),
 634                        X86::ESP, ArgOffset).addReg(getReg(Arg));
 635         } else {
 636           assert(Arg->getType() == Type::DoubleTy && "Unknown FP type!");
 637           ArgOffset += 4;
 638           addRegOffset(BuildMI(BB, X86::FSTr32, 5),
 639                        X86::ESP, ArgOffset).addReg(getReg(Arg));
 640         }
 641         break;
 642
 643       default:
 644         // FIXME: long/ulong/float/double args not handled.
 645         visitInstruction(CI);
 646         break;
 647       }
 648       ArgOffset += 4;
 649     }
 650   }
 651
 652   if (Function *F = CI.getCalledFunction()) {
 653     // Emit a CALL instruction with PC-relative displacement.
 654     BuildMI(BB, X86::CALLpcrel32, 1).addPCDisp(F);
 655   } else {
 656     unsigned Reg = getReg(CI.getCalledValue());
 657     BuildMI(BB, X86::CALLr32, 1).addReg(Reg);
 658   }
 659
 660   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addZImm(NumBytes);
 661
 662   // If there is a return value, scavenge the result from the location the call
 663   // leaves it in...
 664   //
 665   if (CI.getType() != Type::VoidTy) {
 666     unsigned resultTypeClass = getClass(CI.getType());
 667     switch (resultTypeClass) {
 668     case cByte:
 669     case cShort:
 670     case cInt: {
 671       // Integral results are in %eax, or the appropriate portion
 672       // thereof.
 673       static const unsigned regRegMove[] = {
 674         X86::MOVrr8, X86::MOVrr16, X86::MOVrr32
 675       };
 676       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
 677       BuildMI(BB, regRegMove[resultTypeClass], 1, getReg(CI))
 678                  .addReg(AReg[resultTypeClass]);
 679       break;
 680     }
 681     case cFP:     // Floating-point return values live in %ST(0)
 682       BuildMI(BB, X86::FpMOV, 1, getReg(CI)).addReg(X86::ST0);
 683       break;
 684     default:
 685       std::cerr << "Cannot get return value for call of type '"
 686                 << *CI.getType() << "'\n";
 687       visitInstruction(CI);
 688     }
 689   }
 690 }
 691
 692 /// visitSimpleBinary - Implement simple binary operators for integral types...
 693 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or,
 694 /// 4 for Xor.
 695 ///
 696 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
 697   if (B.getType() == Type::BoolTy)  // FIXME: Handle bools for logicals
 698     visitInstruction(B);
 699
 700   unsigned Class = getClass(B.getType());
 701   if (Class > cFP)  // FIXME: Handle longs
 702     visitInstruction(B);
 703
 704   static const unsigned OpcodeTab[][4] = {
 705     // Arithmetic operators
 706     { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32, X86::FpADD },  // ADD
 707     { X86::SUBrr8, X86::SUBrr16, X86::SUBrr32, X86::FpSUB },  // SUB
 708
 709     // Bitwise operators
 710     { X86::ANDrr8, X86::ANDrr16, X86::ANDrr32, 0 },  // AND
 711     { X86:: ORrr8, X86:: ORrr16, X86:: ORrr32, 0 },  // OR
 712     { X86::XORrr8, X86::XORrr16, X86::XORrr32, 0 },  // XOR
 713   };
 714
 715   unsigned Opcode = OpcodeTab[OperatorClass][Class];
 716   assert(Opcode && "Floating point arguments to logical inst?");
 717   unsigned Op0r = getReg(B.getOperand(0));
 718   unsigned Op1r = getReg(B.getOperand(1));
 719   BuildMI(BB, Opcode, 2, getReg(B)).addReg(Op0r).addReg(Op1r);
 720 }
 721
 722 /// doMultiply - Emit appropriate instructions to multiply together
 723 /// the registers op0Reg and op1Reg, and put the result in destReg.
 724 /// The type of the result should be given as resultType.
 725 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI,
 726                       unsigned destReg, const Type *resultType,
 727                       unsigned op0Reg, unsigned op1Reg) {
 728   unsigned Class = getClass(resultType);
 729   switch (Class) {
 730   case cFP:              // Floating point multiply
 731     BuildMI(BB, X86::FpMUL, 2, destReg).addReg(op0Reg).addReg(op1Reg);
 732     return;
 733   default:
 734   case cLong:
 735     assert(0 && "doMultiply not implemented for this class yet!");
 736   case cByte:
 737   case cShort:
 738   case cInt:          // Small integerals, handled below...
 739     break;
 740   }
 741
 742   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
 743   static const unsigned MulOpcode[]={ X86::MULrr8, X86::MULrr16, X86::MULrr32 };
 744   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
 745   unsigned Reg     = Regs[Class];
 746
 747   // Emit a MOV to put the first operand into the appropriately-sized
 748   // subreg of EAX.
 749   BMI(MBB, MBBI, MovOpcode[Class], 1, Reg).addReg (op0Reg);
 750
 751   // Emit the appropriate multiply instruction.
 752   BMI(MBB, MBBI, MulOpcode[Class], 1).addReg (op1Reg);
 753
 754   // Emit another MOV to put the result into the destination register.
 755   BMI(MBB, MBBI, MovOpcode[Class], 1, destReg).addReg (Reg);
 756 }
 757
 758 /// visitMul - Multiplies are not simple binary operators because they must deal
 759 /// with the EAX register explicitly.
 760 ///
 761 void ISel::visitMul(BinaryOperator &I) {
 762   unsigned DestReg = getReg(I);
 763   unsigned Op0Reg  = getReg(I.getOperand(0));
 764   unsigned Op1Reg  = getReg(I.getOperand(1));
 765   MachineBasicBlock::iterator MBBI = BB->end();
 766   doMultiply(BB, MBBI, DestReg, I.getType(), Op0Reg, Op1Reg);
 767 }
 768
 769
 770 /// visitDivRem - Handle division and remainder instructions... these
 771 /// instruction both require the same instructions to be generated, they just
 772 /// select the result from a different register.  Note that both of these
 773 /// instructions work differently for signed and unsigned operands.
 774 ///
 775 void ISel::visitDivRem(BinaryOperator &I) {
 776   unsigned Class     = getClass(I.getType());
 777   unsigned Op0Reg    = getReg(I.getOperand(0));
 778   unsigned Op1Reg    = getReg(I.getOperand(1));
 779   unsigned ResultReg = getReg(I);
 780
 781   switch (Class) {
 782   case cFP:              // Floating point multiply
 783     if (I.getOpcode() == Instruction::Div)
 784       BuildMI(BB, X86::FpDIV, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
 785     else
 786       BuildMI(BB, X86::FpREM, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
 787     return;
 788   default:
 789   case cLong:
 790     assert(0 && "div/rem not implemented for this class yet!");
 791   case cByte:
 792   case cShort:
 793   case cInt:          // Small integerals, handled below...
 794     break;
 795   }
 796
 797   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
 798   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
 799   static const unsigned ExtOpcode[]={ X86::CBW   , X86::CWD    , X86::CDQ     };
 800   static const unsigned ClrOpcode[]={ X86::XORrr8, X86::XORrr16, X86::XORrr32 };
 801   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
 802
 803   static const unsigned DivOpcode[][4] = {
 804     { X86::DIVrr8 , X86::DIVrr16 , X86::DIVrr32 , 0 },  // Unsigned division
 805     { X86::IDIVrr8, X86::IDIVrr16, X86::IDIVrr32, 0 },  // Signed division
 806   };
 807
 808   bool isSigned   = I.getType()->isSigned();
 809   unsigned Reg    = Regs[Class];
 810   unsigned ExtReg = ExtRegs[Class];
 811
 812   // Put the first operand into one of the A registers...
 813   BuildMI(BB, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
 814
 815   if (isSigned) {
 816     // Emit a sign extension instruction...
 817     BuildMI(BB, ExtOpcode[Class], 0);
 818   } else {
 819     // If unsigned, emit a zeroing instruction... (reg = xor reg, reg)
 820     BuildMI(BB, ClrOpcode[Class], 2, ExtReg).addReg(ExtReg).addReg(ExtReg);
 821   }
 822
 823   // Emit the appropriate divide or remainder instruction...
 824   BuildMI(BB, DivOpcode[isSigned][Class], 1).addReg(Op1Reg);
 825
 826   // Figure out which register we want to pick the result out of...
 827   unsigned DestReg = (I.getOpcode() == Instruction::Div) ? Reg : ExtReg;
 828
 829   // Put the result into the destination register...
 830   BuildMI(BB, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
 831 }
 832
 833
 834 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
 835 /// for constant immediate shift values, and for constant immediate
 836 /// shift values equal to 1. Even the general case is sort of special,
 837 /// because the shift amount has to be in CL, not just any old register.
 838 ///
 839 void ISel::visitShiftInst (ShiftInst &I) {
 840   unsigned Op0r = getReg (I.getOperand(0));
 841   unsigned DestReg = getReg(I);
 842   bool isLeftShift = I.getOpcode() == Instruction::Shl;
 843   bool isOperandSigned = I.getType()->isUnsigned();
 844   unsigned OperandClass = getClass(I.getType());
 845
 846   if (OperandClass > cInt)
 847     visitInstruction(I); // Can't handle longs yet!
 848
 849   if (ConstantUInt *CUI = dyn_cast<ConstantUInt> (I.getOperand (1)))
 850     {
 851       // The shift amount is constant, guaranteed to be a ubyte. Get its value.
 852       assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
 853       unsigned char shAmt = CUI->getValue();
 854
 855       static const unsigned ConstantOperand[][4] = {
 856         { X86::SHRir8, X86::SHRir16, X86::SHRir32, 0 },  // SHR
 857         { X86::SARir8, X86::SARir16, X86::SARir32, 0 },  // SAR
 858         { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 },  // SHL
 859         { X86::SHLir8, X86::SHLir16, X86::SHLir32, 0 },  // SAL = SHL
 860       };
 861
 862       const unsigned *OpTab = // Figure out the operand table to use
 863         ConstantOperand[isLeftShift*2+isOperandSigned];
 864
 865       // Emit: <insn> reg, shamt  (shift-by-immediate opcode "ir" form.)
 866       BuildMI(BB, OpTab[OperandClass], 2, DestReg).addReg(Op0r).addZImm(shAmt);
 867     }
 868   else
 869     {
 870       // The shift amount is non-constant.
 871       //
 872       // In fact, you can only shift with a variable shift amount if
 873       // that amount is already in the CL register, so we have to put it
 874       // there first.
 875       //
 876
 877       // Emit: move cl, shiftAmount (put the shift amount in CL.)
 878       BuildMI(BB, X86::MOVrr8, 1, X86::CL).addReg(getReg(I.getOperand(1)));
 879
 880       // This is a shift right (SHR).
 881       static const unsigned NonConstantOperand[][4] = {
 882         { X86::SHRrr8, X86::SHRrr16, X86::SHRrr32, 0 },  // SHR
 883         { X86::SARrr8, X86::SARrr16, X86::SARrr32, 0 },  // SAR
 884         { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 },  // SHL
 885         { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32, 0 },  // SAL = SHL
 886       };
 887
 888       const unsigned *OpTab = // Figure out the operand table to use
 889         NonConstantOperand[isLeftShift*2+isOperandSigned];
 890
 891       BuildMI(BB, OpTab[OperandClass], 1, DestReg).addReg(Op0r);
 892     }
 893 }
 894
 895
 896 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
 897 /// instruction.  The load and store instructions are the only place where we
 898 /// need to worry about the memory layout of the target machine.
 899 ///
 900 void ISel::visitLoadInst(LoadInst &I) {
 901   bool isLittleEndian  = TM.getTargetData().isLittleEndian();
 902   bool hasLongPointers = TM.getTargetData().getPointerSize() == 8;
 903   unsigned SrcAddrReg = getReg(I.getOperand(0));
 904   unsigned DestReg = getReg(I);
 905
 906   unsigned Class = getClass(I.getType());
 907   switch (Class) {
 908   default: visitInstruction(I);   // FIXME: Handle longs...
 909   case cFP: {
 910     // FIXME: Handle endian swapping for FP values.
 911     unsigned Opcode = I.getType() == Type::FloatTy ? X86::FLDr32 : X86::FLDr64;
 912     addDirectMem(BuildMI(BB, Opcode, 4, DestReg), SrcAddrReg);
 913     return;
 914   }
 915   case cInt:      // Integers of various sizes handled below
 916   case cShort:
 917   case cByte: break;
 918   }
 919
 920   // We need to adjust the input pointer if we are emulating a big-endian
 921   // long-pointer target.  On these systems, the pointer that we are interested
 922   // in is in the upper part of the eight byte memory image of the pointer.  It
 923   // also happens to be byte-swapped, but this will be handled later.
 924   //
 925   if (!isLittleEndian && hasLongPointers && isa<PointerType>(I.getType())) {
 926     unsigned R = makeAnotherReg(Type::UIntTy);
 927     BuildMI(BB, X86::ADDri32, 2, R).addReg(SrcAddrReg).addZImm(4);
 928     SrcAddrReg = R;
 929   }
 930
 931   unsigned IReg = DestReg;
 932   if (!isLittleEndian) {  // If big endian we need an intermediate stage
 933     IReg = makeAnotherReg(I.getType());
 934     std::swap(IReg, DestReg);
 935   }
 936
 937   static const unsigned Opcode[] = { X86::MOVmr8, X86::MOVmr16, X86::MOVmr32 };
 938   addDirectMem(BuildMI(BB, Opcode[Class], 4, DestReg), SrcAddrReg);
 939
 940   if (!isLittleEndian) {
 941     // Emit the byte swap instruction...
 942     switch (Class) {
 943     case cByte:
 944       // No byteswap neccesary for 8 bit value...
 945       BuildMI(BB, X86::MOVrr8, 1, IReg).addReg(DestReg);
 946       break;
 947     case cInt:
 948       // Use the 32 bit bswap instruction to do a 32 bit swap...
 949       BuildMI(BB, X86::BSWAPr32, 1, IReg).addReg(DestReg);
 950       break;
 951
 952     case cShort:
 953       // For 16 bit we have to use an xchg instruction, because there is no
 954       // 16-bit bswap.  XCHG is neccesarily not in SSA form, so we force things
 955       // into AX to do the xchg.
 956       //
 957       BuildMI(BB, X86::MOVrr16, 1, X86::AX).addReg(DestReg);
 958       BuildMI(BB, X86::XCHGrr8, 2).addReg(X86::AL, MOTy::UseAndDef)
 959                                   .addReg(X86::AH, MOTy::UseAndDef);
 960       BuildMI(BB, X86::MOVrr16, 1, DestReg).addReg(X86::AX);
 961       break;
 962     default: assert(0 && "Class not handled yet!");
 963     }
 964   }
 965 }
 966
 967
 968 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
 969 /// instruction.
 970 ///
 971 void ISel::visitStoreInst(StoreInst &I) {
 972   bool isLittleEndian  = TM.getTargetData().isLittleEndian();
 973   bool hasLongPointers = TM.getTargetData().getPointerSize() == 8;
 974   unsigned ValReg = getReg(I.getOperand(0));
 975   unsigned AddressReg = getReg(I.getOperand(1));
 976
 977   unsigned Class = getClass(I.getOperand(0)->getType());
 978   switch (Class) {
 979   default: visitInstruction(I);   // FIXME: Handle longs...
 980   case cFP: {
 981     // FIXME: Handle endian swapping for FP values.
 982     unsigned Opcode = I.getOperand(0)->getType() == Type::FloatTy ?
 983                             X86::FSTr32 : X86::FSTr64;
 984     addDirectMem(BuildMI(BB, Opcode, 1+4), AddressReg).addReg(ValReg);
 985     return;
 986   }
 987   case cInt:      // Integers of various sizes handled below
 988   case cShort:
 989   case cByte: break;
 990   }
 991
 992   if (!isLittleEndian && hasLongPointers &&
 993       isa<PointerType>(I.getOperand(0)->getType())) {
 994     unsigned R = makeAnotherReg(Type::UIntTy);
 995     BuildMI(BB, X86::ADDri32, 2, R).addReg(AddressReg).addZImm(4);
 996     AddressReg = R;
 997   }
 998
 999   if (!isLittleEndian && Class != cByte) {
1000     // Emit a byte swap instruction...
1001     switch (Class) {
1002     case cInt: {
1003       unsigned R = makeAnotherReg(I.getOperand(0)->getType());
1004       BuildMI(BB, X86::BSWAPr32, 1, R).addReg(ValReg);
1005       ValReg = R;
1006       break;
1007     }
1008     case cShort:
1009       // For 16 bit we have to use an xchg instruction, because there is no
1010       // 16-bit bswap.  XCHG is neccesarily not in SSA form, so we force things
1011       // into AX to do the xchg.
1012       //
1013       BuildMI(BB, X86::MOVrr16, 1, X86::AX).addReg(ValReg);
1014       BuildMI(BB, X86::XCHGrr8, 2).addReg(X86::AL, MOTy::UseAndDef)
1015                                   .addReg(X86::AH, MOTy::UseAndDef);
1016       ValReg = X86::AX;
1017       break;
1018     default: assert(0 && "Unknown class!");
1019     }
1020   }
1021
1022   static const unsigned Opcode[] = { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32 };
1023   addDirectMem(BuildMI(BB, Opcode[Class], 1+4), AddressReg).addReg(ValReg);
1024 }
1025
1026
1027 /// visitCastInst - Here we have various kinds of copying with or without
1028 /// sign extension going on.
1029 void
1030 ISel::visitCastInst (CastInst &CI)
1031 {
1032   const Type *targetType = CI.getType ();
1033   Value *operand = CI.getOperand (0);
1034   unsigned operandReg = getReg (operand);
1035   const Type *sourceType = operand->getType ();
1036   unsigned destReg = getReg (CI);
1037   //
1038   // Currently we handle:
1039   //
1040   // 1) cast * to bool
1041   //
1042   // 2) cast {sbyte, ubyte} to {sbyte, ubyte}
1043   //    cast {short, ushort} to {ushort, short}
1044   //    cast {int, uint, ptr} to {int, uint, ptr}
1045   //
1046   // 3) cast {sbyte, ubyte} to {ushort, short}
1047   //    cast {sbyte, ubyte} to {int, uint, ptr}
1048   //    cast {short, ushort} to {int, uint, ptr}
1049   //
1050   // 4) cast {int, uint, ptr} to {short, ushort}
1051   //    cast {int, uint, ptr} to {sbyte, ubyte}
1052   //    cast {short, ushort} to {sbyte, ubyte}
1053
1054   // 1) Implement casts to bool by using compare on the operand followed
1055   // by set if not zero on the result.
1056   if (targetType == Type::BoolTy)
1057     {
1058       BuildMI (BB, X86::CMPri8, 2).addReg (operandReg).addZImm (0);
1059       BuildMI (BB, X86::SETNEr, 1, destReg);
1060       return;
1061     }
1062
1063   // 2) Implement casts between values of the same type class (as determined
1064   // by getClass) by using a register-to-register move.
1065   unsigned srcClass = getClassB(sourceType);
1066   unsigned targClass = getClass(targetType);
1067   static const unsigned regRegMove[] = {
1068     X86::MOVrr8, X86::MOVrr16, X86::MOVrr32
1069   };
1070
1071   if (srcClass <= cInt && targClass <= cInt && srcClass == targClass) {
1072     BuildMI(BB, regRegMove[srcClass], 1, destReg).addReg(operandReg);
1073     return;
1074   }
1075   // 3) Handle cast of SMALLER int to LARGER int using a move with sign
1076   // extension or zero extension, depending on whether the source type
1077   // was signed.
1078   if ((srcClass <= cInt) && (targClass <= cInt) && (srcClass < targClass))
1079     {
1080       static const unsigned ops[] = {
1081         X86::MOVSXr16r8, X86::MOVSXr32r8, X86::MOVSXr32r16,
1082         X86::MOVZXr16r8, X86::MOVZXr32r8, X86::MOVZXr32r16
1083       };
1084       unsigned srcSigned = sourceType->isSigned ();
1085       BuildMI (BB, ops[3 * srcSigned + srcClass + targClass - 1], 1,
1086                destReg).addReg (operandReg);
1087       return;
1088     }
1089   // 4) Handle cast of LARGER int to SMALLER int using a move to EAX
1090   // followed by a move out of AX or AL.
1091   if ((srcClass <= cInt) && (targClass <= cInt) && (srcClass > targClass))
1092     {
1093       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
1094       BuildMI (BB, regRegMove[srcClass], 1,
1095                AReg[srcClass]).addReg (operandReg);
1096       BuildMI (BB, regRegMove[targClass], 1, destReg).addReg (AReg[srcClass]);
1097       return;
1098     }
1099   // Anything we haven't handled already, we can't (yet) handle at all.
1100   //
1101   // FP to integral casts can be handled with FISTP to store onto the
1102   // stack while converting to integer, followed by a MOV to load from
1103   // the stack into the result register. Integral to FP casts can be
1104   // handled with MOV to store onto the stack, followed by a FILD to
1105   // load from the stack while converting to FP. For the moment, I
1106   // can't quite get straight in my head how to borrow myself some
1107   // stack space and write on it. Otherwise, this would be trivial.
1108   visitInstruction (CI);
1109 }
1110
1111 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1112 // returns zero when the input is not exactly a power of two.
1113 static unsigned ExactLog2(unsigned Val) {
1114   if (Val == 0) return 0;
1115   unsigned Count = 0;
1116   while (Val != 1) {
1117     if (Val & 1) return 0;
1118     Val >>= 1;
1119     ++Count;
1120   }
1121   return Count+1;
1122 }
1123
1124 /// visitGetElementPtrInst - I don't know, most programs don't have
1125 /// getelementptr instructions, right? That means we can put off
1126 /// implementing this, right? Right. This method emits machine
1127 /// instructions to perform type-safe pointer arithmetic. I am
1128 /// guessing this could be cleaned up somewhat to use fewer temporary
1129 /// registers.
1130 void
1131 ISel::visitGetElementPtrInst (GetElementPtrInst &I)
1132 {
1133   unsigned outputReg = getReg (I);
1134   MachineBasicBlock::iterator MI = BB->end();
1135   emitGEPOperation(BB, MI, I.getOperand(0),
1136                    I.op_begin()+1, I.op_end(), outputReg);
1137 }
1138
1139 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
1140                             MachineBasicBlock::iterator &IP,
1141                             Value *Src, User::op_iterator IdxBegin,
1142                             User::op_iterator IdxEnd, unsigned TargetReg) {
1143   const TargetData &TD = TM.getTargetData();
1144   const Type *Ty = Src->getType();
1145   unsigned basePtrReg = getReg(Src, MBB, IP);
1146
1147   // GEPs have zero or more indices; we must perform a struct access
1148   // or array access for each one.
1149   for (GetElementPtrInst::op_iterator oi = IdxBegin,
1150          oe = IdxEnd; oi != oe; ++oi) {
1151     Value *idx = *oi;
1152     unsigned nextBasePtrReg = makeAnotherReg(Type::UIntTy);
1153     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1154       // It's a struct access.  idx is the index into the structure,
1155       // which names the field. This index must have ubyte type.
1156       const ConstantUInt *CUI = cast<ConstantUInt>(idx);
1157       assert(CUI->getType() == Type::UByteTy
1158               && "Funny-looking structure index in GEP");
1159       // Use the TargetData structure to pick out what the layout of
1160       // the structure is in memory.  Since the structure index must
1161       // be constant, we can get its value and use it to find the
1162       // right byte offset from the StructLayout class's list of
1163       // structure member offsets.
1164       unsigned idxValue = CUI->getValue();
1165       unsigned memberOffset =
1166         TD.getStructLayout(StTy)->MemberOffsets[idxValue];
1167       // Emit an ADD to add memberOffset to the basePtr.
1168       BMI(MBB, IP, X86::ADDri32, 2,
1169           nextBasePtrReg).addReg(basePtrReg).addZImm(memberOffset);
1170       // The next type is the member of the structure selected by the
1171       // index.
1172       Ty = StTy->getElementTypes()[idxValue];
1173     } else if (const SequentialType *SqTy = cast<SequentialType>(Ty)) {
1174       // It's an array or pointer access: [ArraySize x ElementType].
1175
1176       // idx is the index into the array.  Unlike with structure
1177       // indices, we may not know its actual value at code-generation
1178       // time.
1179       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
1180
1181       // We want to add basePtrReg to(idxReg * sizeof ElementType). First, we
1182       // must find the size of the pointed-to type (Not coincidentally, the next
1183       // type is the type of the elements in the array).
1184       Ty = SqTy->getElementType();
1185       unsigned elementSize = TD.getTypeSize(Ty);
1186
1187       // If idxReg is a constant, we don't need to perform the multiply!
1188       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
1189         if (CSI->isNullValue()) {
1190           BMI(MBB, IP, X86::MOVrr32, 1, nextBasePtrReg).addReg(basePtrReg);
1191         } else {
1192           unsigned Offset = elementSize*CSI->getValue();
1193
1194           BMI(MBB, IP, X86::ADDri32, 2,
1195               nextBasePtrReg).addReg(basePtrReg).addZImm(Offset);
1196         }
1197       } else if (elementSize == 1) {
1198         // If the element size is 1, we don't have to multiply, just add
1199         unsigned idxReg = getReg(idx, MBB, IP);
1200         BMI(MBB, IP, X86::ADDrr32, 2,
1201             nextBasePtrReg).addReg(basePtrReg).addReg(idxReg);
1202       } else {
1203         unsigned idxReg = getReg(idx, MBB, IP);
1204         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
1205         if (unsigned Shift = ExactLog2(elementSize)) {
1206           // If the element size is exactly a power of 2, use a shift to get it.
1207
1208           BMI(MBB, IP, X86::SHLir32, 2,
1209               OffsetReg).addReg(idxReg).addZImm(Shift-1);
1210         } else {
1211           // Most general case, emit a multiply...
1212           unsigned elementSizeReg = makeAnotherReg(Type::LongTy);
1213           BMI(MBB, IP, X86::MOVir32, 1, elementSizeReg).addZImm(elementSize);
1214
1215           // Emit a MUL to multiply the register holding the index by
1216           // elementSize, putting the result in OffsetReg.
1217           doMultiply(MBB, IP, OffsetReg, Type::LongTy, idxReg, elementSizeReg);
1218         }
1219         // Emit an ADD to add OffsetReg to the basePtr.
1220         BMI(MBB, IP, X86::ADDrr32, 2,
1221             nextBasePtrReg).addReg(basePtrReg).addReg(OffsetReg);
1222       }
1223     }
1224     // Now that we are here, further indices refer to subtypes of this
1225     // one, so we don't need to worry about basePtrReg itself, anymore.
1226     basePtrReg = nextBasePtrReg;
1227   }
1228   // After we have processed all the indices, the result is left in
1229   // basePtrReg.  Move it to the register where we were expected to
1230   // put the answer.  A 32-bit move should do it, because we are in
1231   // ILP32 land.
1232   BMI(MBB, IP, X86::MOVrr32, 1, TargetReg).addReg(basePtrReg);
1233 }
1234
1235
1236 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
1237 /// frame manager, otherwise do it the hard way.
1238 ///
1239 void ISel::visitAllocaInst(AllocaInst &I) {
1240   // Find the data size of the alloca inst's getAllocatedType.
1241   const Type *Ty = I.getAllocatedType();
1242   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
1243
1244   // If this is a fixed size alloca in the entry block for the function,
1245   // statically stack allocate the space.
1246   //
1247   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getArraySize())) {
1248     if (I.getParent() == I.getParent()->getParent()->begin()) {
1249       TySize *= CUI->getValue();   // Get total allocated size...
1250       unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
1251
1252       // Create a new stack object using the frame manager...
1253       int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
1254       addFrameReference(BuildMI(BB, X86::LEAr32, 5, getReg(I)), FrameIdx);
1255       return;
1256     }
1257   }
1258
1259   // Create a register to hold the temporary result of multiplying the type size
1260   // constant by the variable amount.
1261   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
1262   unsigned SrcReg1 = getReg(I.getArraySize());
1263   unsigned SizeReg = makeAnotherReg(Type::UIntTy);
1264   BuildMI(BB, X86::MOVir32, 1, SizeReg).addZImm(TySize);
1265
1266   // TotalSizeReg = mul <numelements>, <TypeSize>
1267   MachineBasicBlock::iterator MBBI = BB->end();
1268   doMultiply(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, SizeReg);
1269
1270   // AddedSize = add <TotalSizeReg>, 15
1271   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
1272   BuildMI(BB, X86::ADDri32, 2, AddedSizeReg).addReg(TotalSizeReg).addZImm(15);
1273
1274   // AlignedSize = and <AddedSize>, ~15
1275   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
1276   BuildMI(BB, X86::ANDri32, 2, AlignedSize).addReg(AddedSizeReg).addZImm(~15);
1277
1278   // Subtract size from stack pointer, thereby allocating some space.
1279   BuildMI(BB, X86::SUBri32, 2, X86::ESP).addReg(X86::ESP).addZImm(AlignedSize);
1280
1281   // Put a pointer to the space into the result register, by copying
1282   // the stack pointer.
1283   BuildMI(BB, X86::MOVrr32, 1, getReg(I)).addReg(X86::ESP);
1284
1285   // Inform the Frame Information that we have just allocated a variable sized
1286   // object.
1287   F->getFrameInfo()->CreateVariableSizedObject();
1288 }
1289
1290
1291 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
1292 /// into a machine code representation is a very simple peep-hole fashion.  The
1293 /// generated code sucks but the implementation is nice and simple.
1294 ///
1295 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
1296   return new ISel(TM);
1297 }