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