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 X86ISel : public FunctionPass, InstVisitor<X86ISel> {
  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     X86ISel(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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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(); isa<PHINode>(I); ++I) {
 647       PHINode *PN = const_cast<PHINode*>(dyn_cast<PHINode>(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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::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 X86ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
1458                      const std::vector<ValueRecord> &Args) {
1459   // Count how many bytes are to be pushed on the stack...
1460   unsigned NumBytes = 0;
1461
1462   if (!Args.empty()) {
1463     for (unsigned i = 0, e = Args.size(); i != e; ++i)
1464       switch (getClassB(Args[i].Ty)) {
1465       case cByte: case cShort: case cInt:
1466         NumBytes += 4; break;
1467       case cLong:
1468         NumBytes += 8; break;
1469       case cFP:
1470         NumBytes += Args[i].Ty == Type::FloatTy ? 4 : 8;
1471         break;
1472       default: assert(0 && "Unknown class!");
1473       }
1474
1475     // Adjust the stack pointer for the new arguments...
1476     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(NumBytes);
1477
1478     // Arguments go on the stack in reverse order, as specified by the ABI.
1479     unsigned ArgOffset = 0;
1480     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1481       unsigned ArgReg;
1482       switch (getClassB(Args[i].Ty)) {
1483       case cByte:
1484         if (Args[i].Val && isa<ConstantBool>(Args[i].Val)) {
1485           addRegOffset(BuildMI(BB, X86::MOV32mi, 5), X86::ESP, ArgOffset)
1486             .addImm(Args[i].Val == ConstantBool::True);
1487           break;
1488         }
1489         // FALL THROUGH
1490       case cShort:
1491         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1492           // Zero/Sign extend constant, then stuff into memory.
1493           ConstantInt *Val = cast<ConstantInt>(Args[i].Val);
1494           Val = cast<ConstantInt>(ConstantExpr::getCast(Val, Type::IntTy));
1495           addRegOffset(BuildMI(BB, X86::MOV32mi, 5), X86::ESP, ArgOffset)
1496             .addImm(Val->getRawValue() & 0xFFFFFFFF);
1497         } else {
1498           // Promote arg to 32 bits wide into a temporary register...
1499           ArgReg = makeAnotherReg(Type::UIntTy);
1500           promote32(ArgReg, Args[i]);
1501           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1502                        X86::ESP, ArgOffset).addReg(ArgReg);
1503         }
1504         break;
1505       case cInt:
1506         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1507           unsigned Val = cast<ConstantInt>(Args[i].Val)->getRawValue();
1508           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1509                        X86::ESP, ArgOffset).addImm(Val);
1510         } else if (Args[i].Val && isa<ConstantPointerNull>(Args[i].Val)) {
1511           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1512                        X86::ESP, ArgOffset).addImm(0);
1513         } else {
1514           ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1515           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1516                        X86::ESP, ArgOffset).addReg(ArgReg);
1517         }
1518         break;
1519       case cLong:
1520         if (Args[i].Val && isa<ConstantInt>(Args[i].Val)) {
1521           uint64_t Val = cast<ConstantInt>(Args[i].Val)->getRawValue();
1522           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1523                        X86::ESP, ArgOffset).addImm(Val & ~0U);
1524           addRegOffset(BuildMI(BB, X86::MOV32mi, 5),
1525                        X86::ESP, ArgOffset+4).addImm(Val >> 32ULL);
1526         } else {
1527           ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1528           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1529                        X86::ESP, ArgOffset).addReg(ArgReg);
1530           addRegOffset(BuildMI(BB, X86::MOV32mr, 5),
1531                        X86::ESP, ArgOffset+4).addReg(ArgReg+1);
1532         }
1533         ArgOffset += 4;        // 8 byte entry, not 4.
1534         break;
1535
1536       case cFP:
1537         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1538         if (Args[i].Ty == Type::FloatTy) {
1539           addRegOffset(BuildMI(BB, X86::FST32m, 5),
1540                        X86::ESP, ArgOffset).addReg(ArgReg);
1541         } else {
1542           assert(Args[i].Ty == Type::DoubleTy && "Unknown FP type!");
1543           addRegOffset(BuildMI(BB, X86::FST64m, 5),
1544                        X86::ESP, ArgOffset).addReg(ArgReg);
1545           ArgOffset += 4;       // 8 byte entry, not 4.
1546         }
1547         break;
1548
1549       default: assert(0 && "Unknown class!");
1550       }
1551       ArgOffset += 4;
1552     }
1553   } else {
1554     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(0);
1555   }
1556
1557   BB->push_back(CallMI);
1558
1559   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addImm(NumBytes);
1560
1561   // If there is a return value, scavenge the result from the location the call
1562   // leaves it in...
1563   //
1564   if (Ret.Ty != Type::VoidTy) {
1565     unsigned DestClass = getClassB(Ret.Ty);
1566     switch (DestClass) {
1567     case cByte:
1568     case cShort:
1569     case cInt: {
1570       // Integral results are in %eax, or the appropriate portion
1571       // thereof.
1572       static const unsigned regRegMove[] = {
1573         X86::MOV8rr, X86::MOV16rr, X86::MOV32rr
1574       };
1575       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
1576       BuildMI(BB, regRegMove[DestClass], 1, Ret.Reg).addReg(AReg[DestClass]);
1577       break;
1578     }
1579     case cFP:     // Floating-point return values live in %ST(0)
1580       BuildMI(BB, X86::FpGETRESULT, 1, Ret.Reg);
1581       break;
1582     case cLong:   // Long values are left in EDX:EAX
1583       BuildMI(BB, X86::MOV32rr, 1, Ret.Reg).addReg(X86::EAX);
1584       BuildMI(BB, X86::MOV32rr, 1, Ret.Reg+1).addReg(X86::EDX);
1585       break;
1586     default: assert(0 && "Unknown class!");
1587     }
1588   }
1589 }
1590
1591
1592 /// visitCallInst - Push args on stack and do a procedure call instruction.
1593 void X86ISel::visitCallInst(CallInst &CI) {
1594   MachineInstr *TheCall;
1595   if (Function *F = CI.getCalledFunction()) {
1596     // Is it an intrinsic function call?
1597     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) {
1598       visitIntrinsicCall(ID, CI);   // Special intrinsics are not handled here
1599       return;
1600     }
1601
1602     // Emit a CALL instruction with PC-relative displacement.
1603     TheCall = BuildMI(X86::CALLpcrel32, 1).addGlobalAddress(F, true);
1604   } else {  // Emit an indirect call...
1605     unsigned Reg = getReg(CI.getCalledValue());
1606     TheCall = BuildMI(X86::CALL32r, 1).addReg(Reg);
1607   }
1608
1609   std::vector<ValueRecord> Args;
1610   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
1611     Args.push_back(ValueRecord(CI.getOperand(i)));
1612
1613   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
1614   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args);
1615 }
1616
1617 /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
1618 /// function, lowering any calls to unknown intrinsic functions into the
1619 /// equivalent LLVM code.
1620 ///
1621 void X86ISel::LowerUnknownIntrinsicFunctionCalls(Function &F) {
1622   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1623     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
1624       if (CallInst *CI = dyn_cast<CallInst>(I++))
1625         if (Function *F = CI->getCalledFunction())
1626           switch (F->getIntrinsicID()) {
1627           case Intrinsic::not_intrinsic:
1628           case Intrinsic::vastart:
1629           case Intrinsic::vacopy:
1630           case Intrinsic::vaend:
1631           case Intrinsic::returnaddress:
1632           case Intrinsic::frameaddress:
1633           case Intrinsic::memcpy:
1634           case Intrinsic::memset:
1635           case Intrinsic::isunordered:
1636           case Intrinsic::readport:
1637           case Intrinsic::writeport:
1638             // We directly implement these intrinsics
1639             break;
1640           case Intrinsic::readio: {
1641             // On X86, memory operations are in-order.  Lower this intrinsic
1642             // into a volatile load.
1643             Instruction *Before = CI->getPrev();
1644             LoadInst * LI = new LoadInst(CI->getOperand(1), "", true, CI);
1645             CI->replaceAllUsesWith(LI);
1646             BB->getInstList().erase(CI);
1647             break;
1648           }
1649           case Intrinsic::writeio: {
1650             // On X86, memory operations are in-order.  Lower this intrinsic
1651             // into a volatile store.
1652             Instruction *Before = CI->getPrev();
1653             StoreInst *LI = new StoreInst(CI->getOperand(1),
1654                                           CI->getOperand(2), true, CI);
1655             CI->replaceAllUsesWith(LI);
1656             BB->getInstList().erase(CI);
1657             break;
1658           }
1659           default:
1660             // All other intrinsic calls we must lower.
1661             Instruction *Before = CI->getPrev();
1662             TM.getIntrinsicLowering().LowerIntrinsicCall(CI);
1663             if (Before) {        // Move iterator to instruction after call
1664               I = Before; ++I;
1665             } else {
1666               I = BB->begin();
1667             }
1668           }
1669 }
1670
1671 void X86ISel::visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI) {
1672   unsigned TmpReg1, TmpReg2;
1673   switch (ID) {
1674   case Intrinsic::vastart:
1675     // Get the address of the first vararg value...
1676     TmpReg1 = getReg(CI);
1677     addFrameReference(BuildMI(BB, X86::LEA32r, 5, TmpReg1), VarArgsFrameIndex);
1678     return;
1679
1680   case Intrinsic::vacopy:
1681     TmpReg1 = getReg(CI);
1682     TmpReg2 = getReg(CI.getOperand(1));
1683     BuildMI(BB, X86::MOV32rr, 1, TmpReg1).addReg(TmpReg2);
1684     return;
1685   case Intrinsic::vaend: return;   // Noop on X86
1686
1687   case Intrinsic::returnaddress:
1688   case Intrinsic::frameaddress:
1689     TmpReg1 = getReg(CI);
1690     if (cast<Constant>(CI.getOperand(1))->isNullValue()) {
1691       if (ID == Intrinsic::returnaddress) {
1692         // Just load the return address
1693         addFrameReference(BuildMI(BB, X86::MOV32rm, 4, TmpReg1),
1694                           ReturnAddressIndex);
1695       } else {
1696         addFrameReference(BuildMI(BB, X86::LEA32r, 4, TmpReg1),
1697                           ReturnAddressIndex, -4);
1698       }
1699     } else {
1700       // Values other than zero are not implemented yet.
1701       BuildMI(BB, X86::MOV32ri, 1, TmpReg1).addImm(0);
1702     }
1703     return;
1704
1705   case Intrinsic::isunordered:
1706     TmpReg1 = getReg(CI.getOperand(1));
1707     TmpReg2 = getReg(CI.getOperand(2));
1708     emitUCOMr(BB, BB->end(), TmpReg2, TmpReg1);
1709     TmpReg2 = getReg(CI);
1710     BuildMI(BB, X86::SETPr, 0, TmpReg2);
1711     return;
1712
1713   case Intrinsic::memcpy: {
1714     assert(CI.getNumOperands() == 5 && "Illegal llvm.memcpy call!");
1715     unsigned Align = 1;
1716     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1717       Align = AlignC->getRawValue();
1718       if (Align == 0) Align = 1;
1719     }
1720
1721     // Turn the byte code into # iterations
1722     unsigned CountReg;
1723     unsigned Opcode;
1724     switch (Align & 3) {
1725     case 2:   // WORD aligned
1726       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1727         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1728       } else {
1729         CountReg = makeAnotherReg(Type::IntTy);
1730         unsigned ByteReg = getReg(CI.getOperand(3));
1731         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
1732       }
1733       Opcode = X86::REP_MOVSW;
1734       break;
1735     case 0:   // DWORD aligned
1736       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1737         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1738       } else {
1739         CountReg = makeAnotherReg(Type::IntTy);
1740         unsigned ByteReg = getReg(CI.getOperand(3));
1741         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
1742       }
1743       Opcode = X86::REP_MOVSD;
1744       break;
1745     default:  // BYTE aligned
1746       CountReg = getReg(CI.getOperand(3));
1747       Opcode = X86::REP_MOVSB;
1748       break;
1749     }
1750
1751     // No matter what the alignment is, we put the source in ESI, the
1752     // destination in EDI, and the count in ECX.
1753     TmpReg1 = getReg(CI.getOperand(1));
1754     TmpReg2 = getReg(CI.getOperand(2));
1755     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
1756     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
1757     BuildMI(BB, X86::MOV32rr, 1, X86::ESI).addReg(TmpReg2);
1758     BuildMI(BB, Opcode, 0);
1759     return;
1760   }
1761   case Intrinsic::memset: {
1762     assert(CI.getNumOperands() == 5 && "Illegal llvm.memset call!");
1763     unsigned Align = 1;
1764     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1765       Align = AlignC->getRawValue();
1766       if (Align == 0) Align = 1;
1767     }
1768
1769     // Turn the byte code into # iterations
1770     unsigned CountReg;
1771     unsigned Opcode;
1772     if (ConstantInt *ValC = dyn_cast<ConstantInt>(CI.getOperand(2))) {
1773       unsigned Val = ValC->getRawValue() & 255;
1774
1775       // If the value is a constant, then we can potentially use larger copies.
1776       switch (Align & 3) {
1777       case 2:   // WORD aligned
1778         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1779           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1780         } else {
1781           CountReg = makeAnotherReg(Type::IntTy);
1782           unsigned ByteReg = getReg(CI.getOperand(3));
1783           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
1784         }
1785         BuildMI(BB, X86::MOV16ri, 1, X86::AX).addImm((Val << 8) | Val);
1786         Opcode = X86::REP_STOSW;
1787         break;
1788       case 0:   // DWORD aligned
1789         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1790           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1791         } else {
1792           CountReg = makeAnotherReg(Type::IntTy);
1793           unsigned ByteReg = getReg(CI.getOperand(3));
1794           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
1795         }
1796         Val = (Val << 8) | Val;
1797         BuildMI(BB, X86::MOV32ri, 1, X86::EAX).addImm((Val << 16) | Val);
1798         Opcode = X86::REP_STOSD;
1799         break;
1800       default:  // BYTE aligned
1801         CountReg = getReg(CI.getOperand(3));
1802         BuildMI(BB, X86::MOV8ri, 1, X86::AL).addImm(Val);
1803         Opcode = X86::REP_STOSB;
1804         break;
1805       }
1806     } else {
1807       // If it's not a constant value we are storing, just fall back.  We could
1808       // try to be clever to form 16 bit and 32 bit values, but we don't yet.
1809       unsigned ValReg = getReg(CI.getOperand(2));
1810       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
1811       CountReg = getReg(CI.getOperand(3));
1812       Opcode = X86::REP_STOSB;
1813     }
1814
1815     // No matter what the alignment is, we put the source in ESI, the
1816     // destination in EDI, and the count in ECX.
1817     TmpReg1 = getReg(CI.getOperand(1));
1818     //TmpReg2 = getReg(CI.getOperand(2));
1819     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
1820     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
1821     BuildMI(BB, Opcode, 0);
1822     return;
1823   }
1824
1825   case Intrinsic::readport: {
1826     // First, determine that the size of the operand falls within the acceptable
1827     // range for this architecture.
1828     //
1829     if (getClassB(CI.getOperand(1)->getType()) != cShort) {
1830       std::cerr << "llvm.readport: Address size is not 16 bits\n";
1831       exit(1);
1832     }
1833
1834     // Now, move the I/O port address into the DX register and use the IN
1835     // instruction to get the input data.
1836     //
1837     unsigned Class = getClass(CI.getCalledFunction()->getReturnType());
1838     unsigned DestReg = getReg(CI);
1839
1840     // If the port is a single-byte constant, use the immediate form.
1841     if (ConstantInt *C = dyn_cast<ConstantInt>(CI.getOperand(1)))
1842       if ((C->getRawValue() & 255) == C->getRawValue()) {
1843         switch (Class) {
1844         case cByte:
1845           BuildMI(BB, X86::IN8ri, 1).addImm((unsigned char)C->getRawValue());
1846           BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
1847           return;
1848         case cShort:
1849           BuildMI(BB, X86::IN16ri, 1).addImm((unsigned char)C->getRawValue());
1850           BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AX);
1851           return;
1852         case cInt:
1853           BuildMI(BB, X86::IN32ri, 1).addImm((unsigned char)C->getRawValue());
1854           BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::EAX);
1855           return;
1856         }
1857       }
1858
1859     unsigned Reg = getReg(CI.getOperand(1));
1860     BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(Reg);
1861     switch (Class) {
1862     case cByte:
1863       BuildMI(BB, X86::IN8rr, 0);
1864       BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AL);
1865       break;
1866     case cShort:
1867       BuildMI(BB, X86::IN16rr, 0);
1868       BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::AX);
1869       break;
1870     case cInt:
1871       BuildMI(BB, X86::IN32rr, 0);
1872       BuildMI(BB, X86::MOV8rr, 1, DestReg).addReg(X86::EAX);
1873       break;
1874     default:
1875       std::cerr << "Cannot do input on this data type";
1876       exit (1);
1877     }
1878     return;
1879   }
1880
1881   case Intrinsic::writeport: {
1882     // First, determine that the size of the operand falls within the
1883     // acceptable range for this architecture.
1884     if (getClass(CI.getOperand(2)->getType()) != cShort) {
1885       std::cerr << "llvm.writeport: Address size is not 16 bits\n";
1886       exit(1);
1887     }
1888
1889     unsigned Class = getClassB(CI.getOperand(1)->getType());
1890     unsigned ValReg = getReg(CI.getOperand(1));
1891     switch (Class) {
1892     case cByte:
1893       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
1894       break;
1895     case cShort:
1896       BuildMI(BB, X86::MOV16rr, 1, X86::AX).addReg(ValReg);
1897       break;
1898     case cInt:
1899       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(ValReg);
1900       break;
1901     default:
1902       std::cerr << "llvm.writeport: invalid data type for X86 target";
1903       exit(1);
1904     }
1905
1906
1907     // If the port is a single-byte constant, use the immediate form.
1908     if (ConstantInt *C = dyn_cast<ConstantInt>(CI.getOperand(2)))
1909       if ((C->getRawValue() & 255) == C->getRawValue()) {
1910         static const unsigned O[] = { X86::OUT8ir, X86::OUT16ir, X86::OUT32ir };
1911         BuildMI(BB, O[Class], 1).addImm((unsigned char)C->getRawValue());
1912         return;
1913       }
1914
1915     // Otherwise, move the I/O port address into the DX register and the value
1916     // to write into the AL/AX/EAX register.
1917     static const unsigned Opc[] = { X86::OUT8rr, X86::OUT16rr, X86::OUT32rr };
1918     unsigned Reg = getReg(CI.getOperand(2));
1919     BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(Reg);
1920     BuildMI(BB, Opc[Class], 0);
1921     return;
1922   }
1923
1924   default: assert(0 && "Error: unknown intrinsics should have been lowered!");
1925   }
1926 }
1927
1928 static bool isSafeToFoldLoadIntoInstruction(LoadInst &LI, Instruction &User) {
1929   if (LI.getParent() != User.getParent())
1930     return false;
1931   BasicBlock::iterator It = &LI;
1932   // Check all of the instructions between the load and the user.  We should
1933   // really use alias analysis here, but for now we just do something simple.
1934   for (++It; It != BasicBlock::iterator(&User); ++It) {
1935     switch (It->getOpcode()) {
1936     case Instruction::Free:
1937     case Instruction::Store:
1938     case Instruction::Call:
1939     case Instruction::Invoke:
1940       return false;
1941     case Instruction::Load:
1942       if (cast<LoadInst>(It)->isVolatile() && LI.isVolatile())
1943         return false;
1944       break;
1945     }
1946   }
1947   return true;
1948 }
1949
1950 /// visitSimpleBinary - Implement simple binary operators for integral types...
1951 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
1952 /// Xor.
1953 ///
1954 void X86ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
1955   unsigned DestReg = getReg(B);
1956   MachineBasicBlock::iterator MI = BB->end();
1957   Value *Op0 = B.getOperand(0), *Op1 = B.getOperand(1);
1958   unsigned Class = getClassB(B.getType());
1959
1960   // Special case: op Reg, load [mem]
1961   if (isa<LoadInst>(Op0) && !isa<LoadInst>(Op1) && Class != cLong &&
1962       Op0->hasOneUse() &&
1963       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op0), B))
1964     if (!B.swapOperands())
1965       std::swap(Op0, Op1);  // Make sure any loads are in the RHS.
1966
1967   if (isa<LoadInst>(Op1) && Class != cLong && Op1->hasOneUse() &&
1968       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op1), B)) {
1969
1970     unsigned Opcode;
1971     if (Class != cFP) {
1972       static const unsigned OpcodeTab[][3] = {
1973         // Arithmetic operators
1974         { X86::ADD8rm, X86::ADD16rm, X86::ADD32rm },  // ADD
1975         { X86::SUB8rm, X86::SUB16rm, X86::SUB32rm },  // SUB
1976
1977         // Bitwise operators
1978         { X86::AND8rm, X86::AND16rm, X86::AND32rm },  // AND
1979         { X86:: OR8rm, X86:: OR16rm, X86:: OR32rm },  // OR
1980         { X86::XOR8rm, X86::XOR16rm, X86::XOR32rm },  // XOR
1981       };
1982       Opcode = OpcodeTab[OperatorClass][Class];
1983     } else {
1984       static const unsigned OpcodeTab[][2] = {
1985         { X86::FADD32m, X86::FADD64m },  // ADD
1986         { X86::FSUB32m, X86::FSUB64m },  // SUB
1987       };
1988       const Type *Ty = Op0->getType();
1989       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
1990       Opcode = OpcodeTab[OperatorClass][Ty == Type::DoubleTy];
1991     }
1992
1993     unsigned Op0r = getReg(Op0);
1994     if (AllocaInst *AI =
1995         dyn_castFixedAlloca(cast<LoadInst>(Op1)->getOperand(0))) {
1996       unsigned FI = getFixedSizedAllocaFI(AI);
1997       addFrameReference(BuildMI(BB, Opcode, 5, DestReg).addReg(Op0r), FI);
1998
1999     } else {
2000       X86AddressMode AM;
2001       getAddressingMode(cast<LoadInst>(Op1)->getOperand(0), AM);
2002
2003       addFullAddress(BuildMI(BB, Opcode, 5, DestReg).addReg(Op0r), AM);
2004     }
2005     return;
2006   }
2007
2008   // If this is a floating point subtract, check to see if we can fold the first
2009   // operand in.
2010   if (Class == cFP && OperatorClass == 1 &&
2011       isa<LoadInst>(Op0) &&
2012       isSafeToFoldLoadIntoInstruction(*cast<LoadInst>(Op0), B)) {
2013     const Type *Ty = Op0->getType();
2014     assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
2015     unsigned Opcode = Ty == Type::FloatTy ? X86::FSUBR32m : X86::FSUBR64m;
2016
2017     unsigned Op1r = getReg(Op1);
2018     if (AllocaInst *AI =
2019         dyn_castFixedAlloca(cast<LoadInst>(Op0)->getOperand(0))) {
2020       unsigned FI = getFixedSizedAllocaFI(AI);
2021       addFrameReference(BuildMI(BB, Opcode, 5, DestReg).addReg(Op1r), FI);
2022     } else {
2023       X86AddressMode AM;
2024       getAddressingMode(cast<LoadInst>(Op0)->getOperand(0), AM);
2025
2026       addFullAddress(BuildMI(BB, Opcode, 5, DestReg).addReg(Op1r), AM);
2027     }
2028     return;
2029   }
2030
2031   emitSimpleBinaryOperation(BB, MI, Op0, Op1, OperatorClass, DestReg);
2032 }
2033
2034
2035 /// emitBinaryFPOperation - This method handles emission of floating point
2036 /// Add (0), Sub (1), Mul (2), and Div (3) operations.
2037 void X86ISel::emitBinaryFPOperation(MachineBasicBlock *BB,
2038                                     MachineBasicBlock::iterator IP,
2039                                     Value *Op0, Value *Op1,
2040                                     unsigned OperatorClass, unsigned DestReg) {
2041   // Special case: op Reg, <const fp>
2042   if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1))
2043     if (!Op1C->isExactlyValue(+0.0) && !Op1C->isExactlyValue(+1.0)) {
2044       // Create a constant pool entry for this constant.
2045       MachineConstantPool *CP = F->getConstantPool();
2046       unsigned CPI = CP->getConstantPoolIndex(Op1C);
2047       const Type *Ty = Op1->getType();
2048
2049       static const unsigned OpcodeTab[][4] = {
2050         { X86::FADD32m, X86::FSUB32m, X86::FMUL32m, X86::FDIV32m },   // Float
2051         { X86::FADD64m, X86::FSUB64m, X86::FMUL64m, X86::FDIV64m },   // Double
2052       };
2053
2054       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
2055       unsigned Opcode = OpcodeTab[Ty != Type::FloatTy][OperatorClass];
2056       unsigned Op0r = getReg(Op0, BB, IP);
2057       addConstantPoolReference(BuildMI(*BB, IP, Opcode, 5,
2058                                        DestReg).addReg(Op0r), CPI);
2059       return;
2060     }
2061
2062   // Special case: R1 = op <const fp>, R2
2063   if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op0))
2064     if (CFP->isExactlyValue(-0.0) && OperatorClass == 1) {
2065       // -0.0 - X === -X
2066       unsigned op1Reg = getReg(Op1, BB, IP);
2067       BuildMI(*BB, IP, X86::FCHS, 1, DestReg).addReg(op1Reg);
2068       return;
2069     } else if (!CFP->isExactlyValue(+0.0) && !CFP->isExactlyValue(+1.0)) {
2070       // R1 = op CST, R2  -->  R1 = opr R2, CST
2071
2072       // Create a constant pool entry for this constant.
2073       MachineConstantPool *CP = F->getConstantPool();
2074       unsigned CPI = CP->getConstantPoolIndex(CFP);
2075       const Type *Ty = CFP->getType();
2076
2077       static const unsigned OpcodeTab[][4] = {
2078         { X86::FADD32m, X86::FSUBR32m, X86::FMUL32m, X86::FDIVR32m }, // Float
2079         { X86::FADD64m, X86::FSUBR64m, X86::FMUL64m, X86::FDIVR64m }, // Double
2080       };
2081
2082       assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2083       unsigned Opcode = OpcodeTab[Ty != Type::FloatTy][OperatorClass];
2084       unsigned Op1r = getReg(Op1, BB, IP);
2085       addConstantPoolReference(BuildMI(*BB, IP, Opcode, 5,
2086                                        DestReg).addReg(Op1r), CPI);
2087       return;
2088     }
2089
2090   // General case.
2091   static const unsigned OpcodeTab[4] = {
2092     X86::FpADD, X86::FpSUB, X86::FpMUL, X86::FpDIV
2093   };
2094
2095   unsigned Opcode = OpcodeTab[OperatorClass];
2096   unsigned Op0r = getReg(Op0, BB, IP);
2097   unsigned Op1r = getReg(Op1, BB, IP);
2098   BuildMI(*BB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
2099 }
2100
2101 /// emitSimpleBinaryOperation - Implement simple binary operators for integral
2102 /// types...  OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for
2103 /// Or, 4 for Xor.
2104 ///
2105 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
2106 /// and constant expression support.
2107 ///
2108 void X86ISel::emitSimpleBinaryOperation(MachineBasicBlock *MBB,
2109                                         MachineBasicBlock::iterator IP,
2110                                         Value *Op0, Value *Op1,
2111                                         unsigned OperatorClass,
2112                                         unsigned DestReg) {
2113   unsigned Class = getClassB(Op0->getType());
2114
2115   if (Class == cFP) {
2116     assert(OperatorClass < 2 && "No logical ops for FP!");
2117     emitBinaryFPOperation(MBB, IP, Op0, Op1, OperatorClass, DestReg);
2118     return;
2119   }
2120
2121   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0))
2122     if (OperatorClass == 1) {
2123       static unsigned const NEGTab[] = {
2124         X86::NEG8r, X86::NEG16r, X86::NEG32r, 0, X86::NEG32r
2125       };
2126
2127       // sub 0, X -> neg X
2128       if (CI->isNullValue()) {
2129         unsigned op1Reg = getReg(Op1, MBB, IP);
2130         BuildMI(*MBB, IP, NEGTab[Class], 1, DestReg).addReg(op1Reg);
2131
2132         if (Class == cLong) {
2133           // We just emitted: Dl = neg Sl
2134           // Now emit       : T  = addc Sh, 0
2135           //                : Dh = neg T
2136           unsigned T = makeAnotherReg(Type::IntTy);
2137           BuildMI(*MBB, IP, X86::ADC32ri, 2, T).addReg(op1Reg+1).addImm(0);
2138           BuildMI(*MBB, IP, X86::NEG32r, 1, DestReg+1).addReg(T);
2139         }
2140         return;
2141       } else if (Op1->hasOneUse() && Class != cLong) {
2142         // sub C, X -> tmp = neg X; DestReg = add tmp, C.  This is better
2143         // than copying C into a temporary register, because of register
2144         // pressure (tmp and destreg can share a register.
2145         static unsigned const ADDRITab[] = {
2146           X86::ADD8ri, X86::ADD16ri, X86::ADD32ri, 0, X86::ADD32ri
2147         };
2148         unsigned op1Reg = getReg(Op1, MBB, IP);
2149         unsigned Tmp = makeAnotherReg(Op0->getType());
2150         BuildMI(*MBB, IP, NEGTab[Class], 1, Tmp).addReg(op1Reg);
2151         BuildMI(*MBB, IP, ADDRITab[Class], 2,
2152                 DestReg).addReg(Tmp).addImm(CI->getRawValue());
2153         return;
2154       }
2155     }
2156
2157   // Special case: op Reg, <const int>
2158   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
2159     unsigned Op0r = getReg(Op0, MBB, IP);
2160
2161     // xor X, -1 -> not X
2162     if (OperatorClass == 4 && Op1C->isAllOnesValue()) {
2163       static unsigned const NOTTab[] = {
2164         X86::NOT8r, X86::NOT16r, X86::NOT32r, 0, X86::NOT32r
2165       };
2166       BuildMI(*MBB, IP, NOTTab[Class], 1, DestReg).addReg(Op0r);
2167       if (Class == cLong)  // Invert the top part too
2168         BuildMI(*MBB, IP, X86::NOT32r, 1, DestReg+1).addReg(Op0r+1);
2169       return;
2170     }
2171
2172     // add X, -1 -> dec X
2173     if (OperatorClass == 0 && Op1C->isAllOnesValue() && Class != cLong) {
2174       // Note that we can't use dec for 64-bit decrements, because it does not
2175       // set the carry flag!
2176       static unsigned const DECTab[] = { X86::DEC8r, X86::DEC16r, X86::DEC32r };
2177       BuildMI(*MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
2178       return;
2179     }
2180
2181     // add X, 1 -> inc X
2182     if (OperatorClass == 0 && Op1C->equalsInt(1) && Class != cLong) {
2183       // Note that we can't use inc for 64-bit increments, because it does not
2184       // set the carry flag!
2185       static unsigned const INCTab[] = { X86::INC8r, X86::INC16r, X86::INC32r };
2186       BuildMI(*MBB, IP, INCTab[Class], 1, DestReg).addReg(Op0r);
2187       return;
2188     }
2189
2190     static const unsigned OpcodeTab[][5] = {
2191       // Arithmetic operators
2192       { X86::ADD8ri, X86::ADD16ri, X86::ADD32ri, 0, X86::ADD32ri },  // ADD
2193       { X86::SUB8ri, X86::SUB16ri, X86::SUB32ri, 0, X86::SUB32ri },  // SUB
2194
2195       // Bitwise operators
2196       { X86::AND8ri, X86::AND16ri, X86::AND32ri, 0, X86::AND32ri },  // AND
2197       { X86:: OR8ri, X86:: OR16ri, X86:: OR32ri, 0, X86::OR32ri  },  // OR
2198       { X86::XOR8ri, X86::XOR16ri, X86::XOR32ri, 0, X86::XOR32ri },  // XOR
2199     };
2200
2201     unsigned Opcode = OpcodeTab[OperatorClass][Class];
2202     unsigned Op1l = cast<ConstantInt>(Op1C)->getRawValue();
2203
2204     if (Class != cLong) {
2205       BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addImm(Op1l);
2206       return;
2207     }
2208
2209     // If this is a long value and the high or low bits have a special
2210     // property, emit some special cases.
2211     unsigned Op1h = cast<ConstantInt>(Op1C)->getRawValue() >> 32LL;
2212
2213     // If the constant is zero in the low 32-bits, just copy the low part
2214     // across and apply the normal 32-bit operation to the high parts.  There
2215     // will be no carry or borrow into the top.
2216     if (Op1l == 0) {
2217       if (OperatorClass != 2) // All but and...
2218         BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg).addReg(Op0r);
2219       else
2220         BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg).addImm(0);
2221       BuildMI(*MBB, IP, OpcodeTab[OperatorClass][cLong], 2, DestReg+1)
2222         .addReg(Op0r+1).addImm(Op1h);
2223       return;
2224     }
2225
2226     // If this is a logical operation and the top 32-bits are zero, just
2227     // operate on the lower 32.
2228     if (Op1h == 0 && OperatorClass > 1) {
2229       BuildMI(*MBB, IP, OpcodeTab[OperatorClass][cLong], 2, DestReg)
2230         .addReg(Op0r).addImm(Op1l);
2231       if (OperatorClass != 2)  // All but and
2232         BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg+1).addReg(Op0r+1);
2233       else
2234         BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
2235       return;
2236     }
2237
2238     // TODO: We could handle lots of other special cases here, such as AND'ing
2239     // with 0xFFFFFFFF00000000 -> noop, etc.
2240
2241     // Otherwise, code generate the full operation with a constant.
2242     static const unsigned TopTab[] = {
2243       X86::ADC32ri, X86::SBB32ri, X86::AND32ri, X86::OR32ri, X86::XOR32ri
2244     };
2245
2246     BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addImm(Op1l);
2247     BuildMI(*MBB, IP, TopTab[OperatorClass], 2, DestReg+1)
2248       .addReg(Op0r+1).addImm(Op1h);
2249     return;
2250   }
2251
2252   // Finally, handle the general case now.
2253   static const unsigned OpcodeTab[][5] = {
2254     // Arithmetic operators
2255     { X86::ADD8rr, X86::ADD16rr, X86::ADD32rr, 0, X86::ADD32rr },  // ADD
2256     { X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, 0, X86::SUB32rr },  // SUB
2257
2258     // Bitwise operators
2259     { X86::AND8rr, X86::AND16rr, X86::AND32rr, 0, X86::AND32rr },  // AND
2260     { X86:: OR8rr, X86:: OR16rr, X86:: OR32rr, 0, X86:: OR32rr },  // OR
2261     { X86::XOR8rr, X86::XOR16rr, X86::XOR32rr, 0, X86::XOR32rr },  // XOR
2262   };
2263
2264   unsigned Opcode = OpcodeTab[OperatorClass][Class];
2265   unsigned Op0r = getReg(Op0, MBB, IP);
2266   unsigned Op1r = getReg(Op1, MBB, IP);
2267   BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
2268
2269   if (Class == cLong) {        // Handle the upper 32 bits of long values...
2270     static const unsigned TopTab[] = {
2271       X86::ADC32rr, X86::SBB32rr, X86::AND32rr, X86::OR32rr, X86::XOR32rr
2272     };
2273     BuildMI(*MBB, IP, TopTab[OperatorClass], 2,
2274             DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
2275   }
2276 }
2277
2278 /// doMultiply - Emit appropriate instructions to multiply together the
2279 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
2280 /// result should be given as DestTy.
2281 ///
2282 void X86ISel::doMultiply(MachineBasicBlock *MBB,
2283                          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 X86ISel::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 X86ISel::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 X86ISel::emitMultiply(MachineBasicBlock *MBB,
2470                            MachineBasicBlock::iterator IP,
2471                            Value *Op0, Value *Op1, unsigned DestReg) {
2472   MachineBasicBlock &BB = *MBB;
2473   TypeClass Class = getClass(Op0->getType());
2474
2475   // Simple scalar multiply?
2476   unsigned Op0Reg  = getReg(Op0, &BB, IP);
2477   switch (Class) {
2478   case cByte:
2479   case cShort:
2480   case cInt:
2481     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2482       unsigned Val = (unsigned)CI->getRawValue(); // Isn't a 64-bit constant
2483       doMultiplyConst(&BB, IP, DestReg, Op0->getType(), Op0Reg, Val);
2484     } else {
2485       unsigned Op1Reg  = getReg(Op1, &BB, IP);
2486       doMultiply(&BB, IP, DestReg, Op1->getType(), Op0Reg, Op1Reg);
2487     }
2488     return;
2489   case cFP:
2490     emitBinaryFPOperation(MBB, IP, Op0, Op1, 2, DestReg);
2491     return;
2492   case cLong:
2493     break;
2494   }
2495
2496   // Long value.  We have to do things the hard way...
2497   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2498     unsigned CLow = CI->getRawValue();
2499     unsigned CHi  = CI->getRawValue() >> 32;
2500
2501     if (CLow == 0) {
2502       // If the low part of the constant is all zeros, things are simple.
2503       BuildMI(BB, IP, X86::MOV32ri, 1, DestReg).addImm(0);
2504       doMultiplyConst(&BB, IP, DestReg+1, Type::UIntTy, Op0Reg, CHi);
2505       return;
2506     }
2507
2508     // Multiply the two low parts... capturing carry into EDX
2509     unsigned OverflowReg = 0;
2510     if (CLow == 1) {
2511       BuildMI(BB, IP, X86::MOV32rr, 1, DestReg).addReg(Op0Reg);
2512     } else {
2513       unsigned Op1RegL = makeAnotherReg(Type::UIntTy);
2514       OverflowReg = makeAnotherReg(Type::UIntTy);
2515       BuildMI(BB, IP, X86::MOV32ri, 1, Op1RegL).addImm(CLow);
2516       BuildMI(BB, IP, X86::MOV32rr, 1, X86::EAX).addReg(Op0Reg);
2517       BuildMI(BB, IP, X86::MUL32r, 1).addReg(Op1RegL);  // AL*BL
2518
2519       BuildMI(BB, IP, X86::MOV32rr, 1, DestReg).addReg(X86::EAX);   // AL*BL
2520       BuildMI(BB, IP, X86::MOV32rr, 1,
2521               OverflowReg).addReg(X86::EDX);                    // AL*BL >> 32
2522     }
2523
2524     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
2525     doMultiplyConst(&BB, IP, AHBLReg, Type::UIntTy, Op0Reg+1, CLow);
2526
2527     unsigned AHBLplusOverflowReg;
2528     if (OverflowReg) {
2529       AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
2530       BuildMI(BB, IP, X86::ADD32rr, 2,                // AH*BL+(AL*BL >> 32)
2531               AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
2532     } else {
2533       AHBLplusOverflowReg = AHBLReg;
2534     }
2535
2536     if (CHi == 0) {
2537       BuildMI(BB, IP, X86::MOV32rr, 1, DestReg+1).addReg(AHBLplusOverflowReg);
2538     } else {
2539       unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
2540       doMultiplyConst(&BB, IP, ALBHReg, Type::UIntTy, Op0Reg, CHi);
2541
2542       BuildMI(BB, IP, X86::ADD32rr, 2,      // AL*BH + AH*BL + (AL*BL >> 32)
2543               DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
2544     }
2545     return;
2546   }
2547
2548   // General 64x64 multiply
2549
2550   unsigned Op1Reg  = getReg(Op1, &BB, IP);
2551   // Multiply the two low parts... capturing carry into EDX
2552   BuildMI(BB, IP, X86::MOV32rr, 1, X86::EAX).addReg(Op0Reg);
2553   BuildMI(BB, IP, X86::MUL32r, 1).addReg(Op1Reg);  // AL*BL
2554
2555   unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
2556   BuildMI(BB, IP, X86::MOV32rr, 1, DestReg).addReg(X86::EAX);     // AL*BL
2557   BuildMI(BB, IP, X86::MOV32rr, 1,
2558           OverflowReg).addReg(X86::EDX); // AL*BL >> 32
2559
2560   unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
2561   BuildMI(BB, IP, X86::IMUL32rr, 2,
2562           AHBLReg).addReg(Op0Reg+1).addReg(Op1Reg);
2563
2564   unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
2565   BuildMI(BB, IP, X86::ADD32rr, 2,                // AH*BL+(AL*BL >> 32)
2566           AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
2567
2568   unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
2569   BuildMI(BB, IP, X86::IMUL32rr, 2,
2570           ALBHReg).addReg(Op0Reg).addReg(Op1Reg+1);
2571
2572   BuildMI(BB, IP, X86::ADD32rr, 2,      // AL*BH + AH*BL + (AL*BL >> 32)
2573           DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
2574 }
2575
2576
2577 /// visitDivRem - Handle division and remainder instructions... these
2578 /// instruction both require the same instructions to be generated, they just
2579 /// select the result from a different register.  Note that both of these
2580 /// instructions work differently for signed and unsigned operands.
2581 ///
2582 void X86ISel::visitDivRem(BinaryOperator &I) {
2583   unsigned ResultReg = getReg(I);
2584   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2585
2586   // Fold loads into floating point divides.
2587   if (getClass(Op0->getType()) == cFP) {
2588     if (LoadInst *LI = dyn_cast<LoadInst>(Op1))
2589       if (isSafeToFoldLoadIntoInstruction(*LI, I)) {
2590         const Type *Ty = Op0->getType();
2591         assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2592         unsigned Opcode = Ty == Type::FloatTy ? X86::FDIV32m : X86::FDIV64m;
2593
2594         unsigned Op0r = getReg(Op0);
2595         if (AllocaInst *AI = dyn_castFixedAlloca(LI->getOperand(0))) {
2596           unsigned FI = getFixedSizedAllocaFI(AI);
2597           addFrameReference(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op0r), FI);
2598         } else {
2599           X86AddressMode AM;
2600           getAddressingMode(LI->getOperand(0), AM);
2601
2602           addFullAddress(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op0r), AM);
2603         }
2604         return;
2605       }
2606
2607     if (LoadInst *LI = dyn_cast<LoadInst>(Op0))
2608       if (isSafeToFoldLoadIntoInstruction(*LI, I)) {
2609         const Type *Ty = Op0->getType();
2610         assert(Ty == Type::FloatTy||Ty == Type::DoubleTy && "Unknown FP type!");
2611         unsigned Opcode = Ty == Type::FloatTy ? X86::FDIVR32m : X86::FDIVR64m;
2612
2613         unsigned Op1r = getReg(Op1);
2614         if (AllocaInst *AI = dyn_castFixedAlloca(LI->getOperand(0))) {
2615           unsigned FI = getFixedSizedAllocaFI(AI);
2616           addFrameReference(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op1r), FI);
2617         } else {
2618           X86AddressMode AM;
2619           getAddressingMode(LI->getOperand(0), AM);
2620           addFullAddress(BuildMI(BB, Opcode, 5, ResultReg).addReg(Op1r), AM);
2621         }
2622         return;
2623       }
2624   }
2625
2626
2627   MachineBasicBlock::iterator IP = BB->end();
2628   emitDivRemOperation(BB, IP, Op0, Op1,
2629                       I.getOpcode() == Instruction::Div, ResultReg);
2630 }
2631
2632 void X86ISel::emitDivRemOperation(MachineBasicBlock *BB,
2633                                   MachineBasicBlock::iterator IP,
2634                                   Value *Op0, Value *Op1, bool isDiv,
2635                                   unsigned ResultReg) {
2636   const Type *Ty = Op0->getType();
2637   unsigned Class = getClass(Ty);
2638   switch (Class) {
2639   case cFP:              // Floating point divide
2640     if (isDiv) {
2641       emitBinaryFPOperation(BB, IP, Op0, Op1, 3, ResultReg);
2642       return;
2643     } else {               // Floating point remainder...
2644       unsigned Op0Reg = getReg(Op0, BB, IP);
2645       unsigned Op1Reg = getReg(Op1, BB, IP);
2646       MachineInstr *TheCall =
2647         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
2648       std::vector<ValueRecord> Args;
2649       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
2650       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
2651       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
2652     }
2653     return;
2654   case cLong: {
2655     static const char *FnName[] =
2656       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
2657     unsigned Op0Reg = getReg(Op0, BB, IP);
2658     unsigned Op1Reg = getReg(Op1, BB, IP);
2659     unsigned NameIdx = Ty->isUnsigned()*2 + isDiv;
2660     MachineInstr *TheCall =
2661       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
2662
2663     std::vector<ValueRecord> Args;
2664     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
2665     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
2666     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
2667     return;
2668   }
2669   case cByte: case cShort: case cInt:
2670     break;          // Small integrals, handled below...
2671   default: assert(0 && "Unknown class!");
2672   }
2673
2674   static const unsigned MovOpcode[]={ X86::MOV8rr, X86::MOV16rr, X86::MOV32rr };
2675   static const unsigned NEGOpcode[] = { X86::NEG8r, X86::NEG16r, X86::NEG32r };
2676   static const unsigned SAROpcode[]={ X86::SAR8ri, X86::SAR16ri, X86::SAR32ri };
2677   static const unsigned SHROpcode[]={ X86::SHR8ri, X86::SHR16ri, X86::SHR32ri };
2678   static const unsigned ADDOpcode[]={ X86::ADD8rr, X86::ADD16rr, X86::ADD32rr };
2679
2680   // Special case signed division by power of 2.
2681   if (isDiv)
2682     if (ConstantSInt *CI = dyn_cast<ConstantSInt>(Op1)) {
2683       assert(Class != cLong && "This doesn't handle 64-bit divides!");
2684       int V = CI->getValue();
2685
2686       if (V == 1) {       // X /s 1 => X
2687         unsigned Op0Reg = getReg(Op0, BB, IP);
2688         BuildMI(*BB, IP, MovOpcode[Class], 1, ResultReg).addReg(Op0Reg);
2689         return;
2690       }
2691
2692       if (V == -1) {      // X /s -1 => -X
2693         unsigned Op0Reg = getReg(Op0, BB, IP);
2694         BuildMI(*BB, IP, NEGOpcode[Class], 1, ResultReg).addReg(Op0Reg);
2695         return;
2696       }
2697
2698       bool isNeg = false;
2699       if (V < 0) {         // Not a positive power of 2?
2700         V = -V;
2701         isNeg = true;      // Maybe it's a negative power of 2.
2702       }
2703       if (unsigned Log = ExactLog2(V)) {
2704         --Log;
2705         unsigned Op0Reg = getReg(Op0, BB, IP);
2706         unsigned TmpReg = makeAnotherReg(Op0->getType());
2707         if (Log != 1)
2708           BuildMI(*BB, IP, SAROpcode[Class], 2, TmpReg)
2709             .addReg(Op0Reg).addImm(Log-1);
2710         else
2711           BuildMI(*BB, IP, MovOpcode[Class], 1, TmpReg).addReg(Op0Reg);
2712         unsigned TmpReg2 = makeAnotherReg(Op0->getType());
2713         BuildMI(*BB, IP, SHROpcode[Class], 2, TmpReg2)
2714           .addReg(TmpReg).addImm(32-Log);
2715         unsigned TmpReg3 = makeAnotherReg(Op0->getType());
2716         BuildMI(*BB, IP, ADDOpcode[Class], 2, TmpReg3)
2717           .addReg(Op0Reg).addReg(TmpReg2);
2718
2719         unsigned TmpReg4 = isNeg ? makeAnotherReg(Op0->getType()) : ResultReg;
2720         BuildMI(*BB, IP, SAROpcode[Class], 2, TmpReg4)
2721           .addReg(Op0Reg).addImm(Log);
2722         if (isNeg)
2723           BuildMI(*BB, IP, NEGOpcode[Class], 1, ResultReg).addReg(TmpReg4);
2724         return;
2725       }
2726     }
2727
2728   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
2729   static const unsigned ClrOpcode[]={ X86::MOV8ri, X86::MOV16ri, X86::MOV32ri };
2730   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
2731
2732   static const unsigned DivOpcode[][4] = {
2733     { X86::DIV8r , X86::DIV16r , X86::DIV32r , 0 },  // Unsigned division
2734     { X86::IDIV8r, X86::IDIV16r, X86::IDIV32r, 0 },  // Signed division
2735   };
2736
2737   unsigned Reg    = Regs[Class];
2738   unsigned ExtReg = ExtRegs[Class];
2739
2740   // Put the first operand into one of the A registers...
2741   unsigned Op0Reg = getReg(Op0, BB, IP);
2742   unsigned Op1Reg = getReg(Op1, BB, IP);
2743   BuildMI(*BB, IP, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
2744
2745   if (Ty->isSigned()) {
2746     // Emit a sign extension instruction...
2747     unsigned ShiftResult = makeAnotherReg(Op0->getType());
2748     BuildMI(*BB, IP, SAROpcode[Class], 2,ShiftResult).addReg(Op0Reg).addImm(31);
2749     BuildMI(*BB, IP, MovOpcode[Class], 1, ExtReg).addReg(ShiftResult);
2750
2751     // Emit the appropriate divide or remainder instruction...
2752     BuildMI(*BB, IP, DivOpcode[1][Class], 1).addReg(Op1Reg);
2753   } else {
2754     // If unsigned, emit a zeroing instruction... (reg = 0)
2755     BuildMI(*BB, IP, ClrOpcode[Class], 2, ExtReg).addImm(0);
2756
2757     // Emit the appropriate divide or remainder instruction...
2758     BuildMI(*BB, IP, DivOpcode[0][Class], 1).addReg(Op1Reg);
2759   }
2760
2761   // Figure out which register we want to pick the result out of...
2762   unsigned DestReg = isDiv ? Reg : ExtReg;
2763
2764   // Put the result into the destination register...
2765   BuildMI(*BB, IP, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
2766 }
2767
2768
2769 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
2770 /// for constant immediate shift values, and for constant immediate
2771 /// shift values equal to 1. Even the general case is sort of special,
2772 /// because the shift amount has to be in CL, not just any old register.
2773 ///
2774 void X86ISel::visitShiftInst(ShiftInst &I) {
2775   MachineBasicBlock::iterator IP = BB->end ();
2776   emitShiftOperation (BB, IP, I.getOperand (0), I.getOperand (1),
2777                       I.getOpcode () == Instruction::Shl, I.getType (),
2778                       getReg (I));
2779 }
2780
2781 /// emitShiftOperation - Common code shared between visitShiftInst and
2782 /// constant expression support.
2783 void X86ISel::emitShiftOperation(MachineBasicBlock *MBB,
2784                                  MachineBasicBlock::iterator IP,
2785                                  Value *Op, Value *ShiftAmount,
2786                                  bool isLeftShift, const Type *ResultTy,
2787                                  unsigned DestReg) {
2788   unsigned SrcReg = getReg (Op, MBB, IP);
2789   bool isSigned = ResultTy->isSigned ();
2790   unsigned Class = getClass (ResultTy);
2791
2792   static const unsigned ConstantOperand[][4] = {
2793     { X86::SHR8ri, X86::SHR16ri, X86::SHR32ri, X86::SHRD32rri8 },  // SHR
2794     { X86::SAR8ri, X86::SAR16ri, X86::SAR32ri, X86::SHRD32rri8 },  // SAR
2795     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SHL
2796     { X86::SHL8ri, X86::SHL16ri, X86::SHL32ri, X86::SHLD32rri8 },  // SAL = SHL
2797   };
2798
2799   static const unsigned NonConstantOperand[][4] = {
2800     { X86::SHR8rCL, X86::SHR16rCL, X86::SHR32rCL },  // SHR
2801     { X86::SAR8rCL, X86::SAR16rCL, X86::SAR32rCL },  // SAR
2802     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SHL
2803     { X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL },  // SAL = SHL
2804   };
2805
2806   // Longs, as usual, are handled specially...
2807   if (Class == cLong) {
2808     // If we have a constant shift, we can generate much more efficient code
2809     // than otherwise...
2810     //
2811     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
2812       unsigned Amount = CUI->getValue();
2813       if (Amount < 32) {
2814         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
2815         if (isLeftShift) {
2816           BuildMI(*MBB, IP, Opc[3], 3,
2817               DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addImm(Amount);
2818           BuildMI(*MBB, IP, Opc[2], 2, DestReg).addReg(SrcReg).addImm(Amount);
2819         } else {
2820           BuildMI(*MBB, IP, Opc[3], 3,
2821               DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addImm(Amount);
2822           BuildMI(*MBB, IP, Opc[2],2,DestReg+1).addReg(SrcReg+1).addImm(Amount);
2823         }
2824       } else {                 // Shifting more than 32 bits
2825         Amount -= 32;
2826         if (isLeftShift) {
2827           if (Amount != 0) {
2828             BuildMI(*MBB, IP, X86::SHL32ri, 2,
2829                     DestReg + 1).addReg(SrcReg).addImm(Amount);
2830           } else {
2831             BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg+1).addReg(SrcReg);
2832           }
2833           BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg).addImm(0);
2834         } else {
2835           if (Amount != 0) {
2836             BuildMI(*MBB, IP, isSigned ? X86::SAR32ri : X86::SHR32ri, 2,
2837                     DestReg).addReg(SrcReg+1).addImm(Amount);
2838           } else {
2839             BuildMI(*MBB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg+1);
2840           }
2841           BuildMI(*MBB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
2842         }
2843       }
2844     } else {
2845       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2846
2847       if (!isLeftShift && isSigned) {
2848         // If this is a SHR of a Long, then we need to do funny sign extension
2849         // stuff.  TmpReg gets the value to use as the high-part if we are
2850         // shifting more than 32 bits.
2851         BuildMI(*MBB, IP, X86::SAR32ri, 2, TmpReg).addReg(SrcReg).addImm(31);
2852       } else {
2853         // Other shifts use a fixed zero value if the shift is more than 32
2854         // bits.
2855         BuildMI(*MBB, IP, X86::MOV32ri, 1, TmpReg).addImm(0);
2856       }
2857
2858       // Initialize CL with the shift amount...
2859       unsigned ShiftAmountReg = getReg(ShiftAmount, MBB, IP);
2860       BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
2861
2862       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
2863       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
2864       if (isLeftShift) {
2865         // TmpReg2 = shld inHi, inLo
2866         BuildMI(*MBB, IP, X86::SHLD32rrCL,2,TmpReg2).addReg(SrcReg+1)
2867                                                     .addReg(SrcReg);
2868         // TmpReg3 = shl  inLo, CL
2869         BuildMI(*MBB, IP, X86::SHL32rCL, 1, TmpReg3).addReg(SrcReg);
2870
2871         // Set the flags to indicate whether the shift was by more than 32 bits.
2872         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
2873
2874         // DestHi = (>32) ? TmpReg3 : TmpReg2;
2875         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2876                 DestReg+1).addReg(TmpReg2).addReg(TmpReg3);
2877         // DestLo = (>32) ? TmpReg : TmpReg3;
2878         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2879             DestReg).addReg(TmpReg3).addReg(TmpReg);
2880       } else {
2881         // TmpReg2 = shrd inLo, inHi
2882         BuildMI(*MBB, IP, X86::SHRD32rrCL,2,TmpReg2).addReg(SrcReg)
2883                                                     .addReg(SrcReg+1);
2884         // TmpReg3 = s[ah]r  inHi, CL
2885         BuildMI(*MBB, IP, isSigned ? X86::SAR32rCL : X86::SHR32rCL, 1, TmpReg3)
2886                        .addReg(SrcReg+1);
2887
2888         // Set the flags to indicate whether the shift was by more than 32 bits.
2889         BuildMI(*MBB, IP, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
2890
2891         // DestLo = (>32) ? TmpReg3 : TmpReg2;
2892         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2893                 DestReg).addReg(TmpReg2).addReg(TmpReg3);
2894
2895         // DestHi = (>32) ? TmpReg : TmpReg3;
2896         BuildMI(*MBB, IP, X86::CMOVNE32rr, 2,
2897                 DestReg+1).addReg(TmpReg3).addReg(TmpReg);
2898       }
2899     }
2900     return;
2901   }
2902
2903   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
2904     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
2905     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
2906
2907     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
2908     BuildMI(*MBB, IP, Opc[Class], 2,
2909         DestReg).addReg(SrcReg).addImm(CUI->getValue());
2910   } else {                  // The shift amount is non-constant.
2911     unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
2912     BuildMI(*MBB, IP, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
2913
2914     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
2915     BuildMI(*MBB, IP, Opc[Class], 1, DestReg).addReg(SrcReg);
2916   }
2917 }
2918
2919
2920 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
2921 /// instruction.  The load and store instructions are the only place where we
2922 /// need to worry about the memory layout of the target machine.
2923 ///
2924 void X86ISel::visitLoadInst(LoadInst &I) {
2925   // Check to see if this load instruction is going to be folded into a binary
2926   // instruction, like add.  If so, we don't want to emit it.  Wouldn't a real
2927   // pattern matching instruction selector be nice?
2928   unsigned Class = getClassB(I.getType());
2929   if (I.hasOneUse()) {
2930     Instruction *User = cast<Instruction>(I.use_back());
2931     switch (User->getOpcode()) {
2932     case Instruction::Cast:
2933       // If this is a cast from a signed-integer type to a floating point type,
2934       // fold the cast here.
2935       if (getClassB(User->getType()) == cFP &&
2936           (I.getType() == Type::ShortTy || I.getType() == Type::IntTy ||
2937            I.getType() == Type::LongTy)) {
2938         unsigned DestReg = getReg(User);
2939         static const unsigned Opcode[] = {
2940           0/*BYTE*/, X86::FILD16m, X86::FILD32m, 0/*FP*/, X86::FILD64m
2941         };
2942
2943         if (AllocaInst *AI = dyn_castFixedAlloca(I.getOperand(0))) {
2944           unsigned FI = getFixedSizedAllocaFI(AI);
2945           addFrameReference(BuildMI(BB, Opcode[Class], 4, DestReg), FI);
2946         } else {
2947           X86AddressMode AM;
2948           getAddressingMode(I.getOperand(0), AM);
2949           addFullAddress(BuildMI(BB, Opcode[Class], 4, DestReg), AM);
2950         }
2951         return;
2952       } else {
2953         User = 0;
2954       }
2955       break;
2956
2957     case Instruction::Add:
2958     case Instruction::Sub:
2959     case Instruction::And:
2960     case Instruction::Or:
2961     case Instruction::Xor:
2962       if (Class == cLong) User = 0;
2963       break;
2964     case Instruction::Mul:
2965     case Instruction::Div:
2966       if (Class != cFP) User = 0;
2967       break;  // Folding only implemented for floating point.
2968     default: User = 0; break;
2969     }
2970
2971     if (User) {
2972       // Okay, we found a user.  If the load is the first operand and there is
2973       // no second operand load, reverse the operand ordering.  Note that this
2974       // can fail for a subtract (ie, no change will be made).
2975       bool Swapped = false;
2976       if (!isa<LoadInst>(User->getOperand(1)))
2977         Swapped = !cast<BinaryOperator>(User)->swapOperands();
2978
2979       // Okay, now that everything is set up, if this load is used by the second
2980       // operand, and if there are no instructions that invalidate the load
2981       // before the binary operator, eliminate the load.
2982       if (User->getOperand(1) == &I &&
2983           isSafeToFoldLoadIntoInstruction(I, *User))
2984         return;   // Eliminate the load!
2985
2986       // If this is a floating point sub or div, we won't be able to swap the
2987       // operands, but we will still be able to eliminate the load.
2988       if (Class == cFP && User->getOperand(0) == &I &&
2989           !isa<LoadInst>(User->getOperand(1)) &&
2990           (User->getOpcode() == Instruction::Sub ||
2991            User->getOpcode() == Instruction::Div) &&
2992           isSafeToFoldLoadIntoInstruction(I, *User))
2993         return;  // Eliminate the load!
2994
2995       // If we swapped the operands to the instruction, but couldn't fold the
2996       // load anyway, swap them back.  We don't want to break add X, int
2997       // folding.
2998       if (Swapped) cast<BinaryOperator>(User)->swapOperands();
2999     }
3000   }
3001
3002   static const unsigned Opcodes[] = {
3003     X86::MOV8rm, X86::MOV16rm, X86::MOV32rm, X86::FLD32m, X86::MOV32rm
3004   };
3005   unsigned Opcode = Opcodes[Class];
3006   if (I.getType() == Type::DoubleTy) Opcode = X86::FLD64m;
3007
3008   unsigned DestReg = getReg(I);
3009
3010   if (AllocaInst *AI = dyn_castFixedAlloca(I.getOperand(0))) {
3011     unsigned FI = getFixedSizedAllocaFI(AI);
3012     if (Class == cLong) {
3013       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, DestReg), FI);
3014       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), FI, 4);
3015     } else {
3016       addFrameReference(BuildMI(BB, Opcode, 4, DestReg), FI);
3017     }
3018   } else {
3019     X86AddressMode AM;
3020     getAddressingMode(I.getOperand(0), AM);
3021
3022     if (Class == cLong) {
3023       addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg), AM);
3024       AM.Disp += 4;
3025       addFullAddress(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), AM);
3026     } else {
3027       addFullAddress(BuildMI(BB, Opcode, 4, DestReg), AM);
3028     }
3029   }
3030 }
3031
3032 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
3033 /// instruction.
3034 ///
3035 void X86ISel::visitStoreInst(StoreInst &I) {
3036   X86AddressMode AM;
3037   getAddressingMode(I.getOperand(1), AM);
3038
3039   const Type *ValTy = I.getOperand(0)->getType();
3040   unsigned Class = getClassB(ValTy);
3041
3042   if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(0))) {
3043     uint64_t Val = CI->getRawValue();
3044     if (Class == cLong) {
3045       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(Val & ~0U);
3046       AM.Disp += 4;
3047       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(Val>>32);
3048     } else {
3049       static const unsigned Opcodes[] = {
3050         X86::MOV8mi, X86::MOV16mi, X86::MOV32mi
3051       };
3052       unsigned Opcode = Opcodes[Class];
3053       addFullAddress(BuildMI(BB, Opcode, 5), AM).addImm(Val);
3054     }
3055   } else if (isa<ConstantPointerNull>(I.getOperand(0))) {
3056      addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(0);
3057   } else if (ConstantBool *CB = dyn_cast<ConstantBool>(I.getOperand(0))) {
3058     addFullAddress(BuildMI(BB, X86::MOV8mi, 5), AM).addImm(CB->getValue());
3059   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) {
3060     // Store constant FP values with integer instructions to avoid having to
3061     // load the constants from the constant pool then do a store.
3062     if (CFP->getType() == Type::FloatTy) {
3063       union {
3064         unsigned I;
3065         float    F;
3066       } V;
3067       V.F = CFP->getValue();
3068       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(V.I);
3069     } else {
3070       union {
3071         uint64_t I;
3072         double   F;
3073       } V;
3074       V.F = CFP->getValue();
3075       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm((unsigned)V.I);
3076       AM.Disp += 4;
3077       addFullAddress(BuildMI(BB, X86::MOV32mi, 5), AM).addImm(
3078                                                           unsigned(V.I >> 32));
3079     }
3080
3081   } else if (Class == cLong) {
3082     unsigned ValReg = getReg(I.getOperand(0));
3083     addFullAddress(BuildMI(BB, X86::MOV32mr, 5), AM).addReg(ValReg);
3084     AM.Disp += 4;
3085     addFullAddress(BuildMI(BB, X86::MOV32mr, 5), AM).addReg(ValReg+1);
3086   } else {
3087     unsigned ValReg = getReg(I.getOperand(0));
3088     static const unsigned Opcodes[] = {
3089       X86::MOV8mr, X86::MOV16mr, X86::MOV32mr, X86::FST32m
3090     };
3091     unsigned Opcode = Opcodes[Class];
3092     if (ValTy == Type::DoubleTy) Opcode = X86::FST64m;
3093
3094     addFullAddress(BuildMI(BB, Opcode, 1+4), AM).addReg(ValReg);
3095   }
3096 }
3097
3098
3099 /// visitCastInst - Here we have various kinds of copying with or without sign
3100 /// extension going on.
3101 ///
3102 void X86ISel::visitCastInst(CastInst &CI) {
3103   Value *Op = CI.getOperand(0);
3104
3105   unsigned SrcClass = getClassB(Op->getType());
3106   unsigned DestClass = getClassB(CI.getType());
3107   // Noop casts are not emitted: getReg will return the source operand as the
3108   // register to use for any uses of the noop cast.
3109   if (DestClass == SrcClass) {
3110     // The only detail in this plan is that casts from double -> float are
3111     // truncating operations that we have to codegen through memory (despite
3112     // the fact that the source/dest registers are the same class).
3113     if (CI.getType() != Type::FloatTy || Op->getType() != Type::DoubleTy)
3114       return;
3115   }
3116
3117   // If this is a cast from a 32-bit integer to a Long type, and the only uses
3118   // of the case are GEP instructions, then the cast does not need to be
3119   // generated explicitly, it will be folded into the GEP.
3120   if (DestClass == cLong && SrcClass == cInt) {
3121     bool AllUsesAreGEPs = true;
3122     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
3123       if (!isa<GetElementPtrInst>(*I)) {
3124         AllUsesAreGEPs = false;
3125         break;
3126       }
3127
3128     // No need to codegen this cast if all users are getelementptr instrs...
3129     if (AllUsesAreGEPs) return;
3130   }
3131
3132   // If this cast converts a load from a short,int, or long integer to a FP
3133   // value, we will have folded this cast away.
3134   if (DestClass == cFP && isa<LoadInst>(Op) && Op->hasOneUse() &&
3135       (Op->getType() == Type::ShortTy || Op->getType() == Type::IntTy ||
3136        Op->getType() == Type::LongTy))
3137     return;
3138
3139
3140   unsigned DestReg = getReg(CI);
3141   MachineBasicBlock::iterator MI = BB->end();
3142   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
3143 }
3144
3145 /// emitCastOperation - Common code shared between visitCastInst and constant
3146 /// expression cast support.
3147 ///
3148 void X86ISel::emitCastOperation(MachineBasicBlock *BB,
3149                                 MachineBasicBlock::iterator IP,
3150                                 Value *Src, const Type *DestTy,
3151                                 unsigned DestReg) {
3152   const Type *SrcTy = Src->getType();
3153   unsigned SrcClass = getClassB(SrcTy);
3154   unsigned DestClass = getClassB(DestTy);
3155   unsigned SrcReg = getReg(Src, BB, IP);
3156
3157   // Implement casts to bool by using compare on the operand followed by set if
3158   // not zero on the result.
3159   if (DestTy == Type::BoolTy) {
3160     switch (SrcClass) {
3161     case cByte:
3162       BuildMI(*BB, IP, X86::TEST8rr, 2).addReg(SrcReg).addReg(SrcReg);
3163       break;
3164     case cShort:
3165       BuildMI(*BB, IP, X86::TEST16rr, 2).addReg(SrcReg).addReg(SrcReg);
3166       break;
3167     case cInt:
3168       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg).addReg(SrcReg);
3169       break;
3170     case cLong: {
3171       unsigned TmpReg = makeAnotherReg(Type::IntTy);
3172       BuildMI(*BB, IP, X86::OR32rr, 2, TmpReg).addReg(SrcReg).addReg(SrcReg+1);
3173       break;
3174     }
3175     case cFP:
3176       BuildMI(*BB, IP, X86::FTST, 1).addReg(SrcReg);
3177       BuildMI(*BB, IP, X86::FNSTSW8r, 0);
3178       BuildMI(*BB, IP, X86::SAHF, 1);
3179       break;
3180     }
3181
3182     // If the zero flag is not set, then the value is true, set the byte to
3183     // true.
3184     BuildMI(*BB, IP, X86::SETNEr, 1, DestReg);
3185     return;
3186   }
3187
3188   static const unsigned RegRegMove[] = {
3189     X86::MOV8rr, X86::MOV16rr, X86::MOV32rr, X86::FpMOV, X86::MOV32rr
3190   };
3191
3192   // Implement casts between values of the same type class (as determined by
3193   // getClass) by using a register-to-register move.
3194   if (SrcClass == DestClass) {
3195     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
3196       BuildMI(*BB, IP, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
3197     } else if (SrcClass == cFP) {
3198       if (SrcTy == Type::FloatTy) {  // double -> float
3199         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
3200         BuildMI(*BB, IP, X86::FpMOV, 1, DestReg).addReg(SrcReg);
3201       } else {                       // float -> double
3202         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
3203                "Unknown cFP member!");
3204         // Truncate from double to float by storing to memory as short, then
3205         // reading it back.
3206         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
3207         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
3208         addFrameReference(BuildMI(*BB, IP, X86::FST32m, 5), FrameIdx).addReg(SrcReg);
3209         addFrameReference(BuildMI(*BB, IP, X86::FLD32m, 5, DestReg), FrameIdx);
3210       }
3211     } else if (SrcClass == cLong) {
3212       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
3213       BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg+1).addReg(SrcReg+1);
3214     } else {
3215       assert(0 && "Cannot handle this type of cast instruction!");
3216       abort();
3217     }
3218     return;
3219   }
3220
3221   // Handle cast of SMALLER int to LARGER int using a move with sign extension
3222   // or zero extension, depending on whether the source type was signed.
3223   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
3224       SrcClass < DestClass) {
3225     bool isLong = DestClass == cLong;
3226     if (isLong) DestClass = cInt;
3227
3228     static const unsigned Opc[][4] = {
3229       { X86::MOVSX16rr8, X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOV32rr }, // s
3230       { X86::MOVZX16rr8, X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOV32rr }  // u
3231     };
3232
3233     bool isUnsigned = SrcTy->isUnsigned() || SrcTy == Type::BoolTy;
3234     BuildMI(*BB, IP, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
3235         DestReg).addReg(SrcReg);
3236
3237     if (isLong) {  // Handle upper 32 bits as appropriate...
3238       if (isUnsigned)     // Zero out top bits...
3239         BuildMI(*BB, IP, X86::MOV32ri, 1, DestReg+1).addImm(0);
3240       else                // Sign extend bottom half...
3241         BuildMI(*BB, IP, X86::SAR32ri, 2, DestReg+1).addReg(DestReg).addImm(31);
3242     }
3243     return;
3244   }
3245
3246   // Special case long -> int ...
3247   if (SrcClass == cLong && DestClass == cInt) {
3248     BuildMI(*BB, IP, X86::MOV32rr, 1, DestReg).addReg(SrcReg);
3249     return;
3250   }
3251
3252   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
3253   // move out of AX or AL.
3254   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
3255       && SrcClass > DestClass) {
3256     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
3257     BuildMI(*BB, IP, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
3258     BuildMI(*BB, IP, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
3259     return;
3260   }
3261
3262   // Handle casts from integer to floating point now...
3263   if (DestClass == cFP) {
3264     // Promote the integer to a type supported by FLD.  We do this because there
3265     // are no unsigned FLD instructions, so we must promote an unsigned value to
3266     // a larger signed value, then use FLD on the larger value.
3267     //
3268     const Type *PromoteType = 0;
3269     unsigned PromoteOpcode = 0;
3270     unsigned RealDestReg = DestReg;
3271     switch (SrcTy->getTypeID()) {
3272     case Type::BoolTyID:
3273     case Type::SByteTyID:
3274       // We don't have the facilities for directly loading byte sized data from
3275       // memory (even signed).  Promote it to 16 bits.
3276       PromoteType = Type::ShortTy;
3277       PromoteOpcode = X86::MOVSX16rr8;
3278       break;
3279     case Type::UByteTyID:
3280       PromoteType = Type::ShortTy;
3281       PromoteOpcode = X86::MOVZX16rr8;
3282       break;
3283     case Type::UShortTyID:
3284       PromoteType = Type::IntTy;
3285       PromoteOpcode = X86::MOVZX32rr16;
3286       break;
3287     case Type::UIntTyID: {
3288       // Make a 64 bit temporary... and zero out the top of it...
3289       unsigned TmpReg = makeAnotherReg(Type::LongTy);
3290       BuildMI(*BB, IP, X86::MOV32rr, 1, TmpReg).addReg(SrcReg);
3291       BuildMI(*BB, IP, X86::MOV32ri, 1, TmpReg+1).addImm(0);
3292       SrcTy = Type::LongTy;
3293       SrcClass = cLong;
3294       SrcReg = TmpReg;
3295       break;
3296     }
3297     case Type::ULongTyID:
3298       // Don't fild into the read destination.
3299       DestReg = makeAnotherReg(Type::DoubleTy);
3300       break;
3301     default:  // No promotion needed...
3302       break;
3303     }
3304
3305     if (PromoteType) {
3306       unsigned TmpReg = makeAnotherReg(PromoteType);
3307       BuildMI(*BB, IP, PromoteOpcode, 1, TmpReg).addReg(SrcReg);
3308       SrcTy = PromoteType;
3309       SrcClass = getClass(PromoteType);
3310       SrcReg = TmpReg;
3311     }
3312
3313     // Spill the integer to memory and reload it from there...
3314     int FrameIdx =
3315       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
3316
3317     if (SrcClass == cLong) {
3318       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
3319                         FrameIdx).addReg(SrcReg);
3320       addFrameReference(BuildMI(*BB, IP, X86::MOV32mr, 5),
3321                         FrameIdx, 4).addReg(SrcReg+1);
3322     } else {
3323       static const unsigned Op1[] = { X86::MOV8mr, X86::MOV16mr, X86::MOV32mr };
3324       addFrameReference(BuildMI(*BB, IP, Op1[SrcClass], 5),
3325                         FrameIdx).addReg(SrcReg);
3326     }
3327
3328     static const unsigned Op2[] =
3329       { 0/*byte*/, X86::FILD16m, X86::FILD32m, 0/*FP*/, X86::FILD64m };
3330     addFrameReference(BuildMI(*BB, IP, Op2[SrcClass], 5, DestReg), FrameIdx);
3331
3332     // We need special handling for unsigned 64-bit integer sources.  If the
3333     // input number has the "sign bit" set, then we loaded it incorrectly as a
3334     // negative 64-bit number.  In this case, add an offset value.
3335     if (SrcTy == Type::ULongTy) {
3336       // Emit a test instruction to see if the dynamic input value was signed.
3337       BuildMI(*BB, IP, X86::TEST32rr, 2).addReg(SrcReg+1).addReg(SrcReg+1);
3338
3339       // If the sign bit is set, get a pointer to an offset, otherwise get a
3340       // pointer to a zero.
3341       MachineConstantPool *CP = F->getConstantPool();
3342       unsigned Zero = makeAnotherReg(Type::IntTy);
3343       Constant *Null = Constant::getNullValue(Type::UIntTy);
3344       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Zero),
3345                                CP->getConstantPoolIndex(Null));
3346       unsigned Offset = makeAnotherReg(Type::IntTy);
3347       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
3348
3349       addConstantPoolReference(BuildMI(*BB, IP, X86::LEA32r, 5, Offset),
3350                                CP->getConstantPoolIndex(OffsetCst));
3351       unsigned Addr = makeAnotherReg(Type::IntTy);
3352       BuildMI(*BB, IP, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
3353
3354       // Load the constant for an add.  FIXME: this could make an 'fadd' that
3355       // reads directly from memory, but we don't support these yet.
3356       unsigned ConstReg = makeAnotherReg(Type::DoubleTy);
3357       addDirectMem(BuildMI(*BB, IP, X86::FLD32m, 4, ConstReg), Addr);
3358
3359       BuildMI(*BB, IP, X86::FpADD, 2, RealDestReg)
3360                 .addReg(ConstReg).addReg(DestReg);
3361     }
3362
3363     return;
3364   }
3365
3366   // Handle casts from floating point to integer now...
3367   if (SrcClass == cFP) {
3368     // Change the floating point control register to use "round towards zero"
3369     // mode when truncating to an integer value.
3370     //
3371     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
3372     addFrameReference(BuildMI(*BB, IP, X86::FNSTCW16m, 4), CWFrameIdx);
3373
3374     // Load the old value of the high byte of the control word...
3375     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
3376     addFrameReference(BuildMI(*BB, IP, X86::MOV8rm, 4, HighPartOfCW),
3377                       CWFrameIdx, 1);
3378
3379     // Set the high part to be round to zero...
3380     addFrameReference(BuildMI(*BB, IP, X86::MOV8mi, 5),
3381                       CWFrameIdx, 1).addImm(12);
3382
3383     // Reload the modified control word now...
3384     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
3385
3386     // Restore the memory image of control word to original value
3387     addFrameReference(BuildMI(*BB, IP, X86::MOV8mr, 5),
3388                       CWFrameIdx, 1).addReg(HighPartOfCW);
3389
3390     // We don't have the facilities for directly storing byte sized data to
3391     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
3392     // larger classes because we only have signed FP stores.
3393     unsigned StoreClass  = DestClass;
3394     const Type *StoreTy  = DestTy;
3395     if (StoreClass == cByte || DestTy->isUnsigned())
3396       switch (StoreClass) {
3397       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
3398       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
3399       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
3400       // The following treatment of cLong may not be perfectly right,
3401       // but it survives chains of casts of the form
3402       // double->ulong->double.
3403       case cLong:  StoreTy = Type::LongTy;  StoreClass = cLong;  break;
3404       default: assert(0 && "Unknown store class!");
3405       }
3406
3407     // Spill the integer to memory and reload it from there...
3408     int FrameIdx =
3409       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
3410
3411     static const unsigned Op1[] =
3412       { 0, X86::FIST16m, X86::FIST32m, 0, X86::FISTP64m };
3413     addFrameReference(BuildMI(*BB, IP, Op1[StoreClass], 5),
3414                       FrameIdx).addReg(SrcReg);
3415
3416     if (DestClass == cLong) {
3417       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg), FrameIdx);
3418       addFrameReference(BuildMI(*BB, IP, X86::MOV32rm, 4, DestReg+1),
3419                         FrameIdx, 4);
3420     } else {
3421       static const unsigned Op2[] = { X86::MOV8rm, X86::MOV16rm, X86::MOV32rm };
3422       addFrameReference(BuildMI(*BB, IP, Op2[DestClass], 4, DestReg), FrameIdx);
3423     }
3424
3425     // Reload the original control word now...
3426     addFrameReference(BuildMI(*BB, IP, X86::FLDCW16m, 4), CWFrameIdx);
3427     return;
3428   }
3429
3430   // Anything we haven't handled already, we can't (yet) handle at all.
3431   assert(0 && "Unhandled cast instruction!");
3432   abort();
3433 }
3434
3435 /// visitVANextInst - Implement the va_next instruction...
3436 ///
3437 void X86ISel::visitVANextInst(VANextInst &I) {
3438   unsigned VAList = getReg(I.getOperand(0));
3439   unsigned DestReg = getReg(I);
3440
3441   unsigned Size;
3442   switch (I.getArgType()->getTypeID()) {
3443   default:
3444     std::cerr << I;
3445     assert(0 && "Error: bad type for va_next instruction!");
3446     return;
3447   case Type::PointerTyID:
3448   case Type::UIntTyID:
3449   case Type::IntTyID:
3450     Size = 4;
3451     break;
3452   case Type::ULongTyID:
3453   case Type::LongTyID:
3454   case Type::DoubleTyID:
3455     Size = 8;
3456     break;
3457   }
3458
3459   // Increment the VAList pointer...
3460   BuildMI(BB, X86::ADD32ri, 2, DestReg).addReg(VAList).addImm(Size);
3461 }
3462
3463 void X86ISel::visitVAArgInst(VAArgInst &I) {
3464   unsigned VAList = getReg(I.getOperand(0));
3465   unsigned DestReg = getReg(I);
3466
3467   switch (I.getType()->getTypeID()) {
3468   default:
3469     std::cerr << I;
3470     assert(0 && "Error: bad type for va_next instruction!");
3471     return;
3472   case Type::PointerTyID:
3473   case Type::UIntTyID:
3474   case Type::IntTyID:
3475     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
3476     break;
3477   case Type::ULongTyID:
3478   case Type::LongTyID:
3479     addDirectMem(BuildMI(BB, X86::MOV32rm, 4, DestReg), VAList);
3480     addRegOffset(BuildMI(BB, X86::MOV32rm, 4, DestReg+1), VAList, 4);
3481     break;
3482   case Type::DoubleTyID:
3483     addDirectMem(BuildMI(BB, X86::FLD64m, 4, DestReg), VAList);
3484     break;
3485   }
3486 }
3487
3488 /// visitGetElementPtrInst - instruction-select GEP instructions
3489 ///
3490 void X86ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
3491   // If this GEP instruction will be folded into all of its users, we don't need
3492   // to explicitly calculate it!
3493   X86AddressMode AM;
3494   if (isGEPFoldable(0, I.getOperand(0), I.op_begin()+1, I.op_end(), AM)) {
3495     // Check all of the users of the instruction to see if they are loads and
3496     // stores.
3497     bool AllWillFold = true;
3498     for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI)
3499       if (cast<Instruction>(*UI)->getOpcode() != Instruction::Load)
3500         if (cast<Instruction>(*UI)->getOpcode() != Instruction::Store ||
3501             cast<Instruction>(*UI)->getOperand(0) == &I) {
3502           AllWillFold = false;
3503           break;
3504         }
3505
3506     // If the instruction is foldable, and will be folded into all users, don't
3507     // emit it!
3508     if (AllWillFold) return;
3509   }
3510
3511   unsigned outputReg = getReg(I);
3512   emitGEPOperation(BB, BB->end(), I.getOperand(0),
3513                    I.op_begin()+1, I.op_end(), outputReg);
3514 }
3515
3516 /// getGEPIndex - Inspect the getelementptr operands specified with GEPOps and
3517 /// GEPTypes (the derived types being stepped through at each level).  On return
3518 /// from this function, if some indexes of the instruction are representable as
3519 /// an X86 lea instruction, the machine operands are put into the Ops
3520 /// instruction and the consumed indexes are poped from the GEPOps/GEPTypes
3521 /// lists.  Otherwise, GEPOps.size() is returned.  If this returns a an
3522 /// addressing mode that only partially consumes the input, the BaseReg input of
3523 /// the addressing mode must be left free.
3524 ///
3525 /// Note that there is one fewer entry in GEPTypes than there is in GEPOps.
3526 ///
3527 void X86ISel::getGEPIndex(MachineBasicBlock *MBB,
3528                           MachineBasicBlock::iterator IP,
3529                           std::vector<Value*> &GEPOps,
3530                           std::vector<const Type*> &GEPTypes,
3531                           X86AddressMode &AM) {
3532   const TargetData &TD = TM.getTargetData();
3533
3534   // Clear out the state we are working with...
3535   AM.BaseType = X86AddressMode::RegBase;
3536   AM.Base.Reg = 0;   // No base register
3537   AM.Scale = 1;      // Unit scale
3538   AM.IndexReg = 0;   // No index register
3539   AM.Disp = 0;       // No displacement
3540
3541   // While there are GEP indexes that can be folded into the current address,
3542   // keep processing them.
3543   while (!GEPTypes.empty()) {
3544     if (const StructType *StTy = dyn_cast<StructType>(GEPTypes.back())) {
3545       // It's a struct access.  CUI is the index into the structure,
3546       // which names the field. This index must have unsigned type.
3547       const ConstantUInt *CUI = cast<ConstantUInt>(GEPOps.back());
3548
3549       // Use the TargetData structure to pick out what the layout of the
3550       // structure is in memory.  Since the structure index must be constant, we
3551       // can get its value and use it to find the right byte offset from the
3552       // StructLayout class's list of structure member offsets.
3553       AM.Disp += TD.getStructLayout(StTy)->MemberOffsets[CUI->getValue()];
3554       GEPOps.pop_back();        // Consume a GEP operand
3555       GEPTypes.pop_back();
3556     } else {
3557       // It's an array or pointer access: [ArraySize x ElementType].
3558       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
3559       Value *idx = GEPOps.back();
3560
3561       // idx is the index into the array.  Unlike with structure
3562       // indices, we may not know its actual value at code-generation
3563       // time.
3564
3565       // If idx is a constant, fold it into the offset.
3566       unsigned TypeSize = TD.getTypeSize(SqTy->getElementType());
3567       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
3568         AM.Disp += TypeSize*CSI->getValue();
3569       } else if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(idx)) {
3570         AM.Disp += TypeSize*CUI->getValue();
3571       } else {
3572         // If the index reg is already taken, we can't handle this index.
3573         if (AM.IndexReg) return;
3574
3575         // If this is a size that we can handle, then add the index as
3576         switch (TypeSize) {
3577         case 1: case 2: case 4: case 8:
3578           // These are all acceptable scales on X86.
3579           AM.Scale = TypeSize;
3580           break;
3581         default:
3582           // Otherwise, we can't handle this scale
3583           return;
3584         }
3585
3586         if (CastInst *CI = dyn_cast<CastInst>(idx))
3587           if (CI->getOperand(0)->getType() == Type::IntTy ||
3588               CI->getOperand(0)->getType() == Type::UIntTy)
3589             idx = CI->getOperand(0);
3590
3591         AM.IndexReg = MBB ? getReg(idx, MBB, IP) : 1;
3592       }
3593
3594       GEPOps.pop_back();        // Consume a GEP operand
3595       GEPTypes.pop_back();
3596     }
3597   }
3598
3599   // GEPTypes is empty, which means we have a single operand left.  Set it as
3600   // the base register.
3601   //
3602   assert(AM.Base.Reg == 0);
3603
3604   if (AllocaInst *AI = dyn_castFixedAlloca(GEPOps.back())) {
3605     AM.BaseType = X86AddressMode::FrameIndexBase;
3606     AM.Base.FrameIndex = getFixedSizedAllocaFI(AI);
3607     GEPOps.pop_back();
3608     return;
3609   }
3610
3611 #if 0   // FIXME: TODO!
3612   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
3613     // FIXME: When addressing modes are more powerful/correct, we could load
3614     // global addresses directly as 32-bit immediates.
3615   }
3616 #endif
3617
3618   AM.Base.Reg = MBB ? getReg(GEPOps[0], MBB, IP) : 1;
3619   GEPOps.pop_back();        // Consume the last GEP operand
3620 }
3621
3622
3623 /// isGEPFoldable - Return true if the specified GEP can be completely
3624 /// folded into the addressing mode of a load/store or lea instruction.
3625 bool X86ISel::isGEPFoldable(MachineBasicBlock *MBB,
3626                             Value *Src, User::op_iterator IdxBegin,
3627                             User::op_iterator IdxEnd, X86AddressMode &AM) {
3628
3629   std::vector<Value*> GEPOps;
3630   GEPOps.resize(IdxEnd-IdxBegin+1);
3631   GEPOps[0] = Src;
3632   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
3633
3634   std::vector<const Type*>
3635     GEPTypes(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
3636              gep_type_end(Src->getType(), IdxBegin, IdxEnd));
3637
3638   MachineBasicBlock::iterator IP;
3639   if (MBB) IP = MBB->end();
3640   getGEPIndex(MBB, IP, GEPOps, GEPTypes, AM);
3641
3642   // We can fold it away iff the getGEPIndex call eliminated all operands.
3643   return GEPOps.empty();
3644 }
3645
3646 void X86ISel::emitGEPOperation(MachineBasicBlock *MBB,
3647                                MachineBasicBlock::iterator IP,
3648                                Value *Src, User::op_iterator IdxBegin,
3649                                User::op_iterator IdxEnd, unsigned TargetReg) {
3650   const TargetData &TD = TM.getTargetData();
3651
3652   // If this is a getelementptr null, with all constant integer indices, just
3653   // replace it with TargetReg = 42.
3654   if (isa<ConstantPointerNull>(Src)) {
3655     User::op_iterator I = IdxBegin;
3656     for (; I != IdxEnd; ++I)
3657       if (!isa<ConstantInt>(*I))
3658         break;
3659     if (I == IdxEnd) {   // All constant indices
3660       unsigned Offset = TD.getIndexedOffset(Src->getType(),
3661                                          std::vector<Value*>(IdxBegin, IdxEnd));
3662       BuildMI(*MBB, IP, X86::MOV32ri, 1, TargetReg).addImm(Offset);
3663       return;
3664     }
3665   }
3666
3667   std::vector<Value*> GEPOps;
3668   GEPOps.resize(IdxEnd-IdxBegin+1);
3669   GEPOps[0] = Src;
3670   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
3671
3672   std::vector<const Type*> GEPTypes;
3673   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
3674                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
3675
3676   // Keep emitting instructions until we consume the entire GEP instruction.
3677   while (!GEPOps.empty()) {
3678     unsigned OldSize = GEPOps.size();
3679     X86AddressMode AM;
3680     getGEPIndex(MBB, IP, GEPOps, GEPTypes, AM);
3681
3682     if (GEPOps.size() != OldSize) {
3683       // getGEPIndex consumed some of the input.  Build an LEA instruction here.
3684       unsigned NextTarget = 0;
3685       if (!GEPOps.empty()) {
3686         assert(AM.Base.Reg == 0 &&
3687            "getGEPIndex should have left the base register open for chaining!");
3688         NextTarget = AM.Base.Reg = makeAnotherReg(Type::UIntTy);
3689       }
3690
3691       if (AM.BaseType == X86AddressMode::RegBase &&
3692               AM.IndexReg == 0 && AM.Disp == 0)
3693         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(AM.Base.Reg);
3694       else
3695         addFullAddress(BuildMI(*MBB, IP, X86::LEA32r, 5, TargetReg), AM);
3696       --IP;
3697       TargetReg = NextTarget;
3698     } else if (GEPTypes.empty()) {
3699       // The getGEPIndex operation didn't want to build an LEA.  Check to see if
3700       // all operands are consumed but the base pointer.  If so, just load it
3701       // into the register.
3702       if (GlobalValue *GV = dyn_cast<GlobalValue>(GEPOps[0])) {
3703         BuildMI(*MBB, IP, X86::MOV32ri, 1, TargetReg).addGlobalAddress(GV);
3704       } else {
3705         unsigned BaseReg = getReg(GEPOps[0], MBB, IP);
3706         BuildMI(*MBB, IP, X86::MOV32rr, 1, TargetReg).addReg(BaseReg);
3707       }
3708       break;                // we are now done
3709
3710     } else {
3711       // It's an array or pointer access: [ArraySize x ElementType].
3712       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
3713       Value *idx = GEPOps.back();
3714       GEPOps.pop_back();        // Consume a GEP operand
3715       GEPTypes.pop_back();
3716
3717       // Many GEP instructions use a [cast (int/uint) to LongTy] as their
3718       // operand on X86.  Handle this case directly now...
3719       if (CastInst *CI = dyn_cast<CastInst>(idx))
3720         if (CI->getOperand(0)->getType() == Type::IntTy ||
3721             CI->getOperand(0)->getType() == Type::UIntTy)
3722           idx = CI->getOperand(0);
3723
3724       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
3725       // must find the size of the pointed-to type (Not coincidentally, the next
3726       // type is the type of the elements in the array).
3727       const Type *ElTy = SqTy->getElementType();
3728       unsigned elementSize = TD.getTypeSize(ElTy);
3729
3730       // If idxReg is a constant, we don't need to perform the multiply!
3731       if (ConstantInt *CSI = dyn_cast<ConstantInt>(idx)) {
3732         if (!CSI->isNullValue()) {
3733           unsigned Offset = elementSize*CSI->getRawValue();
3734           unsigned Reg = makeAnotherReg(Type::UIntTy);
3735           BuildMI(*MBB, IP, X86::ADD32ri, 2, TargetReg)
3736                                 .addReg(Reg).addImm(Offset);
3737           --IP;            // Insert the next instruction before this one.
3738           TargetReg = Reg; // Codegen the rest of the GEP into this
3739         }
3740       } else if (elementSize == 1) {
3741         // If the element size is 1, we don't have to multiply, just add
3742         unsigned idxReg = getReg(idx, MBB, IP);
3743         unsigned Reg = makeAnotherReg(Type::UIntTy);
3744         BuildMI(*MBB, IP, X86::ADD32rr, 2,TargetReg).addReg(Reg).addReg(idxReg);
3745         --IP;            // Insert the next instruction before this one.
3746         TargetReg = Reg; // Codegen the rest of the GEP into this
3747       } else {
3748         unsigned idxReg = getReg(idx, MBB, IP);
3749         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
3750
3751         // Make sure we can back the iterator up to point to the first
3752         // instruction emitted.
3753         MachineBasicBlock::iterator BeforeIt = IP;
3754         if (IP == MBB->begin())
3755           BeforeIt = MBB->end();
3756         else
3757           --BeforeIt;
3758         doMultiplyConst(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSize);
3759
3760         // Emit an ADD to add OffsetReg to the basePtr.
3761         unsigned Reg = makeAnotherReg(Type::UIntTy);
3762         BuildMI(*MBB, IP, X86::ADD32rr, 2, TargetReg)
3763                           .addReg(Reg).addReg(OffsetReg);
3764
3765         // Step to the first instruction of the multiply.
3766         if (BeforeIt == MBB->end())
3767           IP = MBB->begin();
3768         else
3769           IP = ++BeforeIt;
3770
3771         TargetReg = Reg; // Codegen the rest of the GEP into this
3772       }
3773     }
3774   }
3775 }
3776
3777 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
3778 /// frame manager, otherwise do it the hard way.
3779 ///
3780 void X86ISel::visitAllocaInst(AllocaInst &I) {
3781   // If this is a fixed size alloca in the entry block for the function, we
3782   // statically stack allocate the space, so we don't need to do anything here.
3783   //
3784   if (dyn_castFixedAlloca(&I)) return;
3785
3786   // Find the data size of the alloca inst's getAllocatedType.
3787   const Type *Ty = I.getAllocatedType();
3788   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
3789
3790   // Create a register to hold the temporary result of multiplying the type size
3791   // constant by the variable amount.
3792   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
3793   unsigned SrcReg1 = getReg(I.getArraySize());
3794
3795   // TotalSizeReg = mul <numelements>, <TypeSize>
3796   MachineBasicBlock::iterator MBBI = BB->end();
3797   doMultiplyConst(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, TySize);
3798
3799   // AddedSize = add <TotalSizeReg>, 15
3800   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
3801   BuildMI(BB, X86::ADD32ri, 2, AddedSizeReg).addReg(TotalSizeReg).addImm(15);
3802
3803   // AlignedSize = and <AddedSize>, ~15
3804   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
3805   BuildMI(BB, X86::AND32ri, 2, AlignedSize).addReg(AddedSizeReg).addImm(~15);
3806
3807   // Subtract size from stack pointer, thereby allocating some space.
3808   BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
3809
3810   // Put a pointer to the space into the result register, by copying
3811   // the stack pointer.
3812   BuildMI(BB, X86::MOV32rr, 1, getReg(I)).addReg(X86::ESP);
3813
3814   // Inform the Frame Information that we have just allocated a variable-sized
3815   // object.
3816   F->getFrameInfo()->CreateVariableSizedObject();
3817 }
3818
3819 /// visitMallocInst - Malloc instructions are code generated into direct calls
3820 /// to the library malloc.
3821 ///
3822 void X86ISel::visitMallocInst(MallocInst &I) {
3823   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
3824   unsigned Arg;
3825
3826   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
3827     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
3828   } else {
3829     Arg = makeAnotherReg(Type::UIntTy);
3830     unsigned Op0Reg = getReg(I.getOperand(0));
3831     MachineBasicBlock::iterator MBBI = BB->end();
3832     doMultiplyConst(BB, MBBI, Arg, Type::UIntTy, Op0Reg, AllocSize);
3833   }
3834
3835   std::vector<ValueRecord> Args;
3836   Args.push_back(ValueRecord(Arg, Type::UIntTy));
3837   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
3838                                   1).addExternalSymbol("malloc", true);
3839   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
3840 }
3841
3842
3843 /// visitFreeInst - Free instructions are code gen'd to call the free libc
3844 /// function.
3845 ///
3846 void X86ISel::visitFreeInst(FreeInst &I) {
3847   std::vector<ValueRecord> Args;
3848   Args.push_back(ValueRecord(I.getOperand(0)));
3849   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
3850                                   1).addExternalSymbol("free", true);
3851   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
3852 }
3853
3854 /// createX86SimpleInstructionSelector - This pass converts an LLVM function
3855 /// into a machine code representation is a very simple peep-hole fashion.  The
3856 /// generated code sucks but the implementation is nice and simple.
3857 ///
3858 FunctionPass *llvm::createX86SimpleInstructionSelector(TargetMachine &TM) {
3859   return new X86ISel(TM);
3860 }