lib/Target/X86/X86ISelSimple.cpp

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