lib/Target/X86/InstSelectSimple.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/IntrinsicLowering.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/SSARegMap.h"
  27 #include "llvm/Target/MRegisterInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/Support/GetElementPtrTypeIterator.h"
  30 #include "llvm/Support/InstVisitor.h"
  31 #include "llvm/Support/CFG.h"
  32 #include "Support/Statistic.h"
  33 using namespace llvm;
  34
  35 namespace {
  36   Statistic<>
  37   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
  38 }
  39
  40 namespace {
  41   struct ISel : public FunctionPass, InstVisitor<ISel> {
  42     TargetMachine &TM;
  43     MachineFunction *F;                 // The function we are compiling into
  44     MachineBasicBlock *BB;              // The current MBB we are compiling
  45     int VarArgsFrameIndex;              // FrameIndex for start of varargs area
  46     int ReturnAddressIndex;             // FrameIndex for the return address
  47
  48     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  49
  50     // MBBMap - Mapping between LLVM BB -> Machine BB
  51     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  52
  53     ISel(TargetMachine &tm) : TM(tm), F(0), BB(0) {}
  54
  55     /// runOnFunction - Top level implementation of instruction selection for
  56     /// the entire function.
  57     ///
  58     bool runOnFunction(Function &Fn) {
  59       // First pass over the function, lower any unknown intrinsic functions
  60       // with the IntrinsicLowering class.
  61       LowerUnknownIntrinsicFunctionCalls(Fn);
  62
  63       F = &MachineFunction::construct(&Fn, TM);
  64
  65       // Create all of the machine basic blocks for the function...
  66       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  67         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
  68
  69       BB = &F->front();
  70
  71       // Set up a frame object for the return address.  This is used by the
  72       // llvm.returnaddress & llvm.frameaddress intrinisics.
  73       ReturnAddressIndex = F->getFrameInfo()->CreateFixedObject(4, -4);
  74
  75       // Copy incoming arguments off of the stack...
  76       LoadArgumentsToVirtualRegs(Fn);
  77
  78       // Instruction select everything except PHI nodes
  79       visit(Fn);
  80
  81       // Select the PHI nodes
  82       SelectPHINodes();
  83
  84       // Insert the FP_REG_KILL instructions into blocks that need them.
  85       InsertFPRegKills();
  86
  87       RegMap.clear();
  88       MBBMap.clear();
  89       F = 0;
  90       // We always build a machine code representation for the function
  91       return true;
  92     }
  93
  94     virtual const char *getPassName() const {
  95       return "X86 Simple Instruction Selection";
  96     }
  97
  98     /// visitBasicBlock - This method is called when we are visiting a new basic
  99     /// block.  This simply creates a new MachineBasicBlock to emit code into
 100     /// and adds it to the current MachineFunction.  Subsequent visit* for
 101     /// instructions will be invoked for all instructions in the basic block.
 102     ///
 103     void visitBasicBlock(BasicBlock &LLVM_BB) {
 104       BB = MBBMap[&LLVM_BB];
 105     }
 106
 107     /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
 108     /// function, lowering any calls to unknown intrinsic functions into the
 109     /// equivalent LLVM code.
 110     ///
 111     void LowerUnknownIntrinsicFunctionCalls(Function &F);
 112
 113     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 114     /// from the stack into virtual registers.
 115     ///
 116     void LoadArgumentsToVirtualRegs(Function &F);
 117
 118     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 119     /// because we have to generate our sources into the source basic blocks,
 120     /// not the current one.
 121     ///
 122     void SelectPHINodes();
 123
 124     /// InsertFPRegKills - Insert FP_REG_KILL instructions into basic blocks
 125     /// that need them.  This only occurs due to the floating point stackifier
 126     /// not being aggressive enough to handle arbitrary global stackification.
 127     ///
 128     void InsertFPRegKills();
 129
 130     // Visitation methods for various instructions.  These methods simply emit
 131     // fixed X86 code for each instruction.
 132     //
 133
 134     // Control flow operators
 135     void visitReturnInst(ReturnInst &RI);
 136     void visitBranchInst(BranchInst &BI);
 137
 138     struct ValueRecord {
 139       Value *Val;
 140       unsigned Reg;
 141       const Type *Ty;
 142       ValueRecord(unsigned R, const Type *T) : Val(0), Reg(R), Ty(T) {}
 143       ValueRecord(Value *V) : Val(V), Reg(0), Ty(V->getType()) {}
 144     };
 145     void doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 146                 const std::vector<ValueRecord> &Args);
 147     void visitCallInst(CallInst &I);
 148     void visitIntrinsicCall(Intrinsic::ID ID, CallInst &I);
 149
 150     // Arithmetic operators
 151     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 152     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 153     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 154     void doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
 155                     unsigned DestReg, const Type *DestTy,
 156                     unsigned Op0Reg, unsigned Op1Reg);
 157     void doMultiplyConst(MachineBasicBlock *MBB,
 158                          MachineBasicBlock::iterator MBBI,
 159                          unsigned DestReg, const Type *DestTy,
 160                          unsigned Op0Reg, unsigned Op1Val);
 161     void visitMul(BinaryOperator &B);
 162
 163     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 164     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 165     void visitDivRem(BinaryOperator &B);
 166
 167     // Bitwise operators
 168     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 169     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 170     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 171
 172     // Comparison operators...
 173     void visitSetCondInst(SetCondInst &I);
 174     unsigned EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 175                             MachineBasicBlock *MBB,
 176                             MachineBasicBlock::iterator MBBI);
 177
 178     // Memory Instructions
 179     void visitLoadInst(LoadInst &I);
 180     void visitStoreInst(StoreInst &I);
 181     void visitGetElementPtrInst(GetElementPtrInst &I);
 182     void visitAllocaInst(AllocaInst &I);
 183     void visitMallocInst(MallocInst &I);
 184     void visitFreeInst(FreeInst &I);
 185
 186     // Other operators
 187     void visitShiftInst(ShiftInst &I);
 188     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 189     void visitCastInst(CastInst &I);
 190     void visitVANextInst(VANextInst &I);
 191     void visitVAArgInst(VAArgInst &I);
 192
 193     void visitInstruction(Instruction &I) {
 194       std::cerr << "Cannot instruction select: " << I;
 195       abort();
 196     }
 197
 198     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 199     ///
 200     void promote32(unsigned targetReg, const ValueRecord &VR);
 201
 202     /// getAddressingMode - Get the addressing mode to use to address the
 203     /// specified value.  The returned value should be used with addFullAddress.
 204     void getAddressingMode(Value *Addr, unsigned &BaseReg, unsigned &Scale,
 205                            unsigned &IndexReg, unsigned &Disp);
 206
 207
 208     /// getGEPIndex - This is used to fold GEP instructions into X86 addressing
 209     /// expressions.
 210     void getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
 211                      std::vector<Value*> &GEPOps,
 212                      std::vector<const Type*> &GEPTypes, unsigned &BaseReg,
 213                      unsigned &Scale, unsigned &IndexReg, unsigned &Disp);
 214
 215     /// isGEPFoldable - Return true if the specified GEP can be completely
 216     /// folded into the addressing mode of a load/store or lea instruction.
 217     bool isGEPFoldable(MachineBasicBlock *MBB,
 218                        Value *Src, User::op_iterator IdxBegin,
 219                        User::op_iterator IdxEnd, unsigned &BaseReg,
 220                        unsigned &Scale, unsigned &IndexReg, unsigned &Disp);
 221
 222     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 223     /// constant expression GEP support.
 224     ///
 225     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
 226                           Value *Src, User::op_iterator IdxBegin,
 227                           User::op_iterator IdxEnd, unsigned TargetReg);
 228
 229     /// emitCastOperation - Common code shared between visitCastInst and
 230     /// constant expression cast support.
 231     ///
 232     void emitCastOperation(MachineBasicBlock *BB,MachineBasicBlock::iterator IP,
 233                            Value *Src, const Type *DestTy, unsigned TargetReg);
 234
 235     /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
 236     /// and constant expression support.
 237     ///
 238     void emitSimpleBinaryOperation(MachineBasicBlock *BB,
 239                                    MachineBasicBlock::iterator IP,
 240                                    Value *Op0, Value *Op1,
 241                                    unsigned OperatorClass, unsigned TargetReg);
 242
 243     void emitDivRemOperation(MachineBasicBlock *BB,
 244                              MachineBasicBlock::iterator IP,
 245                              unsigned Op0Reg, unsigned Op1Reg, bool isDiv,
 246                              const Type *Ty, unsigned TargetReg);
 247
 248     /// emitSetCCOperation - Common code shared between visitSetCondInst and
 249     /// constant expression support.
 250     ///
 251     void emitSetCCOperation(MachineBasicBlock *BB,
 252                             MachineBasicBlock::iterator IP,
 253                             Value *Op0, Value *Op1, unsigned Opcode,
 254                             unsigned TargetReg);
 255
 256     /// emitShiftOperation - Common code shared between visitShiftInst and
 257     /// constant expression support.
 258     ///
 259     void emitShiftOperation(MachineBasicBlock *MBB,
 260                             MachineBasicBlock::iterator IP,
 261                             Value *Op, Value *ShiftAmount, bool isLeftShift,
 262                             const Type *ResultTy, unsigned DestReg);
 263
 264
 265     /// copyConstantToRegister - Output the instructions required to put the
 266     /// specified constant into the specified register.
 267     ///
 268     void copyConstantToRegister(MachineBasicBlock *MBB,
 269                                 MachineBasicBlock::iterator MBBI,
 270                                 Constant *C, unsigned Reg);
 271
 272     /// makeAnotherReg - This method returns the next register number we haven't
 273     /// yet used.
 274     ///
 275     /// Long values are handled somewhat specially.  They are always allocated
 276     /// as pairs of 32 bit integer values.  The register number returned is the
 277     /// lower 32 bits of the long value, and the regNum+1 is the upper 32 bits
 278     /// of the long value.
 279     ///
 280     unsigned makeAnotherReg(const Type *Ty) {
 281       assert(dynamic_cast<const X86RegisterInfo*>(TM.getRegisterInfo()) &&
 282              "Current target doesn't have X86 reg info??");
 283       const X86RegisterInfo *MRI =
 284         static_cast<const X86RegisterInfo*>(TM.getRegisterInfo());
 285       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 286         const TargetRegisterClass *RC = MRI->getRegClassForType(Type::IntTy);
 287         // Create the lower part
 288         F->getSSARegMap()->createVirtualRegister(RC);
 289         // Create the upper part.
 290         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 291       }
 292
 293       // Add the mapping of regnumber => reg class to MachineFunction
 294       const TargetRegisterClass *RC = MRI->getRegClassForType(Ty);
 295       return F->getSSARegMap()->createVirtualRegister(RC);
 296     }
 297
 298     /// getReg - This method turns an LLVM value into a register number.  This
 299     /// is guaranteed to produce the same register number for a particular value
 300     /// every time it is queried.
 301     ///
 302     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 303     unsigned getReg(Value *V) {
 304       // Just append to the end of the current bb.
 305       MachineBasicBlock::iterator It = BB->end();
 306       return getReg(V, BB, It);
 307     }
 308     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 309                     MachineBasicBlock::iterator IPt) {
 310       unsigned &Reg = RegMap[V];
 311       if (Reg == 0) {
 312         Reg = makeAnotherReg(V->getType());
 313         RegMap[V] = Reg;
 314       }
 315
 316       // If this operand is a constant, emit the code to copy the constant into
 317       // the register here...
 318       //
 319       if (Constant *C = dyn_cast<Constant>(V)) {
 320         copyConstantToRegister(MBB, IPt, C, Reg);
 321         RegMap.erase(V);  // Assign a new name to this constant if ref'd again
 322       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 323         // Move the address of the global into the register
 324         BuildMI(*MBB, IPt, X86::MOV32ri, 1, Reg).addGlobalAddress(GV);
 325         RegMap.erase(V);  // Assign a new name to this address if ref'd again
 326       }
 327
 328       return Reg;
 329     }
 330   };
 331 }
 332
 333 /// TypeClass - Used by the X86 backend to group LLVM types by their basic X86
 334 /// Representation.
 335 ///
 336 enum TypeClass {
 337   cByte, cShort, cInt, cFP, cLong
 338 };
 339
 340 /// getClass - Turn a primitive type into a "class" number which is based on the
 341 /// size of the type, and whether or not it is floating point.
 342 ///
 343 static inline TypeClass getClass(const Type *Ty) {
 344   switch (Ty->getPrimitiveID()) {
 345   case Type::SByteTyID:
 346   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
 347   case Type::ShortTyID:
 348   case Type::UShortTyID:  return cShort;     // Short operands are class #1
 349   case Type::IntTyID:
 350   case Type::UIntTyID:
 351   case Type::PointerTyID: return cInt;       // Int's and pointers are class #2
 352
 353   case Type::FloatTyID:
 354   case Type::DoubleTyID:  return cFP;        // Floating Point is #3
 355
 356   case Type::LongTyID:
 357   case Type::ULongTyID:   return cLong;      // Longs are class #4
 358   default:
 359     assert(0 && "Invalid type to getClass!");
 360     return cByte;  // not reached
 361   }
 362 }
 363
 364 // getClassB - Just like getClass, but treat boolean values as bytes.
 365 static inline TypeClass getClassB(const Type *Ty) {
 366   if (Ty == Type::BoolTy) return cByte;
 367   return getClass(Ty);
 368 }
 369
 370
 371 /// copyConstantToRegister - Output the instructions required to put the
 372 /// specified constant into the specified register.
 373 ///
 374 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 375                                   MachineBasicBlock::iterator IP,
 376                                   Constant *C, unsigned R) {
 377   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 378     unsigned Class = 0;
 379     switch (CE->getOpcode()) {
 380     case Instruction::GetElementPtr:
 381       emitGEPOperation(MBB, IP, CE->getOperand(0),
 382                        CE->op_begin()+1, CE->op_end(), R);
 383       return;
 384     case Instruction::Cast:
 385       emitCastOperation(MBB, IP, CE->getOperand(0), CE->getType(), R);
 386       return;
 387
 388     case Instruction::Xor: ++Class; // FALL THROUGH
 389     case Instruction::Or:  ++Class; // FALL THROUGH
 390     case Instruction::And: ++Class; // FALL THROUGH
 391     case Instruction::Sub: ++Class; // FALL THROUGH
 392     case Instruction::Add:
 393       emitSimpleBinaryOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 394                                 Class, R);
 395       return;
 396
 397     case Instruction::Mul: {
 398       unsigned Op0Reg = getReg(CE->getOperand(0), MBB, IP);
 399       unsigned Op1Reg = getReg(CE->getOperand(1), MBB, IP);
 400       doMultiply(MBB, IP, R, CE->getType(), Op0Reg, Op1Reg);
 401       return;
 402     }
 403     case Instruction::Div:
 404     case Instruction::Rem: {
 405       unsigned Op0Reg = getReg(CE->getOperand(0), MBB, IP);
 406       unsigned Op1Reg = getReg(CE->getOperand(1), MBB, IP);
 407       emitDivRemOperation(MBB, IP, Op0Reg, Op1Reg,
 408                           CE->getOpcode() == Instruction::Div,
 409                           CE->getType(), R);
 410       return;
 411     }
 412
 413     case Instruction::SetNE:
 414     case Instruction::SetEQ:
 415     case Instruction::SetLT:
 416     case Instruction::SetGT:
 417     case Instruction::SetLE:
 418     case Instruction::SetGE:
 419       emitSetCCOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 420                          CE->getOpcode(), R);
 421       return;
 422
 423     case Instruction::Shl:
 424     case Instruction::Shr:
 425       emitShiftOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 426                          CE->getOpcode() == Instruction::Shl, CE->getType(), R);
 427       return;
 428
 429     default:
 430       std::cerr << "Offending expr: " << C << "\n";
 431       assert(0 && "Constant expression not yet handled!\n");
 432     }
 433   }
 434
 435   if (C->getType()->isIntegral()) {
 436     unsigned Class = getClassB(C->getType());
 437
 438     if (Class == cLong) {
 439       // Copy the value into the register pair.
 440       uint64_t Val = cast<ConstantInt>(C)->getRawValue();
 441       BuildMI(*MBB, IP, X86::MOV32ri, 1, R).addImm(Val & 0xFFFFFFFF);
 442       BuildMI(*MBB, IP, X86::MOV32ri, 1, R+1).addImm(Val >> 32);
 443       return;
 444     }
 445
 446     assert(Class <= cInt && "Type not handled yet!");
 447
 448     static const unsigned IntegralOpcodeTab[] = {
 449       X86::MOV8ri, X86::MOV16ri, X86::MOV32ri
 450     };
 451
 452     if (C->getType() == Type::BoolTy) {
 453       BuildMI(*MBB, IP, X86::MOV8ri, 1, R).addImm(C == ConstantBool::True);
 454     } else {
 455       ConstantInt *CI = cast<ConstantInt>(C);
 456       BuildMI(*MBB, IP, IntegralOpcodeTab[Class],1,R).addImm(CI->getRawValue());
 457     }
 458   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 459     if (CFP->isExactlyValue(+0.0))
 460       BuildMI(*MBB, IP, X86::FLD0, 0, R);
 461     else if (CFP->isExactlyValue(+1.0))
 462       BuildMI(*MBB, IP, X86::FLD1, 0, R);
 463     else {
 464       // Otherwise we need to spill the constant to memory...
 465       MachineConstantPool *CP = F->getConstantPool();
 466       unsigned CPI = CP->getConstantPoolIndex(CFP);
 467       const Type *Ty = CFP->getType();
 468
 469       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
 470       unsigned LoadOpcode = Ty == Type::FloatTy ? X86::FLD32m : X86::FLD64m;
 471       addConstantPoolReference(BuildMI(*MBB, IP, LoadOpcode, 4, R), CPI);
 472     }
 473
 474   } else if (isa<ConstantPointerNull>(C)) {
 475     // Copy zero (null pointer) to the register.
 476     BuildMI(*MBB, IP, X86::MOV32ri, 1, R).addImm(0);
 477   } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 478     BuildMI(*MBB, IP, X86::MOV32ri, 1, R).addGlobalAddress(CPR->getValue());
 479   } else {
 480     std::cerr << "Offending constant: " << C << "\n";
 481     assert(0 && "Type not handled yet!");
 482   }
 483 }
 484
 485 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 486 /// the stack into virtual registers.
 487 ///
 488 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 489   // Emit instructions to load the arguments...  On entry to a function on the
 490   // X86, the stack frame looks like this:
 491   //
 492   // [ESP] -- return address
 493   // [ESP + 4] -- first argument (leftmost lexically)
 494   // [ESP + 8] -- second argument, if first argument is four bytes in size
 495   //    ...
 496   //
 497   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 498   MachineFrameInfo *MFI = F->getFrameInfo();
 499
 500   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 501     unsigned Reg = getReg(*I);
 502
 503     int FI;          // Frame object index
 504     switch (getClassB(I->getType())) {
 505     case cByte:
 506       FI = MFI->CreateFixedObject(1, ArgOffset);
 507       addFrameReference(BuildMI(BB, X86::MOV8rm, 4, Reg), FI);
 508       break;
 509     case cShort:
 510       FI = MFI->CreateFixedObject(2, ArgOffset);
 511       addFrameReference(BuildMI(BB, X86::MOV16rm, 4, Reg), FI);
 512       break;
 513     case cInt:
 514       FI = MFI->CreateFixedObject(4, ArgOffset);
 515       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Reg), FI);
 516       break;
 517     case cLong:
 518       FI = MFI->CreateFixedObject(8, ArgOffset);
 519       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Reg), FI);
 520       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Reg+1), FI, 4);
 521       ArgOffset += 4;   // longs require 4 additional bytes
 522       break;
 523     case cFP:
 524       unsigned Opcode;
 525       if (I->getType() == Type::FloatTy) {
 526         Opcode = X86::FLD32m;
 527         FI = MFI->CreateFixedObject(4, ArgOffset);
 528       } else {
 529         Opcode = X86::FLD64m;
 530         FI = MFI->CreateFixedObject(8, ArgOffset);
 531         ArgOffset += 4;   // doubles require 4 additional bytes
 532       }
 533       addFrameReference(BuildMI(BB, Opcode, 4, Reg), FI);
 534       break;
 535     default:
 536       assert(0 && "Unhandled argument type!");
 537     }
 538     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 539   }
 540
 541   // If the function takes variable number of arguments, add a frame offset for
 542   // the start of the first vararg value... this is used to expand
 543   // llvm.va_start.
 544   if (Fn.getFunctionType()->isVarArg())
 545     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 546 }
 547
 548
 549 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 550 /// because we have to generate our sources into the source basic blocks, not
 551 /// the current one.
 552 ///
 553 void ISel::SelectPHINodes() {
 554   const TargetInstrInfo &TII = TM.getInstrInfo();
 555   const Function &LF = *F->getFunction();  // The LLVM function...
 556   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 557     const BasicBlock *BB = I;
 558     MachineBasicBlock &MBB = *MBBMap[I];
 559
 560     // Loop over all of the PHI nodes in the LLVM basic block...
 561     MachineBasicBlock::iterator PHIInsertPoint = MBB.begin();
 562     for (BasicBlock::const_iterator I = BB->begin();
 563          PHINode *PN = const_cast<PHINode*>(dyn_cast<PHINode>(I)); ++I) {
 564
 565       // Create a new machine instr PHI node, and insert it.
 566       unsigned PHIReg = getReg(*PN);
 567       MachineInstr *PhiMI = BuildMI(MBB, PHIInsertPoint,
 568                                     X86::PHI, PN->getNumOperands(), PHIReg);
 569
 570       MachineInstr *LongPhiMI = 0;
 571       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy)
 572         LongPhiMI = BuildMI(MBB, PHIInsertPoint,
 573                             X86::PHI, PN->getNumOperands(), PHIReg+1);
 574
 575       // PHIValues - Map of blocks to incoming virtual registers.  We use this
 576       // so that we only initialize one incoming value for a particular block,
 577       // even if the block has multiple entries in the PHI node.
 578       //
 579       std::map<MachineBasicBlock*, unsigned> PHIValues;
 580
 581       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 582         MachineBasicBlock *PredMBB = MBBMap[PN->getIncomingBlock(i)];
 583         unsigned ValReg;
 584         std::map<MachineBasicBlock*, unsigned>::iterator EntryIt =
 585           PHIValues.lower_bound(PredMBB);
 586
 587         if (EntryIt != PHIValues.end() && EntryIt->first == PredMBB) {
 588           // We already inserted an initialization of the register for this
 589           // predecessor.  Recycle it.
 590           ValReg = EntryIt->second;
 591
 592         } else {
 593           // Get the incoming value into a virtual register.
 594           //
 595           Value *Val = PN->getIncomingValue(i);
 596
 597           // If this is a constant or GlobalValue, we may have to insert code
 598           // into the basic block to compute it into a virtual register.
 599           if (isa<Constant>(Val) || isa<GlobalValue>(Val)) {
 600             // Because we don't want to clobber any values which might be in
 601             // physical registers with the computation of this constant (which
 602             // might be arbitrarily complex if it is a constant expression),
 603             // just insert the computation at the top of the basic block.
 604             MachineBasicBlock::iterator PI = PredMBB->begin();
 605
 606             // Skip over any PHI nodes though!
 607             while (PI != PredMBB->end() && PI->getOpcode() == X86::PHI)
 608               ++PI;
 609
 610             ValReg = getReg(Val, PredMBB, PI);
 611           } else {
 612             ValReg = getReg(Val);
 613           }
 614
 615           // Remember that we inserted a value for this PHI for this predecessor
 616           PHIValues.insert(EntryIt, std::make_pair(PredMBB, ValReg));
 617         }
 618
 619         PhiMI->addRegOperand(ValReg);
 620         PhiMI->addMachineBasicBlockOperand(PredMBB);
 621         if (LongPhiMI) {
 622           LongPhiMI->addRegOperand(ValReg+1);
 623           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 624         }
 625       }
 626
 627       // Now that we emitted all of the incoming values for the PHI node, make
 628       // sure to reposition the InsertPoint after the PHI that we just added.
 629       // This is needed because we might have inserted a constant into this
 630       // block, right after the PHI's which is before the old insert point!
 631       PHIInsertPoint = LongPhiMI ? LongPhiMI : PhiMI;
 632       ++PHIInsertPoint;
 633     }
 634   }
 635 }
 636
 637 /// RequiresFPRegKill - The floating point stackifier pass cannot insert
 638 /// compensation code on critical edges.  As such, it requires that we kill all
 639 /// FP registers on the exit from any blocks that either ARE critical edges, or
 640 /// branch to a block that has incoming critical edges.
 641 ///
 642 /// Note that this kill instruction will eventually be eliminated when
 643 /// restrictions in the stackifier are relaxed.
 644 ///
 645 static bool RequiresFPRegKill(const BasicBlock *BB) {
 646 #if 0
 647   for (succ_const_iterator SI = succ_begin(BB), E = succ_end(BB); SI!=E; ++SI) {
 648     const BasicBlock *Succ = *SI;
 649     pred_const_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
 650     ++PI;  // Block have at least one predecessory
 651     if (PI != PE) {             // If it has exactly one, this isn't crit edge
 652       // If this block has more than one predecessor, check all of the
 653       // predecessors to see if they have multiple successors.  If so, then the
 654       // block we are analyzing needs an FPRegKill.
 655       for (PI = pred_begin(Succ); PI != PE; ++PI) {
 656         const BasicBlock *Pred = *PI;
 657         succ_const_iterator SI2 = succ_begin(Pred);
 658         ++SI2;  // There must be at least one successor of this block.
 659         if (SI2 != succ_end(Pred))
 660           return true;   // Yes, we must insert the kill on this edge.
 661       }
 662     }
 663   }
 664   // If we got this far, there is no need to insert the kill instruction.
 665   return false;
 666 #else
 667   return true;
 668 #endif
 669 }
 670
 671 // InsertFPRegKills - Insert FP_REG_KILL instructions into basic blocks that
 672 // need them.  This only occurs due to the floating point stackifier not being
 673 // aggressive enough to handle arbitrary global stackification.
 674 //
 675 // Currently we insert an FP_REG_KILL instruction into each block that uses or
 676 // defines a floating point virtual register.
 677 //
 678 // When the global register allocators (like linear scan) finally update live
 679 // variable analysis, we can keep floating point values in registers across
 680 // portions of the CFG that do not involve critical edges.  This will be a big
 681 // win, but we are waiting on the global allocators before we can do this.
 682 //
 683 // With a bit of work, the floating point stackifier pass can be enhanced to
 684 // break critical edges as needed (to make a place to put compensation code),
 685 // but this will require some infrastructure improvements as well.
 686 //
 687 void ISel::InsertFPRegKills() {
 688   SSARegMap &RegMap = *F->getSSARegMap();
 689
 690   for (MachineFunction::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 691     for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
 692       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 693       MachineOperand& MO = I->getOperand(i);
 694         if (MO.isRegister() && MO.getReg()) {
 695           unsigned Reg = MO.getReg();
 696           if (MRegisterInfo::isVirtualRegister(Reg))
 697             if (RegMap.getRegClass(Reg)->getSize() == 10)
 698               goto UsesFPReg;
 699         }
 700       }
 701     // If we haven't found an FP register use or def in this basic block, check
 702     // to see if any of our successors has an FP PHI node, which will cause a
 703     // copy to be inserted into this block.
 704     for (succ_const_iterator SI = succ_begin(BB->getBasicBlock()),
 705            E = succ_end(BB->getBasicBlock()); SI != E; ++SI) {
 706       MachineBasicBlock *SBB = MBBMap[*SI];
 707       for (MachineBasicBlock::iterator I = SBB->begin();
 708            I != SBB->end() && I->getOpcode() == X86::PHI; ++I) {
 709         if (RegMap.getRegClass(I->getOperand(0).getReg())->getSize() == 10)
 710           goto UsesFPReg;
 711       }
 712     }
 713     continue;
 714   UsesFPReg:
 715     // Okay, this block uses an FP register.  If the block has successors (ie,
 716     // it's not an unwind/return), insert the FP_REG_KILL instruction.
 717     if (BB->getBasicBlock()->getTerminator()->getNumSuccessors() &&
 718         RequiresFPRegKill(BB->getBasicBlock())) {
 719       BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
 720       ++NumFPKill;
 721     }
 722   }
 723 }
 724
 725
 726 // canFoldSetCCIntoBranch - Return the setcc instruction if we can fold it into
 727 // the conditional branch instruction which is the only user of the cc
 728 // instruction.  This is the case if the conditional branch is the only user of
 729 // the setcc, and if the setcc is in the same basic block as the conditional
 730 // branch.  We also don't handle long arguments below, so we reject them here as
 731 // well.
 732 //
 733 static SetCondInst *canFoldSetCCIntoBranch(Value *V) {
 734   if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 735     if (SCI->hasOneUse() && isa<BranchInst>(SCI->use_back()) &&
 736         SCI->getParent() == cast<BranchInst>(SCI->use_back())->getParent()) {
 737       const Type *Ty = SCI->getOperand(0)->getType();
 738       if (Ty != Type::LongTy && Ty != Type::ULongTy)
 739         return SCI;
 740     }
 741   return 0;
 742 }
 743
 744 // Return a fixed numbering for setcc instructions which does not depend on the
 745 // order of the opcodes.
 746 //
 747 static unsigned getSetCCNumber(unsigned Opcode) {
 748   switch(Opcode) {
 749   default: assert(0 && "Unknown setcc instruction!");
 750   case Instruction::SetEQ: return 0;
 751   case Instruction::SetNE: return 1;
 752   case Instruction::SetLT: return 2;
 753   case Instruction::SetGE: return 3;
 754   case Instruction::SetGT: return 4;
 755   case Instruction::SetLE: return 5;
 756   }
 757 }
 758
 759 // LLVM  -> X86 signed  X86 unsigned
 760 // -----    ----------  ------------
 761 // seteq -> sete        sete
 762 // setne -> setne       setne
 763 // setlt -> setl        setb
 764 // setge -> setge       setae
 765 // setgt -> setg        seta
 766 // setle -> setle       setbe
 767 // ----
 768 //          sets                       // Used by comparison with 0 optimization
 769 //          setns
 770 static const unsigned SetCCOpcodeTab[2][8] = {
 771   { X86::SETEr, X86::SETNEr, X86::SETBr, X86::SETAEr, X86::SETAr, X86::SETBEr,
 772     0, 0 },
 773   { X86::SETEr, X86::SETNEr, X86::SETLr, X86::SETGEr, X86::SETGr, X86::SETLEr,
 774     X86::SETSr, X86::SETNSr },
 775 };
 776
 777 // EmitComparison - This function emits a comparison of the two operands,
 778 // returning the extended setcc code to use.
 779 unsigned ISel::EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 780                               MachineBasicBlock *MBB,
 781                               MachineBasicBlock::iterator IP) {
 782   // The arguments are already supposed to be of the same type.
 783   const Type *CompTy = Op0->getType();
 784   unsigned Class = getClassB(CompTy);
 785   unsigned Op0r = getReg(Op0, MBB, IP);
 786
 787   // Special case handling of: cmp R, i
 788   if (Class == cByte || Class == cShort || Class == cInt)
 789     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 790       uint64_t Op1v = cast<ConstantInt>(CI)->getRawValue();
 791
 792       // Mask off any upper bits of the constant, if there are any...
 793       Op1v &= (1ULL << (8 << Class)) - 1;
 794
 795       // If this is a comparison against zero, emit more efficient code.  We
 796       // can't handle unsigned comparisons against zero unless they are == or
 797       // !=.  These should have been strength reduced already anyway.
 798       if (Op1v == 0 && (CompTy->isSigned() || OpNum < 2)) {
 799         static const unsigned TESTTab[] = {
 800           X86::TEST8rr, X86::TEST16rr, X86::TEST32rr
 801         };
 802         BuildMI(*MBB, IP, TESTTab[Class], 2).addReg(Op0r).addReg(Op0r);
 803
 804         if (OpNum == 2) return 6;   // Map jl -> js
 805         if (OpNum == 3) return 7;   // Map jg -> jns
 806         return OpNum;
 807       }
 808
 809       static const unsigned CMPTab[] = {
 810         X86::CMP8ri, X86::CMP16ri, X86::CMP32ri
 811       };
 812
 813       BuildMI(*MBB, IP, CMPTab[Class], 2).addReg(Op0r).addImm(Op1v);
 814       return OpNum;
 815     }
 816
 817   // Special case handling of comparison against +/- 0.0
 818   if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op1))
 819     if (CFP->isExactlyValue(+0.0) || CFP->isExactlyValue(-0.0)) {
 820       BuildMI(*MBB, IP, X86::FTST, 1).addReg(Op0r);
 821       BuildMI(*MBB, IP, X86::FNSTSW8r, 0);
 822       BuildMI(*MBB, IP, X86::SAHF, 1);
 823       return OpNum;
 824     }
 825
 826   unsigned Op1r = getReg(Op1, MBB, IP);
 827   switch (Class) {
 828   default: assert(0 && "Unknown type class!");
 829     // Emit: cmp <var1>, <var2> (do the comparison).  We can
 830     // compare 8-bit with 8-bit, 16-bit with 16-bit, 32-bit with
 831     // 32-bit.
 832   case cByte:
 833     BuildMI(*MBB, IP, X86::CMP8rr, 2).addReg(Op0r).addReg(Op1r);
 834     break;
 835   case cShort:
 836     BuildMI(*MBB, IP, X86::CMP16rr, 2).addReg(Op0r).addReg(Op1r);
 837     break;
 838   case cInt:
 839     BuildMI(*MBB, IP, X86::CMP32rr, 2).addReg(Op0r).addReg(Op1r);
 840     break;
 841   case cFP:
 842     BuildMI(*MBB, IP, X86::FpUCOM, 2).addReg(Op0r).addReg(Op1r);
 843     BuildMI(*MBB, IP, X86::FNSTSW8r, 0);
 844     BuildMI(*MBB, IP, X86::SAHF, 1);
 845     break;
 846
 847   case cLong:
 848     if (OpNum < 2) {    // seteq, setne
 849       unsigned LoTmp = makeAnotherReg(Type::IntTy);
 850       unsigned HiTmp = makeAnotherReg(Type::IntTy);
 851       unsigned FinalTmp = makeAnotherReg(Type::IntTy);
 852       BuildMI(*MBB, IP, X86::XOR32rr, 2, LoTmp).addReg(Op0r).addReg(Op1r);
 853       BuildMI(*MBB, IP, X86::XOR32rr, 2, HiTmp).addReg(Op0r+1).addReg(Op1r+1);
 854       BuildMI(*MBB, IP, X86::OR32rr,  2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
 855       break;  // Allow the sete or setne to be generated from flags set by OR
 856     } else {
 857       // Emit a sequence of code which compares the high and low parts once
 858       // each, then uses a conditional move to handle the overflow case.  For
 859       // example, a setlt for long would generate code like this:
 860       //
 861       // AL = lo(op1) < lo(op2)   // Signedness depends on operands
 862       // BL = hi(op1) < hi(op2)   // Always unsigned comparison
 863       // dest = hi(op1) == hi(op2) ? AL : BL;
 864       //
 865
 866       // FIXME: This would be much better if we had hierarchical register
 867       // classes!  Until then, hardcode registers so that we can deal with their
 868       // aliases (because we don't have conditional byte moves).
 869       //
 870       BuildMI(*MBB, IP, X86::CMP32rr, 2).addReg(Op0r).addReg(Op1r);
 871       BuildMI(*MBB, IP, SetCCOpcodeTab[0][OpNum], 0, X86::AL);
 872       BuildMI(*MBB, IP, X86::CMP32rr, 2).addReg(Op0r+1).addReg(Op1r+1);
 873       BuildMI(*MBB, IP, SetCCOpcodeTab[CompTy->isSigned()][OpNum], 0, X86::BL);
 874       BuildMI(*MBB, IP, X86::IMPLICIT_DEF, 0, X86::BH);
 875       BuildMI(*MBB, IP, X86::IMPLICIT_DEF, 0, X86::AH);
 876       BuildMI(*MBB, IP, X86::CMOVE16rr, 2, X86::BX).addReg(X86::BX)
 877                                                    .addReg(X86::AX);
 878       // NOTE: visitSetCondInst knows that the value is dumped into the BL
 879       // register at this point for long values...
 880       return OpNum;
 881     }
 882   }
 883   return OpNum;
 884 }
 885
 886
 887 /// SetCC instructions - Here we just emit boilerplate code to set a byte-sized
 888 /// register, then move it to wherever the result should be.
 889 ///
 890 void ISel::visitSetCondInst(SetCondInst &I) {
 891   if (canFoldSetCCIntoBranch(&I)) return;  // Fold this into a branch...
 892
 893   unsigned DestReg = getReg(I);
 894   MachineBasicBlock::iterator MII = BB->end();
 895   emitSetCCOperation(BB, MII, I.getOperand(0), I.getOperand(1), I.getOpcode(),
 896                      DestReg);
 897 }
 898
 899 /// emitSetCCOperation - Common code shared between visitSetCondInst and
 900 /// constant expression support.
 901 ///
 902 void ISel::emitSetCCOperation(MachineBasicBlock *MBB,
 903                               MachineBasicBlock::iterator IP,
 904                               Value *Op0, Value *Op1, unsigned Opcode,
 905                               unsigned TargetReg) {
 906   unsigned OpNum = getSetCCNumber(Opcode);
 907   OpNum = EmitComparison(OpNum, Op0, Op1, MBB, IP);
 908
 909   const Type *CompTy = Op0->getType();
 910   unsigned CompClass = getClassB(CompTy);
 911   bool isSigned = CompTy->isSigned() && CompClass != cFP;
 912
 913   if (CompClass != cLong || OpNum < 2) {
 914     // Handle normal comparisons with a setcc instruction...
 915     BuildMI(*MBB, IP, SetCCOpcodeTab[isSigned][OpNum], 0, TargetReg);
 916   } else {
 917     // Handle long comparisons by copying the value which is already in BL into
 918     // the register we want...
 919     BuildMI(*MBB, IP, X86::MOV8rr, 1, TargetReg).addReg(X86::BL);
 920   }
 921 }
 922
 923
 924
 925
 926 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
 927 /// operand, in the specified target register.
 928 ///
 929 void ISel::promote32(unsigned targetReg, const ValueRecord &VR) {
 930   bool isUnsigned = VR.Ty->isUnsigned();
 931
 932   // Make sure we have the register number for this value...
 933   unsigned Reg = VR.Val ? getReg(VR.Val) : VR.Reg;
 934
 935   switch (getClassB(VR.Ty)) {
 936   case cByte:
 937     // Extend value into target register (8->32)
 938     if (isUnsigned)
 939       BuildMI(BB, X86::MOVZX32rr8, 1, targetReg).addReg(Reg);
 940     else
 941       BuildMI(BB, X86::MOVSX32rr8, 1, targetReg).addReg(Reg);
 942     break;
 943   case cShort:
 944     // Extend value into target register (16->32)
 945     if (isUnsigned)
 946       BuildMI(BB, X86::MOVZX32rr16, 1, targetReg).addReg(Reg);
 947     else
 948       BuildMI(BB, X86::MOVSX32rr16, 1, targetReg).addReg(Reg);
 949     break;
 950   case cInt:
 951     // Move value into target register (32->32)
 952     BuildMI(BB, X86::MOV32rr, 1, targetReg).addReg(Reg);
 953     break;
 954   default:
 955     assert(0 && "Unpromotable operand class in promote32");
 956   }
 957 }
 958
 959 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 960 /// we have the following possibilities:
 961 ///
 962 ///   ret void: No return value, simply emit a 'ret' instruction
 963 ///   ret sbyte, ubyte : Extend value into EAX and return
 964 ///   ret short, ushort: Extend value into EAX and return
 965 ///   ret int, uint    : Move value into EAX and return
 966 ///   ret pointer      : Move value into EAX and return
 967 ///   ret long, ulong  : Move value into EAX/EDX and return
 968 ///   ret float/double : Top of FP stack
 969 ///
 970 void ISel::visitReturnInst(ReturnInst &I) {
 971   if (I.getNumOperands() == 0) {
 972     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
 973     return;
 974   }
 975
 976   Value *RetVal = I.getOperand(0);
 977   unsigned RetReg = getReg(RetVal);
 978   switch (getClassB(RetVal->getType())) {
 979   case cByte:   // integral return values: extend or move into EAX and return
 980   case cShort:
 981   case cInt:
 982     promote32(X86::EAX, ValueRecord(RetReg, RetVal->getType()));
 983     // Declare that EAX is live on exit
 984     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
 985     break;
 986   case cFP:                   // Floats & Doubles: Return in ST(0)
 987     BuildMI(BB, X86::FpSETRESULT, 1).addReg(RetReg);
 988     // Declare that top-of-stack is live on exit
 989     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
 990     break;
 991   case cLong:
 992     BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(RetReg);
 993     BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(RetReg+1);
 994     // Declare that EAX & EDX are live on exit
 995     BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX)
 996       .addReg(X86::ESP);
 997     break;
 998   default:
 999     visitInstruction(I);
1000   }
1001   // Emit a 'ret' instruction
1002   BuildMI(BB, X86::RET, 0);
1003 }
1004
1005 // getBlockAfter - Return the basic block which occurs lexically after the
1006 // specified one.
1007 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
1008   Function::iterator I = BB; ++I;  // Get iterator to next block
1009   return I != BB->getParent()->end() ? &*I : 0;
1010 }
1011
1012 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
1013 /// that since code layout is frozen at this point, that if we are trying to
1014 /// jump to a block that is the immediate successor of the current block, we can
1015 /// just make a fall-through (but we don't currently).
1016 ///
1017 void ISel::visitBranchInst(BranchInst &BI) {
1018   BasicBlock *NextBB = getBlockAfter(BI.getParent());  // BB after current one
1019
1020   if (!BI.isConditional()) {  // Unconditional branch?
1021     if (BI.getSuccessor(0) != NextBB)
1022       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
1023     return;
1024   }
1025
1026   // See if we can fold the setcc into the branch itself...
1027   SetCondInst *SCI = canFoldSetCCIntoBranch(BI.getCondition());
1028   if (SCI == 0) {
1029     // Nope, cannot fold setcc into this branch.  Emit a branch on a condition
1030     // computed some other way...
1031     unsigned condReg = getReg(BI.getCondition());
1032     BuildMI(BB, X86::CMP8ri, 2).addReg(condReg).addImm(0);
1033     if (BI.getSuccessor(1) == NextBB) {
1034       if (BI.getSuccessor(0) != NextBB)
1035         BuildMI(BB, X86::JNE, 1).addPCDisp(BI.getSuccessor(0));
1036     } else {
1037       BuildMI(BB, X86::JE, 1).addPCDisp(BI.getSuccessor(1));
1038
1039       if (BI.getSuccessor(0) != NextBB)
1040         BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
1041     }
1042     return;
1043   }
1044
1045   unsigned OpNum = getSetCCNumber(SCI->getOpcode());
1046   MachineBasicBlock::iterator MII = BB->end();
1047   OpNum = EmitComparison(OpNum, SCI->getOperand(0), SCI->getOperand(1), BB,MII);
1048
1049   const Type *CompTy = SCI->getOperand(0)->getType();
1050   bool isSigned = CompTy->isSigned() && getClassB(CompTy) != cFP;
1051
1052
1053   // LLVM  -> X86 signed  X86 unsigned
1054   // -----    ----------  ------------
1055   // seteq -> je          je
1056   // setne -> jne         jne
1057   // setlt -> jl          jb
1058   // setge -> jge         jae
1059   // setgt -> jg          ja
1060   // setle -> jle         jbe
1061   // ----
1062   //          js                  // Used by comparison with 0 optimization
1063   //          jns
1064
1065   static const unsigned OpcodeTab[2][8] = {
1066     { X86::JE, X86::JNE, X86::JB, X86::JAE, X86::JA, X86::JBE, 0, 0 },
1067     { X86::JE, X86::JNE, X86::JL, X86::JGE, X86::JG, X86::JLE,
1068       X86::JS, X86::JNS },
1069   };
1070
1071   if (BI.getSuccessor(0) != NextBB) {
1072     BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(0));
1073     if (BI.getSuccessor(1) != NextBB)
1074       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(1));
1075   } else {
1076     // Change to the inverse condition...
1077     if (BI.getSuccessor(1) != NextBB) {
1078       OpNum ^= 1;
1079       BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(1));
1080     }
1081   }
1082 }
1083
1084
1085 /// doCall - This emits an abstract call instruction, setting up the arguments
1086 /// and the return value as appropriate.  For the actual function call itself,
1087 /// it inserts the specified CallMI instruction into the stream.
1088 ///
1089 void ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
1090                   const std::vector<ValueRecord> &Args) {
1091
1092   // Count how many bytes are to be pushed on the stack...
1093   unsigned NumBytes = 0;
1094
1095   if (!Args.empty()) {
1096     for (unsigned i = 0, e = Args.size(); i != e; ++i)
1097       switch (getClassB(Args[i].Ty)) {
1098       case cByte: case cShort: case cInt:
1099         NumBytes += 4; break;
1100       case cLong:
1101         NumBytes += 8; break;
1102       case cFP:
1103         NumBytes += Args[i].Ty == Type::FloatTy ? 4 : 8;
1104         break;
1105       default: assert(0 && "Unknown class!");
1106       }
1107
1108     // Adjust the stack pointer for the new arguments...
1109     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(NumBytes);
1110
1111     // Arguments go on the stack in reverse order, as specified by the ABI.
1112     unsigned ArgOffset = 0;
1113     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1114       unsigned ArgReg;
1115       switch (getClassB(Args[i].Ty)) {
1116       case cByte:
1117       case cShort:
1118         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1119           // Zero/Sign extend constant, then stuff into memory.
1120           ConstantInt *Val = cast<ConstantInt>(Args[i].Val);
1121           Val = cast<ConstantInt>(ConstantExpr::getCast(Val, Type::IntTy));
1122           addRegOffset(BuildMI(BB, X86::MOV32mi, 5), X86::ESP, ArgOffset)
1123             .addImm(Val->getRawValue() & 0xFFFFFFFF);
1124         } else {
1125           // Promote arg to 32 bits wide into a temporary register...
1126           ArgReg = makeAnotherReg(Type::UIntTy);
1127           promote32(ArgReg, Args[i]);
1128           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1129                        X86::ESP, ArgOffset).addReg(ArgReg);
1130         }
1131         break;
1132       case cInt:
1133         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1134           unsigned Val = cast<ConstantInt>(Args[i].Val)->getRawValue();
1135           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1136                        X86::ESP, ArgOffset).addImm(Val);
1137         } else {
1138           ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1139           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1140                        X86::ESP, ArgOffset).addReg(ArgReg);
1141         }
1142         break;
1143       case cLong:
1144         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1145         addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1146                      X86::ESP, ArgOffset).addReg(ArgReg);
1147         addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1148                      X86::ESP, ArgOffset+4).addReg(ArgReg+1);
1149         ArgOffset += 4;        // 8 byte entry, not 4.
1150         break;
1151
1152       case cFP:
1153         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1154         if (Args[i].Ty == Type::FloatTy) {
1155           addRegOffset(BuildMI(BB, X86::FST32m, 5),
1156                        X86::ESP, ArgOffset).addReg(ArgReg);
1157         } else {
1158           assert(Args[i].Ty == Type::DoubleTy && "Unknown FP type!");
1159           addRegOffset(BuildMI(BB, X86::FST64m, 5),
1160                        X86::ESP, ArgOffset).addReg(ArgReg);
1161           ArgOffset += 4;       // 8 byte entry, not 4.
1162         }
1163         break;
1164
1165       default: assert(0 && "Unknown class!");
1166       }
1167       ArgOffset += 4;
1168     }
1169   } else {
1170     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(0);
1171   }
1172
1173   BB->push_back(CallMI);
1174
1175   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addImm(NumBytes);
1176
1177   // If there is a return value, scavenge the result from the location the call
1178   // leaves it in...
1179   //
1180   if (Ret.Ty != Type::VoidTy) {
1181     unsigned DestClass = getClassB(Ret.Ty);
1182     switch (DestClass) {
1183     case cByte:
1184     case cShort:
1185     case cInt: {
1186       // Integral results are in %eax, or the appropriate portion
1187       // thereof.
1188       static const unsigned regRegMove[] = {
1189         X86::MOV8rr, X86::MOV16rr, X86::MOV32rr
1190       };
1191       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
1192       BuildMI(BB, regRegMove[DestClass], 1, Ret.Reg).addReg(AReg[DestClass]);
1193       break;
1194     }
1195     case cFP:     // Floating-point return values live in %ST(0)
1196       BuildMI(BB, X86::FpGETRESULT, 1, Ret.Reg);
1197       break;
1198     case cLong:   // Long values are left in EDX:EAX
1199       BuildMI(BB, X86::MOV32rr, 1, Ret.Reg).addReg(X86::EAX);
1200       BuildMI(BB, X86::MOV32rr, 1, Ret.Reg+1).addReg(X86::EDX);
1201       break;
1202     default: assert(0 && "Unknown class!");
1203     }
1204   }
1205 }
1206
1207
1208 /// visitCallInst - Push args on stack and do a procedure call instruction.
1209 void ISel::visitCallInst(CallInst &CI) {
1210   MachineInstr *TheCall;
1211   if (Function *F = CI.getCalledFunction()) {
1212     // Is it an intrinsic function call?
1213     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) {
1214       visitIntrinsicCall(ID, CI);   // Special intrinsics are not handled here
1215       return;
1216     }
1217
1218     // Emit a CALL instruction with PC-relative displacement.
1219     TheCall = BuildMI(X86::CALLpcrel32, 1).addGlobalAddress(F, true);
1220   } else {  // Emit an indirect call...
1221     unsigned Reg = getReg(CI.getCalledValue());
1222     TheCall = BuildMI(X86::CALL32r, 1).addReg(Reg);
1223   }
1224
1225   std::vector<ValueRecord> Args;
1226   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
1227     Args.push_back(ValueRecord(CI.getOperand(i)));
1228
1229   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
1230   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args);
1231 }
1232
1233
1234 /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
1235 /// function, lowering any calls to unknown intrinsic functions into the
1236 /// equivalent LLVM code.
1237 ///
1238 void ISel::LowerUnknownIntrinsicFunctionCalls(Function &F) {
1239   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1240     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
1241       if (CallInst *CI = dyn_cast<CallInst>(I++))
1242         if (Function *F = CI->getCalledFunction())
1243           switch (F->getIntrinsicID()) {
1244           case Intrinsic::not_intrinsic:
1245           case Intrinsic::va_start:
1246           case Intrinsic::va_copy:
1247           case Intrinsic::va_end:
1248           case Intrinsic::returnaddress:
1249           case Intrinsic::frameaddress:
1250           case Intrinsic::memcpy:
1251           case Intrinsic::memset:
1252             // We directly implement these intrinsics
1253             break;
1254           default:
1255             // All other intrinsic calls we must lower.
1256             Instruction *Before = CI->getPrev();
1257             TM.getIntrinsicLowering().LowerIntrinsicCall(CI);
1258             if (Before) {        // Move iterator to instruction after call
1259               I = Before;  ++I;
1260             } else {
1261               I = BB->begin();
1262             }
1263           }
1264
1265 }
1266
1267 void ISel::visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI) {
1268   unsigned TmpReg1, TmpReg2;
1269   switch (ID) {
1270   case Intrinsic::va_start:
1271     // Get the address of the first vararg value...
1272     TmpReg1 = getReg(CI);
1273     addFrameReference(BuildMI(BB, X86::LEA32r, 5, TmpReg1), VarArgsFrameIndex);
1274     return;
1275
1276   case Intrinsic::va_copy:
1277     TmpReg1 = getReg(CI);
1278     TmpReg2 = getReg(CI.getOperand(1));
1279     BuildMI(BB, X86::MOV32rr, 1, TmpReg1).addReg(TmpReg2);
1280     return;
1281   case Intrinsic::va_end: return;   // Noop on X86
1282
1283   case Intrinsic::returnaddress:
1284   case Intrinsic::frameaddress:
1285     TmpReg1 = getReg(CI);
1286     if (cast<Constant>(CI.getOperand(1))->isNullValue()) {
1287       if (ID == Intrinsic::returnaddress) {
1288         // Just load the return address
1289         addFrameReference(BuildMI(BB, X86::MOV32rm, 4, TmpReg1),
1290                           ReturnAddressIndex);
1291       } else {
1292         addFrameReference(BuildMI(BB, X86::LEA32r, 4, TmpReg1),
1293                           ReturnAddressIndex, -4);
1294       }
1295     } else {
1296       // Values other than zero are not implemented yet.
1297       BuildMI(BB, X86::MOV32ri, 1, TmpReg1).addImm(0);
1298     }
1299     return;
1300
1301   case Intrinsic::memcpy: {
1302     assert(CI.getNumOperands() == 5 && "Illegal llvm.memcpy call!");
1303     unsigned Align = 1;
1304     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1305       Align = AlignC->getRawValue();
1306       if (Align == 0) Align = 1;
1307     }
1308
1309     // Turn the byte code into # iterations
1310     unsigned CountReg;
1311     unsigned Opcode;
1312     switch (Align & 3) {
1313     case 2:   // WORD aligned
1314       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1315         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1316       } else {
1317         CountReg = makeAnotherReg(Type::IntTy);
1318         unsigned ByteReg = getReg(CI.getOperand(3));
1319         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
1320       }
1321       Opcode = X86::REP_MOVSW;
1322       break;
1323     case 0:   // DWORD aligned
1324       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1325         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1326       } else {
1327         CountReg = makeAnotherReg(Type::IntTy);
1328         unsigned ByteReg = getReg(CI.getOperand(3));
1329         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
1330       }
1331       Opcode = X86::REP_MOVSD;
1332       break;
1333     default:  // BYTE aligned
1334       CountReg = getReg(CI.getOperand(3));
1335       Opcode = X86::REP_MOVSB;
1336       break;
1337     }
1338
1339     // No matter what the alignment is, we put the source in ESI, the
1340     // destination in EDI, and the count in ECX.
1341     TmpReg1 = getReg(CI.getOperand(1));
1342     TmpReg2 = getReg(CI.getOperand(2));
1343     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
1344     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
1345     BuildMI(BB, X86::MOV32rr, 1, X86::ESI).addReg(TmpReg2);
1346     BuildMI(BB, Opcode, 0);
1347     return;
1348   }
1349   case Intrinsic::memset: {
1350     assert(CI.getNumOperands() == 5 && "Illegal llvm.memset call!");
1351     unsigned Align = 1;
1352     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1353       Align = AlignC->getRawValue();
1354       if (Align == 0) Align = 1;
1355     }
1356
1357     // Turn the byte code into # iterations
1358     unsigned CountReg;
1359     unsigned Opcode;
1360     if (ConstantInt *ValC = dyn_cast<ConstantInt>(CI.getOperand(2))) {
1361       unsigned Val = ValC->getRawValue() & 255;
1362
1363       // If the value is a constant, then we can potentially use larger copies.
1364       switch (Align & 3) {
1365       case 2:   // WORD aligned
1366         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1367           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1368         } else {
1369           CountReg = makeAnotherReg(Type::IntTy);
1370           unsigned ByteReg = getReg(CI.getOperand(3));
1371           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
1372         }
1373         BuildMI(BB, X86::MOV16ri, 1, X86::AX).addImm((Val << 8) | Val);
1374         Opcode = X86::REP_STOSW;
1375         break;
1376       case 0:   // DWORD aligned
1377         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1378           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1379         } else {
1380           CountReg = makeAnotherReg(Type::IntTy);
1381           unsigned ByteReg = getReg(CI.getOperand(3));
1382           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
1383         }
1384         Val = (Val << 8) | Val;
1385         BuildMI(BB, X86::MOV32ri, 1, X86::EAX).addImm((Val << 16) | Val);
1386         Opcode = X86::REP_STOSD;
1387         break;
1388       default:  // BYTE aligned
1389         CountReg = getReg(CI.getOperand(3));
1390         BuildMI(BB, X86::MOV8ri, 1, X86::AL).addImm(Val);
1391         Opcode = X86::REP_STOSB;
1392         break;
1393       }
1394     } else {
1395       // If it's not a constant value we are storing, just fall back.  We could
1396       // try to be clever to form 16 bit and 32 bit values, but we don't yet.
1397       unsigned ValReg = getReg(CI.getOperand(2));
1398       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
1399       CountReg = getReg(CI.getOperand(3));
1400       Opcode = X86::REP_STOSB;
1401     }
1402
1403     // No matter what the alignment is, we put the source in ESI, the
1404     // destination in EDI, and the count in ECX.
1405     TmpReg1 = getReg(CI.getOperand(1));
1406     //TmpReg2 = getReg(CI.getOperand(2));
1407     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
1408     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
1409     BuildMI(BB, Opcode, 0);
1410     return;
1411   }
1412
1413   default: assert(0 && "Error: unknown intrinsics should have been lowered!");
1414   }
1415 }
1416
1417
1418 /// visitSimpleBinary - Implement simple binary operators for integral types...
1419 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
1420 /// Xor.
1421 ///
1422 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
1423   unsigned DestReg = getReg(B);
1424   MachineBasicBlock::iterator MI = BB->end();
1425   Value *Op0 = B.getOperand(0), *Op1 = B.getOperand(1);
1426
1427   emitSimpleBinaryOperation(BB, MI, Op0, Op1, OperatorClass, DestReg);
1428 }
1429
1430 /// emitSimpleBinaryOperation - Implement simple binary operators for integral
1431 /// types...  OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for
1432 /// Or, 4 for Xor.
1433 ///
1434 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
1435 /// and constant expression support.
1436 ///
1437 void ISel::emitSimpleBinaryOperation(MachineBasicBlock *MBB,
1438                                      MachineBasicBlock::iterator IP,
1439                                      Value *Op0, Value *Op1,
1440                                      unsigned OperatorClass, unsigned DestReg) {
1441   unsigned Class = getClassB(Op0->getType());
1442
1443   // sub 0, X -> neg X
1444   if (OperatorClass == 1 && Class != cLong)
1445     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0)) {
1446       if (CI->isNullValue()) {
1447         unsigned op1Reg = getReg(Op1, MBB, IP);
1448         switch (Class) {
1449         default: assert(0 && "Unknown class for this function!");
1450         case cByte:
1451           BuildMI(*MBB, IP, X86::NEG8r, 1, DestReg).addReg(op1Reg);
1452           return;
1453         case cShort:
1454           BuildMI(*MBB, IP, X86::NEG16r, 1, DestReg).addReg(op1Reg);
1455           return;
1456         case cInt:
1457           BuildMI(*MBB, IP, X86::NEG32r, 1, DestReg).addReg(op1Reg);
1458           return;
1459         }
1460       }
1461     } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op0))
1462       if (CFP->isExactlyValue(-0.0)) {
1463         // -0.0 - X === -X
1464         unsigned op1Reg = getReg(Op1, MBB, IP);
1465         BuildMI(*MBB, IP, X86::FCHS, 1, DestReg).addReg(op1Reg);
1466         return;
1467       }
1468
1469   // Special case: op Reg, <const>
1470   if (Class != cLong && isa<ConstantInt>(Op1)) {
1471     ConstantInt *Op1C = cast<ConstantInt>(Op1);
1472     unsigned Op0r = getReg(Op0, MBB, IP);
1473
1474     // xor X, -1 -> not X
1475     if (OperatorClass == 4 && Op1C->isAllOnesValue()) {
1476       static unsigned const NOTTab[] = { X86::NOT8r, X86::NOT16r, X86::NOT32r };
1477       BuildMI(*MBB, IP, NOTTab[Class], 1, DestReg).addReg(Op0r);
1478       return;
1479     }
1480
1481     // add X, -1 -> dec X
1482     if (OperatorClass == 0 && Op1C->isAllOnesValue()) {
1483       static unsigned const DECTab[] = { X86::DEC8r, X86::DEC16r, X86::DEC32r };
1484       BuildMI(*MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
1485       return;
1486     }
1487
1488     // add X, 1 -> inc X
1489     if (OperatorClass == 0 && Op1C->equalsInt(1)) {
1490       static unsigned const DECTab[] = { X86::INC8r, X86::INC16r, X86::INC32r };
1491       BuildMI(*MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
1492       return;
1493     }
1494
1495     static const unsigned OpcodeTab[][3] = {
1496       // Arithmetic operators
1497       { X86::ADD8ri, X86::ADD16ri, X86::ADD32ri },  // ADD
1498       { X86::SUB8ri, X86::SUB16ri, X86::SUB32ri },  // SUB
1499
1500       // Bitwise operators
1501       { X86::AND8ri, X86::AND16ri, X86::AND32ri },  // AND
1502       { X86:: OR8ri, X86:: OR16ri, X86:: OR32ri },  // OR
1503       { X86::XOR8ri, X86::XOR16ri, X86::XOR32ri },  // XOR
1504     };
1505
1506     assert(Class < cFP && "General code handles 64-bit integer types!");
1507     unsigned Opcode = OpcodeTab[OperatorClass][Class];
1508
1509
1510     uint64_t Op1v = cast<ConstantInt>(Op1C)->getRawValue();
1511     BuildMI(*MBB, IP, Opcode, 5, DestReg).addReg(Op0r).addImm(Op1v);
1512     return;
1513   }
1514
1515   // Finally, handle the general case now.
1516   static const unsigned OpcodeTab[][4] = {
1517     // Arithmetic operators
1518     { X86::ADD8rr, X86::ADD16rr, X86::ADD32rr, X86::FpADD },  // ADD
1519     { X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, X86::FpSUB },  // SUB
1520
1521     // Bitwise operators
1522     { X86::AND8rr, X86::AND16rr, X86::AND32rr, 0 },  // AND
1523     { X86:: OR8rr, X86:: OR16rr, X86:: OR32rr, 0 },  // OR
1524     { X86::XOR8rr, X86::XOR16rr, X86::XOR32rr, 0 },  // XOR
1525   };
1526
1527   bool isLong = false;
1528   if (Class == cLong) {
1529     isLong = true;
1530     Class = cInt;          // Bottom 32 bits are handled just like ints
1531   }
1532
1533   unsigned Opcode = OpcodeTab[OperatorClass][Class];
1534   assert(Opcode && "Floating point arguments to logical inst?");
1535   unsigned Op0r = getReg(Op0, MBB, IP);
1536   unsigned Op1r = getReg(Op1, MBB, IP);
1537   BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
1538
1539   if (isLong) {        // Handle the upper 32 bits of long values...
1540     static const unsigned TopTab[] = {
1541       X86::ADC32rr, X86::SBB32rr, X86::AND32rr, X86::OR32rr, X86::XOR32rr
1542     };
1543     BuildMI(*MBB, IP, TopTab[OperatorClass], 2,
1544             DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
1545   }
1546 }
1547
1548 /// doMultiply - Emit appropriate instructions to multiply together the
1549 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
1550 /// result should be given as DestTy.
1551 ///
1552 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
1553                       unsigned DestReg, const Type *DestTy,
1554                       unsigned op0Reg, unsigned op1Reg) {
1555   unsigned Class = getClass(DestTy);
1556   switch (Class) {
1557   case cFP:              // Floating point multiply
1558     BuildMI(*MBB, MBBI, X86::FpMUL, 2, DestReg).addReg(op0Reg).addReg(op1Reg);
1559     return;
1560   case cInt:
1561   case cShort:
1562     BuildMI(*MBB, MBBI, Class == cInt ? X86::IMUL32rr:X86::IMUL16rr, 2, DestReg)
1563       .addReg(op0Reg).addReg(op1Reg);
1564     return;
1565   case cByte:
1566     // Must use the MUL instruction, which forces use of AL...
1567     BuildMI(*MBB, MBBI, X86::MOV8rr, 1, X86::AL).addReg(op0Reg);
1568     BuildMI(*MBB, MBBI, X86::MUL8r, 1).addReg(op1Reg);
1569     BuildMI(*MBB, MBBI, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
1570     return;
1571   default:
1572   case cLong: assert(0 && "doMultiply cannot operate on LONG values!");
1573   }
1574 }
1575
1576 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1577 // returns zero when the input is not exactly a power of two.
1578 static unsigned ExactLog2(unsigned Val) {
1579   if (Val == 0) return 0;
1580   unsigned Count = 0;
1581   while (Val != 1) {
1582     if (Val & 1) return 0;
1583     Val >>= 1;
1584     ++Count;
1585   }
1586   return Count+1;
1587 }
1588
1589 void ISel::doMultiplyConst(MachineBasicBlock *MBB,
1590                            MachineBasicBlock::iterator IP,
1591                            unsigned DestReg, const Type *DestTy,
1592                            unsigned op0Reg, unsigned ConstRHS) {
1593   unsigned Class = getClass(DestTy);
1594
1595   // If the element size is exactly a power of 2, use a shift to get it.
1596   if (unsigned Shift = ExactLog2(ConstRHS)) {
1597     switch (Class) {
1598     default: assert(0 && "Unknown class for this function!");
1599     case cByte:
1600       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
1601       return;
1602     case cShort:
1603       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
1604       return;
1605     case cInt:
1606       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
1607       return;
1608     }
1609   }
1610
1611   if (Class == cShort) {
1612     BuildMI(*MBB, IP, X86::IMUL16rri,2,DestReg).addReg(op0Reg).addImm(ConstRHS);
1613     return;
1614   } else if (Class == cInt) {
1615     BuildMI(*MBB, IP, X86::IMUL32rri,2,DestReg).addReg(op0Reg).addImm(ConstRHS);
1616     return;
1617   }
1618
1619   // Most general case, emit a normal multiply...
1620   static const unsigned MOVriTab[] = {
1621     X86::MOV8ri, X86::MOV16ri, X86::MOV32ri
1622   };
1623
1624   unsigned TmpReg = makeAnotherReg(DestTy);
1625   BuildMI(*MBB, IP, MOVriTab[Class], 1, TmpReg).addImm(ConstRHS);
1626
1627   // Emit a MUL to multiply the register holding the index by
1628   // elementSize, putting the result in OffsetReg.
1629   doMultiply(MBB, IP, DestReg, DestTy, op0Reg, TmpReg);
1630 }
1631
1632 /// visitMul - Multiplies are not simple binary operators because they must deal
1633 /// with the EAX register explicitly.
1634 ///
1635 void ISel::visitMul(BinaryOperator &I) {
1636   unsigned Op0Reg  = getReg(I.getOperand(0));
1637   unsigned DestReg = getReg(I);
1638
1639   // Simple scalar multiply?
1640   if (I.getType() != Type::LongTy && I.getType() != Type::ULongTy) {
1641     if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1))) {
1642       unsigned Val = (unsigned)CI->getRawValue(); // Cannot be 64-bit constant
1643       MachineBasicBlock::iterator MBBI = BB->end();
1644       doMultiplyConst(BB, MBBI, DestReg, I.getType(), Op0Reg, Val);
1645     } else {
1646       unsigned Op1Reg  = getReg(I.getOperand(1));
1647       MachineBasicBlock::iterator MBBI = BB->end();
1648       doMultiply(BB, MBBI, DestReg, I.getType(), Op0Reg, Op1Reg);
1649     }
1650   } else {
1651     unsigned Op1Reg  = getReg(I.getOperand(1));
1652
1653     // Long value.  We have to do things the hard way...
1654     // Multiply the two low parts... capturing carry into EDX
1655     BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Op0Reg);
1656     BuildMI(BB, X86::MUL32r, 1).addReg(Op1Reg);  // AL*BL
1657
1658     unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
1659     BuildMI(BB, X86::MOV32rr, 1, DestReg).addReg(X86::EAX);     // AL*BL
1660     BuildMI(BB, X86::MOV32rr, 1, OverflowReg).addReg(X86::EDX); // AL*BL >> 32
1661
1662     MachineBasicBlock::iterator MBBI = BB->end();
1663     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
1664     BuildMI(*BB, MBBI, X86::IMUL32rr,2,AHBLReg).addReg(Op0Reg+1).addReg(Op1Reg);
1665
1666     unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
1667     BuildMI(*BB, MBBI, X86::ADD32rr, 2,                  // AH*BL+(AL*BL >> 32)
1668             AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
1669
1670     MBBI = BB->end();
1671     unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
1672     BuildMI(*BB, MBBI, X86::IMUL32rr,2,ALBHReg).addReg(Op0Reg).addReg(Op1Reg+1);
1673
1674     BuildMI(*BB, MBBI, X86::ADD32rr, 2,         // AL*BH + AH*BL + (AL*BL >> 32)
1675             DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
1676   }
1677 }
1678
1679
1680 /// visitDivRem - Handle division and remainder instructions... these
1681 /// instruction both require the same instructions to be generated, they just
1682 /// select the result from a different register.  Note that both of these
1683 /// instructions work differently for signed and unsigned operands.
1684 ///
1685 void ISel::visitDivRem(BinaryOperator &I) {
1686   unsigned Op0Reg = getReg(I.getOperand(0));
1687   unsigned Op1Reg = getReg(I.getOperand(1));
1688   unsigned ResultReg = getReg(I);
1689
1690   MachineBasicBlock::iterator IP = BB->end();
1691   emitDivRemOperation(BB, IP, Op0Reg, Op1Reg, I.getOpcode() == Instruction::Div,
1692                       I.getType(), ResultReg);
1693 }
1694
1695 void ISel::emitDivRemOperation(MachineBasicBlock *BB,
1696                                MachineBasicBlock::iterator IP,
1697                                unsigned Op0Reg, unsigned Op1Reg, bool isDiv,
1698                                const Type *Ty, unsigned ResultReg) {
1699   unsigned Class = getClass(Ty);
1700   switch (Class) {
1701   case cFP:              // Floating point divide
1702     if (isDiv) {
1703       BuildMI(*BB, IP, X86::FpDIV, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
1704     } else {               // Floating point remainder...
1705       MachineInstr *TheCall =
1706         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
1707       std::vector<ValueRecord> Args;
1708       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
1709       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
1710       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
1711     }
1712     return;
1713   case cLong: {
1714     static const char *FnName[] =
1715       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
1716
1717     unsigned NameIdx = Ty->isUnsigned()*2 + isDiv;
1718     MachineInstr *TheCall =
1719       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
1720
1721     std::vector<ValueRecord> Args;
1722     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
1723     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
1724     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
1725     return;
1726   }
1727   case cByte: case cShort: case cInt:
1728     break;          // Small integrals, handled below...
1729   default: assert(0 && "Unknown class!");
1730   }
1731
1732   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
1733   static const unsigned MovOpcode[]={ X86::MOV8rr, X86::MOV16rr, X86::MOV32rr };
1734   static const unsigned SarOpcode[]={ X86::SAR8ri, X86::SAR16ri, X86::SAR32ri };
1735   static const unsigned ClrOpcode[]={ X86::MOV8ri, X86::MOV16ri, X86::MOV32ri };
1736   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
1737
1738   static const unsigned DivOpcode[][4] = {
1739     { X86::DIV8r , X86::DIV16r , X86::DIV32r , 0 },  // Unsigned division
1740     { X86::IDIV8r, X86::IDIV16r, X86::IDIV32r, 0 },  // Signed division
1741   };
1742
1743   bool isSigned   = Ty->isSigned();
1744   unsigned Reg    = Regs[Class];
1745   unsigned ExtReg = ExtRegs[Class];
1746
1747   // Put the first operand into one of the A registers...
1748   BuildMI(*BB, IP, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
1749
1750   if (isSigned) {
1751     // Emit a sign extension instruction...
1752     unsigned ShiftResult = makeAnotherReg(Ty);
1753     BuildMI(*BB, IP, SarOpcode[Class], 2,ShiftResult).addReg(Op0Reg).addImm(31);
1754     BuildMI(*BB, IP, MovOpcode[Class], 1, ExtReg).addReg(ShiftResult);
1755   } else {
1756     // If unsigned, emit a zeroing instruction... (reg = 0)
1757     BuildMI(*BB, IP, ClrOpcode[Class], 2, ExtReg).addImm(0);
1758   }
1759
1760   // Emit the appropriate divide or remainder instruction...
1761   BuildMI(*BB, IP, DivOpcode[isSigned][Class], 1).addReg(Op1Reg);
1762
1763   // Figure out which register we want to pick the result out of...
1764   unsigned DestReg = isDiv ? Reg : ExtReg;
1765
1766   // Put the result into the destination register...
1767   BuildMI(*BB, IP, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
1768 }
1769
1770
1771 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
1772 /// for constant immediate shift values, and for constant immediate
1773 /// shift values equal to 1. Even the general case is sort of special,
1774 /// because the shift amount has to be in CL, not just any old register.
1775 ///
1776 void ISel::visitShiftInst(ShiftInst &I) {
1777   MachineBasicBlock::iterator IP = BB->end ();
1778   emitShiftOperation (BB, IP, I.getOperand (0), I.getOperand (1),
1779                       I.getOpcode () == Instruction::Shl, I.getType (),
1780                       getReg (I));
1781 }
1782
1783 /// emitShiftOperation - Common code shared between visitShiftInst and
1784 /// constant expression support.
1785 void ISel::emitShiftOperation(MachineBasicBlock *MBB,
1786                               MachineBasicBlock::iterator IP,
1787                               Value *Op, Value *ShiftAmount, bool isLeftShift,
1788                               const Type *ResultTy, unsigned DestReg) {
1789   unsigned SrcReg = getReg (Op, MBB, IP);
1790   bool isSigned = ResultTy->isSigned ();
1791   unsigned Class = getClass (ResultTy);
1792
1793   static const unsigned ConstantOperand[][4] = {
1794     { X86::SHR8ri, X86::SHR16ri, X86::SHR32ri, X86::SHRD32rri8 },  // SHR
1795     { X86::SAR8ri, X86::SAR16ri, X86::SAR32ri, X86::SHRD32rri8 },  // SAR
1796     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SHL
1797     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SAL = SHL
1798   };
1799
1800   static const unsigned NonConstantOperand[][4] = {
1801     { X86::SHR8rCL, X86::SHR16rCL, X86::SHR32rCL },  // SHR
1802     { X86::SAR8rCL, X86::SAR16rCL, X86::SAR32rCL },  // SAR
1803     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SHL
1804     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SAL = SHL
1805   };
1806
1807   // Longs, as usual, are handled specially...
1808   if (Class == cLong) {
1809     // If we have a constant shift, we can generate much more efficient code
1810     // than otherwise...
1811     //
1812     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
1813       unsigned Amount = CUI->getValue();
1814       if (Amount < 32) {
1815         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1816         if (isLeftShift) {
1817           BuildMI(*MBB, IP, Opc[3], 3,
1818               DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addImm(Amount);
1819           BuildMI(*MBB, IP, Opc[2], 2, DestReg).addReg(SrcReg).addImm(Amount);
1820         } else {
1821           BuildMI(*MBB, IP, Opc[3], 3,
1822               DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addImm(Amount);
1823           BuildMI(*MBB, IP, Opc[2],2,DestReg+1).addReg(SrcReg+1).addImm(Amount);
1824         }
1825       } else {                 // Shifting more than 32 bits
1826         Amount -= 32;
1827         if (isLeftShift) {
1828           BuildMI(*MBB, IP, X86::SHL32ri, 2,
1829               DestReg + 1).addReg(SrcReg).addImm(Amount);
1830           BuildMI(*MBB, IP, X86::MOV32ri, 1,
1831               DestReg).addImm(0);
1832         } else {
1833           unsigned Opcode = isSigned ? X86::SAR32ri : X86::SHR32ri;
1834           BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(SrcReg+1).addImm(Amount);
1835           BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
1836         }
1837       }
1838     } else {
1839       unsigned TmpReg = makeAnotherReg(Type::IntTy);
1840
1841       if (!isLeftShift && isSigned) {
1842         // If this is a SHR of a Long, then we need to do funny sign extension
1843         // stuff.  TmpReg gets the value to use as the high-part if we are
1844         // shifting more than 32 bits.
1845         BuildMI(*MBB, IP, X86::SAR32ri, 2, TmpReg).addReg(SrcReg).addImm(31);
1846       } else {
1847         // Other shifts use a fixed zero value if the shift is more than 32
1848         // bits.
1849         BuildMI(*MBB, IP, X86::MOV32ri, 1, TmpReg).addImm(0);
1850       }
1851
1852       // Initialize CL with the shift amount...
1853       unsigned ShiftAmountReg = getReg(ShiftAmount, MBB, IP);
1854       BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
1855
1856       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
1857       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
1858       if (isLeftShift) {
1859         // TmpReg2 = shld inHi, inLo
1860         BuildMI(*MBB, IP, X86::SHLD32rrCL,2,TmpReg2).addReg(SrcReg+1)
1861                                                     .addReg(SrcReg);
1862         // TmpReg3 = shl  inLo, CL
1863         BuildMI(*MBB, IP, X86::SHL32rCL, 1, TmpReg3).addReg(SrcReg);
1864
1865         // Set the flags to indicate whether the shift was by more than 32 bits.
1866         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
1867
1868         // DestHi = (>32) ? TmpReg3 : TmpReg2;
1869         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1870                 DestReg+1).addReg(TmpReg2).addReg(TmpReg3);
1871         // DestLo = (>32) ? TmpReg : TmpReg3;
1872         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1873             DestReg).addReg(TmpReg3).addReg(TmpReg);
1874       } else {
1875         // TmpReg2 = shrd inLo, inHi
1876         BuildMI(*MBB, IP, X86::SHRD32rrCL,2,TmpReg2).addReg(SrcReg)
1877                                                     .addReg(SrcReg+1);
1878         // TmpReg3 = s[ah]r  inHi, CL
1879         BuildMI(*MBB, IP, isSigned ? X86::SAR32rCL : X86::SHR32rCL, 1, TmpReg3)
1880                        .addReg(SrcReg+1);
1881
1882         // Set the flags to indicate whether the shift was by more than 32 bits.
1883         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
1884
1885         // DestLo = (>32) ? TmpReg3 : TmpReg2;
1886         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1887                 DestReg).addReg(TmpReg2).addReg(TmpReg3);
1888
1889         // DestHi = (>32) ? TmpReg : TmpReg3;
1890         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1891                 DestReg+1).addReg(TmpReg3).addReg(TmpReg);
1892       }
1893     }
1894     return;
1895   }
1896
1897   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
1898     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
1899     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
1900
1901     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1902     BuildMI(*MBB, IP, Opc[Class], 2,
1903         DestReg).addReg(SrcReg).addImm(CUI->getValue());
1904   } else {                  // The shift amount is non-constant.
1905     unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
1906     BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
1907
1908     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
1909     BuildMI(*MBB, IP, Opc[Class], 1, DestReg).addReg(SrcReg);
1910   }
1911 }
1912
1913
1914 void ISel::getAddressingMode(Value *Addr, unsigned &BaseReg, unsigned &Scale,
1915                              unsigned &IndexReg, unsigned &Disp) {
1916   BaseReg = 0; Scale = 1; IndexReg = 0; Disp = 0;
1917   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) {
1918     if (isGEPFoldable(BB, GEP->getOperand(0), GEP->op_begin()+1, GEP->op_end(),
1919                        BaseReg, Scale, IndexReg, Disp))
1920       return;
1921   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
1922     if (CE->getOpcode() == Instruction::GetElementPtr)
1923       if (isGEPFoldable(BB, CE->getOperand(0), CE->op_begin()+1, CE->op_end(),
1924                         BaseReg, Scale, IndexReg, Disp))
1925         return;
1926   }
1927
1928   // If it's not foldable, reset addr mode.
1929   BaseReg = getReg(Addr);
1930   Scale = 1; IndexReg = 0; Disp = 0;
1931 }
1932
1933
1934 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
1935 /// instruction.  The load and store instructions are the only place where we
1936 /// need to worry about the memory layout of the target machine.
1937 ///
1938 void ISel::visitLoadInst(LoadInst &I) {
1939   unsigned DestReg = getReg(I);
1940   unsigned BaseReg = 0, Scale = 1, IndexReg = 0, Disp = 0;
1941   getAddressingMode(I.getOperand(0), BaseReg, Scale, IndexReg, Disp);
1942
1943   unsigned Class = getClassB(I.getType());
1944   if (Class == cLong) {
1945     addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg),
1946                    BaseReg, Scale, IndexReg, Disp);
1947     addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg+1),
1948                    BaseReg, Scale, IndexReg, Disp+4);
1949     return;
1950   }
1951
1952   static const unsigned Opcodes[] = {
1953     X86::MOV8rm, X86::MOV16rm, X86::MOV32rm, X86::FLD32m
1954   };
1955   unsigned Opcode = Opcodes[Class];
1956   if (I.getType() == Type::DoubleTy) Opcode = X86::FLD64m;
1957   addFullAddress(BuildMI(BB, Opcode, 4, DestReg),
1958                  BaseReg, Scale, IndexReg, Disp);
1959 }
1960
1961 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
1962 /// instruction.
1963 ///
1964 void ISel::visitStoreInst(StoreInst &I) {
1965   unsigned BaseReg, Scale, IndexReg, Disp;
1966   getAddressingMode(I.getOperand(1), BaseReg, Scale, IndexReg, Disp);
1967
1968   const Type *ValTy = I.getOperand(0)->getType();
1969   unsigned Class = getClassB(ValTy);
1970
1971   if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(0))) {
1972     uint64_t Val = CI->getRawValue();
1973     if (Class == cLong) {
1974       addFullAddress(BuildMI(BB, X86::MOV32mi, 5),
1975                      BaseReg, Scale, IndexReg, Disp).addImm(Val & ~0U);
1976       addFullAddress(BuildMI(BB, X86::MOV32mi, 5),
1977                      BaseReg, Scale, IndexReg, Disp+4).addImm(Val>>32);
1978     } else {
1979       static const unsigned Opcodes[] = {
1980         X86::MOV8mi, X86::MOV16mi, X86::MOV32mi
1981       };
1982       unsigned Opcode = Opcodes[Class];
1983       addFullAddress(BuildMI(BB, Opcode, 5),
1984                      BaseReg, Scale, IndexReg, Disp).addImm(Val);
1985     }
1986   } else if (ConstantBool *CB = dyn_cast<ConstantBool>(I.getOperand(0))) {
1987     addFullAddress(BuildMI(BB, X86::MOV8mi, 5),
1988                    BaseReg, Scale, IndexReg, Disp).addImm(CB->getValue());
1989   } else {
1990     if (Class == cLong) {
1991       unsigned ValReg = getReg(I.getOperand(0));
1992       addFullAddress(BuildMI(BB, X86::MOV32mr, 5),
1993                      BaseReg, Scale, IndexReg, Disp).addReg(ValReg);
1994       addFullAddress(BuildMI(BB, X86::MOV32mr, 5),
1995                      BaseReg, Scale, IndexReg, Disp+4).addReg(ValReg+1);
1996     } else {
1997       unsigned ValReg = getReg(I.getOperand(0));
1998       static const unsigned Opcodes[] = {
1999         X86::MOV8mr, X86::MOV16mr, X86::MOV32mr, X86::FST32m
2000       };
2001       unsigned Opcode = Opcodes[Class];
2002       if (ValTy == Type::DoubleTy) Opcode = X86::FST64m;
2003       addFullAddress(BuildMI(BB, Opcode, 1+4),
2004                      BaseReg, Scale, IndexReg, Disp).addReg(ValReg);
2005     }
2006   }
2007 }
2008
2009
2010 /// visitCastInst - Here we have various kinds of copying with or without sign
2011 /// extension going on.
2012 ///
2013 void ISel::visitCastInst(CastInst &CI) {
2014   Value *Op = CI.getOperand(0);
2015   // If this is a cast from a 32-bit integer to a Long type, and the only uses
2016   // of the case are GEP instructions, then the cast does not need to be
2017   // generated explicitly, it will be folded into the GEP.
2018   if (CI.getType() == Type::LongTy &&
2019       (Op->getType() == Type::IntTy || Op->getType() == Type::UIntTy)) {
2020     bool AllUsesAreGEPs = true;
2021     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
2022       if (!isa<GetElementPtrInst>(*I)) {
2023         AllUsesAreGEPs = false;
2024         break;
2025       }
2026
2027     // No need to codegen this cast if all users are getelementptr instrs...
2028     if (AllUsesAreGEPs) return;
2029   }
2030
2031   unsigned DestReg = getReg(CI);
2032   MachineBasicBlock::iterator MI = BB->end();
2033   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
2034 }
2035
2036 /// emitCastOperation - Common code shared between visitCastInst and constant
2037 /// expression cast support.
2038 ///
2039 void ISel::emitCastOperation(MachineBasicBlock *BB,
2040                              MachineBasicBlock::iterator IP,
2041                              Value *Src, const Type *DestTy,
2042                              unsigned DestReg) {
2043   unsigned SrcReg = getReg(Src, BB, IP);
2044   const Type *SrcTy = Src->getType();
2045   unsigned SrcClass = getClassB(SrcTy);
2046   unsigned DestClass = getClassB(DestTy);
2047
2048   // Implement casts to bool by using compare on the operand followed by set if
2049   // not zero on the result.
2050   if (DestTy == Type::BoolTy) {
2051     switch (SrcClass) {
2052     case cByte:
2053       BuildMI(*BB, IP, X86::TEST8rr, 2).addReg(SrcReg).addReg(SrcReg);
2054       break;
2055     case cShort:
2056       BuildMI(*BB, IP, X86::TEST16rr, 2).addReg(SrcReg).addReg(SrcReg);
2057       break;
2058     case cInt:
2059       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg).addReg(SrcReg);
2060       break;
2061     case cLong: {
2062       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2063       BuildMI(*BB, IP, X86::OR32rr, 2, TmpReg).addReg(SrcReg).addReg(SrcReg+1);
2064       break;
2065     }
2066     case cFP:
2067       BuildMI(*BB, IP, X86::FTST, 1).addReg(SrcReg);
2068       BuildMI(*BB, IP, X86::FNSTSW8r, 0);
2069       BuildMI(*BB, IP, X86::SAHF, 1);
2070       break;
2071     }
2072
2073     // If the zero flag is not set, then the value is true, set the byte to
2074     // true.
2075     BuildMI(*BB, IP, X86::SETNEr, 1, DestReg);
2076     return;
2077   }
2078
2079   static const unsigned RegRegMove[] = {
2080     X86::MOV8rr, X86::MOV16rr, X86::MOV32rr, X86::FpMOV, X86::MOV32rr
2081   };
2082
2083   // Implement casts between values of the same type class (as determined by
2084   // getClass) by using a register-to-register move.
2085   if (SrcClass == DestClass) {
2086     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
2087       BuildMI(*BB, IP, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
2088     } else if (SrcClass == cFP) {
2089       if (SrcTy == Type::FloatTy) {  // double -> float
2090         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
2091         BuildMI(*BB, IP, X86::FpMOV, 1, DestReg).addReg(SrcReg);
2092       } else {                       // float -> double
2093         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
2094                "Unknown cFP member!");
2095         // Truncate from double to float by storing to memory as short, then
2096         // reading it back.
2097         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
2098         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
2099         addFrameReference(BuildMI(*BB, IP, X86::FST32m, 5), FrameIdx).addReg(SrcReg);
2100         addFrameReference(BuildMI(*BB, IP, X86::FLD32m, 5, DestReg), FrameIdx);
2101       }
2102     } else if (SrcClass == cLong) {
2103       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
2104       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg+1).addReg(SrcReg+1);
2105     } else {
2106       assert(0 && "Cannot handle this type of cast instruction!");
2107       abort();
2108     }
2109     return;
2110   }
2111
2112   // Handle cast of SMALLER int to LARGER int using a move with sign extension
2113   // or zero extension, depending on whether the source type was signed.
2114   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
2115       SrcClass < DestClass) {
2116     bool isLong = DestClass == cLong;
2117     if (isLong) DestClass = cInt;
2118
2119     static const unsigned Opc[][4] = {
2120       { X86::MOVSX16rr8, X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOV32rr }, // s
2121       { X86::MOVZX16rr8, X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOV32rr }  // u
2122     };
2123
2124     bool isUnsigned = SrcTy->isUnsigned();
2125     BuildMI(*BB, IP, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
2126         DestReg).addReg(SrcReg);
2127
2128     if (isLong) {  // Handle upper 32 bits as appropriate...
2129       if (isUnsigned)     // Zero out top bits...
2130         BuildMI(*BB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
2131       else                // Sign extend bottom half...
2132         BuildMI(*BB, IP, X86::SAR32ri, 2, DestReg+1).addReg(DestReg).addImm(31);
2133     }
2134     return;
2135   }
2136
2137   // Special case long -> int ...
2138   if (SrcClass == cLong && DestClass == cInt) {
2139     BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
2140     return;
2141   }
2142
2143   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
2144   // move out of AX or AL.
2145   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
2146       && SrcClass > DestClass) {
2147     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
2148     BuildMI(*BB, IP, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
2149     BuildMI(*BB, IP, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
2150     return;
2151   }
2152
2153   // Handle casts from integer to floating point now...
2154   if (DestClass == cFP) {
2155     // Promote the integer to a type supported by FLD.  We do this because there
2156     // are no unsigned FLD instructions, so we must promote an unsigned value to
2157     // a larger signed value, then use FLD on the larger value.
2158     //
2159     const Type *PromoteType = 0;
2160     unsigned PromoteOpcode;
2161     unsigned RealDestReg = DestReg;
2162     switch (SrcTy->getPrimitiveID()) {
2163     case Type::BoolTyID:
2164     case Type::SByteTyID:
2165       // We don't have the facilities for directly loading byte sized data from
2166       // memory (even signed).  Promote it to 16 bits.
2167       PromoteType = Type::ShortTy;
2168       PromoteOpcode = X86::MOVSX16rr8;
2169       break;
2170     case Type::UByteTyID:
2171       PromoteType = Type::ShortTy;
2172       PromoteOpcode = X86::MOVZX16rr8;
2173       break;
2174     case Type::UShortTyID:
2175       PromoteType = Type::IntTy;
2176       PromoteOpcode = X86::MOVZX32rr16;
2177       break;
2178     case Type::UIntTyID: {
2179       // Make a 64 bit temporary... and zero out the top of it...
2180       unsigned TmpReg = makeAnotherReg(Type::LongTy);
2181       BuildMI(*BB, IP, X86::MOV32rr, 1, TmpReg).addReg(SrcReg);
2182       BuildMI(*BB, IP, X86::MOV32ri, 1, TmpReg+1).addImm(0);
2183       SrcTy = Type::LongTy;
2184       SrcClass = cLong;
2185       SrcReg = TmpReg;
2186       break;
2187     }
2188     case Type::ULongTyID:
2189       // Don't fild into the read destination.
2190       DestReg = makeAnotherReg(Type::DoubleTy);
2191       break;
2192     default:  // No promotion needed...
2193       break;
2194     }
2195
2196     if (PromoteType) {
2197       unsigned TmpReg = makeAnotherReg(PromoteType);
2198       unsigned Opc = SrcTy->isSigned() ? X86::MOVSX16rr8 : X86::MOVZX16rr8;
2199       BuildMI(*BB, IP, Opc, 1, TmpReg).addReg(SrcReg);
2200       SrcTy = PromoteType;
2201       SrcClass = getClass(PromoteType);
2202       SrcReg = TmpReg;
2203     }
2204
2205     // Spill the integer to memory and reload it from there...
2206     int FrameIdx =
2207       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
2208
2209     if (SrcClass == cLong) {
2210       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
2211                         FrameIdx).addReg(SrcReg);
2212       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
2213                         FrameIdx, 4).addReg(SrcReg+1);
2214     } else {
2215       static const unsigned Op1[] = { X86::MOV8mr, X86::MOV16mr, X86::MOV32mr };
2216       addFrameReference(BuildMI(*BB, IP, Op1[SrcClass], 5),
2217                         FrameIdx).addReg(SrcReg);
2218     }
2219
2220     static const unsigned Op2[] =
2221       { 0/*byte*/, X86::FILD16m, X86::FILD32m, 0/*FP*/, X86::FILD64m };
2222     addFrameReference(BuildMI(*BB, IP, Op2[SrcClass], 5, DestReg), FrameIdx);
2223
2224     // We need special handling for unsigned 64-bit integer sources.  If the
2225     // input number has the "sign bit" set, then we loaded it incorrectly as a
2226     // negative 64-bit number.  In this case, add an offset value.
2227     if (SrcTy == Type::ULongTy) {
2228       // Emit a test instruction to see if the dynamic input value was signed.
2229       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg+1).addReg(SrcReg+1);
2230
2231       // If the sign bit is set, get a pointer to an offset, otherwise get a
2232       // pointer to a zero.
2233       MachineConstantPool *CP = F->getConstantPool();
2234       unsigned Zero = makeAnotherReg(Type::IntTy);
2235       Constant *Null = Constant::getNullValue(Type::UIntTy);
2236       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Zero),
2237                                CP->getConstantPoolIndex(Null));
2238       unsigned Offset = makeAnotherReg(Type::IntTy);
2239       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
2240
2241       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Offset),
2242                                CP->getConstantPoolIndex(OffsetCst));
2243       unsigned Addr = makeAnotherReg(Type::IntTy);
2244       BuildMI(*BB, IP, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
2245
2246       // Load the constant for an add.  FIXME: this could make an 'fadd' that
2247       // reads directly from memory, but we don't support these yet.
2248       unsigned ConstReg = makeAnotherReg(Type::DoubleTy);
2249       addDirectMem(BuildMI(*BB, IP, X86::FLD32m, 4, ConstReg), Addr);
2250
2251       BuildMI(*BB, IP, X86::FpADD, 2, RealDestReg)
2252                 .addReg(ConstReg).addReg(DestReg);
2253     }
2254
2255     return;
2256   }
2257
2258   // Handle casts from floating point to integer now...
2259   if (SrcClass == cFP) {
2260     // Change the floating point control register to use "round towards zero"
2261     // mode when truncating to an integer value.
2262     //
2263     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
2264     addFrameReference(BuildMI(*BB, IP, X86::FNSTCW16m, 4), CWFrameIdx);
2265
2266     // Load the old value of the high byte of the control word...
2267     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
2268     addFrameReference(BuildMI(*BB, IP, X86::MOV8rm, 4, HighPartOfCW),
2269                       CWFrameIdx, 1);
2270
2271     // Set the high part to be round to zero...
2272     addFrameReference(BuildMI(*BB, IP, X86::MOV8mi, 5),
2273                       CWFrameIdx, 1).addImm(12);
2274
2275     // Reload the modified control word now...
2276     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
2277
2278     // Restore the memory image of control word to original value
2279     addFrameReference(BuildMI(*BB, IP, X86::MOV8mr, 5),
2280                       CWFrameIdx, 1).addReg(HighPartOfCW);
2281
2282     // We don't have the facilities for directly storing byte sized data to
2283     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
2284     // larger classes because we only have signed FP stores.
2285     unsigned StoreClass  = DestClass;
2286     const Type *StoreTy  = DestTy;
2287     if (StoreClass == cByte || DestTy->isUnsigned())
2288       switch (StoreClass) {
2289       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
2290       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
2291       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
2292       // The following treatment of cLong may not be perfectly right,
2293       // but it survives chains of casts of the form
2294       // double->ulong->double.
2295       case cLong:  StoreTy = Type::LongTy;  StoreClass = cLong;  break;
2296       default: assert(0 && "Unknown store class!");
2297       }
2298
2299     // Spill the integer to memory and reload it from there...
2300     int FrameIdx =
2301       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
2302
2303     static const unsigned Op1[] =
2304       { 0, X86::FIST16m, X86::FIST32m, 0, X86::FISTP64m };
2305     addFrameReference(BuildMI(*BB, IP, Op1[StoreClass], 5),
2306                       FrameIdx).addReg(SrcReg);
2307
2308     if (DestClass == cLong) {
2309       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg), FrameIdx);
2310       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg+1),
2311                         FrameIdx, 4);
2312     } else {
2313       static const unsigned Op2[] = { X86::MOV8rm, X86::MOV16rm, X86::MOV32rm };
2314       addFrameReference(BuildMI(*BB, IP, Op2[DestClass], 4, DestReg), FrameIdx);
2315     }
2316
2317     // Reload the original control word now...
2318     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
2319     return;
2320   }
2321
2322   // Anything we haven't handled already, we can't (yet) handle at all.
2323   assert(0 && "Unhandled cast instruction!");
2324   abort();
2325 }
2326
2327 /// visitVANextInst - Implement the va_next instruction...
2328 ///
2329 void ISel::visitVANextInst(VANextInst &I) {
2330   unsigned VAList = getReg(I.getOperand(0));
2331   unsigned DestReg = getReg(I);
2332
2333   unsigned Size;
2334   switch (I.getArgType()->getPrimitiveID()) {
2335   default:
2336     std::cerr << I;
2337     assert(0 && "Error: bad type for va_next instruction!");
2338     return;
2339   case Type::PointerTyID:
2340   case Type::UIntTyID:
2341   case Type::IntTyID:
2342     Size = 4;
2343     break;
2344   case Type::ULongTyID:
2345   case Type::LongTyID:
2346   case Type::DoubleTyID:
2347     Size = 8;
2348     break;
2349   }
2350
2351   // Increment the VAList pointer...
2352   BuildMI(BB, X86::ADD32ri, 2, DestReg).addReg(VAList).addImm(Size);
2353 }
2354
2355 void ISel::visitVAArgInst(VAArgInst &I) {
2356   unsigned VAList = getReg(I.getOperand(0));
2357   unsigned DestReg = getReg(I);
2358
2359   switch (I.getType()->getPrimitiveID()) {
2360   default:
2361     std::cerr << I;
2362     assert(0 && "Error: bad type for va_next instruction!");
2363     return;
2364   case Type::PointerTyID:
2365   case Type::UIntTyID:
2366   case Type::IntTyID:
2367     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
2368     break;
2369   case Type::ULongTyID:
2370   case Type::LongTyID:
2371     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
2372     addRegOffset(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), VAList, 4);
2373     break;
2374   case Type::DoubleTyID:
2375     addDirectMem(BuildMI(BB, X86::FLD64m, 4, DestReg), VAList);
2376     break;
2377   }
2378 }
2379
2380 /// visitGetElementPtrInst - instruction-select GEP instructions
2381 ///
2382 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
2383   // If this GEP instruction will be folded into all of its users, we don't need
2384   // to explicitly calculate it!
2385   unsigned A, B, C, D;
2386   if (isGEPFoldable(0, I.getOperand(0), I.op_begin()+1, I.op_end(), A,B,C,D)) {
2387     // Check all of the users of the instruction to see if they are loads and
2388     // stores.
2389     bool AllWillFold = true;
2390     for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI)
2391       if (cast<Instruction>(*UI)->getOpcode() != Instruction::Load)
2392         if (cast<Instruction>(*UI)->getOpcode() != Instruction::Store ||
2393             cast<Instruction>(*UI)->getOperand(0) == &I) {
2394           AllWillFold = false;
2395           break;
2396         }
2397
2398     // If the instruction is foldable, and will be folded into all users, don't
2399     // emit it!
2400     if (AllWillFold) return;
2401   }
2402
2403   unsigned outputReg = getReg(I);
2404   emitGEPOperation(BB, BB->end(), I.getOperand(0),
2405                    I.op_begin()+1, I.op_end(), outputReg);
2406 }
2407
2408 /// getGEPIndex - Inspect the getelementptr operands specified with GEPOps and
2409 /// GEPTypes (the derived types being stepped through at each level).  On return
2410 /// from this function, if some indexes of the instruction are representable as
2411 /// an X86 lea instruction, the machine operands are put into the Ops
2412 /// instruction and the consumed indexes are poped from the GEPOps/GEPTypes
2413 /// lists.  Otherwise, GEPOps.size() is returned.  If this returns a an
2414 /// addressing mode that only partially consumes the input, the BaseReg input of
2415 /// the addressing mode must be left free.
2416 ///
2417 /// Note that there is one fewer entry in GEPTypes than there is in GEPOps.
2418 ///
2419 void ISel::getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
2420                        std::vector<Value*> &GEPOps,
2421                        std::vector<const Type*> &GEPTypes, unsigned &BaseReg,
2422                        unsigned &Scale, unsigned &IndexReg, unsigned &Disp) {
2423   const TargetData &TD = TM.getTargetData();
2424
2425   // Clear out the state we are working with...
2426   BaseReg = 0;    // No base register
2427   Scale = 1;      // Unit scale
2428   IndexReg = 0;   // No index register
2429   Disp = 0;       // No displacement
2430
2431   // While there are GEP indexes that can be folded into the current address,
2432   // keep processing them.
2433   while (!GEPTypes.empty()) {
2434     if (const StructType *StTy = dyn_cast<StructType>(GEPTypes.back())) {
2435       // It's a struct access.  CUI is the index into the structure,
2436       // which names the field. This index must have unsigned type.
2437       const ConstantUInt *CUI = cast<ConstantUInt>(GEPOps.back());
2438
2439       // Use the TargetData structure to pick out what the layout of the
2440       // structure is in memory.  Since the structure index must be constant, we
2441       // can get its value and use it to find the right byte offset from the
2442       // StructLayout class's list of structure member offsets.
2443       Disp += TD.getStructLayout(StTy)->MemberOffsets[CUI->getValue()];
2444       GEPOps.pop_back();        // Consume a GEP operand
2445       GEPTypes.pop_back();
2446     } else {
2447       // It's an array or pointer access: [ArraySize x ElementType].
2448       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
2449       Value *idx = GEPOps.back();
2450
2451       // idx is the index into the array.  Unlike with structure
2452       // indices, we may not know its actual value at code-generation
2453       // time.
2454       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
2455
2456       // If idx is a constant, fold it into the offset.
2457       unsigned TypeSize = TD.getTypeSize(SqTy->getElementType());
2458       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
2459         Disp += TypeSize*CSI->getValue();
2460       } else {
2461         // If the index reg is already taken, we can't handle this index.
2462         if (IndexReg) return;
2463
2464         // If this is a size that we can handle, then add the index as
2465         switch (TypeSize) {
2466         case 1: case 2: case 4: case 8:
2467           // These are all acceptable scales on X86.
2468           Scale = TypeSize;
2469           break;
2470         default:
2471           // Otherwise, we can't handle this scale
2472           return;
2473         }
2474
2475         if (CastInst *CI = dyn_cast<CastInst>(idx))
2476           if (CI->getOperand(0)->getType() == Type::IntTy ||
2477               CI->getOperand(0)->getType() == Type::UIntTy)
2478             idx = CI->getOperand(0);
2479
2480         IndexReg = MBB ? getReg(idx, MBB, IP) : 1;
2481       }
2482
2483       GEPOps.pop_back();        // Consume a GEP operand
2484       GEPTypes.pop_back();
2485     }
2486   }
2487
2488   // GEPTypes is empty, which means we have a single operand left.  See if we
2489   // can set it as the base register.
2490   //
2491   // FIXME: When addressing modes are more powerful/correct, we could load
2492   // global addresses directly as 32-bit immediates.
2493   assert(BaseReg == 0);
2494   BaseReg = MBB ? getReg(GEPOps[0], MBB, IP) : 1;
2495   GEPOps.pop_back();        // Consume the last GEP operand
2496 }
2497
2498
2499 /// isGEPFoldable - Return true if the specified GEP can be completely
2500 /// folded into the addressing mode of a load/store or lea instruction.
2501 bool ISel::isGEPFoldable(MachineBasicBlock *MBB,
2502                          Value *Src, User::op_iterator IdxBegin,
2503                          User::op_iterator IdxEnd, unsigned &BaseReg,
2504                          unsigned &Scale, unsigned &IndexReg, unsigned &Disp) {
2505   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Src))
2506     Src = CPR->getValue();
2507
2508   std::vector<Value*> GEPOps;
2509   GEPOps.resize(IdxEnd-IdxBegin+1);
2510   GEPOps[0] = Src;
2511   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
2512
2513   std::vector<const Type*> GEPTypes;
2514   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
2515                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
2516
2517   MachineBasicBlock::iterator IP;
2518   if (MBB) IP = MBB->end();
2519   getGEPIndex(MBB, IP, GEPOps, GEPTypes, BaseReg, Scale, IndexReg, Disp);
2520
2521   // We can fold it away iff the getGEPIndex call eliminated all operands.
2522   return GEPOps.empty();
2523 }
2524
2525 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
2526                             MachineBasicBlock::iterator IP,
2527                             Value *Src, User::op_iterator IdxBegin,
2528                             User::op_iterator IdxEnd, unsigned TargetReg) {
2529   const TargetData &TD = TM.getTargetData();
2530   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Src))
2531     Src = CPR->getValue();
2532
2533   std::vector<Value*> GEPOps;
2534   GEPOps.resize(IdxEnd-IdxBegin+1);
2535   GEPOps[0] = Src;
2536   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
2537
2538   std::vector<const Type*> GEPTypes;
2539   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
2540                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
2541
2542   // Keep emitting instructions until we consume the entire GEP instruction.
2543   while (!GEPOps.empty()) {
2544     unsigned OldSize = GEPOps.size();
2545     unsigned BaseReg, Scale, IndexReg, Disp;
2546     getGEPIndex(MBB, IP, GEPOps, GEPTypes, BaseReg, Scale, IndexReg, Disp);
2547
2548     if (GEPOps.size() != OldSize) {
2549       // getGEPIndex consumed some of the input.  Build an LEA instruction here.
2550       unsigned NextTarget = 0;
2551       if (!GEPOps.empty()) {
2552         assert(BaseReg == 0 &&
2553            "getGEPIndex should have left the base register open for chaining!");
2554         NextTarget = BaseReg = makeAnotherReg(Type::UIntTy);
2555       }
2556
2557       if (IndexReg == 0 && Disp == 0)
2558         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(BaseReg);
2559       else
2560         addFullAddress(BuildMI(*MBB, IP, X86::LEA32r, 5, TargetReg),
2561                        BaseReg, Scale, IndexReg, Disp);
2562       --IP;
2563       TargetReg = NextTarget;
2564     } else if (GEPTypes.empty()) {
2565       // The getGEPIndex operation didn't want to build an LEA.  Check to see if
2566       // all operands are consumed but the base pointer.  If so, just load it
2567       // into the register.
2568       if (GlobalValue *GV = dyn_cast<GlobalValue>(GEPOps[0])) {
2569         BuildMI(*MBB, IP, X86::MOV32ri, 1, TargetReg).addGlobalAddress(GV);
2570       } else {
2571         unsigned BaseReg = getReg(GEPOps[0], MBB, IP);
2572         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(BaseReg);
2573       }
2574       break;                // we are now done
2575
2576     } else {
2577       // It's an array or pointer access: [ArraySize x ElementType].
2578       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
2579       Value *idx = GEPOps.back();
2580       GEPOps.pop_back();        // Consume a GEP operand
2581       GEPTypes.pop_back();
2582
2583       // idx is the index into the array.  Unlike with structure
2584       // indices, we may not know its actual value at code-generation
2585       // time.
2586       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
2587
2588       // Most GEP instructions use a [cast (int/uint) to LongTy] as their
2589       // operand on X86.  Handle this case directly now...
2590       if (CastInst *CI = dyn_cast<CastInst>(idx))
2591         if (CI->getOperand(0)->getType() == Type::IntTy ||
2592             CI->getOperand(0)->getType() == Type::UIntTy)
2593           idx = CI->getOperand(0);
2594
2595       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
2596       // must find the size of the pointed-to type (Not coincidentally, the next
2597       // type is the type of the elements in the array).
2598       const Type *ElTy = SqTy->getElementType();
2599       unsigned elementSize = TD.getTypeSize(ElTy);
2600
2601       // If idxReg is a constant, we don't need to perform the multiply!
2602       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
2603         if (!CSI->isNullValue()) {
2604           unsigned Offset = elementSize*CSI->getValue();
2605           unsigned Reg = makeAnotherReg(Type::UIntTy);
2606           BuildMI(*MBB, IP, X86::ADD32ri, 2, TargetReg)
2607                                 .addReg(Reg).addImm(Offset);
2608           --IP;            // Insert the next instruction before this one.
2609           TargetReg = Reg; // Codegen the rest of the GEP into this
2610         }
2611       } else if (elementSize == 1) {
2612         // If the element size is 1, we don't have to multiply, just add
2613         unsigned idxReg = getReg(idx, MBB, IP);
2614         unsigned Reg = makeAnotherReg(Type::UIntTy);
2615         BuildMI(*MBB, IP, X86::ADD32rr, 2,TargetReg).addReg(Reg).addReg(idxReg);
2616         --IP;            // Insert the next instruction before this one.
2617         TargetReg = Reg; // Codegen the rest of the GEP into this
2618       } else {
2619         unsigned idxReg = getReg(idx, MBB, IP);
2620         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
2621
2622         // Make sure we can back the iterator up to point to the first
2623         // instruction emitted.
2624         MachineBasicBlock::iterator BeforeIt = IP;
2625         if (IP == MBB->begin())
2626           BeforeIt = MBB->end();
2627         else
2628           --BeforeIt;
2629         doMultiplyConst(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSize);
2630
2631         // Emit an ADD to add OffsetReg to the basePtr.
2632         unsigned Reg = makeAnotherReg(Type::UIntTy);
2633         BuildMI(*MBB, IP, X86::ADD32rr, 2, TargetReg)
2634                           .addReg(Reg).addReg(OffsetReg);
2635
2636         // Step to the first instruction of the multiply.
2637         if (BeforeIt == MBB->end())
2638           IP = MBB->begin();
2639         else
2640           IP = ++BeforeIt;
2641
2642         TargetReg = Reg; // Codegen the rest of the GEP into this
2643       }
2644     }
2645   }
2646 }
2647
2648
2649 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
2650 /// frame manager, otherwise do it the hard way.
2651 ///
2652 void ISel::visitAllocaInst(AllocaInst &I) {
2653   // Find the data size of the alloca inst's getAllocatedType.
2654   const Type *Ty = I.getAllocatedType();
2655   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
2656
2657   // If this is a fixed size alloca in the entry block for the function,
2658   // statically stack allocate the space.
2659   //
2660   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getArraySize())) {
2661     if (I.getParent() == I.getParent()->getParent()->begin()) {
2662       TySize *= CUI->getValue();   // Get total allocated size...
2663       unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
2664
2665       // Create a new stack object using the frame manager...
2666       int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
2667       addFrameReference(BuildMI(BB, X86::LEA32r, 5, getReg(I)), FrameIdx);
2668       return;
2669     }
2670   }
2671
2672   // Create a register to hold the temporary result of multiplying the type size
2673   // constant by the variable amount.
2674   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
2675   unsigned SrcReg1 = getReg(I.getArraySize());
2676
2677   // TotalSizeReg = mul <numelements>, <TypeSize>
2678   MachineBasicBlock::iterator MBBI = BB->end();
2679   doMultiplyConst(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, TySize);
2680
2681   // AddedSize = add <TotalSizeReg>, 15
2682   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
2683   BuildMI(BB, X86::ADD32ri, 2, AddedSizeReg).addReg(TotalSizeReg).addImm(15);
2684
2685   // AlignedSize = and <AddedSize>, ~15
2686   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
2687   BuildMI(BB, X86::AND32ri, 2, AlignedSize).addReg(AddedSizeReg).addImm(~15);
2688
2689   // Subtract size from stack pointer, thereby allocating some space.
2690   BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
2691
2692   // Put a pointer to the space into the result register, by copying
2693   // the stack pointer.
2694   BuildMI(BB, X86::MOV32rr, 1, getReg(I)).addReg(X86::ESP);
2695
2696   // Inform the Frame Information that we have just allocated a variable-sized
2697   // object.
2698   F->getFrameInfo()->CreateVariableSizedObject();
2699 }
2700
2701 /// visitMallocInst - Malloc instructions are code generated into direct calls
2702 /// to the library malloc.
2703 ///
2704 void ISel::visitMallocInst(MallocInst &I) {
2705   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
2706   unsigned Arg;
2707
2708   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
2709     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
2710   } else {
2711     Arg = makeAnotherReg(Type::UIntTy);
2712     unsigned Op0Reg = getReg(I.getOperand(0));
2713     MachineBasicBlock::iterator MBBI = BB->end();
2714     doMultiplyConst(BB, MBBI, Arg, Type::UIntTy, Op0Reg, AllocSize);
2715   }
2716
2717   std::vector<ValueRecord> Args;
2718   Args.push_back(ValueRecord(Arg, Type::UIntTy));
2719   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2720                                   1).addExternalSymbol("malloc", true);
2721   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
2722 }
2723
2724
2725 /// visitFreeInst - Free instructions are code gen'd to call the free libc
2726 /// function.
2727 ///
2728 void ISel::visitFreeInst(FreeInst &I) {
2729   std::vector<ValueRecord> Args;
2730   Args.push_back(ValueRecord(I.getOperand(0)));
2731   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2732                                   1).addExternalSymbol("free", true);
2733   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
2734 }
2735
2736 /// createX86SimpleInstructionSelector - This pass converts an LLVM function
2737 /// into a machine code representation is a very simple peep-hole fashion.  The
2738 /// generated code sucks but the implementation is nice and simple.
2739 ///
2740 FunctionPass *llvm::createX86SimpleInstructionSelector(TargetMachine &TM) {
2741   return new ISel(TM);
2742 }