lib/Target/X86/InstSelectSimple.cpp

   1 //===-- InstSelectSimple.cpp - A simple instruction selector for x86 ------===//
   2 //
   3 // This file defines a simple peephole instruction selector for the x86 target
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "X86.h"
   8 #include "X86InstrInfo.h"
   9 #include "X86InstrBuilder.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/Instructions.h"
  12 #include "llvm/DerivedTypes.h"
  13 #include "llvm/Constants.h"
  14 #include "llvm/Pass.h"
  15 #include "llvm/Intrinsics.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineInstrBuilder.h"
  18 #include "llvm/CodeGen/SSARegMap.h"
  19 #include "llvm/CodeGen/MachineFrameInfo.h"
  20 #include "llvm/CodeGen/MachineConstantPool.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Target/MRegisterInfo.h"
  23 #include "llvm/Support/InstVisitor.h"
  24
  25 /// BMI - A special BuildMI variant that takes an iterator to insert the
  26 /// instruction at as well as a basic block.  This is the version for when you
  27 /// have a destination register in mind.
  28 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  29                                       MachineBasicBlock::iterator &I,
  30                                       int Opcode, unsigned NumOperands,
  31                                       unsigned DestReg) {
  32   assert(I >= MBB->begin() && I <= MBB->end() && "Bad iterator!");
  33   MachineInstr *MI = new MachineInstr(Opcode, NumOperands+1, true, true);
  34   I = MBB->insert(I, MI)+1;
  35   return MachineInstrBuilder(MI).addReg(DestReg, MOTy::Def);
  36 }
  37
  38 /// BMI - A special BuildMI variant that takes an iterator to insert the
  39 /// instruction at as well as a basic block.
  40 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  41                                       MachineBasicBlock::iterator &I,
  42                                       int Opcode, unsigned NumOperands) {
  43   assert(I >= MBB->begin() && I <= MBB->end() && "Bad iterator!");
  44   MachineInstr *MI = new MachineInstr(Opcode, NumOperands, true, true);
  45   I = MBB->insert(I, MI)+1;
  46   return MachineInstrBuilder(MI);
  47 }
  48
  49
  50 namespace {
  51   struct ISel : public FunctionPass, InstVisitor<ISel> {
  52     TargetMachine &TM;
  53     MachineFunction *F;                 // The function we are compiling into
  54     MachineBasicBlock *BB;              // The current MBB we are compiling
  55     int VarArgsFrameIndex;              // FrameIndex for start of varargs area
  56
  57     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  58
  59     // MBBMap - Mapping between LLVM BB -> Machine BB
  60     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  61
  62     ISel(TargetMachine &tm) : TM(tm), F(0), BB(0) {}
  63
  64     /// runOnFunction - Top level implementation of instruction selection for
  65     /// the entire function.
  66     ///
  67     bool runOnFunction(Function &Fn) {
  68       F = &MachineFunction::construct(&Fn, TM);
  69
  70       // Create all of the machine basic blocks for the function...
  71       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  72         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
  73
  74       BB = &F->front();
  75
  76       // Copy incoming arguments off of the stack...
  77       LoadArgumentsToVirtualRegs(Fn);
  78
  79       // Instruction select everything except PHI nodes
  80       visit(Fn);
  81
  82       // Select the PHI nodes
  83       SelectPHINodes();
  84
  85       RegMap.clear();
  86       MBBMap.clear();
  87       F = 0;
  88       // We always build a machine code representation for the function
  89       return true;
  90     }
  91
  92     virtual const char *getPassName() const {
  93       return "X86 Simple Instruction Selection";
  94     }
  95
  96     /// visitBasicBlock - This method is called when we are visiting a new basic
  97     /// block.  This simply creates a new MachineBasicBlock to emit code into
  98     /// and adds it to the current MachineFunction.  Subsequent visit* for
  99     /// instructions will be invoked for all instructions in the basic block.
 100     ///
 101     void visitBasicBlock(BasicBlock &LLVM_BB) {
 102       BB = MBBMap[&LLVM_BB];
 103     }
 104
 105     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 106     /// from the stack into virtual registers.
 107     ///
 108     void LoadArgumentsToVirtualRegs(Function &F);
 109
 110     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 111     /// because we have to generate our sources into the source basic blocks,
 112     /// not the current one.
 113     ///
 114     void SelectPHINodes();
 115
 116     // Visitation methods for various instructions.  These methods simply emit
 117     // fixed X86 code for each instruction.
 118     //
 119
 120     // Control flow operators
 121     void visitReturnInst(ReturnInst &RI);
 122     void visitBranchInst(BranchInst &BI);
 123
 124     struct ValueRecord {
 125       Value *Val;
 126       unsigned Reg;
 127       const Type *Ty;
 128       ValueRecord(unsigned R, const Type *T) : Val(0), Reg(R), Ty(T) {}
 129       ValueRecord(Value *V) : Val(V), Reg(0), Ty(V->getType()) {}
 130     };
 131     void doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 132                 const std::vector<ValueRecord> &Args);
 133     void visitCallInst(CallInst &I);
 134     void visitIntrinsicCall(LLVMIntrinsic::ID ID, CallInst &I);
 135
 136     // Arithmetic operators
 137     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 138     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 139     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 140     void doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI,
 141                     unsigned DestReg, const Type *DestTy,
 142                     unsigned Op0Reg, unsigned Op1Reg);
 143     void visitMul(BinaryOperator &B);
 144
 145     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 146     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 147     void visitDivRem(BinaryOperator &B);
 148
 149     // Bitwise operators
 150     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 151     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 152     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 153
 154     // Comparison operators...
 155     void visitSetCondInst(SetCondInst &I);
 156     bool EmitComparisonGetSignedness(unsigned OpNum, Value *Op0, Value *Op1);
 157
 158     // Memory Instructions
 159     MachineInstr *doFPLoad(MachineBasicBlock *MBB,
 160                            MachineBasicBlock::iterator &MBBI,
 161                            const Type *Ty, unsigned DestReg);
 162     void visitLoadInst(LoadInst &I);
 163     void doFPStore(const Type *Ty, unsigned DestAddrReg, unsigned SrcReg);
 164     void visitStoreInst(StoreInst &I);
 165     void visitGetElementPtrInst(GetElementPtrInst &I);
 166     void visitAllocaInst(AllocaInst &I);
 167     void visitMallocInst(MallocInst &I);
 168     void visitFreeInst(FreeInst &I);
 169
 170     // Other operators
 171     void visitShiftInst(ShiftInst &I);
 172     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 173     void visitCastInst(CastInst &I);
 174     void visitVarArgInst(VarArgInst &I);
 175
 176     void visitInstruction(Instruction &I) {
 177       std::cerr << "Cannot instruction select: " << I;
 178       abort();
 179     }
 180
 181     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 182     ///
 183     void promote32(unsigned targetReg, const ValueRecord &VR);
 184
 185     /// EmitByteSwap - Byteswap SrcReg into DestReg.
 186     ///
 187     void EmitByteSwap(unsigned DestReg, unsigned SrcReg, unsigned Class);
 188
 189     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 190     /// constant expression GEP support.
 191     ///
 192     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator&IP,
 193                           Value *Src, User::op_iterator IdxBegin,
 194                           User::op_iterator IdxEnd, unsigned TargetReg);
 195
 196     /// emitCastOperation - Common code shared between visitCastInst and
 197     /// constant expression cast support.
 198     void emitCastOperation(MachineBasicBlock *BB,MachineBasicBlock::iterator&IP,
 199                            Value *Src, const Type *DestTy, unsigned TargetReg);
 200
 201     /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
 202     /// and constant expression support.
 203     void emitSimpleBinaryOperation(MachineBasicBlock *BB,
 204                                    MachineBasicBlock::iterator &IP,
 205                                    Value *Op0, Value *Op1,
 206                                    unsigned OperatorClass, unsigned TargetReg);
 207
 208     /// copyConstantToRegister - Output the instructions required to put the
 209     /// specified constant into the specified register.
 210     ///
 211     void copyConstantToRegister(MachineBasicBlock *MBB,
 212                                 MachineBasicBlock::iterator &MBBI,
 213                                 Constant *C, unsigned Reg);
 214
 215     /// makeAnotherReg - This method returns the next register number we haven't
 216     /// yet used.
 217     ///
 218     /// Long values are handled somewhat specially.  They are always allocated
 219     /// as pairs of 32 bit integer values.  The register number returned is the
 220     /// lower 32 bits of the long value, and the regNum+1 is the upper 32 bits
 221     /// of the long value.
 222     ///
 223     unsigned makeAnotherReg(const Type *Ty) {
 224       assert(dynamic_cast<const X86RegisterInfo*>(TM.getRegisterInfo()) &&
 225              "Current target doesn't have X86 reg info??");
 226       const X86RegisterInfo *MRI =
 227         static_cast<const X86RegisterInfo*>(TM.getRegisterInfo());
 228       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 229         const TargetRegisterClass *RC = MRI->getRegClassForType(Type::IntTy);
 230         // Create the lower part
 231         F->getSSARegMap()->createVirtualRegister(RC);
 232         // Create the upper part.
 233         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 234       }
 235
 236       // Add the mapping of regnumber => reg class to MachineFunction
 237       const TargetRegisterClass *RC = MRI->getRegClassForType(Ty);
 238       return F->getSSARegMap()->createVirtualRegister(RC);
 239     }
 240
 241     /// getReg - This method turns an LLVM value into a register number.  This
 242     /// is guaranteed to produce the same register number for a particular value
 243     /// every time it is queried.
 244     ///
 245     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 246     unsigned getReg(Value *V) {
 247       // Just append to the end of the current bb.
 248       MachineBasicBlock::iterator It = BB->end();
 249       return getReg(V, BB, It);
 250     }
 251     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 252                     MachineBasicBlock::iterator &IPt) {
 253       unsigned &Reg = RegMap[V];
 254       if (Reg == 0) {
 255         Reg = makeAnotherReg(V->getType());
 256         RegMap[V] = Reg;
 257       }
 258
 259       // If this operand is a constant, emit the code to copy the constant into
 260       // the register here...
 261       //
 262       if (Constant *C = dyn_cast<Constant>(V)) {
 263         copyConstantToRegister(MBB, IPt, C, Reg);
 264         RegMap.erase(V);  // Assign a new name to this constant if ref'd again
 265       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 266         // Move the address of the global into the register
 267         BMI(MBB, IPt, X86::MOVir32, 1, Reg).addGlobalAddress(GV);
 268         RegMap.erase(V);  // Assign a new name to this address if ref'd again
 269       }
 270
 271       return Reg;
 272     }
 273   };
 274 }
 275
 276 /// TypeClass - Used by the X86 backend to group LLVM types by their basic X86
 277 /// Representation.
 278 ///
 279 enum TypeClass {
 280   cByte, cShort, cInt, cFP, cLong
 281 };
 282
 283 /// getClass - Turn a primitive type into a "class" number which is based on the
 284 /// size of the type, and whether or not it is floating point.
 285 ///
 286 static inline TypeClass getClass(const Type *Ty) {
 287   switch (Ty->getPrimitiveID()) {
 288   case Type::SByteTyID:
 289   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
 290   case Type::ShortTyID:
 291   case Type::UShortTyID:  return cShort;     // Short operands are class #1
 292   case Type::IntTyID:
 293   case Type::UIntTyID:
 294   case Type::PointerTyID: return cInt;       // Int's and pointers are class #2
 295
 296   case Type::FloatTyID:
 297   case Type::DoubleTyID:  return cFP;        // Floating Point is #3
 298
 299   case Type::LongTyID:
 300   case Type::ULongTyID:   return cLong;      // Longs are class #4
 301   default:
 302     assert(0 && "Invalid type to getClass!");
 303     return cByte;  // not reached
 304   }
 305 }
 306
 307 // getClassB - Just like getClass, but treat boolean values as bytes.
 308 static inline TypeClass getClassB(const Type *Ty) {
 309   if (Ty == Type::BoolTy) return cByte;
 310   return getClass(Ty);
 311 }
 312
 313
 314 /// copyConstantToRegister - Output the instructions required to put the
 315 /// specified constant into the specified register.
 316 ///
 317 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 318                                   MachineBasicBlock::iterator &IP,
 319                                   Constant *C, unsigned R) {
 320   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 321     unsigned Class = 0;
 322     switch (CE->getOpcode()) {
 323     case Instruction::GetElementPtr:
 324       emitGEPOperation(MBB, IP, CE->getOperand(0),
 325                        CE->op_begin()+1, CE->op_end(), R);
 326       return;
 327     case Instruction::Cast:
 328       emitCastOperation(MBB, IP, CE->getOperand(0), CE->getType(), R);
 329       return;
 330
 331     case Instruction::Xor: ++Class; // FALL THROUGH
 332     case Instruction::Or:  ++Class; // FALL THROUGH
 333     case Instruction::And: ++Class; // FALL THROUGH
 334     case Instruction::Sub: ++Class; // FALL THROUGH
 335     case Instruction::Add:
 336       emitSimpleBinaryOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 337                                 Class, R);
 338       return;
 339
 340     default:
 341       std::cerr << "Offending expr: " << C << "\n";
 342       assert(0 && "Constant expressions not yet handled!\n");
 343     }
 344   }
 345
 346   if (C->getType()->isIntegral()) {
 347     unsigned Class = getClassB(C->getType());
 348
 349     if (Class == cLong) {
 350       // Copy the value into the register pair.
 351       uint64_t Val = cast<ConstantInt>(C)->getRawValue();
 352       BMI(MBB, IP, X86::MOVir32, 1, R).addZImm(Val & 0xFFFFFFFF);
 353       BMI(MBB, IP, X86::MOVir32, 1, R+1).addZImm(Val >> 32);
 354       return;
 355     }
 356
 357     assert(Class <= cInt && "Type not handled yet!");
 358
 359     static const unsigned IntegralOpcodeTab[] = {
 360       X86::MOVir8, X86::MOVir16, X86::MOVir32
 361     };
 362
 363     if (C->getType() == Type::BoolTy) {
 364       BMI(MBB, IP, X86::MOVir8, 1, R).addZImm(C == ConstantBool::True);
 365     } else {
 366       ConstantInt *CI = cast<ConstantInt>(C);
 367       BMI(MBB, IP, IntegralOpcodeTab[Class], 1, R).addZImm(CI->getRawValue());
 368     }
 369   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 370     double Value = CFP->getValue();
 371     if (Value == +0.0)
 372       BMI(MBB, IP, X86::FLD0, 0, R);
 373     else if (Value == +1.0)
 374       BMI(MBB, IP, X86::FLD1, 0, R);
 375     else {
 376       // Otherwise we need to spill the constant to memory...
 377       MachineConstantPool *CP = F->getConstantPool();
 378       unsigned CPI = CP->getConstantPoolIndex(CFP);
 379       addConstantPoolReference(doFPLoad(MBB, IP, CFP->getType(), R), CPI);
 380     }
 381
 382   } else if (isa<ConstantPointerNull>(C)) {
 383     // Copy zero (null pointer) to the register.
 384     BMI(MBB, IP, X86::MOVir32, 1, R).addZImm(0);
 385   } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 386     unsigned SrcReg = getReg(CPR->getValue(), MBB, IP);
 387     BMI(MBB, IP, X86::MOVrr32, 1, R).addReg(SrcReg);
 388   } else {
 389     std::cerr << "Offending constant: " << C << "\n";
 390     assert(0 && "Type not handled yet!");
 391   }
 392 }
 393
 394 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 395 /// the stack into virtual registers.
 396 ///
 397 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 398   // Emit instructions to load the arguments...  On entry to a function on the
 399   // X86, the stack frame looks like this:
 400   //
 401   // [ESP] -- return address
 402   // [ESP + 4] -- first argument (leftmost lexically)
 403   // [ESP + 8] -- second argument, if first argument is four bytes in size
 404   //    ...
 405   //
 406   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 407   MachineFrameInfo *MFI = F->getFrameInfo();
 408
 409   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 410     unsigned Reg = getReg(*I);
 411
 412     int FI;          // Frame object index
 413     switch (getClassB(I->getType())) {
 414     case cByte:
 415       FI = MFI->CreateFixedObject(1, ArgOffset);
 416       addFrameReference(BuildMI(BB, X86::MOVmr8, 4, Reg), FI);
 417       break;
 418     case cShort:
 419       FI = MFI->CreateFixedObject(2, ArgOffset);
 420       addFrameReference(BuildMI(BB, X86::MOVmr16, 4, Reg), FI);
 421       break;
 422     case cInt:
 423       FI = MFI->CreateFixedObject(4, ArgOffset);
 424       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg), FI);
 425       break;
 426     case cLong:
 427       FI = MFI->CreateFixedObject(8, ArgOffset);
 428       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg), FI);
 429       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg+1), FI, 4);
 430       ArgOffset += 4;   // longs require 4 additional bytes
 431       break;
 432     case cFP:
 433       unsigned Opcode;
 434       if (I->getType() == Type::FloatTy) {
 435         Opcode = X86::FLDr32;
 436         FI = MFI->CreateFixedObject(4, ArgOffset);
 437       } else {
 438         Opcode = X86::FLDr64;
 439         FI = MFI->CreateFixedObject(8, ArgOffset);
 440         ArgOffset += 4;   // doubles require 4 additional bytes
 441       }
 442       addFrameReference(BuildMI(BB, Opcode, 4, Reg), FI);
 443       break;
 444     default:
 445       assert(0 && "Unhandled argument type!");
 446     }
 447     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 448   }
 449
 450   // If the function takes variable number of arguments, add a frame offset for
 451   // the start of the first vararg value... this is used to expand
 452   // llvm.va_start.
 453   if (Fn.getFunctionType()->isVarArg())
 454     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 455 }
 456
 457
 458 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 459 /// because we have to generate our sources into the source basic blocks, not
 460 /// the current one.
 461 ///
 462 void ISel::SelectPHINodes() {
 463   const TargetInstrInfo &TII = TM.getInstrInfo();
 464   const Function &LF = *F->getFunction();  // The LLVM function...
 465   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 466     const BasicBlock *BB = I;
 467     MachineBasicBlock *MBB = MBBMap[I];
 468
 469     // Loop over all of the PHI nodes in the LLVM basic block...
 470     unsigned NumPHIs = 0;
 471     for (BasicBlock::const_iterator I = BB->begin();
 472          PHINode *PN = (PHINode*)dyn_cast<PHINode>(I); ++I) {
 473
 474       // Create a new machine instr PHI node, and insert it.
 475       unsigned PHIReg = getReg(*PN);
 476       MachineInstr *PhiMI = BuildMI(X86::PHI, PN->getNumOperands(), PHIReg);
 477       MBB->insert(MBB->begin()+NumPHIs++, PhiMI);
 478
 479       MachineInstr *LongPhiMI = 0;
 480       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy) {
 481         LongPhiMI = BuildMI(X86::PHI, PN->getNumOperands(), PHIReg+1);
 482         MBB->insert(MBB->begin()+NumPHIs++, LongPhiMI);
 483       }
 484
 485       // PHIValues - Map of blocks to incoming virtual registers.  We use this
 486       // so that we only initialize one incoming value for a particular block,
 487       // even if the block has multiple entries in the PHI node.
 488       //
 489       std::map<MachineBasicBlock*, unsigned> PHIValues;
 490
 491       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 492         MachineBasicBlock *PredMBB = MBBMap[PN->getIncomingBlock(i)];
 493         unsigned ValReg;
 494         std::map<MachineBasicBlock*, unsigned>::iterator EntryIt =
 495           PHIValues.lower_bound(PredMBB);
 496
 497         if (EntryIt != PHIValues.end() && EntryIt->first == PredMBB) {
 498           // We already inserted an initialization of the register for this
 499           // predecessor.  Recycle it.
 500           ValReg = EntryIt->second;
 501
 502         } else {
 503           // Get the incoming value into a virtual register.  If it is not
 504           // already available in a virtual register, insert the computation
 505           // code into PredMBB
 506           //
 507           MachineBasicBlock::iterator PI = PredMBB->end();
 508           while (PI != PredMBB->begin() &&
 509                  TII.isTerminatorInstr((*(PI-1))->getOpcode()))
 510             --PI;
 511           ValReg = getReg(PN->getIncomingValue(i), PredMBB, PI);
 512
 513           // Remember that we inserted a value for this PHI for this predecessor
 514           PHIValues.insert(EntryIt, std::make_pair(PredMBB, ValReg));
 515         }
 516
 517         PhiMI->addRegOperand(ValReg);
 518         PhiMI->addMachineBasicBlockOperand(PredMBB);
 519         if (LongPhiMI) {
 520           LongPhiMI->addRegOperand(ValReg+1);
 521           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 522         }
 523       }
 524     }
 525   }
 526 }
 527
 528 // canFoldSetCCIntoBranch - Return the setcc instruction if we can fold it into
 529 // the conditional branch instruction which is the only user of the cc
 530 // instruction.  This is the case if the conditional branch is the only user of
 531 // the setcc, and if the setcc is in the same basic block as the conditional
 532 // branch.  We also don't handle long arguments below, so we reject them here as
 533 // well.
 534 //
 535 static SetCondInst *canFoldSetCCIntoBranch(Value *V) {
 536   if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 537     if (SCI->use_size() == 1 && isa<BranchInst>(SCI->use_back()) &&
 538         SCI->getParent() == cast<BranchInst>(SCI->use_back())->getParent()) {
 539       const Type *Ty = SCI->getOperand(0)->getType();
 540       if (Ty != Type::LongTy && Ty != Type::ULongTy)
 541         return SCI;
 542     }
 543   return 0;
 544 }
 545
 546 // Return a fixed numbering for setcc instructions which does not depend on the
 547 // order of the opcodes.
 548 //
 549 static unsigned getSetCCNumber(unsigned Opcode) {
 550   switch(Opcode) {
 551   default: assert(0 && "Unknown setcc instruction!");
 552   case Instruction::SetEQ: return 0;
 553   case Instruction::SetNE: return 1;
 554   case Instruction::SetLT: return 2;
 555   case Instruction::SetGE: return 3;
 556   case Instruction::SetGT: return 4;
 557   case Instruction::SetLE: return 5;
 558   }
 559 }
 560
 561 // LLVM  -> X86 signed  X86 unsigned
 562 // -----    ----------  ------------
 563 // seteq -> sete        sete
 564 // setne -> setne       setne
 565 // setlt -> setl        setb
 566 // setge -> setge       setae
 567 // setgt -> setg        seta
 568 // setle -> setle       setbe
 569 static const unsigned SetCCOpcodeTab[2][6] = {
 570   {X86::SETEr, X86::SETNEr, X86::SETBr, X86::SETAEr, X86::SETAr, X86::SETBEr},
 571   {X86::SETEr, X86::SETNEr, X86::SETLr, X86::SETGEr, X86::SETGr, X86::SETLEr},
 572 };
 573
 574 bool ISel::EmitComparisonGetSignedness(unsigned OpNum, Value *Op0, Value *Op1) {
 575
 576   // The arguments are already supposed to be of the same type.
 577   const Type *CompTy = Op0->getType();
 578   bool isSigned = CompTy->isSigned();
 579   unsigned Class = getClassB(CompTy);
 580   unsigned Op0r = getReg(Op0);
 581
 582   // Special case handling of: cmp R, i
 583   if (Class == cByte || Class == cShort || Class == cInt)
 584     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 585       uint64_t Op1v = cast<ConstantInt>(CI)->getRawValue();
 586
 587       // Mask off any upper bits of the constant, if there are any...
 588       Op1v &= (1ULL << (8 << Class)) - 1;
 589
 590       switch (Class) {
 591       case cByte:  BuildMI(BB, X86::CMPri8, 2).addReg(Op0r).addZImm(Op1v);break;
 592       case cShort: BuildMI(BB, X86::CMPri16,2).addReg(Op0r).addZImm(Op1v);break;
 593       case cInt:   BuildMI(BB, X86::CMPri32,2).addReg(Op0r).addZImm(Op1v);break;
 594       default:
 595         assert(0 && "Invalid class!");
 596       }
 597       return isSigned;
 598     }
 599
 600   unsigned Op1r = getReg(Op1);
 601   switch (Class) {
 602   default: assert(0 && "Unknown type class!");
 603     // Emit: cmp <var1>, <var2> (do the comparison).  We can
 604     // compare 8-bit with 8-bit, 16-bit with 16-bit, 32-bit with
 605     // 32-bit.
 606   case cByte:
 607     BuildMI(BB, X86::CMPrr8, 2).addReg(Op0r).addReg(Op1r);
 608     break;
 609   case cShort:
 610     BuildMI(BB, X86::CMPrr16, 2).addReg(Op0r).addReg(Op1r);
 611     break;
 612   case cInt:
 613     BuildMI(BB, X86::CMPrr32, 2).addReg(Op0r).addReg(Op1r);
 614     break;
 615   case cFP:
 616     BuildMI(BB, X86::FpUCOM, 2).addReg(Op0r).addReg(Op1r);
 617     BuildMI(BB, X86::FNSTSWr8, 0);
 618     BuildMI(BB, X86::SAHF, 1);
 619     isSigned = false;   // Compare with unsigned operators
 620     break;
 621
 622   case cLong:
 623     if (OpNum < 2) {    // seteq, setne
 624       unsigned LoTmp = makeAnotherReg(Type::IntTy);
 625       unsigned HiTmp = makeAnotherReg(Type::IntTy);
 626       unsigned FinalTmp = makeAnotherReg(Type::IntTy);
 627       BuildMI(BB, X86::XORrr32, 2, LoTmp).addReg(Op0r).addReg(Op1r);
 628       BuildMI(BB, X86::XORrr32, 2, HiTmp).addReg(Op0r+1).addReg(Op1r+1);
 629       BuildMI(BB, X86::ORrr32,  2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
 630       break;  // Allow the sete or setne to be generated from flags set by OR
 631     } else {
 632       // Emit a sequence of code which compares the high and low parts once
 633       // each, then uses a conditional move to handle the overflow case.  For
 634       // example, a setlt for long would generate code like this:
 635       //
 636       // AL = lo(op1) < lo(op2)   // Signedness depends on operands
 637       // BL = hi(op1) < hi(op2)   // Always unsigned comparison
 638       // dest = hi(op1) == hi(op2) ? AL : BL;
 639       //
 640
 641       // FIXME: This would be much better if we had hierarchical register
 642       // classes!  Until then, hardcode registers so that we can deal with their
 643       // aliases (because we don't have conditional byte moves).
 644       //
 645       BuildMI(BB, X86::CMPrr32, 2).addReg(Op0r).addReg(Op1r);
 646       BuildMI(BB, SetCCOpcodeTab[0][OpNum], 0, X86::AL);
 647       BuildMI(BB, X86::CMPrr32, 2).addReg(Op0r+1).addReg(Op1r+1);
 648       BuildMI(BB, SetCCOpcodeTab[isSigned][OpNum], 0, X86::BL);
 649       BuildMI(BB, X86::IMPLICIT_DEF, 0, X86::BH);
 650       BuildMI(BB, X86::IMPLICIT_DEF, 0, X86::AH);
 651       BuildMI(BB, X86::CMOVErr16, 2, X86::BX).addReg(X86::BX).addReg(X86::AX);
 652       // NOTE: visitSetCondInst knows that the value is dumped into the BL
 653       // register at this point for long values...
 654       return isSigned;
 655     }
 656   }
 657   return isSigned;
 658 }
 659
 660
 661 /// SetCC instructions - Here we just emit boilerplate code to set a byte-sized
 662 /// register, then move it to wherever the result should be.
 663 ///
 664 void ISel::visitSetCondInst(SetCondInst &I) {
 665   if (canFoldSetCCIntoBranch(&I)) return;  // Fold this into a branch...
 666
 667   unsigned OpNum = getSetCCNumber(I.getOpcode());
 668   unsigned DestReg = getReg(I);
 669   bool isSigned = EmitComparisonGetSignedness(OpNum, I.getOperand(0),
 670                                               I.getOperand(1));
 671
 672   if (getClassB(I.getOperand(0)->getType()) != cLong || OpNum < 2) {
 673     // Handle normal comparisons with a setcc instruction...
 674     BuildMI(BB, SetCCOpcodeTab[isSigned][OpNum], 0, DestReg);
 675   } else {
 676     // Handle long comparisons by copying the value which is already in BL into
 677     // the register we want...
 678     BuildMI(BB, X86::MOVrr8, 1, DestReg).addReg(X86::BL);
 679   }
 680 }
 681
 682 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
 683 /// operand, in the specified target register.
 684 void ISel::promote32(unsigned targetReg, const ValueRecord &VR) {
 685   bool isUnsigned = VR.Ty->isUnsigned();
 686
 687   // Make sure we have the register number for this value...
 688   unsigned Reg = VR.Val ? getReg(VR.Val) : VR.Reg;
 689
 690   switch (getClassB(VR.Ty)) {
 691   case cByte:
 692     // Extend value into target register (8->32)
 693     if (isUnsigned)
 694       BuildMI(BB, X86::MOVZXr32r8, 1, targetReg).addReg(Reg);
 695     else
 696       BuildMI(BB, X86::MOVSXr32r8, 1, targetReg).addReg(Reg);
 697     break;
 698   case cShort:
 699     // Extend value into target register (16->32)
 700     if (isUnsigned)
 701       BuildMI(BB, X86::MOVZXr32r16, 1, targetReg).addReg(Reg);
 702     else
 703       BuildMI(BB, X86::MOVSXr32r16, 1, targetReg).addReg(Reg);
 704     break;
 705   case cInt:
 706     // Move value into target register (32->32)
 707     BuildMI(BB, X86::MOVrr32, 1, targetReg).addReg(Reg);
 708     break;
 709   default:
 710     assert(0 && "Unpromotable operand class in promote32");
 711   }
 712 }
 713
 714 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 715 /// we have the following possibilities:
 716 ///
 717 ///   ret void: No return value, simply emit a 'ret' instruction
 718 ///   ret sbyte, ubyte : Extend value into EAX and return
 719 ///   ret short, ushort: Extend value into EAX and return
 720 ///   ret int, uint    : Move value into EAX and return
 721 ///   ret pointer      : Move value into EAX and return
 722 ///   ret long, ulong  : Move value into EAX/EDX and return
 723 ///   ret float/double : Top of FP stack
 724 ///
 725 void ISel::visitReturnInst(ReturnInst &I) {
 726   if (I.getNumOperands() == 0) {
 727     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
 728     return;
 729   }
 730
 731   Value *RetVal = I.getOperand(0);
 732   unsigned RetReg = getReg(RetVal);
 733   switch (getClassB(RetVal->getType())) {
 734   case cByte:   // integral return values: extend or move into EAX and return
 735   case cShort:
 736   case cInt:
 737     promote32(X86::EAX, ValueRecord(RetReg, RetVal->getType()));
 738     // Declare that EAX is live on exit
 739     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
 740     break;
 741   case cFP:                   // Floats & Doubles: Return in ST(0)
 742     BuildMI(BB, X86::FpSETRESULT, 1).addReg(RetReg);
 743     // Declare that top-of-stack is live on exit
 744     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
 745     break;
 746   case cLong:
 747     BuildMI(BB, X86::MOVrr32, 1, X86::EAX).addReg(RetReg);
 748     BuildMI(BB, X86::MOVrr32, 1, X86::EDX).addReg(RetReg+1);
 749     // Declare that EAX & EDX are live on exit
 750     BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX).addReg(X86::ESP);
 751     break;
 752   default:
 753     visitInstruction(I);
 754   }
 755   // Emit a 'ret' instruction
 756   BuildMI(BB, X86::RET, 0);
 757 }
 758
 759 // getBlockAfter - Return the basic block which occurs lexically after the
 760 // specified one.
 761 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
 762   Function::iterator I = BB; ++I;  // Get iterator to next block
 763   return I != BB->getParent()->end() ? &*I : 0;
 764 }
 765
 766 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
 767 /// that since code layout is frozen at this point, that if we are trying to
 768 /// jump to a block that is the immediate successor of the current block, we can
 769 /// just make a fall-through (but we don't currently).
 770 ///
 771 void ISel::visitBranchInst(BranchInst &BI) {
 772   BasicBlock *NextBB = getBlockAfter(BI.getParent());  // BB after current one
 773
 774   if (!BI.isConditional()) {  // Unconditional branch?
 775     if (BI.getSuccessor(0) != NextBB)
 776       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 777     return;
 778   }
 779
 780   // See if we can fold the setcc into the branch itself...
 781   SetCondInst *SCI = canFoldSetCCIntoBranch(BI.getCondition());
 782   if (SCI == 0) {
 783     // Nope, cannot fold setcc into this branch.  Emit a branch on a condition
 784     // computed some other way...
 785     unsigned condReg = getReg(BI.getCondition());
 786     BuildMI(BB, X86::CMPri8, 2).addReg(condReg).addZImm(0);
 787     if (BI.getSuccessor(1) == NextBB) {
 788       if (BI.getSuccessor(0) != NextBB)
 789         BuildMI(BB, X86::JNE, 1).addPCDisp(BI.getSuccessor(0));
 790     } else {
 791       BuildMI(BB, X86::JE, 1).addPCDisp(BI.getSuccessor(1));
 792
 793       if (BI.getSuccessor(0) != NextBB)
 794         BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 795     }
 796     return;
 797   }
 798
 799   unsigned OpNum = getSetCCNumber(SCI->getOpcode());
 800   bool isSigned = EmitComparisonGetSignedness(OpNum, SCI->getOperand(0),
 801                                               SCI->getOperand(1));
 802
 803   // LLVM  -> X86 signed  X86 unsigned
 804   // -----    ----------  ------------
 805   // seteq -> je          je
 806   // setne -> jne         jne
 807   // setlt -> jl          jb
 808   // setge -> jge         jae
 809   // setgt -> jg          ja
 810   // setle -> jle         jbe
 811   static const unsigned OpcodeTab[2][6] = {
 812     { X86::JE, X86::JNE, X86::JB, X86::JAE, X86::JA, X86::JBE },
 813     { X86::JE, X86::JNE, X86::JL, X86::JGE, X86::JG, X86::JLE },
 814   };
 815
 816   if (BI.getSuccessor(0) != NextBB) {
 817     BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(0));
 818     if (BI.getSuccessor(1) != NextBB)
 819       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(1));
 820   } else {
 821     // Change to the inverse condition...
 822     if (BI.getSuccessor(1) != NextBB) {
 823       OpNum ^= 1;
 824       BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(1));
 825     }
 826   }
 827 }
 828
 829
 830 /// doCall - This emits an abstract call instruction, setting up the arguments
 831 /// and the return value as appropriate.  For the actual function call itself,
 832 /// it inserts the specified CallMI instruction into the stream.
 833 ///
 834 void ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 835                   const std::vector<ValueRecord> &Args) {
 836
 837   // Count how many bytes are to be pushed on the stack...
 838   unsigned NumBytes = 0;
 839
 840   if (!Args.empty()) {
 841     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 842       switch (getClassB(Args[i].Ty)) {
 843       case cByte: case cShort: case cInt:
 844         NumBytes += 4; break;
 845       case cLong:
 846         NumBytes += 8; break;
 847       case cFP:
 848         NumBytes += Args[i].Ty == Type::FloatTy ? 4 : 8;
 849         break;
 850       default: assert(0 && "Unknown class!");
 851       }
 852
 853     // Adjust the stack pointer for the new arguments...
 854     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(NumBytes);
 855
 856     // Arguments go on the stack in reverse order, as specified by the ABI.
 857     unsigned ArgOffset = 0;
 858     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 859       unsigned ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
 860       switch (getClassB(Args[i].Ty)) {
 861       case cByte:
 862       case cShort: {
 863         // Promote arg to 32 bits wide into a temporary register...
 864         unsigned R = makeAnotherReg(Type::UIntTy);
 865         promote32(R, Args[i]);
 866         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 867                      X86::ESP, ArgOffset).addReg(R);
 868         break;
 869       }
 870       case cInt:
 871         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 872                      X86::ESP, ArgOffset).addReg(ArgReg);
 873         break;
 874       case cLong:
 875         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 876                      X86::ESP, ArgOffset).addReg(ArgReg);
 877         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 878                      X86::ESP, ArgOffset+4).addReg(ArgReg+1);
 879         ArgOffset += 4;        // 8 byte entry, not 4.
 880         break;
 881
 882       case cFP:
 883         if (Args[i].Ty == Type::FloatTy) {
 884           addRegOffset(BuildMI(BB, X86::FSTr32, 5),
 885                        X86::ESP, ArgOffset).addReg(ArgReg);
 886         } else {
 887           assert(Args[i].Ty == Type::DoubleTy && "Unknown FP type!");
 888           addRegOffset(BuildMI(BB, X86::FSTr64, 5),
 889                        X86::ESP, ArgOffset).addReg(ArgReg);
 890           ArgOffset += 4;       // 8 byte entry, not 4.
 891         }
 892         break;
 893
 894       default: assert(0 && "Unknown class!");
 895       }
 896       ArgOffset += 4;
 897     }
 898   } else {
 899     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(0);
 900   }
 901
 902   BB->push_back(CallMI);
 903
 904   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addZImm(NumBytes);
 905
 906   // If there is a return value, scavenge the result from the location the call
 907   // leaves it in...
 908   //
 909   if (Ret.Ty != Type::VoidTy) {
 910     unsigned DestClass = getClassB(Ret.Ty);
 911     switch (DestClass) {
 912     case cByte:
 913     case cShort:
 914     case cInt: {
 915       // Integral results are in %eax, or the appropriate portion
 916       // thereof.
 917       static const unsigned regRegMove[] = {
 918         X86::MOVrr8, X86::MOVrr16, X86::MOVrr32
 919       };
 920       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
 921       BuildMI(BB, regRegMove[DestClass], 1, Ret.Reg).addReg(AReg[DestClass]);
 922       break;
 923     }
 924     case cFP:     // Floating-point return values live in %ST(0)
 925       BuildMI(BB, X86::FpGETRESULT, 1, Ret.Reg);
 926       break;
 927     case cLong:   // Long values are left in EDX:EAX
 928       BuildMI(BB, X86::MOVrr32, 1, Ret.Reg).addReg(X86::EAX);
 929       BuildMI(BB, X86::MOVrr32, 1, Ret.Reg+1).addReg(X86::EDX);
 930       break;
 931     default: assert(0 && "Unknown class!");
 932     }
 933   }
 934 }
 935
 936
 937 /// visitCallInst - Push args on stack and do a procedure call instruction.
 938 void ISel::visitCallInst(CallInst &CI) {
 939   MachineInstr *TheCall;
 940   if (Function *F = CI.getCalledFunction()) {
 941     // Is it an intrinsic function call?
 942     if (LLVMIntrinsic::ID ID = (LLVMIntrinsic::ID)F->getIntrinsicID()) {
 943       visitIntrinsicCall(ID, CI);   // Special intrinsics are not handled here
 944       return;
 945     }
 946
 947     // Emit a CALL instruction with PC-relative displacement.
 948     TheCall = BuildMI(X86::CALLpcrel32, 1).addGlobalAddress(F, true);
 949   } else {  // Emit an indirect call...
 950     unsigned Reg = getReg(CI.getCalledValue());
 951     TheCall = BuildMI(X86::CALLr32, 1).addReg(Reg);
 952   }
 953
 954   std::vector<ValueRecord> Args;
 955   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
 956     Args.push_back(ValueRecord(CI.getOperand(i)));
 957
 958   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
 959   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args);
 960 }
 961
 962 void ISel::visitIntrinsicCall(LLVMIntrinsic::ID ID, CallInst &CI) {
 963   unsigned TmpReg1, TmpReg2;
 964   switch (ID) {
 965   case LLVMIntrinsic::va_start:
 966     // Get the address of the first vararg value...
 967     TmpReg1 = makeAnotherReg(Type::UIntTy);
 968     addFrameReference(BuildMI(BB, X86::LEAr32, 5, TmpReg1), VarArgsFrameIndex);
 969     TmpReg2 = getReg(CI.getOperand(1));
 970     addDirectMem(BuildMI(BB, X86::MOVrm32, 5), TmpReg2).addReg(TmpReg1);
 971     return;
 972
 973   case LLVMIntrinsic::va_end: return;   // Noop on X86
 974   case LLVMIntrinsic::va_copy:
 975     TmpReg1 = getReg(CI.getOperand(2));  // Get existing va_list
 976     TmpReg2 = getReg(CI.getOperand(1));  // Get va_list* to store into
 977     addDirectMem(BuildMI(BB, X86::MOVrm32, 5), TmpReg2).addReg(TmpReg1);
 978     return;
 979
 980   case LLVMIntrinsic::longjmp:
 981     BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("abort", true);
 982     return;
 983
 984   case LLVMIntrinsic::setjmp:
 985     // Setjmp always returns zero...
 986     BuildMI(BB, X86::MOVir32, 1, getReg(CI)).addZImm(0);
 987     return;
 988   default: assert(0 && "Unknown intrinsic for X86!");
 989   }
 990 }
 991
 992
 993 /// visitSimpleBinary - Implement simple binary operators for integral types...
 994 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
 995 /// Xor.
 996 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
 997   unsigned DestReg = getReg(B);
 998   MachineBasicBlock::iterator MI = BB->end();
 999   emitSimpleBinaryOperation(BB, MI, B.getOperand(0), B.getOperand(1),
1000                             OperatorClass, DestReg);
1001 }
1002
1003 /// visitSimpleBinary - Implement simple binary operators for integral types...
1004 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or,
1005 /// 4 for Xor.
1006 ///
1007 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
1008 /// and constant expression support.
1009 void ISel::emitSimpleBinaryOperation(MachineBasicBlock *BB,
1010                                      MachineBasicBlock::iterator &IP,
1011                                      Value *Op0, Value *Op1,
1012                                      unsigned OperatorClass,unsigned TargetReg){
1013   unsigned Class = getClassB(Op0->getType());
1014   if (!isa<ConstantInt>(Op1) || Class == cLong) {
1015     static const unsigned OpcodeTab[][4] = {
1016       // Arithmetic operators
1017       { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32, X86::FpADD },  // ADD
1018       { X86::SUBrr8, X86::SUBrr16, X86::SUBrr32, X86::FpSUB },  // SUB
1019
1020       // Bitwise operators
1021       { X86::ANDrr8, X86::ANDrr16, X86::ANDrr32, 0 },  // AND
1022       { X86:: ORrr8, X86:: ORrr16, X86:: ORrr32, 0 },  // OR
1023       { X86::XORrr8, X86::XORrr16, X86::XORrr32, 0 },  // XOR
1024     };
1025
1026     bool isLong = false;
1027     if (Class == cLong) {
1028       isLong = true;
1029       Class = cInt;          // Bottom 32 bits are handled just like ints
1030     }
1031
1032     unsigned Opcode = OpcodeTab[OperatorClass][Class];
1033     assert(Opcode && "Floating point arguments to logical inst?");
1034     unsigned Op0r = getReg(Op0, BB, IP);
1035     unsigned Op1r = getReg(Op1, BB, IP);
1036     BMI(BB, IP, Opcode, 2, TargetReg).addReg(Op0r).addReg(Op1r);
1037
1038     if (isLong) {        // Handle the upper 32 bits of long values...
1039       static const unsigned TopTab[] = {
1040         X86::ADCrr32, X86::SBBrr32, X86::ANDrr32, X86::ORrr32, X86::XORrr32
1041       };
1042       BMI(BB, IP, TopTab[OperatorClass], 2,
1043           TargetReg+1).addReg(Op0r+1).addReg(Op1r+1);
1044     }
1045   } else {
1046     // Special case: op Reg, <const>
1047     ConstantInt *Op1C = cast<ConstantInt>(Op1);
1048
1049     static const unsigned OpcodeTab[][3] = {
1050       // Arithmetic operators
1051       { X86::ADDri8, X86::ADDri16, X86::ADDri32 },  // ADD
1052       { X86::SUBri8, X86::SUBri16, X86::SUBri32 },  // SUB
1053
1054       // Bitwise operators
1055       { X86::ANDri8, X86::ANDri16, X86::ANDri32 },  // AND
1056       { X86:: ORri8, X86:: ORri16, X86:: ORri32 },  // OR
1057       { X86::XORri8, X86::XORri16, X86::XORri32 },  // XOR
1058     };
1059
1060     assert(Class < 3 && "General code handles 64-bit integer types!");
1061     unsigned Opcode = OpcodeTab[OperatorClass][Class];
1062     unsigned Op0r = getReg(Op0, BB, IP);
1063     uint64_t Op1v = cast<ConstantInt>(Op1C)->getRawValue();
1064
1065     // Mask off any upper bits of the constant, if there are any...
1066     Op1v &= (1ULL << (8 << Class)) - 1;
1067     BMI(BB, IP, Opcode, 2, TargetReg).addReg(Op0r).addZImm(Op1v);
1068   }
1069 }
1070
1071 /// doMultiply - Emit appropriate instructions to multiply together the
1072 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
1073 /// result should be given as DestTy.
1074 ///
1075 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI,
1076                       unsigned DestReg, const Type *DestTy,
1077                       unsigned op0Reg, unsigned op1Reg) {
1078   unsigned Class = getClass(DestTy);
1079   switch (Class) {
1080   case cFP:              // Floating point multiply
1081     BMI(BB, MBBI, X86::FpMUL, 2, DestReg).addReg(op0Reg).addReg(op1Reg);
1082     return;
1083   case cInt:
1084   case cShort:
1085     BMI(BB, MBBI, Class == cInt ? X86::IMULr32 : X86::IMULr16, 2, DestReg)
1086       .addReg(op0Reg).addReg(op1Reg);
1087     return;
1088   case cByte:
1089     // Must use the MUL instruction, which forces use of AL...
1090     BMI(MBB, MBBI, X86::MOVrr8, 1, X86::AL).addReg(op0Reg);
1091     BMI(MBB, MBBI, X86::MULr8, 1).addReg(op1Reg);
1092     BMI(MBB, MBBI, X86::MOVrr8, 1, DestReg).addReg(X86::AL);
1093     return;
1094   default:
1095   case cLong: assert(0 && "doMultiply cannot operate on LONG values!");
1096   }
1097 }
1098
1099 /// visitMul - Multiplies are not simple binary operators because they must deal
1100 /// with the EAX register explicitly.
1101 ///
1102 void ISel::visitMul(BinaryOperator &I) {
1103   unsigned Op0Reg  = getReg(I.getOperand(0));
1104   unsigned Op1Reg  = getReg(I.getOperand(1));
1105   unsigned DestReg = getReg(I);
1106
1107   // Simple scalar multiply?
1108   if (I.getType() != Type::LongTy && I.getType() != Type::ULongTy) {
1109     MachineBasicBlock::iterator MBBI = BB->end();
1110     doMultiply(BB, MBBI, DestReg, I.getType(), Op0Reg, Op1Reg);
1111   } else {
1112     // Long value.  We have to do things the hard way...
1113     // Multiply the two low parts... capturing carry into EDX
1114     BuildMI(BB, X86::MOVrr32, 1, X86::EAX).addReg(Op0Reg);
1115     BuildMI(BB, X86::MULr32, 1).addReg(Op1Reg);  // AL*BL
1116
1117     unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
1118     BuildMI(BB, X86::MOVrr32, 1, DestReg).addReg(X86::EAX);     // AL*BL
1119     BuildMI(BB, X86::MOVrr32, 1, OverflowReg).addReg(X86::EDX); // AL*BL >> 32
1120
1121     MachineBasicBlock::iterator MBBI = BB->end();
1122     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
1123     BMI(BB, MBBI, X86::IMULr32, 2, AHBLReg).addReg(Op0Reg+1).addReg(Op1Reg);
1124
1125     unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
1126     BuildMI(BB, X86::ADDrr32, 2,                         // AH*BL+(AL*BL >> 32)
1127             AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
1128
1129     MBBI = BB->end();
1130     unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
1131     BMI(BB, MBBI, X86::IMULr32, 2, ALBHReg).addReg(Op0Reg).addReg(Op1Reg+1);
1132
1133     BuildMI(BB, X86::ADDrr32, 2,               // AL*BH + AH*BL + (AL*BL >> 32)
1134             DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
1135   }
1136 }
1137
1138
1139 /// visitDivRem - Handle division and remainder instructions... these
1140 /// instruction both require the same instructions to be generated, they just
1141 /// select the result from a different register.  Note that both of these
1142 /// instructions work differently for signed and unsigned operands.
1143 ///
1144 void ISel::visitDivRem(BinaryOperator &I) {
1145   unsigned Class = getClass(I.getType());
1146   unsigned Op0Reg, Op1Reg, ResultReg = getReg(I);
1147
1148   switch (Class) {
1149   case cFP:              // Floating point divide
1150     if (I.getOpcode() == Instruction::Div) {
1151       Op0Reg = getReg(I.getOperand(0));
1152       Op1Reg = getReg(I.getOperand(1));
1153       BuildMI(BB, X86::FpDIV, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
1154     } else {               // Floating point remainder...
1155       MachineInstr *TheCall =
1156         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
1157       std::vector<ValueRecord> Args;
1158       Args.push_back(ValueRecord(I.getOperand(0)));
1159       Args.push_back(ValueRecord(I.getOperand(1)));
1160       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
1161     }
1162     return;
1163   case cLong: {
1164     static const char *FnName[] =
1165       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
1166
1167     unsigned NameIdx = I.getType()->isUnsigned()*2;
1168     NameIdx += I.getOpcode() == Instruction::Div;
1169     MachineInstr *TheCall =
1170       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
1171
1172     std::vector<ValueRecord> Args;
1173     Args.push_back(ValueRecord(I.getOperand(0)));
1174     Args.push_back(ValueRecord(I.getOperand(1)));
1175     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
1176     return;
1177   }
1178   case cByte: case cShort: case cInt:
1179     break;          // Small integerals, handled below...
1180   default: assert(0 && "Unknown class!");
1181   }
1182
1183   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
1184   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
1185   static const unsigned SarOpcode[]={ X86::SARir8, X86::SARir16, X86::SARir32 };
1186   static const unsigned ClrOpcode[]={ X86::XORrr8, X86::XORrr16, X86::XORrr32 };
1187   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
1188
1189   static const unsigned DivOpcode[][4] = {
1190     { X86::DIVr8 , X86::DIVr16 , X86::DIVr32 , 0 },  // Unsigned division
1191     { X86::IDIVr8, X86::IDIVr16, X86::IDIVr32, 0 },  // Signed division
1192   };
1193
1194   bool isSigned   = I.getType()->isSigned();
1195   unsigned Reg    = Regs[Class];
1196   unsigned ExtReg = ExtRegs[Class];
1197
1198   // Put the first operand into one of the A registers...
1199   Op0Reg = getReg(I.getOperand(0));
1200   BuildMI(BB, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
1201
1202   if (isSigned) {
1203     // Emit a sign extension instruction...
1204     unsigned ShiftResult = makeAnotherReg(I.getType());
1205     BuildMI(BB, SarOpcode[Class], 2, ShiftResult).addReg(Op0Reg).addZImm(31);
1206     BuildMI(BB, MovOpcode[Class], 1, ExtReg).addReg(ShiftResult);
1207   } else {
1208     // If unsigned, emit a zeroing instruction... (reg = xor reg, reg)
1209     BuildMI(BB, ClrOpcode[Class], 2, ExtReg).addReg(ExtReg).addReg(ExtReg);
1210   }
1211
1212   // Emit the appropriate divide or remainder instruction...
1213   Op1Reg = getReg(I.getOperand(1));
1214   BuildMI(BB, DivOpcode[isSigned][Class], 1).addReg(Op1Reg);
1215
1216   // Figure out which register we want to pick the result out of...
1217   unsigned DestReg = (I.getOpcode() == Instruction::Div) ? Reg : ExtReg;
1218
1219   // Put the result into the destination register...
1220   BuildMI(BB, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
1221 }
1222
1223
1224 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
1225 /// for constant immediate shift values, and for constant immediate
1226 /// shift values equal to 1. Even the general case is sort of special,
1227 /// because the shift amount has to be in CL, not just any old register.
1228 ///
1229 void ISel::visitShiftInst(ShiftInst &I) {
1230   unsigned SrcReg = getReg(I.getOperand(0));
1231   unsigned DestReg = getReg(I);
1232   bool isLeftShift = I.getOpcode() == Instruction::Shl;
1233   bool isSigned = I.getType()->isSigned();
1234   unsigned Class = getClass(I.getType());
1235
1236   static const unsigned ConstantOperand[][4] = {
1237     { X86::SHRir8, X86::SHRir16, X86::SHRir32, X86::SHRDir32 },  // SHR
1238     { X86::SARir8, X86::SARir16, X86::SARir32, X86::SHRDir32 },  // SAR
1239     { X86::SHLir8, X86::SHLir16, X86::SHLir32, X86::SHLDir32 },  // SHL
1240     { X86::SHLir8, X86::SHLir16, X86::SHLir32, X86::SHLDir32 },  // SAL = SHL
1241   };
1242
1243   static const unsigned NonConstantOperand[][4] = {
1244     { X86::SHRrr8, X86::SHRrr16, X86::SHRrr32 },  // SHR
1245     { X86::SARrr8, X86::SARrr16, X86::SARrr32 },  // SAR
1246     { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32 },  // SHL
1247     { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32 },  // SAL = SHL
1248   };
1249
1250   // Longs, as usual, are handled specially...
1251   if (Class == cLong) {
1252     // If we have a constant shift, we can generate much more efficient code
1253     // than otherwise...
1254     //
1255     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getOperand(1))) {
1256       unsigned Amount = CUI->getValue();
1257       if (Amount < 32) {
1258         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1259         if (isLeftShift) {
1260           BuildMI(BB, Opc[3], 3,
1261                   DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addZImm(Amount);
1262           BuildMI(BB, Opc[2], 2, DestReg).addReg(SrcReg).addZImm(Amount);
1263         } else {
1264           BuildMI(BB, Opc[3], 3,
1265                   DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addZImm(Amount);
1266           BuildMI(BB, Opc[2], 2, DestReg+1).addReg(SrcReg+1).addZImm(Amount);
1267         }
1268       } else {                 // Shifting more than 32 bits
1269         Amount -= 32;
1270         if (isLeftShift) {
1271           BuildMI(BB, X86::SHLir32, 2,DestReg+1).addReg(SrcReg).addZImm(Amount);
1272           BuildMI(BB, X86::MOVir32, 1,DestReg  ).addZImm(0);
1273         } else {
1274           unsigned Opcode = isSigned ? X86::SARir32 : X86::SHRir32;
1275           BuildMI(BB, Opcode, 2, DestReg).addReg(SrcReg+1).addZImm(Amount);
1276           BuildMI(BB, X86::MOVir32, 1, DestReg+1).addZImm(0);
1277         }
1278       }
1279     } else {
1280       unsigned TmpReg = makeAnotherReg(Type::IntTy);
1281
1282       if (!isLeftShift && isSigned) {
1283         // If this is a SHR of a Long, then we need to do funny sign extension
1284         // stuff.  TmpReg gets the value to use as the high-part if we are
1285         // shifting more than 32 bits.
1286         BuildMI(BB, X86::SARir32, 2, TmpReg).addReg(SrcReg).addZImm(31);
1287       } else {
1288         // Other shifts use a fixed zero value if the shift is more than 32
1289         // bits.
1290         BuildMI(BB, X86::MOVir32, 1, TmpReg).addZImm(0);
1291       }
1292
1293       // Initialize CL with the shift amount...
1294       unsigned ShiftAmount = getReg(I.getOperand(1));
1295       BuildMI(BB, X86::MOVrr8, 1, X86::CL).addReg(ShiftAmount);
1296
1297       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
1298       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
1299       if (isLeftShift) {
1300         // TmpReg2 = shld inHi, inLo
1301         BuildMI(BB, X86::SHLDrr32, 2, TmpReg2).addReg(SrcReg+1).addReg(SrcReg);
1302         // TmpReg3 = shl  inLo, CL
1303         BuildMI(BB, X86::SHLrr32, 1, TmpReg3).addReg(SrcReg);
1304
1305         // Set the flags to indicate whether the shift was by more than 32 bits.
1306         BuildMI(BB, X86::TESTri8, 2).addReg(X86::CL).addZImm(32);
1307
1308         // DestHi = (>32) ? TmpReg3 : TmpReg2;
1309         BuildMI(BB, X86::CMOVNErr32, 2,
1310                 DestReg+1).addReg(TmpReg2).addReg(TmpReg3);
1311         // DestLo = (>32) ? TmpReg : TmpReg3;
1312         BuildMI(BB, X86::CMOVNErr32, 2, DestReg).addReg(TmpReg3).addReg(TmpReg);
1313       } else {
1314         // TmpReg2 = shrd inLo, inHi
1315         BuildMI(BB, X86::SHRDrr32, 2, TmpReg2).addReg(SrcReg).addReg(SrcReg+1);
1316         // TmpReg3 = s[ah]r  inHi, CL
1317         BuildMI(BB, isSigned ? X86::SARrr32 : X86::SHRrr32, 1, TmpReg3)
1318                        .addReg(SrcReg+1);
1319
1320         // Set the flags to indicate whether the shift was by more than 32 bits.
1321         BuildMI(BB, X86::TESTri8, 2).addReg(X86::CL).addZImm(32);
1322
1323         // DestLo = (>32) ? TmpReg3 : TmpReg2;
1324         BuildMI(BB, X86::CMOVNErr32, 2,
1325                 DestReg).addReg(TmpReg2).addReg(TmpReg3);
1326
1327         // DestHi = (>32) ? TmpReg : TmpReg3;
1328         BuildMI(BB, X86::CMOVNErr32, 2,
1329                 DestReg+1).addReg(TmpReg3).addReg(TmpReg);
1330       }
1331     }
1332     return;
1333   }
1334
1335   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getOperand(1))) {
1336     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
1337     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
1338
1339     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1340     BuildMI(BB, Opc[Class], 2, DestReg).addReg(SrcReg).addZImm(CUI->getValue());
1341   } else {                  // The shift amount is non-constant.
1342     BuildMI(BB, X86::MOVrr8, 1, X86::CL).addReg(getReg(I.getOperand(1)));
1343
1344     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
1345     BuildMI(BB, Opc[Class], 1, DestReg).addReg(SrcReg);
1346   }
1347 }
1348
1349
1350 /// doFPLoad - This method is used to load an FP value from memory using the
1351 /// current endianness.  NOTE: This method returns a partially constructed load
1352 /// instruction which needs to have the memory source filled in still.
1353 ///
1354 MachineInstr *ISel::doFPLoad(MachineBasicBlock *MBB,
1355                              MachineBasicBlock::iterator &MBBI,
1356                              const Type *Ty, unsigned DestReg) {
1357   assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
1358   unsigned LoadOpcode = Ty == Type::FloatTy ? X86::FLDr32 : X86::FLDr64;
1359
1360   if (TM.getTargetData().isLittleEndian()) // fast path...
1361     return BMI(MBB, MBBI, LoadOpcode, 4, DestReg);
1362
1363   // If we are big-endian, start by creating an LEA instruction to represent the
1364   // address of the memory location to load from...
1365   //
1366   unsigned SrcAddrReg = makeAnotherReg(Type::UIntTy);
1367   MachineInstr *Result = BMI(MBB, MBBI, X86::LEAr32, 5, SrcAddrReg);
1368
1369   // Allocate a temporary stack slot to transform the value into...
1370   int FrameIdx = F->getFrameInfo()->CreateStackObject(Ty, TM.getTargetData());
1371
1372   // Perform the bswaps 32 bits at a time...
1373   unsigned TmpReg1 = makeAnotherReg(Type::UIntTy);
1374   unsigned TmpReg2 = makeAnotherReg(Type::UIntTy);
1375   addDirectMem(BMI(MBB, MBBI, X86::MOVmr32, 4, TmpReg1), SrcAddrReg);
1376   BMI(MBB, MBBI, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1377   unsigned Offset = (Ty == Type::DoubleTy) << 2;
1378   addFrameReference(BMI(MBB, MBBI, X86::MOVrm32, 5),
1379                     FrameIdx, Offset).addReg(TmpReg2);
1380
1381   if (Ty == Type::DoubleTy) {   // Swap the other 32 bits of a double value...
1382     TmpReg1 = makeAnotherReg(Type::UIntTy);
1383     TmpReg2 = makeAnotherReg(Type::UIntTy);
1384
1385     addRegOffset(BMI(MBB, MBBI, X86::MOVmr32, 4, TmpReg1), SrcAddrReg, 4);
1386     BMI(MBB, MBBI, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1387     unsigned Offset = (Ty == Type::DoubleTy) << 2;
1388     addFrameReference(BMI(MBB, MBBI, X86::MOVrm32,5), FrameIdx).addReg(TmpReg2);
1389   }
1390
1391   // Now we can reload the final byteswapped result into the final destination.
1392   addFrameReference(BMI(MBB, MBBI, LoadOpcode, 4, DestReg), FrameIdx);
1393   return Result;
1394 }
1395
1396 /// EmitByteSwap - Byteswap SrcReg into DestReg.
1397 ///
1398 void ISel::EmitByteSwap(unsigned DestReg, unsigned SrcReg, unsigned Class) {
1399   // Emit the byte swap instruction...
1400   switch (Class) {
1401   case cByte:
1402     // No byteswap necessary for 8 bit value...
1403     BuildMI(BB, X86::MOVrr8, 1, DestReg).addReg(SrcReg);
1404     break;
1405   case cInt:
1406     // Use the 32 bit bswap instruction to do a 32 bit swap...
1407     BuildMI(BB, X86::BSWAPr32, 1, DestReg).addReg(SrcReg);
1408     break;
1409
1410   case cShort:
1411     // For 16 bit we have to use an xchg instruction, because there is no
1412     // 16-bit bswap.  XCHG is necessarily not in SSA form, so we force things
1413     // into AX to do the xchg.
1414     //
1415     BuildMI(BB, X86::MOVrr16, 1, X86::AX).addReg(SrcReg);
1416     BuildMI(BB, X86::XCHGrr8, 2).addReg(X86::AL, MOTy::UseAndDef)
1417       .addReg(X86::AH, MOTy::UseAndDef);
1418     BuildMI(BB, X86::MOVrr16, 1, DestReg).addReg(X86::AX);
1419     break;
1420   default: assert(0 && "Cannot byteswap this class!");
1421   }
1422 }
1423
1424
1425 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
1426 /// instruction.  The load and store instructions are the only place where we
1427 /// need to worry about the memory layout of the target machine.
1428 ///
1429 void ISel::visitLoadInst(LoadInst &I) {
1430   bool isLittleEndian  = TM.getTargetData().isLittleEndian();
1431   bool hasLongPointers = TM.getTargetData().getPointerSize() == 8;
1432   unsigned SrcAddrReg = getReg(I.getOperand(0));
1433   unsigned DestReg = getReg(I);
1434
1435   unsigned Class = getClassB(I.getType());
1436   switch (Class) {
1437   case cFP: {
1438     MachineBasicBlock::iterator MBBI = BB->end();
1439     addDirectMem(doFPLoad(BB, MBBI, I.getType(), DestReg), SrcAddrReg);
1440     return;
1441   }
1442   case cLong: case cInt: case cShort: case cByte:
1443     break;      // Integers of various sizes handled below
1444   default: assert(0 && "Unknown memory class!");
1445   }
1446
1447   // We need to adjust the input pointer if we are emulating a big-endian
1448   // long-pointer target.  On these systems, the pointer that we are interested
1449   // in is in the upper part of the eight byte memory image of the pointer.  It
1450   // also happens to be byte-swapped, but this will be handled later.
1451   //
1452   if (!isLittleEndian && hasLongPointers && isa<PointerType>(I.getType())) {
1453     unsigned R = makeAnotherReg(Type::UIntTy);
1454     BuildMI(BB, X86::ADDri32, 2, R).addReg(SrcAddrReg).addZImm(4);
1455     SrcAddrReg = R;
1456   }
1457
1458   unsigned IReg = DestReg;
1459   if (!isLittleEndian)  // If big endian we need an intermediate stage
1460     DestReg = makeAnotherReg(Class != cLong ? I.getType() : Type::UIntTy);
1461
1462   static const unsigned Opcode[] = {
1463     X86::MOVmr8, X86::MOVmr16, X86::MOVmr32, 0, X86::MOVmr32
1464   };
1465   addDirectMem(BuildMI(BB, Opcode[Class], 4, DestReg), SrcAddrReg);
1466
1467   // Handle long values now...
1468   if (Class == cLong) {
1469     if (isLittleEndian) {
1470       addRegOffset(BuildMI(BB, X86::MOVmr32, 4, DestReg+1), SrcAddrReg, 4);
1471     } else {
1472       EmitByteSwap(IReg+1, DestReg, cInt);
1473       unsigned TempReg = makeAnotherReg(Type::IntTy);
1474       addRegOffset(BuildMI(BB, X86::MOVmr32, 4, TempReg), SrcAddrReg, 4);
1475       EmitByteSwap(IReg, TempReg, cInt);
1476     }
1477     return;
1478   }
1479
1480   if (!isLittleEndian)
1481     EmitByteSwap(IReg, DestReg, Class);
1482 }
1483
1484
1485 /// doFPStore - This method is used to store an FP value to memory using the
1486 /// current endianness.
1487 ///
1488 void ISel::doFPStore(const Type *Ty, unsigned DestAddrReg, unsigned SrcReg) {
1489   assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
1490   unsigned StoreOpcode = Ty == Type::FloatTy ? X86::FSTr32 : X86::FSTr64;
1491
1492   if (TM.getTargetData().isLittleEndian()) {  // fast path...
1493     addDirectMem(BuildMI(BB, StoreOpcode,5), DestAddrReg).addReg(SrcReg);
1494     return;
1495   }
1496
1497   // Allocate a temporary stack slot to transform the value into...
1498   int FrameIdx = F->getFrameInfo()->CreateStackObject(Ty, TM.getTargetData());
1499   unsigned SrcAddrReg = makeAnotherReg(Type::UIntTy);
1500   addFrameReference(BuildMI(BB, X86::LEAr32, 5, SrcAddrReg), FrameIdx);
1501
1502   // Store the value into a temporary stack slot...
1503   addDirectMem(BuildMI(BB, StoreOpcode, 5), SrcAddrReg).addReg(SrcReg);
1504
1505   // Perform the bswaps 32 bits at a time...
1506   unsigned TmpReg1 = makeAnotherReg(Type::UIntTy);
1507   unsigned TmpReg2 = makeAnotherReg(Type::UIntTy);
1508   addDirectMem(BuildMI(BB, X86::MOVmr32, 4, TmpReg1), SrcAddrReg);
1509   BuildMI(BB, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1510   unsigned Offset = (Ty == Type::DoubleTy) << 2;
1511   addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
1512                DestAddrReg, Offset).addReg(TmpReg2);
1513
1514   if (Ty == Type::DoubleTy) {   // Swap the other 32 bits of a double value...
1515     TmpReg1 = makeAnotherReg(Type::UIntTy);
1516     TmpReg2 = makeAnotherReg(Type::UIntTy);
1517
1518     addRegOffset(BuildMI(BB, X86::MOVmr32, 4, TmpReg1), SrcAddrReg, 4);
1519     BuildMI(BB, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1520     unsigned Offset = (Ty == Type::DoubleTy) << 2;
1521     addDirectMem(BuildMI(BB, X86::MOVrm32, 5), DestAddrReg).addReg(TmpReg2);
1522   }
1523 }
1524
1525
1526 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
1527 /// instruction.
1528 ///
1529 void ISel::visitStoreInst(StoreInst &I) {
1530   bool isLittleEndian  = TM.getTargetData().isLittleEndian();
1531   bool hasLongPointers = TM.getTargetData().getPointerSize() == 8;
1532   unsigned ValReg      = getReg(I.getOperand(0));
1533   unsigned AddressReg  = getReg(I.getOperand(1));
1534
1535   unsigned Class = getClassB(I.getOperand(0)->getType());
1536   switch (Class) {
1537   case cLong:
1538     if (isLittleEndian) {
1539       addDirectMem(BuildMI(BB, X86::MOVrm32, 1+4), AddressReg).addReg(ValReg);
1540       addRegOffset(BuildMI(BB, X86::MOVrm32, 1+4),
1541                    AddressReg, 4).addReg(ValReg+1);
1542     } else {
1543       unsigned T1 = makeAnotherReg(Type::IntTy);
1544       unsigned T2 = makeAnotherReg(Type::IntTy);
1545       EmitByteSwap(T1, ValReg  , cInt);
1546       EmitByteSwap(T2, ValReg+1, cInt);
1547       addDirectMem(BuildMI(BB, X86::MOVrm32, 1+4), AddressReg).addReg(T2);
1548       addRegOffset(BuildMI(BB, X86::MOVrm32, 1+4), AddressReg, 4).addReg(T1);
1549     }
1550     return;
1551   case cFP:
1552     doFPStore(I.getOperand(0)->getType(), AddressReg, ValReg);
1553     return;
1554   case cInt: case cShort: case cByte:
1555     break;      // Integers of various sizes handled below
1556   default: assert(0 && "Unknown memory class!");
1557   }
1558
1559   if (!isLittleEndian && hasLongPointers &&
1560       isa<PointerType>(I.getOperand(0)->getType())) {
1561     unsigned R = makeAnotherReg(Type::UIntTy);
1562     BuildMI(BB, X86::ADDri32, 2, R).addReg(AddressReg).addZImm(4);
1563     AddressReg = R;
1564   }
1565
1566   if (!isLittleEndian && Class != cByte) {
1567     unsigned R = makeAnotherReg(I.getOperand(0)->getType());
1568     EmitByteSwap(R, ValReg, Class);
1569     ValReg = R;
1570   }
1571
1572   static const unsigned Opcode[] = { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32 };
1573   addDirectMem(BuildMI(BB, Opcode[Class], 1+4), AddressReg).addReg(ValReg);
1574 }
1575
1576
1577 /// visitCastInst - Here we have various kinds of copying with or without
1578 /// sign extension going on.
1579 void ISel::visitCastInst(CastInst &CI) {
1580   Value *Op = CI.getOperand(0);
1581   // If this is a cast from a 32-bit integer to a Long type, and the only uses
1582   // of the case are GEP instructions, then the cast does not need to be
1583   // generated explicitly, it will be folded into the GEP.
1584   if (CI.getType() == Type::LongTy &&
1585       (Op->getType() == Type::IntTy || Op->getType() == Type::UIntTy)) {
1586     bool AllUsesAreGEPs = true;
1587     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
1588       if (!isa<GetElementPtrInst>(*I)) {
1589         AllUsesAreGEPs = false;
1590         break;
1591       }
1592
1593     // No need to codegen this cast if all users are getelementptr instrs...
1594     if (AllUsesAreGEPs) return;
1595   }
1596
1597   unsigned DestReg = getReg(CI);
1598   MachineBasicBlock::iterator MI = BB->end();
1599   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
1600 }
1601
1602 /// emitCastOperation - Common code shared between visitCastInst and
1603 /// constant expression cast support.
1604 void ISel::emitCastOperation(MachineBasicBlock *BB,
1605                              MachineBasicBlock::iterator &IP,
1606                              Value *Src, const Type *DestTy,
1607                              unsigned DestReg) {
1608   unsigned SrcReg = getReg(Src, BB, IP);
1609   const Type *SrcTy = Src->getType();
1610   unsigned SrcClass = getClassB(SrcTy);
1611   unsigned DestClass = getClassB(DestTy);
1612
1613   // Implement casts to bool by using compare on the operand followed by set if
1614   // not zero on the result.
1615   if (DestTy == Type::BoolTy) {
1616     switch (SrcClass) {
1617     case cByte:
1618       BMI(BB, IP, X86::TESTrr8, 2).addReg(SrcReg).addReg(SrcReg);
1619       break;
1620     case cShort:
1621       BMI(BB, IP, X86::TESTrr16, 2).addReg(SrcReg).addReg(SrcReg);
1622       break;
1623     case cInt:
1624       BMI(BB, IP, X86::TESTrr32, 2).addReg(SrcReg).addReg(SrcReg);
1625       break;
1626     case cLong: {
1627       unsigned TmpReg = makeAnotherReg(Type::IntTy);
1628       BMI(BB, IP, X86::ORrr32, 2, TmpReg).addReg(SrcReg).addReg(SrcReg+1);
1629       break;
1630     }
1631     case cFP:
1632       assert(0 && "FIXME: implement cast FP to bool");
1633       abort();
1634     }
1635
1636     // If the zero flag is not set, then the value is true, set the byte to
1637     // true.
1638     BMI(BB, IP, X86::SETNEr, 1, DestReg);
1639     return;
1640   }
1641
1642   static const unsigned RegRegMove[] = {
1643     X86::MOVrr8, X86::MOVrr16, X86::MOVrr32, X86::FpMOV, X86::MOVrr32
1644   };
1645
1646   // Implement casts between values of the same type class (as determined by
1647   // getClass) by using a register-to-register move.
1648   if (SrcClass == DestClass) {
1649     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
1650       BMI(BB, IP, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
1651     } else if (SrcClass == cFP) {
1652       if (SrcTy == Type::FloatTy) {  // double -> float
1653         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
1654         BMI(BB, IP, X86::FpMOV, 1, DestReg).addReg(SrcReg);
1655       } else {                       // float -> double
1656         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
1657                "Unknown cFP member!");
1658         // Truncate from double to float by storing to memory as short, then
1659         // reading it back.
1660         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
1661         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
1662         addFrameReference(BMI(BB, IP, X86::FSTr32, 5), FrameIdx).addReg(SrcReg);
1663         addFrameReference(BMI(BB, IP, X86::FLDr32, 5, DestReg), FrameIdx);
1664       }
1665     } else if (SrcClass == cLong) {
1666       BMI(BB, IP, X86::MOVrr32, 1, DestReg).addReg(SrcReg);
1667       BMI(BB, IP, X86::MOVrr32, 1, DestReg+1).addReg(SrcReg+1);
1668     } else {
1669       assert(0 && "Cannot handle this type of cast instruction!");
1670       abort();
1671     }
1672     return;
1673   }
1674
1675   // Handle cast of SMALLER int to LARGER int using a move with sign extension
1676   // or zero extension, depending on whether the source type was signed.
1677   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
1678       SrcClass < DestClass) {
1679     bool isLong = DestClass == cLong;
1680     if (isLong) DestClass = cInt;
1681
1682     static const unsigned Opc[][4] = {
1683       { X86::MOVSXr16r8, X86::MOVSXr32r8, X86::MOVSXr32r16, X86::MOVrr32 }, // s
1684       { X86::MOVZXr16r8, X86::MOVZXr32r8, X86::MOVZXr32r16, X86::MOVrr32 }  // u
1685     };
1686
1687     bool isUnsigned = SrcTy->isUnsigned();
1688     BMI(BB, IP, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
1689         DestReg).addReg(SrcReg);
1690
1691     if (isLong) {  // Handle upper 32 bits as appropriate...
1692       if (isUnsigned)     // Zero out top bits...
1693         BMI(BB, IP, X86::MOVir32, 1, DestReg+1).addZImm(0);
1694       else                // Sign extend bottom half...
1695         BMI(BB, IP, X86::SARir32, 2, DestReg+1).addReg(DestReg).addZImm(31);
1696     }
1697     return;
1698   }
1699
1700   // Special case long -> int ...
1701   if (SrcClass == cLong && DestClass == cInt) {
1702     BMI(BB, IP, X86::MOVrr32, 1, DestReg).addReg(SrcReg);
1703     return;
1704   }
1705
1706   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
1707   // move out of AX or AL.
1708   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
1709       && SrcClass > DestClass) {
1710     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
1711     BMI(BB, IP, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
1712     BMI(BB, IP, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
1713     return;
1714   }
1715
1716   // Handle casts from integer to floating point now...
1717   if (DestClass == cFP) {
1718     // Promote the integer to a type supported by FLD.  We do this because there
1719     // are no unsigned FLD instructions, so we must promote an unsigned value to
1720     // a larger signed value, then use FLD on the larger value.
1721     //
1722     const Type *PromoteType = 0;
1723     unsigned PromoteOpcode;
1724     switch (SrcTy->getPrimitiveID()) {
1725     case Type::BoolTyID:
1726     case Type::SByteTyID:
1727       // We don't have the facilities for directly loading byte sized data from
1728       // memory (even signed).  Promote it to 16 bits.
1729       PromoteType = Type::ShortTy;
1730       PromoteOpcode = X86::MOVSXr16r8;
1731       break;
1732     case Type::UByteTyID:
1733       PromoteType = Type::ShortTy;
1734       PromoteOpcode = X86::MOVZXr16r8;
1735       break;
1736     case Type::UShortTyID:
1737       PromoteType = Type::IntTy;
1738       PromoteOpcode = X86::MOVZXr32r16;
1739       break;
1740     case Type::UIntTyID: {
1741       // Make a 64 bit temporary... and zero out the top of it...
1742       unsigned TmpReg = makeAnotherReg(Type::LongTy);
1743       BMI(BB, IP, X86::MOVrr32, 1, TmpReg).addReg(SrcReg);
1744       BMI(BB, IP, X86::MOVir32, 1, TmpReg+1).addZImm(0);
1745       SrcTy = Type::LongTy;
1746       SrcClass = cLong;
1747       SrcReg = TmpReg;
1748       break;
1749     }
1750     case Type::ULongTyID:
1751       assert("FIXME: not implemented: cast ulong X to fp type!");
1752     default:  // No promotion needed...
1753       break;
1754     }
1755
1756     if (PromoteType) {
1757       unsigned TmpReg = makeAnotherReg(PromoteType);
1758       BMI(BB, IP, SrcTy->isSigned() ? X86::MOVSXr16r8 : X86::MOVZXr16r8,
1759           1, TmpReg).addReg(SrcReg);
1760       SrcTy = PromoteType;
1761       SrcClass = getClass(PromoteType);
1762       SrcReg = TmpReg;
1763     }
1764
1765     // Spill the integer to memory and reload it from there...
1766     int FrameIdx =
1767       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
1768
1769     if (SrcClass == cLong) {
1770       addFrameReference(BMI(BB, IP, X86::MOVrm32, 5), FrameIdx).addReg(SrcReg);
1771       addFrameReference(BMI(BB, IP, X86::MOVrm32, 5),
1772                         FrameIdx, 4).addReg(SrcReg+1);
1773     } else {
1774       static const unsigned Op1[] = { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32 };
1775       addFrameReference(BMI(BB, IP, Op1[SrcClass], 5), FrameIdx).addReg(SrcReg);
1776     }
1777
1778     static const unsigned Op2[] =
1779       { 0/*byte*/, X86::FILDr16, X86::FILDr32, 0/*FP*/, X86::FILDr64 };
1780     addFrameReference(BMI(BB, IP, Op2[SrcClass], 5, DestReg), FrameIdx);
1781     return;
1782   }
1783
1784   // Handle casts from floating point to integer now...
1785   if (SrcClass == cFP) {
1786     // Change the floating point control register to use "round towards zero"
1787     // mode when truncating to an integer value.
1788     //
1789     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
1790     addFrameReference(BMI(BB, IP, X86::FNSTCWm16, 4), CWFrameIdx);
1791
1792     // Load the old value of the high byte of the control word...
1793     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
1794     addFrameReference(BMI(BB, IP, X86::MOVmr8, 4, HighPartOfCW), CWFrameIdx, 1);
1795
1796     // Set the high part to be round to zero...
1797     addFrameReference(BMI(BB, IP, X86::MOVim8, 5), CWFrameIdx, 1).addZImm(12);
1798
1799     // Reload the modified control word now...
1800     addFrameReference(BMI(BB, IP, X86::FLDCWm16, 4), CWFrameIdx);
1801
1802     // Restore the memory image of control word to original value
1803     addFrameReference(BMI(BB, IP, X86::MOVrm8, 5),
1804                       CWFrameIdx, 1).addReg(HighPartOfCW);
1805
1806     // We don't have the facilities for directly storing byte sized data to
1807     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
1808     // larger classes because we only have signed FP stores.
1809     unsigned StoreClass  = DestClass;
1810     const Type *StoreTy  = DestTy;
1811     if (StoreClass == cByte || DestTy->isUnsigned())
1812       switch (StoreClass) {
1813       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
1814       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
1815       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
1816       // The following treatment of cLong may not be perfectly right,
1817       // but it survives chains of casts of the form
1818       // double->ulong->double.
1819       case cLong:  StoreTy = Type::LongTy;  StoreClass = cLong;  break;
1820       default: assert(0 && "Unknown store class!");
1821       }
1822
1823     // Spill the integer to memory and reload it from there...
1824     int FrameIdx =
1825       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
1826
1827     static const unsigned Op1[] =
1828       { 0, X86::FISTr16, X86::FISTr32, 0, X86::FISTPr64 };
1829     addFrameReference(BMI(BB, IP, Op1[StoreClass], 5), FrameIdx).addReg(SrcReg);
1830
1831     if (DestClass == cLong) {
1832       addFrameReference(BMI(BB, IP, X86::MOVmr32, 4, DestReg), FrameIdx);
1833       addFrameReference(BMI(BB, IP, X86::MOVmr32, 4, DestReg+1), FrameIdx, 4);
1834     } else {
1835       static const unsigned Op2[] = { X86::MOVmr8, X86::MOVmr16, X86::MOVmr32 };
1836       addFrameReference(BMI(BB, IP, Op2[DestClass], 4, DestReg), FrameIdx);
1837     }
1838
1839     // Reload the original control word now...
1840     addFrameReference(BMI(BB, IP, X86::FLDCWm16, 4), CWFrameIdx);
1841     return;
1842   }
1843
1844   // Anything we haven't handled already, we can't (yet) handle at all.
1845   assert(0 && "Unhandled cast instruction!");
1846   abort();
1847 }
1848
1849 /// visitVarArgInst - Implement the va_arg instruction...
1850 ///
1851 void ISel::visitVarArgInst(VarArgInst &I) {
1852   unsigned SrcReg = getReg(I.getOperand(0));
1853   unsigned DestReg = getReg(I);
1854
1855   // Load the va_list into a register...
1856   unsigned VAList = makeAnotherReg(Type::UIntTy);
1857   addDirectMem(BuildMI(BB, X86::MOVmr32, 4, VAList), SrcReg);
1858
1859   unsigned Size;
1860   switch (I.getType()->getPrimitiveID()) {
1861   default:
1862     std::cerr << I;
1863     assert(0 && "Error: bad type for va_arg instruction!");
1864     return;
1865   case Type::PointerTyID:
1866   case Type::UIntTyID:
1867   case Type::IntTyID:
1868     Size = 4;
1869     addDirectMem(BuildMI(BB, X86::MOVmr32, 4, DestReg), VAList);
1870     break;
1871   case Type::ULongTyID:
1872   case Type::LongTyID:
1873     Size = 8;
1874     addDirectMem(BuildMI(BB, X86::MOVmr32, 4, DestReg), VAList);
1875     addRegOffset(BuildMI(BB, X86::MOVmr32, 4, DestReg+1), VAList, 4);
1876     break;
1877   case Type::DoubleTyID:
1878     Size = 8;
1879     addDirectMem(BuildMI(BB, X86::FLDr64, 4, DestReg), VAList);
1880     break;
1881   }
1882
1883   // Increment the VAList pointer...
1884   unsigned NextVAList = makeAnotherReg(Type::UIntTy);
1885   BuildMI(BB, X86::ADDri32, 2, NextVAList).addReg(VAList).addZImm(Size);
1886
1887   // Update the VAList in memory...
1888   addDirectMem(BuildMI(BB, X86::MOVrm32, 5), SrcReg).addReg(NextVAList);
1889 }
1890
1891
1892 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1893 // returns zero when the input is not exactly a power of two.
1894 static unsigned ExactLog2(unsigned Val) {
1895   if (Val == 0) return 0;
1896   unsigned Count = 0;
1897   while (Val != 1) {
1898     if (Val & 1) return 0;
1899     Val >>= 1;
1900     ++Count;
1901   }
1902   return Count+1;
1903 }
1904
1905 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
1906   unsigned outputReg = getReg(I);
1907   MachineBasicBlock::iterator MI = BB->end();
1908   emitGEPOperation(BB, MI, I.getOperand(0),
1909                    I.op_begin()+1, I.op_end(), outputReg);
1910 }
1911
1912 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
1913                             MachineBasicBlock::iterator &IP,
1914                             Value *Src, User::op_iterator IdxBegin,
1915                             User::op_iterator IdxEnd, unsigned TargetReg) {
1916   const TargetData &TD = TM.getTargetData();
1917   const Type *Ty = Src->getType();
1918   unsigned BaseReg = getReg(Src, MBB, IP);
1919
1920   // GEPs have zero or more indices; we must perform a struct access
1921   // or array access for each one.
1922   for (GetElementPtrInst::op_iterator oi = IdxBegin,
1923          oe = IdxEnd; oi != oe; ++oi) {
1924     Value *idx = *oi;
1925     unsigned NextReg = BaseReg;
1926     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1927       // It's a struct access.  idx is the index into the structure,
1928       // which names the field. This index must have ubyte type.
1929       const ConstantUInt *CUI = cast<ConstantUInt>(idx);
1930       assert(CUI->getType() == Type::UByteTy
1931               && "Funny-looking structure index in GEP");
1932       // Use the TargetData structure to pick out what the layout of
1933       // the structure is in memory.  Since the structure index must
1934       // be constant, we can get its value and use it to find the
1935       // right byte offset from the StructLayout class's list of
1936       // structure member offsets.
1937       unsigned idxValue = CUI->getValue();
1938       unsigned FieldOff = TD.getStructLayout(StTy)->MemberOffsets[idxValue];
1939       if (FieldOff) {
1940         NextReg = makeAnotherReg(Type::UIntTy);
1941         // Emit an ADD to add FieldOff to the basePtr.
1942         BMI(MBB, IP, X86::ADDri32, 2,NextReg).addReg(BaseReg).addZImm(FieldOff);
1943       }
1944       // The next type is the member of the structure selected by the
1945       // index.
1946       Ty = StTy->getElementTypes()[idxValue];
1947     } else if (const SequentialType *SqTy = cast<SequentialType>(Ty)) {
1948       // It's an array or pointer access: [ArraySize x ElementType].
1949
1950       // idx is the index into the array.  Unlike with structure
1951       // indices, we may not know its actual value at code-generation
1952       // time.
1953       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
1954
1955       // Most GEP instructions use a [cast (int/uint) to LongTy] as their
1956       // operand on X86.  Handle this case directly now...
1957       if (CastInst *CI = dyn_cast<CastInst>(idx))
1958         if (CI->getOperand(0)->getType() == Type::IntTy ||
1959             CI->getOperand(0)->getType() == Type::UIntTy)
1960           idx = CI->getOperand(0);
1961
1962       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
1963       // must find the size of the pointed-to type (Not coincidentally, the next
1964       // type is the type of the elements in the array).
1965       Ty = SqTy->getElementType();
1966       unsigned elementSize = TD.getTypeSize(Ty);
1967
1968       // If idxReg is a constant, we don't need to perform the multiply!
1969       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
1970         if (!CSI->isNullValue()) {
1971           unsigned Offset = elementSize*CSI->getValue();
1972           NextReg = makeAnotherReg(Type::UIntTy);
1973           BMI(MBB, IP, X86::ADDri32, 2,NextReg).addReg(BaseReg).addZImm(Offset);
1974         }
1975       } else if (elementSize == 1) {
1976         // If the element size is 1, we don't have to multiply, just add
1977         unsigned idxReg = getReg(idx, MBB, IP);
1978         NextReg = makeAnotherReg(Type::UIntTy);
1979         BMI(MBB, IP, X86::ADDrr32, 2, NextReg).addReg(BaseReg).addReg(idxReg);
1980       } else {
1981         unsigned idxReg = getReg(idx, MBB, IP);
1982         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
1983         if (unsigned Shift = ExactLog2(elementSize)) {
1984           // If the element size is exactly a power of 2, use a shift to get it.
1985           BMI(MBB, IP, X86::SHLir32, 2,
1986               OffsetReg).addReg(idxReg).addZImm(Shift-1);
1987         } else {
1988           // Most general case, emit a multiply...
1989           unsigned elementSizeReg = makeAnotherReg(Type::LongTy);
1990           BMI(MBB, IP, X86::MOVir32, 1, elementSizeReg).addZImm(elementSize);
1991
1992           // Emit a MUL to multiply the register holding the index by
1993           // elementSize, putting the result in OffsetReg.
1994           doMultiply(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSizeReg);
1995         }
1996         // Emit an ADD to add OffsetReg to the basePtr.
1997         NextReg = makeAnotherReg(Type::UIntTy);
1998         BMI(MBB, IP, X86::ADDrr32, 2,NextReg).addReg(BaseReg).addReg(OffsetReg);
1999       }
2000     }
2001     // Now that we are here, further indices refer to subtypes of this
2002     // one, so we don't need to worry about BaseReg itself, anymore.
2003     BaseReg = NextReg;
2004   }
2005   // After we have processed all the indices, the result is left in
2006   // BaseReg.  Move it to the register where we were expected to
2007   // put the answer.  A 32-bit move should do it, because we are in
2008   // ILP32 land.
2009   BMI(MBB, IP, X86::MOVrr32, 1, TargetReg).addReg(BaseReg);
2010 }
2011
2012
2013 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
2014 /// frame manager, otherwise do it the hard way.
2015 ///
2016 void ISel::visitAllocaInst(AllocaInst &I) {
2017   // Find the data size of the alloca inst's getAllocatedType.
2018   const Type *Ty = I.getAllocatedType();
2019   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
2020
2021   // If this is a fixed size alloca in the entry block for the function,
2022   // statically stack allocate the space.
2023   //
2024   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getArraySize())) {
2025     if (I.getParent() == I.getParent()->getParent()->begin()) {
2026       TySize *= CUI->getValue();   // Get total allocated size...
2027       unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
2028
2029       // Create a new stack object using the frame manager...
2030       int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
2031       addFrameReference(BuildMI(BB, X86::LEAr32, 5, getReg(I)), FrameIdx);
2032       return;
2033     }
2034   }
2035
2036   // Create a register to hold the temporary result of multiplying the type size
2037   // constant by the variable amount.
2038   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
2039   unsigned SrcReg1 = getReg(I.getArraySize());
2040   unsigned SizeReg = makeAnotherReg(Type::UIntTy);
2041   BuildMI(BB, X86::MOVir32, 1, SizeReg).addZImm(TySize);
2042
2043   // TotalSizeReg = mul <numelements>, <TypeSize>
2044   MachineBasicBlock::iterator MBBI = BB->end();
2045   doMultiply(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, SizeReg);
2046
2047   // AddedSize = add <TotalSizeReg>, 15
2048   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
2049   BuildMI(BB, X86::ADDri32, 2, AddedSizeReg).addReg(TotalSizeReg).addZImm(15);
2050
2051   // AlignedSize = and <AddedSize>, ~15
2052   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
2053   BuildMI(BB, X86::ANDri32, 2, AlignedSize).addReg(AddedSizeReg).addZImm(~15);
2054
2055   // Subtract size from stack pointer, thereby allocating some space.
2056   BuildMI(BB, X86::SUBrr32, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
2057
2058   // Put a pointer to the space into the result register, by copying
2059   // the stack pointer.
2060   BuildMI(BB, X86::MOVrr32, 1, getReg(I)).addReg(X86::ESP);
2061
2062   // Inform the Frame Information that we have just allocated a variable-sized
2063   // object.
2064   F->getFrameInfo()->CreateVariableSizedObject();
2065 }
2066
2067 /// visitMallocInst - Malloc instructions are code generated into direct calls
2068 /// to the library malloc.
2069 ///
2070 void ISel::visitMallocInst(MallocInst &I) {
2071   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
2072   unsigned Arg;
2073
2074   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
2075     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
2076   } else {
2077     Arg = makeAnotherReg(Type::UIntTy);
2078     unsigned Op0Reg = getReg(ConstantUInt::get(Type::UIntTy, AllocSize));
2079     unsigned Op1Reg = getReg(I.getOperand(0));
2080     MachineBasicBlock::iterator MBBI = BB->end();
2081     doMultiply(BB, MBBI, Arg, Type::UIntTy, Op0Reg, Op1Reg);
2082   }
2083
2084   std::vector<ValueRecord> Args;
2085   Args.push_back(ValueRecord(Arg, Type::UIntTy));
2086   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2087                                   1).addExternalSymbol("malloc", true);
2088   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
2089 }
2090
2091
2092 /// visitFreeInst - Free instructions are code gen'd to call the free libc
2093 /// function.
2094 ///
2095 void ISel::visitFreeInst(FreeInst &I) {
2096   std::vector<ValueRecord> Args;
2097   Args.push_back(ValueRecord(I.getOperand(0)));
2098   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2099                                   1).addExternalSymbol("free", true);
2100   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
2101 }
2102
2103
2104 /// createX86SimpleInstructionSelector - This pass converts an LLVM function
2105 /// into a machine code representation is a very simple peep-hole fashion.  The
2106 /// generated code sucks but the implementation is nice and simple.
2107 ///
2108 FunctionPass *createX86SimpleInstructionSelector(TargetMachine &TM) {
2109   return new ISel(TM);
2110 }