lib/Target/X86/InstSelectSimple.cpp

   1 //===-- InstSelectSimple.cpp - A simple instruction selector for x86 ------===//
   2 //
   3 // This file defines a simple peephole instruction selector for the x86 target
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "X86.h"
   8 #include "X86InstrInfo.h"
   9 #include "X86InstrBuilder.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/iTerminators.h"
  12 #include "llvm/iOperators.h"
  13 #include "llvm/iOther.h"
  14 #include "llvm/iPHINode.h"
  15 #include "llvm/iMemory.h"
  16 #include "llvm/Type.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/SSARegMap.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineConstantPool.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Support/InstVisitor.h"
  27 #include "llvm/Target/MRegisterInfo.h"
  28 #include <map>
  29
  30 /// BMI - A special BuildMI variant that takes an iterator to insert the
  31 /// instruction at as well as a basic block.
  32 /// this is the version for when you have a destination register in mind.
  33 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  34                                       MachineBasicBlock::iterator &I,
  35                                       MachineOpCode Opcode,
  36                                       unsigned NumOperands,
  37                                       unsigned DestReg) {
  38   assert(I >= MBB->begin() && I <= MBB->end() && "Bad iterator!");
  39   MachineInstr *MI = new MachineInstr(Opcode, NumOperands+1, true, true);
  40   I = MBB->insert(I, MI)+1;
  41   return MachineInstrBuilder(MI).addReg(DestReg, MOTy::Def);
  42 }
  43
  44 /// BMI - A special BuildMI variant that takes an iterator to insert the
  45 /// instruction at as well as a basic block.
  46 inline static MachineInstrBuilder BMI(MachineBasicBlock *MBB,
  47                                       MachineBasicBlock::iterator &I,
  48                                       MachineOpCode Opcode,
  49                                       unsigned NumOperands) {
  50   assert(I > MBB->begin() && I <= MBB->end() && "Bad iterator!");
  51   MachineInstr *MI = new MachineInstr(Opcode, NumOperands, true, true);
  52   I = MBB->insert(I, MI)+1;
  53   return MachineInstrBuilder(MI);
  54 }
  55
  56
  57 namespace {
  58   struct ISel : public FunctionPass, InstVisitor<ISel> {
  59     TargetMachine &TM;
  60     MachineFunction *F;                    // The function we are compiling into
  61     MachineBasicBlock *BB;                 // The current MBB we are compiling
  62
  63     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  64
  65     // MBBMap - Mapping between LLVM BB -> Machine BB
  66     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  67
  68     ISel(TargetMachine &tm) : TM(tm), F(0), BB(0) {}
  69
  70     /// runOnFunction - Top level implementation of instruction selection for
  71     /// the entire function.
  72     ///
  73     bool runOnFunction(Function &Fn) {
  74       F = &MachineFunction::construct(&Fn, TM);
  75
  76       // Create all of the machine basic blocks for the function...
  77       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  78         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
  79
  80       BB = &F->front();
  81       LoadArgumentsToVirtualRegs(Fn);
  82
  83       // Instruction select everything except PHI nodes
  84       visit(Fn);
  85
  86       // Select the PHI nodes
  87       SelectPHINodes();
  88
  89       RegMap.clear();
  90       MBBMap.clear();
  91       F = 0;
  92       return false;  // We never modify the LLVM itself.
  93     }
  94
  95     virtual const char *getPassName() const {
  96       return "X86 Simple Instruction Selection";
  97     }
  98
  99     /// visitBasicBlock - This method is called when we are visiting a new basic
 100     /// block.  This simply creates a new MachineBasicBlock to emit code into
 101     /// and adds it to the current MachineFunction.  Subsequent visit* for
 102     /// instructions will be invoked for all instructions in the basic block.
 103     ///
 104     void visitBasicBlock(BasicBlock &LLVM_BB) {
 105       BB = MBBMap[&LLVM_BB];
 106     }
 107
 108     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 109     /// from the stack into virtual registers.
 110     ///
 111     void LoadArgumentsToVirtualRegs(Function &F);
 112
 113     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 114     /// because we have to generate our sources into the source basic blocks,
 115     /// not the current one.
 116     ///
 117     void SelectPHINodes();
 118
 119     // Visitation methods for various instructions.  These methods simply emit
 120     // fixed X86 code for each instruction.
 121     //
 122
 123     // Control flow operators
 124     void visitReturnInst(ReturnInst &RI);
 125     void visitBranchInst(BranchInst &BI);
 126
 127     struct ValueRecord {
 128       unsigned Reg;
 129       const Type *Ty;
 130       ValueRecord(unsigned R, const Type *T) : Reg(R), Ty(T) {}
 131     };
 132     void doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 133                 const std::vector<ValueRecord> &Args);
 134     void visitCallInst(CallInst &I);
 135
 136     // Arithmetic operators
 137     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 138     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 139     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 140     void doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI,
 141                     unsigned DestReg, const Type *DestTy,
 142                     unsigned Op0Reg, unsigned Op1Reg);
 143     void visitMul(BinaryOperator &B);
 144
 145     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 146     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 147     void visitDivRem(BinaryOperator &B);
 148
 149     // Bitwise operators
 150     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 151     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 152     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 153
 154     // Comparison operators...
 155     void visitSetCondInst(SetCondInst &I);
 156     bool EmitComparisonGetSignedness(unsigned OpNum, Value *Op0, Value *Op1);
 157
 158     // Memory Instructions
 159     MachineInstr *doFPLoad(MachineBasicBlock *MBB,
 160                            MachineBasicBlock::iterator &MBBI,
 161                            const Type *Ty, unsigned DestReg);
 162     void visitLoadInst(LoadInst &I);
 163     void doFPStore(const Type *Ty, unsigned DestAddrReg, unsigned SrcReg);
 164     void visitStoreInst(StoreInst &I);
 165     void visitGetElementPtrInst(GetElementPtrInst &I);
 166     void visitAllocaInst(AllocaInst &I);
 167     void visitMallocInst(MallocInst &I);
 168     void visitFreeInst(FreeInst &I);
 169
 170     // Other operators
 171     void visitShiftInst(ShiftInst &I);
 172     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 173     void visitCastInst(CastInst &I);
 174
 175     void visitInstruction(Instruction &I) {
 176       std::cerr << "Cannot instruction select: " << I;
 177       abort();
 178     }
 179
 180     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 181     ///
 182     void promote32(unsigned targetReg, const ValueRecord &VR);
 183
 184     /// EmitByteSwap - Byteswap SrcReg into DestReg.
 185     ///
 186     void EmitByteSwap(unsigned DestReg, unsigned SrcReg, unsigned Class);
 187
 188     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 189     /// constant expression GEP support.
 190     ///
 191     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator&IP,
 192                           Value *Src, User::op_iterator IdxBegin,
 193                           User::op_iterator IdxEnd, unsigned TargetReg);
 194
 195     /// copyConstantToRegister - Output the instructions required to put the
 196     /// specified constant into the specified register.
 197     ///
 198     void copyConstantToRegister(MachineBasicBlock *MBB,
 199                                 MachineBasicBlock::iterator &MBBI,
 200                                 Constant *C, unsigned Reg);
 201
 202     /// makeAnotherReg - This method returns the next register number we haven't
 203     /// yet used.
 204     ///
 205     /// Long values are handled somewhat specially.  They are always allocated
 206     /// as pairs of 32 bit integer values.  The register number returned is the
 207     /// lower 32 bits of the long value, and the regNum+1 is the upper 32 bits
 208     /// of the long value.
 209     ///
 210     unsigned makeAnotherReg(const Type *Ty) {
 211       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 212         const TargetRegisterClass *RC =
 213           TM.getRegisterInfo()->getRegClassForType(Type::IntTy);
 214         // Create the lower part
 215         F->getSSARegMap()->createVirtualRegister(RC);
 216         // Create the upper part.
 217         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 218       }
 219
 220       // Add the mapping of regnumber => reg class to MachineFunction
 221       const TargetRegisterClass *RC =
 222         TM.getRegisterInfo()->getRegClassForType(Ty);
 223       return F->getSSARegMap()->createVirtualRegister(RC);
 224     }
 225
 226     /// getReg - This method turns an LLVM value into a register number.  This
 227     /// is guaranteed to produce the same register number for a particular value
 228     /// every time it is queried.
 229     ///
 230     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 231     unsigned getReg(Value *V) {
 232       // Just append to the end of the current bb.
 233       MachineBasicBlock::iterator It = BB->end();
 234       return getReg(V, BB, It);
 235     }
 236     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 237                     MachineBasicBlock::iterator &IPt) {
 238       unsigned &Reg = RegMap[V];
 239       if (Reg == 0) {
 240         Reg = makeAnotherReg(V->getType());
 241         RegMap[V] = Reg;
 242       }
 243
 244       // If this operand is a constant, emit the code to copy the constant into
 245       // the register here...
 246       //
 247       if (Constant *C = dyn_cast<Constant>(V)) {
 248         copyConstantToRegister(MBB, IPt, C, Reg);
 249         RegMap.erase(V);  // Assign a new name to this constant if ref'd again
 250       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 251         // Move the address of the global into the register
 252         BMI(MBB, IPt, X86::MOVir32, 1, Reg).addGlobalAddress(GV);
 253         RegMap.erase(V);  // Assign a new name to this address if ref'd again
 254       }
 255
 256       return Reg;
 257     }
 258   };
 259 }
 260
 261 /// TypeClass - Used by the X86 backend to group LLVM types by their basic X86
 262 /// Representation.
 263 ///
 264 enum TypeClass {
 265   cByte, cShort, cInt, cFP, cLong
 266 };
 267
 268 /// getClass - Turn a primitive type into a "class" number which is based on the
 269 /// size of the type, and whether or not it is floating point.
 270 ///
 271 static inline TypeClass getClass(const Type *Ty) {
 272   switch (Ty->getPrimitiveID()) {
 273   case Type::SByteTyID:
 274   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
 275   case Type::ShortTyID:
 276   case Type::UShortTyID:  return cShort;     // Short operands are class #1
 277   case Type::IntTyID:
 278   case Type::UIntTyID:
 279   case Type::PointerTyID: return cInt;       // Int's and pointers are class #2
 280
 281   case Type::FloatTyID:
 282   case Type::DoubleTyID:  return cFP;        // Floating Point is #3
 283
 284   case Type::LongTyID:
 285   case Type::ULongTyID:   return cLong;      // Longs are class #4
 286   default:
 287     assert(0 && "Invalid type to getClass!");
 288     return cByte;  // not reached
 289   }
 290 }
 291
 292 // getClassB - Just like getClass, but treat boolean values as bytes.
 293 static inline TypeClass getClassB(const Type *Ty) {
 294   if (Ty == Type::BoolTy) return cByte;
 295   return getClass(Ty);
 296 }
 297
 298
 299 /// copyConstantToRegister - Output the instructions required to put the
 300 /// specified constant into the specified register.
 301 ///
 302 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 303                                   MachineBasicBlock::iterator &IP,
 304                                   Constant *C, unsigned R) {
 305   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 306     if (CE->getOpcode() == Instruction::GetElementPtr) {
 307       emitGEPOperation(MBB, IP, CE->getOperand(0),
 308                        CE->op_begin()+1, CE->op_end(), R);
 309       return;
 310     } else if (CE->getOpcode() == Instruction::Cast &&
 311                isa<PointerType>(CE->getType()) &&
 312                isa<PointerType>(CE->getOperand(0)->getType())) {
 313       copyConstantToRegister(MBB, IP, cast<Constant>(CE->getOperand(0)), R);
 314       return;
 315     }
 316
 317     std::cerr << "Offending expr: " << C << "\n";
 318     assert(0 && "Constant expressions not yet handled!\n");
 319   }
 320
 321   if (C->getType()->isIntegral()) {
 322     unsigned Class = getClassB(C->getType());
 323
 324     if (Class == cLong) {
 325       // Copy the value into the register pair.
 326       uint64_t Val;
 327       if (C->getType()->isSigned())
 328         Val = cast<ConstantSInt>(C)->getValue();
 329       else
 330         Val = cast<ConstantUInt>(C)->getValue();
 331
 332       BMI(MBB, IP, X86::MOVir32, 1, R).addZImm(Val & 0xFFFFFFFF);
 333       BMI(MBB, IP, X86::MOVir32, 1, R+1).addZImm(Val >> 32);
 334       return;
 335     }
 336
 337     assert(Class <= cInt && "Type not handled yet!");
 338
 339     static const unsigned IntegralOpcodeTab[] = {
 340       X86::MOVir8, X86::MOVir16, X86::MOVir32
 341     };
 342
 343     if (C->getType() == Type::BoolTy) {
 344       BMI(MBB, IP, X86::MOVir8, 1, R).addZImm(C == ConstantBool::True);
 345     } else if (C->getType()->isSigned()) {
 346       ConstantSInt *CSI = cast<ConstantSInt>(C);
 347       BMI(MBB, IP, IntegralOpcodeTab[Class], 1, R).addZImm(CSI->getValue());
 348     } else {
 349       ConstantUInt *CUI = cast<ConstantUInt>(C);
 350       BMI(MBB, IP, IntegralOpcodeTab[Class], 1, R).addZImm(CUI->getValue());
 351     }
 352   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 353     double Value = CFP->getValue();
 354     if (Value == +0.0)
 355       BMI(MBB, IP, X86::FLD0, 0, R);
 356     else if (Value == +1.0)
 357       BMI(MBB, IP, X86::FLD1, 0, R);
 358     else {
 359       // Otherwise we need to spill the constant to memory...
 360       MachineConstantPool *CP = F->getConstantPool();
 361       unsigned CPI = CP->getConstantPoolIndex(CFP);
 362       addConstantPoolReference(doFPLoad(MBB, IP, CFP->getType(), R), CPI);
 363     }
 364
 365   } else if (isa<ConstantPointerNull>(C)) {
 366     // Copy zero (null pointer) to the register.
 367     BMI(MBB, IP, X86::MOVir32, 1, R).addZImm(0);
 368   } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 369     unsigned SrcReg = getReg(CPR->getValue(), MBB, IP);
 370     BMI(MBB, IP, X86::MOVrr32, 1, R).addReg(SrcReg);
 371   } else {
 372     std::cerr << "Offending constant: " << C << "\n";
 373     assert(0 && "Type not handled yet!");
 374   }
 375 }
 376
 377 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 378 /// the stack into virtual registers.
 379 ///
 380 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 381   // Emit instructions to load the arguments...  On entry to a function on the
 382   // X86, the stack frame looks like this:
 383   //
 384   // [ESP] -- return address
 385   // [ESP + 4] -- first argument (leftmost lexically)
 386   // [ESP + 8] -- second argument, if first argument is four bytes in size
 387   //    ...
 388   //
 389   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 390   MachineFrameInfo *MFI = F->getFrameInfo();
 391
 392   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 393     unsigned Reg = getReg(*I);
 394
 395     int FI;          // Frame object index
 396     switch (getClassB(I->getType())) {
 397     case cByte:
 398       FI = MFI->CreateFixedObject(1, ArgOffset);
 399       addFrameReference(BuildMI(BB, X86::MOVmr8, 4, Reg), FI);
 400       break;
 401     case cShort:
 402       FI = MFI->CreateFixedObject(2, ArgOffset);
 403       addFrameReference(BuildMI(BB, X86::MOVmr16, 4, Reg), FI);
 404       break;
 405     case cInt:
 406       FI = MFI->CreateFixedObject(4, ArgOffset);
 407       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg), FI);
 408       break;
 409     case cLong:
 410       FI = MFI->CreateFixedObject(8, ArgOffset);
 411       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg), FI);
 412       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, Reg+1), FI, 4);
 413       ArgOffset += 4;   // longs require 4 additional bytes
 414       break;
 415     case cFP:
 416       unsigned Opcode;
 417       if (I->getType() == Type::FloatTy) {
 418         Opcode = X86::FLDr32;
 419         FI = MFI->CreateFixedObject(4, ArgOffset);
 420       } else {
 421         Opcode = X86::FLDr64;
 422         FI = MFI->CreateFixedObject(8, ArgOffset);
 423         ArgOffset += 4;   // doubles require 4 additional bytes
 424       }
 425       addFrameReference(BuildMI(BB, Opcode, 4, Reg), FI);
 426       break;
 427     default:
 428       assert(0 && "Unhandled argument type!");
 429     }
 430     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 431   }
 432 }
 433
 434
 435 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 436 /// because we have to generate our sources into the source basic blocks, not
 437 /// the current one.
 438 ///
 439 void ISel::SelectPHINodes() {
 440   const TargetInstrInfo &TII = TM.getInstrInfo();
 441   const Function &LF = *F->getFunction();  // The LLVM function...
 442   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 443     const BasicBlock *BB = I;
 444     MachineBasicBlock *MBB = MBBMap[I];
 445
 446     // Loop over all of the PHI nodes in the LLVM basic block...
 447     unsigned NumPHIs = 0;
 448     for (BasicBlock::const_iterator I = BB->begin();
 449          PHINode *PN = (PHINode*)dyn_cast<PHINode>(&*I); ++I) {
 450
 451       // Create a new machine instr PHI node, and insert it.
 452       unsigned PHIReg = getReg(*PN);
 453       MachineInstr *PhiMI = BuildMI(X86::PHI, PN->getNumOperands(), PHIReg);
 454       MBB->insert(MBB->begin()+NumPHIs++, PhiMI);
 455
 456       MachineInstr *LongPhiMI = 0;
 457       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy) {
 458         LongPhiMI = BuildMI(X86::PHI, PN->getNumOperands(), PHIReg+1);
 459         MBB->insert(MBB->begin()+NumPHIs++, LongPhiMI);
 460       }
 461
 462       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 463         MachineBasicBlock *PredMBB = MBBMap[PN->getIncomingBlock(i)];
 464
 465         // Get the incoming value into a virtual register.  If it is not already
 466         // available in a virtual register, insert the computation code into
 467         // PredMBB
 468         //
 469         MachineBasicBlock::iterator PI = PredMBB->end();
 470         while (PI != PredMBB->begin() &&
 471                TII.isTerminatorInstr((*(PI-1))->getOpcode()))
 472           --PI;
 473         unsigned ValReg = getReg(PN->getIncomingValue(i), PredMBB, PI);
 474         PhiMI->addRegOperand(ValReg);
 475         PhiMI->addMachineBasicBlockOperand(PredMBB);
 476         if (LongPhiMI) {
 477           LongPhiMI->addRegOperand(ValReg+1);
 478           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 479         }
 480       }
 481     }
 482   }
 483 }
 484
 485 // canFoldSetCCIntoBranch - Return the setcc instruction if we can fold it into
 486 // the conditional branch instruction which is the only user of the cc
 487 // instruction.  This is the case if the conditional branch is the only user of
 488 // the setcc, and if the setcc is in the same basic block as the conditional
 489 // branch.  We also don't handle long arguments below, so we reject them here as
 490 // well.
 491 //
 492 static SetCondInst *canFoldSetCCIntoBranch(Value *V) {
 493   if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 494     if (SCI->use_size() == 1 && isa<BranchInst>(SCI->use_back()) &&
 495         SCI->getParent() == cast<BranchInst>(SCI->use_back())->getParent()) {
 496       const Type *Ty = SCI->getOperand(0)->getType();
 497       if (Ty != Type::LongTy && Ty != Type::ULongTy)
 498         return SCI;
 499     }
 500   return 0;
 501 }
 502
 503 // Return a fixed numbering for setcc instructions which does not depend on the
 504 // order of the opcodes.
 505 //
 506 static unsigned getSetCCNumber(unsigned Opcode) {
 507   switch(Opcode) {
 508   default: assert(0 && "Unknown setcc instruction!");
 509   case Instruction::SetEQ: return 0;
 510   case Instruction::SetNE: return 1;
 511   case Instruction::SetLT: return 2;
 512   case Instruction::SetGE: return 3;
 513   case Instruction::SetGT: return 4;
 514   case Instruction::SetLE: return 5;
 515   }
 516 }
 517
 518 // LLVM  -> X86 signed  X86 unsigned
 519 // -----    ----------  ------------
 520 // seteq -> sete        sete
 521 // setne -> setne       setne
 522 // setlt -> setl        setb
 523 // setge -> setge       setae
 524 // setgt -> setg        seta
 525 // setle -> setle       setbe
 526 static const unsigned SetCCOpcodeTab[2][6] = {
 527   {X86::SETEr, X86::SETNEr, X86::SETBr, X86::SETAEr, X86::SETAr, X86::SETBEr},
 528   {X86::SETEr, X86::SETNEr, X86::SETLr, X86::SETGEr, X86::SETGr, X86::SETLEr},
 529 };
 530
 531 bool ISel::EmitComparisonGetSignedness(unsigned OpNum, Value *Op0, Value *Op1) {
 532
 533   // The arguments are already supposed to be of the same type.
 534   const Type *CompTy = Op0->getType();
 535   bool isSigned = CompTy->isSigned();
 536   unsigned reg1 = getReg(Op0);
 537   unsigned reg2 = getReg(Op1);
 538
 539   unsigned Class = getClassB(CompTy);
 540   switch (Class) {
 541   default: assert(0 && "Unknown type class!");
 542     // Emit: cmp <var1>, <var2> (do the comparison).  We can
 543     // compare 8-bit with 8-bit, 16-bit with 16-bit, 32-bit with
 544     // 32-bit.
 545   case cByte:
 546     BuildMI(BB, X86::CMPrr8, 2).addReg(reg1).addReg(reg2);
 547     break;
 548   case cShort:
 549     BuildMI(BB, X86::CMPrr16, 2).addReg(reg1).addReg(reg2);
 550     break;
 551   case cInt:
 552     BuildMI(BB, X86::CMPrr32, 2).addReg(reg1).addReg(reg2);
 553     break;
 554   case cFP:
 555     BuildMI(BB, X86::FpUCOM, 2).addReg(reg1).addReg(reg2);
 556     BuildMI(BB, X86::FNSTSWr8, 0);
 557     BuildMI(BB, X86::SAHF, 1);
 558     isSigned = false;   // Compare with unsigned operators
 559     break;
 560
 561   case cLong:
 562     if (OpNum < 2) {    // seteq, setne
 563       unsigned LoTmp = makeAnotherReg(Type::IntTy);
 564       unsigned HiTmp = makeAnotherReg(Type::IntTy);
 565       unsigned FinalTmp = makeAnotherReg(Type::IntTy);
 566       BuildMI(BB, X86::XORrr32, 2, LoTmp).addReg(reg1).addReg(reg2);
 567       BuildMI(BB, X86::XORrr32, 2, HiTmp).addReg(reg1+1).addReg(reg2+1);
 568       BuildMI(BB, X86::ORrr32,  2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
 569       break;  // Allow the sete or setne to be generated from flags set by OR
 570     } else {
 571       // Emit a sequence of code which compares the high and low parts once
 572       // each, then uses a conditional move to handle the overflow case.  For
 573       // example, a setlt for long would generate code like this:
 574       //
 575       // AL = lo(op1) < lo(op2)   // Signedness depends on operands
 576       // BL = hi(op1) < hi(op2)   // Always unsigned comparison
 577       // dest = hi(op1) == hi(op2) ? AL : BL;
 578       //
 579
 580       // FIXME: This would be much better if we had hierarchical register
 581       // classes!  Until then, hardcode registers so that we can deal with their
 582       // aliases (because we don't have conditional byte moves).
 583       //
 584       BuildMI(BB, X86::CMPrr32, 2).addReg(reg1).addReg(reg2);
 585       BuildMI(BB, SetCCOpcodeTab[0][OpNum], 0, X86::AL);
 586       BuildMI(BB, X86::CMPrr32, 2).addReg(reg1+1).addReg(reg2+1);
 587       BuildMI(BB, SetCCOpcodeTab[isSigned][OpNum], 0, X86::BL);
 588       BuildMI(BB, X86::CMOVErr16, 2, X86::BX).addReg(X86::BX).addReg(X86::AX);
 589       // NOTE: visitSetCondInst knows that the value is dumped into the BL
 590       // register at this point for long values...
 591       return isSigned;
 592     }
 593   }
 594   return isSigned;
 595 }
 596
 597
 598 /// SetCC instructions - Here we just emit boilerplate code to set a byte-sized
 599 /// register, then move it to wherever the result should be.
 600 ///
 601 void ISel::visitSetCondInst(SetCondInst &I) {
 602   if (canFoldSetCCIntoBranch(&I)) return;  // Fold this into a branch...
 603
 604   unsigned OpNum = getSetCCNumber(I.getOpcode());
 605   unsigned DestReg = getReg(I);
 606   bool isSigned = EmitComparisonGetSignedness(OpNum, I.getOperand(0),
 607                                               I.getOperand(1));
 608
 609   if (getClassB(I.getOperand(0)->getType()) != cLong || OpNum < 2) {
 610     // Handle normal comparisons with a setcc instruction...
 611     BuildMI(BB, SetCCOpcodeTab[isSigned][OpNum], 0, DestReg);
 612   } else {
 613     // Handle long comparisons by copying the value which is already in BL into
 614     // the register we want...
 615     BuildMI(BB, X86::MOVrr8, 1, DestReg).addReg(X86::BL);
 616   }
 617 }
 618
 619 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
 620 /// operand, in the specified target register.
 621 void ISel::promote32(unsigned targetReg, const ValueRecord &VR) {
 622   bool isUnsigned = VR.Ty->isUnsigned();
 623   switch (getClassB(VR.Ty)) {
 624   case cByte:
 625     // Extend value into target register (8->32)
 626     if (isUnsigned)
 627       BuildMI(BB, X86::MOVZXr32r8, 1, targetReg).addReg(VR.Reg);
 628     else
 629       BuildMI(BB, X86::MOVSXr32r8, 1, targetReg).addReg(VR.Reg);
 630     break;
 631   case cShort:
 632     // Extend value into target register (16->32)
 633     if (isUnsigned)
 634       BuildMI(BB, X86::MOVZXr32r16, 1, targetReg).addReg(VR.Reg);
 635     else
 636       BuildMI(BB, X86::MOVSXr32r16, 1, targetReg).addReg(VR.Reg);
 637     break;
 638   case cInt:
 639     // Move value into target register (32->32)
 640     BuildMI(BB, X86::MOVrr32, 1, targetReg).addReg(VR.Reg);
 641     break;
 642   default:
 643     assert(0 && "Unpromotable operand class in promote32");
 644   }
 645 }
 646
 647 /// 'ret' instruction - Here we are interested in meeting the x86 ABI.  As such,
 648 /// we have the following possibilities:
 649 ///
 650 ///   ret void: No return value, simply emit a 'ret' instruction
 651 ///   ret sbyte, ubyte : Extend value into EAX and return
 652 ///   ret short, ushort: Extend value into EAX and return
 653 ///   ret int, uint    : Move value into EAX and return
 654 ///   ret pointer      : Move value into EAX and return
 655 ///   ret long, ulong  : Move value into EAX/EDX and return
 656 ///   ret float/double : Top of FP stack
 657 ///
 658 void ISel::visitReturnInst(ReturnInst &I) {
 659   if (I.getNumOperands() == 0) {
 660     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
 661     return;
 662   }
 663
 664   Value *RetVal = I.getOperand(0);
 665   unsigned RetReg = getReg(RetVal);
 666   switch (getClassB(RetVal->getType())) {
 667   case cByte:   // integral return values: extend or move into EAX and return
 668   case cShort:
 669   case cInt:
 670     promote32(X86::EAX, ValueRecord(RetReg, RetVal->getType()));
 671     break;
 672   case cFP:                   // Floats & Doubles: Return in ST(0)
 673     BuildMI(BB, X86::FpSETRESULT, 1).addReg(RetReg);
 674     break;
 675   case cLong:
 676     BuildMI(BB, X86::MOVrr32, 1, X86::EAX).addReg(RetReg);
 677     BuildMI(BB, X86::MOVrr32, 1, X86::EDX).addReg(RetReg+1);
 678     break;
 679   default:
 680     visitInstruction(I);
 681   }
 682   // Emit a 'ret' instruction
 683   BuildMI(BB, X86::RET, 0);
 684 }
 685
 686 // getBlockAfter - Return the basic block which occurs lexically after the
 687 // specified one.
 688 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
 689   Function::iterator I = BB; ++I;  // Get iterator to next block
 690   return I != BB->getParent()->end() ? &*I : 0;
 691 }
 692
 693 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
 694 /// that since code layout is frozen at this point, that if we are trying to
 695 /// jump to a block that is the immediate successor of the current block, we can
 696 /// just make a fall-through (but we don't currently).
 697 ///
 698 void ISel::visitBranchInst(BranchInst &BI) {
 699   BasicBlock *NextBB = getBlockAfter(BI.getParent());  // BB after current one
 700
 701   if (!BI.isConditional()) {  // Unconditional branch?
 702     if (BI.getSuccessor(0) != NextBB)
 703       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 704     return;
 705   }
 706
 707   // See if we can fold the setcc into the branch itself...
 708   SetCondInst *SCI = canFoldSetCCIntoBranch(BI.getCondition());
 709   if (SCI == 0) {
 710     // Nope, cannot fold setcc into this branch.  Emit a branch on a condition
 711     // computed some other way...
 712     unsigned condReg = getReg(BI.getCondition());
 713     BuildMI(BB, X86::CMPri8, 2).addReg(condReg).addZImm(0);
 714     if (BI.getSuccessor(1) == NextBB) {
 715       if (BI.getSuccessor(0) != NextBB)
 716         BuildMI(BB, X86::JNE, 1).addPCDisp(BI.getSuccessor(0));
 717     } else {
 718       BuildMI(BB, X86::JE, 1).addPCDisp(BI.getSuccessor(1));
 719
 720       if (BI.getSuccessor(0) != NextBB)
 721         BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(0));
 722     }
 723     return;
 724   }
 725
 726   unsigned OpNum = getSetCCNumber(SCI->getOpcode());
 727   bool isSigned = EmitComparisonGetSignedness(OpNum, SCI->getOperand(0),
 728                                               SCI->getOperand(1));
 729
 730   // LLVM  -> X86 signed  X86 unsigned
 731   // -----    ----------  ------------
 732   // seteq -> je          je
 733   // setne -> jne         jne
 734   // setlt -> jl          jb
 735   // setge -> jge         jae
 736   // setgt -> jg          ja
 737   // setle -> jle         jbe
 738   static const unsigned OpcodeTab[2][6] = {
 739     { X86::JE, X86::JNE, X86::JB, X86::JAE, X86::JA, X86::JBE },
 740     { X86::JE, X86::JNE, X86::JL, X86::JGE, X86::JG, X86::JLE },
 741   };
 742
 743   if (BI.getSuccessor(0) != NextBB) {
 744     BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(0));
 745     if (BI.getSuccessor(1) != NextBB)
 746       BuildMI(BB, X86::JMP, 1).addPCDisp(BI.getSuccessor(1));
 747   } else {
 748     // Change to the inverse condition...
 749     if (BI.getSuccessor(1) != NextBB) {
 750       OpNum ^= 1;
 751       BuildMI(BB, OpcodeTab[isSigned][OpNum], 1).addPCDisp(BI.getSuccessor(1));
 752     }
 753   }
 754 }
 755
 756
 757 /// doCall - This emits an abstract call instruction, setting up the arguments
 758 /// and the return value as appropriate.  For the actual function call itself,
 759 /// it inserts the specified CallMI instruction into the stream.
 760 ///
 761 void ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 762                   const std::vector<ValueRecord> &Args) {
 763
 764   // Count how many bytes are to be pushed on the stack...
 765   unsigned NumBytes = 0;
 766
 767   if (!Args.empty()) {
 768     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 769       switch (getClassB(Args[i].Ty)) {
 770       case cByte: case cShort: case cInt:
 771         NumBytes += 4; break;
 772       case cLong:
 773         NumBytes += 8; break;
 774       case cFP:
 775         NumBytes += Args[i].Ty == Type::FloatTy ? 4 : 8;
 776         break;
 777       default: assert(0 && "Unknown class!");
 778       }
 779
 780     // Adjust the stack pointer for the new arguments...
 781     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(NumBytes);
 782
 783     // Arguments go on the stack in reverse order, as specified by the ABI.
 784     unsigned ArgOffset = 0;
 785     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 786       unsigned ArgReg = Args[i].Reg;
 787       switch (getClassB(Args[i].Ty)) {
 788       case cByte:
 789       case cShort: {
 790         // Promote arg to 32 bits wide into a temporary register...
 791         unsigned R = makeAnotherReg(Type::UIntTy);
 792         promote32(R, Args[i]);
 793         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 794                      X86::ESP, ArgOffset).addReg(R);
 795         break;
 796       }
 797       case cInt:
 798         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 799                      X86::ESP, ArgOffset).addReg(ArgReg);
 800         break;
 801       case cLong:
 802         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 803                      X86::ESP, ArgOffset).addReg(ArgReg);
 804         addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
 805                      X86::ESP, ArgOffset+4).addReg(ArgReg+1);
 806         ArgOffset += 4;        // 8 byte entry, not 4.
 807         break;
 808
 809       case cFP:
 810         if (Args[i].Ty == Type::FloatTy) {
 811           addRegOffset(BuildMI(BB, X86::FSTr32, 5),
 812                        X86::ESP, ArgOffset).addReg(ArgReg);
 813         } else {
 814           assert(Args[i].Ty == Type::DoubleTy && "Unknown FP type!");
 815           addRegOffset(BuildMI(BB, X86::FSTr64, 5),
 816                        X86::ESP, ArgOffset).addReg(ArgReg);
 817           ArgOffset += 4;       // 8 byte entry, not 4.
 818         }
 819         break;
 820
 821       default: assert(0 && "Unknown class!");
 822       }
 823       ArgOffset += 4;
 824     }
 825   } else {
 826     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addZImm(0);
 827   }
 828
 829   BB->push_back(CallMI);
 830
 831   BuildMI(BB, X86::ADJCALLSTACKUP, 1).addZImm(NumBytes);
 832
 833   // If there is a return value, scavenge the result from the location the call
 834   // leaves it in...
 835   //
 836   if (Ret.Ty != Type::VoidTy) {
 837     unsigned DestClass = getClassB(Ret.Ty);
 838     switch (DestClass) {
 839     case cByte:
 840     case cShort:
 841     case cInt: {
 842       // Integral results are in %eax, or the appropriate portion
 843       // thereof.
 844       static const unsigned regRegMove[] = {
 845         X86::MOVrr8, X86::MOVrr16, X86::MOVrr32
 846       };
 847       static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX };
 848       BuildMI(BB, regRegMove[DestClass], 1, Ret.Reg).addReg(AReg[DestClass]);
 849       break;
 850     }
 851     case cFP:     // Floating-point return values live in %ST(0)
 852       BuildMI(BB, X86::FpGETRESULT, 1, Ret.Reg);
 853       break;
 854     case cLong:   // Long values are left in EDX:EAX
 855       BuildMI(BB, X86::MOVrr32, 1, Ret.Reg).addReg(X86::EAX);
 856       BuildMI(BB, X86::MOVrr32, 1, Ret.Reg+1).addReg(X86::EDX);
 857       break;
 858     default: assert(0 && "Unknown class!");
 859     }
 860   }
 861 }
 862
 863
 864 /// visitCallInst - Push args on stack and do a procedure call instruction.
 865 void ISel::visitCallInst(CallInst &CI) {
 866   MachineInstr *TheCall;
 867   if (Function *F = CI.getCalledFunction()) {
 868     // Emit a CALL instruction with PC-relative displacement.
 869     TheCall = BuildMI(X86::CALLpcrel32, 1).addGlobalAddress(F, true);
 870   } else {  // Emit an indirect call...
 871     unsigned Reg = getReg(CI.getCalledValue());
 872     TheCall = BuildMI(X86::CALLr32, 1).addReg(Reg);
 873   }
 874
 875   std::vector<ValueRecord> Args;
 876   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
 877     Args.push_back(ValueRecord(getReg(CI.getOperand(i)),
 878                                CI.getOperand(i)->getType()));
 879
 880   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
 881   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args);
 882 }
 883
 884
 885 /// visitSimpleBinary - Implement simple binary operators for integral types...
 886 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or,
 887 /// 4 for Xor.
 888 ///
 889 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
 890   unsigned Class = getClassB(B.getType());
 891
 892   static const unsigned OpcodeTab[][4] = {
 893     // Arithmetic operators
 894     { X86::ADDrr8, X86::ADDrr16, X86::ADDrr32, X86::FpADD },  // ADD
 895     { X86::SUBrr8, X86::SUBrr16, X86::SUBrr32, X86::FpSUB },  // SUB
 896
 897     // Bitwise operators
 898     { X86::ANDrr8, X86::ANDrr16, X86::ANDrr32, 0 },  // AND
 899     { X86:: ORrr8, X86:: ORrr16, X86:: ORrr32, 0 },  // OR
 900     { X86::XORrr8, X86::XORrr16, X86::XORrr32, 0 },  // XOR
 901   };
 902
 903   bool isLong = false;
 904   if (Class == cLong) {
 905     isLong = true;
 906     Class = cInt;          // Bottom 32 bits are handled just like ints
 907   }
 908
 909   unsigned Opcode = OpcodeTab[OperatorClass][Class];
 910   assert(Opcode && "Floating point arguments to logical inst?");
 911   unsigned Op0r = getReg(B.getOperand(0));
 912   unsigned Op1r = getReg(B.getOperand(1));
 913   unsigned DestReg = getReg(B);
 914   BuildMI(BB, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
 915
 916   if (isLong) {        // Handle the upper 32 bits of long values...
 917     static const unsigned TopTab[] = {
 918       X86::ADCrr32, X86::SBBrr32, X86::ANDrr32, X86::ORrr32, X86::XORrr32
 919     };
 920     BuildMI(BB, TopTab[OperatorClass], 2,
 921             DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
 922   }
 923 }
 924
 925 /// doMultiply - Emit appropriate instructions to multiply together the
 926 /// registers op0Reg and op1Reg, and put the result in DestReg.  The type of the
 927 /// result should be given as DestTy.
 928 ///
 929 /// FIXME: doMultiply should use one of the two address IMUL instructions!
 930 ///
 931 void ISel::doMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI,
 932                       unsigned DestReg, const Type *DestTy,
 933                       unsigned op0Reg, unsigned op1Reg) {
 934   unsigned Class = getClass(DestTy);
 935   switch (Class) {
 936   case cFP:              // Floating point multiply
 937     BMI(BB, MBBI, X86::FpMUL, 2, DestReg).addReg(op0Reg).addReg(op1Reg);
 938     return;
 939   default:
 940   case cLong: assert(0 && "doMultiply cannot operate on LONG values!");
 941   case cByte:
 942   case cShort:
 943   case cInt:          // Small integerals, handled below...
 944     break;
 945   }
 946
 947   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
 948   static const unsigned MulOpcode[]={ X86::MULr8 , X86::MULr16 , X86::MULr32  };
 949   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
 950   unsigned Reg     = Regs[Class];
 951
 952   // Emit a MOV to put the first operand into the appropriately-sized
 953   // subreg of EAX.
 954   BMI(MBB, MBBI, MovOpcode[Class], 1, Reg).addReg(op0Reg);
 955
 956   // Emit the appropriate multiply instruction.
 957   BMI(MBB, MBBI, MulOpcode[Class], 1).addReg(op1Reg);
 958
 959   // Emit another MOV to put the result into the destination register.
 960   BMI(MBB, MBBI, MovOpcode[Class], 1, DestReg).addReg(Reg);
 961 }
 962
 963 /// visitMul - Multiplies are not simple binary operators because they must deal
 964 /// with the EAX register explicitly.
 965 ///
 966 void ISel::visitMul(BinaryOperator &I) {
 967   unsigned Op0Reg  = getReg(I.getOperand(0));
 968   unsigned Op1Reg  = getReg(I.getOperand(1));
 969   unsigned DestReg = getReg(I);
 970
 971   // Simple scalar multiply?
 972   if (I.getType() != Type::LongTy && I.getType() != Type::ULongTy) {
 973     MachineBasicBlock::iterator MBBI = BB->end();
 974     doMultiply(BB, MBBI, DestReg, I.getType(), Op0Reg, Op1Reg);
 975   } else {
 976     // Long value.  We have to do things the hard way...
 977     // Multiply the two low parts... capturing carry into EDX
 978     BuildMI(BB, X86::MOVrr32, 1, X86::EAX).addReg(Op0Reg);
 979     BuildMI(BB, X86::MULr32, 1).addReg(Op1Reg);  // AL*BL
 980
 981     unsigned OverflowReg = makeAnotherReg(Type::UIntTy);
 982     BuildMI(BB, X86::MOVrr32, 1, DestReg).addReg(X86::EAX);     // AL*BL
 983     BuildMI(BB, X86::MOVrr32, 1, OverflowReg).addReg(X86::EDX); // AL*BL >> 32
 984
 985     MachineBasicBlock::iterator MBBI = BB->end();
 986     unsigned AHBLReg = makeAnotherReg(Type::UIntTy);
 987     doMultiply(BB, MBBI, AHBLReg, Type::UIntTy, Op0Reg+1, Op1Reg); // AH*BL
 988
 989     unsigned AHBLplusOverflowReg = makeAnotherReg(Type::UIntTy);
 990     BuildMI(BB, X86::ADDrr32, 2,                         // AH*BL+(AL*BL >> 32)
 991             AHBLplusOverflowReg).addReg(AHBLReg).addReg(OverflowReg);
 992
 993     MBBI = BB->end();
 994     unsigned ALBHReg = makeAnotherReg(Type::UIntTy);
 995     doMultiply(BB, MBBI, ALBHReg, Type::UIntTy, Op0Reg, Op1Reg+1); // AL*BH
 996
 997     BuildMI(BB, X86::ADDrr32, 2,               // AL*BH + AH*BL + (AL*BL >> 32)
 998             DestReg+1).addReg(AHBLplusOverflowReg).addReg(ALBHReg);
 999   }
1000 }
1001
1002
1003 /// visitDivRem - Handle division and remainder instructions... these
1004 /// instruction both require the same instructions to be generated, they just
1005 /// select the result from a different register.  Note that both of these
1006 /// instructions work differently for signed and unsigned operands.
1007 ///
1008 void ISel::visitDivRem(BinaryOperator &I) {
1009   unsigned Class     = getClass(I.getType());
1010   unsigned Op0Reg    = getReg(I.getOperand(0));
1011   unsigned Op1Reg    = getReg(I.getOperand(1));
1012   unsigned ResultReg = getReg(I);
1013
1014   switch (Class) {
1015   case cFP:              // Floating point divide
1016     if (I.getOpcode() == Instruction::Div)
1017       BuildMI(BB, X86::FpDIV, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
1018     else {               // Floating point remainder...
1019       MachineInstr *TheCall =
1020         BuildMI(X86::CALLpcrel32, 1).addExternalSymbol("fmod", true);
1021       std::vector<ValueRecord> Args;
1022       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
1023       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
1024       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args);
1025     }
1026     return;
1027   case cLong: {
1028     static const char *FnName[] =
1029       { "__moddi3", "__divdi3", "__umoddi3", "__udivdi3" };
1030
1031     unsigned NameIdx = I.getType()->isUnsigned()*2;
1032     NameIdx += I.getOpcode() == Instruction::Div;
1033     MachineInstr *TheCall =
1034       BuildMI(X86::CALLpcrel32, 1).addExternalSymbol(FnName[NameIdx], true);
1035
1036     std::vector<ValueRecord> Args;
1037     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
1038     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
1039     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args);
1040     return;
1041   }
1042   case cByte: case cShort: case cInt:
1043     break;          // Small integerals, handled below...
1044   default: assert(0 && "Unknown class!");
1045   }
1046
1047   static const unsigned Regs[]     ={ X86::AL    , X86::AX     , X86::EAX     };
1048   static const unsigned MovOpcode[]={ X86::MOVrr8, X86::MOVrr16, X86::MOVrr32 };
1049   static const unsigned ExtOpcode[]={ X86::CBW   , X86::CWD    , X86::CDQ     };
1050   static const unsigned ClrOpcode[]={ X86::XORrr8, X86::XORrr16, X86::XORrr32 };
1051   static const unsigned ExtRegs[]  ={ X86::AH    , X86::DX     , X86::EDX     };
1052
1053   static const unsigned DivOpcode[][4] = {
1054     { X86::DIVr8 , X86::DIVr16 , X86::DIVr32 , 0 },  // Unsigned division
1055     { X86::IDIVr8, X86::IDIVr16, X86::IDIVr32, 0 },  // Signed division
1056   };
1057
1058   bool isSigned   = I.getType()->isSigned();
1059   unsigned Reg    = Regs[Class];
1060   unsigned ExtReg = ExtRegs[Class];
1061
1062   // Put the first operand into one of the A registers...
1063   BuildMI(BB, MovOpcode[Class], 1, Reg).addReg(Op0Reg);
1064
1065   if (isSigned) {
1066     // Emit a sign extension instruction...
1067     BuildMI(BB, ExtOpcode[Class], 0);
1068   } else {
1069     // If unsigned, emit a zeroing instruction... (reg = xor reg, reg)
1070     BuildMI(BB, ClrOpcode[Class], 2, ExtReg).addReg(ExtReg).addReg(ExtReg);
1071   }
1072
1073   // Emit the appropriate divide or remainder instruction...
1074   BuildMI(BB, DivOpcode[isSigned][Class], 1).addReg(Op1Reg);
1075
1076   // Figure out which register we want to pick the result out of...
1077   unsigned DestReg = (I.getOpcode() == Instruction::Div) ? Reg : ExtReg;
1078
1079   // Put the result into the destination register...
1080   BuildMI(BB, MovOpcode[Class], 1, ResultReg).addReg(DestReg);
1081 }
1082
1083
1084 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
1085 /// for constant immediate shift values, and for constant immediate
1086 /// shift values equal to 1. Even the general case is sort of special,
1087 /// because the shift amount has to be in CL, not just any old register.
1088 ///
1089 void ISel::visitShiftInst(ShiftInst &I) {
1090   unsigned SrcReg = getReg(I.getOperand(0));
1091   unsigned DestReg = getReg(I);
1092   bool isLeftShift = I.getOpcode() == Instruction::Shl;
1093   bool isSigned = I.getType()->isSigned();
1094   unsigned Class = getClass(I.getType());
1095
1096   static const unsigned ConstantOperand[][4] = {
1097     { X86::SHRir8, X86::SHRir16, X86::SHRir32, X86::SHRDir32 },  // SHR
1098     { X86::SARir8, X86::SARir16, X86::SARir32, X86::SHRDir32 },  // SAR
1099     { X86::SHLir8, X86::SHLir16, X86::SHLir32, X86::SHLDir32 },  // SHL
1100     { X86::SHLir8, X86::SHLir16, X86::SHLir32, X86::SHLDir32 },  // SAL = SHL
1101   };
1102
1103   static const unsigned NonConstantOperand[][4] = {
1104     { X86::SHRrr8, X86::SHRrr16, X86::SHRrr32 },  // SHR
1105     { X86::SARrr8, X86::SARrr16, X86::SARrr32 },  // SAR
1106     { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32 },  // SHL
1107     { X86::SHLrr8, X86::SHLrr16, X86::SHLrr32 },  // SAL = SHL
1108   };
1109
1110   // Longs, as usual, are handled specially...
1111   if (Class == cLong) {
1112     // If we have a constant shift, we can generate much more efficient code
1113     // than otherwise...
1114     //
1115     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getOperand(1))) {
1116       unsigned Amount = CUI->getValue();
1117       if (Amount < 32) {
1118         const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1119         if (isLeftShift) {
1120           BuildMI(BB, Opc[3], 3,
1121                   DestReg+1).addReg(SrcReg+1).addReg(SrcReg).addZImm(Amount);
1122           BuildMI(BB, Opc[2], 2, DestReg).addReg(SrcReg).addZImm(Amount);
1123         } else {
1124           BuildMI(BB, Opc[3], 3,
1125                   DestReg).addReg(SrcReg  ).addReg(SrcReg+1).addZImm(Amount);
1126           BuildMI(BB, Opc[2], 2, DestReg+1).addReg(SrcReg+1).addZImm(Amount);
1127         }
1128       } else {                 // Shifting more than 32 bits
1129         Amount -= 32;
1130         if (isLeftShift) {
1131           BuildMI(BB, X86::SHLir32, 2,DestReg+1).addReg(SrcReg).addZImm(Amount);
1132           BuildMI(BB, X86::MOVir32, 1,DestReg  ).addZImm(0);
1133         } else {
1134           unsigned Opcode = isSigned ? X86::SARir32 : X86::SHRir32;
1135           BuildMI(BB, Opcode, 2, DestReg).addReg(SrcReg+1).addZImm(Amount);
1136           BuildMI(BB, X86::MOVir32, 1, DestReg+1).addZImm(0);
1137         }
1138       }
1139     } else {
1140       visitInstruction(I);  // FIXME: Implement long shift by non-constant
1141     }
1142     return;
1143   }
1144
1145   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getOperand(1))) {
1146     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
1147     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
1148
1149     const unsigned *Opc = ConstantOperand[isLeftShift*2+isSigned];
1150     BuildMI(BB, Opc[Class], 2, DestReg).addReg(SrcReg).addZImm(CUI->getValue());
1151   } else {                  // The shift amount is non-constant.
1152     BuildMI(BB, X86::MOVrr8, 1, X86::CL).addReg(getReg(I.getOperand(1)));
1153
1154     const unsigned *Opc = NonConstantOperand[isLeftShift*2+isSigned];
1155     BuildMI(BB, Opc[Class], 1, DestReg).addReg(SrcReg);
1156   }
1157 }
1158
1159
1160 /// doFPLoad - This method is used to load an FP value from memory using the
1161 /// current endianness.  NOTE: This method returns a partially constructed load
1162 /// instruction which needs to have the memory source filled in still.
1163 ///
1164 MachineInstr *ISel::doFPLoad(MachineBasicBlock *MBB,
1165                              MachineBasicBlock::iterator &MBBI,
1166                              const Type *Ty, unsigned DestReg) {
1167   assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
1168   unsigned LoadOpcode = Ty == Type::FloatTy ? X86::FLDr32 : X86::FLDr64;
1169
1170   if (TM.getTargetData().isLittleEndian()) // fast path...
1171     return BMI(MBB, MBBI, LoadOpcode, 4, DestReg);
1172
1173   // If we are big-endian, start by creating an LEA instruction to represent the
1174   // address of the memory location to load from...
1175   //
1176   unsigned SrcAddrReg = makeAnotherReg(Type::UIntTy);
1177   MachineInstr *Result = BMI(MBB, MBBI, X86::LEAr32, 5, SrcAddrReg);
1178
1179   // Allocate a temporary stack slot to transform the value into...
1180   int FrameIdx = F->getFrameInfo()->CreateStackObject(Ty, TM.getTargetData());
1181
1182   // Perform the bswaps 32 bits at a time...
1183   unsigned TmpReg1 = makeAnotherReg(Type::UIntTy);
1184   unsigned TmpReg2 = makeAnotherReg(Type::UIntTy);
1185   addDirectMem(BMI(MBB, MBBI, X86::MOVmr32, 4, TmpReg1), SrcAddrReg);
1186   BMI(MBB, MBBI, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1187   unsigned Offset = (Ty == Type::DoubleTy) << 2;
1188   addFrameReference(BMI(MBB, MBBI, X86::MOVrm32, 5),
1189                     FrameIdx, Offset).addReg(TmpReg2);
1190
1191   if (Ty == Type::DoubleTy) {   // Swap the other 32 bits of a double value...
1192     TmpReg1 = makeAnotherReg(Type::UIntTy);
1193     TmpReg2 = makeAnotherReg(Type::UIntTy);
1194
1195     addRegOffset(BMI(MBB, MBBI, X86::MOVmr32, 4, TmpReg1), SrcAddrReg, 4);
1196     BMI(MBB, MBBI, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1197     unsigned Offset = (Ty == Type::DoubleTy) << 2;
1198     addFrameReference(BMI(MBB, MBBI, X86::MOVrm32,5), FrameIdx).addReg(TmpReg2);
1199   }
1200
1201   // Now we can reload the final byteswapped result into the final destination.
1202   addFrameReference(BMI(MBB, MBBI, LoadOpcode, 4, DestReg), FrameIdx);
1203   return Result;
1204 }
1205
1206 /// EmitByteSwap - Byteswap SrcReg into DestReg.
1207 ///
1208 void ISel::EmitByteSwap(unsigned DestReg, unsigned SrcReg, unsigned Class) {
1209   // Emit the byte swap instruction...
1210   switch (Class) {
1211   case cByte:
1212     // No byteswap necessary for 8 bit value...
1213     BuildMI(BB, X86::MOVrr8, 1, DestReg).addReg(SrcReg);
1214     break;
1215   case cInt:
1216     // Use the 32 bit bswap instruction to do a 32 bit swap...
1217     BuildMI(BB, X86::BSWAPr32, 1, DestReg).addReg(SrcReg);
1218     break;
1219
1220   case cShort:
1221     // For 16 bit we have to use an xchg instruction, because there is no
1222     // 16-bit bswap.  XCHG is necessarily not in SSA form, so we force things
1223     // into AX to do the xchg.
1224     //
1225     BuildMI(BB, X86::MOVrr16, 1, X86::AX).addReg(SrcReg);
1226     BuildMI(BB, X86::XCHGrr8, 2).addReg(X86::AL, MOTy::UseAndDef)
1227       .addReg(X86::AH, MOTy::UseAndDef);
1228     BuildMI(BB, X86::MOVrr16, 1, DestReg).addReg(X86::AX);
1229     break;
1230   default: assert(0 && "Cannot byteswap this class!");
1231   }
1232 }
1233
1234
1235 /// visitLoadInst - Implement LLVM load instructions in terms of the x86 'mov'
1236 /// instruction.  The load and store instructions are the only place where we
1237 /// need to worry about the memory layout of the target machine.
1238 ///
1239 void ISel::visitLoadInst(LoadInst &I) {
1240   bool isLittleEndian  = TM.getTargetData().isLittleEndian();
1241   bool hasLongPointers = TM.getTargetData().getPointerSize() == 8;
1242   unsigned SrcAddrReg = getReg(I.getOperand(0));
1243   unsigned DestReg = getReg(I);
1244
1245   unsigned Class = getClass(I.getType());
1246   switch (Class) {
1247   case cFP: {
1248     MachineBasicBlock::iterator MBBI = BB->end();
1249     addDirectMem(doFPLoad(BB, MBBI, I.getType(), DestReg), SrcAddrReg);
1250     return;
1251   }
1252   case cLong: case cInt: case cShort: case cByte:
1253     break;      // Integers of various sizes handled below
1254   default: assert(0 && "Unknown memory class!");
1255   }
1256
1257   // We need to adjust the input pointer if we are emulating a big-endian
1258   // long-pointer target.  On these systems, the pointer that we are interested
1259   // in is in the upper part of the eight byte memory image of the pointer.  It
1260   // also happens to be byte-swapped, but this will be handled later.
1261   //
1262   if (!isLittleEndian && hasLongPointers && isa<PointerType>(I.getType())) {
1263     unsigned R = makeAnotherReg(Type::UIntTy);
1264     BuildMI(BB, X86::ADDri32, 2, R).addReg(SrcAddrReg).addZImm(4);
1265     SrcAddrReg = R;
1266   }
1267
1268   unsigned IReg = DestReg;
1269   if (!isLittleEndian)  // If big endian we need an intermediate stage
1270     DestReg = makeAnotherReg(Class != cLong ? I.getType() : Type::UIntTy);
1271
1272   static const unsigned Opcode[] = {
1273     X86::MOVmr8, X86::MOVmr16, X86::MOVmr32, 0, X86::MOVmr32
1274   };
1275   addDirectMem(BuildMI(BB, Opcode[Class], 4, DestReg), SrcAddrReg);
1276
1277   // Handle long values now...
1278   if (Class == cLong) {
1279     if (isLittleEndian) {
1280       addRegOffset(BuildMI(BB, X86::MOVmr32, 4, DestReg+1), SrcAddrReg, 4);
1281     } else {
1282       EmitByteSwap(IReg+1, DestReg, cInt);
1283       unsigned TempReg = makeAnotherReg(Type::IntTy);
1284       addRegOffset(BuildMI(BB, X86::MOVmr32, 4, TempReg), SrcAddrReg, 4);
1285       EmitByteSwap(IReg, TempReg, cInt);
1286     }
1287     return;
1288   }
1289
1290   if (!isLittleEndian)
1291     EmitByteSwap(IReg, DestReg, Class);
1292 }
1293
1294
1295 /// doFPStore - This method is used to store an FP value to memory using the
1296 /// current endianness.
1297 ///
1298 void ISel::doFPStore(const Type *Ty, unsigned DestAddrReg, unsigned SrcReg) {
1299   assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
1300   unsigned StoreOpcode = Ty == Type::FloatTy ? X86::FSTr32 : X86::FSTr64;
1301
1302   if (TM.getTargetData().isLittleEndian()) {  // fast path...
1303     addDirectMem(BuildMI(BB, StoreOpcode,5), DestAddrReg).addReg(SrcReg);
1304     return;
1305   }
1306
1307   // Allocate a temporary stack slot to transform the value into...
1308   int FrameIdx = F->getFrameInfo()->CreateStackObject(Ty, TM.getTargetData());
1309   unsigned SrcAddrReg = makeAnotherReg(Type::UIntTy);
1310   addFrameReference(BuildMI(BB, X86::LEAr32, 5, SrcAddrReg), FrameIdx);
1311
1312   // Store the value into a temporary stack slot...
1313   addDirectMem(BuildMI(BB, StoreOpcode, 5), SrcAddrReg).addReg(SrcReg);
1314
1315   // Perform the bswaps 32 bits at a time...
1316   unsigned TmpReg1 = makeAnotherReg(Type::UIntTy);
1317   unsigned TmpReg2 = makeAnotherReg(Type::UIntTy);
1318   addDirectMem(BuildMI(BB, X86::MOVmr32, 4, TmpReg1), SrcAddrReg);
1319   BuildMI(BB, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1320   unsigned Offset = (Ty == Type::DoubleTy) << 2;
1321   addRegOffset(BuildMI(BB, X86::MOVrm32, 5),
1322                DestAddrReg, Offset).addReg(TmpReg2);
1323
1324   if (Ty == Type::DoubleTy) {   // Swap the other 32 bits of a double value...
1325     TmpReg1 = makeAnotherReg(Type::UIntTy);
1326     TmpReg2 = makeAnotherReg(Type::UIntTy);
1327
1328     addRegOffset(BuildMI(BB, X86::MOVmr32, 4, TmpReg1), SrcAddrReg, 4);
1329     BuildMI(BB, X86::BSWAPr32, 1, TmpReg2).addReg(TmpReg1);
1330     unsigned Offset = (Ty == Type::DoubleTy) << 2;
1331     addDirectMem(BuildMI(BB, X86::MOVrm32, 5), DestAddrReg).addReg(TmpReg2);
1332   }
1333 }
1334
1335
1336 /// visitStoreInst - Implement LLVM store instructions in terms of the x86 'mov'
1337 /// instruction.
1338 ///
1339 void ISel::visitStoreInst(StoreInst &I) {
1340   bool isLittleEndian  = TM.getTargetData().isLittleEndian();
1341   bool hasLongPointers = TM.getTargetData().getPointerSize() == 8;
1342   unsigned ValReg      = getReg(I.getOperand(0));
1343   unsigned AddressReg  = getReg(I.getOperand(1));
1344
1345   unsigned Class = getClass(I.getOperand(0)->getType());
1346   switch (Class) {
1347   case cLong:
1348     if (isLittleEndian) {
1349       addDirectMem(BuildMI(BB, X86::MOVrm32, 1+4), AddressReg).addReg(ValReg);
1350       addRegOffset(BuildMI(BB, X86::MOVrm32, 1+4),
1351                    AddressReg, 4).addReg(ValReg+1);
1352     } else {
1353       unsigned T1 = makeAnotherReg(Type::IntTy);
1354       unsigned T2 = makeAnotherReg(Type::IntTy);
1355       EmitByteSwap(T1, ValReg  , cInt);
1356       EmitByteSwap(T2, ValReg+1, cInt);
1357       addDirectMem(BuildMI(BB, X86::MOVrm32, 1+4), AddressReg).addReg(T2);
1358       addRegOffset(BuildMI(BB, X86::MOVrm32, 1+4), AddressReg, 4).addReg(T1);
1359     }
1360     return;
1361   case cFP:
1362     doFPStore(I.getOperand(0)->getType(), AddressReg, ValReg);
1363     return;
1364   case cInt: case cShort: case cByte:
1365     break;      // Integers of various sizes handled below
1366   default: assert(0 && "Unknown memory class!");
1367   }
1368
1369   if (!isLittleEndian && hasLongPointers &&
1370       isa<PointerType>(I.getOperand(0)->getType())) {
1371     unsigned R = makeAnotherReg(Type::UIntTy);
1372     BuildMI(BB, X86::ADDri32, 2, R).addReg(AddressReg).addZImm(4);
1373     AddressReg = R;
1374   }
1375
1376   if (!isLittleEndian && Class != cByte) {
1377     unsigned R = makeAnotherReg(I.getOperand(0)->getType());
1378     EmitByteSwap(R, ValReg, Class);
1379     ValReg = R;
1380   }
1381
1382   static const unsigned Opcode[] = { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32 };
1383   addDirectMem(BuildMI(BB, Opcode[Class], 1+4), AddressReg).addReg(ValReg);
1384 }
1385
1386
1387 /// visitCastInst - Here we have various kinds of copying with or without
1388 /// sign extension going on.
1389 void ISel::visitCastInst(CastInst &CI) {
1390   const Type *DestTy = CI.getType();
1391   Value *Src = CI.getOperand(0);
1392   unsigned SrcReg = getReg(Src);
1393   const Type *SrcTy = Src->getType();
1394   unsigned SrcClass = getClassB(SrcTy);
1395   unsigned DestReg = getReg(CI);
1396   unsigned DestClass = getClassB(DestTy);
1397
1398   // Implement casts to bool by using compare on the operand followed by set if
1399   // not zero on the result.
1400   if (DestTy == Type::BoolTy) {
1401     if (SrcClass == cFP || SrcClass == cLong)
1402       visitInstruction(CI);
1403
1404     BuildMI(BB, X86::CMPri8, 2).addReg(SrcReg).addZImm(0);
1405     BuildMI(BB, X86::SETNEr, 1, DestReg);
1406     return;
1407   }
1408
1409   static const unsigned RegRegMove[] = {
1410     X86::MOVrr8, X86::MOVrr16, X86::MOVrr32, X86::FpMOV, X86::MOVrr32
1411   };
1412
1413   // Implement casts between values of the same type class (as determined by
1414   // getClass) by using a register-to-register move.
1415   if (SrcClass == DestClass) {
1416     if (SrcClass <= cInt || (SrcClass == cFP && SrcTy == DestTy)) {
1417       BuildMI(BB, RegRegMove[SrcClass], 1, DestReg).addReg(SrcReg);
1418     } else if (SrcClass == cFP) {
1419       if (SrcTy == Type::FloatTy) {  // double -> float
1420         assert(DestTy == Type::DoubleTy && "Unknown cFP member!");
1421         BuildMI(BB, X86::FpMOV, 1, DestReg).addReg(SrcReg);
1422       } else {                       // float -> double
1423         assert(SrcTy == Type::DoubleTy && DestTy == Type::FloatTy &&
1424                "Unknown cFP member!");
1425         // Truncate from double to float by storing to memory as short, then
1426         // reading it back.
1427         unsigned FltAlign = TM.getTargetData().getFloatAlignment();
1428         int FrameIdx = F->getFrameInfo()->CreateStackObject(4, FltAlign);
1429         addFrameReference(BuildMI(BB, X86::FSTr32, 5), FrameIdx).addReg(SrcReg);
1430         addFrameReference(BuildMI(BB, X86::FLDr32, 5, DestReg), FrameIdx);
1431       }
1432     } else if (SrcClass == cLong) {
1433       BuildMI(BB, X86::MOVrr32, 1, DestReg).addReg(SrcReg);
1434       BuildMI(BB, X86::MOVrr32, 1, DestReg+1).addReg(SrcReg+1);
1435     } else {
1436       visitInstruction(CI);
1437     }
1438     return;
1439   }
1440
1441   // Handle cast of SMALLER int to LARGER int using a move with sign extension
1442   // or zero extension, depending on whether the source type was signed.
1443   if (SrcClass <= cInt && (DestClass <= cInt || DestClass == cLong) &&
1444       SrcClass < DestClass) {
1445     bool isLong = DestClass == cLong;
1446     if (isLong) DestClass = cInt;
1447
1448     static const unsigned Opc[][4] = {
1449       { X86::MOVSXr16r8, X86::MOVSXr32r8, X86::MOVSXr32r16, X86::MOVrr32 }, // s
1450       { X86::MOVZXr16r8, X86::MOVZXr32r8, X86::MOVZXr32r16, X86::MOVrr32 }  // u
1451     };
1452
1453     bool isUnsigned = SrcTy->isUnsigned();
1454     BuildMI(BB, Opc[isUnsigned][SrcClass + DestClass - 1], 1,
1455             DestReg).addReg(SrcReg);
1456
1457     if (isLong) {  // Handle upper 32 bits as appropriate...
1458       if (isUnsigned)     // Zero out top bits...
1459         BuildMI(BB, X86::MOVir32, 1, DestReg+1).addZImm(0);
1460       else                // Sign extend bottom half...
1461         BuildMI(BB, X86::SARir32, 2, DestReg+1).addReg(DestReg).addZImm(31);
1462     }
1463     return;
1464   }
1465
1466   // Special case long -> int ...
1467   if (SrcClass == cLong && DestClass == cInt) {
1468     BuildMI(BB, X86::MOVrr32, 1, DestReg).addReg(SrcReg);
1469     return;
1470   }
1471
1472   // Handle cast of LARGER int to SMALLER int using a move to EAX followed by a
1473   // move out of AX or AL.
1474   if ((SrcClass <= cInt || SrcClass == cLong) && DestClass <= cInt
1475       && SrcClass > DestClass) {
1476     static const unsigned AReg[] = { X86::AL, X86::AX, X86::EAX, 0, X86::EAX };
1477     BuildMI(BB, RegRegMove[SrcClass], 1, AReg[SrcClass]).addReg(SrcReg);
1478     BuildMI(BB, RegRegMove[DestClass], 1, DestReg).addReg(AReg[DestClass]);
1479     return;
1480   }
1481
1482   // Handle casts from integer to floating point now...
1483   if (DestClass == cFP) {
1484     // unsigned int -> load as 64 bit int.
1485     // unsigned long long -> more complex
1486     if (SrcTy->isUnsigned() && SrcTy != Type::UByteTy)
1487       visitInstruction(CI);  // don't handle unsigned src yet!
1488
1489     // We don't have the facilities for directly loading byte sized data from
1490     // memory.  Promote it to 16 bits.
1491     if (SrcClass == cByte) {
1492       unsigned TmpReg = makeAnotherReg(Type::ShortTy);
1493       BuildMI(BB, SrcTy->isSigned() ? X86::MOVSXr16r8 : X86::MOVZXr16r8,
1494               1, TmpReg).addReg(SrcReg);
1495       SrcTy = Type::ShortTy;     // Pretend the short is our input now!
1496       SrcClass = cShort;
1497       SrcReg = TmpReg;
1498     }
1499
1500     // Spill the integer to memory and reload it from there...
1501     int FrameIdx =
1502       F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
1503
1504     if (SrcClass == cLong) {
1505       if (SrcTy == Type::ULongTy) visitInstruction(CI);
1506       addFrameReference(BuildMI(BB, X86::MOVrm32, 5), FrameIdx).addReg(SrcReg);
1507       addFrameReference(BuildMI(BB, X86::MOVrm32, 5),
1508                         FrameIdx, 4).addReg(SrcReg+1);
1509     } else {
1510       static const unsigned Op1[] = { X86::MOVrm8, X86::MOVrm16, X86::MOVrm32 };
1511       addFrameReference(BuildMI(BB, Op1[SrcClass], 5), FrameIdx).addReg(SrcReg);
1512     }
1513
1514     static const unsigned Op2[] =
1515       { 0, X86::FILDr16, X86::FILDr32, 0, X86::FILDr64 };
1516     addFrameReference(BuildMI(BB, Op2[SrcClass], 5, DestReg), FrameIdx);
1517     return;
1518   }
1519
1520   // Handle casts from floating point to integer now...
1521   if (SrcClass == cFP) {
1522     // Change the floating point control register to use "round towards zero"
1523     // mode when truncating to an integer value.
1524     //
1525     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
1526     addFrameReference(BuildMI(BB, X86::FNSTCWm16, 4), CWFrameIdx);
1527
1528     // Load the old value of the high byte of the control word...
1529     unsigned HighPartOfCW = makeAnotherReg(Type::UByteTy);
1530     addFrameReference(BuildMI(BB, X86::MOVmr8, 4, HighPartOfCW), CWFrameIdx, 1);
1531
1532     // Set the high part to be round to zero...
1533     addFrameReference(BuildMI(BB, X86::MOVim8, 5), CWFrameIdx, 1).addZImm(12);
1534
1535     // Reload the modified control word now...
1536     addFrameReference(BuildMI(BB, X86::FLDCWm16, 4), CWFrameIdx);
1537
1538     // Restore the memory image of control word to original value
1539     addFrameReference(BuildMI(BB, X86::MOVrm8, 5),
1540                       CWFrameIdx, 1).addReg(HighPartOfCW);
1541
1542     // We don't have the facilities for directly storing byte sized data to
1543     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
1544     // larger classes because we only have signed FP stores.
1545     unsigned StoreClass  = DestClass;
1546     const Type *StoreTy  = DestTy;
1547     if (StoreClass == cByte || DestTy->isUnsigned())
1548       switch (StoreClass) {
1549       case cByte:  StoreTy = Type::ShortTy; StoreClass = cShort; break;
1550       case cShort: StoreTy = Type::IntTy;   StoreClass = cInt;   break;
1551       case cInt:   StoreTy = Type::LongTy;  StoreClass = cLong;  break;
1552       case cLong:  visitInstruction(CI); // unsigned long long -> more complex
1553       default: assert(0 && "Unknown store class!");
1554       }
1555
1556     // Spill the integer to memory and reload it from there...
1557     int FrameIdx =
1558       F->getFrameInfo()->CreateStackObject(StoreTy, TM.getTargetData());
1559
1560     static const unsigned Op1[] =
1561       { 0, X86::FISTr16, X86::FISTr32, 0, X86::FISTPr64 };
1562     addFrameReference(BuildMI(BB, Op1[StoreClass], 5), FrameIdx).addReg(SrcReg);
1563
1564     if (DestClass == cLong) {
1565       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, DestReg), FrameIdx);
1566       addFrameReference(BuildMI(BB, X86::MOVmr32, 4, DestReg+1), FrameIdx, 4);
1567     } else {
1568       static const unsigned Op2[] = { X86::MOVmr8, X86::MOVmr16, X86::MOVmr32 };
1569       addFrameReference(BuildMI(BB, Op2[DestClass], 4, DestReg), FrameIdx);
1570     }
1571
1572     // Reload the original control word now...
1573     addFrameReference(BuildMI(BB, X86::FLDCWm16, 4), CWFrameIdx);
1574     return;
1575   }
1576
1577   // Anything we haven't handled already, we can't (yet) handle at all.
1578   visitInstruction (CI);
1579 }
1580
1581 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1582 // returns zero when the input is not exactly a power of two.
1583 static unsigned ExactLog2(unsigned Val) {
1584   if (Val == 0) return 0;
1585   unsigned Count = 0;
1586   while (Val != 1) {
1587     if (Val & 1) return 0;
1588     Val >>= 1;
1589     ++Count;
1590   }
1591   return Count+1;
1592 }
1593
1594 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
1595   unsigned outputReg = getReg(I);
1596   MachineBasicBlock::iterator MI = BB->end();
1597   emitGEPOperation(BB, MI, I.getOperand(0),
1598                    I.op_begin()+1, I.op_end(), outputReg);
1599 }
1600
1601 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
1602                             MachineBasicBlock::iterator &IP,
1603                             Value *Src, User::op_iterator IdxBegin,
1604                             User::op_iterator IdxEnd, unsigned TargetReg) {
1605   const TargetData &TD = TM.getTargetData();
1606   const Type *Ty = Src->getType();
1607   unsigned BaseReg = getReg(Src, MBB, IP);
1608
1609   // GEPs have zero or more indices; we must perform a struct access
1610   // or array access for each one.
1611   for (GetElementPtrInst::op_iterator oi = IdxBegin,
1612          oe = IdxEnd; oi != oe; ++oi) {
1613     Value *idx = *oi;
1614     unsigned NextReg = BaseReg;
1615     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1616       // It's a struct access.  idx is the index into the structure,
1617       // which names the field. This index must have ubyte type.
1618       const ConstantUInt *CUI = cast<ConstantUInt>(idx);
1619       assert(CUI->getType() == Type::UByteTy
1620               && "Funny-looking structure index in GEP");
1621       // Use the TargetData structure to pick out what the layout of
1622       // the structure is in memory.  Since the structure index must
1623       // be constant, we can get its value and use it to find the
1624       // right byte offset from the StructLayout class's list of
1625       // structure member offsets.
1626       unsigned idxValue = CUI->getValue();
1627       unsigned FieldOff = TD.getStructLayout(StTy)->MemberOffsets[idxValue];
1628       if (FieldOff) {
1629         NextReg = makeAnotherReg(Type::UIntTy);
1630         // Emit an ADD to add FieldOff to the basePtr.
1631         BMI(MBB, IP, X86::ADDri32, 2,NextReg).addReg(BaseReg).addZImm(FieldOff);
1632       }
1633       // The next type is the member of the structure selected by the
1634       // index.
1635       Ty = StTy->getElementTypes()[idxValue];
1636     } else if (const SequentialType *SqTy = cast<SequentialType>(Ty)) {
1637       // It's an array or pointer access: [ArraySize x ElementType].
1638
1639       // idx is the index into the array.  Unlike with structure
1640       // indices, we may not know its actual value at code-generation
1641       // time.
1642       assert(idx->getType() == Type::LongTy && "Bad GEP array index!");
1643
1644       // We want to add BaseReg to(idxReg * sizeof ElementType). First, we
1645       // must find the size of the pointed-to type (Not coincidentally, the next
1646       // type is the type of the elements in the array).
1647       Ty = SqTy->getElementType();
1648       unsigned elementSize = TD.getTypeSize(Ty);
1649
1650       // If idxReg is a constant, we don't need to perform the multiply!
1651       if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(idx)) {
1652         if (!CSI->isNullValue()) {
1653           unsigned Offset = elementSize*CSI->getValue();
1654           NextReg = makeAnotherReg(Type::UIntTy);
1655           BMI(MBB, IP, X86::ADDri32, 2,NextReg).addReg(BaseReg).addZImm(Offset);
1656         }
1657       } else if (elementSize == 1) {
1658         // If the element size is 1, we don't have to multiply, just add
1659         unsigned idxReg = getReg(idx, MBB, IP);
1660         NextReg = makeAnotherReg(Type::UIntTy);
1661         BMI(MBB, IP, X86::ADDrr32, 2, NextReg).addReg(BaseReg).addReg(idxReg);
1662       } else {
1663         unsigned idxReg = getReg(idx, MBB, IP);
1664         unsigned OffsetReg = makeAnotherReg(Type::UIntTy);
1665         if (unsigned Shift = ExactLog2(elementSize)) {
1666           // If the element size is exactly a power of 2, use a shift to get it.
1667           BMI(MBB, IP, X86::SHLir32, 2,
1668               OffsetReg).addReg(idxReg).addZImm(Shift-1);
1669         } else {
1670           // Most general case, emit a multiply...
1671           unsigned elementSizeReg = makeAnotherReg(Type::LongTy);
1672           BMI(MBB, IP, X86::MOVir32, 1, elementSizeReg).addZImm(elementSize);
1673
1674           // Emit a MUL to multiply the register holding the index by
1675           // elementSize, putting the result in OffsetReg.
1676           doMultiply(MBB, IP, OffsetReg, Type::IntTy, idxReg, elementSizeReg);
1677         }
1678         // Emit an ADD to add OffsetReg to the basePtr.
1679         NextReg = makeAnotherReg(Type::UIntTy);
1680         BMI(MBB, IP, X86::ADDrr32, 2,NextReg).addReg(BaseReg).addReg(OffsetReg);
1681       }
1682     }
1683     // Now that we are here, further indices refer to subtypes of this
1684     // one, so we don't need to worry about BaseReg itself, anymore.
1685     BaseReg = NextReg;
1686   }
1687   // After we have processed all the indices, the result is left in
1688   // BaseReg.  Move it to the register where we were expected to
1689   // put the answer.  A 32-bit move should do it, because we are in
1690   // ILP32 land.
1691   BMI(MBB, IP, X86::MOVrr32, 1, TargetReg).addReg(BaseReg);
1692 }
1693
1694
1695 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
1696 /// frame manager, otherwise do it the hard way.
1697 ///
1698 void ISel::visitAllocaInst(AllocaInst &I) {
1699   // Find the data size of the alloca inst's getAllocatedType.
1700   const Type *Ty = I.getAllocatedType();
1701   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
1702
1703   // If this is a fixed size alloca in the entry block for the function,
1704   // statically stack allocate the space.
1705   //
1706   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(I.getArraySize())) {
1707     if (I.getParent() == I.getParent()->getParent()->begin()) {
1708       TySize *= CUI->getValue();   // Get total allocated size...
1709       unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
1710
1711       // Create a new stack object using the frame manager...
1712       int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
1713       addFrameReference(BuildMI(BB, X86::LEAr32, 5, getReg(I)), FrameIdx);
1714       return;
1715     }
1716   }
1717
1718   // Create a register to hold the temporary result of multiplying the type size
1719   // constant by the variable amount.
1720   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
1721   unsigned SrcReg1 = getReg(I.getArraySize());
1722   unsigned SizeReg = makeAnotherReg(Type::UIntTy);
1723   BuildMI(BB, X86::MOVir32, 1, SizeReg).addZImm(TySize);
1724
1725   // TotalSizeReg = mul <numelements>, <TypeSize>
1726   MachineBasicBlock::iterator MBBI = BB->end();
1727   doMultiply(BB, MBBI, TotalSizeReg, Type::UIntTy, SrcReg1, SizeReg);
1728
1729   // AddedSize = add <TotalSizeReg>, 15
1730   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
1731   BuildMI(BB, X86::ADDri32, 2, AddedSizeReg).addReg(TotalSizeReg).addZImm(15);
1732
1733   // AlignedSize = and <AddedSize>, ~15
1734   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
1735   BuildMI(BB, X86::ANDri32, 2, AlignedSize).addReg(AddedSizeReg).addZImm(~15);
1736
1737   // Subtract size from stack pointer, thereby allocating some space.
1738   BuildMI(BB, X86::SUBrr32, 2, X86::ESP).addReg(X86::ESP).addReg(AlignedSize);
1739
1740   // Put a pointer to the space into the result register, by copying
1741   // the stack pointer.
1742   BuildMI(BB, X86::MOVrr32, 1, getReg(I)).addReg(X86::ESP);
1743
1744   // Inform the Frame Information that we have just allocated a variable sized
1745   // object.
1746   F->getFrameInfo()->CreateVariableSizedObject();
1747 }
1748
1749 /// visitMallocInst - Malloc instructions are code generated into direct calls
1750 /// to the library malloc.
1751 ///
1752 void ISel::visitMallocInst(MallocInst &I) {
1753   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
1754   unsigned Arg;
1755
1756   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
1757     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
1758   } else {
1759     Arg = makeAnotherReg(Type::UIntTy);
1760     unsigned Op0Reg = getReg(ConstantUInt::get(Type::UIntTy, AllocSize));
1761     unsigned Op1Reg = getReg(I.getOperand(0));
1762     MachineBasicBlock::iterator MBBI = BB->end();
1763     doMultiply(BB, MBBI, Arg, Type::UIntTy, Op0Reg, Op1Reg);
1764
1765
1766   }
1767
1768   std::vector<ValueRecord> Args;
1769   Args.push_back(ValueRecord(Arg, Type::UIntTy));
1770   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
1771                                   1).addExternalSymbol("malloc", true);
1772   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args);
1773 }
1774
1775
1776 /// visitFreeInst - Free instructions are code gen'd to call the free libc
1777 /// function.
1778 ///
1779 void ISel::visitFreeInst(FreeInst &I) {
1780   std::vector<ValueRecord> Args;
1781   Args.push_back(ValueRecord(getReg(I.getOperand(0)),
1782                              I.getOperand(0)->getType()));
1783   MachineInstr *TheCall = BuildMI(X86::CALLpcrel32,
1784                                   1).addExternalSymbol("free", true);
1785   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args);
1786 }
1787
1788
1789 /// createSimpleX86InstructionSelector - This pass converts an LLVM function
1790 /// into a machine code representation is a very simple peep-hole fashion.  The
1791 /// generated code sucks but the implementation is nice and simple.
1792 ///
1793 Pass *createSimpleX86InstructionSelector(TargetMachine &TM) {
1794   return new ISel(TM);
1795 }