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::vastart:
1246           case Intrinsic::vacopy:
1247           case Intrinsic::vaend:
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 static bool isSafeToFoldLoadIntoInstruction(LoadInst &LI, Instruction &User) {
1418   if (LI.getParent() != User.getParent())
1419     return false;
1420   BasicBlock::iterator It = &LI;
1421   // Check all of the instructions between the load and the user.  We should
1422   // really use alias analysis here, but for now we just do something simple.
1423   for (++It; It != BasicBlock::iterator(&User); ++It) {
1424     switch (It->getOpcode()) {
1425     case Instruction::Store:
1426     case Instruction::Call:
1427     case Instruction::Invoke:
1428       return false;
1429     }
1430   }
1431   return true;
1432 }
1433
1434
1435 /// visitSimpleBinary - Implement simple binary operators for integral types...
1436 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
1437 /// Xor.
1438 ///
1439 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
1440   unsigned DestReg = getReg(B);
1441   MachineBasicBlock::iterator MI = BB->end();
1442   Value *Op0 = B.getOperand(0), *Op1 = B.getOperand(1);
1443
1444   // Special case: op Reg, load [mem]
1445   if (isa<LoadInst>(Op0) && !isa<LoadInst>(Op1))
1446     if (!B.swapOperands())
1447       std::swap(Op0, Op1);  // Make sure any loads are in the RHS.
1448
1449   unsigned Class = getClassB(B.getType());
1450   if (isa<LoadInst>(Op1) && Class < cFP &&
1451       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op1), B)) {
1452
1453     static const unsigned OpcodeTab[][3] = {
1454       // Arithmetic operators
1455       { X86::ADD8rm, X86::ADD16rm, X86::ADD32rm },  // ADD
1456       { X86::SUB8rm, X86::SUB16rm, X86::SUB32rm },  // SUB
1457
1458       // Bitwise operators
1459       { X86::AND8rm, X86::AND16rm, X86::AND32rm },  // AND
1460       { X86:: OR8rm, X86:: OR16rm, X86:: OR32rm },  // OR
1461       { X86::XOR8rm, X86::XOR16rm, X86::XOR32rm },  // XOR
1462     };
1463
1464     assert(Class < cFP && "General code handles 64-bit integer types!");
1465     unsigned Opcode = OpcodeTab[OperatorClass][Class];
1466
1467     unsigned BaseReg, Scale, IndexReg, Disp;
1468     getAddressingMode(cast<LoadInst>(Op1)->getOperand(0), BaseReg,
1469                       Scale, IndexReg, Disp);
1470
1471     unsigned Op0r = getReg(Op0);
1472     addFullAddress(BuildMI(BB, Opcode, 2, DestReg).addReg(Op0r),
1473                    BaseReg, Scale, IndexReg, Disp);
1474     return;
1475   }
1476
1477   emitSimpleBinaryOperation(BB, MI, Op0, Op1, OperatorClass, DestReg);
1478 }
1479
1480 /// emitSimpleBinaryOperation - Implement simple binary operators for integral
1481 /// types...  OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for
1482 /// Or, 4 for Xor.
1483 ///
1484 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
1485 /// and constant expression support.
1486 ///
1487 void ISel::emitSimpleBinaryOperation(MachineBasicBlock *MBB,
1488                                      MachineBasicBlock::iterator IP,
1489                                      Value *Op0, Value *Op1,
1490                                      unsigned OperatorClass, unsigned DestReg) {
1491   unsigned Class = getClassB(Op0->getType());
1492
1493   // sub 0, X -> neg X
1494   if (OperatorClass == 1 && Class != cLong)
1495     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0)) {
1496       if (CI->isNullValue()) {
1497         unsigned op1Reg = getReg(Op1, MBB, IP);
1498         switch (Class) {
1499         default: assert(0 && "Unknown class for this function!");
1500         case cByte:
1501           BuildMI(*MBB, IP, X86::NEG8r, 1, DestReg).addReg(op1Reg);
1502           return;
1503         case cShort:
1504           BuildMI(*MBB, IP, X86::NEG16r, 1, DestReg).addReg(op1Reg);
1505           return;
1506         case cInt:
1507           BuildMI(*MBB, IP, X86::NEG32r, 1, DestReg).addReg(op1Reg);
1508           return;
1509         }
1510       }
1511     } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op0))
1512       if (CFP->isExactlyValue(-0.0)) {
1513         // -0.0 - X === -X
1514         unsigned op1Reg = getReg(Op1, MBB, IP);
1515         BuildMI(*MBB, IP, X86::FCHS, 1, DestReg).addReg(op1Reg);
1516         return;
1517       }
1518
1519   // Special case: op Reg, <const>
1520   if (Class != cLong && isa<ConstantInt>(Op1)) {
1521     ConstantInt *Op1C = cast<ConstantInt>(Op1);
1522     unsigned Op0r = getReg(Op0, MBB, IP);
1523
1524     // xor X, -1 -> not X
1525     if (OperatorClass == 4 && Op1C->isAllOnesValue()) {
1526       static unsigned const NOTTab[] = { X86::NOT8r, X86::NOT16r, X86::NOT32r };
1527       BuildMI(*MBB, IP, NOTTab[Class], 1, DestReg).addReg(Op0r);
1528       return;
1529     }
1530
1531     // add X, -1 -> dec X
1532     if (OperatorClass == 0 && Op1C->isAllOnesValue()) {
1533       static unsigned const DECTab[] = { X86::DEC8r, X86::DEC16r, X86::DEC32r };
1534       BuildMI(*MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
1535       return;
1536     }
1537
1538     // add X, 1 -> inc X
1539     if (OperatorClass == 0 && Op1C->equalsInt(1)) {
1540       static unsigned const DECTab[] = { X86::INC8r, X86::INC16r, X86::INC32r };
1541       BuildMI(*MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
1542       return;
1543     }
1544
1545     static const unsigned OpcodeTab[][3] = {
1546       // Arithmetic operators
1547       { X86::ADD8ri, X86::ADD16ri, X86::ADD32ri },  // ADD
1548       { X86::SUB8ri, X86::SUB16ri, X86::SUB32ri },  // SUB
1549
1550       // Bitwise operators
1551       { X86::AND8ri, X86::AND16ri, X86::AND32ri },  // AND
1552       { X86:: OR8ri, X86:: OR16ri, X86:: OR32ri },  // OR
1553       { X86::XOR8ri, X86::XOR16ri, X86::XOR32ri },  // XOR
1554     };
1555
1556     assert(Class < cFP && "General code handles 64-bit integer types!");
1557     unsigned Opcode = OpcodeTab[OperatorClass][Class];
1558
1559
1560     uint64_t Op1v = cast<ConstantInt>(Op1C)->getRawValue();
1561     BuildMI(*MBB, IP, Opcode, 5, DestReg).addReg(Op0r).addImm(Op1v);
1562     return;
1563   }
1564
1565   // Finally, handle the general case now.
1566   static const unsigned OpcodeTab[][4] = {
1567     // Arithmetic operators
1568     { X86::ADD8rr, X86::ADD16rr, X86::ADD32rr, X86::FpADD },  // ADD
1569     { X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, X86::FpSUB },  // SUB
1570
1571     // Bitwise operators
1572     { X86::AND8rr, X86::AND16rr, X86::AND32rr, 0 },  // AND
1573     { X86:: OR8rr, X86:: OR16rr, X86:: OR32rr, 0 },  // OR
1574     { X86::XOR8rr, X86::XOR16rr, X86::XOR32rr, 0 },  // XOR
1575   };
1576
1577   bool isLong = false;
1578   if (Class == cLong) {
1579     isLong = true;
1580     Class = cInt;          // Bottom 32 bits are handled just like ints
1581   }
1582
1583   unsigned Opcode = OpcodeTab[OperatorClass][Class];
1584   assert(Opcode && "Floating point arguments to logical inst?");
1585   unsigned Op0r = getReg(Op0, MBB, IP);
1586   unsigned Op1r = getReg(Op1, MBB, IP);
1587   BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
1588
1589   if (isLong) {        // Handle the upper 32 bits of long values...
1590     static const unsigned TopTab[] = {
1591       X86::ADC32rr, X86::SBB32rr, X86::AND32rr, X86::OR32rr, X86::XOR32rr
1592     };
1593     BuildMI(*MBB, IP, TopTab[OperatorClass], 2,
1594             DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
1595   }
1596 }
1597
1598 /// doMultiply - Emit appropriate instructions to multiply together the
1599 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
1600 /// result should be given as DestTy.
1601 ///
1602 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
1603                       unsigned DestReg, const Type *DestTy,
1604                       unsigned op0Reg, unsigned op1Reg) {
1605   unsigned Class = getClass(DestTy);
1606   switch (Class) {
1607   case cFP:              // Floating point multiply
1608     BuildMI(*MBB, MBBI, X86::FpMUL, 2, DestReg).addReg(op0Reg).addReg(op1Reg);
1609     return;
1610   case cInt:
1611   case cShort:
1612     BuildMI(*MBB, MBBI, Class == cInt ? X86::IMUL32rr:X86::IMUL16rr, 2, DestReg)
1613       .addReg(op0Reg).addReg(op1Reg);
1614     return;
1615   case cByte:
1616     // Must use the MUL instruction, which forces use of AL...
1617     BuildMI(*MBB, MBBI, X86::MOV8rr, 1, X86::AL).addReg(op0Reg);
1618     BuildMI(*MBB, MBBI, X86::MUL8r, 1).addReg(op1Reg);
1619     BuildMI(*MBB, MBBI, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
1620     return;
1621   default:
1622   case cLong: assert(0 && "doMultiply cannot operate on LONG values!");
1623   }
1624 }
1625
1626 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1627 // returns zero when the input is not exactly a power of two.
1628 static unsigned ExactLog2(unsigned Val) {
1629   if (Val == 0) return 0;
1630   unsigned Count = 0;
1631   while (Val != 1) {
1632     if (Val & 1) return 0;
1633     Val >>= 1;
1634     ++Count;
1635   }
1636   return Count+1;
1637 }
1638
1639 void ISel::doMultiplyConst(MachineBasicBlock *MBB,
1640                            MachineBasicBlock::iterator IP,
1641                            unsigned DestReg, const Type *DestTy,
1642                            unsigned op0Reg, unsigned ConstRHS) {
1643   unsigned Class = getClass(DestTy);
1644
1645   // If the element size is exactly a power of 2, use a shift to get it.
1646   if (unsigned Shift = ExactLog2(ConstRHS)) {
1647     switch (Class) {
1648     default: assert(0 && "Unknown class for this function!");
1649     case cByte:
1650       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
1651       return;
1652     case cShort:
1653       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
1654       return;
1655     case cInt:
1656       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
1657       return;
1658     }
1659   }
1660
1661   if (Class == cShort) {
1662     BuildMI(*MBB, IP, X86::IMUL16rri,2,DestReg).addReg(op0Reg).addImm(ConstRHS);
1663     return;
1664   } else if (Class == cInt) {
1665     BuildMI(*MBB, IP, X86::IMUL32rri,2,DestReg).addReg(op0Reg).addImm(ConstRHS);
1666     return;
1667   }
1668
1669   // Most general case, emit a normal multiply...
1670   static const unsigned MOVriTab[] = {
1671     X86::MOV8ri, X86::MOV16ri, X86::MOV32ri
1672   };
1673
1674   unsigned TmpReg = makeAnotherReg(DestTy);
1675   BuildMI(*MBB, IP, MOVriTab[Class], 1, TmpReg).addImm(ConstRHS);
1676
1677   // Emit a MUL to multiply the register holding the index by
1678   // elementSize, putting the result in OffsetReg.
1679   doMultiply(MBB, IP, DestReg, DestTy, op0Reg, TmpReg);
1680 }
1681
1682 /// visitMul - Multiplies are not simple binary operators because they must deal
1683 /// with the EAX register explicitly.
1684 ///
1685 void ISel::visitMul(BinaryOperator &I) {
1686   unsigned Op0Reg  = getReg(I.getOperand(0));
1687   unsigned DestReg = getReg(I);
1688
1689   // Simple scalar multiply?
1690   if (I.getType() != Type::LongTy && I.getType() != Type::ULongTy) {
1691     if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1))) {
1692       unsigned Val = (unsigned)CI->getRawValue(); // Cannot be 64-bit constant
1693       MachineBasicBlock::iterator MBBI = BB->end();
1694       doMultiplyConst(BB, MBBI, DestReg, I.getType(), Op0Reg, Val);
1695     } else {
1696       unsigned Op1Reg  = getReg(I.getOperand(1));
1697       MachineBasicBlock::iterator MBBI = BB->end();
1698       doMultiply(BB, MBBI, DestReg, I.getType(), Op0Reg, Op1Reg);
1699     }
1700   } else {
1701     unsigned Op1Reg  = getReg(I.getOperand(1));
1702
1703     // Long value.  We have to do things the hard way...
1704     // Multiply the two low parts... capturing carry into EDX
1705     BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Op0Reg);
1706     BuildMI(BB, X86::MUL32r, 1).addReg(Op1Reg);  // AL*BL
1707
1708     unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
1709     BuildMI(BB, X86::MOV32rr, 1, DestReg).addReg(X86::EAX);     // AL*BL
1710     BuildMI(BB, X86::MOV32rr, 1, OverflowReg).addReg(X86::EDX); // AL*BL >> 32
1711
1712     MachineBasicBlock::iterator MBBI = BB->end();
1713     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
1714     BuildMI(*BB, MBBI, X86::IMUL32rr,2,AHBLReg).addReg(Op0Reg+1).addReg(Op1Reg);
1715
1716     unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
1717     BuildMI(*BB, MBBI, X86::ADD32rr, 2,                  // AH*BL+(AL*BL >> 32)
1718             AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
1719
1720     MBBI = BB->end();
1721     unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
1722     BuildMI(*BB, MBBI, X86::IMUL32rr,2,ALBHReg).addReg(Op0Reg).addReg(Op1Reg+1);
1723
1724     BuildMI(*BB, MBBI, X86::ADD32rr, 2,         // AL*BH + AH*BL + (AL*BL >> 32)
1725             DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
1726   }
1727 }
1728
1729
1730 /// visitDivRem - Handle division and remainder instructions... these
1731 /// instruction both require the same instructions to be generated, they just
1732 /// select the result from a different register.  Note that both of these
1733 /// instructions work differently for signed and unsigned operands.
1734 ///
1735 void ISel::visitDivRem(BinaryOperator &I) {
1736   unsigned Op0Reg = getReg(I.getOperand(0));
1737   unsigned Op1Reg = getReg(I.getOperand(1));
1738   unsigned ResultReg = getReg(I);
1739
1740   MachineBasicBlock::iterator IP = BB->end();
1741   emitDivRemOperation(BB, IP, Op0Reg, Op1Reg, I.getOpcode() == Instruction::Div,
1742                       I.getType(), ResultReg);
1743 }
1744
1745 void ISel::emitDivRemOperation(MachineBasicBlock *BB,
1746                                MachineBasicBlock::iterator IP,
1747                                unsigned Op0Reg, unsigned Op1Reg, bool isDiv,
1748                                const Type *Ty, unsigned ResultReg) {
1749   unsigned Class = getClass(Ty);
1750   switch (Class) {
1751   case cFP:              // Floating point divide
1752     if (isDiv) {
1753       BuildMI(*BB, IP, X86::FpDIV, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
1754     } else {               // Floating point remainder...
1755       MachineInstr *TheCall =
1756         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
1757       std::vector<ValueRecord> Args;
1758       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
1759       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
1760       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
1761     }
1762     return;
1763   case cLong: {
1764     static const char *FnName[] =
1765       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
1766
1767     unsigned NameIdx = Ty->isUnsigned()*2 + isDiv;
1768     MachineInstr *TheCall =
1769       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
1770
1771     std::vector<ValueRecord> Args;
1772     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
1773     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
1774     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
1775     return;
1776   }
1777   case cByte: case cShort: case cInt:
1778     break;          // Small integrals, handled below...
1779   default: assert(0 && "Unknown class!");
1780   }
1781
1782   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
1783   static const unsigned MovOpcode[]={ X86::MOV8rr, X86::MOV16rr, X86::MOV32rr };
1784   static const unsigned SarOpcode[]={ X86::SAR8ri, X86::SAR16ri, X86::SAR32ri };
1785   static const unsigned ClrOpcode[]={ X86::MOV8ri, X86::MOV16ri, X86::MOV32ri };
1786   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
1787
1788   static const unsigned DivOpcode[][4] = {
1789     { X86::DIV8r , X86::DIV16r , X86::DIV32r , 0 },  // Unsigned division
1790     { X86::IDIV8r, X86::IDIV16r, X86::IDIV32r, 0 },  // Signed division
1791   };
1792
1793   bool isSigned   = Ty->isSigned();
1794   unsigned Reg    = Regs[Class];
1795   unsigned ExtReg = ExtRegs[Class];
1796
1797   // Put the first operand into one of the A registers...
1798   BuildMI(*BB, IP, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
1799
1800   if (isSigned) {
1801     // Emit a sign extension instruction...
1802     unsigned ShiftResult = makeAnotherReg(Ty);
1803     BuildMI(*BB, IP, SarOpcode[Class], 2,ShiftResult).addReg(Op0Reg).addImm(31);
1804     BuildMI(*BB, IP, MovOpcode[Class], 1, ExtReg).addReg(ShiftResult);
1805   } else {
1806     // If unsigned, emit a zeroing instruction... (reg = 0)
1807     BuildMI(*BB, IP, ClrOpcode[Class], 2, ExtReg).addImm(0);
1808   }
1809
1810   // Emit the appropriate divide or remainder instruction...
1811   BuildMI(*BB, IP, DivOpcode[isSigned][Class], 1).addReg(Op1Reg);
1812
1813   // Figure out which register we want to pick the result out of...
1814   unsigned DestReg = isDiv ? Reg : ExtReg;
1815
1816   // Put the result into the destination register...
1817   BuildMI(*BB, IP, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
1818 }
1819
1820
1821 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
1822 /// for constant immediate shift values, and for constant immediate
1823 /// shift values equal to 1. Even the general case is sort of special,
1824 /// because the shift amount has to be in CL, not just any old register.
1825 ///
1826 void ISel::visitShiftInst(ShiftInst &I) {
1827   MachineBasicBlock::iterator IP = BB->end ();
1828   emitShiftOperation (BB, IP, I.getOperand (0), I.getOperand (1),
1829                       I.getOpcode () == Instruction::Shl, I.getType (),
1830                       getReg (I));
1831 }
1832
1833 /// emitShiftOperation - Common code shared between visitShiftInst and
1834 /// constant expression support.
1835 void ISel::emitShiftOperation(MachineBasicBlock *MBB,
1836                               MachineBasicBlock::iterator IP,
1837                               Value *Op, Value *ShiftAmount, bool isLeftShift,
1838                               const Type *ResultTy, unsigned DestReg) {
1839   unsigned SrcReg = getReg (Op, MBB, IP);
1840   bool isSigned = ResultTy->isSigned ();
1841   unsigned Class = getClass (ResultTy);
1842
1843   static const unsigned ConstantOperand[][4] = {
1844     { X86::SHR8ri, X86::SHR16ri, X86::SHR32ri, X86::SHRD32rri8 },  // SHR
1845     { X86::SAR8ri, X86::SAR16ri, X86::SAR32ri, X86::SHRD32rri8 },  // SAR
1846     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SHL
1847     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SAL = SHL
1848   };
1849
1850   static const unsigned NonConstantOperand[][4] = {
1851     { X86::SHR8rCL, X86::SHR16rCL, X86::SHR32rCL },  // SHR
1852     { X86::SAR8rCL, X86::SAR16rCL, X86::SAR32rCL },  // SAR
1853     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SHL
1854     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SAL = SHL
1855   };
1856
1857   // Longs, as usual, are handled specially...
1858   if (Class == cLong) {
1859     // If we have a constant shift, we can generate much more efficient code
1860     // than otherwise...
1861     //
1862     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
1863       unsigned Amount = CUI->getValue();
1864       if (Amount < 32) {
1865         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1866         if (isLeftShift) {
1867           BuildMI(*MBB, IP, Opc[3], 3,
1868               DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addImm(Amount);
1869           BuildMI(*MBB, IP, Opc[2], 2, DestReg).addReg(SrcReg).addImm(Amount);
1870         } else {
1871           BuildMI(*MBB, IP, Opc[3], 3,
1872               DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addImm(Amount);
1873           BuildMI(*MBB, IP, Opc[2],2,DestReg+1).addReg(SrcReg+1).addImm(Amount);
1874         }
1875       } else {                 // Shifting more than 32 bits
1876         Amount -= 32;
1877         if (isLeftShift) {
1878           BuildMI(*MBB, IP, X86::SHL32ri, 2,
1879               DestReg + 1).addReg(SrcReg).addImm(Amount);
1880           BuildMI(*MBB, IP, X86::MOV32ri, 1,
1881               DestReg).addImm(0);
1882         } else {
1883           unsigned Opcode = isSigned ? X86::SAR32ri : X86::SHR32ri;
1884           BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(SrcReg+1).addImm(Amount);
1885           BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
1886         }
1887       }
1888     } else {
1889       unsigned TmpReg = makeAnotherReg(Type::IntTy);
1890
1891       if (!isLeftShift && isSigned) {
1892         // If this is a SHR of a Long, then we need to do funny sign extension
1893         // stuff.  TmpReg gets the value to use as the high-part if we are
1894         // shifting more than 32 bits.
1895         BuildMI(*MBB, IP, X86::SAR32ri, 2, TmpReg).addReg(SrcReg).addImm(31);
1896       } else {
1897         // Other shifts use a fixed zero value if the shift is more than 32
1898         // bits.
1899         BuildMI(*MBB, IP, X86::MOV32ri, 1, TmpReg).addImm(0);
1900       }
1901
1902       // Initialize CL with the shift amount...
1903       unsigned ShiftAmountReg = getReg(ShiftAmount, MBB, IP);
1904       BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
1905
1906       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
1907       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
1908       if (isLeftShift) {
1909         // TmpReg2 = shld inHi, inLo
1910         BuildMI(*MBB, IP, X86::SHLD32rrCL,2,TmpReg2).addReg(SrcReg+1)
1911                                                     .addReg(SrcReg);
1912         // TmpReg3 = shl  inLo, CL
1913         BuildMI(*MBB, IP, X86::SHL32rCL, 1, TmpReg3).addReg(SrcReg);
1914
1915         // Set the flags to indicate whether the shift was by more than 32 bits.
1916         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
1917
1918         // DestHi = (>32) ? TmpReg3 : TmpReg2;
1919         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1920                 DestReg+1).addReg(TmpReg2).addReg(TmpReg3);
1921         // DestLo = (>32) ? TmpReg : TmpReg3;
1922         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1923             DestReg).addReg(TmpReg3).addReg(TmpReg);
1924       } else {
1925         // TmpReg2 = shrd inLo, inHi
1926         BuildMI(*MBB, IP, X86::SHRD32rrCL,2,TmpReg2).addReg(SrcReg)
1927                                                     .addReg(SrcReg+1);
1928         // TmpReg3 = s[ah]r  inHi, CL
1929         BuildMI(*MBB, IP, isSigned ? X86::SAR32rCL : X86::SHR32rCL, 1, TmpReg3)
1930                        .addReg(SrcReg+1);
1931
1932         // Set the flags to indicate whether the shift was by more than 32 bits.
1933         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
1934
1935         // DestLo = (>32) ? TmpReg3 : TmpReg2;
1936         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1937                 DestReg).addReg(TmpReg2).addReg(TmpReg3);
1938
1939         // DestHi = (>32) ? TmpReg : TmpReg3;
1940         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
1941                 DestReg+1).addReg(TmpReg3).addReg(TmpReg);
1942       }
1943     }
1944     return;
1945   }
1946
1947   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
1948     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
1949     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
1950
1951     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1952     BuildMI(*MBB, IP, Opc[Class], 2,
1953         DestReg).addReg(SrcReg).addImm(CUI->getValue());
1954   } else {                  // The shift amount is non-constant.
1955     unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
1956     BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
1957
1958     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
1959     BuildMI(*MBB, IP, Opc[Class], 1, DestReg).addReg(SrcReg);
1960   }
1961 }
1962
1963
1964 void ISel::getAddressingMode(Value *Addr, unsigned &BaseReg, unsigned &Scale,
1965                              unsigned &IndexReg, unsigned &Disp) {
1966   BaseReg = 0; Scale = 1; IndexReg = 0; Disp = 0;
1967   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) {
1968     if (isGEPFoldable(BB, GEP->getOperand(0), GEP->op_begin()+1, GEP->op_end(),
1969                        BaseReg, Scale, IndexReg, Disp))
1970       return;
1971   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
1972     if (CE->getOpcode() == Instruction::GetElementPtr)
1973       if (isGEPFoldable(BB, CE->getOperand(0), CE->op_begin()+1, CE->op_end(),
1974                         BaseReg, Scale, IndexReg, Disp))
1975         return;
1976   }
1977
1978   // If it's not foldable, reset addr mode.
1979   BaseReg = getReg(Addr);
1980   Scale = 1; IndexReg = 0; Disp = 0;
1981 }
1982
1983
1984 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
1985 /// instruction.  The load and store instructions are the only place where we
1986 /// need to worry about the memory layout of the target machine.
1987 ///
1988 void ISel::visitLoadInst(LoadInst &I) {
1989   // Check to see if this load instruction is going to be folded into a binary
1990   // instruction, like add.  If so, we don't want to emit it.  Wouldn't a real
1991   // pattern matching instruction selector be nice?
1992   if (I.hasOneUse() && getClassB(I.getType()) < cFP) {
1993     Instruction *User = cast<Instruction>(I.use_back());
1994     switch (User->getOpcode()) {
1995     default: User = 0; break;
1996     case Instruction::Add:
1997     case Instruction::Sub:
1998     case Instruction::And:
1999     case Instruction::Or:
2000     case Instruction::Xor:
2001       break;
2002     }
2003
2004     if (User) {
2005       // Okay, we found a user.  If the load is the first operand and there is
2006       // no second operand load, reverse the operand ordering.  Note that this
2007       // can fail for a subtract (ie, no change will be made).
2008       if (!isa<LoadInst>(User->getOperand(1)))
2009         cast<BinaryOperator>(User)->swapOperands();
2010
2011       // Okay, now that everything is set up, if this load is used by the second
2012       // operand, and if there are no instructions that invalidate the load
2013       // before the binary operator, eliminate the load.
2014       if (User->getOperand(1) == &I &&
2015           isSafeToFoldLoadIntoInstruction(I, *User))
2016         return;   // Eliminate the load!
2017     }
2018   }
2019
2020   unsigned DestReg = getReg(I);
2021   unsigned BaseReg = 0, Scale = 1, IndexReg = 0, Disp = 0;
2022   getAddressingMode(I.getOperand(0), BaseReg, Scale, IndexReg, Disp);
2023
2024   unsigned Class = getClassB(I.getType());
2025   if (Class == cLong) {
2026     addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg),
2027                    BaseReg, Scale, IndexReg, Disp);
2028     addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg+1),
2029                    BaseReg, Scale, IndexReg, Disp+4);
2030     return;
2031   }
2032
2033   static const unsigned Opcodes[] = {
2034     X86::MOV8rm, X86::MOV16rm, X86::MOV32rm, X86::FLD32m
2035   };
2036   unsigned Opcode = Opcodes[Class];
2037   if (I.getType() == Type::DoubleTy) Opcode = X86::FLD64m;
2038   addFullAddress(BuildMI(BB, Opcode, 4, DestReg),
2039                  BaseReg, Scale, IndexReg, Disp);
2040 }
2041
2042 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
2043 /// instruction.
2044 ///
2045 void ISel::visitStoreInst(StoreInst &I) {
2046   unsigned BaseReg, Scale, IndexReg, Disp;
2047   getAddressingMode(I.getOperand(1), BaseReg, Scale, IndexReg, Disp);
2048
2049   const Type *ValTy = I.getOperand(0)->getType();
2050   unsigned Class = getClassB(ValTy);
2051
2052   if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(0))) {
2053     uint64_t Val = CI->getRawValue();
2054     if (Class == cLong) {
2055       addFullAddress(BuildMI(BB, X86::MOV32mi, 5),
2056                      BaseReg, Scale, IndexReg, Disp).addImm(Val & ~0U);
2057       addFullAddress(BuildMI(BB, X86::MOV32mi, 5),
2058                      BaseReg, Scale, IndexReg, Disp+4).addImm(Val>>32);
2059     } else {
2060       static const unsigned Opcodes[] = {
2061         X86::MOV8mi, X86::MOV16mi, X86::MOV32mi
2062       };
2063       unsigned Opcode = Opcodes[Class];
2064       addFullAddress(BuildMI(BB, Opcode, 5),
2065                      BaseReg, Scale, IndexReg, Disp).addImm(Val);
2066     }
2067   } else if (ConstantBool *CB = dyn_cast<ConstantBool>(I.getOperand(0))) {
2068     addFullAddress(BuildMI(BB, X86::MOV8mi, 5),
2069                    BaseReg, Scale, IndexReg, Disp).addImm(CB->getValue());
2070   } else {
2071     if (Class == cLong) {
2072       unsigned ValReg = getReg(I.getOperand(0));
2073       addFullAddress(BuildMI(BB, X86::MOV32mr, 5),
2074                      BaseReg, Scale, IndexReg, Disp).addReg(ValReg);
2075       addFullAddress(BuildMI(BB, X86::MOV32mr, 5),
2076                      BaseReg, Scale, IndexReg, Disp+4).addReg(ValReg+1);
2077     } else {
2078       unsigned ValReg = getReg(I.getOperand(0));
2079       static const unsigned Opcodes[] = {
2080         X86::MOV8mr, X86::MOV16mr, X86::MOV32mr, X86::FST32m
2081       };
2082       unsigned Opcode = Opcodes[Class];
2083       if (ValTy == Type::DoubleTy) Opcode = X86::FST64m;
2084       addFullAddress(BuildMI(BB, Opcode, 1+4),
2085                      BaseReg, Scale, IndexReg, Disp).addReg(ValReg);
2086     }
2087   }
2088 }
2089
2090
2091 /// visitCastInst - Here we have various kinds of copying with or without sign
2092 /// extension going on.
2093 ///
2094 void ISel::visitCastInst(CastInst &CI) {
2095   Value *Op = CI.getOperand(0);
2096   // If this is a cast from a 32-bit integer to a Long type, and the only uses
2097   // of the case are GEP instructions, then the cast does not need to be
2098   // generated explicitly, it will be folded into the GEP.
2099   if (CI.getType() == Type::LongTy &&
2100       (Op->getType() == Type::IntTy || Op->getType() == Type::UIntTy)) {
2101     bool AllUsesAreGEPs = true;
2102     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
2103       if (!isa<GetElementPtrInst>(*I)) {
2104         AllUsesAreGEPs = false;
2105         break;
2106       }
2107
2108     // No need to codegen this cast if all users are getelementptr instrs...
2109     if (AllUsesAreGEPs) return;
2110   }
2111
2112   unsigned DestReg = getReg(CI);
2113   MachineBasicBlock::iterator MI = BB->end();
2114   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
2115 }
2116
2117 /// emitCastOperation - Common code shared between visitCastInst and constant
2118 /// expression cast support.
2119 ///
2120 void ISel::emitCastOperation(MachineBasicBlock *BB,
2121                              MachineBasicBlock::iterator IP,
2122                              Value *Src, const Type *DestTy,
2123                              unsigned DestReg) {
2124   unsigned SrcReg = getReg(Src, BB, IP);
2125   const Type *SrcTy = Src->getType();
2126   unsigned SrcClass = getClassB(SrcTy);
2127   unsigned DestClass = getClassB(DestTy);
2128
2129   // Implement casts to bool by using compare on the operand followed by set if
2130   // not zero on the result.
2131   if (DestTy == Type::BoolTy) {
2132     switch (SrcClass) {
2133     case cByte:
2134       BuildMI(*BB, IP, X86::TEST8rr, 2).addReg(SrcReg).addReg(SrcReg);
2135       break;
2136     case cShort:
2137       BuildMI(*BB, IP, X86::TEST16rr, 2).addReg(SrcReg).addReg(SrcReg);
2138       break;
2139     case cInt:
2140       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg).addReg(SrcReg);
2141       break;
2142     case cLong: {
2143       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2144       BuildMI(*BB, IP, X86::OR32rr, 2, TmpReg).addReg(SrcReg).addReg(SrcReg+1);
2145       break;
2146     }
2147     case cFP:
2148       BuildMI(*BB, IP, X86::FTST, 1).addReg(SrcReg);
2149       BuildMI(*BB, IP, X86::FNSTSW8r, 0);
2150       BuildMI(*BB, IP, X86::SAHF, 1);
2151       break;
2152     }
2153
2154     // If the zero flag is not set, then the value is true, set the byte to
2155     // true.
2156     BuildMI(*BB, IP, X86::SETNEr, 1, DestReg);
2157     return;
2158   }
2159
2160   static const unsigned RegRegMove[] = {
2161     X86::MOV8rr, X86::MOV16rr, X86::MOV32rr, X86::FpMOV, X86::MOV32rr
2162   };
2163
2164   // Implement casts between values of the same type class (as determined by
2165   // getClass) by using a register-to-register move.
2166   if (SrcClass == DestClass) {
2167     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
2168       BuildMI(*BB, IP, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
2169     } else if (SrcClass == cFP) {
2170       if (SrcTy == Type::FloatTy) {  // double -> float
2171         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
2172         BuildMI(*BB, IP, X86::FpMOV, 1, DestReg).addReg(SrcReg);
2173       } else {                       // float -> double
2174         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
2175                "Unknown cFP member!");
2176         // Truncate from double to float by storing to memory as short, then
2177         // reading it back.
2178         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
2179         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
2180         addFrameReference(BuildMI(*BB, IP, X86::FST32m, 5), FrameIdx).addReg(SrcReg);
2181         addFrameReference(BuildMI(*BB, IP, X86::FLD32m, 5, DestReg), FrameIdx);
2182       }
2183     } else if (SrcClass == cLong) {
2184       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
2185       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg+1).addReg(SrcReg+1);
2186     } else {
2187       assert(0 && "Cannot handle this type of cast instruction!");
2188       abort();
2189     }
2190     return;
2191   }
2192
2193   // Handle cast of SMALLER int to LARGER int using a move with sign extension
2194   // or zero extension, depending on whether the source type was signed.
2195   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
2196       SrcClass < DestClass) {
2197     bool isLong = DestClass == cLong;
2198     if (isLong) DestClass = cInt;
2199
2200     static const unsigned Opc[][4] = {
2201       { X86::MOVSX16rr8, X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOV32rr }, // s
2202       { X86::MOVZX16rr8, X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOV32rr }  // u
2203     };
2204
2205     bool isUnsigned = SrcTy->isUnsigned();
2206     BuildMI(*BB, IP, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
2207         DestReg).addReg(SrcReg);
2208
2209     if (isLong) {  // Handle upper 32 bits as appropriate...
2210       if (isUnsigned)     // Zero out top bits...
2211         BuildMI(*BB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
2212       else                // Sign extend bottom half...
2213         BuildMI(*BB, IP, X86::SAR32ri, 2, DestReg+1).addReg(DestReg).addImm(31);
2214     }
2215     return;
2216   }
2217
2218   // Special case long -> int ...
2219   if (SrcClass == cLong && DestClass == cInt) {
2220     BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
2221     return;
2222   }
2223
2224   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
2225   // move out of AX or AL.
2226   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
2227       && SrcClass > DestClass) {
2228     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
2229     BuildMI(*BB, IP, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
2230     BuildMI(*BB, IP, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
2231     return;
2232   }
2233
2234   // Handle casts from integer to floating point now...
2235   if (DestClass == cFP) {
2236     // Promote the integer to a type supported by FLD.  We do this because there
2237     // are no unsigned FLD instructions, so we must promote an unsigned value to
2238     // a larger signed value, then use FLD on the larger value.
2239     //
2240     const Type *PromoteType = 0;
2241     unsigned PromoteOpcode;
2242     unsigned RealDestReg = DestReg;
2243     switch (SrcTy->getPrimitiveID()) {
2244     case Type::BoolTyID:
2245     case Type::SByteTyID:
2246       // We don't have the facilities for directly loading byte sized data from
2247       // memory (even signed).  Promote it to 16 bits.
2248       PromoteType = Type::ShortTy;
2249       PromoteOpcode = X86::MOVSX16rr8;
2250       break;
2251     case Type::UByteTyID:
2252       PromoteType = Type::ShortTy;
2253       PromoteOpcode = X86::MOVZX16rr8;
2254       break;
2255     case Type::UShortTyID:
2256       PromoteType = Type::IntTy;
2257       PromoteOpcode = X86::MOVZX32rr16;
2258       break;
2259     case Type::UIntTyID: {
2260       // Make a 64 bit temporary... and zero out the top of it...
2261       unsigned TmpReg = makeAnotherReg(Type::LongTy);
2262       BuildMI(*BB, IP, X86::MOV32rr, 1, TmpReg).addReg(SrcReg);
2263       BuildMI(*BB, IP, X86::MOV32ri, 1, TmpReg+1).addImm(0);
2264       SrcTy = Type::LongTy;
2265       SrcClass = cLong;
2266       SrcReg = TmpReg;
2267       break;
2268     }
2269     case Type::ULongTyID:
2270       // Don't fild into the read destination.
2271       DestReg = makeAnotherReg(Type::DoubleTy);
2272       break;
2273     default:  // No promotion needed...
2274       break;
2275     }
2276
2277     if (PromoteType) {
2278       unsigned TmpReg = makeAnotherReg(PromoteType);
2279       unsigned Opc = SrcTy->isSigned() ? X86::MOVSX16rr8 : X86::MOVZX16rr8;
2280       BuildMI(*BB, IP, Opc, 1, TmpReg).addReg(SrcReg);
2281       SrcTy = PromoteType;
2282       SrcClass = getClass(PromoteType);
2283       SrcReg = TmpReg;
2284     }
2285
2286     // Spill the integer to memory and reload it from there...
2287     int FrameIdx =
2288       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
2289
2290     if (SrcClass == cLong) {
2291       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
2292                         FrameIdx).addReg(SrcReg);
2293       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
2294                         FrameIdx, 4).addReg(SrcReg+1);
2295     } else {
2296       static const unsigned Op1[] = { X86::MOV8mr, X86::MOV16mr, X86::MOV32mr };
2297       addFrameReference(BuildMI(*BB, IP, Op1[SrcClass], 5),
2298                         FrameIdx).addReg(SrcReg);
2299     }
2300
2301     static const unsigned Op2[] =
2302       { 0/*byte*/, X86::FILD16m, X86::FILD32m, 0/*FP*/, X86::FILD64m };
2303     addFrameReference(BuildMI(*BB, IP, Op2[SrcClass], 5, DestReg), FrameIdx);
2304
2305     // We need special handling for unsigned 64-bit integer sources.  If the
2306     // input number has the "sign bit" set, then we loaded it incorrectly as a
2307     // negative 64-bit number.  In this case, add an offset value.
2308     if (SrcTy == Type::ULongTy) {
2309       // Emit a test instruction to see if the dynamic input value was signed.
2310       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg+1).addReg(SrcReg+1);
2311
2312       // If the sign bit is set, get a pointer to an offset, otherwise get a
2313       // pointer to a zero.
2314       MachineConstantPool *CP = F->getConstantPool();
2315       unsigned Zero = makeAnotherReg(Type::IntTy);
2316       Constant *Null = Constant::getNullValue(Type::UIntTy);
2317       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Zero),
2318                                CP->getConstantPoolIndex(Null));
2319       unsigned Offset = makeAnotherReg(Type::IntTy);
2320       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
2321
2322       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Offset),
2323                                CP->getConstantPoolIndex(OffsetCst));
2324       unsigned Addr = makeAnotherReg(Type::IntTy);
2325       BuildMI(*BB, IP, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
2326
2327       // Load the constant for an add.  FIXME: this could make an 'fadd' that
2328       // reads directly from memory, but we don't support these yet.
2329       unsigned ConstReg = makeAnotherReg(Type::DoubleTy);
2330       addDirectMem(BuildMI(*BB, IP, X86::FLD32m, 4, ConstReg), Addr);
2331
2332       BuildMI(*BB, IP, X86::FpADD, 2, RealDestReg)
2333                 .addReg(ConstReg).addReg(DestReg);
2334     }
2335
2336     return;
2337   }
2338
2339   // Handle casts from floating point to integer now...
2340   if (SrcClass == cFP) {
2341     // Change the floating point control register to use "round towards zero"
2342     // mode when truncating to an integer value.
2343     //
2344     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
2345     addFrameReference(BuildMI(*BB, IP, X86::FNSTCW16m, 4), CWFrameIdx);
2346
2347     // Load the old value of the high byte of the control word...
2348     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
2349     addFrameReference(BuildMI(*BB, IP, X86::MOV8rm, 4, HighPartOfCW),
2350                       CWFrameIdx, 1);
2351
2352     // Set the high part to be round to zero...
2353     addFrameReference(BuildMI(*BB, IP, X86::MOV8mi, 5),
2354                       CWFrameIdx, 1).addImm(12);
2355
2356     // Reload the modified control word now...
2357     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
2358
2359     // Restore the memory image of control word to original value
2360     addFrameReference(BuildMI(*BB, IP, X86::MOV8mr, 5),
2361                       CWFrameIdx, 1).addReg(HighPartOfCW);
2362
2363     // We don't have the facilities for directly storing byte sized data to
2364     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
2365     // larger classes because we only have signed FP stores.
2366     unsigned StoreClass  = DestClass;
2367     const Type *StoreTy  = DestTy;
2368     if (StoreClass == cByte || DestTy->isUnsigned())
2369       switch (StoreClass) {
2370       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
2371       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
2372       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
2373       // The following treatment of cLong may not be perfectly right,
2374       // but it survives chains of casts of the form
2375       // double->ulong->double.
2376       case cLong:  StoreTy = Type::LongTy;  StoreClass = cLong;  break;
2377       default: assert(0 && "Unknown store class!");
2378       }
2379
2380     // Spill the integer to memory and reload it from there...
2381     int FrameIdx =
2382       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
2383
2384     static const unsigned Op1[] =
2385       { 0, X86::FIST16m, X86::FIST32m, 0, X86::FISTP64m };
2386     addFrameReference(BuildMI(*BB, IP, Op1[StoreClass], 5),
2387                       FrameIdx).addReg(SrcReg);
2388
2389     if (DestClass == cLong) {
2390       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg), FrameIdx);
2391       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg+1),
2392                         FrameIdx, 4);
2393     } else {
2394       static const unsigned Op2[] = { X86::MOV8rm, X86::MOV16rm, X86::MOV32rm };
2395       addFrameReference(BuildMI(*BB, IP, Op2[DestClass], 4, DestReg), FrameIdx);
2396     }
2397
2398     // Reload the original control word now...
2399     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
2400     return;
2401   }
2402
2403   // Anything we haven't handled already, we can't (yet) handle at all.
2404   assert(0 && "Unhandled cast instruction!");
2405   abort();
2406 }
2407
2408 /// visitVANextInst - Implement the va_next instruction...
2409 ///
2410 void ISel::visitVANextInst(VANextInst &I) {
2411   unsigned VAList = getReg(I.getOperand(0));
2412   unsigned DestReg = getReg(I);
2413
2414   unsigned Size;
2415   switch (I.getArgType()->getPrimitiveID()) {
2416   default:
2417     std::cerr << I;
2418     assert(0 && "Error: bad type for va_next instruction!");
2419     return;
2420   case Type::PointerTyID:
2421   case Type::UIntTyID:
2422   case Type::IntTyID:
2423     Size = 4;
2424     break;
2425   case Type::ULongTyID:
2426   case Type::LongTyID:
2427   case Type::DoubleTyID:
2428     Size = 8;
2429     break;
2430   }
2431
2432   // Increment the VAList pointer...
2433   BuildMI(BB, X86::ADD32ri, 2, DestReg).addReg(VAList).addImm(Size);
2434 }
2435
2436 void ISel::visitVAArgInst(VAArgInst &I) {
2437   unsigned VAList = getReg(I.getOperand(0));
2438   unsigned DestReg = getReg(I);
2439
2440   switch (I.getType()->getPrimitiveID()) {
2441   default:
2442     std::cerr << I;
2443     assert(0 && "Error: bad type for va_next instruction!");
2444     return;
2445   case Type::PointerTyID:
2446   case Type::UIntTyID:
2447   case Type::IntTyID:
2448     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
2449     break;
2450   case Type::ULongTyID:
2451   case Type::LongTyID:
2452     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
2453     addRegOffset(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), VAList, 4);
2454     break;
2455   case Type::DoubleTyID:
2456     addDirectMem(BuildMI(BB, X86::FLD64m, 4, DestReg), VAList);
2457     break;
2458   }
2459 }
2460
2461 /// visitGetElementPtrInst - instruction-select GEP instructions
2462 ///
2463 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
2464   // If this GEP instruction will be folded into all of its users, we don't need
2465   // to explicitly calculate it!
2466   unsigned A, B, C, D;
2467   if (isGEPFoldable(0, I.getOperand(0), I.op_begin()+1, I.op_end(), A,B,C,D)) {
2468     // Check all of the users of the instruction to see if they are loads and
2469     // stores.
2470     bool AllWillFold = true;
2471     for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI)
2472       if (cast<Instruction>(*UI)->getOpcode() != Instruction::Load)
2473         if (cast<Instruction>(*UI)->getOpcode() != Instruction::Store ||
2474             cast<Instruction>(*UI)->getOperand(0) == &I) {
2475           AllWillFold = false;
2476           break;
2477         }
2478
2479     // If the instruction is foldable, and will be folded into all users, don't
2480     // emit it!
2481     if (AllWillFold) return;
2482   }
2483
2484   unsigned outputReg = getReg(I);
2485   emitGEPOperation(BB, BB->end(), I.getOperand(0),
2486                    I.op_begin()+1, I.op_end(), outputReg);
2487 }
2488
2489 /// getGEPIndex - Inspect the getelementptr operands specified with GEPOps and
2490 /// GEPTypes (the derived types being stepped through at each level).  On return
2491 /// from this function, if some indexes of the instruction are representable as
2492 /// an X86 lea instruction, the machine operands are put into the Ops
2493 /// instruction and the consumed indexes are poped from the GEPOps/GEPTypes
2494 /// lists.  Otherwise, GEPOps.size() is returned.  If this returns a an
2495 /// addressing mode that only partially consumes the input, the BaseReg input of
2496 /// the addressing mode must be left free.
2497 ///
2498 /// Note that there is one fewer entry in GEPTypes than there is in GEPOps.
2499 ///
2500 void ISel::getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
2501                        std::vector<Value*> &GEPOps,
2502                        std::vector<const Type*> &GEPTypes, unsigned &BaseReg,
2503                        unsigned &Scale, unsigned &IndexReg, unsigned &Disp) {
2504   const TargetData &TD = TM.getTargetData();
2505
2506   // Clear out the state we are working with...
2507   BaseReg = 0;    // No base register
2508   Scale = 1;      // Unit scale
2509   IndexReg = 0;   // No index register
2510   Disp = 0;       // No displacement
2511
2512   // While there are GEP indexes that can be folded into the current address,
2513   // keep processing them.
2514   while (!GEPTypes.empty()) {
2515     if (const StructType *StTy = dyn_cast<StructType>(GEPTypes.back())) {
2516       // It's a struct access.  CUI is the index into the structure,
2517       // which names the field. This index must have unsigned type.
2518       const ConstantUInt *CUI = cast<ConstantUInt>(GEPOps.back());
2519
2520       // Use the TargetData structure to pick out what the layout of the
2521       // structure is in memory.  Since the structure index must be constant, we
2522       // can get its value and use it to find the right byte offset from the
2523       // StructLayout class's list of structure member offsets.
2524       Disp += TD.getStructLayout(StTy)->MemberOffsets[CUI->getValue()];
2525       GEPOps.pop_back();        // Consume a GEP operand
2526       GEPTypes.pop_back();
2527     } else {
2528       // It's an array or pointer access: [ArraySize x ElementType].
2529       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
2530       Value *idx = GEPOps.back();
2531
2532       // idx is the index into the array.  Unlike with structure
2533       // indices, we may not know its actual value at code-generation
2534       // time.
2535       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
2536
2537       // If idx is a constant, fold it into the offset.
2538       unsigned TypeSize = TD.getTypeSize(SqTy->getElementType());
2539       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
2540         Disp += TypeSize*CSI->getValue();
2541       } else {
2542         // If the index reg is already taken, we can't handle this index.
2543         if (IndexReg) return;
2544
2545         // If this is a size that we can handle, then add the index as
2546         switch (TypeSize) {
2547         case 1: case 2: case 4: case 8:
2548           // These are all acceptable scales on X86.
2549           Scale = TypeSize;
2550           break;
2551         default:
2552           // Otherwise, we can't handle this scale
2553           return;
2554         }
2555
2556         if (CastInst *CI = dyn_cast<CastInst>(idx))
2557           if (CI->getOperand(0)->getType() == Type::IntTy ||
2558               CI->getOperand(0)->getType() == Type::UIntTy)
2559             idx = CI->getOperand(0);
2560
2561         IndexReg = MBB ? getReg(idx, MBB, IP) : 1;
2562       }
2563
2564       GEPOps.pop_back();        // Consume a GEP operand
2565       GEPTypes.pop_back();
2566     }
2567   }
2568
2569   // GEPTypes is empty, which means we have a single operand left.  See if we
2570   // can set it as the base register.
2571   //
2572   // FIXME: When addressing modes are more powerful/correct, we could load
2573   // global addresses directly as 32-bit immediates.
2574   assert(BaseReg == 0);
2575   BaseReg = MBB ? getReg(GEPOps[0], MBB, IP) : 1;
2576   GEPOps.pop_back();        // Consume the last GEP operand
2577 }
2578
2579
2580 /// isGEPFoldable - Return true if the specified GEP can be completely
2581 /// folded into the addressing mode of a load/store or lea instruction.
2582 bool ISel::isGEPFoldable(MachineBasicBlock *MBB,
2583                          Value *Src, User::op_iterator IdxBegin,
2584                          User::op_iterator IdxEnd, unsigned &BaseReg,
2585                          unsigned &Scale, unsigned &IndexReg, unsigned &Disp) {
2586   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Src))
2587     Src = CPR->getValue();
2588
2589   std::vector<Value*> GEPOps;
2590   GEPOps.resize(IdxEnd-IdxBegin+1);
2591   GEPOps[0] = Src;
2592   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
2593
2594   std::vector<const Type*> GEPTypes;
2595   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
2596                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
2597
2598   MachineBasicBlock::iterator IP;
2599   if (MBB) IP = MBB->end();
2600   getGEPIndex(MBB, IP, GEPOps, GEPTypes, BaseReg, Scale, IndexReg, Disp);
2601
2602   // We can fold it away iff the getGEPIndex call eliminated all operands.
2603   return GEPOps.empty();
2604 }
2605
2606 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
2607                             MachineBasicBlock::iterator IP,
2608                             Value *Src, User::op_iterator IdxBegin,
2609                             User::op_iterator IdxEnd, unsigned TargetReg) {
2610   const TargetData &TD = TM.getTargetData();
2611   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Src))
2612     Src = CPR->getValue();
2613
2614   std::vector<Value*> GEPOps;
2615   GEPOps.resize(IdxEnd-IdxBegin+1);
2616   GEPOps[0] = Src;
2617   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
2618
2619   std::vector<const Type*> GEPTypes;
2620   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
2621                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
2622
2623   // Keep emitting instructions until we consume the entire GEP instruction.
2624   while (!GEPOps.empty()) {
2625     unsigned OldSize = GEPOps.size();
2626     unsigned BaseReg, Scale, IndexReg, Disp;
2627     getGEPIndex(MBB, IP, GEPOps, GEPTypes, BaseReg, Scale, IndexReg, Disp);
2628
2629     if (GEPOps.size() != OldSize) {
2630       // getGEPIndex consumed some of the input.  Build an LEA instruction here.
2631       unsigned NextTarget = 0;
2632       if (!GEPOps.empty()) {
2633         assert(BaseReg == 0 &&
2634            "getGEPIndex should have left the base register open for chaining!");
2635         NextTarget = BaseReg = makeAnotherReg(Type::UIntTy);
2636       }
2637
2638       if (IndexReg == 0 && Disp == 0)
2639         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(BaseReg);
2640       else
2641         addFullAddress(BuildMI(*MBB, IP, X86::LEA32r, 5, TargetReg),
2642                        BaseReg, Scale, IndexReg, Disp);
2643       --IP;
2644       TargetReg = NextTarget;
2645     } else if (GEPTypes.empty()) {
2646       // The getGEPIndex operation didn't want to build an LEA.  Check to see if
2647       // all operands are consumed but the base pointer.  If so, just load it
2648       // into the register.
2649       if (GlobalValue *GV = dyn_cast<GlobalValue>(GEPOps[0])) {
2650         BuildMI(*MBB, IP, X86::MOV32ri, 1, TargetReg).addGlobalAddress(GV);
2651       } else {
2652         unsigned BaseReg = getReg(GEPOps[0], MBB, IP);
2653         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(BaseReg);
2654       }
2655       break;                // we are now done
2656
2657     } else {
2658       // It's an array or pointer access: [ArraySize x ElementType].
2659       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
2660       Value *idx = GEPOps.back();
2661       GEPOps.pop_back();        // Consume a GEP operand
2662       GEPTypes.pop_back();
2663
2664       // idx is the index into the array.  Unlike with structure
2665       // indices, we may not know its actual value at code-generation
2666       // time.
2667       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
2668
2669       // Most GEP instructions use a [cast (int/uint) to LongTy] as their
2670       // operand on X86.  Handle this case directly now...
2671       if (CastInst *CI = dyn_cast<CastInst>(idx))
2672         if (CI->getOperand(0)->getType() == Type::IntTy ||
2673             CI->getOperand(0)->getType() == Type::UIntTy)
2674           idx = CI->getOperand(0);
2675
2676       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
2677       // must find the size of the pointed-to type (Not coincidentally, the next
2678       // type is the type of the elements in the array).
2679       const Type *ElTy = SqTy->getElementType();
2680       unsigned elementSize = TD.getTypeSize(ElTy);
2681
2682       // If idxReg is a constant, we don't need to perform the multiply!
2683       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
2684         if (!CSI->isNullValue()) {
2685           unsigned Offset = elementSize*CSI->getValue();
2686           unsigned Reg = makeAnotherReg(Type::UIntTy);
2687           BuildMI(*MBB, IP, X86::ADD32ri, 2, TargetReg)
2688                                 .addReg(Reg).addImm(Offset);
2689           --IP;            // Insert the next instruction before this one.
2690           TargetReg = Reg; // Codegen the rest of the GEP into this
2691         }
2692       } else if (elementSize == 1) {
2693         // If the element size is 1, we don't have to multiply, just add
2694         unsigned idxReg = getReg(idx, MBB, IP);
2695         unsigned Reg = makeAnotherReg(Type::UIntTy);
2696         BuildMI(*MBB, IP, X86::ADD32rr, 2,TargetReg).addReg(Reg).addReg(idxReg);
2697         --IP;            // Insert the next instruction before this one.
2698         TargetReg = Reg; // Codegen the rest of the GEP into this
2699       } else {
2700         unsigned idxReg = getReg(idx, MBB, IP);
2701         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
2702
2703         // Make sure we can back the iterator up to point to the first
2704         // instruction emitted.
2705         MachineBasicBlock::iterator BeforeIt = IP;
2706         if (IP == MBB->begin())
2707           BeforeIt = MBB->end();
2708         else
2709           --BeforeIt;
2710         doMultiplyConst(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSize);
2711
2712         // Emit an ADD to add OffsetReg to the basePtr.
2713         unsigned Reg = makeAnotherReg(Type::UIntTy);
2714         BuildMI(*MBB, IP, X86::ADD32rr, 2, TargetReg)
2715                           .addReg(Reg).addReg(OffsetReg);
2716
2717         // Step to the first instruction of the multiply.
2718         if (BeforeIt == MBB->end())
2719           IP = MBB->begin();
2720         else
2721           IP = ++BeforeIt;
2722
2723         TargetReg = Reg; // Codegen the rest of the GEP into this
2724       }
2725     }
2726   }
2727 }
2728
2729
2730 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
2731 /// frame manager, otherwise do it the hard way.
2732 ///
2733 void ISel::visitAllocaInst(AllocaInst &I) {
2734   // Find the data size of the alloca inst's getAllocatedType.
2735   const Type *Ty = I.getAllocatedType();
2736   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
2737
2738   // If this is a fixed size alloca in the entry block for the function,
2739   // statically stack allocate the space.
2740   //
2741   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getArraySize())) {
2742     if (I.getParent() == I.getParent()->getParent()->begin()) {
2743       TySize *= CUI->getValue();   // Get total allocated size...
2744       unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
2745
2746       // Create a new stack object using the frame manager...
2747       int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
2748       addFrameReference(BuildMI(BB, X86::LEA32r, 5, getReg(I)), FrameIdx);
2749       return;
2750     }
2751   }
2752
2753   // Create a register to hold the temporary result of multiplying the type size
2754   // constant by the variable amount.
2755   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
2756   unsigned SrcReg1 = getReg(I.getArraySize());
2757
2758   // TotalSizeReg = mul <numelements>, <TypeSize>
2759   MachineBasicBlock::iterator MBBI = BB->end();
2760   doMultiplyConst(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, TySize);
2761
2762   // AddedSize = add <TotalSizeReg>, 15
2763   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
2764   BuildMI(BB, X86::ADD32ri, 2, AddedSizeReg).addReg(TotalSizeReg).addImm(15);
2765
2766   // AlignedSize = and <AddedSize>, ~15
2767   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
2768   BuildMI(BB, X86::AND32ri, 2, AlignedSize).addReg(AddedSizeReg).addImm(~15);
2769
2770   // Subtract size from stack pointer, thereby allocating some space.
2771   BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
2772
2773   // Put a pointer to the space into the result register, by copying
2774   // the stack pointer.
2775   BuildMI(BB, X86::MOV32rr, 1, getReg(I)).addReg(X86::ESP);
2776
2777   // Inform the Frame Information that we have just allocated a variable-sized
2778   // object.
2779   F->getFrameInfo()->CreateVariableSizedObject();
2780 }
2781
2782 /// visitMallocInst - Malloc instructions are code generated into direct calls
2783 /// to the library malloc.
2784 ///
2785 void ISel::visitMallocInst(MallocInst &I) {
2786   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
2787   unsigned Arg;
2788
2789   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
2790     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
2791   } else {
2792     Arg = makeAnotherReg(Type::UIntTy);
2793     unsigned Op0Reg = getReg(I.getOperand(0));
2794     MachineBasicBlock::iterator MBBI = BB->end();
2795     doMultiplyConst(BB, MBBI, Arg, Type::UIntTy, Op0Reg, AllocSize);
2796   }
2797
2798   std::vector<ValueRecord> Args;
2799   Args.push_back(ValueRecord(Arg, Type::UIntTy));
2800   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2801                                   1).addExternalSymbol("malloc", true);
2802   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
2803 }
2804
2805
2806 /// visitFreeInst - Free instructions are code gen'd to call the free libc
2807 /// function.
2808 ///
2809 void ISel::visitFreeInst(FreeInst &I) {
2810   std::vector<ValueRecord> Args;
2811   Args.push_back(ValueRecord(I.getOperand(0)));
2812   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2813                                   1).addExternalSymbol("free", true);
2814   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
2815 }
2816
2817 /// createX86SimpleInstructionSelector - This pass converts an LLVM function
2818 /// into a machine code representation is a very simple peep-hole fashion.  The
2819 /// generated code sucks but the implementation is nice and simple.
2820 ///
2821 FunctionPass *llvm::createX86SimpleInstructionSelector(TargetMachine &TM) {
2822   return new ISel(TM);
2823 }