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