lib/Target/X86/InstSelectSimple.cpp

   1 //===-- InstSelectSimple.cpp - A simple instruction selector for x86 ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a simple peephole instruction selector for the x86 target
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "X86.h"
  15 #include "X86InstrBuilder.h"
  16 #include "X86InstrInfo.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/IntrinsicLowering.h"
  22 #include "llvm/Pass.h"
  23 #include "llvm/CodeGen/MachineConstantPool.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineInstrBuilder.h"
  27 #include "llvm/CodeGen/SSARegMap.h"
  28 #include "llvm/Target/MRegisterInfo.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include "llvm/Support/GetElementPtrTypeIterator.h"
  31 #include "llvm/Support/InstVisitor.h"
  32 #include "llvm/Support/CFG.h"
  33 #include "Support/Statistic.h"
  34 using namespace llvm;
  35
  36 namespace {
  37   Statistic<>
  38   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
  39 }
  40
  41 /// BMI - A special BuildMI variant that takes an iterator to insert the
  42 /// instruction at as well as a basic block.  This is the version for when you
  43 /// have a destination register in mind.
  44 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  45                                       MachineBasicBlock::iterator I,
  46                                       int Opcode, unsigned NumOperands,
  47                                       unsigned DestReg) {
  48   MachineInstr *MI = new MachineInstr(Opcode, NumOperands+1, true, true);
  49   MBB->insert(I, MI);
  50   return MachineInstrBuilder(MI).addReg(DestReg, MachineOperand::Def);
  51 }
  52
  53 /// BMI - A special BuildMI variant that takes an iterator to insert the
  54 /// instruction at as well as a basic block.
  55 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  56                                       MachineBasicBlock::iterator I,
  57                                       int Opcode, unsigned NumOperands) {
  58   MachineInstr *MI = new MachineInstr(Opcode, NumOperands, true, true);
  59   MBB->insert(I, MI);
  60   return MachineInstrBuilder(MI);
  61 }
  62
  63
  64 namespace {
  65   struct ISel : public FunctionPass, InstVisitor<ISel> {
  66     TargetMachine &TM;
  67     MachineFunction *F;                 // The function we are compiling into
  68     MachineBasicBlock *BB;              // The current MBB we are compiling
  69     int VarArgsFrameIndex;              // FrameIndex for start of varargs area
  70     int ReturnAddressIndex;             // FrameIndex for the return address
  71
  72     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  73
  74     // MBBMap - Mapping between LLVM BB -> Machine BB
  75     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  76
  77     ISel(TargetMachine &tm) : TM(tm), F(0), BB(0) {}
  78
  79     /// runOnFunction - Top level implementation of instruction selection for
  80     /// the entire function.
  81     ///
  82     bool runOnFunction(Function &Fn) {
  83       // First pass over the function, lower any unknown intrinsic functions
  84       // with the IntrinsicLowering class.
  85       LowerUnknownIntrinsicFunctionCalls(Fn);
  86
  87       F = &MachineFunction::construct(&Fn, TM);
  88
  89       // Create all of the machine basic blocks for the function...
  90       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  91         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
  92
  93       BB = &F->front();
  94
  95       // Set up a frame object for the return address.  This is used by the
  96       // llvm.returnaddress & llvm.frameaddress intrinisics.
  97       ReturnAddressIndex = F->getFrameInfo()->CreateFixedObject(4, -4);
  98
  99       // Copy incoming arguments off of the stack...
 100       LoadArgumentsToVirtualRegs(Fn);
 101
 102       // Instruction select everything except PHI nodes
 103       visit(Fn);
 104
 105       // Select the PHI nodes
 106       SelectPHINodes();
 107
 108       // Insert the FP_REG_KILL instructions into blocks that need them.
 109       InsertFPRegKills();
 110
 111       RegMap.clear();
 112       MBBMap.clear();
 113       F = 0;
 114       // We always build a machine code representation for the function
 115       return true;
 116     }
 117
 118     virtual const char *getPassName() const {
 119       return "X86 Simple Instruction Selection";
 120     }
 121
 122     /// visitBasicBlock - This method is called when we are visiting a new basic
 123     /// block.  This simply creates a new MachineBasicBlock to emit code into
 124     /// and adds it to the current MachineFunction.  Subsequent visit* for
 125     /// instructions will be invoked for all instructions in the basic block.
 126     ///
 127     void visitBasicBlock(BasicBlock &LLVM_BB) {
 128       BB = MBBMap[&LLVM_BB];
 129     }
 130
 131     /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
 132     /// function, lowering any calls to unknown intrinsic functions into the
 133     /// equivalent LLVM code.
 134     void LowerUnknownIntrinsicFunctionCalls(Function &F);
 135
 136     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 137     /// from the stack into virtual registers.
 138     ///
 139     void LoadArgumentsToVirtualRegs(Function &F);
 140
 141     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 142     /// because we have to generate our sources into the source basic blocks,
 143     /// not the current one.
 144     ///
 145     void SelectPHINodes();
 146
 147     /// InsertFPRegKills - Insert FP_REG_KILL instructions into basic blocks
 148     /// that need them.  This only occurs due to the floating point stackifier
 149     /// not being aggressive enough to handle arbitrary global stackification.
 150     ///
 151     void InsertFPRegKills();
 152
 153     // Visitation methods for various instructions.  These methods simply emit
 154     // fixed X86 code for each instruction.
 155     //
 156
 157     // Control flow operators
 158     void visitReturnInst(ReturnInst &RI);
 159     void visitBranchInst(BranchInst &BI);
 160
 161     struct ValueRecord {
 162       Value *Val;
 163       unsigned Reg;
 164       const Type *Ty;
 165       ValueRecord(unsigned R, const Type *T) : Val(0), Reg(R), Ty(T) {}
 166       ValueRecord(Value *V) : Val(V), Reg(0), Ty(V->getType()) {}
 167     };
 168     void doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 169                 const std::vector<ValueRecord> &Args);
 170     void visitCallInst(CallInst &I);
 171     void visitIntrinsicCall(Intrinsic::ID ID, CallInst &I);
 172
 173     // Arithmetic operators
 174     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 175     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 176     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 177     void doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
 178                     unsigned DestReg, const Type *DestTy,
 179                     unsigned Op0Reg, unsigned Op1Reg);
 180     void doMultiplyConst(MachineBasicBlock *MBB,
 181                          MachineBasicBlock::iterator MBBI,
 182                          unsigned DestReg, const Type *DestTy,
 183                          unsigned Op0Reg, unsigned Op1Val);
 184     void visitMul(BinaryOperator &B);
 185
 186     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 187     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 188     void visitDivRem(BinaryOperator &B);
 189
 190     // Bitwise operators
 191     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 192     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 193     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 194
 195     // Comparison operators...
 196     void visitSetCondInst(SetCondInst &I);
 197     unsigned EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 198                             MachineBasicBlock *MBB,
 199                             MachineBasicBlock::iterator MBBI);
 200
 201     // Memory Instructions
 202     void visitLoadInst(LoadInst &I);
 203     void visitStoreInst(StoreInst &I);
 204     void visitGetElementPtrInst(GetElementPtrInst &I);
 205     void visitAllocaInst(AllocaInst &I);
 206     void visitMallocInst(MallocInst &I);
 207     void visitFreeInst(FreeInst &I);
 208
 209     // Other operators
 210     void visitShiftInst(ShiftInst &I);
 211     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 212     void visitCastInst(CastInst &I);
 213     void visitVANextInst(VANextInst &I);
 214     void visitVAArgInst(VAArgInst &I);
 215
 216     void visitInstruction(Instruction &I) {
 217       std::cerr << "Cannot instruction select: " << I;
 218       abort();
 219     }
 220
 221     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 222     ///
 223     void promote32(unsigned targetReg, const ValueRecord &VR);
 224
 225     // getGEPIndex - This is used to fold GEP instructions into X86 addressing
 226     // expressions.
 227     void getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
 228                      std::vector<Value*> &GEPOps,
 229                      std::vector<const Type*> &GEPTypes, unsigned &BaseReg,
 230                      unsigned &Scale, unsigned &IndexReg, unsigned &Disp);
 231
 232     /// isGEPFoldable - Return true if the specified GEP can be completely
 233     /// folded into the addressing mode of a load/store or lea instruction.
 234     bool isGEPFoldable(MachineBasicBlock *MBB,
 235                        Value *Src, User::op_iterator IdxBegin,
 236                        User::op_iterator IdxEnd, unsigned &BaseReg,
 237                        unsigned &Scale, unsigned &IndexReg, unsigned &Disp);
 238
 239     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 240     /// constant expression GEP support.
 241     ///
 242     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
 243                           Value *Src, User::op_iterator IdxBegin,
 244                           User::op_iterator IdxEnd, unsigned TargetReg);
 245
 246     /// emitCastOperation - Common code shared between visitCastInst and
 247     /// constant expression cast support.
 248     void emitCastOperation(MachineBasicBlock *BB,MachineBasicBlock::iterator IP,
 249                            Value *Src, const Type *DestTy, unsigned TargetReg);
 250
 251     /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
 252     /// and constant expression support.
 253     void emitSimpleBinaryOperation(MachineBasicBlock *BB,
 254                                    MachineBasicBlock::iterator IP,
 255                                    Value *Op0, Value *Op1,
 256                                    unsigned OperatorClass, unsigned TargetReg);
 257
 258     void emitDivRemOperation(MachineBasicBlock *BB,
 259                              MachineBasicBlock::iterator IP,
 260                              unsigned Op0Reg, unsigned Op1Reg, bool isDiv,
 261                              const Type *Ty, unsigned TargetReg);
 262
 263     /// emitSetCCOperation - Common code shared between visitSetCondInst and
 264     /// constant expression support.
 265     void emitSetCCOperation(MachineBasicBlock *BB,
 266                             MachineBasicBlock::iterator IP,
 267                             Value *Op0, Value *Op1, unsigned Opcode,
 268                             unsigned TargetReg);
 269
 270     /// emitShiftOperation - Common code shared between visitShiftInst and
 271     /// constant expression support.
 272     void emitShiftOperation(MachineBasicBlock *MBB,
 273                             MachineBasicBlock::iterator IP,
 274                             Value *Op, Value *ShiftAmount, bool isLeftShift,
 275                             const Type *ResultTy, unsigned DestReg);
 276
 277
 278     /// copyConstantToRegister - Output the instructions required to put the
 279     /// specified constant into the specified register.
 280     ///
 281     void copyConstantToRegister(MachineBasicBlock *MBB,
 282                                 MachineBasicBlock::iterator MBBI,
 283                                 Constant *C, unsigned Reg);
 284
 285     /// makeAnotherReg - This method returns the next register number we haven't
 286     /// yet used.
 287     ///
 288     /// Long values are handled somewhat specially.  They are always allocated
 289     /// as pairs of 32 bit integer values.  The register number returned is the
 290     /// lower 32 bits of the long value, and the regNum+1 is the upper 32 bits
 291     /// of the long value.
 292     ///
 293     unsigned makeAnotherReg(const Type *Ty) {
 294       assert(dynamic_cast<const X86RegisterInfo*>(TM.getRegisterInfo()) &&
 295              "Current target doesn't have X86 reg info??");
 296       const X86RegisterInfo *MRI =
 297         static_cast<const X86RegisterInfo*>(TM.getRegisterInfo());
 298       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 299         const TargetRegisterClass *RC = MRI->getRegClassForType(Type::IntTy);
 300         // Create the lower part
 301         F->getSSARegMap()->createVirtualRegister(RC);
 302         // Create the upper part.
 303         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 304       }
 305
 306       // Add the mapping of regnumber => reg class to MachineFunction
 307       const TargetRegisterClass *RC = MRI->getRegClassForType(Ty);
 308       return F->getSSARegMap()->createVirtualRegister(RC);
 309     }
 310
 311     /// getReg - This method turns an LLVM value into a register number.  This
 312     /// is guaranteed to produce the same register number for a particular value
 313     /// every time it is queried.
 314     ///
 315     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 316     unsigned getReg(Value *V) {
 317       // Just append to the end of the current bb.
 318       MachineBasicBlock::iterator It = BB->end();
 319       return getReg(V, BB, It);
 320     }
 321     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 322                     MachineBasicBlock::iterator IPt) {
 323       unsigned &Reg = RegMap[V];
 324       if (Reg == 0) {
 325         Reg = makeAnotherReg(V->getType());
 326         RegMap[V] = Reg;
 327       }
 328
 329       // If this operand is a constant, emit the code to copy the constant into
 330       // the register here...
 331       //
 332       if (Constant *C = dyn_cast<Constant>(V)) {
 333         copyConstantToRegister(MBB, IPt, C, Reg);
 334         RegMap.erase(V);  // Assign a new name to this constant if ref'd again
 335       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 336         // Move the address of the global into the register
 337         BMI(MBB, IPt, X86::MOVri32, 1, Reg).addGlobalAddress(GV);
 338         RegMap.erase(V);  // Assign a new name to this address if ref'd again
 339       }
 340
 341       return Reg;
 342     }
 343   };
 344 }
 345
 346 /// TypeClass - Used by the X86 backend to group LLVM types by their basic X86
 347 /// Representation.
 348 ///
 349 enum TypeClass {
 350   cByte, cShort, cInt, cFP, cLong
 351 };
 352
 353 /// getClass - Turn a primitive type into a "class" number which is based on the
 354 /// size of the type, and whether or not it is floating point.
 355 ///
 356 static inline TypeClass getClass(const Type *Ty) {
 357   switch (Ty->getPrimitiveID()) {
 358   case Type::SByteTyID:
 359   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
 360   case Type::ShortTyID:
 361   case Type::UShortTyID:  return cShort;     // Short operands are class #1
 362   case Type::IntTyID:
 363   case Type::UIntTyID:
 364   case Type::PointerTyID: return cInt;       // Int's and pointers are class #2
 365
 366   case Type::FloatTyID:
 367   case Type::DoubleTyID:  return cFP;        // Floating Point is #3
 368
 369   case Type::LongTyID:
 370   case Type::ULongTyID:   return cLong;      // Longs are class #4
 371   default:
 372     assert(0 && "Invalid type to getClass!");
 373     return cByte;  // not reached
 374   }
 375 }
 376
 377 // getClassB - Just like getClass, but treat boolean values as bytes.
 378 static inline TypeClass getClassB(const Type *Ty) {
 379   if (Ty == Type::BoolTy) return cByte;
 380   return getClass(Ty);
 381 }
 382
 383
 384 /// copyConstantToRegister - Output the instructions required to put the
 385 /// specified constant into the specified register.
 386 ///
 387 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 388                                   MachineBasicBlock::iterator IP,
 389                                   Constant *C, unsigned R) {
 390   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 391     unsigned Class = 0;
 392     switch (CE->getOpcode()) {
 393     case Instruction::GetElementPtr:
 394       emitGEPOperation(MBB, IP, CE->getOperand(0),
 395                        CE->op_begin()+1, CE->op_end(), R);
 396       return;
 397     case Instruction::Cast:
 398       emitCastOperation(MBB, IP, CE->getOperand(0), CE->getType(), R);
 399       return;
 400
 401     case Instruction::Xor: ++Class; // FALL THROUGH
 402     case Instruction::Or:  ++Class; // FALL THROUGH
 403     case Instruction::And: ++Class; // FALL THROUGH
 404     case Instruction::Sub: ++Class; // FALL THROUGH
 405     case Instruction::Add:
 406       emitSimpleBinaryOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 407                                 Class, R);
 408       return;
 409
 410     case Instruction::Mul: {
 411       unsigned Op0Reg = getReg(CE->getOperand(0), MBB, IP);
 412       unsigned Op1Reg = getReg(CE->getOperand(1), MBB, IP);
 413       doMultiply(MBB, IP, R, CE->getType(), Op0Reg, Op1Reg);
 414       return;
 415     }
 416     case Instruction::Div:
 417     case Instruction::Rem: {
 418       unsigned Op0Reg = getReg(CE->getOperand(0), MBB, IP);
 419       unsigned Op1Reg = getReg(CE->getOperand(1), MBB, IP);
 420       emitDivRemOperation(MBB, IP, Op0Reg, Op1Reg,
 421                           CE->getOpcode() == Instruction::Div,
 422                           CE->getType(), R);
 423       return;
 424     }
 425
 426     case Instruction::SetNE:
 427     case Instruction::SetEQ:
 428     case Instruction::SetLT:
 429     case Instruction::SetGT:
 430     case Instruction::SetLE:
 431     case Instruction::SetGE:
 432       emitSetCCOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 433                          CE->getOpcode(), R);
 434       return;
 435
 436     case Instruction::Shl:
 437     case Instruction::Shr:
 438       emitShiftOperation(MBB, IP, CE->getOperand(0), CE->getOperand(1),
 439                          CE->getOpcode() == Instruction::Shl, CE->getType(), R);
 440       return;
 441
 442     default:
 443       std::cerr << "Offending expr: " << C << "\n";
 444       assert(0 && "Constant expression not yet handled!\n");
 445     }
 446   }
 447
 448   if (C->getType()->isIntegral()) {
 449     unsigned Class = getClassB(C->getType());
 450
 451     if (Class == cLong) {
 452       // Copy the value into the register pair.
 453       uint64_t Val = cast<ConstantInt>(C)->getRawValue();
 454       BMI(MBB, IP, X86::MOVri32, 1, R).addZImm(Val & 0xFFFFFFFF);
 455       BMI(MBB, IP, X86::MOVri32, 1, R+1).addZImm(Val >> 32);
 456       return;
 457     }
 458
 459     assert(Class <= cInt && "Type not handled yet!");
 460
 461     static const unsigned IntegralOpcodeTab[] = {
 462       X86::MOVri8, X86::MOVri16, X86::MOVri32
 463     };
 464
 465     if (C->getType() == Type::BoolTy) {
 466       BMI(MBB, IP, X86::MOVri8, 1, R).addZImm(C == ConstantBool::True);
 467     } else {
 468       ConstantInt *CI = cast<ConstantInt>(C);
 469       BMI(MBB, IP, IntegralOpcodeTab[Class], 1, R).addZImm(CI->getRawValue());
 470     }
 471   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 472     if (CFP->isExactlyValue(+0.0))
 473       BMI(MBB, IP, X86::FLD0, 0, R);
 474     else if (CFP->isExactlyValue(+1.0))
 475       BMI(MBB, IP, X86::FLD1, 0, R);
 476     else {
 477       // Otherwise we need to spill the constant to memory...
 478       MachineConstantPool *CP = F->getConstantPool();
 479       unsigned CPI = CP->getConstantPoolIndex(CFP);
 480       const Type *Ty = CFP->getType();
 481
 482       assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
 483       unsigned LoadOpcode = Ty == Type::FloatTy ? X86::FLDr32 : X86::FLDr64;
 484       addConstantPoolReference(BMI(MBB, IP, LoadOpcode, 4, R), CPI);
 485     }
 486
 487   } else if (isa<ConstantPointerNull>(C)) {
 488     // Copy zero (null pointer) to the register.
 489     BMI(MBB, IP, X86::MOVri32, 1, R).addZImm(0);
 490   } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 491     BMI(MBB, IP, X86::MOVri32, 1, R).addGlobalAddress(CPR->getValue());
 492   } else {
 493     std::cerr << "Offending constant: " << C << "\n";
 494     assert(0 && "Type not handled yet!");
 495   }
 496 }
 497
 498 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 499 /// the stack into virtual registers.
 500 ///
 501 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 502   // Emit instructions to load the arguments...  On entry to a function on the
 503   // X86, the stack frame looks like this:
 504   //
 505   // [ESP] -- return address
 506   // [ESP + 4] -- first argument (leftmost lexically)
 507   // [ESP + 8] -- second argument, if first argument is four bytes in size
 508   //    ...
 509   //
 510   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 511   MachineFrameInfo *MFI = F->getFrameInfo();
 512
 513   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 514     unsigned Reg = getReg(*I);
 515
 516     int FI;          // Frame object index
 517     switch (getClassB(I->getType())) {
 518     case cByte:
 519       FI = MFI->CreateFixedObject(1, ArgOffset);
 520       addFrameReference(BuildMI(BB, X86::MOVrm8, 4, Reg), FI);
 521       break;
 522     case cShort:
 523       FI = MFI->CreateFixedObject(2, ArgOffset);
 524       addFrameReference(BuildMI(BB, X86::MOVrm16, 4, Reg), FI);
 525       break;
 526     case cInt:
 527       FI = MFI->CreateFixedObject(4, ArgOffset);
 528       addFrameReference(BuildMI(BB, X86::MOVrm32, 4, Reg), FI);
 529       break;
 530     case cLong:
 531       FI = MFI->CreateFixedObject(8, ArgOffset);
 532       addFrameReference(BuildMI(BB, X86::MOVrm32, 4, Reg), FI);
 533       addFrameReference(BuildMI(BB, X86::MOVrm32, 4, Reg+1), FI, 4);
 534       ArgOffset += 4;   // longs require 4 additional bytes
 535       break;
 536     case cFP:
 537       unsigned Opcode;
 538       if (I->getType() == Type::FloatTy) {
 539         Opcode = X86::FLDr32;
 540         FI = MFI->CreateFixedObject(4, ArgOffset);
 541       } else {
 542         Opcode = X86::FLDr64;
 543         FI = MFI->CreateFixedObject(8, ArgOffset);
 544         ArgOffset += 4;   // doubles require 4 additional bytes
 545       }
 546       addFrameReference(BuildMI(BB, Opcode, 4, Reg), FI);
 547       break;
 548     default:
 549       assert(0 && "Unhandled argument type!");
 550     }
 551     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 552   }
 553
 554   // If the function takes variable number of arguments, add a frame offset for
 555   // the start of the first vararg value... this is used to expand
 556   // llvm.va_start.
 557   if (Fn.getFunctionType()->isVarArg())
 558     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 559 }
 560
 561
 562 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 563 /// because we have to generate our sources into the source basic blocks, not
 564 /// the current one.
 565 ///
 566 void ISel::SelectPHINodes() {
 567   const TargetInstrInfo &TII = TM.getInstrInfo();
 568   const Function &LF = *F->getFunction();  // The LLVM function...
 569   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 570     const BasicBlock *BB = I;
 571     MachineBasicBlock *MBB = MBBMap[I];
 572
 573     // Loop over all of the PHI nodes in the LLVM basic block...
 574     MachineBasicBlock::iterator instr = MBB->begin();
 575     for (BasicBlock::const_iterator I = BB->begin();
 576          PHINode *PN = const_cast<PHINode*>(dyn_cast<PHINode>(I)); ++I) {
 577
 578       // Create a new machine instr PHI node, and insert it.
 579       unsigned PHIReg = getReg(*PN);
 580       MachineInstr *PhiMI = BuildMI(X86::PHI, PN->getNumOperands(), PHIReg);
 581       MBB->insert(instr, PhiMI);
 582
 583       MachineInstr *LongPhiMI = 0;
 584       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy) {
 585         LongPhiMI = BuildMI(X86::PHI, PN->getNumOperands(), PHIReg+1);
 586         MBB->insert(instr, LongPhiMI);
 587       }
 588
 589       // PHIValues - Map of blocks to incoming virtual registers.  We use this
 590       // so that we only initialize one incoming value for a particular block,
 591       // even if the block has multiple entries in the PHI node.
 592       //
 593       std::map<MachineBasicBlock*, unsigned> PHIValues;
 594
 595       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 596         MachineBasicBlock *PredMBB = MBBMap[PN->getIncomingBlock(i)];
 597         unsigned ValReg;
 598         std::map<MachineBasicBlock*, unsigned>::iterator EntryIt =
 599           PHIValues.lower_bound(PredMBB);
 600
 601         if (EntryIt != PHIValues.end() && EntryIt->first == PredMBB) {
 602           // We already inserted an initialization of the register for this
 603           // predecessor.  Recycle it.
 604           ValReg = EntryIt->second;
 605
 606         } else {
 607           // Get the incoming value into a virtual register.
 608           //
 609           Value *Val = PN->getIncomingValue(i);
 610
 611           // If this is a constant or GlobalValue, we may have to insert code
 612           // into the basic block to compute it into a virtual register.
 613           if (isa<Constant>(Val) || isa<GlobalValue>(Val)) {
 614             // Because we don't want to clobber any values which might be in
 615             // physical registers with the computation of this constant (which
 616             // might be arbitrarily complex if it is a constant expression),
 617             // just insert the computation at the top of the basic block.
 618             MachineBasicBlock::iterator PI = PredMBB->begin();
 619
 620             // Skip over any PHI nodes though!
 621             while (PI != PredMBB->end() && PI->getOpcode() == X86::PHI)
 622               ++PI;
 623
 624             ValReg = getReg(Val, PredMBB, PI);
 625           } else {
 626             ValReg = getReg(Val);
 627           }
 628
 629           // Remember that we inserted a value for this PHI for this predecessor
 630           PHIValues.insert(EntryIt, std::make_pair(PredMBB, ValReg));
 631         }
 632
 633         PhiMI->addRegOperand(ValReg);
 634         PhiMI->addMachineBasicBlockOperand(PredMBB);
 635         if (LongPhiMI) {
 636           LongPhiMI->addRegOperand(ValReg+1);
 637           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 638         }
 639       }
 640     }
 641   }
 642 }
 643
 644 /// RequiresFPRegKill - The floating point stackifier pass cannot insert
 645 /// compensation code on critical edges.  As such, it requires that we kill all
 646 /// FP registers on the exit from any blocks that either ARE critical edges, or
 647 /// branch to a block that has incoming critical edges.
 648 ///
 649 /// Note that this kill instruction will eventually be eliminated when
 650 /// restrictions in the stackifier are relaxed.
 651 ///
 652 static bool RequiresFPRegKill(const BasicBlock *BB) {
 653 #if 0
 654   for (succ_const_iterator SI = succ_begin(BB), E = succ_end(BB); SI!=E; ++SI) {
 655     const BasicBlock *Succ = *SI;
 656     pred_const_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
 657     ++PI;  // Block have at least one predecessory
 658     if (PI != PE) {             // If it has exactly one, this isn't crit edge
 659       // If this block has more than one predecessor, check all of the
 660       // predecessors to see if they have multiple successors.  If so, then the
 661       // block we are analyzing needs an FPRegKill.
 662       for (PI = pred_begin(Succ); PI != PE; ++PI) {
 663         const BasicBlock *Pred = *PI;
 664         succ_const_iterator SI2 = succ_begin(Pred);
 665         ++SI2;  // There must be at least one successor of this block.
 666         if (SI2 != succ_end(Pred))
 667           return true;   // Yes, we must insert the kill on this edge.
 668       }
 669     }
 670   }
 671   // If we got this far, there is no need to insert the kill instruction.
 672   return false;
 673 #else
 674   return true;
 675 #endif
 676 }
 677
 678 // InsertFPRegKills - Insert FP_REG_KILL instructions into basic blocks that
 679 // need them.  This only occurs due to the floating point stackifier not being
 680 // aggressive enough to handle arbitrary global stackification.
 681 //
 682 // Currently we insert an FP_REG_KILL instruction into each block that uses or
 683 // defines a floating point virtual register.
 684 //
 685 // When the global register allocators (like linear scan) finally update live
 686 // variable analysis, we can keep floating point values in registers across
 687 // portions of the CFG that do not involve critical edges.  This will be a big
 688 // win, but we are waiting on the global allocators before we can do this.
 689 //
 690 // With a bit of work, the floating point stackifier pass can be enhanced to
 691 // break critical edges as needed (to make a place to put compensation code),
 692 // but this will require some infrastructure improvements as well.
 693 //
 694 void ISel::InsertFPRegKills() {
 695   SSARegMap &RegMap = *F->getSSARegMap();
 696
 697   for (MachineFunction::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 698     for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
 699       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 700       MachineOperand& MO = I->getOperand(i);
 701         if (MO.isRegister() && MO.getReg()) {
 702           unsigned Reg = MO.getReg();
 703           if (MRegisterInfo::isVirtualRegister(Reg))
 704             if (RegMap.getRegClass(Reg)->getSize() == 10)
 705               goto UsesFPReg;
 706         }
 707       }
 708     // If we haven't found an FP register use or def in this basic block, check
 709     // to see if any of our successors has an FP PHI node, which will cause a
 710     // copy to be inserted into this block.
 711     for (succ_const_iterator SI = succ_begin(BB->getBasicBlock()),
 712            E = succ_end(BB->getBasicBlock()); SI != E; ++SI) {
 713       MachineBasicBlock *SBB = MBBMap[*SI];
 714       for (MachineBasicBlock::iterator I = SBB->begin();
 715            I != SBB->end() && I->getOpcode() == X86::PHI; ++I) {
 716         if (RegMap.getRegClass(I->getOperand(0).getReg())->getSize() == 10)
 717           goto UsesFPReg;
 718       }
 719     }
 720     continue;
 721   UsesFPReg:
 722     // Okay, this block uses an FP register.  If the block has successors (ie,
 723     // it's not an unwind/return), insert the FP_REG_KILL instruction.
 724     if (BB->getBasicBlock()->getTerminator()->getNumSuccessors() &&
 725         RequiresFPRegKill(BB->getBasicBlock())) {
 726       BMI(BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
 727       ++NumFPKill;
 728     }
 729   }
 730 }
 731
 732
 733 // canFoldSetCCIntoBranch - Return the setcc instruction if we can fold it into
 734 // the conditional branch instruction which is the only user of the cc
 735 // instruction.  This is the case if the conditional branch is the only user of
 736 // the setcc, and if the setcc is in the same basic block as the conditional
 737 // branch.  We also don't handle long arguments below, so we reject them here as
 738 // well.
 739 //
 740 static SetCondInst *canFoldSetCCIntoBranch(Value *V) {
 741   if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 742     if (SCI->hasOneUse() && isa<BranchInst>(SCI->use_back()) &&
 743         SCI->getParent() == cast<BranchInst>(SCI->use_back())->getParent()) {
 744       const Type *Ty = SCI->getOperand(0)->getType();
 745       if (Ty != Type::LongTy && Ty != Type::ULongTy)
 746         return SCI;
 747     }
 748   return 0;
 749 }
 750
 751 // Return a fixed numbering for setcc instructions which does not depend on the
 752 // order of the opcodes.
 753 //
 754 static unsigned getSetCCNumber(unsigned Opcode) {
 755   switch(Opcode) {
 756   default: assert(0 && "Unknown setcc instruction!");
 757   case Instruction::SetEQ: return 0;
 758   case Instruction::SetNE: return 1;
 759   case Instruction::SetLT: return 2;
 760   case Instruction::SetGE: return 3;
 761   case Instruction::SetGT: return 4;
 762   case Instruction::SetLE: return 5;
 763   }
 764 }
 765
 766 // LLVM  -> X86 signed  X86 unsigned
 767 // -----    ----------  ------------
 768 // seteq -> sete        sete
 769 // setne -> setne       setne
 770 // setlt -> setl        setb
 771 // setge -> setge       setae
 772 // setgt -> setg        seta
 773 // setle -> setle       setbe
 774 // ----
 775 //          sets                       // Used by comparison with 0 optimization
 776 //          setns
 777 static const unsigned SetCCOpcodeTab[2][8] = {
 778   { X86::SETEr, X86::SETNEr, X86::SETBr, X86::SETAEr, X86::SETAr, X86::SETBEr,
 779     0, 0 },
 780   { X86::SETEr, X86::SETNEr, X86::SETLr, X86::SETGEr, X86::SETGr, X86::SETLEr,
 781     X86::SETSr, X86::SETNSr },
 782 };
 783
 784 // EmitComparison - This function emits a comparison of the two operands,
 785 // returning the extended setcc code to use.
 786 unsigned ISel::EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 787                               MachineBasicBlock *MBB,
 788                               MachineBasicBlock::iterator IP) {
 789   // The arguments are already supposed to be of the same type.
 790   const Type *CompTy = Op0->getType();
 791   unsigned Class = getClassB(CompTy);
 792   unsigned Op0r = getReg(Op0, MBB, IP);
 793
 794   // Special case handling of: cmp R, i
 795   if (Class == cByte || Class == cShort || Class == cInt)
 796     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 797       uint64_t Op1v = cast<ConstantInt>(CI)->getRawValue();
 798
 799       // Mask off any upper bits of the constant, if there are any...
 800       Op1v &= (1ULL << (8 << Class)) - 1;
 801
 802       // If this is a comparison against zero, emit more efficient code.  We
 803       // can't handle unsigned comparisons against zero unless they are == or
 804       // !=.  These should have been strength reduced already anyway.
 805       if (Op1v == 0 && (CompTy->isSigned() || OpNum < 2)) {
 806         static const unsigned TESTTab[] = {
 807           X86::TESTrr8, X86::TESTrr16, X86::TESTrr32
 808         };
 809         BMI(MBB, IP, TESTTab[Class], 2).addReg(Op0r).addReg(Op0r);
 810
 811         if (OpNum == 2) return 6;   // Map jl -> js
 812         if (OpNum == 3) return 7;   // Map jg -> jns
 813         return OpNum;
 814       }
 815
 816       static const unsigned CMPTab[] = {
 817         X86::CMPri8, X86::CMPri16, X86::CMPri32
 818       };
 819
 820       BMI(MBB, IP, CMPTab[Class], 2).addReg(Op0r).addZImm(Op1v);
 821       return OpNum;
 822     }
 823
 824   // Special case handling of comparison against +/- 0.0
 825   if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op1))
 826     if (CFP->isExactlyValue(+0.0) || CFP->isExactlyValue(-0.0)) {
 827       BMI(MBB, IP, X86::FTST, 1).addReg(Op0r);
 828       BMI(MBB, IP, X86::FNSTSWr8, 0);
 829       BMI(MBB, IP, X86::SAHF, 1);
 830       return OpNum;
 831     }
 832
 833   unsigned Op1r = getReg(Op1, MBB, IP);
 834   switch (Class) {
 835   default: assert(0 && "Unknown type class!");
 836     // Emit: cmp <var1>, <var2> (do the comparison).  We can
 837     // compare 8-bit with 8-bit, 16-bit with 16-bit, 32-bit with
 838     // 32-bit.
 839   case cByte:
 840     BMI(MBB, IP, X86::CMPrr8, 2).addReg(Op0r).addReg(Op1r);
 841     break;
 842   case cShort:
 843     BMI(MBB, IP, X86::CMPrr16, 2).addReg(Op0r).addReg(Op1r);
 844     break;
 845   case cInt:
 846     BMI(MBB, IP, X86::CMPrr32, 2).addReg(Op0r).addReg(Op1r);
 847     break;
 848   case cFP:
 849     BMI(MBB, IP, X86::FpUCOM, 2).addReg(Op0r).addReg(Op1r);
 850     BMI(MBB, IP, X86::FNSTSWr8, 0);
 851     BMI(MBB, IP, X86::SAHF, 1);
 852     break;
 853
 854   case cLong:
 855     if (OpNum < 2) {    // seteq, setne
 856       unsigned LoTmp = makeAnotherReg(Type::IntTy);
 857       unsigned HiTmp = makeAnotherReg(Type::IntTy);
 858       unsigned FinalTmp = makeAnotherReg(Type::IntTy);
 859       BMI(MBB, IP, X86::XORrr32, 2, LoTmp).addReg(Op0r).addReg(Op1r);
 860       BMI(MBB, IP, X86::XORrr32, 2, HiTmp).addReg(Op0r+1).addReg(Op1r+1);
 861       BMI(MBB, IP, X86::ORrr32,  2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
 862       break;  // Allow the sete or setne to be generated from flags set by OR
 863     } else {
 864       // Emit a sequence of code which compares the high and low parts once
 865       // each, then uses a conditional move to handle the overflow case.  For
 866       // example, a setlt for long would generate code like this:
 867       //
 868       // AL = lo(op1) < lo(op2)   // Signedness depends on operands
 869       // BL = hi(op1) < hi(op2)   // Always unsigned comparison
 870       // dest = hi(op1) == hi(op2) ? AL : BL;
 871       //
 872
 873       // FIXME: This would be much better if we had hierarchical register
 874       // classes!  Until then, hardcode registers so that we can deal with their
 875       // aliases (because we don't have conditional byte moves).
 876       //
 877       BMI(MBB, IP, X86::CMPrr32, 2).addReg(Op0r).addReg(Op1r);
 878       BMI(MBB, IP, SetCCOpcodeTab[0][OpNum], 0, X86::AL);
 879       BMI(MBB, IP, X86::CMPrr32, 2).addReg(Op0r+1).addReg(Op1r+1);
 880       BMI(MBB, IP, SetCCOpcodeTab[CompTy->isSigned()][OpNum], 0, X86::BL);
 881       BMI(MBB, IP, X86::IMPLICIT_DEF, 0, X86::BH);
 882       BMI(MBB, IP, X86::IMPLICIT_DEF, 0, X86::AH);
 883       BMI(MBB, IP, X86::CMOVErr16, 2, X86::BX).addReg(X86::BX).addReg(X86::AX);
 884       // NOTE: visitSetCondInst knows that the value is dumped into the BL
 885       // register at this point for long values...
 886       return OpNum;
 887     }
 888   }
 889   return OpNum;
 890 }
 891
 892
 893 /// SetCC instructions - Here we just emit boilerplate code to set a byte-sized
 894 /// register, then move it to wherever the result should be.
 895 ///
 896 void ISel::visitSetCondInst(SetCondInst &I) {
 897   if (canFoldSetCCIntoBranch(&I)) return;  // Fold this into a branch...
 898
 899   unsigned DestReg = getReg(I);
 900   MachineBasicBlock::iterator MII = BB->end();
 901   emitSetCCOperation(BB, MII, I.getOperand(0), I.getOperand(1), I.getOpcode(),
 902                      DestReg);
 903 }
 904
 905 /// emitSetCCOperation - Common code shared between visitSetCondInst and
 906 /// constant expression support.
 907 void ISel::emitSetCCOperation(MachineBasicBlock *MBB,
 908                               MachineBasicBlock::iterator IP,
 909                               Value *Op0, Value *Op1, unsigned Opcode,
 910                               unsigned TargetReg) {
 911   unsigned OpNum = getSetCCNumber(Opcode);
 912   OpNum = EmitComparison(OpNum, Op0, Op1, MBB, IP);
 913
 914   const Type *CompTy = Op0->getType();
 915   unsigned CompClass = getClassB(CompTy);
 916   bool isSigned = CompTy->isSigned() && CompClass != cFP;
 917
 918   if (CompClass != cLong || OpNum < 2) {
 919     // Handle normal comparisons with a setcc instruction...
 920     BMI(MBB, IP, SetCCOpcodeTab[isSigned][OpNum], 0, TargetReg);
 921   } else {
 922     // Handle long comparisons by copying the value which is already in BL into
 923     // the register we want...
 924     BMI(MBB, IP, X86::MOVrr8, 1, TargetReg).addReg(X86::BL);
 925   }
 926 }
 927
 928
 929
 930
 931 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
 932 /// operand, in the specified target register.
 933 void ISel::promote32(unsigned targetReg, const ValueRecord &VR) {
 934   bool isUnsigned = VR.Ty->isUnsigned();
 935
 936   // Make sure we have the register number for this value...
 937   unsigned Reg = VR.Val ? getReg(VR.Val) : VR.Reg;
 938
 939   switch (getClassB(VR.Ty)) {
 940   case cByte:
 941     // Extend value into target register (8->32)
 942     if (isUnsigned)
 943       BuildMI(BB, X86::MOVZXr32r8, 1, targetReg).addReg(Reg);
 944     else
 945       BuildMI(BB, X86::MOVSXr32r8, 1, targetReg).addReg(Reg);
 946     break;
 947   case cShort:
 948     // Extend value into target register (16->32)
 949     if (isUnsigned)
 950       BuildMI(BB, X86::MOVZXr32r16, 1, targetReg).addReg(Reg);
 951     else
 952       BuildMI(BB, X86::MOVSXr32r16, 1, targetReg).addReg(Reg);
 953     break;
 954   case cInt:
 955     // Move value into target register (32->32)
 956     BuildMI(BB, X86::MOVrr32, 1, targetReg).addReg(Reg);
 957     break;
 958   default:
 959     assert(0 && "Unpromotable operand class in promote32");
 960   }
 961 }
 962
 963 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 964 /// we have the following possibilities:
 965 ///
 966 ///   ret void: No return value, simply emit a 'ret' instruction
 967 ///   ret sbyte, ubyte : Extend value into EAX and return
 968 ///   ret short, ushort: Extend value into EAX and return
 969 ///   ret int, uint    : Move value into EAX and return
 970 ///   ret pointer      : Move value into EAX and return
 971 ///   ret long, ulong  : Move value into EAX/EDX and return
 972 ///   ret float/double : Top of FP stack
 973 ///
 974 void ISel::visitReturnInst(ReturnInst &I) {
 975   if (I.getNumOperands() == 0) {
 976     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
 977     return;
 978   }
 979
 980   Value *RetVal = I.getOperand(0);
 981   unsigned RetReg = getReg(RetVal);
 982   switch (getClassB(RetVal->getType())) {
 983   case cByte:   // integral return values: extend or move into EAX and return
 984   case cShort:
 985   case cInt:
 986     promote32(X86::EAX, ValueRecord(RetReg, RetVal->getType()));
 987     // Declare that EAX is live on exit
 988     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
 989     break;
 990   case cFP:                   // Floats & Doubles: Return in ST(0)
 991     BuildMI(BB, X86::FpSETRESULT, 1).addReg(RetReg);
 992     // Declare that top-of-stack is live on exit
 993     BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
 994     break;
 995   case cLong:
 996     BuildMI(BB, X86::MOVrr32, 1, X86::EAX).addReg(RetReg);
 997     BuildMI(BB, X86::MOVrr32, 1, X86::EDX).addReg(RetReg+1);
 998     // Declare that EAX & EDX are live on exit
 999     BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX)
1000       .addReg(X86::ESP);
1001     break;
1002   default:
1003     visitInstruction(I);
1004   }
1005   // Emit a 'ret' instruction
1006   BuildMI(BB, X86::RET, 0);
1007 }
1008
1009 // getBlockAfter - Return the basic block which occurs lexically after the
1010 // specified one.
1011 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
1012   Function::iterator I = BB; ++I;  // Get iterator to next block
1013   return I != BB->getParent()->end() ? &*I : 0;
1014 }
1015
1016 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
1017 /// that since code layout is frozen at this point, that if we are trying to
1018 /// jump to a block that is the immediate successor of the current block, we can
1019 /// just make a fall-through (but we don't currently).
1020 ///
1021 void ISel::visitBranchInst(BranchInst &BI) {
1022   BasicBlock *NextBB = getBlockAfter(BI.getParent());  // BB after current one
1023
1024   if (!BI.isConditional()) {  // Unconditional branch?
1025     if (BI.getSuccessor(0) != NextBB)
1026       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
1027     return;
1028   }
1029
1030   // See if we can fold the setcc into the branch itself...
1031   SetCondInst *SCI = canFoldSetCCIntoBranch(BI.getCondition());
1032   if (SCI == 0) {
1033     // Nope, cannot fold setcc into this branch.  Emit a branch on a condition
1034     // computed some other way...
1035     unsigned condReg = getReg(BI.getCondition());
1036     BuildMI(BB, X86::CMPri8, 2).addReg(condReg).addZImm(0);
1037     if (BI.getSuccessor(1) == NextBB) {
1038       if (BI.getSuccessor(0) != NextBB)
1039         BuildMI(BB, X86::JNE, 1).addPCDisp(BI.getSuccessor(0));
1040     } else {
1041       BuildMI(BB, X86::JE, 1).addPCDisp(BI.getSuccessor(1));
1042
1043       if (BI.getSuccessor(0) != NextBB)
1044         BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
1045     }
1046     return;
1047   }
1048
1049   unsigned OpNum = getSetCCNumber(SCI->getOpcode());
1050   MachineBasicBlock::iterator MII = BB->end();
1051   OpNum = EmitComparison(OpNum, SCI->getOperand(0), SCI->getOperand(1), BB,MII);
1052
1053   const Type *CompTy = SCI->getOperand(0)->getType();
1054   bool isSigned = CompTy->isSigned() && getClassB(CompTy) != cFP;
1055
1056
1057   // LLVM  -> X86 signed  X86 unsigned
1058   // -----    ----------  ------------
1059   // seteq -> je          je
1060   // setne -> jne         jne
1061   // setlt -> jl          jb
1062   // setge -> jge         jae
1063   // setgt -> jg          ja
1064   // setle -> jle         jbe
1065   // ----
1066   //          js                  // Used by comparison with 0 optimization
1067   //          jns
1068
1069   static const unsigned OpcodeTab[2][8] = {
1070     { X86::JE, X86::JNE, X86::JB, X86::JAE, X86::JA, X86::JBE, 0, 0 },
1071     { X86::JE, X86::JNE, X86::JL, X86::JGE, X86::JG, X86::JLE,
1072       X86::JS, X86::JNS },
1073   };
1074
1075   if (BI.getSuccessor(0) != NextBB) {
1076     BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(0));
1077     if (BI.getSuccessor(1) != NextBB)
1078       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(1));
1079   } else {
1080     // Change to the inverse condition...
1081     if (BI.getSuccessor(1) != NextBB) {
1082       OpNum ^= 1;
1083       BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(1));
1084     }
1085   }
1086 }
1087
1088
1089 /// doCall - This emits an abstract call instruction, setting up the arguments
1090 /// and the return value as appropriate.  For the actual function call itself,
1091 /// it inserts the specified CallMI instruction into the stream.
1092 ///
1093 void ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
1094                   const std::vector<ValueRecord> &Args) {
1095
1096   // Count how many bytes are to be pushed on the stack...
1097   unsigned NumBytes = 0;
1098
1099   if (!Args.empty()) {
1100     for (unsigned i = 0, e = Args.size(); i != e; ++i)
1101       switch (getClassB(Args[i].Ty)) {
1102       case cByte: case cShort: case cInt:
1103         NumBytes += 4; break;
1104       case cLong:
1105         NumBytes += 8; break;
1106       case cFP:
1107         NumBytes += Args[i].Ty == Type::FloatTy ? 4 : 8;
1108         break;
1109       default: assert(0 && "Unknown class!");
1110       }
1111
1112     // Adjust the stack pointer for the new arguments...
1113     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(NumBytes);
1114
1115     // Arguments go on the stack in reverse order, as specified by the ABI.
1116     unsigned ArgOffset = 0;
1117     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1118       unsigned ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1119       switch (getClassB(Args[i].Ty)) {
1120       case cByte:
1121       case cShort: {
1122         // Promote arg to 32 bits wide into a temporary register...
1123         unsigned R = makeAnotherReg(Type::UIntTy);
1124         promote32(R, Args[i]);
1125         addRegOffset(BuildMI(BB, X86::MOVmr32, 5),
1126                      X86::ESP, ArgOffset).addReg(R);
1127         break;
1128       }
1129       case cInt:
1130         addRegOffset(BuildMI(BB, X86::MOVmr32, 5),
1131                      X86::ESP, ArgOffset).addReg(ArgReg);
1132         break;
1133       case cLong:
1134         addRegOffset(BuildMI(BB, X86::MOVmr32, 5),
1135                      X86::ESP, ArgOffset).addReg(ArgReg);
1136         addRegOffset(BuildMI(BB, X86::MOVmr32, 5),
1137                      X86::ESP, ArgOffset+4).addReg(ArgReg+1);
1138         ArgOffset += 4;        // 8 byte entry, not 4.
1139         break;
1140
1141       case cFP:
1142         if (Args[i].Ty == Type::FloatTy) {
1143           addRegOffset(BuildMI(BB, X86::FSTr32, 5),
1144                        X86::ESP, ArgOffset).addReg(ArgReg);
1145         } else {
1146           assert(Args[i].Ty == Type::DoubleTy && "Unknown FP type!");
1147           addRegOffset(BuildMI(BB, X86::FSTr64, 5),
1148                        X86::ESP, ArgOffset).addReg(ArgReg);
1149           ArgOffset += 4;       // 8 byte entry, not 4.
1150         }
1151         break;
1152
1153       default: assert(0 && "Unknown class!");
1154       }
1155       ArgOffset += 4;
1156     }
1157   } else {
1158     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(0);
1159   }
1160
1161   BB->push_back(CallMI);
1162
1163   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addZImm(NumBytes);
1164
1165   // If there is a return value, scavenge the result from the location the call
1166   // leaves it in...
1167   //
1168   if (Ret.Ty != Type::VoidTy) {
1169     unsigned DestClass = getClassB(Ret.Ty);
1170     switch (DestClass) {
1171     case cByte:
1172     case cShort:
1173     case cInt: {
1174       // Integral results are in %eax, or the appropriate portion
1175       // thereof.
1176       static const unsigned regRegMove[] = {
1177         X86::MOVrr8, X86::MOVrr16, X86::MOVrr32
1178       };
1179       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
1180       BuildMI(BB, regRegMove[DestClass], 1, Ret.Reg).addReg(AReg[DestClass]);
1181       break;
1182     }
1183     case cFP:     // Floating-point return values live in %ST(0)
1184       BuildMI(BB, X86::FpGETRESULT, 1, Ret.Reg);
1185       break;
1186     case cLong:   // Long values are left in EDX:EAX
1187       BuildMI(BB, X86::MOVrr32, 1, Ret.Reg).addReg(X86::EAX);
1188       BuildMI(BB, X86::MOVrr32, 1, Ret.Reg+1).addReg(X86::EDX);
1189       break;
1190     default: assert(0 && "Unknown class!");
1191     }
1192   }
1193 }
1194
1195
1196 /// visitCallInst - Push args on stack and do a procedure call instruction.
1197 void ISel::visitCallInst(CallInst &CI) {
1198   MachineInstr *TheCall;
1199   if (Function *F = CI.getCalledFunction()) {
1200     // Is it an intrinsic function call?
1201     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) {
1202       visitIntrinsicCall(ID, CI);   // Special intrinsics are not handled here
1203       return;
1204     }
1205
1206     // Emit a CALL instruction with PC-relative displacement.
1207     TheCall = BuildMI(X86::CALLpcrel32, 1).addGlobalAddress(F, true);
1208   } else {  // Emit an indirect call...
1209     unsigned Reg = getReg(CI.getCalledValue());
1210     TheCall = BuildMI(X86::CALLr32, 1).addReg(Reg);
1211   }
1212
1213   std::vector<ValueRecord> Args;
1214   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
1215     Args.push_back(ValueRecord(CI.getOperand(i)));
1216
1217   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
1218   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args);
1219 }
1220
1221
1222 /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
1223 /// function, lowering any calls to unknown intrinsic functions into the
1224 /// equivalent LLVM code.
1225 void ISel::LowerUnknownIntrinsicFunctionCalls(Function &F) {
1226   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1227     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
1228       if (CallInst *CI = dyn_cast<CallInst>(I++))
1229         if (Function *F = CI->getCalledFunction())
1230           switch (F->getIntrinsicID()) {
1231           case Intrinsic::not_intrinsic:
1232           case Intrinsic::va_start:
1233           case Intrinsic::va_copy:
1234           case Intrinsic::va_end:
1235           case Intrinsic::returnaddress:
1236           case Intrinsic::frameaddress:
1237           case Intrinsic::memcpy:
1238           case Intrinsic::memset:
1239             // We directly implement these intrinsics
1240             break;
1241           default:
1242             // All other intrinsic calls we must lower.
1243             Instruction *Before = CI->getPrev();
1244             TM.getIntrinsicLowering().LowerIntrinsicCall(CI);
1245             if (Before) {        // Move iterator to instruction after call
1246               I = Before;  ++I;
1247             } else {
1248               I = BB->begin();
1249             }
1250           }
1251
1252 }
1253
1254 void ISel::visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI) {
1255   unsigned TmpReg1, TmpReg2;
1256   switch (ID) {
1257   case Intrinsic::va_start:
1258     // Get the address of the first vararg value...
1259     TmpReg1 = getReg(CI);
1260     addFrameReference(BuildMI(BB, X86::LEAr32, 5, TmpReg1), VarArgsFrameIndex);
1261     return;
1262
1263   case Intrinsic::va_copy:
1264     TmpReg1 = getReg(CI);
1265     TmpReg2 = getReg(CI.getOperand(1));
1266     BuildMI(BB, X86::MOVrr32, 1, TmpReg1).addReg(TmpReg2);
1267     return;
1268   case Intrinsic::va_end: return;   // Noop on X86
1269
1270   case Intrinsic::returnaddress:
1271   case Intrinsic::frameaddress:
1272     TmpReg1 = getReg(CI);
1273     if (cast<Constant>(CI.getOperand(1))->isNullValue()) {
1274       if (ID == Intrinsic::returnaddress) {
1275         // Just load the return address
1276         addFrameReference(BuildMI(BB, X86::MOVrm32, 4, TmpReg1),
1277                           ReturnAddressIndex);
1278       } else {
1279         addFrameReference(BuildMI(BB, X86::LEAr32, 4, TmpReg1),
1280                           ReturnAddressIndex, -4);
1281       }
1282     } else {
1283       // Values other than zero are not implemented yet.
1284       BuildMI(BB, X86::MOVri32, 1, TmpReg1).addZImm(0);
1285     }
1286     return;
1287
1288   case Intrinsic::memcpy: {
1289     assert(CI.getNumOperands() == 5 && "Illegal llvm.memcpy call!");
1290     unsigned Align = 1;
1291     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1292       Align = AlignC->getRawValue();
1293       if (Align == 0) Align = 1;
1294     }
1295
1296     // Turn the byte code into # iterations
1297     unsigned CountReg;
1298     unsigned Opcode;
1299     switch (Align & 3) {
1300     case 2:   // WORD aligned
1301       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1302         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1303       } else {
1304         CountReg = makeAnotherReg(Type::IntTy);
1305         unsigned ByteReg = getReg(CI.getOperand(3));
1306         BuildMI(BB, X86::SHRri32, 2, CountReg).addReg(ByteReg).addZImm(1);
1307       }
1308       Opcode = X86::REP_MOVSW;
1309       break;
1310     case 0:   // DWORD aligned
1311       if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1312         CountReg = getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1313       } else {
1314         CountReg = makeAnotherReg(Type::IntTy);
1315         unsigned ByteReg = getReg(CI.getOperand(3));
1316         BuildMI(BB, X86::SHRri32, 2, CountReg).addReg(ByteReg).addZImm(2);
1317       }
1318       Opcode = X86::REP_MOVSD;
1319       break;
1320     default:  // BYTE aligned
1321       CountReg = getReg(CI.getOperand(3));
1322       Opcode = X86::REP_MOVSB;
1323       break;
1324     }
1325
1326     // No matter what the alignment is, we put the source in ESI, the
1327     // destination in EDI, and the count in ECX.
1328     TmpReg1 = getReg(CI.getOperand(1));
1329     TmpReg2 = getReg(CI.getOperand(2));
1330     BuildMI(BB, X86::MOVrr32, 1, X86::ECX).addReg(CountReg);
1331     BuildMI(BB, X86::MOVrr32, 1, X86::EDI).addReg(TmpReg1);
1332     BuildMI(BB, X86::MOVrr32, 1, X86::ESI).addReg(TmpReg2);
1333     BuildMI(BB, Opcode, 0);
1334     return;
1335   }
1336   case Intrinsic::memset: {
1337     assert(CI.getNumOperands() == 5 && "Illegal llvm.memset call!");
1338     unsigned Align = 1;
1339     if (ConstantInt *AlignC = dyn_cast<ConstantInt>(CI.getOperand(4))) {
1340       Align = AlignC->getRawValue();
1341       if (Align == 0) Align = 1;
1342     }
1343
1344     // Turn the byte code into # iterations
1345     unsigned CountReg;
1346     unsigned Opcode;
1347     if (ConstantInt *ValC = dyn_cast<ConstantInt>(CI.getOperand(2))) {
1348       unsigned Val = ValC->getRawValue() & 255;
1349
1350       // If the value is a constant, then we can potentially use larger copies.
1351       switch (Align & 3) {
1352       case 2:   // WORD aligned
1353         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1354           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/2));
1355         } else {
1356           CountReg = makeAnotherReg(Type::IntTy);
1357           unsigned ByteReg = getReg(CI.getOperand(3));
1358           BuildMI(BB, X86::SHRri32, 2, CountReg).addReg(ByteReg).addZImm(1);
1359         }
1360         BuildMI(BB, X86::MOVri16, 1, X86::AX).addZImm((Val << 8) | Val);
1361         Opcode = X86::REP_STOSW;
1362         break;
1363       case 0:   // DWORD aligned
1364         if (ConstantInt *I = dyn_cast<ConstantInt>(CI.getOperand(3))) {
1365           CountReg =getReg(ConstantUInt::get(Type::UIntTy, I->getRawValue()/4));
1366         } else {
1367           CountReg = makeAnotherReg(Type::IntTy);
1368           unsigned ByteReg = getReg(CI.getOperand(3));
1369           BuildMI(BB, X86::SHRri32, 2, CountReg).addReg(ByteReg).addZImm(2);
1370         }
1371         Val = (Val << 8) | Val;
1372         BuildMI(BB, X86::MOVri32, 1, X86::EAX).addZImm((Val << 16) | Val);
1373         Opcode = X86::REP_STOSD;
1374         break;
1375       default:  // BYTE aligned
1376         CountReg = getReg(CI.getOperand(3));
1377         BuildMI(BB, X86::MOVri8, 1, X86::AL).addZImm(Val);
1378         Opcode = X86::REP_STOSB;
1379         break;
1380       }
1381     } else {
1382       // If it's not a constant value we are storing, just fall back.  We could
1383       // try to be clever to form 16 bit and 32 bit values, but we don't yet.
1384       unsigned ValReg = getReg(CI.getOperand(2));
1385       BuildMI(BB, X86::MOVrr8, 1, X86::AL).addReg(ValReg);
1386       CountReg = getReg(CI.getOperand(3));
1387       Opcode = X86::REP_STOSB;
1388     }
1389
1390     // No matter what the alignment is, we put the source in ESI, the
1391     // destination in EDI, and the count in ECX.
1392     TmpReg1 = getReg(CI.getOperand(1));
1393     //TmpReg2 = getReg(CI.getOperand(2));
1394     BuildMI(BB, X86::MOVrr32, 1, X86::ECX).addReg(CountReg);
1395     BuildMI(BB, X86::MOVrr32, 1, X86::EDI).addReg(TmpReg1);
1396     BuildMI(BB, Opcode, 0);
1397     return;
1398   }
1399
1400   default: assert(0 && "Error: unknown intrinsics should have been lowered!");
1401   }
1402 }
1403
1404
1405 /// visitSimpleBinary - Implement simple binary operators for integral types...
1406 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
1407 /// Xor.
1408 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
1409   unsigned DestReg = getReg(B);
1410   MachineBasicBlock::iterator MI = BB->end();
1411   emitSimpleBinaryOperation(BB, MI, B.getOperand(0), B.getOperand(1),
1412                             OperatorClass, DestReg);
1413 }
1414
1415 /// emitSimpleBinaryOperation - Implement simple binary operators for integral
1416 /// types...  OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for
1417 /// Or, 4 for Xor.
1418 ///
1419 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
1420 /// and constant expression support.
1421 ///
1422 void ISel::emitSimpleBinaryOperation(MachineBasicBlock *MBB,
1423                                      MachineBasicBlock::iterator IP,
1424                                      Value *Op0, Value *Op1,
1425                                      unsigned OperatorClass, unsigned DestReg) {
1426   unsigned Class = getClassB(Op0->getType());
1427
1428   // sub 0, X -> neg X
1429   if (OperatorClass == 1 && Class != cLong)
1430     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0)) {
1431       if (CI->isNullValue()) {
1432         unsigned op1Reg = getReg(Op1, MBB, IP);
1433         switch (Class) {
1434         default: assert(0 && "Unknown class for this function!");
1435         case cByte:
1436           BMI(MBB, IP, X86::NEGr8, 1, DestReg).addReg(op1Reg);
1437           return;
1438         case cShort:
1439           BMI(MBB, IP, X86::NEGr16, 1, DestReg).addReg(op1Reg);
1440           return;
1441         case cInt:
1442           BMI(MBB, IP, X86::NEGr32, 1, DestReg).addReg(op1Reg);
1443           return;
1444         }
1445       }
1446     } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(Op0))
1447       if (CFP->isExactlyValue(-0.0)) {
1448         // -0.0 - X === -X
1449         unsigned op1Reg = getReg(Op1, MBB, IP);
1450         BMI(MBB, IP, X86::FCHS, 1, DestReg).addReg(op1Reg);
1451         return;
1452       }
1453
1454   if (!isa<ConstantInt>(Op1) || Class == cLong) {
1455     static const unsigned OpcodeTab[][4] = {
1456       // Arithmetic operators
1457       { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32, X86::FpADD },  // ADD
1458       { X86::SUBrr8, X86::SUBrr16, X86::SUBrr32, X86::FpSUB },  // SUB
1459
1460       // Bitwise operators
1461       { X86::ANDrr8, X86::ANDrr16, X86::ANDrr32, 0 },  // AND
1462       { X86:: ORrr8, X86:: ORrr16, X86:: ORrr32, 0 },  // OR
1463       { X86::XORrr8, X86::XORrr16, X86::XORrr32, 0 },  // XOR
1464     };
1465
1466     bool isLong = false;
1467     if (Class == cLong) {
1468       isLong = true;
1469       Class = cInt;          // Bottom 32 bits are handled just like ints
1470     }
1471
1472     unsigned Opcode = OpcodeTab[OperatorClass][Class];
1473     assert(Opcode && "Floating point arguments to logical inst?");
1474     unsigned Op0r = getReg(Op0, MBB, IP);
1475     unsigned Op1r = getReg(Op1, MBB, IP);
1476     BMI(MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
1477
1478     if (isLong) {        // Handle the upper 32 bits of long values...
1479       static const unsigned TopTab[] = {
1480         X86::ADCrr32, X86::SBBrr32, X86::ANDrr32, X86::ORrr32, X86::XORrr32
1481       };
1482       BMI(MBB, IP, TopTab[OperatorClass], 2,
1483           DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
1484     }
1485     return;
1486   }
1487
1488   // Special case: op Reg, <const>
1489   ConstantInt *Op1C = cast<ConstantInt>(Op1);
1490   unsigned Op0r = getReg(Op0, MBB, IP);
1491
1492   // xor X, -1 -> not X
1493   if (OperatorClass == 4 && Op1C->isAllOnesValue()) {
1494     static unsigned const NOTTab[] = { X86::NOTr8, X86::NOTr16, X86::NOTr32 };
1495     BMI(MBB, IP, NOTTab[Class], 1, DestReg).addReg(Op0r);
1496     return;
1497   }
1498
1499   // add X, -1 -> dec X
1500   if (OperatorClass == 0 && Op1C->isAllOnesValue()) {
1501     static unsigned const DECTab[] = { X86::DECr8, X86::DECr16, X86::DECr32 };
1502     BMI(MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
1503     return;
1504   }
1505
1506   // add X, 1 -> inc X
1507   if (OperatorClass == 0 && Op1C->equalsInt(1)) {
1508     static unsigned const DECTab[] = { X86::INCr8, X86::INCr16, X86::INCr32 };
1509     BMI(MBB, IP, DECTab[Class], 1, DestReg).addReg(Op0r);
1510     return;
1511   }
1512
1513   static const unsigned OpcodeTab[][3] = {
1514     // Arithmetic operators
1515     { X86::ADDri8, X86::ADDri16, X86::ADDri32 },  // ADD
1516     { X86::SUBri8, X86::SUBri16, X86::SUBri32 },  // SUB
1517
1518     // Bitwise operators
1519     { X86::ANDri8, X86::ANDri16, X86::ANDri32 },  // AND
1520     { X86:: ORri8, X86:: ORri16, X86:: ORri32 },  // OR
1521     { X86::XORri8, X86::XORri16, X86::XORri32 },  // XOR
1522   };
1523
1524   assert(Class < 3 && "General code handles 64-bit integer types!");
1525   unsigned Opcode = OpcodeTab[OperatorClass][Class];
1526   uint64_t Op1v = cast<ConstantInt>(Op1C)->getRawValue();
1527
1528   // Mask off any upper bits of the constant, if there are any...
1529   Op1v &= (1ULL << (8 << Class)) - 1;
1530   BMI(MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addZImm(Op1v);
1531 }
1532
1533 /// doMultiply - Emit appropriate instructions to multiply together the
1534 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
1535 /// result should be given as DestTy.
1536 ///
1537 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
1538                       unsigned DestReg, const Type *DestTy,
1539                       unsigned op0Reg, unsigned op1Reg) {
1540   unsigned Class = getClass(DestTy);
1541   switch (Class) {
1542   case cFP:              // Floating point multiply
1543     BMI(BB, MBBI, X86::FpMUL, 2, DestReg).addReg(op0Reg).addReg(op1Reg);
1544     return;
1545   case cInt:
1546   case cShort:
1547     BMI(BB, MBBI, Class == cInt ? X86::IMULrr32 : X86::IMULrr16, 2, DestReg)
1548       .addReg(op0Reg).addReg(op1Reg);
1549     return;
1550   case cByte:
1551     // Must use the MUL instruction, which forces use of AL...
1552     BMI(MBB, MBBI, X86::MOVrr8, 1, X86::AL).addReg(op0Reg);
1553     BMI(MBB, MBBI, X86::MULr8, 1).addReg(op1Reg);
1554     BMI(MBB, MBBI, X86::MOVrr8, 1, DestReg).addReg(X86::AL);
1555     return;
1556   default:
1557   case cLong: assert(0 && "doMultiply cannot operate on LONG values!");
1558   }
1559 }
1560
1561 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1562 // returns zero when the input is not exactly a power of two.
1563 static unsigned ExactLog2(unsigned Val) {
1564   if (Val == 0) return 0;
1565   unsigned Count = 0;
1566   while (Val != 1) {
1567     if (Val & 1) return 0;
1568     Val >>= 1;
1569     ++Count;
1570   }
1571   return Count+1;
1572 }
1573
1574 void ISel::doMultiplyConst(MachineBasicBlock *MBB,
1575                            MachineBasicBlock::iterator IP,
1576                            unsigned DestReg, const Type *DestTy,
1577                            unsigned op0Reg, unsigned ConstRHS) {
1578   unsigned Class = getClass(DestTy);
1579
1580   // If the element size is exactly a power of 2, use a shift to get it.
1581   if (unsigned Shift = ExactLog2(ConstRHS)) {
1582     switch (Class) {
1583     default: assert(0 && "Unknown class for this function!");
1584     case cByte:
1585       BMI(MBB, IP, X86::SHLri32, 2, DestReg).addReg(op0Reg).addZImm(Shift-1);
1586       return;
1587     case cShort:
1588       BMI(MBB, IP, X86::SHLri32, 2, DestReg).addReg(op0Reg).addZImm(Shift-1);
1589       return;
1590     case cInt:
1591       BMI(MBB, IP, X86::SHLri32, 2, DestReg).addReg(op0Reg).addZImm(Shift-1);
1592       return;
1593     }
1594   }
1595
1596   if (Class == cShort) {
1597     BMI(MBB, IP, X86::IMULrri16, 2, DestReg).addReg(op0Reg).addZImm(ConstRHS);
1598     return;
1599   } else if (Class == cInt) {
1600     BMI(MBB, IP, X86::IMULrri32, 2, DestReg).addReg(op0Reg).addZImm(ConstRHS);
1601     return;
1602   }
1603
1604   // Most general case, emit a normal multiply...
1605   static const unsigned MOVriTab[] = {
1606     X86::MOVri8, X86::MOVri16, X86::MOVri32
1607   };
1608
1609   unsigned TmpReg = makeAnotherReg(DestTy);
1610   BMI(MBB, IP, MOVriTab[Class], 1, TmpReg).addZImm(ConstRHS);
1611
1612   // Emit a MUL to multiply the register holding the index by
1613   // elementSize, putting the result in OffsetReg.
1614   doMultiply(MBB, IP, DestReg, DestTy, op0Reg, TmpReg);
1615 }
1616
1617 /// visitMul - Multiplies are not simple binary operators because they must deal
1618 /// with the EAX register explicitly.
1619 ///
1620 void ISel::visitMul(BinaryOperator &I) {
1621   unsigned Op0Reg  = getReg(I.getOperand(0));
1622   unsigned DestReg = getReg(I);
1623
1624   // Simple scalar multiply?
1625   if (I.getType() != Type::LongTy && I.getType() != Type::ULongTy) {
1626     if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1))) {
1627       unsigned Val = (unsigned)CI->getRawValue(); // Cannot be 64-bit constant
1628       MachineBasicBlock::iterator MBBI = BB->end();
1629       doMultiplyConst(BB, MBBI, DestReg, I.getType(), Op0Reg, Val);
1630     } else {
1631       unsigned Op1Reg  = getReg(I.getOperand(1));
1632       MachineBasicBlock::iterator MBBI = BB->end();
1633       doMultiply(BB, MBBI, DestReg, I.getType(), Op0Reg, Op1Reg);
1634     }
1635   } else {
1636     unsigned Op1Reg  = getReg(I.getOperand(1));
1637
1638     // Long value.  We have to do things the hard way...
1639     // Multiply the two low parts... capturing carry into EDX
1640     BuildMI(BB, X86::MOVrr32, 1, X86::EAX).addReg(Op0Reg);
1641     BuildMI(BB, X86::MULr32, 1).addReg(Op1Reg);  // AL*BL
1642
1643     unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
1644     BuildMI(BB, X86::MOVrr32, 1, DestReg).addReg(X86::EAX);     // AL*BL
1645     BuildMI(BB, X86::MOVrr32, 1, OverflowReg).addReg(X86::EDX); // AL*BL >> 32
1646
1647     MachineBasicBlock::iterator MBBI = BB->end();
1648     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);   // AH*BL
1649     BMI(BB, MBBI, X86::IMULrr32, 2, AHBLReg).addReg(Op0Reg+1).addReg(Op1Reg);
1650
1651     unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
1652     BuildMI(BB, X86::ADDrr32, 2,                         // AH*BL+(AL*BL >> 32)
1653             AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
1654
1655     MBBI = BB->end();
1656     unsigned ALBHReg = makeAnotherReg(Type::UIntTy); // AL*BH
1657     BMI(BB, MBBI, X86::IMULrr32, 2, ALBHReg).addReg(Op0Reg).addReg(Op1Reg+1);
1658
1659     BuildMI(BB, X86::ADDrr32, 2,               // AL*BH + AH*BL + (AL*BL >> 32)
1660             DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
1661   }
1662 }
1663
1664
1665 /// visitDivRem - Handle division and remainder instructions... these
1666 /// instruction both require the same instructions to be generated, they just
1667 /// select the result from a different register.  Note that both of these
1668 /// instructions work differently for signed and unsigned operands.
1669 ///
1670 void ISel::visitDivRem(BinaryOperator &I) {
1671   unsigned Op0Reg = getReg(I.getOperand(0));
1672   unsigned Op1Reg = getReg(I.getOperand(1));
1673   unsigned ResultReg = getReg(I);
1674
1675   MachineBasicBlock::iterator IP = BB->end();
1676   emitDivRemOperation(BB, IP, Op0Reg, Op1Reg, I.getOpcode() == Instruction::Div,
1677                       I.getType(), ResultReg);
1678 }
1679
1680 void ISel::emitDivRemOperation(MachineBasicBlock *BB,
1681                                MachineBasicBlock::iterator IP,
1682                                unsigned Op0Reg, unsigned Op1Reg, bool isDiv,
1683                                const Type *Ty, unsigned ResultReg) {
1684   unsigned Class = getClass(Ty);
1685   switch (Class) {
1686   case cFP:              // Floating point divide
1687     if (isDiv) {
1688       BMI(BB, IP, X86::FpDIV, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
1689     } else {               // Floating point remainder...
1690       MachineInstr *TheCall =
1691         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
1692       std::vector<ValueRecord> Args;
1693       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
1694       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
1695       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
1696     }
1697     return;
1698   case cLong: {
1699     static const char *FnName[] =
1700       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
1701
1702     unsigned NameIdx = Ty->isUnsigned()*2 + isDiv;
1703     MachineInstr *TheCall =
1704       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
1705
1706     std::vector<ValueRecord> Args;
1707     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
1708     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
1709     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
1710     return;
1711   }
1712   case cByte: case cShort: case cInt:
1713     break;          // Small integrals, handled below...
1714   default: assert(0 && "Unknown class!");
1715   }
1716
1717   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
1718   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
1719   static const unsigned SarOpcode[]={ X86::SARri8, X86::SARri16, X86::SARri32 };
1720   static const unsigned ClrOpcode[]={ X86::MOVri8, X86::MOVri16, X86::MOVri32 };
1721   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
1722
1723   static const unsigned DivOpcode[][4] = {
1724     { X86::DIVr8 , X86::DIVr16 , X86::DIVr32 , 0 },  // Unsigned division
1725     { X86::IDIVr8, X86::IDIVr16, X86::IDIVr32, 0 },  // Signed division
1726   };
1727
1728   bool isSigned   = Ty->isSigned();
1729   unsigned Reg    = Regs[Class];
1730   unsigned ExtReg = ExtRegs[Class];
1731
1732   // Put the first operand into one of the A registers...
1733   BMI(BB, IP, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
1734
1735   if (isSigned) {
1736     // Emit a sign extension instruction...
1737     unsigned ShiftResult = makeAnotherReg(Ty);
1738     BMI(BB, IP, SarOpcode[Class], 2, ShiftResult).addReg(Op0Reg).addZImm(31);
1739     BMI(BB, IP, MovOpcode[Class], 1, ExtReg).addReg(ShiftResult);
1740   } else {
1741     // If unsigned, emit a zeroing instruction... (reg = 0)
1742     BMI(BB, IP, ClrOpcode[Class], 2, ExtReg).addZImm(0);
1743   }
1744
1745   // Emit the appropriate divide or remainder instruction...
1746   BMI(BB, IP, DivOpcode[isSigned][Class], 1).addReg(Op1Reg);
1747
1748   // Figure out which register we want to pick the result out of...
1749   unsigned DestReg = isDiv ? Reg : ExtReg;
1750
1751   // Put the result into the destination register...
1752   BMI(BB, IP, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
1753 }
1754
1755
1756 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
1757 /// for constant immediate shift values, and for constant immediate
1758 /// shift values equal to 1. Even the general case is sort of special,
1759 /// because the shift amount has to be in CL, not just any old register.
1760 ///
1761 void ISel::visitShiftInst(ShiftInst &I) {
1762   MachineBasicBlock::iterator IP = BB->end ();
1763   emitShiftOperation (BB, IP, I.getOperand (0), I.getOperand (1),
1764                       I.getOpcode () == Instruction::Shl, I.getType (),
1765                       getReg (I));
1766 }
1767
1768 /// emitShiftOperation - Common code shared between visitShiftInst and
1769 /// constant expression support.
1770 void ISel::emitShiftOperation(MachineBasicBlock *MBB,
1771                               MachineBasicBlock::iterator IP,
1772                               Value *Op, Value *ShiftAmount, bool isLeftShift,
1773                               const Type *ResultTy, unsigned DestReg) {
1774   unsigned SrcReg = getReg (Op, MBB, IP);
1775   bool isSigned = ResultTy->isSigned ();
1776   unsigned Class = getClass (ResultTy);
1777
1778   static const unsigned ConstantOperand[][4] = {
1779     { X86::SHRri8, X86::SHRri16, X86::SHRri32, X86::SHRDrri32 },  // SHR
1780     { X86::SARri8, X86::SARri16, X86::SARri32, X86::SHRDrri32 },  // SAR
1781     { X86::SHLri8, X86::SHLri16, X86::SHLri32, X86::SHLDrri32 },  // SHL
1782     { X86::SHLri8, X86::SHLri16, X86::SHLri32, X86::SHLDrri32 },  // SAL = SHL
1783   };
1784
1785   static const unsigned NonConstantOperand[][4] = {
1786     { X86::SHRrCL8, X86::SHRrCL16, X86::SHRrCL32 },  // SHR
1787     { X86::SARrCL8, X86::SARrCL16, X86::SARrCL32 },  // SAR
1788     { X86::SHLrCL8, X86::SHLrCL16, X86::SHLrCL32 },  // SHL
1789     { X86::SHLrCL8, X86::SHLrCL16, X86::SHLrCL32 },  // SAL = SHL
1790   };
1791
1792   // Longs, as usual, are handled specially...
1793   if (Class == cLong) {
1794     // If we have a constant shift, we can generate much more efficient code
1795     // than otherwise...
1796     //
1797     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
1798       unsigned Amount = CUI->getValue();
1799       if (Amount < 32) {
1800         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1801         if (isLeftShift) {
1802           BMI(MBB, IP, Opc[3], 3,
1803               DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addZImm(Amount);
1804           BMI(MBB, IP, Opc[2], 2, DestReg).addReg(SrcReg).addZImm(Amount);
1805         } else {
1806           BMI(MBB, IP, Opc[3], 3,
1807               DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addZImm(Amount);
1808           BMI(MBB, IP, Opc[2], 2, DestReg+1).addReg(SrcReg+1).addZImm(Amount);
1809         }
1810       } else {                 // Shifting more than 32 bits
1811         Amount -= 32;
1812         if (isLeftShift) {
1813           BMI(MBB, IP, X86::SHLri32, 2,
1814               DestReg + 1).addReg(SrcReg).addZImm(Amount);
1815           BMI(MBB, IP, X86::MOVri32, 1,
1816               DestReg).addZImm(0);
1817         } else {
1818           unsigned Opcode = isSigned ? X86::SARri32 : X86::SHRri32;
1819           BMI(MBB, IP, Opcode, 2, DestReg).addReg(SrcReg+1).addZImm(Amount);
1820           BMI(MBB, IP, X86::MOVri32, 1, DestReg+1).addZImm(0);
1821         }
1822       }
1823     } else {
1824       unsigned TmpReg = makeAnotherReg(Type::IntTy);
1825
1826       if (!isLeftShift && isSigned) {
1827         // If this is a SHR of a Long, then we need to do funny sign extension
1828         // stuff.  TmpReg gets the value to use as the high-part if we are
1829         // shifting more than 32 bits.
1830         BMI(MBB, IP, X86::SARri32, 2, TmpReg).addReg(SrcReg).addZImm(31);
1831       } else {
1832         // Other shifts use a fixed zero value if the shift is more than 32
1833         // bits.
1834         BMI(MBB, IP, X86::MOVri32, 1, TmpReg).addZImm(0);
1835       }
1836
1837       // Initialize CL with the shift amount...
1838       unsigned ShiftAmountReg = getReg(ShiftAmount, MBB, IP);
1839       BMI(MBB, IP, X86::MOVrr8, 1, X86::CL).addReg(ShiftAmountReg);
1840
1841       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
1842       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
1843       if (isLeftShift) {
1844         // TmpReg2 = shld inHi, inLo
1845         BMI(MBB, IP, X86::SHLDrrCL32,2,TmpReg2).addReg(SrcReg+1).addReg(SrcReg);
1846         // TmpReg3 = shl  inLo, CL
1847         BMI(MBB, IP, X86::SHLrCL32, 1, TmpReg3).addReg(SrcReg);
1848
1849         // Set the flags to indicate whether the shift was by more than 32 bits.
1850         BMI(MBB, IP, X86::TESTri8, 2).addReg(X86::CL).addZImm(32);
1851
1852         // DestHi = (>32) ? TmpReg3 : TmpReg2;
1853         BMI(MBB, IP, X86::CMOVNErr32, 2,
1854                 DestReg+1).addReg(TmpReg2).addReg(TmpReg3);
1855         // DestLo = (>32) ? TmpReg : TmpReg3;
1856         BMI(MBB, IP, X86::CMOVNErr32, 2,
1857             DestReg).addReg(TmpReg3).addReg(TmpReg);
1858       } else {
1859         // TmpReg2 = shrd inLo, inHi
1860         BMI(MBB, IP, X86::SHRDrrCL32,2,TmpReg2).addReg(SrcReg).addReg(SrcReg+1);
1861         // TmpReg3 = s[ah]r  inHi, CL
1862         BMI(MBB, IP, isSigned ? X86::SARrCL32 : X86::SHRrCL32, 1, TmpReg3)
1863                        .addReg(SrcReg+1);
1864
1865         // Set the flags to indicate whether the shift was by more than 32 bits.
1866         BMI(MBB, IP, X86::TESTri8, 2).addReg(X86::CL).addZImm(32);
1867
1868         // DestLo = (>32) ? TmpReg3 : TmpReg2;
1869         BMI(MBB, IP, X86::CMOVNErr32, 2,
1870                 DestReg).addReg(TmpReg2).addReg(TmpReg3);
1871
1872         // DestHi = (>32) ? TmpReg : TmpReg3;
1873         BMI(MBB, IP, X86::CMOVNErr32, 2,
1874                 DestReg+1).addReg(TmpReg3).addReg(TmpReg);
1875       }
1876     }
1877     return;
1878   }
1879
1880   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
1881     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
1882     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
1883
1884     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1885     BMI(MBB, IP, Opc[Class], 2,
1886         DestReg).addReg(SrcReg).addZImm(CUI->getValue());
1887   } else {                  // The shift amount is non-constant.
1888     unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
1889     BMI(MBB, IP, X86::MOVrr8, 1, X86::CL).addReg(ShiftAmountReg);
1890
1891     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
1892     BMI(MBB, IP, Opc[Class], 1, DestReg).addReg(SrcReg);
1893   }
1894 }
1895
1896
1897 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
1898 /// instruction.  The load and store instructions are the only place where we
1899 /// need to worry about the memory layout of the target machine.
1900 ///
1901 void ISel::visitLoadInst(LoadInst &I) {
1902   unsigned DestReg = getReg(I);
1903   unsigned BaseReg = 0, Scale = 1, IndexReg = 0, Disp = 0;
1904   Value *Addr = I.getOperand(0);
1905   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) {
1906     if (isGEPFoldable(BB, GEP->getOperand(0), GEP->op_begin()+1, GEP->op_end(),
1907                        BaseReg, Scale, IndexReg, Disp))
1908       Addr = 0;  // Address is consumed!
1909   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
1910     if (CE->getOpcode() == Instruction::GetElementPtr)
1911       if (isGEPFoldable(BB, CE->getOperand(0), CE->op_begin()+1, CE->op_end(),
1912                         BaseReg, Scale, IndexReg, Disp))
1913         Addr = 0;
1914   }
1915
1916   if (Addr) {
1917     // If it's not foldable, reset addr mode.
1918     BaseReg = getReg(Addr);
1919     Scale = 1; IndexReg = 0; Disp = 0;
1920   }
1921
1922   unsigned Class = getClassB(I.getType());
1923   if (Class == cLong) {
1924     addFullAddress(BuildMI(BB, X86::MOVrm32, 4, DestReg),
1925                    BaseReg, Scale, IndexReg, Disp);
1926     addFullAddress(BuildMI(BB, X86::MOVrm32, 4, DestReg+1),
1927                    BaseReg, Scale, IndexReg, Disp+4);
1928     return;
1929   }
1930
1931   static const unsigned Opcodes[] = {
1932     X86::MOVrm8, X86::MOVrm16, X86::MOVrm32, X86::FLDr32
1933   };
1934   unsigned Opcode = Opcodes[Class];
1935   if (I.getType() == Type::DoubleTy) Opcode = X86::FLDr64;
1936   addFullAddress(BuildMI(BB, Opcode, 4, DestReg),
1937                  BaseReg, Scale, IndexReg, Disp);
1938 }
1939
1940 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
1941 /// instruction.
1942 ///
1943 void ISel::visitStoreInst(StoreInst &I) {
1944   unsigned BaseReg = 0, Scale = 1, IndexReg = 0, Disp = 0;
1945   Value *Addr = I.getOperand(1);
1946   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) {
1947     if (isGEPFoldable(BB, GEP->getOperand(0), GEP->op_begin()+1, GEP->op_end(),
1948                        BaseReg, Scale, IndexReg, Disp))
1949       Addr = 0;  // Address is consumed!
1950   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
1951     if (CE->getOpcode() == Instruction::GetElementPtr)
1952       if (isGEPFoldable(BB, CE->getOperand(0), CE->op_begin()+1, CE->op_end(),
1953                         BaseReg, Scale, IndexReg, Disp))
1954         Addr = 0;
1955   }
1956
1957   if (Addr) {
1958     // If it's not foldable, reset addr mode.
1959     BaseReg = getReg(Addr);
1960     Scale = 1; IndexReg = 0; Disp = 0;
1961   }
1962
1963   const Type *ValTy = I.getOperand(0)->getType();
1964   unsigned Class = getClassB(ValTy);
1965
1966   if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(0))) {
1967     uint64_t Val = CI->getRawValue();
1968     if (Class == cLong) {
1969       addFullAddress(BuildMI(BB, X86::MOVmi32, 5),
1970                      BaseReg, Scale, IndexReg, Disp).addZImm(Val & ~0U);
1971       addFullAddress(BuildMI(BB, X86::MOVmi32, 5),
1972                      BaseReg, Scale, IndexReg, Disp+4).addZImm(Val>>32);
1973     } else {
1974       static const unsigned Opcodes[] = {
1975         X86::MOVmi8, X86::MOVmi16, X86::MOVmi32
1976       };
1977       unsigned Opcode = Opcodes[Class];
1978       addFullAddress(BuildMI(BB, Opcode, 5),
1979                      BaseReg, Scale, IndexReg, Disp).addZImm(Val);
1980     }
1981   } else if (ConstantBool *CB = dyn_cast<ConstantBool>(I.getOperand(0))) {
1982     addFullAddress(BuildMI(BB, X86::MOVmi8, 5),
1983                    BaseReg, Scale, IndexReg, Disp).addZImm(CB->getValue());
1984   } else {
1985     if (Class == cLong) {
1986       unsigned ValReg = getReg(I.getOperand(0));
1987       addFullAddress(BuildMI(BB, X86::MOVmr32, 5),
1988                      BaseReg, Scale, IndexReg, Disp).addReg(ValReg);
1989       addFullAddress(BuildMI(BB, X86::MOVmr32, 5),
1990                      BaseReg, Scale, IndexReg, Disp+4).addReg(ValReg+1);
1991     } else {
1992       unsigned ValReg = getReg(I.getOperand(0));
1993       static const unsigned Opcodes[] = {
1994         X86::MOVmr8, X86::MOVmr16, X86::MOVmr32, X86::FSTr32
1995       };
1996       unsigned Opcode = Opcodes[Class];
1997       if (ValTy == Type::DoubleTy) Opcode = X86::FSTr64;
1998       addFullAddress(BuildMI(BB, Opcode, 1+4),
1999                      BaseReg, Scale, IndexReg, Disp).addReg(ValReg);
2000     }
2001   }
2002 }
2003
2004
2005 /// visitCastInst - Here we have various kinds of copying with or without
2006 /// sign extension going on.
2007 void ISel::visitCastInst(CastInst &CI) {
2008   Value *Op = CI.getOperand(0);
2009   // If this is a cast from a 32-bit integer to a Long type, and the only uses
2010   // of the case are GEP instructions, then the cast does not need to be
2011   // generated explicitly, it will be folded into the GEP.
2012   if (CI.getType() == Type::LongTy &&
2013       (Op->getType() == Type::IntTy || Op->getType() == Type::UIntTy)) {
2014     bool AllUsesAreGEPs = true;
2015     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
2016       if (!isa<GetElementPtrInst>(*I)) {
2017         AllUsesAreGEPs = false;
2018         break;
2019       }
2020
2021     // No need to codegen this cast if all users are getelementptr instrs...
2022     if (AllUsesAreGEPs) return;
2023   }
2024
2025   unsigned DestReg = getReg(CI);
2026   MachineBasicBlock::iterator MI = BB->end();
2027   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
2028 }
2029
2030 /// emitCastOperation - Common code shared between visitCastInst and
2031 /// constant expression cast support.
2032 void ISel::emitCastOperation(MachineBasicBlock *BB,
2033                              MachineBasicBlock::iterator IP,
2034                              Value *Src, const Type *DestTy,
2035                              unsigned DestReg) {
2036   unsigned SrcReg = getReg(Src, BB, IP);
2037   const Type *SrcTy = Src->getType();
2038   unsigned SrcClass = getClassB(SrcTy);
2039   unsigned DestClass = getClassB(DestTy);
2040
2041   // Implement casts to bool by using compare on the operand followed by set if
2042   // not zero on the result.
2043   if (DestTy == Type::BoolTy) {
2044     switch (SrcClass) {
2045     case cByte:
2046       BMI(BB, IP, X86::TESTrr8, 2).addReg(SrcReg).addReg(SrcReg);
2047       break;
2048     case cShort:
2049       BMI(BB, IP, X86::TESTrr16, 2).addReg(SrcReg).addReg(SrcReg);
2050       break;
2051     case cInt:
2052       BMI(BB, IP, X86::TESTrr32, 2).addReg(SrcReg).addReg(SrcReg);
2053       break;
2054     case cLong: {
2055       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2056       BMI(BB, IP, X86::ORrr32, 2, TmpReg).addReg(SrcReg).addReg(SrcReg+1);
2057       break;
2058     }
2059     case cFP:
2060       BMI(BB, IP, X86::FTST, 1).addReg(SrcReg);
2061       BMI(BB, IP, X86::FNSTSWr8, 0);
2062       BMI(BB, IP, X86::SAHF, 1);
2063       break;
2064     }
2065
2066     // If the zero flag is not set, then the value is true, set the byte to
2067     // true.
2068     BMI(BB, IP, X86::SETNEr, 1, DestReg);
2069     return;
2070   }
2071
2072   static const unsigned RegRegMove[] = {
2073     X86::MOVrr8, X86::MOVrr16, X86::MOVrr32, X86::FpMOV, X86::MOVrr32
2074   };
2075
2076   // Implement casts between values of the same type class (as determined by
2077   // getClass) by using a register-to-register move.
2078   if (SrcClass == DestClass) {
2079     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
2080       BMI(BB, IP, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
2081     } else if (SrcClass == cFP) {
2082       if (SrcTy == Type::FloatTy) {  // double -> float
2083         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
2084         BMI(BB, IP, X86::FpMOV, 1, DestReg).addReg(SrcReg);
2085       } else {                       // float -> double
2086         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
2087                "Unknown cFP member!");
2088         // Truncate from double to float by storing to memory as short, then
2089         // reading it back.
2090         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
2091         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
2092         addFrameReference(BMI(BB, IP, X86::FSTr32, 5), FrameIdx).addReg(SrcReg);
2093         addFrameReference(BMI(BB, IP, X86::FLDr32, 5, DestReg), FrameIdx);
2094       }
2095     } else if (SrcClass == cLong) {
2096       BMI(BB, IP, X86::MOVrr32, 1, DestReg).addReg(SrcReg);
2097       BMI(BB, IP, X86::MOVrr32, 1, DestReg+1).addReg(SrcReg+1);
2098     } else {
2099       assert(0 && "Cannot handle this type of cast instruction!");
2100       abort();
2101     }
2102     return;
2103   }
2104
2105   // Handle cast of SMALLER int to LARGER int using a move with sign extension
2106   // or zero extension, depending on whether the source type was signed.
2107   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
2108       SrcClass < DestClass) {
2109     bool isLong = DestClass == cLong;
2110     if (isLong) DestClass = cInt;
2111
2112     static const unsigned Opc[][4] = {
2113       { X86::MOVSXr16r8, X86::MOVSXr32r8, X86::MOVSXr32r16, X86::MOVrr32 }, // s
2114       { X86::MOVZXr16r8, X86::MOVZXr32r8, X86::MOVZXr32r16, X86::MOVrr32 }  // u
2115     };
2116
2117     bool isUnsigned = SrcTy->isUnsigned();
2118     BMI(BB, IP, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
2119         DestReg).addReg(SrcReg);
2120
2121     if (isLong) {  // Handle upper 32 bits as appropriate...
2122       if (isUnsigned)     // Zero out top bits...
2123         BMI(BB, IP, X86::MOVri32, 1, DestReg+1).addZImm(0);
2124       else                // Sign extend bottom half...
2125         BMI(BB, IP, X86::SARri32, 2, DestReg+1).addReg(DestReg).addZImm(31);
2126     }
2127     return;
2128   }
2129
2130   // Special case long -> int ...
2131   if (SrcClass == cLong && DestClass == cInt) {
2132     BMI(BB, IP, X86::MOVrr32, 1, DestReg).addReg(SrcReg);
2133     return;
2134   }
2135
2136   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
2137   // move out of AX or AL.
2138   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
2139       && SrcClass > DestClass) {
2140     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
2141     BMI(BB, IP, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
2142     BMI(BB, IP, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
2143     return;
2144   }
2145
2146   // Handle casts from integer to floating point now...
2147   if (DestClass == cFP) {
2148     // Promote the integer to a type supported by FLD.  We do this because there
2149     // are no unsigned FLD instructions, so we must promote an unsigned value to
2150     // a larger signed value, then use FLD on the larger value.
2151     //
2152     const Type *PromoteType = 0;
2153     unsigned PromoteOpcode;
2154     unsigned RealDestReg = DestReg;
2155     switch (SrcTy->getPrimitiveID()) {
2156     case Type::BoolTyID:
2157     case Type::SByteTyID:
2158       // We don't have the facilities for directly loading byte sized data from
2159       // memory (even signed).  Promote it to 16 bits.
2160       PromoteType = Type::ShortTy;
2161       PromoteOpcode = X86::MOVSXr16r8;
2162       break;
2163     case Type::UByteTyID:
2164       PromoteType = Type::ShortTy;
2165       PromoteOpcode = X86::MOVZXr16r8;
2166       break;
2167     case Type::UShortTyID:
2168       PromoteType = Type::IntTy;
2169       PromoteOpcode = X86::MOVZXr32r16;
2170       break;
2171     case Type::UIntTyID: {
2172       // Make a 64 bit temporary... and zero out the top of it...
2173       unsigned TmpReg = makeAnotherReg(Type::LongTy);
2174       BMI(BB, IP, X86::MOVrr32, 1, TmpReg).addReg(SrcReg);
2175       BMI(BB, IP, X86::MOVri32, 1, TmpReg+1).addZImm(0);
2176       SrcTy = Type::LongTy;
2177       SrcClass = cLong;
2178       SrcReg = TmpReg;
2179       break;
2180     }
2181     case Type::ULongTyID:
2182       // Don't fild into the read destination.
2183       DestReg = makeAnotherReg(Type::DoubleTy);
2184       break;
2185     default:  // No promotion needed...
2186       break;
2187     }
2188
2189     if (PromoteType) {
2190       unsigned TmpReg = makeAnotherReg(PromoteType);
2191       unsigned Opc = SrcTy->isSigned() ? X86::MOVSXr16r8 : X86::MOVZXr16r8;
2192       BMI(BB, IP, Opc, 1, TmpReg).addReg(SrcReg);
2193       SrcTy = PromoteType;
2194       SrcClass = getClass(PromoteType);
2195       SrcReg = TmpReg;
2196     }
2197
2198     // Spill the integer to memory and reload it from there...
2199     int FrameIdx =
2200       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
2201
2202     if (SrcClass == cLong) {
2203       addFrameReference(BMI(BB, IP, X86::MOVmr32, 5), FrameIdx).addReg(SrcReg);
2204       addFrameReference(BMI(BB, IP, X86::MOVmr32, 5),
2205                         FrameIdx, 4).addReg(SrcReg+1);
2206     } else {
2207       static const unsigned Op1[] = { X86::MOVmr8, X86::MOVmr16, X86::MOVmr32 };
2208       addFrameReference(BMI(BB, IP, Op1[SrcClass], 5), FrameIdx).addReg(SrcReg);
2209     }
2210
2211     static const unsigned Op2[] =
2212       { 0/*byte*/, X86::FILDr16, X86::FILDr32, 0/*FP*/, X86::FILDr64 };
2213     addFrameReference(BMI(BB, IP, Op2[SrcClass], 5, DestReg), FrameIdx);
2214
2215     // We need special handling for unsigned 64-bit integer sources.  If the
2216     // input number has the "sign bit" set, then we loaded it incorrectly as a
2217     // negative 64-bit number.  In this case, add an offset value.
2218     if (SrcTy == Type::ULongTy) {
2219       // Emit a test instruction to see if the dynamic input value was signed.
2220       BMI(BB, IP, X86::TESTrr32, 2).addReg(SrcReg+1).addReg(SrcReg+1);
2221
2222       // If the sign bit is set, get a pointer to an offset, otherwise get a
2223       // pointer to a zero.
2224       MachineConstantPool *CP = F->getConstantPool();
2225       unsigned Zero = makeAnotherReg(Type::IntTy);
2226       Constant *Null = Constant::getNullValue(Type::UIntTy);
2227       addConstantPoolReference(BMI(BB, IP, X86::LEAr32, 5, Zero),
2228                                CP->getConstantPoolIndex(Null));
2229       unsigned Offset = makeAnotherReg(Type::IntTy);
2230       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
2231
2232       addConstantPoolReference(BMI(BB, IP, X86::LEAr32, 5, Offset),
2233                                CP->getConstantPoolIndex(OffsetCst));
2234       unsigned Addr = makeAnotherReg(Type::IntTy);
2235       BMI(BB, IP, X86::CMOVSrr32, 2, Addr).addReg(Zero).addReg(Offset);
2236
2237       // Load the constant for an add.  FIXME: this could make an 'fadd' that
2238       // reads directly from memory, but we don't support these yet.
2239       unsigned ConstReg = makeAnotherReg(Type::DoubleTy);
2240       addDirectMem(BMI(BB, IP, X86::FLDr32, 4, ConstReg), Addr);
2241
2242       BMI(BB, IP, X86::FpADD, 2, RealDestReg).addReg(ConstReg).addReg(DestReg);
2243     }
2244
2245     return;
2246   }
2247
2248   // Handle casts from floating point to integer now...
2249   if (SrcClass == cFP) {
2250     // Change the floating point control register to use "round towards zero"
2251     // mode when truncating to an integer value.
2252     //
2253     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
2254     addFrameReference(BMI(BB, IP, X86::FNSTCWm16, 4), CWFrameIdx);
2255
2256     // Load the old value of the high byte of the control word...
2257     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
2258     addFrameReference(BMI(BB, IP, X86::MOVrm8, 4, HighPartOfCW), CWFrameIdx, 1);
2259
2260     // Set the high part to be round to zero...
2261     addFrameReference(BMI(BB, IP, X86::MOVmi8, 5), CWFrameIdx, 1).addZImm(12);
2262
2263     // Reload the modified control word now...
2264     addFrameReference(BMI(BB, IP, X86::FLDCWm16, 4), CWFrameIdx);
2265
2266     // Restore the memory image of control word to original value
2267     addFrameReference(BMI(BB, IP, X86::MOVmr8, 5),
2268                       CWFrameIdx, 1).addReg(HighPartOfCW);
2269
2270     // We don't have the facilities for directly storing byte sized data to
2271     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
2272     // larger classes because we only have signed FP stores.
2273     unsigned StoreClass  = DestClass;
2274     const Type *StoreTy  = DestTy;
2275     if (StoreClass == cByte || DestTy->isUnsigned())
2276       switch (StoreClass) {
2277       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
2278       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
2279       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
2280       // The following treatment of cLong may not be perfectly right,
2281       // but it survives chains of casts of the form
2282       // double->ulong->double.
2283       case cLong:  StoreTy = Type::LongTy;  StoreClass = cLong;  break;
2284       default: assert(0 && "Unknown store class!");
2285       }
2286
2287     // Spill the integer to memory and reload it from there...
2288     int FrameIdx =
2289       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
2290
2291     static const unsigned Op1[] =
2292       { 0, X86::FISTr16, X86::FISTr32, 0, X86::FISTPr64 };
2293     addFrameReference(BMI(BB, IP, Op1[StoreClass], 5), FrameIdx).addReg(SrcReg);
2294
2295     if (DestClass == cLong) {
2296       addFrameReference(BMI(BB, IP, X86::MOVrm32, 4, DestReg), FrameIdx);
2297       addFrameReference(BMI(BB, IP, X86::MOVrm32, 4, DestReg+1), FrameIdx, 4);
2298     } else {
2299       static const unsigned Op2[] = { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32 };
2300       addFrameReference(BMI(BB, IP, Op2[DestClass], 4, DestReg), FrameIdx);
2301     }
2302
2303     // Reload the original control word now...
2304     addFrameReference(BMI(BB, IP, X86::FLDCWm16, 4), CWFrameIdx);
2305     return;
2306   }
2307
2308   // Anything we haven't handled already, we can't (yet) handle at all.
2309   assert(0 && "Unhandled cast instruction!");
2310   abort();
2311 }
2312
2313 /// visitVANextInst - Implement the va_next instruction...
2314 ///
2315 void ISel::visitVANextInst(VANextInst &I) {
2316   unsigned VAList = getReg(I.getOperand(0));
2317   unsigned DestReg = getReg(I);
2318
2319   unsigned Size;
2320   switch (I.getArgType()->getPrimitiveID()) {
2321   default:
2322     std::cerr << I;
2323     assert(0 && "Error: bad type for va_next instruction!");
2324     return;
2325   case Type::PointerTyID:
2326   case Type::UIntTyID:
2327   case Type::IntTyID:
2328     Size = 4;
2329     break;
2330   case Type::ULongTyID:
2331   case Type::LongTyID:
2332   case Type::DoubleTyID:
2333     Size = 8;
2334     break;
2335   }
2336
2337   // Increment the VAList pointer...
2338   BuildMI(BB, X86::ADDri32, 2, DestReg).addReg(VAList).addZImm(Size);
2339 }
2340
2341 void ISel::visitVAArgInst(VAArgInst &I) {
2342   unsigned VAList = getReg(I.getOperand(0));
2343   unsigned DestReg = getReg(I);
2344
2345   switch (I.getType()->getPrimitiveID()) {
2346   default:
2347     std::cerr << I;
2348     assert(0 && "Error: bad type for va_next instruction!");
2349     return;
2350   case Type::PointerTyID:
2351   case Type::UIntTyID:
2352   case Type::IntTyID:
2353     addDirectMem(BuildMI(BB, X86::MOVrm32, 4, DestReg), VAList);
2354     break;
2355   case Type::ULongTyID:
2356   case Type::LongTyID:
2357     addDirectMem(BuildMI(BB, X86::MOVrm32, 4, DestReg), VAList);
2358     addRegOffset(BuildMI(BB, X86::MOVrm32, 4, DestReg+1), VAList, 4);
2359     break;
2360   case Type::DoubleTyID:
2361     addDirectMem(BuildMI(BB, X86::FLDr64, 4, DestReg), VAList);
2362     break;
2363   }
2364 }
2365
2366
2367 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
2368   // If this GEP instruction will be folded into all of its users, we don't need
2369   // to explicitly calculate it!
2370   unsigned A, B, C, D;
2371   if (isGEPFoldable(0, I.getOperand(0), I.op_begin()+1, I.op_end(), A,B,C,D)) {
2372     // Check all of the users of the instruction to see if they are loads and
2373     // stores.
2374     bool AllWillFold = true;
2375     for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI)
2376       if (cast<Instruction>(*UI)->getOpcode() != Instruction::Load)
2377         if (cast<Instruction>(*UI)->getOpcode() != Instruction::Store ||
2378             cast<Instruction>(*UI)->getOperand(0) == &I) {
2379           AllWillFold = false;
2380           break;
2381         }
2382
2383     // If the instruction is foldable, and will be folded into all users, don't
2384     // emit it!
2385     if (AllWillFold) return;
2386   }
2387
2388   unsigned outputReg = getReg(I);
2389   emitGEPOperation(BB, BB->end(), I.getOperand(0),
2390                    I.op_begin()+1, I.op_end(), outputReg);
2391 }
2392
2393 /// getGEPIndex - Inspect the getelementptr operands specified with GEPOps and
2394 /// GEPTypes (the derived types being stepped through at each level).  On return
2395 /// from this function, if some indexes of the instruction are representable as
2396 /// an X86 lea instruction, the machine operands are put into the Ops
2397 /// instruction and the consumed indexes are poped from the GEPOps/GEPTypes
2398 /// lists.  Otherwise, GEPOps.size() is returned.  If this returns a an
2399 /// addressing mode that only partially consumes the input, the BaseReg input of
2400 /// the addressing mode must be left free.
2401 ///
2402 /// Note that there is one fewer entry in GEPTypes than there is in GEPOps.
2403 ///
2404 void ISel::getGEPIndex(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
2405                        std::vector<Value*> &GEPOps,
2406                        std::vector<const Type*> &GEPTypes, unsigned &BaseReg,
2407                        unsigned &Scale, unsigned &IndexReg, unsigned &Disp) {
2408   const TargetData &TD = TM.getTargetData();
2409
2410   // Clear out the state we are working with...
2411   BaseReg = 0;    // No base register
2412   Scale = 1;      // Unit scale
2413   IndexReg = 0;   // No index register
2414   Disp = 0;       // No displacement
2415
2416   // While there are GEP indexes that can be folded into the current address,
2417   // keep processing them.
2418   while (!GEPTypes.empty()) {
2419     if (const StructType *StTy = dyn_cast<StructType>(GEPTypes.back())) {
2420       // It's a struct access.  CUI is the index into the structure,
2421       // which names the field. This index must have unsigned type.
2422       const ConstantUInt *CUI = cast<ConstantUInt>(GEPOps.back());
2423
2424       // Use the TargetData structure to pick out what the layout of the
2425       // structure is in memory.  Since the structure index must be constant, we
2426       // can get its value and use it to find the right byte offset from the
2427       // StructLayout class's list of structure member offsets.
2428       Disp += TD.getStructLayout(StTy)->MemberOffsets[CUI->getValue()];
2429       GEPOps.pop_back();        // Consume a GEP operand
2430       GEPTypes.pop_back();
2431     } else {
2432       // It's an array or pointer access: [ArraySize x ElementType].
2433       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
2434       Value *idx = GEPOps.back();
2435
2436       // idx is the index into the array.  Unlike with structure
2437       // indices, we may not know its actual value at code-generation
2438       // time.
2439       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
2440
2441       // If idx is a constant, fold it into the offset.
2442       unsigned TypeSize = TD.getTypeSize(SqTy->getElementType());
2443       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
2444         Disp += TypeSize*CSI->getValue();
2445       } else {
2446         // If the index reg is already taken, we can't handle this index.
2447         if (IndexReg) return;
2448
2449         // If this is a size that we can handle, then add the index as
2450         switch (TypeSize) {
2451         case 1: case 2: case 4: case 8:
2452           // These are all acceptable scales on X86.
2453           Scale = TypeSize;
2454           break;
2455         default:
2456           // Otherwise, we can't handle this scale
2457           return;
2458         }
2459
2460         if (CastInst *CI = dyn_cast<CastInst>(idx))
2461           if (CI->getOperand(0)->getType() == Type::IntTy ||
2462               CI->getOperand(0)->getType() == Type::UIntTy)
2463             idx = CI->getOperand(0);
2464
2465         IndexReg = MBB ? getReg(idx, MBB, IP) : 1;
2466       }
2467
2468       GEPOps.pop_back();        // Consume a GEP operand
2469       GEPTypes.pop_back();
2470     }
2471   }
2472
2473   // GEPTypes is empty, which means we have a single operand left.  See if we
2474   // can set it as the base register.
2475   //
2476   // FIXME: When addressing modes are more powerful/correct, we could load
2477   // global addresses directly as 32-bit immediates.
2478   assert(BaseReg == 0);
2479   BaseReg = MBB ? getReg(GEPOps[0], MBB, IP) : 1;
2480   GEPOps.pop_back();        // Consume the last GEP operand
2481 }
2482
2483
2484 /// isGEPFoldable - Return true if the specified GEP can be completely
2485 /// folded into the addressing mode of a load/store or lea instruction.
2486 bool ISel::isGEPFoldable(MachineBasicBlock *MBB,
2487                          Value *Src, User::op_iterator IdxBegin,
2488                          User::op_iterator IdxEnd, unsigned &BaseReg,
2489                          unsigned &Scale, unsigned &IndexReg, unsigned &Disp) {
2490   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Src))
2491     Src = CPR->getValue();
2492
2493   std::vector<Value*> GEPOps;
2494   GEPOps.resize(IdxEnd-IdxBegin+1);
2495   GEPOps[0] = Src;
2496   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
2497
2498   std::vector<const Type*> GEPTypes;
2499   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
2500                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
2501
2502   MachineBasicBlock::iterator IP;
2503   if (MBB) IP = MBB->end();
2504   getGEPIndex(MBB, IP, GEPOps, GEPTypes, BaseReg, Scale, IndexReg, Disp);
2505
2506   // We can fold it away iff the getGEPIndex call eliminated all operands.
2507   return GEPOps.empty();
2508 }
2509
2510 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
2511                             MachineBasicBlock::iterator IP,
2512                             Value *Src, User::op_iterator IdxBegin,
2513                             User::op_iterator IdxEnd, unsigned TargetReg) {
2514   const TargetData &TD = TM.getTargetData();
2515   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Src))
2516     Src = CPR->getValue();
2517
2518   std::vector<Value*> GEPOps;
2519   GEPOps.resize(IdxEnd-IdxBegin+1);
2520   GEPOps[0] = Src;
2521   std::copy(IdxBegin, IdxEnd, GEPOps.begin()+1);
2522
2523   std::vector<const Type*> GEPTypes;
2524   GEPTypes.assign(gep_type_begin(Src->getType(), IdxBegin, IdxEnd),
2525                   gep_type_end(Src->getType(), IdxBegin, IdxEnd));
2526
2527   // Keep emitting instructions until we consume the entire GEP instruction.
2528   while (!GEPOps.empty()) {
2529     unsigned OldSize = GEPOps.size();
2530     unsigned BaseReg, Scale, IndexReg, Disp;
2531     getGEPIndex(MBB, IP, GEPOps, GEPTypes, BaseReg, Scale, IndexReg, Disp);
2532
2533     if (GEPOps.size() != OldSize) {
2534       // getGEPIndex consumed some of the input.  Build an LEA instruction here.
2535       unsigned NextTarget = 0;
2536       if (!GEPOps.empty()) {
2537         assert(BaseReg == 0 &&
2538            "getGEPIndex should have left the base register open for chaining!");
2539         NextTarget = BaseReg = makeAnotherReg(Type::UIntTy);
2540       }
2541
2542       if (IndexReg == 0 && Disp == 0)
2543         BMI(MBB, IP, X86::MOVrr32, 1, TargetReg).addReg(BaseReg);
2544       else
2545         addFullAddress(BMI(MBB, IP, X86::LEAr32, 5, TargetReg),
2546                        BaseReg, Scale, IndexReg, Disp);
2547       --IP;
2548       TargetReg = NextTarget;
2549     } else if (GEPTypes.empty()) {
2550       // The getGEPIndex operation didn't want to build an LEA.  Check to see if
2551       // all operands are consumed but the base pointer.  If so, just load it
2552       // into the register.
2553       if (GlobalValue *GV = dyn_cast<GlobalValue>(GEPOps[0])) {
2554         BMI(MBB, IP, X86::MOVri32, 1, TargetReg).addGlobalAddress(GV);
2555       } else {
2556         unsigned BaseReg = getReg(GEPOps[0], MBB, IP);
2557         BMI(MBB, IP, X86::MOVrr32, 1, TargetReg).addReg(BaseReg);
2558       }
2559       break;                // we are now done
2560
2561     } else {
2562       // It's an array or pointer access: [ArraySize x ElementType].
2563       const SequentialType *SqTy = cast<SequentialType>(GEPTypes.back());
2564       Value *idx = GEPOps.back();
2565       GEPOps.pop_back();        // Consume a GEP operand
2566       GEPTypes.pop_back();
2567
2568       // idx is the index into the array.  Unlike with structure
2569       // indices, we may not know its actual value at code-generation
2570       // time.
2571       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
2572
2573       // Most GEP instructions use a [cast (int/uint) to LongTy] as their
2574       // operand on X86.  Handle this case directly now...
2575       if (CastInst *CI = dyn_cast<CastInst>(idx))
2576         if (CI->getOperand(0)->getType() == Type::IntTy ||
2577             CI->getOperand(0)->getType() == Type::UIntTy)
2578           idx = CI->getOperand(0);
2579
2580       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
2581       // must find the size of the pointed-to type (Not coincidentally, the next
2582       // type is the type of the elements in the array).
2583       const Type *ElTy = SqTy->getElementType();
2584       unsigned elementSize = TD.getTypeSize(ElTy);
2585
2586       // If idxReg is a constant, we don't need to perform the multiply!
2587       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
2588         if (!CSI->isNullValue()) {
2589           unsigned Offset = elementSize*CSI->getValue();
2590           unsigned Reg = makeAnotherReg(Type::UIntTy);
2591           BMI(MBB, IP, X86::ADDri32, 2, TargetReg).addReg(Reg).addZImm(Offset);
2592           --IP;            // Insert the next instruction before this one.
2593           TargetReg = Reg; // Codegen the rest of the GEP into this
2594         }
2595       } else if (elementSize == 1) {
2596         // If the element size is 1, we don't have to multiply, just add
2597         unsigned idxReg = getReg(idx, MBB, IP);
2598         unsigned Reg = makeAnotherReg(Type::UIntTy);
2599         BMI(MBB, IP, X86::ADDrr32, 2, TargetReg).addReg(Reg).addReg(idxReg);
2600         --IP;            // Insert the next instruction before this one.
2601         TargetReg = Reg; // Codegen the rest of the GEP into this
2602       } else {
2603         unsigned idxReg = getReg(idx, MBB, IP);
2604         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
2605
2606         // Make sure we can back the iterator up to point to the first
2607         // instruction emitted.
2608         MachineBasicBlock::iterator BeforeIt = IP;
2609         if (IP == MBB->begin())
2610           BeforeIt = MBB->end();
2611         else
2612           --BeforeIt;
2613         doMultiplyConst(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSize);
2614
2615         // Emit an ADD to add OffsetReg to the basePtr.
2616         unsigned Reg = makeAnotherReg(Type::UIntTy);
2617         BMI(MBB, IP, X86::ADDrr32, 2, TargetReg).addReg(Reg).addReg(OffsetReg);
2618
2619         // Step to the first instruction of the multiply.
2620         if (BeforeIt == MBB->end())
2621           IP = MBB->begin();
2622         else
2623           IP = ++BeforeIt;
2624
2625         TargetReg = Reg; // Codegen the rest of the GEP into this
2626       }
2627     }
2628   }
2629 }
2630
2631
2632 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
2633 /// frame manager, otherwise do it the hard way.
2634 ///
2635 void ISel::visitAllocaInst(AllocaInst &I) {
2636   // Find the data size of the alloca inst's getAllocatedType.
2637   const Type *Ty = I.getAllocatedType();
2638   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
2639
2640   // If this is a fixed size alloca in the entry block for the function,
2641   // statically stack allocate the space.
2642   //
2643   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getArraySize())) {
2644     if (I.getParent() == I.getParent()->getParent()->begin()) {
2645       TySize *= CUI->getValue();   // Get total allocated size...
2646       unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
2647
2648       // Create a new stack object using the frame manager...
2649       int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
2650       addFrameReference(BuildMI(BB, X86::LEAr32, 5, getReg(I)), FrameIdx);
2651       return;
2652     }
2653   }
2654
2655   // Create a register to hold the temporary result of multiplying the type size
2656   // constant by the variable amount.
2657   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
2658   unsigned SrcReg1 = getReg(I.getArraySize());
2659
2660   // TotalSizeReg = mul <numelements>, <TypeSize>
2661   MachineBasicBlock::iterator MBBI = BB->end();
2662   doMultiplyConst(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, TySize);
2663
2664   // AddedSize = add <TotalSizeReg>, 15
2665   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
2666   BuildMI(BB, X86::ADDri32, 2, AddedSizeReg).addReg(TotalSizeReg).addZImm(15);
2667
2668   // AlignedSize = and <AddedSize>, ~15
2669   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
2670   BuildMI(BB, X86::ANDri32, 2, AlignedSize).addReg(AddedSizeReg).addZImm(~15);
2671
2672   // Subtract size from stack pointer, thereby allocating some space.
2673   BuildMI(BB, X86::SUBrr32, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
2674
2675   // Put a pointer to the space into the result register, by copying
2676   // the stack pointer.
2677   BuildMI(BB, X86::MOVrr32, 1, getReg(I)).addReg(X86::ESP);
2678
2679   // Inform the Frame Information that we have just allocated a variable-sized
2680   // object.
2681   F->getFrameInfo()->CreateVariableSizedObject();
2682 }
2683
2684 /// visitMallocInst - Malloc instructions are code generated into direct calls
2685 /// to the library malloc.
2686 ///
2687 void ISel::visitMallocInst(MallocInst &I) {
2688   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
2689   unsigned Arg;
2690
2691   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
2692     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
2693   } else {
2694     Arg = makeAnotherReg(Type::UIntTy);
2695     unsigned Op0Reg = getReg(I.getOperand(0));
2696     MachineBasicBlock::iterator MBBI = BB->end();
2697     doMultiplyConst(BB, MBBI, Arg, Type::UIntTy, Op0Reg, AllocSize);
2698   }
2699
2700   std::vector<ValueRecord> Args;
2701   Args.push_back(ValueRecord(Arg, Type::UIntTy));
2702   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2703                                   1).addExternalSymbol("malloc", true);
2704   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
2705 }
2706
2707
2708 /// visitFreeInst - Free instructions are code gen'd to call the free libc
2709 /// function.
2710 ///
2711 void ISel::visitFreeInst(FreeInst &I) {
2712   std::vector<ValueRecord> Args;
2713   Args.push_back(ValueRecord(I.getOperand(0)));
2714   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
2715                                   1).addExternalSymbol("free", true);
2716   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
2717 }
2718
2719 /// createX86SimpleInstructionSelector - This pass converts an LLVM function
2720 /// into a machine code representation is a very simple peep-hole fashion.  The
2721 /// generated code sucks but the implementation is nice and simple.
2722 ///
2723 FunctionPass *llvm::createX86SimpleInstructionSelector(TargetMachine &TM) {
2724   return new ISel(TM);
2725 }