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