lib/Target/X86/X86ISelSimple.cpp

   1 //===-- X86ISelSimple.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/Pass.h"
  22 #include "llvm/CodeGen/IntrinsicLowering.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/ADT/Statistic.h"
  32 using namespace llvm;
  33
  34 namespace {
  35   Statistic<>
  36   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
  37
  38   /// TypeClass - Used by the X86 backend to group LLVM types by their basic X86
  39   /// Representation.
  40   ///
  41   enum TypeClass {
  42     cByte, cShort, cInt, cFP, cLong
  43   };
  44 }
  45
  46 /// getClass - Turn a primitive type into a "class" number which is based on the
  47 /// size of the type, and whether or not it is floating point.
  48 ///
  49 static inline TypeClass getClass(const Type *Ty) {
  50   switch (Ty->getTypeID()) {
  51   case Type::SByteTyID:
  52   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
  53   case Type::ShortTyID:
  54   case Type::UShortTyID:  return cShort;     // Short operands are class #1
  55   case Type::IntTyID:
  56   case Type::UIntTyID:
  57   case Type::PointerTyID: return cInt;       // Int's and pointers are class #2
  58
  59   case Type::FloatTyID:
  60   case Type::DoubleTyID:  return cFP;        // Floating Point is #3
  61
  62   case Type::LongTyID:
  63   case Type::ULongTyID:   return cLong;      // Longs are class #4
  64   default:
  65     assert(0 && "Invalid type to getClass!");
  66     return cByte;  // not reached
  67   }
  68 }
  69
  70 // getClassB - Just like getClass, but treat boolean values as bytes.
  71 static inline TypeClass getClassB(const Type *Ty) {
  72   if (Ty == Type::BoolTy) return cByte;
  73   return getClass(Ty);
  74 }
  75
  76 namespace {
  77   struct ISel : public FunctionPass, InstVisitor<ISel> {
  78     TargetMachine &TM;
  79     MachineFunction *F;                 // The function we are compiling into
  80     MachineBasicBlock *BB;              // The current MBB we are compiling
  81     int VarArgsFrameIndex;              // FrameIndex for start of varargs area
  82     int ReturnAddressIndex;             // FrameIndex for the return address
  83
  84     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  85
  86     // MBBMap - Mapping between LLVM BB -> Machine BB
  87     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  88
  89     // AllocaMap - Mapping from fixed sized alloca instructions to the
  90     // FrameIndex for the alloca.
  91     std::map<AllocaInst*, unsigned> AllocaMap;
  92
  93     ISel(TargetMachine &tm) : TM(tm), F(0), BB(0) {}
  94
  95     /// runOnFunction - Top level implementation of instruction selection for
  96     /// the entire function.
  97     ///
  98     bool runOnFunction(Function &Fn) {
  99       // First pass over the function, lower any unknown intrinsic functions
 100       // with the IntrinsicLowering class.
 101       LowerUnknownIntrinsicFunctionCalls(Fn);
 102
 103       F = &MachineFunction::construct(&Fn, TM);
 104
 105       // Create all of the machine basic blocks for the function...
 106       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 107         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
 108
 109       BB = &F->front();
 110
 111       // Set up a frame object for the return address.  This is used by the
 112       // llvm.returnaddress & llvm.frameaddress intrinisics.
 113       ReturnAddressIndex = F->getFrameInfo()->CreateFixedObject(4, -4);
 114
 115       // Copy incoming arguments off of the stack...
 116       LoadArgumentsToVirtualRegs(Fn);
 117
 118       // Instruction select everything except PHI nodes
 119       visit(Fn);
 120
 121       // Select the PHI nodes
 122       SelectPHINodes();
 123
 124       // Insert the FP_REG_KILL instructions into blocks that need them.
 125       InsertFPRegKills();
 126
 127       RegMap.clear();
 128       MBBMap.clear();
 129       AllocaMap.clear();
 130       F = 0;
 131       // We always build a machine code representation for the function
 132       return true;
 133     }
 134
 135     virtual const char *getPassName() const {
 136       return "X86 Simple Instruction Selection";
 137     }
 138
 139     /// visitBasicBlock - This method is called when we are visiting a new basic
 140     /// block.  This simply creates a new MachineBasicBlock to emit code into
 141     /// and adds it to the current MachineFunction.  Subsequent visit* for
 142     /// instructions will be invoked for all instructions in the basic block.
 143     ///
 144     void visitBasicBlock(BasicBlock &LLVM_BB) {
 145       BB = MBBMap[&LLVM_BB];
 146     }
 147
 148     /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
 149     /// function, lowering any calls to unknown intrinsic functions into the
 150     /// equivalent LLVM code.
 151     ///
 152     void LowerUnknownIntrinsicFunctionCalls(Function &F);
 153
 154     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 155     /// from the stack into virtual registers.
 156     ///
 157     void LoadArgumentsToVirtualRegs(Function &F);
 158
 159     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 160     /// because we have to generate our sources into the source basic blocks,
 161     /// not the current one.
 162     ///
 163     void SelectPHINodes();
 164
 165     /// InsertFPRegKills - Insert FP_REG_KILL instructions into basic blocks
 166     /// that need them.  This only occurs due to the floating point stackifier
 167     /// not being aggressive enough to handle arbitrary global stackification.
 168     ///
 169     void InsertFPRegKills();
 170
 171     // Visitation methods for various instructions.  These methods simply emit
 172     // fixed X86 code for each instruction.
 173     //
 174
 175     // Control flow operators
 176     void visitReturnInst(ReturnInst &RI);
 177     void visitBranchInst(BranchInst &BI);
 178
 179     struct ValueRecord {
 180       Value *Val;
 181       unsigned Reg;
 182       const Type *Ty;
 183       ValueRecord(unsigned R, const Type *T) : Val(0), Reg(R), Ty(T) {}
 184       ValueRecord(Value *V) : Val(V), Reg(0), Ty(V->getType()) {}
 185     };
 186     void doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 187                 const std::vector<ValueRecord> &Args);
 188     void visitCallInst(CallInst &I);
 189     void visitIntrinsicCall(Intrinsic::ID ID, CallInst &I);
 190
 191     // Arithmetic operators
 192     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 193     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 194     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 195     void visitMul(BinaryOperator &B);
 196
 197     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 198     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 199     void visitDivRem(BinaryOperator &B);
 200
 201     // Bitwise operators
 202     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 203     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 204     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 205
 206     // Comparison operators...
 207     void visitSetCondInst(SetCondInst &I);
 208     unsigned EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 209                             MachineBasicBlock *MBB,
 210                             MachineBasicBlock::iterator MBBI);
 211     void visitSelectInst(SelectInst &SI);
 212
 213
 214     // Memory Instructions
 215     void visitLoadInst(LoadInst &I);
 216     void visitStoreInst(StoreInst &I);
 217     void visitGetElementPtrInst(GetElementPtrInst &I);
 218     void visitAllocaInst(AllocaInst &I);
 219     void visitMallocInst(MallocInst &I);
 220     void visitFreeInst(FreeInst &I);
 221
 222     // Other operators
 223     void visitShiftInst(ShiftInst &I);
 224     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 225     void visitCastInst(CastInst &I);
 226     void visitVANextInst(VANextInst &I);
 227     void visitVAArgInst(VAArgInst &I);
 228
 229     void visitInstruction(Instruction &I) {
 230       std::cerr << "Cannot instruction select: " << I;
 231       abort();
 232     }
 233
 234     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 235     ///
 236     void promote32(unsigned targetReg, const ValueRecord &VR);
 237
 238     /// getAddressingMode - Get the addressing mode to use to address the
 239     /// specified value.  The returned value should be used with addFullAddress.
 240     void getAddressingMode(Value *Addr, X86AddressMode &AM);
 241
 242
 243     /// getGEPIndex - This is used to fold GEP instructions into X86 addressing
 244     /// expressions.
 245     void getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
 246                      std::vector<Value*> &GEPOps,
 247                      std::vector<const Type*> &GEPTypes,
 248                      X86AddressMode &AM);
 249
 250     /// isGEPFoldable - Return true if the specified GEP can be completely
 251     /// folded into the addressing mode of a load/store or lea instruction.
 252     bool isGEPFoldable(MachineBasicBlock *MBB,
 253                        Value *Src, User::op_iterator IdxBegin,
 254                        User::op_iterator IdxEnd, X86AddressMode &AM);
 255
 256     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 257     /// constant expression GEP support.
 258     ///
 259     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
 260                           Value *Src, User::op_iterator IdxBegin,
 261                           User::op_iterator IdxEnd, unsigned TargetReg);
 262
 263     /// emitCastOperation - Common code shared between visitCastInst and
 264     /// constant expression cast support.
 265     ///
 266     void emitCastOperation(MachineBasicBlock *BB,MachineBasicBlock::iterator IP,
 267                            Value *Src, const Type *DestTy, unsigned TargetReg);
 268
 269     /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
 270     /// and constant expression support.
 271     ///
 272     void emitSimpleBinaryOperation(MachineBasicBlock *BB,
 273                                    MachineBasicBlock::iterator IP,
 274                                    Value *Op0, Value *Op1,
 275                                    unsigned OperatorClass, unsigned TargetReg);
 276
 277     /// emitBinaryFPOperation - This method handles emission of floating point
 278     /// Add (0), Sub (1), Mul (2), and Div (3) operations.
 279     void emitBinaryFPOperation(MachineBasicBlock *BB,
 280                                MachineBasicBlock::iterator IP,
 281                                Value *Op0, Value *Op1,
 282                                unsigned OperatorClass, unsigned TargetReg);
 283
 284     void emitMultiply(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
 285                       Value *Op0, Value *Op1, unsigned TargetReg);
 286
 287     void doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
 288                     unsigned DestReg, const Type *DestTy,
 289                     unsigned Op0Reg, unsigned Op1Reg);
 290     void doMultiplyConst(MachineBasicBlock *MBB,
 291                          MachineBasicBlock::iterator MBBI,
 292                          unsigned DestReg, const Type *DestTy,
 293                          unsigned Op0Reg, unsigned Op1Val);
 294
 295     void emitDivRemOperation(MachineBasicBlock *BB,
 296                              MachineBasicBlock::iterator IP,
 297                              Value *Op0, Value *Op1, bool isDiv,
 298                              unsigned TargetReg);
 299
 300     /// emitSetCCOperation - Common code shared between visitSetCondInst and
 301     /// constant expression support.
 302     ///
 303     void emitSetCCOperation(MachineBasicBlock *BB,
 304                             MachineBasicBlock::iterator IP,
 305                             Value *Op0, Value *Op1, unsigned Opcode,
 306                             unsigned TargetReg);
 307
 308     /// emitShiftOperation - Common code shared between visitShiftInst and
 309     /// constant expression support.
 310     ///
 311     void emitShiftOperation(MachineBasicBlock *MBB,
 312                             MachineBasicBlock::iterator IP,
 313                             Value *Op, Value *ShiftAmount, bool isLeftShift,
 314                             const Type *ResultTy, unsigned DestReg);
 315
 316     /// emitSelectOperation - Common code shared between visitSelectInst and the
 317     /// constant expression support.
 318     void emitSelectOperation(MachineBasicBlock *MBB,
 319                              MachineBasicBlock::iterator IP,
 320                              Value *Cond, Value *TrueVal, Value *FalseVal,
 321                              unsigned DestReg);
 322
 323     /// copyConstantToRegister - Output the instructions required to put the
 324     /// specified constant into the specified register.
 325     ///
 326     void copyConstantToRegister(MachineBasicBlock *MBB,
 327                                 MachineBasicBlock::iterator MBBI,
 328                                 Constant *C, unsigned Reg);
 329
 330     void emitUCOMr(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
 331                    unsigned LHS, unsigned RHS);
 332
 333     /// makeAnotherReg - This method returns the next register number we haven't
 334     /// yet used.
 335     ///
 336     /// Long values are handled somewhat specially.  They are always allocated
 337     /// as pairs of 32 bit integer values.  The register number returned is the
 338     /// lower 32 bits of the long value, and the regNum+1 is the upper 32 bits
 339     /// of the long value.
 340     ///
 341     unsigned makeAnotherReg(const Type *Ty) {
 342       assert(dynamic_cast<const X86RegisterInfo*>(TM.getRegisterInfo()) &&
 343              "Current target doesn't have X86 reg info??");
 344       const X86RegisterInfo *MRI =
 345         static_cast<const X86RegisterInfo*>(TM.getRegisterInfo());
 346       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 347         const TargetRegisterClass *RC = MRI->getRegClassForType(Type::IntTy);
 348         // Create the lower part
 349         F->getSSARegMap()->createVirtualRegister(RC);
 350         // Create the upper part.
 351         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 352       }
 353
 354       // Add the mapping of regnumber => reg class to MachineFunction
 355       const TargetRegisterClass *RC = MRI->getRegClassForType(Ty);
 356       return F->getSSARegMap()->createVirtualRegister(RC);
 357     }
 358
 359     /// getReg - This method turns an LLVM value into a register number.
 360     ///
 361     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 362     unsigned getReg(Value *V) {
 363       // Just append to the end of the current bb.
 364       MachineBasicBlock::iterator It = BB->end();
 365       return getReg(V, BB, It);
 366     }
 367     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 368                     MachineBasicBlock::iterator IPt);
 369
 370     /// getFixedSizedAllocaFI - Return the frame index for a fixed sized alloca
 371     /// that is to be statically allocated with the initial stack frame
 372     /// adjustment.
 373     unsigned getFixedSizedAllocaFI(AllocaInst *AI);
 374   };
 375 }
 376
 377 /// dyn_castFixedAlloca - If the specified value is a fixed size alloca
 378 /// instruction in the entry block, return it.  Otherwise, return a null
 379 /// pointer.
 380 static AllocaInst *dyn_castFixedAlloca(Value *V) {
 381   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 382     BasicBlock *BB = AI->getParent();
 383     if (isa<ConstantUInt>(AI->getArraySize()) && BB ==&BB->getParent()->front())
 384       return AI;
 385   }
 386   return 0;
 387 }
 388
 389 /// getReg - This method turns an LLVM value into a register number.
 390 ///
 391 unsigned ISel::getReg(Value *V, MachineBasicBlock *MBB,
 392                       MachineBasicBlock::iterator IPt) {
 393   // If this operand is a constant, emit the code to copy the constant into
 394   // the register here...
 395   if (Constant *C = dyn_cast<Constant>(V)) {
 396     unsigned Reg = makeAnotherReg(V->getType());
 397     copyConstantToRegister(MBB, IPt, C, Reg);
 398     return Reg;
 399   } else if (CastInst *CI = dyn_cast<CastInst>(V)) {
 400     // Do not emit noop casts at all, unless it's a double -> float cast.
 401     if (getClassB(CI->getType()) == getClassB(CI->getOperand(0)->getType()) &&
 402         (CI->getType() != Type::FloatTy ||
 403          CI->getOperand(0)->getType() != Type::DoubleTy))
 404       return getReg(CI->getOperand(0), MBB, IPt);
 405   } else if (AllocaInst *AI = dyn_castFixedAlloca(V)) {
 406     // If the alloca address couldn't be folded into the instruction addressing,
 407     // emit an explicit LEA as appropriate.
 408     unsigned Reg = makeAnotherReg(V->getType());
 409     unsigned FI = getFixedSizedAllocaFI(AI);
 410     addFrameReference(BuildMI(*MBB, IPt, X86::LEA32r, 4, Reg), FI);
 411     return Reg;
 412   }
 413
 414   unsigned &Reg = RegMap[V];
 415   if (Reg == 0) {
 416     Reg = makeAnotherReg(V->getType());
 417     RegMap[V] = Reg;
 418   }
 419
 420   return Reg;
 421 }
 422
 423 /// getFixedSizedAllocaFI - Return the frame index for a fixed sized alloca
 424 /// that is to be statically allocated with the initial stack frame
 425 /// adjustment.
 426 unsigned ISel::getFixedSizedAllocaFI(AllocaInst *AI) {
 427   // Already computed this?
 428   std::map<AllocaInst*, unsigned>::iterator I = AllocaMap.lower_bound(AI);
 429   if (I != AllocaMap.end() && I->first == AI) return I->second;
 430
 431   const Type *Ty = AI->getAllocatedType();
 432   ConstantUInt *CUI = cast<ConstantUInt>(AI->getArraySize());
 433   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
 434   TySize *= CUI->getValue();   // Get total allocated size...
 435   unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
 436
 437   // Create a new stack object using the frame manager...
 438   int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
 439   AllocaMap.insert(I, std::make_pair(AI, FrameIdx));
 440   return FrameIdx;
 441 }
 442
 443
 444 /// copyConstantToRegister - Output the instructions required to put the
 445 /// specified constant into the specified register.
 446 ///
 447 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 448                                   MachineBasicBlock::iterator IP,
 449                                   Constant *C, unsigned R) {
 450   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 451     unsigned Class = 0;
 452     switch (CE->getOpcode()) {
 453     case Instruction::GetElementPtr:
 454       emitGEPOperation(MBB, IP, CE->getOperand(0),
 455                        CE->op_begin()+1, CE->op_end(), R);
 456       return;
 457     case Instruction::Cast:
 458       emitCastOperation(MBB, IP, CE->getOperand(0), CE->getType(), R);
 459       return;
 460
 461     case Instruction::Xor: ++Class; // FALL THROUGH
 462     case Instruction::Or:  ++Class; // FALL THROUGH
 463     case Instruction::And: ++Class; // FALL THROUGH
 464     case Instruction::Sub: ++Class; // FALL THROUGH
 465     case Instruction::Add:
 466       emitSimpleBinaryOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 467                                 Class, R);
 468       return;
 469
 470     case Instruction::Mul:
 471       emitMultiply(MBB, IP, CE->getOperand(0), CE->getOperand(1), R);
 472       return;
 473
 474     case Instruction::Div:
 475     case Instruction::Rem:
 476       emitDivRemOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 477                           CE->getOpcode() == Instruction::Div, R);
 478       return;
 479
 480     case Instruction::SetNE:
 481     case Instruction::SetEQ:
 482     case Instruction::SetLT:
 483     case Instruction::SetGT:
 484     case Instruction::SetLE:
 485     case Instruction::SetGE:
 486       emitSetCCOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 487                          CE->getOpcode(), R);
 488       return;
 489
 490     case Instruction::Shl:
 491     case Instruction::Shr:
 492       emitShiftOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 493                          CE->getOpcode() == Instruction::Shl, CE->getType(), R);
 494       return;
 495
 496     case Instruction::Select:
 497       emitSelectOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 498                           CE->getOperand(2), R);
 499       return;
 500
 501     default:
 502       std::cerr << "Offending expr: " << *C << "\n";
 503       assert(0 && "Constant expression not yet handled!\n");
 504     }
 505   }
 506
 507   if (C->getType()->isIntegral()) {
 508     unsigned Class = getClassB(C->getType());
 509
 510     if (Class == cLong) {
 511       // Copy the value into the register pair.
 512       uint64_t Val = cast<ConstantInt>(C)->getRawValue();
 513       BuildMI(*MBB, IP, X86::MOV32ri, 1, R).addImm(Val & 0xFFFFFFFF);
 514       BuildMI(*MBB, IP, X86::MOV32ri, 1, R+1).addImm(Val >> 32);
 515       return;
 516     }
 517
 518     assert(Class <= cInt && "Type not handled yet!");
 519
 520     static const unsigned IntegralOpcodeTab[] = {
 521       X86::MOV8ri, X86::MOV16ri, X86::MOV32ri
 522     };
 523
 524     if (C->getType() == Type::BoolTy) {
 525       BuildMI(*MBB, IP, X86::MOV8ri, 1, R).addImm(C == ConstantBool::True);
 526     } else {
 527       ConstantInt *CI = cast<ConstantInt>(C);
 528       BuildMI(*MBB, IP, IntegralOpcodeTab[Class],1,R).addImm(CI->getRawValue());
 529     }
 530   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 531     if (CFP->isExactlyValue(+0.0))
 532       BuildMI(*MBB, IP, X86::FLD0, 0, R);
 533     else if (CFP->isExactlyValue(+1.0))
 534       BuildMI(*MBB, IP, X86::FLD1, 0, R);
 535     else {
 536       // Otherwise we need to spill the constant to memory...
 537       MachineConstantPool *CP = F->getConstantPool();
 538       unsigned CPI = CP->getConstantPoolIndex(CFP);
 539       const Type *Ty = CFP->getType();
 540
 541       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
 542       unsigned LoadOpcode = Ty == Type::FloatTy ? X86::FLD32m : X86::FLD64m;
 543       addConstantPoolReference(BuildMI(*MBB, IP, LoadOpcode, 4, R), CPI);
 544     }
 545
 546   } else if (isa<ConstantPointerNull>(C)) {
 547     // Copy zero (null pointer) to the register.
 548     BuildMI(*MBB, IP, X86::MOV32ri, 1, R).addImm(0);
 549   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
 550     BuildMI(*MBB, IP, X86::MOV32ri, 1, R).addGlobalAddress(GV);
 551   } else {
 552     std::cerr << "Offending constant: " << *C << "\n";
 553     assert(0 && "Type not handled yet!");
 554   }
 555 }
 556
 557 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 558 /// the stack into virtual registers.
 559 ///
 560 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 561   // Emit instructions to load the arguments...  On entry to a function on the
 562   // X86, the stack frame looks like this:
 563   //
 564   // [ESP] -- return address
 565   // [ESP + 4] -- first argument (leftmost lexically)
 566   // [ESP + 8] -- second argument, if first argument is four bytes in size
 567   //    ...
 568   //
 569   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 570   MachineFrameInfo *MFI = F->getFrameInfo();
 571
 572   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 573     bool ArgLive = !I->use_empty();
 574     unsigned Reg = ArgLive ? getReg(*I) : 0;
 575     int FI;          // Frame object index
 576
 577     switch (getClassB(I->getType())) {
 578     case cByte:
 579       if (ArgLive) {
 580         FI = MFI->CreateFixedObject(1, ArgOffset);
 581         addFrameReference(BuildMI(BB, X86::MOV8rm, 4, Reg), FI);
 582       }
 583       break;
 584     case cShort:
 585       if (ArgLive) {
 586         FI = MFI->CreateFixedObject(2, ArgOffset);
 587         addFrameReference(BuildMI(BB, X86::MOV16rm, 4, Reg), FI);
 588       }
 589       break;
 590     case cInt:
 591       if (ArgLive) {
 592         FI = MFI->CreateFixedObject(4, ArgOffset);
 593         addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Reg), FI);
 594       }
 595       break;
 596     case cLong:
 597       if (ArgLive) {
 598         FI = MFI->CreateFixedObject(8, ArgOffset);
 599         addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Reg), FI);
 600         addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Reg+1), FI, 4);
 601       }
 602       ArgOffset += 4;   // longs require 4 additional bytes
 603       break;
 604     case cFP:
 605       if (ArgLive) {
 606         unsigned Opcode;
 607         if (I->getType() == Type::FloatTy) {
 608           Opcode = X86::FLD32m;
 609           FI = MFI->CreateFixedObject(4, ArgOffset);
 610         } else {
 611           Opcode = X86::FLD64m;
 612           FI = MFI->CreateFixedObject(8, ArgOffset);
 613         }
 614         addFrameReference(BuildMI(BB, Opcode, 4, Reg), FI);
 615       }
 616       if (I->getType() == Type::DoubleTy)
 617         ArgOffset += 4;   // doubles require 4 additional bytes
 618       break;
 619     default:
 620       assert(0 && "Unhandled argument type!");
 621     }
 622     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 623   }
 624
 625   // If the function takes variable number of arguments, add a frame offset for
 626   // the start of the first vararg value... this is used to expand
 627   // llvm.va_start.
 628   if (Fn.getFunctionType()->isVarArg())
 629     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 630 }
 631
 632
 633 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 634 /// because we have to generate our sources into the source basic blocks, not
 635 /// the current one.
 636 ///
 637 void ISel::SelectPHINodes() {
 638   const TargetInstrInfo &TII = *TM.getInstrInfo();
 639   const Function &LF = *F->getFunction();  // The LLVM function...
 640   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 641     const BasicBlock *BB = I;
 642     MachineBasicBlock &MBB = *MBBMap[I];
 643
 644     // Loop over all of the PHI nodes in the LLVM basic block...
 645     MachineBasicBlock::iterator PHIInsertPoint = MBB.begin();
 646     for (BasicBlock::const_iterator I = BB->begin();
 647          PHINode *PN = const_cast<PHINode*>(dyn_cast<PHINode>(I)); ++I) {
 648
 649       // Create a new machine instr PHI node, and insert it.
 650       unsigned PHIReg = getReg(*PN);
 651       MachineInstr *PhiMI = BuildMI(MBB, PHIInsertPoint,
 652                                     X86::PHI, PN->getNumOperands(), PHIReg);
 653
 654       MachineInstr *LongPhiMI = 0;
 655       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy)
 656         LongPhiMI = BuildMI(MBB, PHIInsertPoint,
 657                             X86::PHI, PN->getNumOperands(), PHIReg+1);
 658
 659       // PHIValues - Map of blocks to incoming virtual registers.  We use this
 660       // so that we only initialize one incoming value for a particular block,
 661       // even if the block has multiple entries in the PHI node.
 662       //
 663       std::map<MachineBasicBlock*, unsigned> PHIValues;
 664
 665       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 666         MachineBasicBlock *PredMBB = MBBMap[PN->getIncomingBlock(i)];
 667         unsigned ValReg;
 668         std::map<MachineBasicBlock*, unsigned>::iterator EntryIt =
 669           PHIValues.lower_bound(PredMBB);
 670
 671         if (EntryIt != PHIValues.end() && EntryIt->first == PredMBB) {
 672           // We already inserted an initialization of the register for this
 673           // predecessor.  Recycle it.
 674           ValReg = EntryIt->second;
 675
 676         } else {
 677           // Get the incoming value into a virtual register.
 678           //
 679           Value *Val = PN->getIncomingValue(i);
 680
 681           // If this is a constant or GlobalValue, we may have to insert code
 682           // into the basic block to compute it into a virtual register.
 683           if ((isa<Constant>(Val) && !isa<ConstantExpr>(Val))) {
 684             // Simple constants get emitted at the end of the basic block,
 685             // before any terminator instructions.  We "know" that the code to
 686             // move a constant into a register will never clobber any flags.
 687             ValReg = getReg(Val, PredMBB, PredMBB->getFirstTerminator());
 688           } else {
 689             // Because we don't want to clobber any values which might be in
 690             // physical registers with the computation of this constant (which
 691             // might be arbitrarily complex if it is a constant expression),
 692             // just insert the computation at the top of the basic block.
 693             MachineBasicBlock::iterator PI = PredMBB->begin();
 694
 695             // Skip over any PHI nodes though!
 696             while (PI != PredMBB->end() && PI->getOpcode() == X86::PHI)
 697               ++PI;
 698
 699             ValReg = getReg(Val, PredMBB, PI);
 700           }
 701
 702           // Remember that we inserted a value for this PHI for this predecessor
 703           PHIValues.insert(EntryIt, std::make_pair(PredMBB, ValReg));
 704         }
 705
 706         PhiMI->addRegOperand(ValReg);
 707         PhiMI->addMachineBasicBlockOperand(PredMBB);
 708         if (LongPhiMI) {
 709           LongPhiMI->addRegOperand(ValReg+1);
 710           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 711         }
 712       }
 713
 714       // Now that we emitted all of the incoming values for the PHI node, make
 715       // sure to reposition the InsertPoint after the PHI that we just added.
 716       // This is needed because we might have inserted a constant into this
 717       // block, right after the PHI's which is before the old insert point!
 718       PHIInsertPoint = LongPhiMI ? LongPhiMI : PhiMI;
 719       ++PHIInsertPoint;
 720     }
 721   }
 722 }
 723
 724 /// RequiresFPRegKill - The floating point stackifier pass cannot insert
 725 /// compensation code on critical edges.  As such, it requires that we kill all
 726 /// FP registers on the exit from any blocks that either ARE critical edges, or
 727 /// branch to a block that has incoming critical edges.
 728 ///
 729 /// Note that this kill instruction will eventually be eliminated when
 730 /// restrictions in the stackifier are relaxed.
 731 ///
 732 static bool RequiresFPRegKill(const MachineBasicBlock *MBB) {
 733 #if 0
 734   const BasicBlock *BB = MBB->getBasicBlock ();
 735   for (succ_const_iterator SI = succ_begin(BB), E = succ_end(BB); SI!=E; ++SI) {
 736     const BasicBlock *Succ = *SI;
 737     pred_const_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
 738     ++PI;  // Block have at least one predecessory
 739     if (PI != PE) {             // If it has exactly one, this isn't crit edge
 740       // If this block has more than one predecessor, check all of the
 741       // predecessors to see if they have multiple successors.  If so, then the
 742       // block we are analyzing needs an FPRegKill.
 743       for (PI = pred_begin(Succ); PI != PE; ++PI) {
 744         const BasicBlock *Pred = *PI;
 745         succ_const_iterator SI2 = succ_begin(Pred);
 746         ++SI2;  // There must be at least one successor of this block.
 747         if (SI2 != succ_end(Pred))
 748           return true;   // Yes, we must insert the kill on this edge.
 749       }
 750     }
 751   }
 752   // If we got this far, there is no need to insert the kill instruction.
 753   return false;
 754 #else
 755   return true;
 756 #endif
 757 }
 758
 759 // InsertFPRegKills - Insert FP_REG_KILL instructions into basic blocks that
 760 // need them.  This only occurs due to the floating point stackifier not being
 761 // aggressive enough to handle arbitrary global stackification.
 762 //
 763 // Currently we insert an FP_REG_KILL instruction into each block that uses or
 764 // defines a floating point virtual register.
 765 //
 766 // When the global register allocators (like linear scan) finally update live
 767 // variable analysis, we can keep floating point values in registers across
 768 // portions of the CFG that do not involve critical edges.  This will be a big
 769 // win, but we are waiting on the global allocators before we can do this.
 770 //
 771 // With a bit of work, the floating point stackifier pass can be enhanced to
 772 // break critical edges as needed (to make a place to put compensation code),
 773 // but this will require some infrastructure improvements as well.
 774 //
 775 void ISel::InsertFPRegKills() {
 776   SSARegMap &RegMap = *F->getSSARegMap();
 777
 778   for (MachineFunction::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 779     for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
 780       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 781       MachineOperand& MO = I->getOperand(i);
 782         if (MO.isRegister() && MO.getReg()) {
 783           unsigned Reg = MO.getReg();
 784           if (MRegisterInfo::isVirtualRegister(Reg))
 785             if (RegMap.getRegClass(Reg)->getSize() == 10)
 786               goto UsesFPReg;
 787         }
 788       }
 789     // If we haven't found an FP register use or def in this basic block, check
 790     // to see if any of our successors has an FP PHI node, which will cause a
 791     // copy to be inserted into this block.
 792     for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(),
 793          SE = BB->succ_end(); SI != SE; ++SI) {
 794       MachineBasicBlock *SBB = *SI;
 795       for (MachineBasicBlock::iterator I = SBB->begin();
 796            I != SBB->end() && I->getOpcode() == X86::PHI; ++I) {
 797         if (RegMap.getRegClass(I->getOperand(0).getReg())->getSize() == 10)
 798           goto UsesFPReg;
 799       }
 800     }
 801     continue;
 802   UsesFPReg:
 803     // Okay, this block uses an FP register.  If the block has successors (ie,
 804     // it's not an unwind/return), insert the FP_REG_KILL instruction.
 805     if (BB->succ_size () && RequiresFPRegKill(BB)) {
 806       BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
 807       ++NumFPKill;
 808     }
 809   }
 810 }
 811
 812
 813 void ISel::getAddressingMode(Value *Addr, X86AddressMode &AM) {
 814   AM.BaseType = X86AddressMode::RegBase;
 815   AM.Base.Reg = 0; AM.Scale = 1; AM.IndexReg = 0; AM.Disp = 0;
 816   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) {
 817     if (isGEPFoldable(BB, GEP->getOperand(0), GEP->op_begin()+1, GEP->op_end(),
 818                        AM))
 819       return;
 820   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
 821     if (CE->getOpcode() == Instruction::GetElementPtr)
 822       if (isGEPFoldable(BB, CE->getOperand(0), CE->op_begin()+1, CE->op_end(),
 823                         AM))
 824         return;
 825   } else if (AllocaInst *AI = dyn_castFixedAlloca(Addr)) {
 826     AM.BaseType = X86AddressMode::FrameIndexBase;
 827     AM.Base.FrameIndex = getFixedSizedAllocaFI(AI);
 828     return;
 829   }
 830
 831   // If it's not foldable, reset addr mode.
 832   AM.BaseType = X86AddressMode::RegBase;
 833   AM.Base.Reg = getReg(Addr);
 834   AM.Scale = 1; AM.IndexReg = 0; AM.Disp = 0;
 835 }
 836
 837 // canFoldSetCCIntoBranchOrSelect - Return the setcc instruction if we can fold
 838 // it into the conditional branch or select instruction which is the only user
 839 // of the cc instruction.  This is the case if the conditional branch is the
 840 // only user of the setcc.  We also don't handle long arguments below, so we
 841 // reject them here as well.
 842 //
 843 static SetCondInst *canFoldSetCCIntoBranchOrSelect(Value *V) {
 844   if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 845     if (SCI->hasOneUse()) {
 846       Instruction *User = cast<Instruction>(SCI->use_back());
 847       if ((isa<BranchInst>(User) || isa<SelectInst>(User)) &&
 848           (getClassB(SCI->getOperand(0)->getType()) != cLong ||
 849            SCI->getOpcode() == Instruction::SetEQ ||
 850            SCI->getOpcode() == Instruction::SetNE))
 851         return SCI;
 852     }
 853   return 0;
 854 }
 855
 856 // Return a fixed numbering for setcc instructions which does not depend on the
 857 // order of the opcodes.
 858 //
 859 static unsigned getSetCCNumber(unsigned Opcode) {
 860   switch(Opcode) {
 861   default: assert(0 && "Unknown setcc instruction!");
 862   case Instruction::SetEQ: return 0;
 863   case Instruction::SetNE: return 1;
 864   case Instruction::SetLT: return 2;
 865   case Instruction::SetGE: return 3;
 866   case Instruction::SetGT: return 4;
 867   case Instruction::SetLE: return 5;
 868   }
 869 }
 870
 871 // LLVM  -> X86 signed  X86 unsigned
 872 // -----    ----------  ------------
 873 // seteq -> sete        sete
 874 // setne -> setne       setne
 875 // setlt -> setl        setb
 876 // setge -> setge       setae
 877 // setgt -> setg        seta
 878 // setle -> setle       setbe
 879 // ----
 880 //          sets                       // Used by comparison with 0 optimization
 881 //          setns
 882 static const unsigned SetCCOpcodeTab[2][8] = {
 883   { X86::SETEr, X86::SETNEr, X86::SETBr, X86::SETAEr, X86::SETAr, X86::SETBEr,
 884     0, 0 },
 885   { X86::SETEr, X86::SETNEr, X86::SETLr, X86::SETGEr, X86::SETGr, X86::SETLEr,
 886     X86::SETSr, X86::SETNSr },
 887 };
 888
 889 /// emitUCOMr - In the future when we support processors before the P6, this
 890 /// wraps the logic for emitting an FUCOMr vs FUCOMIr.
 891 void ISel::emitUCOMr(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
 892                      unsigned LHS, unsigned RHS) {
 893   if (0) { // for processors prior to the P6
 894     BuildMI(*MBB, IP, X86::FUCOMr, 2).addReg(LHS).addReg(RHS);
 895     BuildMI(*MBB, IP, X86::FNSTSW8r, 0);
 896     BuildMI(*MBB, IP, X86::SAHF, 1);
 897   } else {
 898     BuildMI(*MBB, IP, X86::FUCOMIr, 2).addReg(LHS).addReg(RHS);
 899   }
 900 }
 901
 902 // EmitComparison - This function emits a comparison of the two operands,
 903 // returning the extended setcc code to use.
 904 unsigned ISel::EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 905                               MachineBasicBlock *MBB,
 906                               MachineBasicBlock::iterator IP) {
 907   // The arguments are already supposed to be of the same type.
 908   const Type *CompTy = Op0->getType();
 909   unsigned Class = getClassB(CompTy);
 910   unsigned Op0r = getReg(Op0, MBB, IP);
 911
 912   // Special case handling of: cmp R, i
 913   if (isa<ConstantPointerNull>(Op1)) {
 914     if (OpNum < 2)    // seteq/setne -> test
 915       BuildMI(*MBB, IP, X86::TEST32rr, 2).addReg(Op0r).addReg(Op0r);
 916     else
 917       BuildMI(*MBB, IP, X86::CMP32ri, 2).addReg(Op0r).addImm(0);
 918     return OpNum;
 919
 920   } else if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 921     if (Class == cByte || Class == cShort || Class == cInt) {
 922       unsigned Op1v = CI->getRawValue();
 923
 924       // Mask off any upper bits of the constant, if there are any...
 925       Op1v &= (1ULL << (8 << Class)) - 1;
 926
 927       // If this is a comparison against zero, emit more efficient code.  We
 928       // can't handle unsigned comparisons against zero unless they are == or
 929       // !=.  These should have been strength reduced already anyway.
 930       if (Op1v == 0 && (CompTy->isSigned() || OpNum < 2)) {
 931         static const unsigned TESTTab[] = {
 932           X86::TEST8rr, X86::TEST16rr, X86::TEST32rr
 933         };
 934         BuildMI(*MBB, IP, TESTTab[Class], 2).addReg(Op0r).addReg(Op0r);
 935
 936         if (OpNum == 2) return 6;   // Map jl -> js
 937         if (OpNum == 3) return 7;   // Map jg -> jns
 938         return OpNum;
 939       }
 940
 941       static const unsigned CMPTab[] = {
 942         X86::CMP8ri, X86::CMP16ri, X86::CMP32ri
 943       };
 944
 945       BuildMI(*MBB, IP, CMPTab[Class], 2).addReg(Op0r).addImm(Op1v);
 946       return OpNum;
 947     } else {
 948       assert(Class == cLong && "Unknown integer class!");
 949       unsigned LowCst = CI->getRawValue();
 950       unsigned HiCst = CI->getRawValue() >> 32;
 951       if (OpNum < 2) {    // seteq, setne
 952         unsigned LoTmp = Op0r;
 953         if (LowCst != 0) {
 954           LoTmp = makeAnotherReg(Type::IntTy);
 955           BuildMI(*MBB, IP, X86::XOR32ri, 2, LoTmp).addReg(Op0r).addImm(LowCst);
 956         }
 957         unsigned HiTmp = Op0r+1;
 958         if (HiCst != 0) {
 959           HiTmp = makeAnotherReg(Type::IntTy);
 960           BuildMI(*MBB, IP, X86::XOR32ri, 2,HiTmp).addReg(Op0r+1).addImm(HiCst);
 961         }
 962         unsigned FinalTmp = makeAnotherReg(Type::IntTy);
 963         BuildMI(*MBB, IP, X86::OR32rr, 2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
 964         return OpNum;
 965       } else {
 966         // Emit a sequence of code which compares the high and low parts once
 967         // each, then uses a conditional move to handle the overflow case.  For
 968         // example, a setlt for long would generate code like this:
 969         //
 970         // AL = lo(op1) < lo(op2)   // Always unsigned comparison
 971         // BL = hi(op1) < hi(op2)   // Signedness depends on operands
 972         // dest = hi(op1) == hi(op2) ? BL : AL;
 973         //
 974
 975         // FIXME: This would be much better if we had hierarchical register
 976         // classes!  Until then, hardcode registers so that we can deal with
 977         // their aliases (because we don't have conditional byte moves).
 978         //
 979         BuildMI(*MBB, IP, X86::CMP32ri, 2).addReg(Op0r).addImm(LowCst);
 980         BuildMI(*MBB, IP, SetCCOpcodeTab[0][OpNum], 0, X86::AL);
 981         BuildMI(*MBB, IP, X86::CMP32ri, 2).addReg(Op0r+1).addImm(HiCst);
 982         BuildMI(*MBB, IP, SetCCOpcodeTab[CompTy->isSigned()][OpNum], 0,X86::BL);
 983         BuildMI(*MBB, IP, X86::IMPLICIT_DEF, 0, X86::BH);
 984         BuildMI(*MBB, IP, X86::IMPLICIT_DEF, 0, X86::AH);
 985         BuildMI(*MBB, IP, X86::CMOVE16rr, 2, X86::BX).addReg(X86::BX)
 986           .addReg(X86::AX);
 987         // NOTE: visitSetCondInst knows that the value is dumped into the BL
 988         // register at this point for long values...
 989         return OpNum;
 990       }
 991     }
 992   }
 993
 994   // Special case handling of comparison against +/- 0.0
 995   if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op1))
 996     if (CFP->isExactlyValue(+0.0) || CFP->isExactlyValue(-0.0)) {
 997       BuildMI(*MBB, IP, X86::FTST, 1).addReg(Op0r);
 998       BuildMI(*MBB, IP, X86::FNSTSW8r, 0);
 999       BuildMI(*MBB, IP, X86::SAHF, 1);
1000       return OpNum;
1001     }
1002
1003   unsigned Op1r = getReg(Op1, MBB, IP);
1004   switch (Class) {
1005   default: assert(0 && "Unknown type class!");
1006     // Emit: cmp <var1>, <var2> (do the comparison).  We can
1007     // compare 8-bit with 8-bit, 16-bit with 16-bit, 32-bit with
1008     // 32-bit.
1009   case cByte:
1010     BuildMI(*MBB, IP, X86::CMP8rr, 2).addReg(Op0r).addReg(Op1r);
1011     break;
1012   case cShort:
1013     BuildMI(*MBB, IP, X86::CMP16rr, 2).addReg(Op0r).addReg(Op1r);
1014     break;
1015   case cInt:
1016     BuildMI(*MBB, IP, X86::CMP32rr, 2).addReg(Op0r).addReg(Op1r);
1017     break;
1018   case cFP:
1019     emitUCOMr(MBB, IP, Op0r, Op1r);
1020     break;
1021
1022   case cLong:
1023     if (OpNum < 2) {    // seteq, setne
1024       unsigned LoTmp = makeAnotherReg(Type::IntTy);
1025       unsigned HiTmp = makeAnotherReg(Type::IntTy);
1026       unsigned FinalTmp = makeAnotherReg(Type::IntTy);
1027       BuildMI(*MBB, IP, X86::XOR32rr, 2, LoTmp).addReg(Op0r).addReg(Op1r);
1028       BuildMI(*MBB, IP, X86::XOR32rr, 2, HiTmp).addReg(Op0r+1).addReg(Op1r+1);
1029       BuildMI(*MBB, IP, X86::OR32rr,  2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
1030       break;  // Allow the sete or setne to be generated from flags set by OR
1031     } else {
1032       // Emit a sequence of code which compares the high and low parts once
1033       // each, then uses a conditional move to handle the overflow case.  For
1034       // example, a setlt for long would generate code like this:
1035       //
1036       // AL = lo(op1) < lo(op2)   // Signedness depends on operands
1037       // BL = hi(op1) < hi(op2)   // Always unsigned comparison
1038       // dest = hi(op1) == hi(op2) ? BL : AL;
1039       //
1040
1041       // FIXME: This would be much better if we had hierarchical register
1042       // classes!  Until then, hardcode registers so that we can deal with their
1043       // aliases (because we don't have conditional byte moves).
1044       //
1045       BuildMI(*MBB, IP, X86::CMP32rr, 2).addReg(Op0r).addReg(Op1r);
1046       BuildMI(*MBB, IP, SetCCOpcodeTab[0][OpNum], 0, X86::AL);
1047       BuildMI(*MBB, IP, X86::CMP32rr, 2).addReg(Op0r+1).addReg(Op1r+1);
1048       BuildMI(*MBB, IP, SetCCOpcodeTab[CompTy->isSigned()][OpNum], 0, X86::BL);
1049       BuildMI(*MBB, IP, X86::IMPLICIT_DEF, 0, X86::BH);
1050       BuildMI(*MBB, IP, X86::IMPLICIT_DEF, 0, X86::AH);
1051       BuildMI(*MBB, IP, X86::CMOVE16rr, 2, X86::BX).addReg(X86::BX)
1052                                                    .addReg(X86::AX);
1053       // NOTE: visitSetCondInst knows that the value is dumped into the BL
1054       // register at this point for long values...
1055       return OpNum;
1056     }
1057   }
1058   return OpNum;
1059 }
1060
1061 /// SetCC instructions - Here we just emit boilerplate code to set a byte-sized
1062 /// register, then move it to wherever the result should be.
1063 ///
1064 void ISel::visitSetCondInst(SetCondInst &I) {
1065   if (canFoldSetCCIntoBranchOrSelect(&I))
1066     return;  // Fold this into a branch or select.
1067
1068   unsigned DestReg = getReg(I);
1069   MachineBasicBlock::iterator MII = BB->end();
1070   emitSetCCOperation(BB, MII, I.getOperand(0), I.getOperand(1), I.getOpcode(),
1071                      DestReg);
1072 }
1073
1074 /// emitSetCCOperation - Common code shared between visitSetCondInst and
1075 /// constant expression support.
1076 ///
1077 void ISel::emitSetCCOperation(MachineBasicBlock *MBB,
1078                               MachineBasicBlock::iterator IP,
1079                               Value *Op0, Value *Op1, unsigned Opcode,
1080                               unsigned TargetReg) {
1081   unsigned OpNum = getSetCCNumber(Opcode);
1082   OpNum = EmitComparison(OpNum, Op0, Op1, MBB, IP);
1083
1084   const Type *CompTy = Op0->getType();
1085   unsigned CompClass = getClassB(CompTy);
1086   bool isSigned = CompTy->isSigned() && CompClass != cFP;
1087
1088   if (CompClass != cLong || OpNum < 2) {
1089     // Handle normal comparisons with a setcc instruction...
1090     BuildMI(*MBB, IP, SetCCOpcodeTab[isSigned][OpNum], 0, TargetReg);
1091   } else {
1092     // Handle long comparisons by copying the value which is already in BL into
1093     // the register we want...
1094     BuildMI(*MBB, IP, X86::MOV8rr, 1, TargetReg).addReg(X86::BL);
1095   }
1096 }
1097
1098 void ISel::visitSelectInst(SelectInst &SI) {
1099   unsigned DestReg = getReg(SI);
1100   MachineBasicBlock::iterator MII = BB->end();
1101   emitSelectOperation(BB, MII, SI.getCondition(), SI.getTrueValue(),
1102                       SI.getFalseValue(), DestReg);
1103 }
1104
1105 /// emitSelect - Common code shared between visitSelectInst and the constant
1106 /// expression support.
1107 void ISel::emitSelectOperation(MachineBasicBlock *MBB,
1108                                MachineBasicBlock::iterator IP,
1109                                Value *Cond, Value *TrueVal, Value *FalseVal,
1110                                unsigned DestReg) {
1111   unsigned SelectClass = getClassB(TrueVal->getType());
1112
1113   // We don't support 8-bit conditional moves.  If we have incoming constants,
1114   // transform them into 16-bit constants to avoid having a run-time conversion.
1115   if (SelectClass == cByte) {
1116     if (Constant *T = dyn_cast<Constant>(TrueVal))
1117       TrueVal = ConstantExpr::getCast(T, Type::ShortTy);
1118     if (Constant *F = dyn_cast<Constant>(FalseVal))
1119       FalseVal = ConstantExpr::getCast(F, Type::ShortTy);
1120   }
1121
1122   unsigned TrueReg  = getReg(TrueVal, MBB, IP);
1123   unsigned FalseReg = getReg(FalseVal, MBB, IP);
1124   if (TrueReg == FalseReg) {
1125     static const unsigned Opcode[] = {
1126       X86::MOV8rr, X86::MOV16rr, X86::MOV32rr, X86::FpMOV, X86::MOV32rr
1127     };
1128     BuildMI(*MBB, IP, Opcode[SelectClass], 1, DestReg).addReg(TrueReg);
1129     if (SelectClass == cLong)
1130       BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg+1).addReg(TrueReg+1);
1131     return;
1132   }
1133
1134   unsigned Opcode;
1135   if (SetCondInst *SCI = canFoldSetCCIntoBranchOrSelect(Cond)) {
1136     // We successfully folded the setcc into the select instruction.
1137
1138     unsigned OpNum = getSetCCNumber(SCI->getOpcode());
1139     OpNum = EmitComparison(OpNum, SCI->getOperand(0), SCI->getOperand(1), MBB,
1140                            IP);
1141
1142     const Type *CompTy = SCI->getOperand(0)->getType();
1143     bool isSigned = CompTy->isSigned() && getClassB(CompTy) != cFP;
1144
1145     // LLVM  -> X86 signed  X86 unsigned
1146     // -----    ----------  ------------
1147     // seteq -> cmovNE      cmovNE
1148     // setne -> cmovE       cmovE
1149     // setlt -> cmovGE      cmovAE
1150     // setge -> cmovL       cmovB
1151     // setgt -> cmovLE      cmovBE
1152     // setle -> cmovG       cmovA
1153     // ----
1154     //          cmovNS              // Used by comparison with 0 optimization
1155     //          cmovS
1156
1157     switch (SelectClass) {
1158     default: assert(0 && "Unknown value class!");
1159     case cFP: {
1160       // Annoyingly, we don't have a full set of floating point conditional
1161       // moves.  :(
1162       static const unsigned OpcodeTab[2][8] = {
1163         { X86::FCMOVNE, X86::FCMOVE, X86::FCMOVAE, X86::FCMOVB,
1164           X86::FCMOVBE, X86::FCMOVA, 0, 0 },
1165         { X86::FCMOVNE, X86::FCMOVE, 0, 0, 0, 0, 0, 0 },
1166       };
1167       Opcode = OpcodeTab[isSigned][OpNum];
1168
1169       // If opcode == 0, we hit a case that we don't support.  Output a setcc
1170       // and compare the result against zero.
1171       if (Opcode == 0) {
1172         unsigned CompClass = getClassB(CompTy);
1173         unsigned CondReg;
1174         if (CompClass != cLong || OpNum < 2) {
1175           CondReg = makeAnotherReg(Type::BoolTy);
1176           // Handle normal comparisons with a setcc instruction...
1177           BuildMI(*MBB, IP, SetCCOpcodeTab[isSigned][OpNum], 0, CondReg);
1178         } else {
1179           // Long comparisons end up in the BL register.
1180           CondReg = X86::BL;
1181         }
1182
1183         BuildMI(*MBB, IP, X86::TEST8rr, 2).addReg(CondReg).addReg(CondReg);
1184         Opcode = X86::FCMOVE;
1185       }
1186       break;
1187     }
1188     case cByte:
1189     case cShort: {
1190       static const unsigned OpcodeTab[2][8] = {
1191         { X86::CMOVNE16rr, X86::CMOVE16rr, X86::CMOVAE16rr, X86::CMOVB16rr,
1192           X86::CMOVBE16rr, X86::CMOVA16rr, 0, 0 },
1193         { X86::CMOVNE16rr, X86::CMOVE16rr, X86::CMOVGE16rr, X86::CMOVL16rr,
1194           X86::CMOVLE16rr, X86::CMOVG16rr, X86::CMOVNS16rr, X86::CMOVS16rr },
1195       };
1196       Opcode = OpcodeTab[isSigned][OpNum];
1197       break;
1198     }
1199     case cInt:
1200     case cLong: {
1201       static const unsigned OpcodeTab[2][8] = {
1202         { X86::CMOVNE32rr, X86::CMOVE32rr, X86::CMOVAE32rr, X86::CMOVB32rr,
1203           X86::CMOVBE32rr, X86::CMOVA32rr, 0, 0 },
1204         { X86::CMOVNE32rr, X86::CMOVE32rr, X86::CMOVGE32rr, X86::CMOVL32rr,
1205           X86::CMOVLE32rr, X86::CMOVG32rr, X86::CMOVNS32rr, X86::CMOVS32rr },
1206       };
1207       Opcode = OpcodeTab[isSigned][OpNum];
1208       break;
1209     }
1210     }
1211   } else {
1212     // Get the value being branched on, and use it to set the condition codes.
1213     unsigned CondReg = getReg(Cond, MBB, IP);
1214     BuildMI(*MBB, IP, X86::TEST8rr, 2).addReg(CondReg).addReg(CondReg);
1215     switch (SelectClass) {
1216     default: assert(0 && "Unknown value class!");
1217     case cFP:    Opcode = X86::FCMOVE; break;
1218     case cByte:
1219     case cShort: Opcode = X86::CMOVE16rr; break;
1220     case cInt:
1221     case cLong:  Opcode = X86::CMOVE32rr; break;
1222     }
1223   }
1224
1225   unsigned RealDestReg = DestReg;
1226
1227
1228   // Annoyingly enough, X86 doesn't HAVE 8-bit conditional moves.  Because of
1229   // this, we have to promote the incoming values to 16 bits, perform a 16-bit
1230   // cmove, then truncate the result.
1231   if (SelectClass == cByte) {
1232     DestReg = makeAnotherReg(Type::ShortTy);
1233     if (getClassB(TrueVal->getType()) == cByte) {
1234       // Promote the true value, by storing it into AL, and reading from AX.
1235       BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::AL).addReg(TrueReg);
1236       BuildMI(*MBB, IP, X86::MOV8ri, 1, X86::AH).addImm(0);
1237       TrueReg = makeAnotherReg(Type::ShortTy);
1238       BuildMI(*MBB, IP, X86::MOV16rr, 1, TrueReg).addReg(X86::AX);
1239     }
1240     if (getClassB(FalseVal->getType()) == cByte) {
1241       // Promote the true value, by storing it into CL, and reading from CX.
1242       BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(FalseReg);
1243       BuildMI(*MBB, IP, X86::MOV8ri, 1, X86::CH).addImm(0);
1244       FalseReg = makeAnotherReg(Type::ShortTy);
1245       BuildMI(*MBB, IP, X86::MOV16rr, 1, FalseReg).addReg(X86::CX);
1246     }
1247   }
1248
1249   BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(TrueReg).addReg(FalseReg);
1250
1251   switch (SelectClass) {
1252   case cByte:
1253     // We did the computation with 16-bit registers.  Truncate back to our
1254     // result by copying into AX then copying out AL.
1255     BuildMI(*MBB, IP, X86::MOV16rr, 1, X86::AX).addReg(DestReg);
1256     BuildMI(*MBB, IP, X86::MOV8rr, 1, RealDestReg).addReg(X86::AL);
1257     break;
1258   case cLong:
1259     // Move the upper half of the value as well.
1260     BuildMI(*MBB, IP, Opcode, 2,DestReg+1).addReg(TrueReg+1).addReg(FalseReg+1);
1261     break;
1262   }
1263 }
1264
1265
1266
1267 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
1268 /// operand, in the specified target register.
1269 ///
1270 void ISel::promote32(unsigned targetReg, const ValueRecord &VR) {
1271   bool isUnsigned = VR.Ty->isUnsigned() || VR.Ty == Type::BoolTy;
1272
1273   Value *Val = VR.Val;
1274   const Type *Ty = VR.Ty;
1275   if (Val) {
1276     if (Constant *C = dyn_cast<Constant>(Val)) {
1277       Val = ConstantExpr::getCast(C, Type::IntTy);
1278       Ty = Type::IntTy;
1279     }
1280
1281     // If this is a simple constant, just emit a MOVri directly to avoid the
1282     // copy.
1283     if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
1284       int TheVal = CI->getRawValue() & 0xFFFFFFFF;
1285       BuildMI(BB, X86::MOV32ri, 1, targetReg).addImm(TheVal);
1286       return;
1287     }
1288   }
1289
1290   // Make sure we have the register number for this value...
1291   unsigned Reg = Val ? getReg(Val) : VR.Reg;
1292
1293   switch (getClassB(Ty)) {
1294   case cByte:
1295     // Extend value into target register (8->32)
1296     if (isUnsigned)
1297       BuildMI(BB, X86::MOVZX32rr8, 1, targetReg).addReg(Reg);
1298     else
1299       BuildMI(BB, X86::MOVSX32rr8, 1, targetReg).addReg(Reg);
1300     break;
1301   case cShort:
1302     // Extend value into target register (16->32)
1303     if (isUnsigned)
1304       BuildMI(BB, X86::MOVZX32rr16, 1, targetReg).addReg(Reg);
1305     else
1306       BuildMI(BB, X86::MOVSX32rr16, 1, targetReg).addReg(Reg);
1307     break;
1308   case cInt:
1309     // Move value into target register (32->32)
1310     BuildMI(BB, X86::MOV32rr, 1, targetReg).addReg(Reg);
1311     break;
1312   default:
1313     assert(0 && "Unpromotable operand class in promote32");
1314   }
1315 }
1316
1317 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
1318 /// we have the following possibilities:
1319 ///
1320 ///   ret void: No return value, simply emit a 'ret' instruction
1321 ///   ret sbyte, ubyte : Extend value into EAX and return
1322 ///   ret short, ushort: Extend value into EAX and return
1323 ///   ret int, uint    : Move value into EAX and return
1324 ///   ret pointer      : Move value into EAX and return
1325 ///   ret long, ulong  : Move value into EAX/EDX and return
1326 ///   ret float/double : Top of FP stack
1327 ///
1328 void ISel::visitReturnInst(ReturnInst &I) {
1329   if (I.getNumOperands() == 0) {
1330     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
1331     return;
1332   }
1333
1334   Value *RetVal = I.getOperand(0);
1335   switch (getClassB(RetVal->getType())) {
1336   case cByte:   // integral return values: extend or move into EAX and return
1337   case cShort:
1338   case cInt:
1339     promote32(X86::EAX, ValueRecord(RetVal));
1340     // Declare that EAX is live on exit
1341     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
1342     break;
1343   case cFP: {                  // Floats & Doubles: Return in ST(0)
1344     unsigned RetReg = getReg(RetVal);
1345     BuildMI(BB, X86::FpSETRESULT, 1).addReg(RetReg);
1346     // Declare that top-of-stack is live on exit
1347     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
1348     break;
1349   }
1350   case cLong: {
1351     unsigned RetReg = getReg(RetVal);
1352     BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(RetReg);
1353     BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(RetReg+1);
1354     // Declare that EAX & EDX are live on exit
1355     BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX)
1356       .addReg(X86::ESP);
1357     break;
1358   }
1359   default:
1360     visitInstruction(I);
1361   }
1362   // Emit a 'ret' instruction
1363   BuildMI(BB, X86::RET, 0);
1364 }
1365
1366 // getBlockAfter - Return the basic block which occurs lexically after the
1367 // specified one.
1368 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
1369   Function::iterator I = BB; ++I;  // Get iterator to next block
1370   return I != BB->getParent()->end() ? &*I : 0;
1371 }
1372
1373 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
1374 /// that since code layout is frozen at this point, that if we are trying to
1375 /// jump to a block that is the immediate successor of the current block, we can
1376 /// just make a fall-through (but we don't currently).
1377 ///
1378 void ISel::visitBranchInst(BranchInst &BI) {
1379   // Update machine-CFG edges
1380   BB->addSuccessor (MBBMap[BI.getSuccessor(0)]);
1381   if (BI.isConditional())
1382     BB->addSuccessor (MBBMap[BI.getSuccessor(1)]);
1383
1384   BasicBlock *NextBB = getBlockAfter(BI.getParent());  // BB after current one
1385
1386   if (!BI.isConditional()) {  // Unconditional branch?
1387     if (BI.getSuccessor(0) != NextBB)
1388       BuildMI(BB, X86::JMP, 1).addMBB(MBBMap[BI.getSuccessor(0)]);
1389     return;
1390   }
1391
1392   // See if we can fold the setcc into the branch itself...
1393   SetCondInst *SCI = canFoldSetCCIntoBranchOrSelect(BI.getCondition());
1394   if (SCI == 0) {
1395     // Nope, cannot fold setcc into this branch.  Emit a branch on a condition
1396     // computed some other way...
1397     unsigned condReg = getReg(BI.getCondition());
1398     BuildMI(BB, X86::TEST8rr, 2).addReg(condReg).addReg(condReg);
1399     if (BI.getSuccessor(1) == NextBB) {
1400       if (BI.getSuccessor(0) != NextBB)
1401         BuildMI(BB, X86::JNE, 1).addMBB(MBBMap[BI.getSuccessor(0)]);
1402     } else {
1403       BuildMI(BB, X86::JE, 1).addMBB(MBBMap[BI.getSuccessor(1)]);
1404
1405       if (BI.getSuccessor(0) != NextBB)
1406         BuildMI(BB, X86::JMP, 1).addMBB(MBBMap[BI.getSuccessor(0)]);
1407     }
1408     return;
1409   }
1410
1411   unsigned OpNum = getSetCCNumber(SCI->getOpcode());
1412   MachineBasicBlock::iterator MII = BB->end();
1413   OpNum = EmitComparison(OpNum, SCI->getOperand(0), SCI->getOperand(1), BB,MII);
1414
1415   const Type *CompTy = SCI->getOperand(0)->getType();
1416   bool isSigned = CompTy->isSigned() && getClassB(CompTy) != cFP;
1417
1418
1419   // LLVM  -> X86 signed  X86 unsigned
1420   // -----    ----------  ------------
1421   // seteq -> je          je
1422   // setne -> jne         jne
1423   // setlt -> jl          jb
1424   // setge -> jge         jae
1425   // setgt -> jg          ja
1426   // setle -> jle         jbe
1427   // ----
1428   //          js                  // Used by comparison with 0 optimization
1429   //          jns
1430
1431   static const unsigned OpcodeTab[2][8] = {
1432     { X86::JE, X86::JNE, X86::JB, X86::JAE, X86::JA, X86::JBE, 0, 0 },
1433     { X86::JE, X86::JNE, X86::JL, X86::JGE, X86::JG, X86::JLE,
1434       X86::JS, X86::JNS },
1435   };
1436
1437   if (BI.getSuccessor(0) != NextBB) {
1438     BuildMI(BB, OpcodeTab[isSigned][OpNum], 1)
1439       .addMBB(MBBMap[BI.getSuccessor(0)]);
1440     if (BI.getSuccessor(1) != NextBB)
1441       BuildMI(BB, X86::JMP, 1).addMBB(MBBMap[BI.getSuccessor(1)]);
1442   } else {
1443     // Change to the inverse condition...
1444     if (BI.getSuccessor(1) != NextBB) {
1445       OpNum ^= 1;
1446       BuildMI(BB, OpcodeTab[isSigned][OpNum], 1)
1447         .addMBB(MBBMap[BI.getSuccessor(1)]);
1448     }
1449   }
1450 }
1451
1452
1453 /// doCall - This emits an abstract call instruction, setting up the arguments
1454 /// and the return value as appropriate.  For the actual function call itself,
1455 /// it inserts the specified CallMI instruction into the stream.
1456 ///
1457 void ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
1458                   const std::vector<ValueRecord> &Args) {
1459
1460   // Count how many bytes are to be pushed on the stack...
1461   unsigned NumBytes = 0;
1462
1463   if (!Args.empty()) {
1464     for (unsigned i = 0, e = Args.size(); i != e; ++i)
1465       switch (getClassB(Args[i].Ty)) {
1466       case cByte: case cShort: case cInt:
1467         NumBytes += 4; break;
1468       case cLong:
1469         NumBytes += 8; break;
1470       case cFP:
1471         NumBytes += Args[i].Ty == Type::FloatTy ? 4 : 8;
1472         break;
1473       default: assert(0 && "Unknown class!");
1474       }
1475
1476     // Adjust the stack pointer for the new arguments...
1477     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(NumBytes);
1478
1479     // Arguments go on the stack in reverse order, as specified by the ABI.
1480     unsigned ArgOffset = 0;
1481     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1482       unsigned ArgReg;
1483       switch (getClassB(Args[i].Ty)) {
1484       case cByte:
1485         if (Args[i].Val && isa<ConstantBool>(Args[i].Val)) {
1486           addRegOffset(BuildMI(BB, X86::MOV32mi, 5), X86::ESP, ArgOffset)
1487             .addImm(Args[i].Val == ConstantBool::True);
1488           break;
1489         }
1490         // FALL THROUGH
1491       case cShort:
1492         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1493           // Zero/Sign extend constant, then stuff into memory.
1494           ConstantInt *Val = cast<ConstantInt>(Args[i].Val);
1495           Val = cast<ConstantInt>(ConstantExpr::getCast(Val, Type::IntTy));
1496           addRegOffset(BuildMI(BB, X86::MOV32mi, 5), X86::ESP, ArgOffset)
1497             .addImm(Val->getRawValue() & 0xFFFFFFFF);
1498         } else {
1499           // Promote arg to 32 bits wide into a temporary register...
1500           ArgReg = makeAnotherReg(Type::UIntTy);
1501           promote32(ArgReg, Args[i]);
1502           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1503                        X86::ESP, ArgOffset).addReg(ArgReg);
1504         }
1505         break;
1506       case cInt:
1507         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1508           unsigned Val = cast<ConstantInt>(Args[i].Val)->getRawValue();
1509           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1510                        X86::ESP, ArgOffset).addImm(Val);
1511         } else if (Args[i].Val && isa<ConstantPointerNull>(Args[i].Val)) {
1512           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1513                        X86::ESP, ArgOffset).addImm(0);
1514         } else {
1515           ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1516           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1517                        X86::ESP, ArgOffset).addReg(ArgReg);
1518         }
1519         break;
1520       case cLong:
1521         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1522           uint64_t Val = cast<ConstantInt>(Args[i].Val)->getRawValue();
1523           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1524                        X86::ESP, ArgOffset).addImm(Val & ~0U);
1525           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1526                        X86::ESP, ArgOffset+4).addImm(Val >> 32ULL);
1527         } else {
1528           ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1529           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1530                        X86::ESP, ArgOffset).addReg(ArgReg);
1531           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1532                        X86::ESP, ArgOffset+4).addReg(ArgReg+1);
1533         }
1534         ArgOffset += 4;        // 8 byte entry, not 4.
1535         break;
1536
1537       case cFP:
1538         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1539         if (Args[i].Ty == Type::FloatTy) {
1540           addRegOffset(BuildMI(BB, X86::FST32m, 5),
1541                        X86::ESP, ArgOffset).addReg(ArgReg);
1542         } else {
1543           assert(Args[i].Ty == Type::DoubleTy && "Unknown FP type!");
1544           addRegOffset(BuildMI(BB, X86::FST64m, 5),
1545                        X86::ESP, ArgOffset).addReg(ArgReg);
1546           ArgOffset += 4;       // 8 byte entry, not 4.
1547         }
1548         break;
1549
1550       default: assert(0 && "Unknown class!");
1551       }
1552       ArgOffset += 4;
1553     }
1554   } else {
1555     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(0);
1556   }
1557
1558   BB->push_back(CallMI);
1559
1560   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addImm(NumBytes);
1561
1562   // If there is a return value, scavenge the result from the location the call
1563   // leaves it in...
1564   //
1565   if (Ret.Ty != Type::VoidTy) {
1566     unsigned DestClass = getClassB(Ret.Ty);
1567     switch (DestClass) {
1568     case cByte:
1569     case cShort:
1570     case cInt: {
1571       // Integral results are in %eax, or the appropriate portion
1572       // thereof.
1573       static const unsigned regRegMove[] = {
1574         X86::MOV8rr, X86::MOV16rr, X86::MOV32rr
1575       };
1576       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
1577       BuildMI(BB, regRegMove[DestClass], 1, Ret.Reg).addReg(AReg[DestClass]);
1578       break;
1579     }
1580     case cFP:     // Floating-point return values live in %ST(0)
1581       BuildMI(BB, X86::FpGETRESULT, 1, Ret.Reg);
1582       break;
1583     case cLong:   // Long values are left in EDX:EAX
1584       BuildMI(BB, X86::MOV32rr, 1, Ret.Reg).addReg(X86::EAX);
1585       BuildMI(BB, X86::MOV32rr, 1, Ret.Reg+1).addReg(X86::EDX);
1586       break;
1587     default: assert(0 && "Unknown class!");
1588     }
1589   }
1590 }
1591
1592
1593 /// visitCallInst - Push args on stack and do a procedure call instruction.
1594 void ISel::visitCallInst(CallInst &CI) {
1595   MachineInstr *TheCall;
1596   if (Function *F = CI.getCalledFunction()) {
1597     // Is it an intrinsic function call?
1598     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) {
1599       visitIntrinsicCall(ID, CI);   // Special intrinsics are not handled here
1600       return;
1601     }
1602
1603     // Emit a CALL instruction with PC-relative displacement.
1604     TheCall = BuildMI(X86::CALLpcrel32, 1).addGlobalAddress(F, true);
1605   } else {  // Emit an indirect call...
1606     unsigned Reg = getReg(CI.getCalledValue());
1607     TheCall = BuildMI(X86::CALL32r, 1).addReg(Reg);
1608   }
1609
1610   std::vector<ValueRecord> Args;
1611   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
1612     Args.push_back(ValueRecord(CI.getOperand(i)));
1613
1614   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
1615   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args);
1616 }
1617
1618 /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
1619 /// function, lowering any calls to unknown intrinsic functions into the
1620 /// equivalent LLVM code.
1621 ///
1622 void ISel::LowerUnknownIntrinsicFunctionCalls(Function &F) {
1623   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1624     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
1625       if (CallInst *CI = dyn_cast<CallInst>(I++))
1626         if (Function *F = CI->getCalledFunction())
1627           switch (F->getIntrinsicID()) {
1628           case Intrinsic::not_intrinsic:
1629           case Intrinsic::vastart:
1630           case Intrinsic::vacopy:
1631           case Intrinsic::vaend:
1632           case Intrinsic::returnaddress:
1633           case Intrinsic::frameaddress:
1634           case Intrinsic::memcpy:
1635           case Intrinsic::memset:
1636           case Intrinsic::isunordered:
1637           case Intrinsic::readport:
1638           case Intrinsic::writeport:
1639             // We directly implement these intrinsics
1640             break;
1641           case Intrinsic::readio: {
1642             // On X86, memory operations are in-order.  Lower this intrinsic
1643             // into a volatile load.
1644             Instruction *Before = CI->getPrev();
1645             LoadInst * LI = new LoadInst(CI->getOperand(1), "", true, CI);
1646             CI->replaceAllUsesWith(LI);
1647             BB->getInstList().erase(CI);
1648             break;
1649           }
1650           case Intrinsic::writeio: {
1651             // On X86, memory operations are in-order.  Lower this intrinsic
1652             // into a volatile store.
1653             Instruction *Before = CI->getPrev();
1654             StoreInst *LI = new StoreInst(CI->getOperand(1),
1655                                           CI->getOperand(2), true, CI);
1656             CI->replaceAllUsesWith(LI);
1657             BB->getInstList().erase(CI);
1658             break;
1659           }
1660           default:
1661             // All other intrinsic calls we must lower.
1662             Instruction *Before = CI->getPrev();
1663             TM.getIntrinsicLowering().LowerIntrinsicCall(CI);
1664             if (Before) {        // Move iterator to instruction after call
1665               I = Before; ++I;
1666             } else {
1667               I = BB->begin();
1668             }
1669           }
1670 }
1671
1672 void ISel::visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI) {
1673   unsigned TmpReg1, TmpReg2;
1674   switch (ID) {
1675   case Intrinsic::vastart:
1676     // Get the address of the first vararg value...
1677     TmpReg1 = getReg(CI);
1678     addFrameReference(BuildMI(BB, X86::LEA32r, 5, TmpReg1), VarArgsFrameIndex);
1679     return;
1680
1681   case Intrinsic::vacopy:
1682     TmpReg1 = getReg(CI);
1683     TmpReg2 = getReg(CI.getOperand(1));
1684     BuildMI(BB, X86::MOV32rr, 1, TmpReg1).addReg(TmpReg2);
1685     return;
1686   case Intrinsic::vaend: return;   // Noop on X86
1687
1688   case Intrinsic::returnaddress:
1689   case Intrinsic::frameaddress:
1690     TmpReg1 = getReg(CI);
1691     if (cast<Constant>(CI.getOperand(1))->isNullValue()) {
1692       if (ID == Intrinsic::returnaddress) {
1693         // Just load the return address
1694         addFrameReference(BuildMI(BB, X86::MOV32rm, 4, TmpReg1),
1695                           ReturnAddressIndex);
1696       } else {
1697         addFrameReference(BuildMI(BB, X86::LEA32r, 4, TmpReg1),
1698                           ReturnAddressIndex, -4);
1699       }
1700     } else {
1701       // Values other than zero are not implemented yet.
1702       BuildMI(BB, X86::MOV32ri, 1, TmpReg1).addImm(0);
1703     }
1704     return;
1705
1706   case Intrinsic::isunordered:
1707     TmpReg1 = getReg(CI.getOperand(1));
1708     TmpReg2 = getReg(CI.getOperand(2));
1709     emitUCOMr(BB, BB->end(), TmpReg2, TmpReg1);
1710     TmpReg2 = getReg(CI);
1711     BuildMI(BB, X86::SETPr, 0, TmpReg2);
1712     return;
1713
1714   case Intrinsic::memcpy: {
1715     assert(CI.getNumOperands() == 5 && "Illegal llvm.memcpy call!");
1716     unsigned Align = 1;
1717     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1718       Align = AlignC->getRawValue();
1719       if (Align == 0) Align = 1;
1720     }
1721
1722     // Turn the byte code into # iterations
1723     unsigned CountReg;
1724     unsigned Opcode;
1725     switch (Align & 3) {
1726     case 2:   // WORD aligned
1727       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1728         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1729       } else {
1730         CountReg = makeAnotherReg(Type::IntTy);
1731         unsigned ByteReg = getReg(CI.getOperand(3));
1732         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
1733       }
1734       Opcode = X86::REP_MOVSW;
1735       break;
1736     case 0:   // DWORD aligned
1737       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1738         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1739       } else {
1740         CountReg = makeAnotherReg(Type::IntTy);
1741         unsigned ByteReg = getReg(CI.getOperand(3));
1742         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
1743       }
1744       Opcode = X86::REP_MOVSD;
1745       break;
1746     default:  // BYTE aligned
1747       CountReg = getReg(CI.getOperand(3));
1748       Opcode = X86::REP_MOVSB;
1749       break;
1750     }
1751
1752     // No matter what the alignment is, we put the source in ESI, the
1753     // destination in EDI, and the count in ECX.
1754     TmpReg1 = getReg(CI.getOperand(1));
1755     TmpReg2 = getReg(CI.getOperand(2));
1756     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
1757     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
1758     BuildMI(BB, X86::MOV32rr, 1, X86::ESI).addReg(TmpReg2);
1759     BuildMI(BB, Opcode, 0);
1760     return;
1761   }
1762   case Intrinsic::memset: {
1763     assert(CI.getNumOperands() == 5 && "Illegal llvm.memset call!");
1764     unsigned Align = 1;
1765     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1766       Align = AlignC->getRawValue();
1767       if (Align == 0) Align = 1;
1768     }
1769
1770     // Turn the byte code into # iterations
1771     unsigned CountReg;
1772     unsigned Opcode;
1773     if (ConstantInt *ValC = dyn_cast<ConstantInt>(CI.getOperand(2))) {
1774       unsigned Val = ValC->getRawValue() & 255;
1775
1776       // If the value is a constant, then we can potentially use larger copies.
1777       switch (Align & 3) {
1778       case 2:   // WORD aligned
1779         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1780           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1781         } else {
1782           CountReg = makeAnotherReg(Type::IntTy);
1783           unsigned ByteReg = getReg(CI.getOperand(3));
1784           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
1785         }
1786         BuildMI(BB, X86::MOV16ri, 1, X86::AX).addImm((Val << 8) | Val);
1787         Opcode = X86::REP_STOSW;
1788         break;
1789       case 0:   // DWORD aligned
1790         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1791           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1792         } else {
1793           CountReg = makeAnotherReg(Type::IntTy);
1794           unsigned ByteReg = getReg(CI.getOperand(3));
1795           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
1796         }
1797         Val = (Val << 8) | Val;
1798         BuildMI(BB, X86::MOV32ri, 1, X86::EAX).addImm((Val << 16) | Val);
1799         Opcode = X86::REP_STOSD;
1800         break;
1801       default:  // BYTE aligned
1802         CountReg = getReg(CI.getOperand(3));
1803         BuildMI(BB, X86::MOV8ri, 1, X86::AL).addImm(Val);
1804         Opcode = X86::REP_STOSB;
1805         break;
1806       }
1807     } else {
1808       // If it's not a constant value we are storing, just fall back.  We could
1809       // try to be clever to form 16 bit and 32 bit values, but we don't yet.
1810       unsigned ValReg = getReg(CI.getOperand(2));
1811       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
1812       CountReg = getReg(CI.getOperand(3));
1813       Opcode = X86::REP_STOSB;
1814     }
1815
1816     // No matter what the alignment is, we put the source in ESI, the
1817     // destination in EDI, and the count in ECX.
1818     TmpReg1 = getReg(CI.getOperand(1));
1819     //TmpReg2 = getReg(CI.getOperand(2));
1820     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
1821     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
1822     BuildMI(BB, Opcode, 0);
1823     return;
1824   }
1825
1826   case Intrinsic::readport: {
1827     // First, determine that the size of the operand falls within the acceptable
1828     // range for this architecture.
1829     //
1830     if (getClassB(CI.getOperand(1)->getType()) != cShort) {
1831       std::cerr << "llvm.readport: Address size is not 16 bits\n";
1832       exit(1);
1833     }
1834
1835     // Now, move the I/O port address into the DX register and use the IN
1836     // instruction to get the input data.
1837     //
1838     unsigned Class = getClass(CI.getCalledFunction()->getReturnType());
1839     unsigned DestReg = getReg(CI);
1840
1841     // If the port is a single-byte constant, use the immediate form.
1842     if (ConstantInt *C = dyn_cast<ConstantInt>(CI.getOperand(1)))
1843       if ((C->getRawValue() & 255) == C->getRawValue()) {
1844         switch (Class) {
1845         case cByte:
1846           BuildMI(BB, X86::IN8ri, 1).addImm((unsigned char)C->getRawValue());
1847           BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
1848           return;
1849         case cShort:
1850           BuildMI(BB, X86::IN16ri, 1).addImm((unsigned char)C->getRawValue());
1851           BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AX);
1852           return;
1853         case cInt:
1854           BuildMI(BB, X86::IN32ri, 1).addImm((unsigned char)C->getRawValue());
1855           BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::EAX);
1856           return;
1857         }
1858       }
1859
1860     unsigned Reg = getReg(CI.getOperand(1));
1861     BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(Reg);
1862     switch (Class) {
1863     case cByte:
1864       BuildMI(BB, X86::IN8rr, 0);
1865       BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
1866       break;
1867     case cShort:
1868       BuildMI(BB, X86::IN16rr, 0);
1869       BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AX);
1870       break;
1871     case cInt:
1872       BuildMI(BB, X86::IN32rr, 0);
1873       BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::EAX);
1874       break;
1875     default:
1876       std::cerr << "Cannot do input on this data type";
1877       exit (1);
1878     }
1879     return;
1880   }
1881
1882   case Intrinsic::writeport: {
1883     // First, determine that the size of the operand falls within the
1884     // acceptable range for this architecture.
1885     if (getClass(CI.getOperand(2)->getType()) != cShort) {
1886       std::cerr << "llvm.writeport: Address size is not 16 bits\n";
1887       exit(1);
1888     }
1889
1890     unsigned Class = getClassB(CI.getOperand(1)->getType());
1891     unsigned ValReg = getReg(CI.getOperand(1));
1892     switch (Class) {
1893     case cByte:
1894       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
1895       break;
1896     case cShort:
1897       BuildMI(BB, X86::MOV16rr, 1, X86::AX).addReg(ValReg);
1898       break;
1899     case cInt:
1900       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(ValReg);
1901       break;
1902     default:
1903       std::cerr << "llvm.writeport: invalid data type for X86 target";
1904       exit(1);
1905     }
1906
1907
1908     // If the port is a single-byte constant, use the immediate form.
1909     if (ConstantInt *C = dyn_cast<ConstantInt>(CI.getOperand(2)))
1910       if ((C->getRawValue() & 255) == C->getRawValue()) {
1911         static const unsigned O[] = { X86::OUT8ir, X86::OUT16ir, X86::OUT32ir };
1912         BuildMI(BB, O[Class], 1).addImm((unsigned char)C->getRawValue());
1913         return;
1914       }
1915
1916     // Otherwise, move the I/O port address into the DX register and the value
1917     // to write into the AL/AX/EAX register.
1918     static const unsigned Opc[] = { X86::OUT8rr, X86::OUT16rr, X86::OUT32rr };
1919     unsigned Reg = getReg(CI.getOperand(2));
1920     BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(Reg);
1921     BuildMI(BB, Opc[Class], 0);
1922     return;
1923   }
1924
1925   default: assert(0 && "Error: unknown intrinsics should have been lowered!");
1926   }
1927 }
1928
1929 static bool isSafeToFoldLoadIntoInstruction(LoadInst &LI, Instruction &User) {
1930   if (LI.getParent() != User.getParent())
1931     return false;
1932   BasicBlock::iterator It = &LI;
1933   // Check all of the instructions between the load and the user.  We should
1934   // really use alias analysis here, but for now we just do something simple.
1935   for (++It; It != BasicBlock::iterator(&User); ++It) {
1936     switch (It->getOpcode()) {
1937     case Instruction::Free:
1938     case Instruction::Store:
1939     case Instruction::Call:
1940     case Instruction::Invoke:
1941       return false;
1942     case Instruction::Load:
1943       if (cast<LoadInst>(It)->isVolatile() && LI.isVolatile())
1944         return false;
1945       break;
1946     }
1947   }
1948   return true;
1949 }
1950
1951 /// visitSimpleBinary - Implement simple binary operators for integral types...
1952 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
1953 /// Xor.
1954 ///
1955 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
1956   unsigned DestReg = getReg(B);
1957   MachineBasicBlock::iterator MI = BB->end();
1958   Value *Op0 = B.getOperand(0), *Op1 = B.getOperand(1);
1959   unsigned Class = getClassB(B.getType());
1960
1961   // Special case: op Reg, load [mem]
1962   if (isa<LoadInst>(Op0) && !isa<LoadInst>(Op1) && Class != cLong &&
1963       Op0->hasOneUse() &&
1964       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op0), B))
1965     if (!B.swapOperands())
1966       std::swap(Op0, Op1);  // Make sure any loads are in the RHS.
1967
1968   if (isa<LoadInst>(Op1) && Class != cLong && Op1->hasOneUse() &&
1969       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op1), B)) {
1970
1971     unsigned Opcode;
1972     if (Class != cFP) {
1973       static const unsigned OpcodeTab[][3] = {
1974         // Arithmetic operators
1975         { X86::ADD8rm, X86::ADD16rm, X86::ADD32rm },  // ADD
1976         { X86::SUB8rm, X86::SUB16rm, X86::SUB32rm },  // SUB
1977
1978         // Bitwise operators
1979         { X86::AND8rm, X86::AND16rm, X86::AND32rm },  // AND
1980         { X86:: OR8rm, X86:: OR16rm, X86:: OR32rm },  // OR
1981         { X86::XOR8rm, X86::XOR16rm, X86::XOR32rm },  // XOR
1982       };
1983       Opcode = OpcodeTab[OperatorClass][Class];
1984     } else {
1985       static const unsigned OpcodeTab[][2] = {
1986         { X86::FADD32m, X86::FADD64m },  // ADD
1987         { X86::FSUB32m, X86::FSUB64m },  // SUB
1988       };
1989       const Type *Ty = Op0->getType();
1990       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
1991       Opcode = OpcodeTab[OperatorClass][Ty == Type::DoubleTy];
1992     }
1993
1994     unsigned Op0r = getReg(Op0);
1995     if (AllocaInst *AI =
1996         dyn_castFixedAlloca(cast<LoadInst>(Op1)->getOperand(0))) {
1997       unsigned FI = getFixedSizedAllocaFI(AI);
1998       addFrameReference(BuildMI(BB, Opcode, 5, DestReg).addReg(Op0r), FI);
1999
2000     } else {
2001       X86AddressMode AM;
2002       getAddressingMode(cast<LoadInst>(Op1)->getOperand(0), AM);
2003
2004       addFullAddress(BuildMI(BB, Opcode, 5, DestReg).addReg(Op0r), AM);
2005     }
2006     return;
2007   }
2008
2009   // If this is a floating point subtract, check to see if we can fold the first
2010   // operand in.
2011   if (Class == cFP && OperatorClass == 1 &&
2012       isa<LoadInst>(Op0) &&
2013       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op0), B)) {
2014     const Type *Ty = Op0->getType();
2015     assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
2016     unsigned Opcode = Ty == Type::FloatTy ? X86::FSUBR32m : X86::FSUBR64m;
2017
2018     unsigned Op1r = getReg(Op1);
2019     if (AllocaInst *AI =
2020         dyn_castFixedAlloca(cast<LoadInst>(Op0)->getOperand(0))) {
2021       unsigned FI = getFixedSizedAllocaFI(AI);
2022       addFrameReference(BuildMI(BB, Opcode, 5, DestReg).addReg(Op1r), FI);
2023     } else {
2024       X86AddressMode AM;
2025       getAddressingMode(cast<LoadInst>(Op0)->getOperand(0), AM);
2026
2027       addFullAddress(BuildMI(BB, Opcode, 5, DestReg).addReg(Op1r), AM);
2028     }
2029     return;
2030   }
2031
2032   emitSimpleBinaryOperation(BB, MI, Op0, Op1, OperatorClass, DestReg);
2033 }
2034
2035
2036 /// emitBinaryFPOperation - This method handles emission of floating point
2037 /// Add (0), Sub (1), Mul (2), and Div (3) operations.
2038 void ISel::emitBinaryFPOperation(MachineBasicBlock *BB,
2039                                  MachineBasicBlock::iterator IP,
2040                                  Value *Op0, Value *Op1,
2041                                  unsigned OperatorClass, unsigned DestReg) {
2042
2043   // Special case: op Reg, <const fp>
2044   if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1))
2045     if (!Op1C->isExactlyValue(+0.0) && !Op1C->isExactlyValue(+1.0)) {
2046       // Create a constant pool entry for this constant.
2047       MachineConstantPool *CP = F->getConstantPool();
2048       unsigned CPI = CP->getConstantPoolIndex(Op1C);
2049       const Type *Ty = Op1->getType();
2050
2051       static const unsigned OpcodeTab[][4] = {
2052         { X86::FADD32m, X86::FSUB32m, X86::FMUL32m, X86::FDIV32m },   // Float
2053         { X86::FADD64m, X86::FSUB64m, X86::FMUL64m, X86::FDIV64m },   // Double
2054       };
2055
2056       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
2057       unsigned Opcode = OpcodeTab[Ty != Type::FloatTy][OperatorClass];
2058       unsigned Op0r = getReg(Op0, BB, IP);
2059       addConstantPoolReference(BuildMI(*BB, IP, Opcode, 5,
2060                                        DestReg).addReg(Op0r), CPI);
2061       return;
2062     }
2063
2064   // Special case: R1 = op <const fp>, R2
2065   if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op0))
2066     if (CFP->isExactlyValue(-0.0) && OperatorClass == 1) {
2067       // -0.0 - X === -X
2068       unsigned op1Reg = getReg(Op1, BB, IP);
2069       BuildMI(*BB, IP, X86::FCHS, 1, DestReg).addReg(op1Reg);
2070       return;
2071     } else if (!CFP->isExactlyValue(+0.0) && !CFP->isExactlyValue(+1.0)) {
2072       // R1 = op CST, R2  -->  R1 = opr R2, CST
2073
2074       // Create a constant pool entry for this constant.
2075       MachineConstantPool *CP = F->getConstantPool();
2076       unsigned CPI = CP->getConstantPoolIndex(CFP);
2077       const Type *Ty = CFP->getType();
2078
2079       static const unsigned OpcodeTab[][4] = {
2080         { X86::FADD32m, X86::FSUBR32m, X86::FMUL32m, X86::FDIVR32m }, // Float
2081         { X86::FADD64m, X86::FSUBR64m, X86::FMUL64m, X86::FDIVR64m }, // Double
2082       };
2083
2084       assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2085       unsigned Opcode = OpcodeTab[Ty != Type::FloatTy][OperatorClass];
2086       unsigned Op1r = getReg(Op1, BB, IP);
2087       addConstantPoolReference(BuildMI(*BB, IP, Opcode, 5,
2088                                        DestReg).addReg(Op1r), CPI);
2089       return;
2090     }
2091
2092   // General case.
2093   static const unsigned OpcodeTab[4] = {
2094     X86::FpADD, X86::FpSUB, X86::FpMUL, X86::FpDIV
2095   };
2096
2097   unsigned Opcode = OpcodeTab[OperatorClass];
2098   unsigned Op0r = getReg(Op0, BB, IP);
2099   unsigned Op1r = getReg(Op1, BB, IP);
2100   BuildMI(*BB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
2101 }
2102
2103 /// emitSimpleBinaryOperation - Implement simple binary operators for integral
2104 /// types...  OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for
2105 /// Or, 4 for Xor.
2106 ///
2107 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
2108 /// and constant expression support.
2109 ///
2110 void ISel::emitSimpleBinaryOperation(MachineBasicBlock *MBB,
2111                                      MachineBasicBlock::iterator IP,
2112                                      Value *Op0, Value *Op1,
2113                                      unsigned OperatorClass, unsigned DestReg) {
2114   unsigned Class = getClassB(Op0->getType());
2115
2116   if (Class == cFP) {
2117     assert(OperatorClass < 2 && "No logical ops for FP!");
2118     emitBinaryFPOperation(MBB, IP, Op0, Op1, OperatorClass, DestReg);
2119     return;
2120   }
2121
2122   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0))
2123     if (OperatorClass == 1) {
2124       static unsigned const NEGTab[] = {
2125         X86::NEG8r, X86::NEG16r, X86::NEG32r, 0, X86::NEG32r
2126       };
2127
2128       // sub 0, X -> neg X
2129       if (CI->isNullValue()) {
2130         unsigned op1Reg = getReg(Op1, MBB, IP);
2131         BuildMI(*MBB, IP, NEGTab[Class], 1, DestReg).addReg(op1Reg);
2132
2133         if (Class == cLong) {
2134           // We just emitted: Dl = neg Sl
2135           // Now emit       : T  = addc Sh, 0
2136           //                : Dh = neg T
2137           unsigned T = makeAnotherReg(Type::IntTy);
2138           BuildMI(*MBB, IP, X86::ADC32ri, 2, T).addReg(op1Reg+1).addImm(0);
2139           BuildMI(*MBB, IP, X86::NEG32r, 1, DestReg+1).addReg(T);
2140         }
2141         return;
2142       } else if (Op1->hasOneUse() && Class != cLong) {
2143         // sub C, X -> tmp = neg X; DestReg = add tmp, C.  This is better
2144         // than copying C into a temporary register, because of register
2145         // pressure (tmp and destreg can share a register.
2146         static unsigned const ADDRITab[] = {
2147           X86::ADD8ri, X86::ADD16ri, X86::ADD32ri, 0, X86::ADD32ri
2148         };
2149         unsigned op1Reg = getReg(Op1, MBB, IP);
2150         unsigned Tmp = makeAnotherReg(Op0->getType());
2151         BuildMI(*MBB, IP, NEGTab[Class], 1, Tmp).addReg(op1Reg);
2152         BuildMI(*MBB, IP, ADDRITab[Class], 2,
2153                 DestReg).addReg(Tmp).addImm(CI->getRawValue());
2154         return;
2155       }
2156     }
2157
2158   // Special case: op Reg, <const int>
2159   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
2160     unsigned Op0r = getReg(Op0, MBB, IP);
2161
2162     // xor X, -1 -> not X
2163     if (OperatorClass == 4 && Op1C->isAllOnesValue()) {
2164       static unsigned const NOTTab[] = {
2165         X86::NOT8r, X86::NOT16r, X86::NOT32r, 0, X86::NOT32r
2166       };
2167       BuildMI(*MBB, IP, NOTTab[Class], 1, DestReg).addReg(Op0r);
2168       if (Class == cLong)  // Invert the top part too
2169         BuildMI(*MBB, IP, X86::NOT32r, 1, DestReg+1).addReg(Op0r+1);
2170       return;
2171     }
2172
2173     // add X, -1 -> dec X
2174     if (OperatorClass == 0 && Op1C->isAllOnesValue() && Class != cLong) {
2175       // Note that we can't use dec for 64-bit decrements, because it does not
2176       // set the carry flag!
2177       static unsigned const DECTab[] = { X86::DEC8r, X86::DEC16r, X86::DEC32r };
2178       BuildMI(*MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
2179       return;
2180     }
2181
2182     // add X, 1 -> inc X
2183     if (OperatorClass == 0 && Op1C->equalsInt(1) && Class != cLong) {
2184       // Note that we can't use inc for 64-bit increments, because it does not
2185       // set the carry flag!
2186       static unsigned const INCTab[] = { X86::INC8r, X86::INC16r, X86::INC32r };
2187       BuildMI(*MBB, IP, INCTab[Class], 1, DestReg).addReg(Op0r);
2188       return;
2189     }
2190
2191     static const unsigned OpcodeTab[][5] = {
2192       // Arithmetic operators
2193       { X86::ADD8ri, X86::ADD16ri, X86::ADD32ri, 0, X86::ADD32ri },  // ADD
2194       { X86::SUB8ri, X86::SUB16ri, X86::SUB32ri, 0, X86::SUB32ri },  // SUB
2195
2196       // Bitwise operators
2197       { X86::AND8ri, X86::AND16ri, X86::AND32ri, 0, X86::AND32ri },  // AND
2198       { X86:: OR8ri, X86:: OR16ri, X86:: OR32ri, 0, X86::OR32ri  },  // OR
2199       { X86::XOR8ri, X86::XOR16ri, X86::XOR32ri, 0, X86::XOR32ri },  // XOR
2200     };
2201
2202     unsigned Opcode = OpcodeTab[OperatorClass][Class];
2203     unsigned Op1l = cast<ConstantInt>(Op1C)->getRawValue();
2204
2205     if (Class != cLong) {
2206       BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addImm(Op1l);
2207       return;
2208     }
2209
2210     // If this is a long value and the high or low bits have a special
2211     // property, emit some special cases.
2212     unsigned Op1h = cast<ConstantInt>(Op1C)->getRawValue() >> 32LL;
2213
2214     // If the constant is zero in the low 32-bits, just copy the low part
2215     // across and apply the normal 32-bit operation to the high parts.  There
2216     // will be no carry or borrow into the top.
2217     if (Op1l == 0) {
2218       if (OperatorClass != 2) // All but and...
2219         BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg).addReg(Op0r);
2220       else
2221         BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg).addImm(0);
2222       BuildMI(*MBB, IP, OpcodeTab[OperatorClass][cLong], 2, DestReg+1)
2223         .addReg(Op0r+1).addImm(Op1h);
2224       return;
2225     }
2226
2227     // If this is a logical operation and the top 32-bits are zero, just
2228     // operate on the lower 32.
2229     if (Op1h == 0 && OperatorClass > 1) {
2230       BuildMI(*MBB, IP, OpcodeTab[OperatorClass][cLong], 2, DestReg)
2231         .addReg(Op0r).addImm(Op1l);
2232       if (OperatorClass != 2)  // All but and
2233         BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg+1).addReg(Op0r+1);
2234       else
2235         BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
2236       return;
2237     }
2238
2239     // TODO: We could handle lots of other special cases here, such as AND'ing
2240     // with 0xFFFFFFFF00000000 -> noop, etc.
2241
2242     // Otherwise, code generate the full operation with a constant.
2243     static const unsigned TopTab[] = {
2244       X86::ADC32ri, X86::SBB32ri, X86::AND32ri, X86::OR32ri, X86::XOR32ri
2245     };
2246
2247     BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addImm(Op1l);
2248     BuildMI(*MBB, IP, TopTab[OperatorClass], 2, DestReg+1)
2249       .addReg(Op0r+1).addImm(Op1h);
2250     return;
2251   }
2252
2253   // Finally, handle the general case now.
2254   static const unsigned OpcodeTab[][5] = {
2255     // Arithmetic operators
2256     { X86::ADD8rr, X86::ADD16rr, X86::ADD32rr, 0, X86::ADD32rr },  // ADD
2257     { X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, 0, X86::SUB32rr },  // SUB
2258
2259     // Bitwise operators
2260     { X86::AND8rr, X86::AND16rr, X86::AND32rr, 0, X86::AND32rr },  // AND
2261     { X86:: OR8rr, X86:: OR16rr, X86:: OR32rr, 0, X86:: OR32rr },  // OR
2262     { X86::XOR8rr, X86::XOR16rr, X86::XOR32rr, 0, X86::XOR32rr },  // XOR
2263   };
2264
2265   unsigned Opcode = OpcodeTab[OperatorClass][Class];
2266   unsigned Op0r = getReg(Op0, MBB, IP);
2267   unsigned Op1r = getReg(Op1, MBB, IP);
2268   BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
2269
2270   if (Class == cLong) {        // Handle the upper 32 bits of long values...
2271     static const unsigned TopTab[] = {
2272       X86::ADC32rr, X86::SBB32rr, X86::AND32rr, X86::OR32rr, X86::XOR32rr
2273     };
2274     BuildMI(*MBB, IP, TopTab[OperatorClass], 2,
2275             DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
2276   }
2277 }
2278
2279 /// doMultiply - Emit appropriate instructions to multiply together the
2280 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
2281 /// result should be given as DestTy.
2282 ///
2283 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
2284                       unsigned DestReg, const Type *DestTy,
2285                       unsigned op0Reg, unsigned op1Reg) {
2286   unsigned Class = getClass(DestTy);
2287   switch (Class) {
2288   case cInt:
2289   case cShort:
2290     BuildMI(*MBB, MBBI, Class == cInt ? X86::IMUL32rr:X86::IMUL16rr, 2, DestReg)
2291       .addReg(op0Reg).addReg(op1Reg);
2292     return;
2293   case cByte:
2294     // Must use the MUL instruction, which forces use of AL...
2295     BuildMI(*MBB, MBBI, X86::MOV8rr, 1, X86::AL).addReg(op0Reg);
2296     BuildMI(*MBB, MBBI, X86::MUL8r, 1).addReg(op1Reg);
2297     BuildMI(*MBB, MBBI, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
2298     return;
2299   default:
2300   case cLong: assert(0 && "doMultiply cannot operate on LONG values!");
2301   }
2302 }
2303
2304 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
2305 // returns zero when the input is not exactly a power of two.
2306 static unsigned ExactLog2(unsigned Val) {
2307   if (Val == 0 || (Val & (Val-1))) return 0;
2308   unsigned Count = 0;
2309   while (Val != 1) {
2310     Val >>= 1;
2311     ++Count;
2312   }
2313   return Count+1;
2314 }
2315
2316
2317 /// doMultiplyConst - This function is specialized to efficiently codegen an 8,
2318 /// 16, or 32-bit integer multiply by a constant.
2319 void ISel::doMultiplyConst(MachineBasicBlock *MBB,
2320                            MachineBasicBlock::iterator IP,
2321                            unsigned DestReg, const Type *DestTy,
2322                            unsigned op0Reg, unsigned ConstRHS) {
2323   static const unsigned MOVrrTab[] = {X86::MOV8rr, X86::MOV16rr, X86::MOV32rr};
2324   static const unsigned MOVriTab[] = {X86::MOV8ri, X86::MOV16ri, X86::MOV32ri};
2325   static const unsigned ADDrrTab[] = {X86::ADD8rr, X86::ADD16rr, X86::ADD32rr};
2326   static const unsigned NEGrTab[]  = {X86::NEG8r , X86::NEG16r , X86::NEG32r };
2327
2328   unsigned Class = getClass(DestTy);
2329   unsigned TmpReg;
2330
2331   // Handle special cases here.
2332   switch (ConstRHS) {
2333   case -2:
2334     TmpReg = makeAnotherReg(DestTy);
2335     BuildMI(*MBB, IP, NEGrTab[Class], 1, TmpReg).addReg(op0Reg);
2336     BuildMI(*MBB, IP, ADDrrTab[Class], 1,DestReg).addReg(TmpReg).addReg(TmpReg);
2337     return;
2338   case -1:
2339     BuildMI(*MBB, IP, NEGrTab[Class], 1, DestReg).addReg(op0Reg);
2340     return;
2341   case 0:
2342     BuildMI(*MBB, IP, MOVriTab[Class], 1, DestReg).addImm(0);
2343     return;
2344   case 1:
2345     BuildMI(*MBB, IP, MOVrrTab[Class], 1, DestReg).addReg(op0Reg);
2346     return;
2347   case 2:
2348     BuildMI(*MBB, IP, ADDrrTab[Class], 1,DestReg).addReg(op0Reg).addReg(op0Reg);
2349     return;
2350   case 3:
2351   case 5:
2352   case 9:
2353     if (Class == cInt) {
2354       X86AddressMode AM;
2355       AM.BaseType = X86AddressMode::RegBase;
2356       AM.Base.Reg = op0Reg;
2357       AM.Scale = ConstRHS-1;
2358       AM.IndexReg = op0Reg;
2359       AM.Disp = 0;
2360       addFullAddress(BuildMI(*MBB, IP, X86::LEA32r, 5, DestReg), AM);
2361       return;
2362     }
2363   case -3:
2364   case -5:
2365   case -9:
2366     if (Class == cInt) {
2367       TmpReg = makeAnotherReg(DestTy);
2368       X86AddressMode AM;
2369       AM.BaseType = X86AddressMode::RegBase;
2370       AM.Base.Reg = op0Reg;
2371       AM.Scale = -ConstRHS-1;
2372       AM.IndexReg = op0Reg;
2373       AM.Disp = 0;
2374       addFullAddress(BuildMI(*MBB, IP, X86::LEA32r, 5, TmpReg), AM);
2375       BuildMI(*MBB, IP, NEGrTab[Class], 1, DestReg).addReg(TmpReg);
2376       return;
2377     }
2378   }
2379
2380   // If the element size is exactly a power of 2, use a shift to get it.
2381   if (unsigned Shift = ExactLog2(ConstRHS)) {
2382     switch (Class) {
2383     default: assert(0 && "Unknown class for this function!");
2384     case cByte:
2385       BuildMI(*MBB, IP, X86::SHL8ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
2386       return;
2387     case cShort:
2388       BuildMI(*MBB, IP, X86::SHL16ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
2389       return;
2390     case cInt:
2391       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(op0Reg).addImm(Shift-1);
2392       return;
2393     }
2394   }
2395
2396   // If the element size is a negative power of 2, use a shift/neg to get it.
2397   if (unsigned Shift = ExactLog2(-ConstRHS)) {
2398     TmpReg = makeAnotherReg(DestTy);
2399     BuildMI(*MBB, IP, NEGrTab[Class], 1, TmpReg).addReg(op0Reg);
2400     switch (Class) {
2401     default: assert(0 && "Unknown class for this function!");
2402     case cByte:
2403       BuildMI(*MBB, IP, X86::SHL8ri,2, DestReg).addReg(TmpReg).addImm(Shift-1);
2404       return;
2405     case cShort:
2406       BuildMI(*MBB, IP, X86::SHL16ri,2, DestReg).addReg(TmpReg).addImm(Shift-1);
2407       return;
2408     case cInt:
2409       BuildMI(*MBB, IP, X86::SHL32ri,2, DestReg).addReg(TmpReg).addImm(Shift-1);
2410       return;
2411     }
2412   }
2413
2414   if (Class == cShort) {
2415     BuildMI(*MBB, IP, X86::IMUL16rri,2,DestReg).addReg(op0Reg).addImm(ConstRHS);
2416     return;
2417   } else if (Class == cInt) {
2418     BuildMI(*MBB, IP, X86::IMUL32rri,2,DestReg).addReg(op0Reg).addImm(ConstRHS);
2419     return;
2420   }
2421
2422   // Most general case, emit a normal multiply...
2423   TmpReg = makeAnotherReg(DestTy);
2424   BuildMI(*MBB, IP, MOVriTab[Class], 1, TmpReg).addImm(ConstRHS);
2425
2426   // Emit a MUL to multiply the register holding the index by
2427   // elementSize, putting the result in OffsetReg.
2428   doMultiply(MBB, IP, DestReg, DestTy, op0Reg, TmpReg);
2429 }
2430
2431 /// visitMul - Multiplies are not simple binary operators because they must deal
2432 /// with the EAX register explicitly.
2433 ///
2434 void ISel::visitMul(BinaryOperator &I) {
2435   unsigned ResultReg = getReg(I);
2436
2437   Value *Op0 = I.getOperand(0);
2438   Value *Op1 = I.getOperand(1);
2439
2440   // Fold loads into floating point multiplies.
2441   if (getClass(Op0->getType()) == cFP) {
2442     if (isa<LoadInst>(Op0) && !isa<LoadInst>(Op1))
2443       if (!I.swapOperands())
2444         std::swap(Op0, Op1);  // Make sure any loads are in the RHS.
2445     if (LoadInst *LI = dyn_cast<LoadInst>(Op1))
2446       if (isSafeToFoldLoadIntoInstruction(*LI, I)) {
2447         const Type *Ty = Op0->getType();
2448         assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2449         unsigned Opcode = Ty == Type::FloatTy ? X86::FMUL32m : X86::FMUL64m;
2450
2451         unsigned Op0r = getReg(Op0);
2452         if (AllocaInst *AI = dyn_castFixedAlloca(LI->getOperand(0))) {
2453           unsigned FI = getFixedSizedAllocaFI(AI);
2454           addFrameReference(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op0r), FI);
2455         } else {
2456           X86AddressMode AM;
2457           getAddressingMode(LI->getOperand(0), AM);
2458
2459           addFullAddress(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op0r), AM);
2460         }
2461         return;
2462       }
2463   }
2464
2465   MachineBasicBlock::iterator IP = BB->end();
2466   emitMultiply(BB, IP, Op0, Op1, ResultReg);
2467 }
2468
2469 void ISel::emitMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
2470                         Value *Op0, Value *Op1, unsigned DestReg) {
2471   MachineBasicBlock &BB = *MBB;
2472   TypeClass Class = getClass(Op0->getType());
2473
2474   // Simple scalar multiply?
2475   unsigned Op0Reg  = getReg(Op0, &BB, IP);
2476   switch (Class) {
2477   case cByte:
2478   case cShort:
2479   case cInt:
2480     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2481       unsigned Val = (unsigned)CI->getRawValue(); // Isn't a 64-bit constant
2482       doMultiplyConst(&BB, IP, DestReg, Op0->getType(), Op0Reg, Val);
2483     } else {
2484       unsigned Op1Reg  = getReg(Op1, &BB, IP);
2485       doMultiply(&BB, IP, DestReg, Op1->getType(), Op0Reg, Op1Reg);
2486     }
2487     return;
2488   case cFP:
2489     emitBinaryFPOperation(MBB, IP, Op0, Op1, 2, DestReg);
2490     return;
2491   case cLong:
2492     break;
2493   }
2494
2495   // Long value.  We have to do things the hard way...
2496   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2497     unsigned CLow = CI->getRawValue();
2498     unsigned CHi  = CI->getRawValue() >> 32;
2499
2500     if (CLow == 0) {
2501       // If the low part of the constant is all zeros, things are simple.
2502       BuildMI(BB, IP, X86::MOV32ri, 1, DestReg).addImm(0);
2503       doMultiplyConst(&BB, IP, DestReg+1, Type::UIntTy, Op0Reg, CHi);
2504       return;
2505     }
2506
2507     // Multiply the two low parts... capturing carry into EDX
2508     unsigned OverflowReg = 0;
2509     if (CLow == 1) {
2510       BuildMI(BB, IP, X86::MOV32rr, 1, DestReg).addReg(Op0Reg);
2511     } else {
2512       unsigned Op1RegL = makeAnotherReg(Type::UIntTy);
2513       OverflowReg = makeAnotherReg(Type::UIntTy);
2514       BuildMI(BB, IP, X86::MOV32ri, 1, Op1RegL).addImm(CLow);
2515       BuildMI(BB, IP, X86::MOV32rr, 1, X86::EAX).addReg(Op0Reg);
2516       BuildMI(BB, IP, X86::MUL32r, 1).addReg(Op1RegL);  // AL*BL
2517
2518       BuildMI(BB, IP, X86::MOV32rr, 1, DestReg).addReg(X86::EAX);   // AL*BL
2519       BuildMI(BB, IP, X86::MOV32rr, 1,
2520               OverflowReg).addReg(X86::EDX);                    // AL*BL >> 32
2521     }
2522
2523     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
2524     doMultiplyConst(&BB, IP, AHBLReg, Type::UIntTy, Op0Reg+1, CLow);
2525
2526     unsigned AHBLplusOverflowReg;
2527     if (OverflowReg) {
2528       AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
2529       BuildMI(BB, IP, X86::ADD32rr, 2,                // AH*BL+(AL*BL >> 32)
2530               AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
2531     } else {
2532       AHBLplusOverflowReg = AHBLReg;
2533     }
2534
2535     if (CHi == 0) {
2536       BuildMI(BB, IP, X86::MOV32rr, 1, DestReg+1).addReg(AHBLplusOverflowReg);
2537     } else {
2538       unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
2539       doMultiplyConst(&BB, IP, ALBHReg, Type::UIntTy, Op0Reg, CHi);
2540
2541       BuildMI(BB, IP, X86::ADD32rr, 2,      // AL*BH + AH*BL + (AL*BL >> 32)
2542               DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
2543     }
2544     return;
2545   }
2546
2547   // General 64x64 multiply
2548
2549   unsigned Op1Reg  = getReg(Op1, &BB, IP);
2550   // Multiply the two low parts... capturing carry into EDX
2551   BuildMI(BB, IP, X86::MOV32rr, 1, X86::EAX).addReg(Op0Reg);
2552   BuildMI(BB, IP, X86::MUL32r, 1).addReg(Op1Reg);  // AL*BL
2553
2554   unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
2555   BuildMI(BB, IP, X86::MOV32rr, 1, DestReg).addReg(X86::EAX);     // AL*BL
2556   BuildMI(BB, IP, X86::MOV32rr, 1,
2557           OverflowReg).addReg(X86::EDX); // AL*BL >> 32
2558
2559   unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
2560   BuildMI(BB, IP, X86::IMUL32rr, 2,
2561           AHBLReg).addReg(Op0Reg+1).addReg(Op1Reg);
2562
2563   unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
2564   BuildMI(BB, IP, X86::ADD32rr, 2,                // AH*BL+(AL*BL >> 32)
2565           AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
2566
2567   unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
2568   BuildMI(BB, IP, X86::IMUL32rr, 2,
2569           ALBHReg).addReg(Op0Reg).addReg(Op1Reg+1);
2570
2571   BuildMI(BB, IP, X86::ADD32rr, 2,      // AL*BH + AH*BL + (AL*BL >> 32)
2572           DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
2573 }
2574
2575
2576 /// visitDivRem - Handle division and remainder instructions... these
2577 /// instruction both require the same instructions to be generated, they just
2578 /// select the result from a different register.  Note that both of these
2579 /// instructions work differently for signed and unsigned operands.
2580 ///
2581 void ISel::visitDivRem(BinaryOperator &I) {
2582   unsigned ResultReg = getReg(I);
2583   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2584
2585   // Fold loads into floating point divides.
2586   if (getClass(Op0->getType()) == cFP) {
2587     if (LoadInst *LI = dyn_cast<LoadInst>(Op1))
2588       if (isSafeToFoldLoadIntoInstruction(*LI, I)) {
2589         const Type *Ty = Op0->getType();
2590         assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2591         unsigned Opcode = Ty == Type::FloatTy ? X86::FDIV32m : X86::FDIV64m;
2592
2593         unsigned Op0r = getReg(Op0);
2594         if (AllocaInst *AI = dyn_castFixedAlloca(LI->getOperand(0))) {
2595           unsigned FI = getFixedSizedAllocaFI(AI);
2596           addFrameReference(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op0r), FI);
2597         } else {
2598           X86AddressMode AM;
2599           getAddressingMode(LI->getOperand(0), AM);
2600
2601           addFullAddress(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op0r), AM);
2602         }
2603         return;
2604       }
2605
2606     if (LoadInst *LI = dyn_cast<LoadInst>(Op0))
2607       if (isSafeToFoldLoadIntoInstruction(*LI, I)) {
2608         const Type *Ty = Op0->getType();
2609         assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2610         unsigned Opcode = Ty == Type::FloatTy ? X86::FDIVR32m : X86::FDIVR64m;
2611
2612         unsigned Op1r = getReg(Op1);
2613         if (AllocaInst *AI = dyn_castFixedAlloca(LI->getOperand(0))) {
2614           unsigned FI = getFixedSizedAllocaFI(AI);
2615           addFrameReference(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op1r), FI);
2616         } else {
2617           X86AddressMode AM;
2618           getAddressingMode(LI->getOperand(0), AM);
2619           addFullAddress(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op1r), AM);
2620         }
2621         return;
2622       }
2623   }
2624
2625
2626   MachineBasicBlock::iterator IP = BB->end();
2627   emitDivRemOperation(BB, IP, Op0, Op1,
2628                       I.getOpcode() == Instruction::Div, ResultReg);
2629 }
2630
2631 void ISel::emitDivRemOperation(MachineBasicBlock *BB,
2632                                MachineBasicBlock::iterator IP,
2633                                Value *Op0, Value *Op1, bool isDiv,
2634                                unsigned ResultReg) {
2635   const Type *Ty = Op0->getType();
2636   unsigned Class = getClass(Ty);
2637   switch (Class) {
2638   case cFP:              // Floating point divide
2639     if (isDiv) {
2640       emitBinaryFPOperation(BB, IP, Op0, Op1, 3, ResultReg);
2641       return;
2642     } else {               // Floating point remainder...
2643       unsigned Op0Reg = getReg(Op0, BB, IP);
2644       unsigned Op1Reg = getReg(Op1, BB, IP);
2645       MachineInstr *TheCall =
2646         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
2647       std::vector<ValueRecord> Args;
2648       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
2649       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
2650       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
2651     }
2652     return;
2653   case cLong: {
2654     static const char *FnName[] =
2655       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
2656     unsigned Op0Reg = getReg(Op0, BB, IP);
2657     unsigned Op1Reg = getReg(Op1, BB, IP);
2658     unsigned NameIdx = Ty->isUnsigned()*2 + isDiv;
2659     MachineInstr *TheCall =
2660       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
2661
2662     std::vector<ValueRecord> Args;
2663     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
2664     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
2665     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
2666     return;
2667   }
2668   case cByte: case cShort: case cInt:
2669     break;          // Small integrals, handled below...
2670   default: assert(0 && "Unknown class!");
2671   }
2672
2673   static const unsigned MovOpcode[]={ X86::MOV8rr, X86::MOV16rr, X86::MOV32rr };
2674   static const unsigned NEGOpcode[] = { X86::NEG8r, X86::NEG16r, X86::NEG32r };
2675   static const unsigned SAROpcode[]={ X86::SAR8ri, X86::SAR16ri, X86::SAR32ri };
2676   static const unsigned SHROpcode[]={ X86::SHR8ri, X86::SHR16ri, X86::SHR32ri };
2677   static const unsigned ADDOpcode[]={ X86::ADD8rr, X86::ADD16rr, X86::ADD32rr };
2678
2679   // Special case signed division by power of 2.
2680   if (isDiv)
2681     if (ConstantSInt *CI = dyn_cast<ConstantSInt>(Op1)) {
2682       assert(Class != cLong && "This doesn't handle 64-bit divides!");
2683       int V = CI->getValue();
2684
2685       if (V == 1) {       // X /s 1 => X
2686         unsigned Op0Reg = getReg(Op0, BB, IP);
2687         BuildMI(*BB, IP, MovOpcode[Class], 1, ResultReg).addReg(Op0Reg);
2688         return;
2689       }
2690
2691       if (V == -1) {      // X /s -1 => -X
2692         unsigned Op0Reg = getReg(Op0, BB, IP);
2693         BuildMI(*BB, IP, NEGOpcode[Class], 1, ResultReg).addReg(Op0Reg);
2694         return;
2695       }
2696
2697       bool isNeg = false;
2698       if (V < 0) {         // Not a positive power of 2?
2699         V = -V;
2700         isNeg = true;      // Maybe it's a negative power of 2.
2701       }
2702       if (unsigned Log = ExactLog2(V)) {
2703         --Log;
2704         unsigned Op0Reg = getReg(Op0, BB, IP);
2705         unsigned TmpReg = makeAnotherReg(Op0->getType());
2706         if (Log != 1)
2707           BuildMI(*BB, IP, SAROpcode[Class], 2, TmpReg)
2708             .addReg(Op0Reg).addImm(Log-1);
2709         else
2710           BuildMI(*BB, IP, MovOpcode[Class], 1, TmpReg).addReg(Op0Reg);
2711         unsigned TmpReg2 = makeAnotherReg(Op0->getType());
2712         BuildMI(*BB, IP, SHROpcode[Class], 2, TmpReg2)
2713           .addReg(TmpReg).addImm(32-Log);
2714         unsigned TmpReg3 = makeAnotherReg(Op0->getType());
2715         BuildMI(*BB, IP, ADDOpcode[Class], 2, TmpReg3)
2716           .addReg(Op0Reg).addReg(TmpReg2);
2717
2718         unsigned TmpReg4 = isNeg ? makeAnotherReg(Op0->getType()) : ResultReg;
2719         BuildMI(*BB, IP, SAROpcode[Class], 2, TmpReg4)
2720           .addReg(Op0Reg).addImm(Log);
2721         if (isNeg)
2722           BuildMI(*BB, IP, NEGOpcode[Class], 1, ResultReg).addReg(TmpReg4);
2723         return;
2724       }
2725     }
2726
2727   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
2728   static const unsigned ClrOpcode[]={ X86::MOV8ri, X86::MOV16ri, X86::MOV32ri };
2729   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
2730
2731   static const unsigned DivOpcode[][4] = {
2732     { X86::DIV8r , X86::DIV16r , X86::DIV32r , 0 },  // Unsigned division
2733     { X86::IDIV8r, X86::IDIV16r, X86::IDIV32r, 0 },  // Signed division
2734   };
2735
2736   unsigned Reg    = Regs[Class];
2737   unsigned ExtReg = ExtRegs[Class];
2738
2739   // Put the first operand into one of the A registers...
2740   unsigned Op0Reg = getReg(Op0, BB, IP);
2741   unsigned Op1Reg = getReg(Op1, BB, IP);
2742   BuildMI(*BB, IP, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
2743
2744   if (Ty->isSigned()) {
2745     // Emit a sign extension instruction...
2746     unsigned ShiftResult = makeAnotherReg(Op0->getType());
2747     BuildMI(*BB, IP, SAROpcode[Class], 2,ShiftResult).addReg(Op0Reg).addImm(31);
2748     BuildMI(*BB, IP, MovOpcode[Class], 1, ExtReg).addReg(ShiftResult);
2749
2750     // Emit the appropriate divide or remainder instruction...
2751     BuildMI(*BB, IP, DivOpcode[1][Class], 1).addReg(Op1Reg);
2752   } else {
2753     // If unsigned, emit a zeroing instruction... (reg = 0)
2754     BuildMI(*BB, IP, ClrOpcode[Class], 2, ExtReg).addImm(0);
2755
2756     // Emit the appropriate divide or remainder instruction...
2757     BuildMI(*BB, IP, DivOpcode[0][Class], 1).addReg(Op1Reg);
2758   }
2759
2760   // Figure out which register we want to pick the result out of...
2761   unsigned DestReg = isDiv ? Reg : ExtReg;
2762
2763   // Put the result into the destination register...
2764   BuildMI(*BB, IP, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
2765 }
2766
2767
2768 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
2769 /// for constant immediate shift values, and for constant immediate
2770 /// shift values equal to 1. Even the general case is sort of special,
2771 /// because the shift amount has to be in CL, not just any old register.
2772 ///
2773 void ISel::visitShiftInst(ShiftInst &I) {
2774   MachineBasicBlock::iterator IP = BB->end ();
2775   emitShiftOperation (BB, IP, I.getOperand (0), I.getOperand (1),
2776                       I.getOpcode () == Instruction::Shl, I.getType (),
2777                       getReg (I));
2778 }
2779
2780 /// emitShiftOperation - Common code shared between visitShiftInst and
2781 /// constant expression support.
2782 void ISel::emitShiftOperation(MachineBasicBlock *MBB,
2783                               MachineBasicBlock::iterator IP,
2784                               Value *Op, Value *ShiftAmount, bool isLeftShift,
2785                               const Type *ResultTy, unsigned DestReg) {
2786   unsigned SrcReg = getReg (Op, MBB, IP);
2787   bool isSigned = ResultTy->isSigned ();
2788   unsigned Class = getClass (ResultTy);
2789
2790   static const unsigned ConstantOperand[][4] = {
2791     { X86::SHR8ri, X86::SHR16ri, X86::SHR32ri, X86::SHRD32rri8 },  // SHR
2792     { X86::SAR8ri, X86::SAR16ri, X86::SAR32ri, X86::SHRD32rri8 },  // SAR
2793     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SHL
2794     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SAL = SHL
2795   };
2796
2797   static const unsigned NonConstantOperand[][4] = {
2798     { X86::SHR8rCL, X86::SHR16rCL, X86::SHR32rCL },  // SHR
2799     { X86::SAR8rCL, X86::SAR16rCL, X86::SAR32rCL },  // SAR
2800     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SHL
2801     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SAL = SHL
2802   };
2803
2804   // Longs, as usual, are handled specially...
2805   if (Class == cLong) {
2806     // If we have a constant shift, we can generate much more efficient code
2807     // than otherwise...
2808     //
2809     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
2810       unsigned Amount = CUI->getValue();
2811       if (Amount < 32) {
2812         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
2813         if (isLeftShift) {
2814           BuildMI(*MBB, IP, Opc[3], 3,
2815               DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addImm(Amount);
2816           BuildMI(*MBB, IP, Opc[2], 2, DestReg).addReg(SrcReg).addImm(Amount);
2817         } else {
2818           BuildMI(*MBB, IP, Opc[3], 3,
2819               DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addImm(Amount);
2820           BuildMI(*MBB, IP, Opc[2],2,DestReg+1).addReg(SrcReg+1).addImm(Amount);
2821         }
2822       } else {                 // Shifting more than 32 bits
2823         Amount -= 32;
2824         if (isLeftShift) {
2825           if (Amount != 0) {
2826             BuildMI(*MBB, IP, X86::SHL32ri, 2,
2827                     DestReg + 1).addReg(SrcReg).addImm(Amount);
2828           } else {
2829             BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg+1).addReg(SrcReg);
2830           }
2831           BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg).addImm(0);
2832         } else {
2833           if (Amount != 0) {
2834             BuildMI(*MBB, IP, isSigned ? X86::SAR32ri : X86::SHR32ri, 2,
2835                     DestReg).addReg(SrcReg+1).addImm(Amount);
2836           } else {
2837             BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg+1);
2838           }
2839           BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
2840         }
2841       }
2842     } else {
2843       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2844
2845       if (!isLeftShift && isSigned) {
2846         // If this is a SHR of a Long, then we need to do funny sign extension
2847         // stuff.  TmpReg gets the value to use as the high-part if we are
2848         // shifting more than 32 bits.
2849         BuildMI(*MBB, IP, X86::SAR32ri, 2, TmpReg).addReg(SrcReg).addImm(31);
2850       } else {
2851         // Other shifts use a fixed zero value if the shift is more than 32
2852         // bits.
2853         BuildMI(*MBB, IP, X86::MOV32ri, 1, TmpReg).addImm(0);
2854       }
2855
2856       // Initialize CL with the shift amount...
2857       unsigned ShiftAmountReg = getReg(ShiftAmount, MBB, IP);
2858       BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
2859
2860       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
2861       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
2862       if (isLeftShift) {
2863         // TmpReg2 = shld inHi, inLo
2864         BuildMI(*MBB, IP, X86::SHLD32rrCL,2,TmpReg2).addReg(SrcReg+1)
2865                                                     .addReg(SrcReg);
2866         // TmpReg3 = shl  inLo, CL
2867         BuildMI(*MBB, IP, X86::SHL32rCL, 1, TmpReg3).addReg(SrcReg);
2868
2869         // Set the flags to indicate whether the shift was by more than 32 bits.
2870         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
2871
2872         // DestHi = (>32) ? TmpReg3 : TmpReg2;
2873         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2874                 DestReg+1).addReg(TmpReg2).addReg(TmpReg3);
2875         // DestLo = (>32) ? TmpReg : TmpReg3;
2876         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2877             DestReg).addReg(TmpReg3).addReg(TmpReg);
2878       } else {
2879         // TmpReg2 = shrd inLo, inHi
2880         BuildMI(*MBB, IP, X86::SHRD32rrCL,2,TmpReg2).addReg(SrcReg)
2881                                                     .addReg(SrcReg+1);
2882         // TmpReg3 = s[ah]r  inHi, CL
2883         BuildMI(*MBB, IP, isSigned ? X86::SAR32rCL : X86::SHR32rCL, 1, TmpReg3)
2884                        .addReg(SrcReg+1);
2885
2886         // Set the flags to indicate whether the shift was by more than 32 bits.
2887         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
2888
2889         // DestLo = (>32) ? TmpReg3 : TmpReg2;
2890         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2891                 DestReg).addReg(TmpReg2).addReg(TmpReg3);
2892
2893         // DestHi = (>32) ? TmpReg : TmpReg3;
2894         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2895                 DestReg+1).addReg(TmpReg3).addReg(TmpReg);
2896       }
2897     }
2898     return;
2899   }
2900
2901   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
2902     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
2903     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
2904
2905     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
2906     BuildMI(*MBB, IP, Opc[Class], 2,
2907         DestReg).addReg(SrcReg).addImm(CUI->getValue());
2908   } else {                  // The shift amount is non-constant.
2909     unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
2910     BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
2911
2912     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
2913     BuildMI(*MBB, IP, Opc[Class], 1, DestReg).addReg(SrcReg);
2914   }
2915 }
2916
2917
2918 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
2919 /// instruction.  The load and store instructions are the only place where we
2920 /// need to worry about the memory layout of the target machine.
2921 ///
2922 void ISel::visitLoadInst(LoadInst &I) {
2923   // Check to see if this load instruction is going to be folded into a binary
2924   // instruction, like add.  If so, we don't want to emit it.  Wouldn't a real
2925   // pattern matching instruction selector be nice?
2926   unsigned Class = getClassB(I.getType());
2927   if (I.hasOneUse()) {
2928     Instruction *User = cast<Instruction>(I.use_back());
2929     switch (User->getOpcode()) {
2930     case Instruction::Cast:
2931       // If this is a cast from a signed-integer type to a floating point type,
2932       // fold the cast here.
2933       if (getClassB(User->getType()) == cFP &&
2934           (I.getType() == Type::ShortTy || I.getType() == Type::IntTy ||
2935            I.getType() == Type::LongTy)) {
2936         unsigned DestReg = getReg(User);
2937         static const unsigned Opcode[] = {
2938           0/*BYTE*/, X86::FILD16m, X86::FILD32m, 0/*FP*/, X86::FILD64m
2939         };
2940
2941         if (AllocaInst *AI = dyn_castFixedAlloca(I.getOperand(0))) {
2942           unsigned FI = getFixedSizedAllocaFI(AI);
2943           addFrameReference(BuildMI(BB, Opcode[Class], 4, DestReg), FI);
2944         } else {
2945           X86AddressMode AM;
2946           getAddressingMode(I.getOperand(0), AM);
2947           addFullAddress(BuildMI(BB, Opcode[Class], 4, DestReg), AM);
2948         }
2949         return;
2950       } else {
2951         User = 0;
2952       }
2953       break;
2954
2955     case Instruction::Add:
2956     case Instruction::Sub:
2957     case Instruction::And:
2958     case Instruction::Or:
2959     case Instruction::Xor:
2960       if (Class == cLong) User = 0;
2961       break;
2962     case Instruction::Mul:
2963     case Instruction::Div:
2964       if (Class != cFP) User = 0;
2965       break;  // Folding only implemented for floating point.
2966     default: User = 0; break;
2967     }
2968
2969     if (User) {
2970       // Okay, we found a user.  If the load is the first operand and there is
2971       // no second operand load, reverse the operand ordering.  Note that this
2972       // can fail for a subtract (ie, no change will be made).
2973       bool Swapped = false;
2974       if (!isa<LoadInst>(User->getOperand(1)))
2975         Swapped = !cast<BinaryOperator>(User)->swapOperands();
2976
2977       // Okay, now that everything is set up, if this load is used by the second
2978       // operand, and if there are no instructions that invalidate the load
2979       // before the binary operator, eliminate the load.
2980       if (User->getOperand(1) == &I &&
2981           isSafeToFoldLoadIntoInstruction(I, *User))
2982         return;   // Eliminate the load!
2983
2984       // If this is a floating point sub or div, we won't be able to swap the
2985       // operands, but we will still be able to eliminate the load.
2986       if (Class == cFP && User->getOperand(0) == &I &&
2987           !isa<LoadInst>(User->getOperand(1)) &&
2988           (User->getOpcode() == Instruction::Sub ||
2989            User->getOpcode() == Instruction::Div) &&
2990           isSafeToFoldLoadIntoInstruction(I, *User))
2991         return;  // Eliminate the load!
2992
2993       // If we swapped the operands to the instruction, but couldn't fold the
2994       // load anyway, swap them back.  We don't want to break add X, int
2995       // folding.
2996       if (Swapped) cast<BinaryOperator>(User)->swapOperands();
2997     }
2998   }
2999
3000   static const unsigned Opcodes[] = {
3001     X86::MOV8rm, X86::MOV16rm, X86::MOV32rm, X86::FLD32m, X86::MOV32rm
3002   };
3003   unsigned Opcode = Opcodes[Class];
3004   if (I.getType() == Type::DoubleTy) Opcode = X86::FLD64m;
3005
3006   unsigned DestReg = getReg(I);
3007
3008   if (AllocaInst *AI = dyn_castFixedAlloca(I.getOperand(0))) {
3009     unsigned FI = getFixedSizedAllocaFI(AI);
3010     if (Class == cLong) {
3011       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, DestReg), FI);
3012       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), FI, 4);
3013     } else {
3014       addFrameReference(BuildMI(BB, Opcode, 4, DestReg), FI);
3015     }
3016   } else {
3017     X86AddressMode AM;
3018     getAddressingMode(I.getOperand(0), AM);
3019
3020     if (Class == cLong) {
3021       addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg), AM);
3022       AM.Disp += 4;
3023       addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), AM);
3024     } else {
3025       addFullAddress(BuildMI(BB, Opcode, 4, DestReg), AM);
3026     }
3027   }
3028 }
3029
3030 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
3031 /// instruction.
3032 ///
3033 void ISel::visitStoreInst(StoreInst &I) {
3034   X86AddressMode AM;
3035   getAddressingMode(I.getOperand(1), AM);
3036
3037   const Type *ValTy = I.getOperand(0)->getType();
3038   unsigned Class = getClassB(ValTy);
3039
3040   if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(0))) {
3041     uint64_t Val = CI->getRawValue();
3042     if (Class == cLong) {
3043       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(Val & ~0U);
3044       AM.Disp += 4;
3045       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(Val>>32);
3046     } else {
3047       static const unsigned Opcodes[] = {
3048         X86::MOV8mi, X86::MOV16mi, X86::MOV32mi
3049       };
3050       unsigned Opcode = Opcodes[Class];
3051       addFullAddress(BuildMI(BB, Opcode, 5), AM).addImm(Val);
3052     }
3053   } else if (isa<ConstantPointerNull>(I.getOperand(0))) {
3054      addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(0);
3055   } else if (ConstantBool *CB = dyn_cast<ConstantBool>(I.getOperand(0))) {
3056     addFullAddress(BuildMI(BB, X86::MOV8mi, 5), AM).addImm(CB->getValue());
3057   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) {
3058     // Store constant FP values with integer instructions to avoid having to
3059     // load the constants from the constant pool then do a store.
3060     if (CFP->getType() == Type::FloatTy) {
3061       union {
3062         unsigned I;
3063         float    F;
3064       } V;
3065       V.F = CFP->getValue();
3066       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(V.I);
3067     } else {
3068       union {
3069         uint64_t I;
3070         double   F;
3071       } V;
3072       V.F = CFP->getValue();
3073       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm((unsigned)V.I);
3074       AM.Disp += 4;
3075       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(
3076                                                           unsigned(V.I >> 32));
3077     }
3078
3079   } else if (Class == cLong) {
3080     unsigned ValReg = getReg(I.getOperand(0));
3081     addFullAddress(BuildMI(BB, X86::MOV32mr, 5), AM).addReg(ValReg);
3082     AM.Disp += 4;
3083     addFullAddress(BuildMI(BB, X86::MOV32mr, 5), AM).addReg(ValReg+1);
3084   } else {
3085     unsigned ValReg = getReg(I.getOperand(0));
3086     static const unsigned Opcodes[] = {
3087       X86::MOV8mr, X86::MOV16mr, X86::MOV32mr, X86::FST32m
3088     };
3089     unsigned Opcode = Opcodes[Class];
3090     if (ValTy == Type::DoubleTy) Opcode = X86::FST64m;
3091
3092     addFullAddress(BuildMI(BB, Opcode, 1+4), AM).addReg(ValReg);
3093   }
3094 }
3095
3096
3097 /// visitCastInst - Here we have various kinds of copying with or without sign
3098 /// extension going on.
3099 ///
3100 void ISel::visitCastInst(CastInst &CI) {
3101   Value *Op = CI.getOperand(0);
3102
3103   unsigned SrcClass = getClassB(Op->getType());
3104   unsigned DestClass = getClassB(CI.getType());
3105   // Noop casts are not emitted: getReg will return the source operand as the
3106   // register to use for any uses of the noop cast.
3107   if (DestClass == SrcClass) {
3108     // The only detail in this plan is that casts from double -> float are
3109     // truncating operations that we have to codegen through memory (despite
3110     // the fact that the source/dest registers are the same class).
3111     if (CI.getType() != Type::FloatTy || Op->getType() != Type::DoubleTy)
3112       return;
3113   }
3114
3115   // If this is a cast from a 32-bit integer to a Long type, and the only uses
3116   // of the case are GEP instructions, then the cast does not need to be
3117   // generated explicitly, it will be folded into the GEP.
3118   if (DestClass == cLong && SrcClass == cInt) {
3119     bool AllUsesAreGEPs = true;
3120     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
3121       if (!isa<GetElementPtrInst>(*I)) {
3122         AllUsesAreGEPs = false;
3123         break;
3124       }
3125
3126     // No need to codegen this cast if all users are getelementptr instrs...
3127     if (AllUsesAreGEPs) return;
3128   }
3129
3130   // If this cast converts a load from a short,int, or long integer to a FP
3131   // value, we will have folded this cast away.
3132   if (DestClass == cFP && isa<LoadInst>(Op) && Op->hasOneUse() &&
3133       (Op->getType() == Type::ShortTy || Op->getType() == Type::IntTy ||
3134        Op->getType() == Type::LongTy))
3135     return;
3136
3137
3138   unsigned DestReg = getReg(CI);
3139   MachineBasicBlock::iterator MI = BB->end();
3140   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
3141 }
3142
3143 /// emitCastOperation - Common code shared between visitCastInst and constant
3144 /// expression cast support.
3145 ///
3146 void ISel::emitCastOperation(MachineBasicBlock *BB,
3147                              MachineBasicBlock::iterator IP,
3148                              Value *Src, const Type *DestTy,
3149                              unsigned DestReg) {
3150   const Type *SrcTy = Src->getType();
3151   unsigned SrcClass = getClassB(SrcTy);
3152   unsigned DestClass = getClassB(DestTy);
3153   unsigned SrcReg = getReg(Src, BB, IP);
3154
3155   // Implement casts to bool by using compare on the operand followed by set if
3156   // not zero on the result.
3157   if (DestTy == Type::BoolTy) {
3158     switch (SrcClass) {
3159     case cByte:
3160       BuildMI(*BB, IP, X86::TEST8rr, 2).addReg(SrcReg).addReg(SrcReg);
3161       break;
3162     case cShort:
3163       BuildMI(*BB, IP, X86::TEST16rr, 2).addReg(SrcReg).addReg(SrcReg);
3164       break;
3165     case cInt:
3166       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg).addReg(SrcReg);
3167       break;
3168     case cLong: {
3169       unsigned TmpReg = makeAnotherReg(Type::IntTy);
3170       BuildMI(*BB, IP, X86::OR32rr, 2, TmpReg).addReg(SrcReg).addReg(SrcReg+1);
3171       break;
3172     }
3173     case cFP:
3174       BuildMI(*BB, IP, X86::FTST, 1).addReg(SrcReg);
3175       BuildMI(*BB, IP, X86::FNSTSW8r, 0);
3176       BuildMI(*BB, IP, X86::SAHF, 1);
3177       break;
3178     }
3179
3180     // If the zero flag is not set, then the value is true, set the byte to
3181     // true.
3182     BuildMI(*BB, IP, X86::SETNEr, 1, DestReg);
3183     return;
3184   }
3185
3186   static const unsigned RegRegMove[] = {
3187     X86::MOV8rr, X86::MOV16rr, X86::MOV32rr, X86::FpMOV, X86::MOV32rr
3188   };
3189
3190   // Implement casts between values of the same type class (as determined by
3191   // getClass) by using a register-to-register move.
3192   if (SrcClass == DestClass) {
3193     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
3194       BuildMI(*BB, IP, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
3195     } else if (SrcClass == cFP) {
3196       if (SrcTy == Type::FloatTy) {  // double -> float
3197         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
3198         BuildMI(*BB, IP, X86::FpMOV, 1, DestReg).addReg(SrcReg);
3199       } else {                       // float -> double
3200         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
3201                "Unknown cFP member!");
3202         // Truncate from double to float by storing to memory as short, then
3203         // reading it back.
3204         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
3205         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
3206         addFrameReference(BuildMI(*BB, IP, X86::FST32m, 5), FrameIdx).addReg(SrcReg);
3207         addFrameReference(BuildMI(*BB, IP, X86::FLD32m, 5, DestReg), FrameIdx);
3208       }
3209     } else if (SrcClass == cLong) {
3210       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
3211       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg+1).addReg(SrcReg+1);
3212     } else {
3213       assert(0 && "Cannot handle this type of cast instruction!");
3214       abort();
3215     }
3216     return;
3217   }
3218
3219   // Handle cast of SMALLER int to LARGER int using a move with sign extension
3220   // or zero extension, depending on whether the source type was signed.
3221   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
3222       SrcClass < DestClass) {
3223     bool isLong = DestClass == cLong;
3224     if (isLong) DestClass = cInt;
3225
3226     static const unsigned Opc[][4] = {
3227       { X86::MOVSX16rr8, X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOV32rr }, // s
3228       { X86::MOVZX16rr8, X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOV32rr }  // u
3229     };
3230
3231     bool isUnsigned = SrcTy->isUnsigned() || SrcTy == Type::BoolTy;
3232     BuildMI(*BB, IP, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
3233         DestReg).addReg(SrcReg);
3234
3235     if (isLong) {  // Handle upper 32 bits as appropriate...
3236       if (isUnsigned)     // Zero out top bits...
3237         BuildMI(*BB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
3238       else                // Sign extend bottom half...
3239         BuildMI(*BB, IP, X86::SAR32ri, 2, DestReg+1).addReg(DestReg).addImm(31);
3240     }
3241     return;
3242   }
3243
3244   // Special case long -> int ...
3245   if (SrcClass == cLong && DestClass == cInt) {
3246     BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
3247     return;
3248   }
3249
3250   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
3251   // move out of AX or AL.
3252   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
3253       && SrcClass > DestClass) {
3254     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
3255     BuildMI(*BB, IP, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
3256     BuildMI(*BB, IP, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
3257     return;
3258   }
3259
3260   // Handle casts from integer to floating point now...
3261   if (DestClass == cFP) {
3262     // Promote the integer to a type supported by FLD.  We do this because there
3263     // are no unsigned FLD instructions, so we must promote an unsigned value to
3264     // a larger signed value, then use FLD on the larger value.
3265     //
3266     const Type *PromoteType = 0;
3267     unsigned PromoteOpcode = 0;
3268     unsigned RealDestReg = DestReg;
3269     switch (SrcTy->getTypeID()) {
3270     case Type::BoolTyID:
3271     case Type::SByteTyID:
3272       // We don't have the facilities for directly loading byte sized data from
3273       // memory (even signed).  Promote it to 16 bits.
3274       PromoteType = Type::ShortTy;
3275       PromoteOpcode = X86::MOVSX16rr8;
3276       break;
3277     case Type::UByteTyID:
3278       PromoteType = Type::ShortTy;
3279       PromoteOpcode = X86::MOVZX16rr8;
3280       break;
3281     case Type::UShortTyID:
3282       PromoteType = Type::IntTy;
3283       PromoteOpcode = X86::MOVZX32rr16;
3284       break;
3285     case Type::UIntTyID: {
3286       // Make a 64 bit temporary... and zero out the top of it...
3287       unsigned TmpReg = makeAnotherReg(Type::LongTy);
3288       BuildMI(*BB, IP, X86::MOV32rr, 1, TmpReg).addReg(SrcReg);
3289       BuildMI(*BB, IP, X86::MOV32ri, 1, TmpReg+1).addImm(0);
3290       SrcTy = Type::LongTy;
3291       SrcClass = cLong;
3292       SrcReg = TmpReg;
3293       break;
3294     }
3295     case Type::ULongTyID:
3296       // Don't fild into the read destination.
3297       DestReg = makeAnotherReg(Type::DoubleTy);
3298       break;
3299     default:  // No promotion needed...
3300       break;
3301     }
3302
3303     if (PromoteType) {
3304       unsigned TmpReg = makeAnotherReg(PromoteType);
3305       BuildMI(*BB, IP, PromoteOpcode, 1, TmpReg).addReg(SrcReg);
3306       SrcTy = PromoteType;
3307       SrcClass = getClass(PromoteType);
3308       SrcReg = TmpReg;
3309     }
3310
3311     // Spill the integer to memory and reload it from there...
3312     int FrameIdx =
3313       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
3314
3315     if (SrcClass == cLong) {
3316       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
3317                         FrameIdx).addReg(SrcReg);
3318       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
3319                         FrameIdx, 4).addReg(SrcReg+1);
3320     } else {
3321       static const unsigned Op1[] = { X86::MOV8mr, X86::MOV16mr, X86::MOV32mr };
3322       addFrameReference(BuildMI(*BB, IP, Op1[SrcClass], 5),
3323                         FrameIdx).addReg(SrcReg);
3324     }
3325
3326     static const unsigned Op2[] =
3327       { 0/*byte*/, X86::FILD16m, X86::FILD32m, 0/*FP*/, X86::FILD64m };
3328     addFrameReference(BuildMI(*BB, IP, Op2[SrcClass], 5, DestReg), FrameIdx);
3329
3330     // We need special handling for unsigned 64-bit integer sources.  If the
3331     // input number has the "sign bit" set, then we loaded it incorrectly as a
3332     // negative 64-bit number.  In this case, add an offset value.
3333     if (SrcTy == Type::ULongTy) {
3334       // Emit a test instruction to see if the dynamic input value was signed.
3335       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg+1).addReg(SrcReg+1);
3336
3337       // If the sign bit is set, get a pointer to an offset, otherwise get a
3338       // pointer to a zero.
3339       MachineConstantPool *CP = F->getConstantPool();
3340       unsigned Zero = makeAnotherReg(Type::IntTy);
3341       Constant *Null = Constant::getNullValue(Type::UIntTy);
3342       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Zero),
3343                                CP->getConstantPoolIndex(Null));
3344       unsigned Offset = makeAnotherReg(Type::IntTy);
3345       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
3346
3347       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Offset),
3348                                CP->getConstantPoolIndex(OffsetCst));
3349       unsigned Addr = makeAnotherReg(Type::IntTy);
3350       BuildMI(*BB, IP, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
3351
3352       // Load the constant for an add.  FIXME: this could make an 'fadd' that
3353       // reads directly from memory, but we don't support these yet.
3354       unsigned ConstReg = makeAnotherReg(Type::DoubleTy);
3355       addDirectMem(BuildMI(*BB, IP, X86::FLD32m, 4, ConstReg), Addr);
3356
3357       BuildMI(*BB, IP, X86::FpADD, 2, RealDestReg)
3358                 .addReg(ConstReg).addReg(DestReg);
3359     }
3360
3361     return;
3362   }
3363
3364   // Handle casts from floating point to integer now...
3365   if (SrcClass == cFP) {
3366     // Change the floating point control register to use "round towards zero"
3367     // mode when truncating to an integer value.
3368     //
3369     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
3370     addFrameReference(BuildMI(*BB, IP, X86::FNSTCW16m, 4), CWFrameIdx);
3371
3372     // Load the old value of the high byte of the control word...
3373     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
3374     addFrameReference(BuildMI(*BB, IP, X86::MOV8rm, 4, HighPartOfCW),
3375                       CWFrameIdx, 1);
3376
3377     // Set the high part to be round to zero...
3378     addFrameReference(BuildMI(*BB, IP, X86::MOV8mi, 5),
3379                       CWFrameIdx, 1).addImm(12);
3380
3381     // Reload the modified control word now...
3382     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
3383
3384     // Restore the memory image of control word to original value
3385     addFrameReference(BuildMI(*BB, IP, X86::MOV8mr, 5),
3386                       CWFrameIdx, 1).addReg(HighPartOfCW);
3387
3388     // We don't have the facilities for directly storing byte sized data to
3389     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
3390     // larger classes because we only have signed FP stores.
3391     unsigned StoreClass  = DestClass;
3392     const Type *StoreTy  = DestTy;
3393     if (StoreClass == cByte || DestTy->isUnsigned())
3394       switch (StoreClass) {
3395       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
3396       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
3397       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
3398       // The following treatment of cLong may not be perfectly right,
3399       // but it survives chains of casts of the form
3400       // double->ulong->double.
3401       case cLong:  StoreTy = Type::LongTy;  StoreClass = cLong;  break;
3402       default: assert(0 && "Unknown store class!");
3403       }
3404
3405     // Spill the integer to memory and reload it from there...
3406     int FrameIdx =
3407       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
3408
3409     static const unsigned Op1[] =
3410       { 0, X86::FIST16m, X86::FIST32m, 0, X86::FISTP64m };
3411     addFrameReference(BuildMI(*BB, IP, Op1[StoreClass], 5),
3412                       FrameIdx).addReg(SrcReg);
3413
3414     if (DestClass == cLong) {
3415       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg), FrameIdx);
3416       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg+1),
3417                         FrameIdx, 4);
3418     } else {
3419       static const unsigned Op2[] = { X86::MOV8rm, X86::MOV16rm, X86::MOV32rm };
3420       addFrameReference(BuildMI(*BB, IP, Op2[DestClass], 4, DestReg), FrameIdx);
3421     }
3422
3423     // Reload the original control word now...
3424     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
3425     return;
3426   }
3427
3428   // Anything we haven't handled already, we can't (yet) handle at all.
3429   assert(0 && "Unhandled cast instruction!");
3430   abort();
3431 }
3432
3433 /// visitVANextInst - Implement the va_next instruction...
3434 ///
3435 void ISel::visitVANextInst(VANextInst &I) {
3436   unsigned VAList = getReg(I.getOperand(0));
3437   unsigned DestReg = getReg(I);
3438
3439   unsigned Size;
3440   switch (I.getArgType()->getTypeID()) {
3441   default:
3442     std::cerr << I;
3443     assert(0 && "Error: bad type for va_next instruction!");
3444     return;
3445   case Type::PointerTyID:
3446   case Type::UIntTyID:
3447   case Type::IntTyID:
3448     Size = 4;
3449     break;
3450   case Type::ULongTyID:
3451   case Type::LongTyID:
3452   case Type::DoubleTyID:
3453     Size = 8;
3454     break;
3455   }
3456
3457   // Increment the VAList pointer...
3458   BuildMI(BB, X86::ADD32ri, 2, DestReg).addReg(VAList).addImm(Size);
3459 }
3460
3461 void ISel::visitVAArgInst(VAArgInst &I) {
3462   unsigned VAList = getReg(I.getOperand(0));
3463   unsigned DestReg = getReg(I);
3464
3465   switch (I.getType()->getTypeID()) {
3466   default:
3467     std::cerr << I;
3468     assert(0 && "Error: bad type for va_next instruction!");
3469     return;
3470   case Type::PointerTyID:
3471   case Type::UIntTyID:
3472   case Type::IntTyID:
3473     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
3474     break;
3475   case Type::ULongTyID:
3476   case Type::LongTyID:
3477     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
3478     addRegOffset(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), VAList, 4);
3479     break;
3480   case Type::DoubleTyID:
3481     addDirectMem(BuildMI(BB, X86::FLD64m, 4, DestReg), VAList);
3482     break;
3483   }
3484 }
3485
3486 /// visitGetElementPtrInst - instruction-select GEP instructions
3487 ///
3488 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
3489   // If this GEP instruction will be folded into all of its users, we don't need
3490   // to explicitly calculate it!
3491   X86AddressMode AM;
3492   if (isGEPFoldable(0, I.getOperand(0), I.op_begin()+1, I.op_end(), AM)) {
3493     // Check all of the users of the instruction to see if they are loads and
3494     // stores.
3495     bool AllWillFold = true;
3496     for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI)
3497       if (cast<Instruction>(*UI)->getOpcode() != Instruction::Load)
3498         if (cast<Instruction>(*UI)->getOpcode() != Instruction::Store ||
3499             cast<Instruction>(*UI)->getOperand(0) == &I) {
3500           AllWillFold = false;
3501           break;
3502         }
3503
3504     // If the instruction is foldable, and will be folded into all users, don't
3505     // emit it!
3506     if (AllWillFold) return;
3507   }
3508
3509   unsigned outputReg = getReg(I);
3510   emitGEPOperation(BB, BB->end(), I.getOperand(0),
3511                    I.op_begin()+1, I.op_end(), outputReg);
3512 }
3513
3514 /// getGEPIndex - Inspect the getelementptr operands specified with GEPOps and
3515 /// GEPTypes (the derived types being stepped through at each level).  On return
3516 /// from this function, if some indexes of the instruction are representable as
3517 /// an X86 lea instruction, the machine operands are put into the Ops
3518 /// instruction and the consumed indexes are poped from the GEPOps/GEPTypes
3519 /// lists.  Otherwise, GEPOps.size() is returned.  If this returns a an
3520 /// addressing mode that only partially consumes the input, the BaseReg input of
3521 /// the addressing mode must be left free.
3522 ///
3523 /// Note that there is one fewer entry in GEPTypes than there is in GEPOps.
3524 ///
3525 void ISel::getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
3526                        std::vector<Value*> &GEPOps,
3527                        std::vector<const Type*> &GEPTypes,
3528                        X86AddressMode &AM) {
3529   const TargetData &TD = TM.getTargetData();
3530
3531   // Clear out the state we are working with...
3532   AM.BaseType = X86AddressMode::RegBase;
3533   AM.Base.Reg = 0;   // No base register
3534   AM.Scale = 1;      // Unit scale
3535   AM.IndexReg = 0;   // No index register
3536   AM.Disp = 0;       // No displacement
3537
3538   // While there are GEP indexes that can be folded into the current address,
3539   // keep processing them.
3540   while (!GEPTypes.empty()) {
3541     if (const StructType *StTy = dyn_cast<StructType>(GEPTypes.back())) {
3542       // It's a struct access.  CUI is the index into the structure,
3543       // which names the field. This index must have unsigned type.
3544       const ConstantUInt *CUI = cast<ConstantUInt>(GEPOps.back());
3545
3546       // Use the TargetData structure to pick out what the layout of the
3547       // structure is in memory.  Since the structure index must be constant, we
3548       // can get its value and use it to find the right byte offset from the
3549       // StructLayout class's list of structure member offsets.
3550       AM.Disp += TD.getStructLayout(StTy)->MemberOffsets[CUI->getValue()];
3551       GEPOps.pop_back();        // Consume a GEP operand
3552       GEPTypes.pop_back();
3553     } else {
3554       // It's an array or pointer access: [ArraySize x ElementType].
3555       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
3556       Value *idx = GEPOps.back();
3557
3558       // idx is the index into the array.  Unlike with structure
3559       // indices, we may not know its actual value at code-generation
3560       // time.
3561
3562       // If idx is a constant, fold it into the offset.
3563       unsigned TypeSize = TD.getTypeSize(SqTy->getElementType());
3564       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
3565         AM.Disp += TypeSize*CSI->getValue();
3566       } else if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(idx)) {
3567         AM.Disp += TypeSize*CUI->getValue();
3568       } else {
3569         // If the index reg is already taken, we can't handle this index.
3570         if (AM.IndexReg) return;
3571
3572         // If this is a size that we can handle, then add the index as
3573         switch (TypeSize) {
3574         case 1: case 2: case 4: case 8:
3575           // These are all acceptable scales on X86.
3576           AM.Scale = TypeSize;
3577           break;
3578         default:
3579           // Otherwise, we can't handle this scale
3580           return;
3581         }
3582
3583         if (CastInst *CI = dyn_cast<CastInst>(idx))
3584           if (CI->getOperand(0)->getType() == Type::IntTy ||
3585               CI->getOperand(0)->getType() == Type::UIntTy)
3586             idx = CI->getOperand(0);
3587
3588         AM.IndexReg = MBB ? getReg(idx, MBB, IP) : 1;
3589       }
3590
3591       GEPOps.pop_back();        // Consume a GEP operand
3592       GEPTypes.pop_back();
3593     }
3594   }
3595
3596   // GEPTypes is empty, which means we have a single operand left.  Set it as
3597   // the base register.
3598   //
3599   assert(AM.Base.Reg == 0);
3600
3601   if (AllocaInst *AI = dyn_castFixedAlloca(GEPOps.back())) {
3602     AM.BaseType = X86AddressMode::FrameIndexBase;
3603     AM.Base.FrameIndex = getFixedSizedAllocaFI(AI);
3604     GEPOps.pop_back();
3605     return;
3606   }
3607
3608 #if 0   // FIXME: TODO!
3609   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
3610     // FIXME: When addressing modes are more powerful/correct, we could load
3611     // global addresses directly as 32-bit immediates.
3612   }
3613 #endif
3614
3615   AM.Base.Reg = MBB ? getReg(GEPOps[0], MBB, IP) : 1;
3616   GEPOps.pop_back();        // Consume the last GEP operand
3617 }
3618
3619
3620 /// isGEPFoldable - Return true if the specified GEP can be completely
3621 /// folded into the addressing mode of a load/store or lea instruction.
3622 bool ISel::isGEPFoldable(MachineBasicBlock *MBB,
3623                          Value *Src, User::op_iterator IdxBegin,
3624                          User::op_iterator IdxEnd, X86AddressMode &AM) {
3625
3626   std::vector<Value*> GEPOps;
3627   GEPOps.resize(IdxEnd-IdxBegin+1);
3628   GEPOps[0] = Src;
3629   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
3630
3631   std::vector<const Type*>
3632     GEPTypes(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
3633              gep_type_end(Src->getType(), IdxBegin, IdxEnd));
3634
3635   MachineBasicBlock::iterator IP;
3636   if (MBB) IP = MBB->end();
3637   getGEPIndex(MBB, IP, GEPOps, GEPTypes, AM);
3638
3639   // We can fold it away iff the getGEPIndex call eliminated all operands.
3640   return GEPOps.empty();
3641 }
3642
3643 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
3644                             MachineBasicBlock::iterator IP,
3645                             Value *Src, User::op_iterator IdxBegin,
3646                             User::op_iterator IdxEnd, unsigned TargetReg) {
3647   const TargetData &TD = TM.getTargetData();
3648
3649   // If this is a getelementptr null, with all constant integer indices, just
3650   // replace it with TargetReg = 42.
3651   if (isa<ConstantPointerNull>(Src)) {
3652     User::op_iterator I = IdxBegin;
3653     for (; I != IdxEnd; ++I)
3654       if (!isa<ConstantInt>(*I))
3655         break;
3656     if (I == IdxEnd) {   // All constant indices
3657       unsigned Offset = TD.getIndexedOffset(Src->getType(),
3658                                          std::vector<Value*>(IdxBegin, IdxEnd));
3659       BuildMI(*MBB, IP, X86::MOV32ri, 1, TargetReg).addImm(Offset);
3660       return;
3661     }
3662   }
3663
3664   std::vector<Value*> GEPOps;
3665   GEPOps.resize(IdxEnd-IdxBegin+1);
3666   GEPOps[0] = Src;
3667   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
3668
3669   std::vector<const Type*> GEPTypes;
3670   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
3671                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
3672
3673   // Keep emitting instructions until we consume the entire GEP instruction.
3674   while (!GEPOps.empty()) {
3675     unsigned OldSize = GEPOps.size();
3676     X86AddressMode AM;
3677     getGEPIndex(MBB, IP, GEPOps, GEPTypes, AM);
3678
3679     if (GEPOps.size() != OldSize) {
3680       // getGEPIndex consumed some of the input.  Build an LEA instruction here.
3681       unsigned NextTarget = 0;
3682       if (!GEPOps.empty()) {
3683         assert(AM.Base.Reg == 0 &&
3684            "getGEPIndex should have left the base register open for chaining!");
3685         NextTarget = AM.Base.Reg = makeAnotherReg(Type::UIntTy);
3686       }
3687
3688       if (AM.BaseType == X86AddressMode::RegBase &&
3689               AM.IndexReg == 0 && AM.Disp == 0)
3690         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(AM.Base.Reg);
3691       else
3692         addFullAddress(BuildMI(*MBB, IP, X86::LEA32r, 5, TargetReg), AM);
3693       --IP;
3694       TargetReg = NextTarget;
3695     } else if (GEPTypes.empty()) {
3696       // The getGEPIndex operation didn't want to build an LEA.  Check to see if
3697       // all operands are consumed but the base pointer.  If so, just load it
3698       // into the register.
3699       if (GlobalValue *GV = dyn_cast<GlobalValue>(GEPOps[0])) {
3700         BuildMI(*MBB, IP, X86::MOV32ri, 1, TargetReg).addGlobalAddress(GV);
3701       } else {
3702         unsigned BaseReg = getReg(GEPOps[0], MBB, IP);
3703         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(BaseReg);
3704       }
3705       break;                // we are now done
3706
3707     } else {
3708       // It's an array or pointer access: [ArraySize x ElementType].
3709       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
3710       Value *idx = GEPOps.back();
3711       GEPOps.pop_back();        // Consume a GEP operand
3712       GEPTypes.pop_back();
3713
3714       // Many GEP instructions use a [cast (int/uint) to LongTy] as their
3715       // operand on X86.  Handle this case directly now...
3716       if (CastInst *CI = dyn_cast<CastInst>(idx))
3717         if (CI->getOperand(0)->getType() == Type::IntTy ||
3718             CI->getOperand(0)->getType() == Type::UIntTy)
3719           idx = CI->getOperand(0);
3720
3721       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
3722       // must find the size of the pointed-to type (Not coincidentally, the next
3723       // type is the type of the elements in the array).
3724       const Type *ElTy = SqTy->getElementType();
3725       unsigned elementSize = TD.getTypeSize(ElTy);
3726
3727       // If idxReg is a constant, we don't need to perform the multiply!
3728       if (ConstantInt *CSI = dyn_cast<ConstantInt>(idx)) {
3729         if (!CSI->isNullValue()) {
3730           unsigned Offset = elementSize*CSI->getRawValue();
3731           unsigned Reg = makeAnotherReg(Type::UIntTy);
3732           BuildMI(*MBB, IP, X86::ADD32ri, 2, TargetReg)
3733                                 .addReg(Reg).addImm(Offset);
3734           --IP;            // Insert the next instruction before this one.
3735           TargetReg = Reg; // Codegen the rest of the GEP into this
3736         }
3737       } else if (elementSize == 1) {
3738         // If the element size is 1, we don't have to multiply, just add
3739         unsigned idxReg = getReg(idx, MBB, IP);
3740         unsigned Reg = makeAnotherReg(Type::UIntTy);
3741         BuildMI(*MBB, IP, X86::ADD32rr, 2,TargetReg).addReg(Reg).addReg(idxReg);
3742         --IP;            // Insert the next instruction before this one.
3743         TargetReg = Reg; // Codegen the rest of the GEP into this
3744       } else {
3745         unsigned idxReg = getReg(idx, MBB, IP);
3746         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
3747
3748         // Make sure we can back the iterator up to point to the first
3749         // instruction emitted.
3750         MachineBasicBlock::iterator BeforeIt = IP;
3751         if (IP == MBB->begin())
3752           BeforeIt = MBB->end();
3753         else
3754           --BeforeIt;
3755         doMultiplyConst(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSize);
3756
3757         // Emit an ADD to add OffsetReg to the basePtr.
3758         unsigned Reg = makeAnotherReg(Type::UIntTy);
3759         BuildMI(*MBB, IP, X86::ADD32rr, 2, TargetReg)
3760                           .addReg(Reg).addReg(OffsetReg);
3761
3762         // Step to the first instruction of the multiply.
3763         if (BeforeIt == MBB->end())
3764           IP = MBB->begin();
3765         else
3766           IP = ++BeforeIt;
3767
3768         TargetReg = Reg; // Codegen the rest of the GEP into this
3769       }
3770     }
3771   }
3772 }
3773
3774 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
3775 /// frame manager, otherwise do it the hard way.
3776 ///
3777 void ISel::visitAllocaInst(AllocaInst &I) {
3778   // If this is a fixed size alloca in the entry block for the function, we
3779   // statically stack allocate the space, so we don't need to do anything here.
3780   //
3781   if (dyn_castFixedAlloca(&I)) return;
3782
3783   // Find the data size of the alloca inst's getAllocatedType.
3784   const Type *Ty = I.getAllocatedType();
3785   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
3786
3787   // Create a register to hold the temporary result of multiplying the type size
3788   // constant by the variable amount.
3789   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
3790   unsigned SrcReg1 = getReg(I.getArraySize());
3791
3792   // TotalSizeReg = mul <numelements>, <TypeSize>
3793   MachineBasicBlock::iterator MBBI = BB->end();
3794   doMultiplyConst(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, TySize);
3795
3796   // AddedSize = add <TotalSizeReg>, 15
3797   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
3798   BuildMI(BB, X86::ADD32ri, 2, AddedSizeReg).addReg(TotalSizeReg).addImm(15);
3799
3800   // AlignedSize = and <AddedSize>, ~15
3801   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
3802   BuildMI(BB, X86::AND32ri, 2, AlignedSize).addReg(AddedSizeReg).addImm(~15);
3803
3804   // Subtract size from stack pointer, thereby allocating some space.
3805   BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
3806
3807   // Put a pointer to the space into the result register, by copying
3808   // the stack pointer.
3809   BuildMI(BB, X86::MOV32rr, 1, getReg(I)).addReg(X86::ESP);
3810
3811   // Inform the Frame Information that we have just allocated a variable-sized
3812   // object.
3813   F->getFrameInfo()->CreateVariableSizedObject();
3814 }
3815
3816 /// visitMallocInst - Malloc instructions are code generated into direct calls
3817 /// to the library malloc.
3818 ///
3819 void ISel::visitMallocInst(MallocInst &I) {
3820   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
3821   unsigned Arg;
3822
3823   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
3824     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
3825   } else {
3826     Arg = makeAnotherReg(Type::UIntTy);
3827     unsigned Op0Reg = getReg(I.getOperand(0));
3828     MachineBasicBlock::iterator MBBI = BB->end();
3829     doMultiplyConst(BB, MBBI, Arg, Type::UIntTy, Op0Reg, AllocSize);
3830   }
3831
3832   std::vector<ValueRecord> Args;
3833   Args.push_back(ValueRecord(Arg, Type::UIntTy));
3834   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
3835                                   1).addExternalSymbol("malloc", true);
3836   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
3837 }
3838
3839
3840 /// visitFreeInst - Free instructions are code gen'd to call the free libc
3841 /// function.
3842 ///
3843 void ISel::visitFreeInst(FreeInst &I) {
3844   std::vector<ValueRecord> Args;
3845   Args.push_back(ValueRecord(I.getOperand(0)));
3846   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
3847                                   1).addExternalSymbol("free", true);
3848   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
3849 }
3850
3851 /// createX86SimpleInstructionSelector - This pass converts an LLVM function
3852 /// into a machine code representation is a very simple peep-hole fashion.  The
3853 /// generated code sucks but the implementation is nice and simple.
3854 ///
3855 FunctionPass *llvm::createX86SimpleInstructionSelector(TargetMachine &TM) {
3856   return new ISel(TM);
3857 }