lib/Target/PowerPC/PPC32ISelSimple.cpp

   1 //===-- PPC32ISelSimple.cpp - A simple instruction selector PowerPC32 -----===//
   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 #define DEBUG_TYPE "isel"
  11 #include "PowerPC.h"
  12 #include "PowerPCInstrBuilder.h"
  13 #include "PowerPCInstrInfo.h"
  14 #include "PPC32TargetMachine.h"
  15 #include "llvm/Constants.h"
  16 #include "llvm/DerivedTypes.h"
  17 #include "llvm/Function.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/CodeGen/IntrinsicLowering.h"
  21 #include "llvm/CodeGen/MachineConstantPool.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/SSARegMap.h"
  25 #include "llvm/Target/MRegisterInfo.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "llvm/Support/GetElementPtrTypeIterator.h"
  28 #include "llvm/Support/InstVisitor.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include <vector>
  32 using namespace llvm;
  33
  34 namespace {
  35   /// TypeClass - Used by the PowerPC backend to group LLVM types by their basic
  36   /// PPC Representation.
  37   ///
  38   enum TypeClass {
  39     cByte, cShort, cInt, cFP32, cFP64, cLong
  40   };
  41 }
  42
  43 /// getClass - Turn a primitive type into a "class" number which is based on the
  44 /// size of the type, and whether or not it is floating point.
  45 ///
  46 static inline TypeClass getClass(const Type *Ty) {
  47   switch (Ty->getTypeID()) {
  48   case Type::SByteTyID:
  49   case Type::UByteTyID:   return cByte;      // Byte operands are class #0
  50   case Type::ShortTyID:
  51   case Type::UShortTyID:  return cShort;     // Short operands are class #1
  52   case Type::IntTyID:
  53   case Type::UIntTyID:
  54   case Type::PointerTyID: return cInt;       // Ints and pointers are class #2
  55
  56   case Type::FloatTyID:   return cFP32;      // Single float is #3
  57   case Type::DoubleTyID:  return cFP64;      // Double Point is #4
  58
  59   case Type::LongTyID:
  60   case Type::ULongTyID:   return cLong;      // Longs are class #5
  61   default:
  62     assert(0 && "Invalid type to getClass!");
  63     return cByte;  // not reached
  64   }
  65 }
  66
  67 // getClassB - Just like getClass, but treat boolean values as ints.
  68 static inline TypeClass getClassB(const Type *Ty) {
  69   if (Ty == Type::BoolTy) return cByte;
  70   return getClass(Ty);
  71 }
  72
  73 namespace {
  74   struct ISel : public FunctionPass, InstVisitor<ISel> {
  75     PPC32TargetMachine &TM;
  76     MachineFunction *F;                 // The function we are compiling into
  77     MachineBasicBlock *BB;              // The current MBB we are compiling
  78     int VarArgsFrameIndex;              // FrameIndex for start of varargs area
  79
  80     std::map<Value*, unsigned> RegMap;  // Mapping between Values and SSA Regs
  81
  82     // External functions used in the Module
  83     Function *fmodfFn, *fmodFn, *__cmpdi2Fn, *__moddi3Fn, *__divdi3Fn,
  84       *__umoddi3Fn,  *__udivdi3Fn, *__fixsfdiFn, *__fixdfdiFn, *__fixunssfdiFn,
  85       *__fixunsdfdiFn, *__floatdisfFn, *__floatdidfFn, *mallocFn, *freeFn;
  86
  87     // MBBMap - Mapping between LLVM BB -> Machine BB
  88     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  89
  90     // AllocaMap - Mapping from fixed sized alloca instructions to the
  91     // FrameIndex for the alloca.
  92     std::map<AllocaInst*, unsigned> AllocaMap;
  93
  94     // A Reg to hold the base address used for global loads and stores, and a
  95     // flag to set whether or not we need to emit it for this function.
  96     unsigned GlobalBaseReg;
  97     bool GlobalBaseInitialized;
  98
  99     ISel(TargetMachine &tm) : TM(reinterpret_cast<PPC32TargetMachine&>(tm)),
 100       F(0), BB(0) {}
 101
 102     bool doInitialization(Module &M) {
 103       // Add external functions that we may call
 104       Type *i = Type::IntTy;
 105       Type *d = Type::DoubleTy;
 106       Type *f = Type::FloatTy;
 107       Type *l = Type::LongTy;
 108       Type *ul = Type::ULongTy;
 109       Type *voidPtr = PointerType::get(Type::SByteTy);
 110       // float fmodf(float, float);
 111       fmodfFn = M.getOrInsertFunction("fmodf", f, f, f, 0);
 112       // double fmod(double, double);
 113       fmodFn = M.getOrInsertFunction("fmod", d, d, d, 0);
 114       // int __cmpdi2(long, long);
 115       __cmpdi2Fn = M.getOrInsertFunction("__cmpdi2", i, l, l, 0);
 116       // long __moddi3(long, long);
 117       __moddi3Fn = M.getOrInsertFunction("__moddi3", l, l, l, 0);
 118       // long __divdi3(long, long);
 119       __divdi3Fn = M.getOrInsertFunction("__divdi3", l, l, l, 0);
 120       // unsigned long __umoddi3(unsigned long, unsigned long);
 121       __umoddi3Fn = M.getOrInsertFunction("__umoddi3", ul, ul, ul, 0);
 122       // unsigned long __udivdi3(unsigned long, unsigned long);
 123       __udivdi3Fn = M.getOrInsertFunction("__udivdi3", ul, ul, ul, 0);
 124       // long __fixsfdi(float)
 125       __fixsfdiFn = M.getOrInsertFunction("__fixsfdi", l, f, 0);
 126       // long __fixdfdi(double)
 127       __fixdfdiFn = M.getOrInsertFunction("__fixdfdi", l, d, 0);
 128       // unsigned long __fixunssfdi(float)
 129       __fixunssfdiFn = M.getOrInsertFunction("__fixunssfdi", ul, f, 0);
 130       // unsigned long __fixunsdfdi(double)
 131       __fixunsdfdiFn = M.getOrInsertFunction("__fixunsdfdi", ul, d, 0);
 132       // float __floatdisf(long)
 133       __floatdisfFn = M.getOrInsertFunction("__floatdisf", f, l, 0);
 134       // double __floatdidf(long)
 135       __floatdidfFn = M.getOrInsertFunction("__floatdidf", d, l, 0);
 136       // void* malloc(size_t)
 137       mallocFn = M.getOrInsertFunction("malloc", voidPtr, Type::UIntTy, 0);
 138       // void free(void*)
 139       freeFn = M.getOrInsertFunction("free", Type::VoidTy, voidPtr, 0);
 140       return false;
 141     }
 142
 143     /// runOnFunction - Top level implementation of instruction selection for
 144     /// the entire function.
 145     ///
 146     bool runOnFunction(Function &Fn) {
 147       // First pass over the function, lower any unknown intrinsic functions
 148       // with the IntrinsicLowering class.
 149       LowerUnknownIntrinsicFunctionCalls(Fn);
 150
 151       F = &MachineFunction::construct(&Fn, TM);
 152
 153       // Create all of the machine basic blocks for the function...
 154       for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 155         F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
 156
 157       BB = &F->front();
 158
 159       // Make sure we re-emit a set of the global base reg if necessary
 160       GlobalBaseInitialized = false;
 161
 162       // Copy incoming arguments off of the stack...
 163       LoadArgumentsToVirtualRegs(Fn);
 164
 165       // Instruction select everything except PHI nodes
 166       visit(Fn);
 167
 168       // Select the PHI nodes
 169       SelectPHINodes();
 170
 171       RegMap.clear();
 172       MBBMap.clear();
 173       AllocaMap.clear();
 174       F = 0;
 175       // We always build a machine code representation for the function
 176       return true;
 177     }
 178
 179     virtual const char *getPassName() const {
 180       return "PowerPC Simple Instruction Selection";
 181     }
 182
 183     /// visitBasicBlock - This method is called when we are visiting a new basic
 184     /// block.  This simply creates a new MachineBasicBlock to emit code into
 185     /// and adds it to the current MachineFunction.  Subsequent visit* for
 186     /// instructions will be invoked for all instructions in the basic block.
 187     ///
 188     void visitBasicBlock(BasicBlock &LLVM_BB) {
 189       BB = MBBMap[&LLVM_BB];
 190     }
 191
 192     /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
 193     /// function, lowering any calls to unknown intrinsic functions into the
 194     /// equivalent LLVM code.
 195     ///
 196     void LowerUnknownIntrinsicFunctionCalls(Function &F);
 197
 198     /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function
 199     /// from the stack into virtual registers.
 200     ///
 201     void LoadArgumentsToVirtualRegs(Function &F);
 202
 203     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 204     /// because we have to generate our sources into the source basic blocks,
 205     /// not the current one.
 206     ///
 207     void SelectPHINodes();
 208
 209     // Visitation methods for various instructions.  These methods simply emit
 210     // fixed PowerPC code for each instruction.
 211
 212     // Control flow operators
 213     void visitReturnInst(ReturnInst &RI);
 214     void visitBranchInst(BranchInst &BI);
 215
 216     struct ValueRecord {
 217       Value *Val;
 218       unsigned Reg;
 219       const Type *Ty;
 220       ValueRecord(unsigned R, const Type *T) : Val(0), Reg(R), Ty(T) {}
 221       ValueRecord(Value *V) : Val(V), Reg(0), Ty(V->getType()) {}
 222     };
 223
 224     // This struct is for recording the necessary operations to emit the GEP
 225     struct CollapsedGepOp {
 226       bool isMul;
 227       Value *index;
 228       ConstantSInt *size;
 229       CollapsedGepOp(bool mul, Value *i, ConstantSInt *s) :
 230         isMul(mul), index(i), size(s) {}
 231     };
 232
 233     void doCall(const ValueRecord &Ret, MachineInstr *CallMI,
 234                 const std::vector<ValueRecord> &Args, bool isVarArg);
 235     void visitCallInst(CallInst &I);
 236     void visitIntrinsicCall(Intrinsic::ID ID, CallInst &I);
 237
 238     // Arithmetic operators
 239     void visitSimpleBinary(BinaryOperator &B, unsigned OpcodeClass);
 240     void visitAdd(BinaryOperator &B) { visitSimpleBinary(B, 0); }
 241     void visitSub(BinaryOperator &B) { visitSimpleBinary(B, 1); }
 242     void visitMul(BinaryOperator &B);
 243
 244     void visitDiv(BinaryOperator &B) { visitDivRem(B); }
 245     void visitRem(BinaryOperator &B) { visitDivRem(B); }
 246     void visitDivRem(BinaryOperator &B);
 247
 248     // Bitwise operators
 249     void visitAnd(BinaryOperator &B) { visitSimpleBinary(B, 2); }
 250     void visitOr (BinaryOperator &B) { visitSimpleBinary(B, 3); }
 251     void visitXor(BinaryOperator &B) { visitSimpleBinary(B, 4); }
 252
 253     // Comparison operators...
 254     void visitSetCondInst(SetCondInst &I);
 255     unsigned EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 256                             MachineBasicBlock *MBB,
 257                             MachineBasicBlock::iterator MBBI);
 258     void visitSelectInst(SelectInst &SI);
 259
 260
 261     // Memory Instructions
 262     void visitLoadInst(LoadInst &I);
 263     void visitStoreInst(StoreInst &I);
 264     void visitGetElementPtrInst(GetElementPtrInst &I);
 265     void visitAllocaInst(AllocaInst &I);
 266     void visitMallocInst(MallocInst &I);
 267     void visitFreeInst(FreeInst &I);
 268
 269     // Other operators
 270     void visitShiftInst(ShiftInst &I);
 271     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
 272     void visitCastInst(CastInst &I);
 273     void visitVANextInst(VANextInst &I);
 274     void visitVAArgInst(VAArgInst &I);
 275
 276     void visitInstruction(Instruction &I) {
 277       std::cerr << "Cannot instruction select: " << I;
 278       abort();
 279     }
 280
 281     unsigned ExtendOrClear(MachineBasicBlock *MBB,
 282                            MachineBasicBlock::iterator IP,
 283                            Value *Op0, Value *Op1);
 284
 285     /// promote32 - Make a value 32-bits wide, and put it somewhere.
 286     ///
 287     void promote32(unsigned targetReg, const ValueRecord &VR);
 288
 289     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 290     /// constant expression GEP support.
 291     ///
 292     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
 293                           Value *Src, User::op_iterator IdxBegin,
 294                           User::op_iterator IdxEnd, unsigned TargetReg,
 295                           bool CollapseRemainder, ConstantSInt **Remainder,
 296                           unsigned *PendingAddReg);
 297
 298     /// emitCastOperation - Common code shared between visitCastInst and
 299     /// constant expression cast support.
 300     ///
 301     void emitCastOperation(MachineBasicBlock *BB,MachineBasicBlock::iterator IP,
 302                            Value *Src, const Type *DestTy, unsigned TargetReg);
 303
 304     /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
 305     /// and constant expression support.
 306     ///
 307     void emitSimpleBinaryOperation(MachineBasicBlock *BB,
 308                                    MachineBasicBlock::iterator IP,
 309                                    Value *Op0, Value *Op1,
 310                                    unsigned OperatorClass, unsigned TargetReg);
 311
 312     /// emitBinaryFPOperation - This method handles emission of floating point
 313     /// Add (0), Sub (1), Mul (2), and Div (3) operations.
 314     void emitBinaryFPOperation(MachineBasicBlock *BB,
 315                                MachineBasicBlock::iterator IP,
 316                                Value *Op0, Value *Op1,
 317                                unsigned OperatorClass, unsigned TargetReg);
 318
 319     void emitMultiply(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
 320                       Value *Op0, Value *Op1, unsigned TargetReg);
 321
 322     void doMultiply(MachineBasicBlock *MBB,
 323                     MachineBasicBlock::iterator IP,
 324                     unsigned DestReg, Value *Op0, Value *Op1);
 325
 326     /// doMultiplyConst - This method will multiply the value in Op0Reg by the
 327     /// value of the ContantInt *CI
 328     void doMultiplyConst(MachineBasicBlock *MBB,
 329                          MachineBasicBlock::iterator IP,
 330                          unsigned DestReg, Value *Op0, ConstantInt *CI);
 331
 332     void emitDivRemOperation(MachineBasicBlock *BB,
 333                              MachineBasicBlock::iterator IP,
 334                              Value *Op0, Value *Op1, bool isDiv,
 335                              unsigned TargetReg);
 336
 337     /// emitSetCCOperation - Common code shared between visitSetCondInst and
 338     /// constant expression support.
 339     ///
 340     void emitSetCCOperation(MachineBasicBlock *BB,
 341                             MachineBasicBlock::iterator IP,
 342                             Value *Op0, Value *Op1, unsigned Opcode,
 343                             unsigned TargetReg);
 344
 345     /// emitShiftOperation - Common code shared between visitShiftInst and
 346     /// constant expression support.
 347     ///
 348     void emitShiftOperation(MachineBasicBlock *MBB,
 349                             MachineBasicBlock::iterator IP,
 350                             Value *Op, Value *ShiftAmount, bool isLeftShift,
 351                             const Type *ResultTy, unsigned DestReg);
 352
 353     /// emitSelectOperation - Common code shared between visitSelectInst and the
 354     /// constant expression support.
 355     ///
 356     void emitSelectOperation(MachineBasicBlock *MBB,
 357                              MachineBasicBlock::iterator IP,
 358                              Value *Cond, Value *TrueVal, Value *FalseVal,
 359                              unsigned DestReg);
 360
 361     /// copyGlobalBaseToRegister - Output the instructions required to put the
 362     /// base address to use for accessing globals into a register.
 363     ///
 364     void ISel::copyGlobalBaseToRegister(MachineBasicBlock *MBB,
 365                                         MachineBasicBlock::iterator IP,
 366                                         unsigned R);
 367
 368     /// copyConstantToRegister - Output the instructions required to put the
 369     /// specified constant into the specified register.
 370     ///
 371     void copyConstantToRegister(MachineBasicBlock *MBB,
 372                                 MachineBasicBlock::iterator MBBI,
 373                                 Constant *C, unsigned Reg);
 374
 375     void emitUCOM(MachineBasicBlock *MBB, MachineBasicBlock::iterator MBBI,
 376                    unsigned LHS, unsigned RHS);
 377
 378     /// makeAnotherReg - This method returns the next register number we haven't
 379     /// yet used.
 380     ///
 381     /// Long values are handled somewhat specially.  They are always allocated
 382     /// as pairs of 32 bit integer values.  The register number returned is the
 383     /// high 32 bits of the long value, and the regNum+1 is the low 32 bits.
 384     ///
 385     unsigned makeAnotherReg(const Type *Ty) {
 386       assert(dynamic_cast<const PPC32RegisterInfo*>(TM.getRegisterInfo()) &&
 387              "Current target doesn't have PPC reg info??");
 388       const PPC32RegisterInfo *PPCRI =
 389         static_cast<const PPC32RegisterInfo*>(TM.getRegisterInfo());
 390       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 391         const TargetRegisterClass *RC = PPCRI->getRegClassForType(Type::IntTy);
 392         // Create the upper part
 393         F->getSSARegMap()->createVirtualRegister(RC);
 394         // Create the lower part.
 395         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 396       }
 397
 398       // Add the mapping of regnumber => reg class to MachineFunction
 399       const TargetRegisterClass *RC = PPCRI->getRegClassForType(Ty);
 400       return F->getSSARegMap()->createVirtualRegister(RC);
 401     }
 402
 403     /// getReg - This method turns an LLVM value into a register number.
 404     ///
 405     unsigned getReg(Value &V) { return getReg(&V); }  // Allow references
 406     unsigned getReg(Value *V) {
 407       // Just append to the end of the current bb.
 408       MachineBasicBlock::iterator It = BB->end();
 409       return getReg(V, BB, It);
 410     }
 411     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 412                     MachineBasicBlock::iterator IPt);
 413
 414     /// canUseAsImmediateForOpcode - This method returns whether a ConstantInt
 415     /// is okay to use as an immediate argument to a certain binary operation
 416     bool canUseAsImmediateForOpcode(ConstantInt *CI, unsigned Opcode);
 417
 418     /// getFixedSizedAllocaFI - Return the frame index for a fixed sized alloca
 419     /// that is to be statically allocated with the initial stack frame
 420     /// adjustment.
 421     unsigned getFixedSizedAllocaFI(AllocaInst *AI);
 422   };
 423 }
 424
 425 /// dyn_castFixedAlloca - If the specified value is a fixed size alloca
 426 /// instruction in the entry block, return it.  Otherwise, return a null
 427 /// pointer.
 428 static AllocaInst *dyn_castFixedAlloca(Value *V) {
 429   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 430     BasicBlock *BB = AI->getParent();
 431     if (isa<ConstantUInt>(AI->getArraySize()) && BB ==&BB->getParent()->front())
 432       return AI;
 433   }
 434   return 0;
 435 }
 436
 437 /// getReg - This method turns an LLVM value into a register number.
 438 ///
 439 unsigned ISel::getReg(Value *V, MachineBasicBlock *MBB,
 440                       MachineBasicBlock::iterator IPt) {
 441   if (Constant *C = dyn_cast<Constant>(V)) {
 442     unsigned Reg = makeAnotherReg(V->getType());
 443     copyConstantToRegister(MBB, IPt, C, Reg);
 444     return Reg;
 445   } else if (AllocaInst *AI = dyn_castFixedAlloca(V)) {
 446     unsigned Reg = makeAnotherReg(V->getType());
 447     unsigned FI = getFixedSizedAllocaFI(AI);
 448     addFrameReference(BuildMI(*MBB, IPt, PPC::ADDI, 2, Reg), FI, 0, false);
 449     return Reg;
 450   }
 451
 452   unsigned &Reg = RegMap[V];
 453   if (Reg == 0) {
 454     Reg = makeAnotherReg(V->getType());
 455     RegMap[V] = Reg;
 456   }
 457
 458   return Reg;
 459 }
 460
 461 /// canUseAsImmediateForOpcode - This method returns whether a ConstantInt
 462 /// is okay to use as an immediate argument to a certain binary operator.
 463 ///
 464 /// Operator is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for Xor.
 465 bool ISel::canUseAsImmediateForOpcode(ConstantInt *CI, unsigned Operator) {
 466   ConstantSInt *Op1Cs;
 467   ConstantUInt *Op1Cu;
 468
 469   // ADDI, Compare, and non-indexed Load take SIMM
 470   bool cond1 = (Operator == 0)
 471     && (Op1Cs = dyn_cast<ConstantSInt>(CI))
 472     && (Op1Cs->getValue() <= 32767)
 473     && (Op1Cs->getValue() >= -32768);
 474
 475   // SUBI takes -SIMM since it is a mnemonic for ADDI
 476   bool cond2 = (Operator == 1)
 477     && (Op1Cs = dyn_cast<ConstantSInt>(CI))
 478     && (Op1Cs->getValue() <= 32768)
 479     && (Op1Cs->getValue() >= -32767);
 480
 481   // ANDIo, ORI, and XORI take unsigned values
 482   bool cond3 = (Operator >= 2)
 483     && (Op1Cs = dyn_cast<ConstantSInt>(CI))
 484     && (Op1Cs->getValue() >= 0)
 485     && (Op1Cs->getValue() <= 32767);
 486
 487   // ADDI and SUBI take SIMMs, so we have to make sure the UInt would fit
 488   bool cond4 = (Operator < 2)
 489     && (Op1Cu = dyn_cast<ConstantUInt>(CI))
 490     && (Op1Cu->getValue() <= 32767);
 491
 492   // ANDIo, ORI, and XORI take UIMMs, so they can be larger
 493   bool cond5 = (Operator >= 2)
 494     && (Op1Cu = dyn_cast<ConstantUInt>(CI))
 495     && (Op1Cu->getValue() <= 65535);
 496
 497   if (cond1 || cond2 || cond3 || cond4 || cond5)
 498     return true;
 499
 500   return false;
 501 }
 502
 503 /// getFixedSizedAllocaFI - Return the frame index for a fixed sized alloca
 504 /// that is to be statically allocated with the initial stack frame
 505 /// adjustment.
 506 unsigned ISel::getFixedSizedAllocaFI(AllocaInst *AI) {
 507   // Already computed this?
 508   std::map<AllocaInst*, unsigned>::iterator I = AllocaMap.lower_bound(AI);
 509   if (I != AllocaMap.end() && I->first == AI) return I->second;
 510
 511   const Type *Ty = AI->getAllocatedType();
 512   ConstantUInt *CUI = cast<ConstantUInt>(AI->getArraySize());
 513   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
 514   TySize *= CUI->getValue();   // Get total allocated size...
 515   unsigned Alignment = TM.getTargetData().getTypeAlignment(Ty);
 516
 517   // Create a new stack object using the frame manager...
 518   int FrameIdx = F->getFrameInfo()->CreateStackObject(TySize, Alignment);
 519   AllocaMap.insert(I, std::make_pair(AI, FrameIdx));
 520   return FrameIdx;
 521 }
 522
 523
 524 /// copyGlobalBaseToRegister - Output the instructions required to put the
 525 /// base address to use for accessing globals into a register.
 526 ///
 527 void ISel::copyGlobalBaseToRegister(MachineBasicBlock *MBB,
 528                                     MachineBasicBlock::iterator IP,
 529                                     unsigned R) {
 530   if (!GlobalBaseInitialized) {
 531     // Insert the set of GlobalBaseReg into the first MBB of the function
 532     MachineBasicBlock &FirstMBB = F->front();
 533     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 534     GlobalBaseReg = makeAnotherReg(Type::IntTy);
 535     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 536     BuildMI(FirstMBB, MBBI, PPC::MFLR, 0, GlobalBaseReg).addReg(PPC::LR);
 537     GlobalBaseInitialized = true;
 538   }
 539   // Emit our copy of GlobalBaseReg to the destination register in the
 540   // current MBB
 541   BuildMI(*MBB, IP, PPC::OR, 2, R).addReg(GlobalBaseReg)
 542     .addReg(GlobalBaseReg);
 543 }
 544
 545 /// copyConstantToRegister - Output the instructions required to put the
 546 /// specified constant into the specified register.
 547 ///
 548 void ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 549                                   MachineBasicBlock::iterator IP,
 550                                   Constant *C, unsigned R) {
 551   if (C->getType()->isIntegral()) {
 552     unsigned Class = getClassB(C->getType());
 553
 554     if (Class == cLong) {
 555       if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(C)) {
 556         uint64_t uval = CUI->getValue();
 557         unsigned hiUVal = uval >> 32;
 558         unsigned loUVal = uval;
 559         ConstantUInt *CUHi = ConstantUInt::get(Type::UIntTy, hiUVal);
 560         ConstantUInt *CULo = ConstantUInt::get(Type::UIntTy, loUVal);
 561         copyConstantToRegister(MBB, IP, CUHi, R);
 562         copyConstantToRegister(MBB, IP, CULo, R+1);
 563         return;
 564       } else if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(C)) {
 565         int64_t sval = CSI->getValue();
 566         int hiSVal = sval >> 32;
 567         int loSVal = sval;
 568         ConstantSInt *CSHi = ConstantSInt::get(Type::IntTy, hiSVal);
 569         ConstantSInt *CSLo = ConstantSInt::get(Type::IntTy, loSVal);
 570         copyConstantToRegister(MBB, IP, CSHi, R);
 571         copyConstantToRegister(MBB, IP, CSLo, R+1);
 572         return;
 573       } else {
 574         std::cerr << "Unhandled long constant type!\n";
 575         abort();
 576       }
 577     }
 578
 579     assert(Class <= cInt && "Type not handled yet!");
 580
 581     // Handle bool
 582     if (C->getType() == Type::BoolTy) {
 583       BuildMI(*MBB, IP, PPC::LI, 1, R).addSImm(C == ConstantBool::True);
 584       return;
 585     }
 586
 587     // Handle int
 588     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(C)) {
 589       unsigned uval = CUI->getValue();
 590       if (uval < 32768) {
 591         BuildMI(*MBB, IP, PPC::LI, 1, R).addSImm(uval);
 592       } else {
 593         unsigned Temp = makeAnotherReg(Type::IntTy);
 594         BuildMI(*MBB, IP, PPC::LIS, 1, Temp).addSImm(uval >> 16);
 595         BuildMI(*MBB, IP, PPC::ORI, 2, R).addReg(Temp).addImm(uval);
 596       }
 597       return;
 598     } else if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(C)) {
 599       int sval = CSI->getValue();
 600       if (sval < 32768 && sval >= -32768) {
 601         BuildMI(*MBB, IP, PPC::LI, 1, R).addSImm(sval);
 602       } else {
 603         unsigned Temp = makeAnotherReg(Type::IntTy);
 604         BuildMI(*MBB, IP, PPC::LIS, 1, Temp).addSImm(sval >> 16);
 605         BuildMI(*MBB, IP, PPC::ORI, 2, R).addReg(Temp).addImm(sval);
 606       }
 607       return;
 608     }
 609     std::cerr << "Unhandled integer constant!\n";
 610     abort();
 611   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 612     // We need to spill the constant to memory...
 613     MachineConstantPool *CP = F->getConstantPool();
 614     unsigned CPI = CP->getConstantPoolIndex(CFP);
 615     const Type *Ty = CFP->getType();
 616
 617     assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
 618
 619     // Load addr of constant to reg; constant is located at base + distance
 620     unsigned GlobalBase = makeAnotherReg(Type::IntTy);
 621     unsigned Reg1 = makeAnotherReg(Type::IntTy);
 622     unsigned Opcode = (Ty == Type::FloatTy) ? PPC::LFS : PPC::LFD;
 623     // Move value at base + distance into return reg
 624     copyGlobalBaseToRegister(MBB, IP, GlobalBase);
 625     BuildMI(*MBB, IP, PPC::LOADHiAddr, 2, Reg1).addReg(GlobalBase)
 626       .addConstantPoolIndex(CPI);
 627     BuildMI(*MBB, IP, Opcode, 2, R).addConstantPoolIndex(CPI).addReg(Reg1);
 628   } else if (isa<ConstantPointerNull>(C)) {
 629     // Copy zero (null pointer) to the register.
 630     BuildMI(*MBB, IP, PPC::LI, 1, R).addSImm(0);
 631   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
 632     // GV is located at base + distance
 633
 634     unsigned GlobalBase = makeAnotherReg(Type::IntTy);
 635     unsigned TmpReg = makeAnotherReg(GV->getType());
 636     unsigned Opcode = (GV->hasWeakLinkage()
 637                       || GV->isExternal()
 638                       || dyn_cast<Function>(GV)) ? PPC::LWZ : PPC::LA;
 639
 640     // Move value at base + distance into return reg
 641     copyGlobalBaseToRegister(MBB, IP, GlobalBase);
 642     BuildMI(*MBB, IP, PPC::LOADHiAddr, 2, TmpReg).addReg(GlobalBase)
 643       .addGlobalAddress(GV);
 644     BuildMI(*MBB, IP, Opcode, 2, R).addGlobalAddress(GV).addReg(TmpReg);
 645
 646     // Add the GV to the list of things whose addresses have been taken.
 647     TM.AddressTaken.insert(GV);
 648   } else {
 649     std::cerr << "Offending constant: " << *C << "\n";
 650     assert(0 && "Type not handled yet!");
 651   }
 652 }
 653
 654 /// LoadArgumentsToVirtualRegs - Load all of the arguments to this function from
 655 /// the stack into virtual registers.
 656 void ISel::LoadArgumentsToVirtualRegs(Function &Fn) {
 657   unsigned ArgOffset = 24;
 658   unsigned GPR_remaining = 8;
 659   unsigned FPR_remaining = 13;
 660   unsigned GPR_idx = 0, FPR_idx = 0;
 661   static const unsigned GPR[] = {
 662     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 663     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 664   };
 665   static const unsigned FPR[] = {
 666     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 667     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 668   };
 669
 670   MachineFrameInfo *MFI = F->getFrameInfo();
 671
 672   for (Function::aiterator I = Fn.abegin(), E = Fn.aend(); I != E; ++I) {
 673     bool ArgLive = !I->use_empty();
 674     unsigned Reg = ArgLive ? getReg(*I) : 0;
 675     int FI;          // Frame object index
 676
 677     switch (getClassB(I->getType())) {
 678     case cByte:
 679       if (ArgLive) {
 680         FI = MFI->CreateFixedObject(4, ArgOffset);
 681         if (GPR_remaining > 0) {
 682           BuildMI(BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 683           BuildMI(BB, PPC::OR, 2, Reg).addReg(GPR[GPR_idx])
 684             .addReg(GPR[GPR_idx]);
 685         } else {
 686           addFrameReference(BuildMI(BB, PPC::LBZ, 2, Reg), FI);
 687         }
 688       }
 689       break;
 690     case cShort:
 691       if (ArgLive) {
 692         FI = MFI->CreateFixedObject(4, ArgOffset);
 693         if (GPR_remaining > 0) {
 694           BuildMI(BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 695           BuildMI(BB, PPC::OR, 2, Reg).addReg(GPR[GPR_idx])
 696             .addReg(GPR[GPR_idx]);
 697         } else {
 698           addFrameReference(BuildMI(BB, PPC::LHZ, 2, Reg), FI);
 699         }
 700       }
 701       break;
 702     case cInt:
 703       if (ArgLive) {
 704         FI = MFI->CreateFixedObject(4, ArgOffset);
 705         if (GPR_remaining > 0) {
 706           BuildMI(BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 707           BuildMI(BB, PPC::OR, 2, Reg).addReg(GPR[GPR_idx])
 708             .addReg(GPR[GPR_idx]);
 709         } else {
 710           addFrameReference(BuildMI(BB, PPC::LWZ, 2, Reg), FI);
 711         }
 712       }
 713       break;
 714     case cLong:
 715       if (ArgLive) {
 716         FI = MFI->CreateFixedObject(8, ArgOffset);
 717         if (GPR_remaining > 1) {
 718           BuildMI(BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 719           BuildMI(BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx+1]);
 720           BuildMI(BB, PPC::OR, 2, Reg).addReg(GPR[GPR_idx])
 721             .addReg(GPR[GPR_idx]);
 722           BuildMI(BB, PPC::OR, 2, Reg+1).addReg(GPR[GPR_idx+1])
 723             .addReg(GPR[GPR_idx+1]);
 724         } else {
 725           addFrameReference(BuildMI(BB, PPC::LWZ, 2, Reg), FI);
 726           addFrameReference(BuildMI(BB, PPC::LWZ, 2, Reg+1), FI, 4);
 727         }
 728       }
 729       // longs require 4 additional bytes and use 2 GPRs
 730       ArgOffset += 4;
 731       if (GPR_remaining > 1) {
 732         GPR_remaining--;
 733         GPR_idx++;
 734       }
 735       break;
 736     case cFP32:
 737      if (ArgLive) {
 738         FI = MFI->CreateFixedObject(4, ArgOffset);
 739
 740         if (FPR_remaining > 0) {
 741           BuildMI(BB, PPC::IMPLICIT_DEF, 0, FPR[FPR_idx]);
 742           BuildMI(BB, PPC::FMR, 1, Reg).addReg(FPR[FPR_idx]);
 743           FPR_remaining--;
 744           FPR_idx++;
 745         } else {
 746           addFrameReference(BuildMI(BB, PPC::LFS, 2, Reg), FI);
 747         }
 748       }
 749       break;
 750     case cFP64:
 751       if (ArgLive) {
 752         FI = MFI->CreateFixedObject(8, ArgOffset);
 753
 754         if (FPR_remaining > 0) {
 755           BuildMI(BB, PPC::IMPLICIT_DEF, 0, FPR[FPR_idx]);
 756           BuildMI(BB, PPC::FMR, 1, Reg).addReg(FPR[FPR_idx]);
 757           FPR_remaining--;
 758           FPR_idx++;
 759         } else {
 760           addFrameReference(BuildMI(BB, PPC::LFD, 2, Reg), FI);
 761         }
 762       }
 763
 764       // doubles require 4 additional bytes and use 2 GPRs of param space
 765       ArgOffset += 4;
 766       if (GPR_remaining > 0) {
 767         GPR_remaining--;
 768         GPR_idx++;
 769       }
 770       break;
 771     default:
 772       assert(0 && "Unhandled argument type!");
 773     }
 774     ArgOffset += 4;  // Each argument takes at least 4 bytes on the stack...
 775     if (GPR_remaining > 0) {
 776       GPR_remaining--;    // uses up 2 GPRs
 777       GPR_idx++;
 778     }
 779   }
 780
 781   // If the function takes variable number of arguments, add a frame offset for
 782   // the start of the first vararg value... this is used to expand
 783   // llvm.va_start.
 784   if (Fn.getFunctionType()->isVarArg())
 785     VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
 786 }
 787
 788
 789 /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
 790 /// because we have to generate our sources into the source basic blocks, not
 791 /// the current one.
 792 ///
 793 void ISel::SelectPHINodes() {
 794   const TargetInstrInfo &TII = *TM.getInstrInfo();
 795   const Function &LF = *F->getFunction();  // The LLVM function...
 796   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 797     const BasicBlock *BB = I;
 798     MachineBasicBlock &MBB = *MBBMap[I];
 799
 800     // Loop over all of the PHI nodes in the LLVM basic block...
 801     MachineBasicBlock::iterator PHIInsertPoint = MBB.begin();
 802     for (BasicBlock::const_iterator I = BB->begin();
 803          PHINode *PN = const_cast<PHINode*>(dyn_cast<PHINode>(I)); ++I) {
 804
 805       // Create a new machine instr PHI node, and insert it.
 806       unsigned PHIReg = getReg(*PN);
 807       MachineInstr *PhiMI = BuildMI(MBB, PHIInsertPoint,
 808                                     PPC::PHI, PN->getNumOperands(), PHIReg);
 809
 810       MachineInstr *LongPhiMI = 0;
 811       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy)
 812         LongPhiMI = BuildMI(MBB, PHIInsertPoint,
 813                             PPC::PHI, PN->getNumOperands(), PHIReg+1);
 814
 815       // PHIValues - Map of blocks to incoming virtual registers.  We use this
 816       // so that we only initialize one incoming value for a particular block,
 817       // even if the block has multiple entries in the PHI node.
 818       //
 819       std::map<MachineBasicBlock*, unsigned> PHIValues;
 820
 821       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 822         MachineBasicBlock *PredMBB = 0;
 823         for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin (),
 824              PE = MBB.pred_end (); PI != PE; ++PI)
 825           if (PN->getIncomingBlock(i) == (*PI)->getBasicBlock()) {
 826             PredMBB = *PI;
 827             break;
 828           }
 829         assert (PredMBB && "Couldn't find incoming machine-cfg edge for phi");
 830
 831         unsigned ValReg;
 832         std::map<MachineBasicBlock*, unsigned>::iterator EntryIt =
 833           PHIValues.lower_bound(PredMBB);
 834
 835         if (EntryIt != PHIValues.end() && EntryIt->first == PredMBB) {
 836           // We already inserted an initialization of the register for this
 837           // predecessor.  Recycle it.
 838           ValReg = EntryIt->second;
 839         } else {
 840           // Get the incoming value into a virtual register.
 841           //
 842           Value *Val = PN->getIncomingValue(i);
 843
 844           // If this is a constant or GlobalValue, we may have to insert code
 845           // into the basic block to compute it into a virtual register.
 846           if ((isa<Constant>(Val) && !isa<ConstantExpr>(Val)) ||
 847               isa<GlobalValue>(Val)) {
 848             // Simple constants get emitted at the end of the basic block,
 849             // before any terminator instructions.  We "know" that the code to
 850             // move a constant into a register will never clobber any flags.
 851             ValReg = getReg(Val, PredMBB, PredMBB->getFirstTerminator());
 852           } else {
 853             // Because we don't want to clobber any values which might be in
 854             // physical registers with the computation of this constant (which
 855             // might be arbitrarily complex if it is a constant expression),
 856             // just insert the computation at the top of the basic block.
 857             MachineBasicBlock::iterator PI = PredMBB->begin();
 858
 859             // Skip over any PHI nodes though!
 860             while (PI != PredMBB->end() && PI->getOpcode() == PPC::PHI)
 861               ++PI;
 862
 863             ValReg = getReg(Val, PredMBB, PI);
 864           }
 865
 866           // Remember that we inserted a value for this PHI for this predecessor
 867           PHIValues.insert(EntryIt, std::make_pair(PredMBB, ValReg));
 868         }
 869
 870         PhiMI->addRegOperand(ValReg);
 871         PhiMI->addMachineBasicBlockOperand(PredMBB);
 872         if (LongPhiMI) {
 873           LongPhiMI->addRegOperand(ValReg+1);
 874           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 875         }
 876       }
 877
 878       // Now that we emitted all of the incoming values for the PHI node, make
 879       // sure to reposition the InsertPoint after the PHI that we just added.
 880       // This is needed because we might have inserted a constant into this
 881       // block, right after the PHI's which is before the old insert point!
 882       PHIInsertPoint = LongPhiMI ? LongPhiMI : PhiMI;
 883       ++PHIInsertPoint;
 884     }
 885   }
 886 }
 887
 888
 889 // canFoldSetCCIntoBranchOrSelect - Return the setcc instruction if we can fold
 890 // it into the conditional branch or select instruction which is the only user
 891 // of the cc instruction.  This is the case if the conditional branch is the
 892 // only user of the setcc, and if the setcc is in the same basic block as the
 893 // conditional branch.
 894 //
 895 static SetCondInst *canFoldSetCCIntoBranchOrSelect(Value *V) {
 896   if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 897     if (SCI->hasOneUse()) {
 898       Instruction *User = cast<Instruction>(SCI->use_back());
 899       if ((isa<BranchInst>(User) || isa<SelectInst>(User)) &&
 900           SCI->getParent() == User->getParent())
 901         return SCI;
 902     }
 903   return 0;
 904 }
 905
 906
 907 // canFoldGEPIntoLoadOrStore - Return the GEP instruction if we can fold it into
 908 // the load or store instruction that is the only user of the GEP.
 909 //
 910 static GetElementPtrInst *canFoldGEPIntoLoadOrStore(Value *V) {
 911   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V))
 912     if (GEPI->hasOneUse()) {
 913       Instruction *User = cast<Instruction>(GEPI->use_back());
 914       if (isa<StoreInst>(User) &&
 915           GEPI->getParent() == User->getParent() &&
 916           User->getOperand(0) != GEPI &&
 917           User->getOperand(1) == GEPI) {
 918         return GEPI;
 919       }
 920       if (isa<LoadInst>(User) &&
 921           GEPI->getParent() == User->getParent() &&
 922           User->getOperand(0) == GEPI) {
 923         return GEPI;
 924       }
 925     }
 926   return 0;
 927 }
 928
 929
 930 // Return a fixed numbering for setcc instructions which does not depend on the
 931 // order of the opcodes.
 932 //
 933 static unsigned getSetCCNumber(unsigned Opcode) {
 934   switch (Opcode) {
 935   default: assert(0 && "Unknown setcc instruction!");
 936   case Instruction::SetEQ: return 0;
 937   case Instruction::SetNE: return 1;
 938   case Instruction::SetLT: return 2;
 939   case Instruction::SetGE: return 3;
 940   case Instruction::SetGT: return 4;
 941   case Instruction::SetLE: return 5;
 942   }
 943 }
 944
 945 static unsigned getPPCOpcodeForSetCCNumber(unsigned Opcode) {
 946   switch (Opcode) {
 947   default: assert(0 && "Unknown setcc instruction!");
 948   case Instruction::SetEQ: return PPC::BEQ;
 949   case Instruction::SetNE: return PPC::BNE;
 950   case Instruction::SetLT: return PPC::BLT;
 951   case Instruction::SetGE: return PPC::BGE;
 952   case Instruction::SetGT: return PPC::BGT;
 953   case Instruction::SetLE: return PPC::BLE;
 954   }
 955 }
 956
 957 /// emitUCOM - emits an unordered FP compare.
 958 void ISel::emitUCOM(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
 959                      unsigned LHS, unsigned RHS) {
 960     BuildMI(*MBB, IP, PPC::FCMPU, 2, PPC::CR0).addReg(LHS).addReg(RHS);
 961 }
 962
 963 unsigned ISel::ExtendOrClear(MachineBasicBlock *MBB,
 964                              MachineBasicBlock::iterator IP,
 965                              Value *Op0, Value *Op1) {
 966   const Type *CompTy = Op0->getType();
 967   unsigned Reg = getReg(Op0, MBB, IP);
 968   unsigned Class = getClassB(CompTy);
 969
 970   // Before we do a comparison or SetCC, we have to make sure that we truncate
 971   // the source registers appropriately.
 972   if (Class == cByte) {
 973     unsigned TmpReg = makeAnotherReg(CompTy);
 974     if (CompTy->isSigned())
 975       BuildMI(*MBB, IP, PPC::EXTSB, 1, TmpReg).addReg(Reg);
 976     else
 977       BuildMI(*MBB, IP, PPC::RLWINM, 4, TmpReg).addReg(Reg).addImm(0)
 978         .addImm(24).addImm(31);
 979     Reg = TmpReg;
 980   } else if (Class == cShort) {
 981     unsigned TmpReg = makeAnotherReg(CompTy);
 982     if (CompTy->isSigned())
 983       BuildMI(*MBB, IP, PPC::EXTSH, 1, TmpReg).addReg(Reg);
 984     else
 985       BuildMI(*MBB, IP, PPC::RLWINM, 4, TmpReg).addReg(Reg).addImm(0)
 986         .addImm(16).addImm(31);
 987     Reg = TmpReg;
 988   }
 989   return Reg;
 990 }
 991
 992 /// EmitComparison - emits a comparison of the two operands, returning the
 993 /// extended setcc code to use.  The result is in CR0.
 994 ///
 995 unsigned ISel::EmitComparison(unsigned OpNum, Value *Op0, Value *Op1,
 996                               MachineBasicBlock *MBB,
 997                               MachineBasicBlock::iterator IP) {
 998   // The arguments are already supposed to be of the same type.
 999   const Type *CompTy = Op0->getType();
1000   unsigned Class = getClassB(CompTy);
1001   unsigned Op0r = ExtendOrClear(MBB, IP, Op0, Op1);
1002
1003   // Use crand for lt, gt and crandc for le, ge
1004   unsigned CROpcode = (OpNum == 2 || OpNum == 4) ? PPC::CRAND : PPC::CRANDC;
1005   // ? cr1[lt] : cr1[gt]
1006   unsigned CR1field = (OpNum == 2 || OpNum == 3) ? 4 : 5;
1007   // ? cr0[lt] : cr0[gt]
1008   unsigned CR0field = (OpNum == 2 || OpNum == 5) ? 0 : 1;
1009   unsigned Opcode = CompTy->isSigned() ? PPC::CMPW : PPC::CMPLW;
1010   unsigned OpcodeImm = CompTy->isSigned() ? PPC::CMPWI : PPC::CMPLWI;
1011
1012   // Special case handling of: cmp R, i
1013   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1014     if (Class == cByte || Class == cShort || Class == cInt) {
1015       unsigned Op1v = CI->getRawValue() & 0xFFFF;
1016       unsigned OpClass = (CompTy->isSigned()) ? 0 : 2;
1017
1018       // Treat compare like ADDI for the purposes of immediate suitability
1019       if (canUseAsImmediateForOpcode(CI, OpClass)) {
1020         BuildMI(*MBB, IP, OpcodeImm, 2, PPC::CR0).addReg(Op0r).addSImm(Op1v);
1021       } else {
1022         unsigned Op1r = getReg(Op1, MBB, IP);
1023         BuildMI(*MBB, IP, Opcode, 2, PPC::CR0).addReg(Op0r).addReg(Op1r);
1024       }
1025       return OpNum;
1026     } else {
1027       assert(Class == cLong && "Unknown integer class!");
1028       unsigned LowCst = CI->getRawValue();
1029       unsigned HiCst = CI->getRawValue() >> 32;
1030       if (OpNum < 2) {    // seteq, setne
1031         unsigned LoLow = makeAnotherReg(Type::IntTy);
1032         unsigned LoTmp = makeAnotherReg(Type::IntTy);
1033         unsigned HiLow = makeAnotherReg(Type::IntTy);
1034         unsigned HiTmp = makeAnotherReg(Type::IntTy);
1035         unsigned FinalTmp = makeAnotherReg(Type::IntTy);
1036
1037         BuildMI(*MBB, IP, PPC::XORI, 2, LoLow).addReg(Op0r+1)
1038           .addImm(LowCst & 0xFFFF);
1039         BuildMI(*MBB, IP, PPC::XORIS, 2, LoTmp).addReg(LoLow)
1040           .addImm(LowCst >> 16);
1041         BuildMI(*MBB, IP, PPC::XORI, 2, HiLow).addReg(Op0r)
1042           .addImm(HiCst & 0xFFFF);
1043         BuildMI(*MBB, IP, PPC::XORIS, 2, HiTmp).addReg(HiLow)
1044           .addImm(HiCst >> 16);
1045         BuildMI(*MBB, IP, PPC::ORo, 2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
1046         return OpNum;
1047       } else {
1048         unsigned ConstReg = makeAnotherReg(CompTy);
1049         copyConstantToRegister(MBB, IP, CI, ConstReg);
1050
1051         // cr0 = r3 ccOpcode r5 or (r3 == r5 AND r4 ccOpcode r6)
1052         BuildMI(*MBB, IP, Opcode, 2, PPC::CR0).addReg(Op0r)
1053           .addReg(ConstReg);
1054         BuildMI(*MBB, IP, Opcode, 2, PPC::CR1).addReg(Op0r+1)
1055           .addReg(ConstReg+1);
1056         BuildMI(*MBB, IP, PPC::CRAND, 3).addImm(2).addImm(2).addImm(CR1field);
1057         BuildMI(*MBB, IP, PPC::CROR, 3).addImm(CR0field).addImm(CR0field)
1058           .addImm(2);
1059         return OpNum;
1060       }
1061     }
1062   }
1063
1064   unsigned Op1r = getReg(Op1, MBB, IP);
1065
1066   switch (Class) {
1067   default: assert(0 && "Unknown type class!");
1068   case cByte:
1069   case cShort:
1070   case cInt:
1071     BuildMI(*MBB, IP, Opcode, 2, PPC::CR0).addReg(Op0r).addReg(Op1r);
1072     break;
1073
1074   case cFP32:
1075   case cFP64:
1076     emitUCOM(MBB, IP, Op0r, Op1r);
1077     break;
1078
1079   case cLong:
1080     if (OpNum < 2) {    // seteq, setne
1081       unsigned LoTmp = makeAnotherReg(Type::IntTy);
1082       unsigned HiTmp = makeAnotherReg(Type::IntTy);
1083       unsigned FinalTmp = makeAnotherReg(Type::IntTy);
1084       BuildMI(*MBB, IP, PPC::XOR, 2, HiTmp).addReg(Op0r).addReg(Op1r);
1085       BuildMI(*MBB, IP, PPC::XOR, 2, LoTmp).addReg(Op0r+1).addReg(Op1r+1);
1086       BuildMI(*MBB, IP, PPC::ORo,  2, FinalTmp).addReg(LoTmp).addReg(HiTmp);
1087       break;  // Allow the sete or setne to be generated from flags set by OR
1088     } else {
1089       unsigned TmpReg1 = makeAnotherReg(Type::IntTy);
1090       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
1091
1092       // cr0 = r3 ccOpcode r5 or (r3 == r5 AND r4 ccOpcode r6)
1093       BuildMI(*MBB, IP, Opcode, 2, PPC::CR0).addReg(Op0r).addReg(Op1r);
1094       BuildMI(*MBB, IP, Opcode, 2, PPC::CR1).addReg(Op0r+1).addReg(Op1r+1);
1095       BuildMI(*MBB, IP, PPC::CRAND, 3).addImm(2).addImm(2).addImm(CR1field);
1096       BuildMI(*MBB, IP, PPC::CROR, 3).addImm(CR0field).addImm(CR0field)
1097         .addImm(2);
1098       return OpNum;
1099     }
1100   }
1101   return OpNum;
1102 }
1103
1104 /// visitSetCondInst - emit code to calculate the condition via
1105 /// EmitComparison(), and possibly store a 0 or 1 to a register as a result
1106 ///
1107 void ISel::visitSetCondInst(SetCondInst &I) {
1108   if (canFoldSetCCIntoBranchOrSelect(&I))
1109     return;
1110
1111   unsigned DestReg = getReg(I);
1112   unsigned Opcode = I.getOpcode();
1113   unsigned PPCOpcode = getPPCOpcodeForSetCCNumber(Opcode);
1114
1115   // Create an iterator with which to insert the MBB for copying the false value
1116   // and the MBB to hold the PHI instruction for this SetCC.
1117   MachineBasicBlock *thisMBB = BB;
1118   const BasicBlock *LLVM_BB = BB->getBasicBlock();
1119   ilist<MachineBasicBlock>::iterator It = BB;
1120   ++It;
1121
1122   //  thisMBB:
1123   //  ...
1124   //   cmpTY cr0, r1, r2
1125   //   %TrueValue = li 1
1126   //   bCC sinkMBB
1127   EmitComparison(Opcode, I.getOperand(0), I.getOperand(1), BB, BB->end());
1128   unsigned TrueValue = makeAnotherReg(I.getType());
1129   BuildMI(BB, PPC::LI, 1, TrueValue).addSImm(1);
1130   MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1131   MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1132   BuildMI(BB, PPCOpcode, 2).addReg(PPC::CR0).addMBB(sinkMBB);
1133   F->getBasicBlockList().insert(It, copy0MBB);
1134   F->getBasicBlockList().insert(It, sinkMBB);
1135   // Update machine-CFG edges
1136   BB->addSuccessor(copy0MBB);
1137   BB->addSuccessor(sinkMBB);
1138
1139   //  copy0MBB:
1140   //   %FalseValue = li 0
1141   //   fallthrough
1142   BB = copy0MBB;
1143   unsigned FalseValue = makeAnotherReg(I.getType());
1144   BuildMI(BB, PPC::LI, 1, FalseValue).addSImm(0);
1145   // Update machine-CFG edges
1146   BB->addSuccessor(sinkMBB);
1147
1148   //  sinkMBB:
1149   //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1150   //  ...
1151   BB = sinkMBB;
1152   BuildMI(BB, PPC::PHI, 4, DestReg).addReg(FalseValue)
1153     .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1154 }
1155
1156 void ISel::visitSelectInst(SelectInst &SI) {
1157   unsigned DestReg = getReg(SI);
1158   MachineBasicBlock::iterator MII = BB->end();
1159   emitSelectOperation(BB, MII, SI.getCondition(), SI.getTrueValue(),
1160                       SI.getFalseValue(), DestReg);
1161 }
1162
1163 /// emitSelect - Common code shared between visitSelectInst and the constant
1164 /// expression support.
1165 /// FIXME: this is most likely broken in one or more ways.  Namely, PowerPC has
1166 /// no select instruction.  FSEL only works for comparisons against zero.
1167 void ISel::emitSelectOperation(MachineBasicBlock *MBB,
1168                                MachineBasicBlock::iterator IP,
1169                                Value *Cond, Value *TrueVal, Value *FalseVal,
1170                                unsigned DestReg) {
1171   unsigned SelectClass = getClassB(TrueVal->getType());
1172   unsigned Opcode;
1173
1174   // See if we can fold the setcc into the select instruction, or if we have
1175   // to get the register of the Cond value
1176   if (SetCondInst *SCI = canFoldSetCCIntoBranchOrSelect(Cond)) {
1177     // We successfully folded the setcc into the select instruction.
1178     unsigned OpNum = getSetCCNumber(SCI->getOpcode());
1179     OpNum = EmitComparison(OpNum, SCI->getOperand(0),SCI->getOperand(1),MBB,IP);
1180     Opcode = getPPCOpcodeForSetCCNumber(SCI->getOpcode());
1181   } else {
1182     unsigned CondReg = getReg(Cond, MBB, IP);
1183     BuildMI(*MBB, IP, PPC::CMPWI, 2, PPC::CR0).addReg(CondReg).addSImm(0);
1184     Opcode = getPPCOpcodeForSetCCNumber(Instruction::SetNE);
1185   }
1186   unsigned TrueValue = getReg(TrueVal, BB, BB->end());
1187
1188   MachineBasicBlock *thisMBB = BB;
1189   const BasicBlock *LLVM_BB = BB->getBasicBlock();
1190   ilist<MachineBasicBlock>::iterator It = BB;
1191   ++It;
1192
1193   //  thisMBB:
1194   //  ...
1195   //   cmpTY cr0, r1, r2
1196   //   %TrueValue = ...
1197   //   bCC sinkMBB
1198   MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1199   MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1200   BuildMI(BB, Opcode, 2).addReg(PPC::CR0).addMBB(sinkMBB);
1201   F->getBasicBlockList().insert(It, copy0MBB);
1202   F->getBasicBlockList().insert(It, sinkMBB);
1203   // Update machine-CFG edges
1204   BB->addSuccessor(copy0MBB);
1205   BB->addSuccessor(sinkMBB);
1206
1207   //  copy0MBB:
1208   //   %FalseValue = ...
1209   //   fallthrough
1210   BB = copy0MBB;
1211   unsigned FalseValue = getReg(FalseVal, BB, BB->begin());
1212   // Update machine-CFG edges
1213   BB->addSuccessor(sinkMBB);
1214
1215   //  sinkMBB:
1216   //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1217   //  ...
1218   BB = sinkMBB;
1219   BuildMI(BB, PPC::PHI, 4, DestReg).addReg(FalseValue)
1220     .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1221
1222   // For a register pair representing a long value, define the second reg
1223   // FIXME: Can this really be correct for selecting longs?
1224   if (getClassB(TrueVal->getType()) == cLong)
1225     BuildMI(BB, PPC::LI, 1, DestReg+1).addImm(0);
1226   return;
1227 }
1228
1229
1230
1231 /// promote32 - Emit instructions to turn a narrow operand into a 32-bit-wide
1232 /// operand, in the specified target register.
1233 ///
1234 void ISel::promote32(unsigned targetReg, const ValueRecord &VR) {
1235   bool isUnsigned = VR.Ty->isUnsigned() || VR.Ty == Type::BoolTy;
1236
1237   Value *Val = VR.Val;
1238   const Type *Ty = VR.Ty;
1239   if (Val) {
1240     if (Constant *C = dyn_cast<Constant>(Val)) {
1241       Val = ConstantExpr::getCast(C, Type::IntTy);
1242       if (isa<ConstantExpr>(Val))   // Could not fold
1243         Val = C;
1244       else
1245         Ty = Type::IntTy;           // Folded!
1246     }
1247
1248     // If this is a simple constant, just emit a load directly to avoid the copy
1249     if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
1250       int TheVal = CI->getRawValue() & 0xFFFFFFFF;
1251
1252       if (TheVal < 32768 && TheVal >= -32768) {
1253         BuildMI(BB, PPC::LI, 1, targetReg).addSImm(TheVal);
1254       } else {
1255         unsigned TmpReg = makeAnotherReg(Type::IntTy);
1256         BuildMI(BB, PPC::LIS, 1, TmpReg).addSImm(TheVal >> 16);
1257         BuildMI(BB, PPC::ORI, 2, targetReg).addReg(TmpReg)
1258           .addImm(TheVal & 0xFFFF);
1259       }
1260       return;
1261     }
1262   }
1263
1264   // Make sure we have the register number for this value...
1265   unsigned Reg = Val ? getReg(Val) : VR.Reg;
1266   switch (getClassB(Ty)) {
1267   case cByte:
1268     // Extend value into target register (8->32)
1269     if (isUnsigned)
1270       BuildMI(BB, PPC::RLWINM, 4, targetReg).addReg(Reg).addZImm(0)
1271         .addZImm(24).addZImm(31);
1272     else
1273       BuildMI(BB, PPC::EXTSB, 1, targetReg).addReg(Reg);
1274     break;
1275   case cShort:
1276     // Extend value into target register (16->32)
1277     if (isUnsigned)
1278       BuildMI(BB, PPC::RLWINM, 4, targetReg).addReg(Reg).addZImm(0)
1279         .addZImm(16).addZImm(31);
1280     else
1281       BuildMI(BB, PPC::EXTSH, 1, targetReg).addReg(Reg);
1282     break;
1283   case cInt:
1284     // Move value into target register (32->32)
1285     BuildMI(BB, PPC::OR, 2, targetReg).addReg(Reg).addReg(Reg);
1286     break;
1287   default:
1288     assert(0 && "Unpromotable operand class in promote32");
1289   }
1290 }
1291
1292 /// visitReturnInst - implemented with BLR
1293 ///
1294 void ISel::visitReturnInst(ReturnInst &I) {
1295   // Only do the processing if this is a non-void return
1296   if (I.getNumOperands() > 0) {
1297     Value *RetVal = I.getOperand(0);
1298     switch (getClassB(RetVal->getType())) {
1299     case cByte:   // integral return values: extend or move into r3 and return
1300     case cShort:
1301     case cInt:
1302       promote32(PPC::R3, ValueRecord(RetVal));
1303       break;
1304     case cFP32:
1305     case cFP64: {   // Floats & Doubles: Return in f1
1306       unsigned RetReg = getReg(RetVal);
1307       BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(RetReg);
1308       break;
1309     }
1310     case cLong: {
1311       unsigned RetReg = getReg(RetVal);
1312       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(RetReg).addReg(RetReg);
1313       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(RetReg+1).addReg(RetReg+1);
1314       break;
1315     }
1316     default:
1317       visitInstruction(I);
1318     }
1319   }
1320   BuildMI(BB, PPC::BLR, 1).addImm(0);
1321 }
1322
1323 // getBlockAfter - Return the basic block which occurs lexically after the
1324 // specified one.
1325 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
1326   Function::iterator I = BB; ++I;  // Get iterator to next block
1327   return I != BB->getParent()->end() ? &*I : 0;
1328 }
1329
1330 /// visitBranchInst - Handle conditional and unconditional branches here.  Note
1331 /// that since code layout is frozen at this point, that if we are trying to
1332 /// jump to a block that is the immediate successor of the current block, we can
1333 /// just make a fall-through (but we don't currently).
1334 ///
1335 void ISel::visitBranchInst(BranchInst &BI) {
1336   // Update machine-CFG edges
1337   BB->addSuccessor(MBBMap[BI.getSuccessor(0)]);
1338   if (BI.isConditional())
1339     BB->addSuccessor(MBBMap[BI.getSuccessor(1)]);
1340
1341   BasicBlock *NextBB = getBlockAfter(BI.getParent());  // BB after current one
1342
1343   if (!BI.isConditional()) {  // Unconditional branch?
1344     if (BI.getSuccessor(0) != NextBB)
1345       BuildMI(BB, PPC::B, 1).addMBB(MBBMap[BI.getSuccessor(0)]);
1346     return;
1347   }
1348
1349   // See if we can fold the setcc into the branch itself...
1350   SetCondInst *SCI = canFoldSetCCIntoBranchOrSelect(BI.getCondition());
1351   if (SCI == 0) {
1352     // Nope, cannot fold setcc into this branch.  Emit a branch on a condition
1353     // computed some other way...
1354     unsigned condReg = getReg(BI.getCondition());
1355     BuildMI(BB, PPC::CMPLI, 3, PPC::CR0).addImm(0).addReg(condReg)
1356       .addImm(0);
1357     if (BI.getSuccessor(1) == NextBB) {
1358       if (BI.getSuccessor(0) != NextBB)
1359         BuildMI(BB, PPC::COND_BRANCH, 3).addReg(PPC::CR0).addImm(PPC::BNE)
1360           .addMBB(MBBMap[BI.getSuccessor(0)])
1361           .addMBB(MBBMap[BI.getSuccessor(1)]);
1362     } else {
1363       BuildMI(BB, PPC::COND_BRANCH, 3).addReg(PPC::CR0).addImm(PPC::BEQ)
1364         .addMBB(MBBMap[BI.getSuccessor(1)])
1365         .addMBB(MBBMap[BI.getSuccessor(0)]);
1366       if (BI.getSuccessor(0) != NextBB)
1367         BuildMI(BB, PPC::B, 1).addMBB(MBBMap[BI.getSuccessor(0)]);
1368     }
1369     return;
1370   }
1371
1372   unsigned OpNum = getSetCCNumber(SCI->getOpcode());
1373   unsigned Opcode = getPPCOpcodeForSetCCNumber(SCI->getOpcode());
1374   MachineBasicBlock::iterator MII = BB->end();
1375   OpNum = EmitComparison(OpNum, SCI->getOperand(0), SCI->getOperand(1), BB,MII);
1376
1377   if (BI.getSuccessor(0) != NextBB) {
1378     BuildMI(BB, PPC::COND_BRANCH, 3).addReg(PPC::CR0).addImm(Opcode)
1379       .addMBB(MBBMap[BI.getSuccessor(0)])
1380       .addMBB(MBBMap[BI.getSuccessor(1)]);
1381     if (BI.getSuccessor(1) != NextBB)
1382       BuildMI(BB, PPC::B, 1).addMBB(MBBMap[BI.getSuccessor(1)]);
1383   } else {
1384     // Change to the inverse condition...
1385     if (BI.getSuccessor(1) != NextBB) {
1386       Opcode = PPC32InstrInfo::invertPPCBranchOpcode(Opcode);
1387       BuildMI(BB, PPC::COND_BRANCH, 3).addReg(PPC::CR0).addImm(Opcode)
1388         .addMBB(MBBMap[BI.getSuccessor(1)])
1389         .addMBB(MBBMap[BI.getSuccessor(0)]);
1390     }
1391   }
1392 }
1393
1394 /// doCall - This emits an abstract call instruction, setting up the arguments
1395 /// and the return value as appropriate.  For the actual function call itself,
1396 /// it inserts the specified CallMI instruction into the stream.
1397 ///
1398 /// FIXME: See Documentation at the following URL for "correct" behavior
1399 /// <http://developer.apple.com/documentation/DeveloperTools/Conceptual/MachORuntime/2rt_powerpc_abi/chapter_9_section_5.html>
1400 void ISel::doCall(const ValueRecord &Ret, MachineInstr *CallMI,
1401                   const std::vector<ValueRecord> &Args, bool isVarArg) {
1402   // Count how many bytes are to be pushed on the stack, including the linkage
1403   // area, and parameter passing area.
1404   unsigned NumBytes = 24;
1405   unsigned ArgOffset = 24;
1406
1407   if (!Args.empty()) {
1408     for (unsigned i = 0, e = Args.size(); i != e; ++i)
1409       switch (getClassB(Args[i].Ty)) {
1410       case cByte: case cShort: case cInt:
1411         NumBytes += 4; break;
1412       case cLong:
1413         NumBytes += 8; break;
1414       case cFP32:
1415         NumBytes += 4; break;
1416       case cFP64:
1417         NumBytes += 8; break;
1418         break;
1419       default: assert(0 && "Unknown class!");
1420       }
1421
1422     // Just to be safe, we'll always reserve the full 24 bytes of linkage area
1423     // plus 32 bytes of argument space in case any called code gets funky on us.
1424     if (NumBytes < 56) NumBytes = 56;
1425
1426     // Adjust the stack pointer for the new arguments...
1427     // These functions are automatically eliminated by the prolog/epilog pass
1428     BuildMI(BB, PPC::ADJCALLSTACKDOWN, 1).addImm(NumBytes);
1429
1430     // Arguments go on the stack in reverse order, as specified by the ABI.
1431     // Offset to the paramater area on the stack is 24.
1432     int GPR_remaining = 8, FPR_remaining = 13;
1433     unsigned GPR_idx = 0, FPR_idx = 0;
1434     static const unsigned GPR[] = {
1435       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
1436       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
1437     };
1438     static const unsigned FPR[] = {
1439       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6,
1440       PPC::F7, PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12,
1441       PPC::F13
1442     };
1443
1444     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1445       unsigned ArgReg;
1446       switch (getClassB(Args[i].Ty)) {
1447       case cByte:
1448       case cShort:
1449         // Promote arg to 32 bits wide into a temporary register...
1450         ArgReg = makeAnotherReg(Type::UIntTy);
1451         promote32(ArgReg, Args[i]);
1452
1453         // Reg or stack?
1454         if (GPR_remaining > 0) {
1455           BuildMI(BB, PPC::OR, 2, GPR[GPR_idx]).addReg(ArgReg)
1456             .addReg(ArgReg);
1457           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1458         }
1459         if (GPR_remaining <= 0 || isVarArg) {
1460           BuildMI(BB, PPC::STW, 3).addReg(ArgReg).addSImm(ArgOffset)
1461             .addReg(PPC::R1);
1462         }
1463         break;
1464       case cInt:
1465         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1466
1467         // Reg or stack?
1468         if (GPR_remaining > 0) {
1469           BuildMI(BB, PPC::OR, 2, GPR[GPR_idx]).addReg(ArgReg)
1470             .addReg(ArgReg);
1471           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1472         }
1473         if (GPR_remaining <= 0 || isVarArg) {
1474           BuildMI(BB, PPC::STW, 3).addReg(ArgReg).addSImm(ArgOffset)
1475             .addReg(PPC::R1);
1476         }
1477         break;
1478       case cLong:
1479         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1480
1481         // Reg or stack?  Note that PPC calling conventions state that long args
1482         // are passed rN = hi, rN+1 = lo, opposite of LLVM.
1483         if (GPR_remaining > 1) {
1484           BuildMI(BB, PPC::OR, 2, GPR[GPR_idx]).addReg(ArgReg)
1485             .addReg(ArgReg);
1486           BuildMI(BB, PPC::OR, 2, GPR[GPR_idx+1]).addReg(ArgReg+1)
1487             .addReg(ArgReg+1);
1488           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1489           CallMI->addRegOperand(GPR[GPR_idx+1], MachineOperand::Use);
1490         }
1491         if (GPR_remaining <= 1 || isVarArg) {
1492           BuildMI(BB, PPC::STW, 3).addReg(ArgReg).addSImm(ArgOffset)
1493             .addReg(PPC::R1);
1494           BuildMI(BB, PPC::STW, 3).addReg(ArgReg+1).addSImm(ArgOffset+4)
1495             .addReg(PPC::R1);
1496         }
1497
1498         ArgOffset += 4;        // 8 byte entry, not 4.
1499         GPR_remaining -= 1;    // uses up 2 GPRs
1500         GPR_idx += 1;
1501         break;
1502       case cFP32:
1503         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1504         // Reg or stack?
1505         if (FPR_remaining > 0) {
1506           BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgReg);
1507           CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1508           FPR_remaining--;
1509           FPR_idx++;
1510
1511           // If this is a vararg function, and there are GPRs left, also
1512           // pass the float in an int.  Otherwise, put it on the stack.
1513           if (isVarArg) {
1514             BuildMI(BB, PPC::STFS, 3).addReg(ArgReg).addSImm(ArgOffset)
1515             .addReg(PPC::R1);
1516             if (GPR_remaining > 0) {
1517               BuildMI(BB, PPC::LWZ, 2, GPR[GPR_idx])
1518               .addSImm(ArgOffset).addReg(PPC::R1);
1519               CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1520             }
1521           }
1522         } else {
1523           BuildMI(BB, PPC::STFS, 3).addReg(ArgReg).addSImm(ArgOffset)
1524           .addReg(PPC::R1);
1525         }
1526         break;
1527       case cFP64:
1528         ArgReg = Args[i].Val ? getReg(Args[i].Val) : Args[i].Reg;
1529         // Reg or stack?
1530         if (FPR_remaining > 0) {
1531           BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgReg);
1532           CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1533           FPR_remaining--;
1534           FPR_idx++;
1535           // For vararg functions, must pass doubles via int regs as well
1536           if (isVarArg) {
1537             BuildMI(BB, PPC::STFD, 3).addReg(ArgReg).addSImm(ArgOffset)
1538             .addReg(PPC::R1);
1539
1540             // Doubles can be split across reg + stack for varargs
1541             if (GPR_remaining > 0) {
1542               BuildMI(BB, PPC::LWZ, 2, GPR[GPR_idx]).addSImm(ArgOffset)
1543               .addReg(PPC::R1);
1544               CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1545             }
1546             if (GPR_remaining > 1) {
1547               BuildMI(BB, PPC::LWZ, 2, GPR[GPR_idx+1])
1548                 .addSImm(ArgOffset+4).addReg(PPC::R1);
1549               CallMI->addRegOperand(GPR[GPR_idx+1], MachineOperand::Use);
1550             }
1551           }
1552         } else {
1553           BuildMI(BB, PPC::STFD, 3).addReg(ArgReg).addSImm(ArgOffset)
1554           .addReg(PPC::R1);
1555         }
1556         // Doubles use 8 bytes, and 2 GPRs worth of param space
1557         ArgOffset += 4;
1558         GPR_remaining--;
1559         GPR_idx++;
1560         break;
1561
1562       default: assert(0 && "Unknown class!");
1563       }
1564       ArgOffset += 4;
1565       GPR_remaining--;
1566       GPR_idx++;
1567     }
1568   } else {
1569     BuildMI(BB, PPC::ADJCALLSTACKDOWN, 1).addImm(NumBytes);
1570   }
1571
1572   BuildMI(BB, PPC::IMPLICIT_DEF, 0, PPC::LR);
1573   BB->push_back(CallMI);
1574
1575   // These functions are automatically eliminated by the prolog/epilog pass
1576   BuildMI(BB, PPC::ADJCALLSTACKUP, 1).addImm(NumBytes);
1577
1578   // If there is a return value, scavenge the result from the location the call
1579   // leaves it in...
1580   //
1581   if (Ret.Ty != Type::VoidTy) {
1582     unsigned DestClass = getClassB(Ret.Ty);
1583     switch (DestClass) {
1584     case cByte:
1585     case cShort:
1586     case cInt:
1587       // Integral results are in r3
1588       BuildMI(BB, PPC::OR, 2, Ret.Reg).addReg(PPC::R3).addReg(PPC::R3);
1589       break;
1590     case cFP32:   // Floating-point return values live in f1
1591     case cFP64:
1592       BuildMI(BB, PPC::FMR, 1, Ret.Reg).addReg(PPC::F1);
1593       break;
1594     case cLong:   // Long values are in r3:r4
1595       BuildMI(BB, PPC::OR, 2, Ret.Reg).addReg(PPC::R3).addReg(PPC::R3);
1596       BuildMI(BB, PPC::OR, 2, Ret.Reg+1).addReg(PPC::R4).addReg(PPC::R4);
1597       break;
1598     default: assert(0 && "Unknown class!");
1599     }
1600   }
1601 }
1602
1603
1604 /// visitCallInst - Push args on stack and do a procedure call instruction.
1605 void ISel::visitCallInst(CallInst &CI) {
1606   MachineInstr *TheCall;
1607   Function *F = CI.getCalledFunction();
1608   if (F) {
1609     // Is it an intrinsic function call?
1610     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) {
1611       visitIntrinsicCall(ID, CI);   // Special intrinsics are not handled here
1612       return;
1613     }
1614     // Emit a CALL instruction with PC-relative displacement.
1615     TheCall = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(F, true);
1616     // Add it to the set of functions called to be used by the Printer
1617     TM.CalledFunctions.insert(F);
1618   } else {  // Emit an indirect call through the CTR
1619     unsigned Reg = getReg(CI.getCalledValue());
1620     BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Reg).addReg(Reg);
1621     BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
1622     TheCall = BuildMI(PPC::CALLindirect, 2).addZImm(20).addZImm(0)
1623       .addReg(PPC::R12);
1624   }
1625
1626   std::vector<ValueRecord> Args;
1627   for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
1628     Args.push_back(ValueRecord(CI.getOperand(i)));
1629
1630   unsigned DestReg = CI.getType() != Type::VoidTy ? getReg(CI) : 0;
1631   bool isVarArg = F ? F->getFunctionType()->isVarArg() : true;
1632   doCall(ValueRecord(DestReg, CI.getType()), TheCall, Args, isVarArg);
1633 }
1634
1635
1636 /// dyncastIsNan - Return the operand of an isnan operation if this is an isnan.
1637 ///
1638 static Value *dyncastIsNan(Value *V) {
1639   if (CallInst *CI = dyn_cast<CallInst>(V))
1640     if (Function *F = CI->getCalledFunction())
1641       if (F->getIntrinsicID() == Intrinsic::isunordered)
1642         return CI->getOperand(1);
1643   return 0;
1644 }
1645
1646 /// isOnlyUsedByUnorderedComparisons - Return true if this value is only used by
1647 /// or's whos operands are all calls to the isnan predicate.
1648 static bool isOnlyUsedByUnorderedComparisons(Value *V) {
1649   assert(dyncastIsNan(V) && "The value isn't an isnan call!");
1650
1651   // Check all uses, which will be or's of isnans if this predicate is true.
1652   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
1653     Instruction *I = cast<Instruction>(*UI);
1654     if (I->getOpcode() != Instruction::Or) return false;
1655     if (I->getOperand(0) != V && !dyncastIsNan(I->getOperand(0))) return false;
1656     if (I->getOperand(1) != V && !dyncastIsNan(I->getOperand(1))) return false;
1657   }
1658
1659   return true;
1660 }
1661
1662 /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
1663 /// function, lowering any calls to unknown intrinsic functions into the
1664 /// equivalent LLVM code.
1665 ///
1666 void ISel::LowerUnknownIntrinsicFunctionCalls(Function &F) {
1667   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1668     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
1669       if (CallInst *CI = dyn_cast<CallInst>(I++))
1670         if (Function *F = CI->getCalledFunction())
1671           switch (F->getIntrinsicID()) {
1672           case Intrinsic::not_intrinsic:
1673           case Intrinsic::vastart:
1674           case Intrinsic::vacopy:
1675           case Intrinsic::vaend:
1676           case Intrinsic::returnaddress:
1677           case Intrinsic::frameaddress:
1678             // FIXME: should lower these ourselves
1679             // case Intrinsic::isunordered:
1680             // case Intrinsic::memcpy: -> doCall().  system memcpy almost
1681             // guaranteed to be faster than anything we generate ourselves
1682             // We directly implement these intrinsics
1683             break;
1684           case Intrinsic::readio: {
1685             // On PPC, memory operations are in-order.  Lower this intrinsic
1686             // into a volatile load.
1687             Instruction *Before = CI->getPrev();
1688             LoadInst * LI = new LoadInst(CI->getOperand(1), "", true, CI);
1689             CI->replaceAllUsesWith(LI);
1690             BB->getInstList().erase(CI);
1691             break;
1692           }
1693           case Intrinsic::writeio: {
1694             // On PPC, memory operations are in-order.  Lower this intrinsic
1695             // into a volatile store.
1696             Instruction *Before = CI->getPrev();
1697             StoreInst *SI = new StoreInst(CI->getOperand(1),
1698                                           CI->getOperand(2), true, CI);
1699             CI->replaceAllUsesWith(SI);
1700             BB->getInstList().erase(CI);
1701             break;
1702           }
1703           default:
1704             // All other intrinsic calls we must lower.
1705             Instruction *Before = CI->getPrev();
1706             TM.getIntrinsicLowering().LowerIntrinsicCall(CI);
1707             if (Before) {        // Move iterator to instruction after call
1708               I = Before; ++I;
1709             } else {
1710               I = BB->begin();
1711             }
1712           }
1713 }
1714
1715 void ISel::visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI) {
1716   unsigned TmpReg1, TmpReg2, TmpReg3;
1717   switch (ID) {
1718   case Intrinsic::vastart:
1719     // Get the address of the first vararg value...
1720     TmpReg1 = getReg(CI);
1721     addFrameReference(BuildMI(BB, PPC::ADDI, 2, TmpReg1), VarArgsFrameIndex,
1722                       0, false);
1723     return;
1724
1725   case Intrinsic::vacopy:
1726     TmpReg1 = getReg(CI);
1727     TmpReg2 = getReg(CI.getOperand(1));
1728     BuildMI(BB, PPC::OR, 2, TmpReg1).addReg(TmpReg2).addReg(TmpReg2);
1729     return;
1730   case Intrinsic::vaend: return;
1731
1732   case Intrinsic::returnaddress:
1733     TmpReg1 = getReg(CI);
1734     if (cast<Constant>(CI.getOperand(1))->isNullValue()) {
1735       MachineFrameInfo *MFI = F->getFrameInfo();
1736       unsigned NumBytes = MFI->getStackSize();
1737
1738       BuildMI(BB, PPC::LWZ, 2, TmpReg1).addSImm(NumBytes+8)
1739         .addReg(PPC::R1);
1740     } else {
1741       // Values other than zero are not implemented yet.
1742       BuildMI(BB, PPC::LI, 1, TmpReg1).addSImm(0);
1743     }
1744     return;
1745
1746   case Intrinsic::frameaddress:
1747     TmpReg1 = getReg(CI);
1748     if (cast<Constant>(CI.getOperand(1))->isNullValue()) {
1749       BuildMI(BB, PPC::OR, 2, TmpReg1).addReg(PPC::R1).addReg(PPC::R1);
1750     } else {
1751       // Values other than zero are not implemented yet.
1752       BuildMI(BB, PPC::LI, 1, TmpReg1).addSImm(0);
1753     }
1754     return;
1755
1756 #if 0
1757     // This may be useful for supporting isunordered
1758   case Intrinsic::isnan:
1759     // If this is only used by 'isunordered' style comparisons, don't emit it.
1760     if (isOnlyUsedByUnorderedComparisons(&CI)) return;
1761     TmpReg1 = getReg(CI.getOperand(1));
1762     emitUCOM(BB, BB->end(), TmpReg1, TmpReg1);
1763     TmpReg2 = makeAnotherReg(Type::IntTy);
1764     BuildMI(BB, PPC::MFCR, TmpReg2);
1765     TmpReg3 = getReg(CI);
1766     BuildMI(BB, PPC::RLWINM, 4, TmpReg3).addReg(TmpReg2).addImm(4).addImm(31).addImm(31);
1767     return;
1768 #endif
1769
1770   default: assert(0 && "Error: unknown intrinsics should have been lowered!");
1771   }
1772 }
1773
1774 /// visitSimpleBinary - Implement simple binary operators for integral types...
1775 /// OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for Or, 4 for
1776 /// Xor.
1777 ///
1778 void ISel::visitSimpleBinary(BinaryOperator &B, unsigned OperatorClass) {
1779   unsigned DestReg = getReg(B);
1780   MachineBasicBlock::iterator MI = BB->end();
1781   Value *Op0 = B.getOperand(0), *Op1 = B.getOperand(1);
1782   unsigned Class = getClassB(B.getType());
1783
1784   emitSimpleBinaryOperation(BB, MI, Op0, Op1, OperatorClass, DestReg);
1785 }
1786
1787 /// emitBinaryFPOperation - This method handles emission of floating point
1788 /// Add (0), Sub (1), Mul (2), and Div (3) operations.
1789 void ISel::emitBinaryFPOperation(MachineBasicBlock *BB,
1790                                  MachineBasicBlock::iterator IP,
1791                                  Value *Op0, Value *Op1,
1792                                  unsigned OperatorClass, unsigned DestReg) {
1793
1794   static const unsigned OpcodeTab[][4] = {
1795     { PPC::FADDS, PPC::FSUBS, PPC::FMULS, PPC::FDIVS },  // Float
1796     { PPC::FADD,  PPC::FSUB,  PPC::FMUL,  PPC::FDIV },   // Double
1797   };
1798
1799   // Special case: R1 = op <const fp>, R2
1800   if (ConstantFP *Op0C = dyn_cast<ConstantFP>(Op0))
1801     if (Op0C->isExactlyValue(-0.0) && OperatorClass == 1) {
1802       // -0.0 - X === -X
1803       unsigned op1Reg = getReg(Op1, BB, IP);
1804       BuildMI(*BB, IP, PPC::FNEG, 1, DestReg).addReg(op1Reg);
1805       return;
1806     }
1807
1808   unsigned Opcode = OpcodeTab[Op0->getType() == Type::DoubleTy][OperatorClass];
1809   unsigned Op0r = getReg(Op0, BB, IP);
1810   unsigned Op1r = getReg(Op1, BB, IP);
1811   BuildMI(*BB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
1812 }
1813
1814 /// emitSimpleBinaryOperation - Implement simple binary operators for integral
1815 /// types...  OperatorClass is one of: 0 for Add, 1 for Sub, 2 for And, 3 for
1816 /// Or, 4 for Xor.
1817 ///
1818 /// emitSimpleBinaryOperation - Common code shared between visitSimpleBinary
1819 /// and constant expression support.
1820 ///
1821 void ISel::emitSimpleBinaryOperation(MachineBasicBlock *MBB,
1822                                      MachineBasicBlock::iterator IP,
1823                                      Value *Op0, Value *Op1,
1824                                      unsigned OperatorClass, unsigned DestReg) {
1825   unsigned Class = getClassB(Op0->getType());
1826
1827   // Arithmetic and Bitwise operators
1828   static const unsigned OpcodeTab[] = {
1829     PPC::ADD, PPC::SUB, PPC::AND, PPC::OR, PPC::XOR
1830   };
1831   static const unsigned ImmOpcodeTab[] = {
1832     PPC::ADDI, PPC::SUBI, PPC::ANDIo, PPC::ORI, PPC::XORI
1833   };
1834   static const unsigned RImmOpcodeTab[] = {
1835     PPC::ADDI, PPC::SUBFIC, PPC::ANDIo, PPC::ORI, PPC::XORI
1836   };
1837
1838   // Otherwise, code generate the full operation with a constant.
1839   static const unsigned BottomTab[] = {
1840     PPC::ADDC, PPC::SUBC, PPC::AND, PPC::OR, PPC::XOR
1841   };
1842   static const unsigned TopTab[] = {
1843     PPC::ADDE, PPC::SUBFE, PPC::AND, PPC::OR, PPC::XOR
1844   };
1845
1846   if (Class == cFP32 || Class == cFP64) {
1847     assert(OperatorClass < 2 && "No logical ops for FP!");
1848     emitBinaryFPOperation(MBB, IP, Op0, Op1, OperatorClass, DestReg);
1849     return;
1850   }
1851
1852   if (Op0->getType() == Type::BoolTy) {
1853     if (OperatorClass == 3)
1854       // If this is an or of two isnan's, emit an FP comparison directly instead
1855       // of or'ing two isnan's together.
1856       if (Value *LHS = dyncastIsNan(Op0))
1857         if (Value *RHS = dyncastIsNan(Op1)) {
1858           unsigned Op0Reg = getReg(RHS, MBB, IP), Op1Reg = getReg(LHS, MBB, IP);
1859           unsigned TmpReg = makeAnotherReg(Type::IntTy);
1860           emitUCOM(MBB, IP, Op0Reg, Op1Reg);
1861           BuildMI(*MBB, IP, PPC::MFCR, TmpReg);
1862           BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(TmpReg).addImm(4)
1863             .addImm(31).addImm(31);
1864           return;
1865         }
1866   }
1867
1868   // Special case: op <const int>, Reg
1869   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0)) {
1870     // sub 0, X -> subfic
1871     if (OperatorClass == 1 && canUseAsImmediateForOpcode(CI, 0)) {
1872       unsigned Op1r = getReg(Op1, MBB, IP);
1873       int imm = CI->getRawValue() & 0xFFFF;
1874
1875       if (Class == cLong) {
1876         BuildMI(*MBB, IP, PPC::SUBFIC, 2, DestReg+1).addReg(Op1r+1)
1877           .addSImm(imm);
1878         BuildMI(*MBB, IP, PPC::SUBFZE, 1, DestReg).addReg(Op1r);
1879       } else {
1880         BuildMI(*MBB, IP, PPC::SUBFIC, 2, DestReg).addReg(Op1r).addSImm(imm);
1881       }
1882       return;
1883     }
1884
1885     // If it is easy to do, swap the operands and emit an immediate op
1886     if (Class != cLong && OperatorClass != 1 &&
1887         canUseAsImmediateForOpcode(CI, OperatorClass)) {
1888       unsigned Op1r = getReg(Op1, MBB, IP);
1889       int imm = CI->getRawValue() & 0xFFFF;
1890
1891       if (OperatorClass < 2)
1892         BuildMI(*MBB, IP, RImmOpcodeTab[OperatorClass], 2, DestReg).addReg(Op1r)
1893           .addSImm(imm);
1894       else
1895         BuildMI(*MBB, IP, RImmOpcodeTab[OperatorClass], 2, DestReg).addReg(Op1r)
1896           .addZImm(imm);
1897       return;
1898     }
1899   }
1900
1901   // Special case: op Reg, <const int>
1902   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
1903     unsigned Op0r = getReg(Op0, MBB, IP);
1904
1905     // xor X, -1 -> not X
1906     if (OperatorClass == 4 && Op1C->isAllOnesValue()) {
1907       BuildMI(*MBB, IP, PPC::NOR, 2, DestReg).addReg(Op0r).addReg(Op0r);
1908       if (Class == cLong)  // Invert the low part too
1909         BuildMI(*MBB, IP, PPC::NOR, 2, DestReg+1).addReg(Op0r+1)
1910           .addReg(Op0r+1);
1911       return;
1912     }
1913
1914     if (Class != cLong) {
1915       if (canUseAsImmediateForOpcode(Op1C, OperatorClass)) {
1916         int immediate = Op1C->getRawValue() & 0xFFFF;
1917
1918         if (OperatorClass < 2)
1919           BuildMI(*MBB, IP, ImmOpcodeTab[OperatorClass], 2,DestReg).addReg(Op0r)
1920             .addSImm(immediate);
1921         else
1922           BuildMI(*MBB, IP, ImmOpcodeTab[OperatorClass], 2,DestReg).addReg(Op0r)
1923             .addZImm(immediate);
1924       } else {
1925         unsigned Op1r = getReg(Op1, MBB, IP);
1926         BuildMI(*MBB, IP, OpcodeTab[OperatorClass], 2, DestReg).addReg(Op0r)
1927           .addReg(Op1r);
1928       }
1929       return;
1930     }
1931
1932     unsigned Op1r = getReg(Op1, MBB, IP);
1933
1934     BuildMI(*MBB, IP, BottomTab[OperatorClass], 2, DestReg+1).addReg(Op0r+1)
1935       .addReg(Op1r+1);
1936     BuildMI(*MBB, IP, TopTab[OperatorClass], 2, DestReg).addReg(Op0r)
1937       .addReg(Op1r);
1938     return;
1939   }
1940
1941   // We couldn't generate an immediate variant of the op, load both halves into
1942   // registers and emit the appropriate opcode.
1943   unsigned Op0r = getReg(Op0, MBB, IP);
1944   unsigned Op1r = getReg(Op1, MBB, IP);
1945
1946   if (Class != cLong) {
1947     unsigned Opcode = OpcodeTab[OperatorClass];
1948     BuildMI(*MBB, IP, Opcode, 2, DestReg).addReg(Op0r).addReg(Op1r);
1949   } else {
1950     BuildMI(*MBB, IP, BottomTab[OperatorClass], 2, DestReg+1).addReg(Op0r+1)
1951       .addReg(Op1r+1);
1952     BuildMI(*MBB, IP, TopTab[OperatorClass], 2, DestReg).addReg(Op0r)
1953       .addReg(Op1r);
1954   }
1955   return;
1956 }
1957
1958 // ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
1959 // returns zero when the input is not exactly a power of two.
1960 static unsigned ExactLog2(unsigned Val) {
1961   if (Val == 0 || (Val & (Val-1))) return 0;
1962   unsigned Count = 0;
1963   while (Val != 1) {
1964     Val >>= 1;
1965     ++Count;
1966   }
1967   return Count;
1968 }
1969
1970 /// doMultiply - Emit appropriate instructions to multiply together the
1971 /// Values Op0 and Op1, and put the result in DestReg.
1972 ///
1973 void ISel::doMultiply(MachineBasicBlock *MBB,
1974                       MachineBasicBlock::iterator IP,
1975                       unsigned DestReg, Value *Op0, Value *Op1) {
1976   unsigned Class0 = getClass(Op0->getType());
1977   unsigned Class1 = getClass(Op1->getType());
1978
1979   unsigned Op0r = getReg(Op0, MBB, IP);
1980   unsigned Op1r = getReg(Op1, MBB, IP);
1981
1982   // 64 x 64 -> 64
1983   if (Class0 == cLong && Class1 == cLong) {
1984     unsigned Tmp1 = makeAnotherReg(Type::IntTy);
1985     unsigned Tmp2 = makeAnotherReg(Type::IntTy);
1986     unsigned Tmp3 = makeAnotherReg(Type::IntTy);
1987     unsigned Tmp4 = makeAnotherReg(Type::IntTy);
1988     BuildMI(*MBB, IP, PPC::MULHWU, 2, Tmp1).addReg(Op0r+1).addReg(Op1r+1);
1989     BuildMI(*MBB, IP, PPC::MULLW, 2, DestReg+1).addReg(Op0r+1).addReg(Op1r+1);
1990     BuildMI(*MBB, IP, PPC::MULLW, 2, Tmp2).addReg(Op0r+1).addReg(Op1r);
1991     BuildMI(*MBB, IP, PPC::ADD, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1992     BuildMI(*MBB, IP, PPC::MULLW, 2, Tmp4).addReg(Op0r).addReg(Op1r+1);
1993     BuildMI(*MBB, IP, PPC::ADD, 2, DestReg).addReg(Tmp3).addReg(Tmp4);
1994     return;
1995   }
1996
1997   // 64 x 32 or less, promote 32 to 64 and do a 64 x 64
1998   if (Class0 == cLong && Class1 <= cInt) {
1999     unsigned Tmp0 = makeAnotherReg(Type::IntTy);
2000     unsigned Tmp1 = makeAnotherReg(Type::IntTy);
2001     unsigned Tmp2 = makeAnotherReg(Type::IntTy);
2002     unsigned Tmp3 = makeAnotherReg(Type::IntTy);
2003     unsigned Tmp4 = makeAnotherReg(Type::IntTy);
2004     if (Op1->getType()->isSigned())
2005       BuildMI(*MBB, IP, PPC::SRAWI, 2, Tmp0).addReg(Op1r).addImm(31);
2006     else
2007       BuildMI(*MBB, IP, PPC::LI, 2, Tmp0).addSImm(0);
2008     BuildMI(*MBB, IP, PPC::MULHWU, 2, Tmp1).addReg(Op0r+1).addReg(Op1r);
2009     BuildMI(*MBB, IP, PPC::MULLW, 2, DestReg+1).addReg(Op0r+1).addReg(Op1r);
2010     BuildMI(*MBB, IP, PPC::MULLW, 2, Tmp2).addReg(Op0r+1).addReg(Tmp0);
2011     BuildMI(*MBB, IP, PPC::ADD, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
2012     BuildMI(*MBB, IP, PPC::MULLW, 2, Tmp4).addReg(Op0r).addReg(Op1r);
2013     BuildMI(*MBB, IP, PPC::ADD, 2, DestReg).addReg(Tmp3).addReg(Tmp4);
2014     return;
2015   }
2016
2017   // 32 x 32 -> 32
2018   if (Class0 <= cInt && Class1 <= cInt) {
2019     BuildMI(*MBB, IP, PPC::MULLW, 2, DestReg).addReg(Op0r).addReg(Op1r);
2020     return;
2021   }
2022
2023   assert(0 && "doMultiply cannot operate on unknown type!");
2024 }
2025
2026 /// doMultiplyConst - This method will multiply the value in Op0 by the
2027 /// value of the ContantInt *CI
2028 void ISel::doMultiplyConst(MachineBasicBlock *MBB,
2029                            MachineBasicBlock::iterator IP,
2030                            unsigned DestReg, Value *Op0, ConstantInt *CI) {
2031   unsigned Class = getClass(Op0->getType());
2032
2033   // Mul op0, 0 ==> 0
2034   if (CI->isNullValue()) {
2035     BuildMI(*MBB, IP, PPC::LI, 1, DestReg).addSImm(0);
2036     if (Class == cLong)
2037       BuildMI(*MBB, IP, PPC::LI, 1, DestReg+1).addSImm(0);
2038     return;
2039   }
2040
2041   // Mul op0, 1 ==> op0
2042   if (CI->equalsInt(1)) {
2043     unsigned Op0r = getReg(Op0, MBB, IP);
2044     BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(Op0r).addReg(Op0r);
2045     if (Class == cLong)
2046       BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(Op0r+1).addReg(Op0r+1);
2047     return;
2048   }
2049
2050   // If the element size is exactly a power of 2, use a shift to get it.
2051   if (unsigned Shift = ExactLog2(CI->getRawValue())) {
2052     ConstantUInt *ShiftCI = ConstantUInt::get(Type::UByteTy, Shift);
2053     emitShiftOperation(MBB, IP, Op0, ShiftCI, true, Op0->getType(), DestReg);
2054     return;
2055   }
2056
2057   // If 32 bits or less and immediate is in right range, emit mul by immediate
2058   if (Class == cByte || Class == cShort || Class == cInt) {
2059     if (canUseAsImmediateForOpcode(CI, 0)) {
2060       unsigned Op0r = getReg(Op0, MBB, IP);
2061       unsigned imm = CI->getRawValue() & 0xFFFF;
2062       BuildMI(*MBB, IP, PPC::MULLI, 2, DestReg).addReg(Op0r).addSImm(imm);
2063       return;
2064     }
2065   }
2066
2067   doMultiply(MBB, IP, DestReg, Op0, CI);
2068 }
2069
2070 void ISel::visitMul(BinaryOperator &I) {
2071   unsigned ResultReg = getReg(I);
2072
2073   Value *Op0 = I.getOperand(0);
2074   Value *Op1 = I.getOperand(1);
2075
2076   MachineBasicBlock::iterator IP = BB->end();
2077   emitMultiply(BB, IP, Op0, Op1, ResultReg);
2078 }
2079
2080 void ISel::emitMultiply(MachineBasicBlock *MBB, MachineBasicBlock::iterator IP,
2081                         Value *Op0, Value *Op1, unsigned DestReg) {
2082   TypeClass Class = getClass(Op0->getType());
2083
2084   switch (Class) {
2085   case cByte:
2086   case cShort:
2087   case cInt:
2088   case cLong:
2089     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2090       doMultiplyConst(MBB, IP, DestReg, Op0, CI);
2091     } else {
2092       doMultiply(MBB, IP, DestReg, Op0, Op1);
2093     }
2094     return;
2095   case cFP32:
2096   case cFP64:
2097     emitBinaryFPOperation(MBB, IP, Op0, Op1, 2, DestReg);
2098     return;
2099     break;
2100   }
2101 }
2102
2103
2104 /// visitDivRem - Handle division and remainder instructions... these
2105 /// instruction both require the same instructions to be generated, they just
2106 /// select the result from a different register.  Note that both of these
2107 /// instructions work differently for signed and unsigned operands.
2108 ///
2109 void ISel::visitDivRem(BinaryOperator &I) {
2110   unsigned ResultReg = getReg(I);
2111   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2112
2113   MachineBasicBlock::iterator IP = BB->end();
2114   emitDivRemOperation(BB, IP, Op0, Op1, I.getOpcode() == Instruction::Div,
2115                       ResultReg);
2116 }
2117
2118 void ISel::emitDivRemOperation(MachineBasicBlock *BB,
2119                                MachineBasicBlock::iterator IP,
2120                                Value *Op0, Value *Op1, bool isDiv,
2121                                unsigned ResultReg) {
2122   const Type *Ty = Op0->getType();
2123   unsigned Class = getClass(Ty);
2124   switch (Class) {
2125   case cFP32:
2126     if (isDiv) {
2127       // Floating point divide...
2128       emitBinaryFPOperation(BB, IP, Op0, Op1, 3, ResultReg);
2129       return;
2130     } else {
2131       // Floating point remainder via fmodf(float x, float y);
2132       unsigned Op0Reg = getReg(Op0, BB, IP);
2133       unsigned Op1Reg = getReg(Op1, BB, IP);
2134       MachineInstr *TheCall =
2135         BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(fmodfFn, true);
2136       std::vector<ValueRecord> Args;
2137       Args.push_back(ValueRecord(Op0Reg, Type::FloatTy));
2138       Args.push_back(ValueRecord(Op1Reg, Type::FloatTy));
2139       doCall(ValueRecord(ResultReg, Type::FloatTy), TheCall, Args, false);
2140       TM.CalledFunctions.insert(fmodfFn);
2141     }
2142     return;
2143   case cFP64:
2144     if (isDiv) {
2145       // Floating point divide...
2146       emitBinaryFPOperation(BB, IP, Op0, Op1, 3, ResultReg);
2147       return;
2148     } else {
2149       // Floating point remainder via fmod(double x, double y);
2150       unsigned Op0Reg = getReg(Op0, BB, IP);
2151       unsigned Op1Reg = getReg(Op1, BB, IP);
2152       MachineInstr *TheCall =
2153         BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(fmodFn, true);
2154       std::vector<ValueRecord> Args;
2155       Args.push_back(ValueRecord(Op0Reg, Type::DoubleTy));
2156       Args.push_back(ValueRecord(Op1Reg, Type::DoubleTy));
2157       doCall(ValueRecord(ResultReg, Type::DoubleTy), TheCall, Args, false);
2158       TM.CalledFunctions.insert(fmodFn);
2159     }
2160     return;
2161   case cLong: {
2162     static Function* const Funcs[] =
2163       { __moddi3Fn, __divdi3Fn, __umoddi3Fn, __udivdi3Fn };
2164     unsigned Op0Reg = getReg(Op0, BB, IP);
2165     unsigned Op1Reg = getReg(Op1, BB, IP);
2166     unsigned NameIdx = Ty->isUnsigned()*2 + isDiv;
2167     MachineInstr *TheCall =
2168       BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(Funcs[NameIdx], true);
2169
2170     std::vector<ValueRecord> Args;
2171     Args.push_back(ValueRecord(Op0Reg, Type::LongTy));
2172     Args.push_back(ValueRecord(Op1Reg, Type::LongTy));
2173     doCall(ValueRecord(ResultReg, Type::LongTy), TheCall, Args, false);
2174     TM.CalledFunctions.insert(Funcs[NameIdx]);
2175     return;
2176   }
2177   case cByte: case cShort: case cInt:
2178     break;          // Small integrals, handled below...
2179   default: assert(0 && "Unknown class!");
2180   }
2181
2182   // Special case signed division by power of 2.
2183   if (isDiv)
2184     if (ConstantSInt *CI = dyn_cast<ConstantSInt>(Op1)) {
2185       assert(Class != cLong && "This doesn't handle 64-bit divides!");
2186       int V = CI->getValue();
2187
2188       if (V == 1) {       // X /s 1 => X
2189         unsigned Op0Reg = getReg(Op0, BB, IP);
2190         BuildMI(*BB, IP, PPC::OR, 2, ResultReg).addReg(Op0Reg).addReg(Op0Reg);
2191         return;
2192       }
2193
2194       if (V == -1) {      // X /s -1 => -X
2195         unsigned Op0Reg = getReg(Op0, BB, IP);
2196         BuildMI(*BB, IP, PPC::NEG, 1, ResultReg).addReg(Op0Reg);
2197         return;
2198       }
2199
2200       unsigned log2V = ExactLog2(V);
2201       if (log2V != 0 && Ty->isSigned()) {
2202         unsigned Op0Reg = getReg(Op0, BB, IP);
2203         unsigned TmpReg = makeAnotherReg(Op0->getType());
2204
2205         BuildMI(*BB, IP, PPC::SRAWI, 2, TmpReg).addReg(Op0Reg).addImm(log2V);
2206         BuildMI(*BB, IP, PPC::ADDZE, 1, ResultReg).addReg(TmpReg);
2207         return;
2208       }
2209     }
2210
2211   unsigned Op0Reg = getReg(Op0, BB, IP);
2212   unsigned Op1Reg = getReg(Op1, BB, IP);
2213   unsigned Opcode = Ty->isSigned() ? PPC::DIVW : PPC::DIVWU;
2214
2215   if (isDiv) {
2216     BuildMI(*BB, IP, Opcode, 2, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
2217   } else { // Remainder
2218     unsigned TmpReg1 = makeAnotherReg(Op0->getType());
2219     unsigned TmpReg2 = makeAnotherReg(Op0->getType());
2220
2221     BuildMI(*BB, IP, Opcode, 2, TmpReg1).addReg(Op0Reg).addReg(Op1Reg);
2222     BuildMI(*BB, IP, PPC::MULLW, 2, TmpReg2).addReg(TmpReg1).addReg(Op1Reg);
2223     BuildMI(*BB, IP, PPC::SUBF, 2, ResultReg).addReg(TmpReg2).addReg(Op0Reg);
2224   }
2225 }
2226
2227
2228 /// Shift instructions: 'shl', 'sar', 'shr' - Some special cases here
2229 /// for constant immediate shift values, and for constant immediate
2230 /// shift values equal to 1. Even the general case is sort of special,
2231 /// because the shift amount has to be in CL, not just any old register.
2232 ///
2233 void ISel::visitShiftInst(ShiftInst &I) {
2234   MachineBasicBlock::iterator IP = BB->end();
2235   emitShiftOperation(BB, IP, I.getOperand(0), I.getOperand(1),
2236                      I.getOpcode() == Instruction::Shl, I.getType(),
2237                      getReg(I));
2238 }
2239
2240 /// emitShiftOperation - Common code shared between visitShiftInst and
2241 /// constant expression support.
2242 ///
2243 void ISel::emitShiftOperation(MachineBasicBlock *MBB,
2244                               MachineBasicBlock::iterator IP,
2245                               Value *Op, Value *ShiftAmount, bool isLeftShift,
2246                               const Type *ResultTy, unsigned DestReg) {
2247   unsigned SrcReg = getReg (Op, MBB, IP);
2248   bool isSigned = ResultTy->isSigned ();
2249   unsigned Class = getClass (ResultTy);
2250
2251   // Longs, as usual, are handled specially...
2252   if (Class == cLong) {
2253     // If we have a constant shift, we can generate much more efficient code
2254     // than otherwise...
2255     //
2256     if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
2257       unsigned Amount = CUI->getValue();
2258       if (Amount < 32) {
2259         if (isLeftShift) {
2260           // FIXME: RLWIMI is a use-and-def of DestReg+1, but that violates SSA
2261           BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
2262             .addImm(Amount).addImm(0).addImm(31-Amount);
2263           BuildMI(*MBB, IP, PPC::RLWIMI, 5).addReg(DestReg).addReg(SrcReg+1)
2264             .addImm(Amount).addImm(32-Amount).addImm(31);
2265           BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg+1).addReg(SrcReg+1)
2266             .addImm(Amount).addImm(0).addImm(31-Amount);
2267         } else {
2268           // FIXME: RLWIMI is a use-and-def of DestReg, but that violates SSA
2269           BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg+1).addReg(SrcReg+1)
2270             .addImm(32-Amount).addImm(Amount).addImm(31);
2271           BuildMI(*MBB, IP, PPC::RLWIMI, 5).addReg(DestReg+1).addReg(SrcReg)
2272             .addImm(32-Amount).addImm(0).addImm(Amount-1);
2273           BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
2274             .addImm(32-Amount).addImm(Amount).addImm(31);
2275         }
2276       } else {                 // Shifting more than 32 bits
2277         Amount -= 32;
2278         if (isLeftShift) {
2279           if (Amount != 0) {
2280             BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg+1)
2281               .addImm(Amount).addImm(0).addImm(31-Amount);
2282           } else {
2283             BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg+1)
2284               .addReg(SrcReg+1);
2285           }
2286           BuildMI(*MBB, IP, PPC::LI, 1, DestReg+1).addSImm(0);
2287         } else {
2288           if (Amount != 0) {
2289             if (isSigned)
2290               BuildMI(*MBB, IP, PPC::SRAWI, 2, DestReg+1).addReg(SrcReg)
2291                 .addImm(Amount);
2292             else
2293               BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg+1).addReg(SrcReg)
2294                 .addImm(32-Amount).addImm(Amount).addImm(31);
2295           } else {
2296             BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg)
2297               .addReg(SrcReg);
2298           }
2299           BuildMI(*MBB, IP,PPC::LI, 1, DestReg).addSImm(0);
2300         }
2301       }
2302     } else {
2303       unsigned TmpReg1 = makeAnotherReg(Type::IntTy);
2304       unsigned TmpReg2 = makeAnotherReg(Type::IntTy);
2305       unsigned TmpReg3 = makeAnotherReg(Type::IntTy);
2306       unsigned TmpReg4 = makeAnotherReg(Type::IntTy);
2307       unsigned TmpReg5 = makeAnotherReg(Type::IntTy);
2308       unsigned TmpReg6 = makeAnotherReg(Type::IntTy);
2309       unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
2310
2311       if (isLeftShift) {
2312         BuildMI(*MBB, IP, PPC::SUBFIC, 2, TmpReg1).addReg(ShiftAmountReg)
2313           .addSImm(32);
2314         BuildMI(*MBB, IP, PPC::SLW, 2, TmpReg2).addReg(SrcReg)
2315           .addReg(ShiftAmountReg);
2316         BuildMI(*MBB, IP, PPC::SRW, 2, TmpReg3).addReg(SrcReg+1)
2317           .addReg(TmpReg1);
2318         BuildMI(*MBB, IP, PPC::OR, 2,TmpReg4).addReg(TmpReg2).addReg(TmpReg3);
2319         BuildMI(*MBB, IP, PPC::ADDI, 2, TmpReg5).addReg(ShiftAmountReg)
2320           .addSImm(-32);
2321         BuildMI(*MBB, IP, PPC::SLW, 2, TmpReg6).addReg(SrcReg+1)
2322           .addReg(TmpReg5);
2323         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(TmpReg4)
2324           .addReg(TmpReg6);
2325         BuildMI(*MBB, IP, PPC::SLW, 2, DestReg+1).addReg(SrcReg+1)
2326           .addReg(ShiftAmountReg);
2327       } else {
2328         if (isSigned) { // shift right algebraic
2329           MachineBasicBlock *TmpMBB =new MachineBasicBlock(BB->getBasicBlock());
2330           MachineBasicBlock *PhiMBB =new MachineBasicBlock(BB->getBasicBlock());
2331           MachineBasicBlock *OldMBB = BB;
2332           ilist<MachineBasicBlock>::iterator It = BB; ++It;
2333           F->getBasicBlockList().insert(It, TmpMBB);
2334           F->getBasicBlockList().insert(It, PhiMBB);
2335           BB->addSuccessor(TmpMBB);
2336           BB->addSuccessor(PhiMBB);
2337
2338           BuildMI(*MBB, IP, PPC::SUBFIC, 2, TmpReg1).addReg(ShiftAmountReg)
2339             .addSImm(32);
2340           BuildMI(*MBB, IP, PPC::SRW, 2, TmpReg2).addReg(SrcReg+1)
2341             .addReg(ShiftAmountReg);
2342           BuildMI(*MBB, IP, PPC::SLW, 2, TmpReg3).addReg(SrcReg)
2343             .addReg(TmpReg1);
2344           BuildMI(*MBB, IP, PPC::OR, 2, TmpReg4).addReg(TmpReg2)
2345             .addReg(TmpReg3);
2346           BuildMI(*MBB, IP, PPC::ADDICo, 2, TmpReg5).addReg(ShiftAmountReg)
2347             .addSImm(-32);
2348           BuildMI(*MBB, IP, PPC::SRAW, 2, TmpReg6).addReg(SrcReg)
2349             .addReg(TmpReg5);
2350           BuildMI(*MBB, IP, PPC::SRAW, 2, DestReg).addReg(SrcReg)
2351             .addReg(ShiftAmountReg);
2352           BuildMI(*MBB, IP, PPC::BLE, 2).addReg(PPC::CR0).addMBB(PhiMBB);
2353
2354           // OrMBB:
2355           //   Select correct least significant half if the shift amount > 32
2356           BB = TmpMBB;
2357           unsigned OrReg = makeAnotherReg(Type::IntTy);
2358           BuildMI(BB, PPC::OR, 2, OrReg).addReg(TmpReg6).addImm(TmpReg6);
2359           TmpMBB->addSuccessor(PhiMBB);
2360
2361           BB = PhiMBB;
2362           BuildMI(BB, PPC::PHI, 4, DestReg+1).addReg(TmpReg4).addMBB(OldMBB)
2363             .addReg(OrReg).addMBB(TmpMBB);
2364         } else { // shift right logical
2365           BuildMI(*MBB, IP, PPC::SUBFIC, 2, TmpReg1).addReg(ShiftAmountReg)
2366             .addSImm(32);
2367           BuildMI(*MBB, IP, PPC::SRW, 2, TmpReg2).addReg(SrcReg+1)
2368             .addReg(ShiftAmountReg);
2369           BuildMI(*MBB, IP, PPC::SLW, 2, TmpReg3).addReg(SrcReg)
2370             .addReg(TmpReg1);
2371           BuildMI(*MBB, IP, PPC::OR, 2, TmpReg4).addReg(TmpReg2)
2372             .addReg(TmpReg3);
2373           BuildMI(*MBB, IP, PPC::ADDI, 2, TmpReg5).addReg(ShiftAmountReg)
2374             .addSImm(-32);
2375           BuildMI(*MBB, IP, PPC::SRW, 2, TmpReg6).addReg(SrcReg)
2376             .addReg(TmpReg5);
2377           BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(TmpReg4)
2378             .addReg(TmpReg6);
2379           BuildMI(*MBB, IP, PPC::SRW, 2, DestReg).addReg(SrcReg)
2380             .addReg(ShiftAmountReg);
2381         }
2382       }
2383     }
2384     return;
2385   }
2386
2387   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(ShiftAmount)) {
2388     // The shift amount is constant, guaranteed to be a ubyte. Get its value.
2389     assert(CUI->getType() == Type::UByteTy && "Shift amount not a ubyte?");
2390     unsigned Amount = CUI->getValue();
2391
2392     if (isLeftShift) {
2393       BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
2394         .addImm(Amount).addImm(0).addImm(31-Amount);
2395     } else {
2396       if (isSigned) {
2397         BuildMI(*MBB, IP, PPC::SRAWI,2,DestReg).addReg(SrcReg).addImm(Amount);
2398       } else {
2399         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
2400           .addImm(32-Amount).addImm(Amount).addImm(31);
2401       }
2402     }
2403   } else {                  // The shift amount is non-constant.
2404     unsigned ShiftAmountReg = getReg (ShiftAmount, MBB, IP);
2405
2406     if (isLeftShift) {
2407       BuildMI(*MBB, IP, PPC::SLW, 2, DestReg).addReg(SrcReg)
2408         .addReg(ShiftAmountReg);
2409     } else {
2410       BuildMI(*MBB, IP, isSigned ? PPC::SRAW : PPC::SRW, 2, DestReg)
2411         .addReg(SrcReg).addReg(ShiftAmountReg);
2412     }
2413   }
2414 }
2415
2416 /// LoadNeedsSignExtend - On PowerPC, there is no load byte with sign extend.
2417 /// Therefore, if this is a byte load and the destination type is signed, we
2418 /// would normall need to also emit a sign extend instruction after the load.
2419 /// However, store instructions don't care whether a signed type was sign
2420 /// extended across a whole register.  Also, a SetCC instruction will emit its
2421 /// own sign extension to force the value into the appropriate range, so we
2422 /// need not emit it here.  Ideally, this kind of thing wouldn't be necessary
2423 /// once LLVM's type system is improved.
2424 static bool LoadNeedsSignExtend(LoadInst &LI) {
2425   if (cByte == getClassB(LI.getType()) && LI.getType()->isSigned()) {
2426     bool AllUsesAreStoresOrSetCC = true;
2427     for (Value::use_iterator I = LI.use_begin(), E = LI.use_end(); I != E; ++I)
2428       if (!isa<StoreInst>(*I) && !isa<SetCondInst>(*I)) {
2429         AllUsesAreStoresOrSetCC = false;
2430         break;
2431       }
2432     if (!AllUsesAreStoresOrSetCC)
2433       return true;
2434   }
2435   return false;
2436 }
2437
2438 /// visitLoadInst - Implement LLVM load instructions.  Pretty straightforward
2439 /// mapping of LLVM classes to PPC load instructions, with the exception of
2440 /// signed byte loads, which need a sign extension following them.
2441 ///
2442 void ISel::visitLoadInst(LoadInst &I) {
2443   // Immediate opcodes, for reg+imm addressing
2444   static const unsigned ImmOpcodes[] = {
2445     PPC::LBZ, PPC::LHZ, PPC::LWZ,
2446     PPC::LFS, PPC::LFD, PPC::LWZ
2447   };
2448   // Indexed opcodes, for reg+reg addressing
2449   static const unsigned IdxOpcodes[] = {
2450     PPC::LBZX, PPC::LHZX, PPC::LWZX,
2451     PPC::LFSX, PPC::LFDX, PPC::LWZX
2452   };
2453
2454   unsigned Class     = getClassB(I.getType());
2455   unsigned ImmOpcode = ImmOpcodes[Class];
2456   unsigned IdxOpcode = IdxOpcodes[Class];
2457   unsigned DestReg   = getReg(I);
2458   Value *SourceAddr  = I.getOperand(0);
2459
2460   if (Class == cShort && I.getType()->isSigned()) ImmOpcode = PPC::LHA;
2461   if (Class == cShort && I.getType()->isSigned()) IdxOpcode = PPC::LHAX;
2462
2463   if (AllocaInst *AI = dyn_castFixedAlloca(SourceAddr)) {
2464     unsigned FI = getFixedSizedAllocaFI(AI);
2465     if (Class == cLong) {
2466       addFrameReference(BuildMI(BB, ImmOpcode, 2, DestReg), FI);
2467       addFrameReference(BuildMI(BB, ImmOpcode, 2, DestReg+1), FI, 4);
2468     } else if (LoadNeedsSignExtend(I)) {
2469       unsigned TmpReg = makeAnotherReg(I.getType());
2470       addFrameReference(BuildMI(BB, ImmOpcode, 2, TmpReg), FI);
2471       BuildMI(BB, PPC::EXTSB, 1, DestReg).addReg(TmpReg);
2472     } else {
2473       addFrameReference(BuildMI(BB, ImmOpcode, 2, DestReg), FI);
2474     }
2475     return;
2476   }
2477
2478   // If this load is the only use of the GEP instruction that is its address,
2479   // then we can fold the GEP directly into the load instruction.
2480   // emitGEPOperation with a second to last arg of 'true' will place the
2481   // base register for the GEP into baseReg, and the constant offset from that
2482   // into offset.  If the offset fits in 16 bits, we can emit a reg+imm store
2483   // otherwise, we copy the offset into another reg, and use reg+reg addressing.
2484   if (GetElementPtrInst *GEPI = canFoldGEPIntoLoadOrStore(SourceAddr)) {
2485     unsigned baseReg = getReg(GEPI);
2486     unsigned pendingAdd;
2487     ConstantSInt *offset;
2488
2489     emitGEPOperation(BB, BB->end(), GEPI->getOperand(0), GEPI->op_begin()+1,
2490                      GEPI->op_end(), baseReg, true, &offset, &pendingAdd);
2491
2492     if (pendingAdd == 0 && Class != cLong &&
2493         canUseAsImmediateForOpcode(offset, 0)) {
2494       if (LoadNeedsSignExtend(I)) {
2495         unsigned TmpReg = makeAnotherReg(I.getType());
2496         BuildMI(BB, ImmOpcode, 2, TmpReg).addSImm(offset->getValue())
2497           .addReg(baseReg);
2498         BuildMI(BB, PPC::EXTSB, 1, DestReg).addReg(TmpReg);
2499       } else {
2500         BuildMI(BB, ImmOpcode, 2, DestReg).addSImm(offset->getValue())
2501           .addReg(baseReg);
2502       }
2503       return;
2504     }
2505
2506     unsigned indexReg = (pendingAdd != 0) ? pendingAdd : getReg(offset);
2507
2508     if (Class == cLong) {
2509       unsigned indexPlus4 = makeAnotherReg(Type::IntTy);
2510       BuildMI(BB, PPC::ADDI, 2, indexPlus4).addReg(indexReg).addSImm(4);
2511       BuildMI(BB, IdxOpcode, 2, DestReg).addReg(indexReg).addReg(baseReg);
2512       BuildMI(BB, IdxOpcode, 2, DestReg+1).addReg(indexPlus4).addReg(baseReg);
2513     } else if (LoadNeedsSignExtend(I)) {
2514       unsigned TmpReg = makeAnotherReg(I.getType());
2515       BuildMI(BB, IdxOpcode, 2, TmpReg).addReg(indexReg).addReg(baseReg);
2516       BuildMI(BB, PPC::EXTSB, 1, DestReg).addReg(TmpReg);
2517     } else {
2518       BuildMI(BB, IdxOpcode, 2, DestReg).addReg(indexReg).addReg(baseReg);
2519     }
2520     return;
2521   }
2522
2523   // The fallback case, where the load was from a source that could not be
2524   // folded into the load instruction.
2525   unsigned SrcAddrReg = getReg(SourceAddr);
2526
2527   if (Class == cLong) {
2528     BuildMI(BB, ImmOpcode, 2, DestReg).addSImm(0).addReg(SrcAddrReg);
2529     BuildMI(BB, ImmOpcode, 2, DestReg+1).addSImm(4).addReg(SrcAddrReg);
2530   } else if (LoadNeedsSignExtend(I)) {
2531     unsigned TmpReg = makeAnotherReg(I.getType());
2532     BuildMI(BB, ImmOpcode, 2, TmpReg).addSImm(0).addReg(SrcAddrReg);
2533     BuildMI(BB, PPC::EXTSB, 1, DestReg).addReg(TmpReg);
2534   } else {
2535     BuildMI(BB, ImmOpcode, 2, DestReg).addSImm(0).addReg(SrcAddrReg);
2536   }
2537 }
2538
2539 /// visitStoreInst - Implement LLVM store instructions
2540 ///
2541 void ISel::visitStoreInst(StoreInst &I) {
2542   // Immediate opcodes, for reg+imm addressing
2543   static const unsigned ImmOpcodes[] = {
2544     PPC::STB, PPC::STH, PPC::STW,
2545     PPC::STFS, PPC::STFD, PPC::STW
2546   };
2547   // Indexed opcodes, for reg+reg addressing
2548   static const unsigned IdxOpcodes[] = {
2549     PPC::STBX, PPC::STHX, PPC::STWX,
2550     PPC::STFSX, PPC::STFDX, PPC::STWX
2551   };
2552
2553   Value *SourceAddr  = I.getOperand(1);
2554   const Type *ValTy  = I.getOperand(0)->getType();
2555   unsigned Class     = getClassB(ValTy);
2556   unsigned ImmOpcode = ImmOpcodes[Class];
2557   unsigned IdxOpcode = IdxOpcodes[Class];
2558   unsigned ValReg    = getReg(I.getOperand(0));
2559
2560   // If this store is the only use of the GEP instruction that is its address,
2561   // then we can fold the GEP directly into the store instruction.
2562   // emitGEPOperation with a second to last arg of 'true' will place the
2563   // base register for the GEP into baseReg, and the constant offset from that
2564   // into offset.  If the offset fits in 16 bits, we can emit a reg+imm store
2565   // otherwise, we copy the offset into another reg, and use reg+reg addressing.
2566   if (GetElementPtrInst *GEPI = canFoldGEPIntoLoadOrStore(SourceAddr)) {
2567     unsigned baseReg = getReg(GEPI);
2568     unsigned pendingAdd;
2569     ConstantSInt *offset;
2570
2571     emitGEPOperation(BB, BB->end(), GEPI->getOperand(0), GEPI->op_begin()+1,
2572                      GEPI->op_end(), baseReg, true, &offset, &pendingAdd);
2573
2574     if (0 == pendingAdd && Class != cLong &&
2575         canUseAsImmediateForOpcode(offset, 0)) {
2576       BuildMI(BB, ImmOpcode, 3).addReg(ValReg).addSImm(offset->getValue())
2577         .addReg(baseReg);
2578       return;
2579     }
2580
2581     unsigned indexReg = (pendingAdd != 0) ? pendingAdd : getReg(offset);
2582
2583     if (Class == cLong) {
2584       unsigned indexPlus4 = makeAnotherReg(Type::IntTy);
2585       BuildMI(BB, PPC::ADDI, 2, indexPlus4).addReg(indexReg).addSImm(4);
2586       BuildMI(BB, IdxOpcode, 3).addReg(ValReg).addReg(indexReg).addReg(baseReg);
2587       BuildMI(BB, IdxOpcode, 3).addReg(ValReg+1).addReg(indexPlus4)
2588         .addReg(baseReg);
2589       return;
2590     }
2591     BuildMI(BB, IdxOpcode, 3).addReg(ValReg).addReg(indexReg).addReg(baseReg);
2592     return;
2593   }
2594
2595   // If the store address wasn't the only use of a GEP, we fall back to the
2596   // standard path: store the ValReg at the value in AddressReg.
2597   unsigned AddressReg  = getReg(I.getOperand(1));
2598   if (Class == cLong) {
2599     BuildMI(BB, ImmOpcode, 3).addReg(ValReg).addSImm(0).addReg(AddressReg);
2600     BuildMI(BB, ImmOpcode, 3).addReg(ValReg+1).addSImm(4).addReg(AddressReg);
2601     return;
2602   }
2603   BuildMI(BB, ImmOpcode, 3).addReg(ValReg).addSImm(0).addReg(AddressReg);
2604 }
2605
2606
2607 /// visitCastInst - Here we have various kinds of copying with or without sign
2608 /// extension going on.
2609 ///
2610 void ISel::visitCastInst(CastInst &CI) {
2611   Value *Op = CI.getOperand(0);
2612
2613   unsigned SrcClass = getClassB(Op->getType());
2614   unsigned DestClass = getClassB(CI.getType());
2615
2616   // If this is a cast from a 32-bit integer to a Long type, and the only uses
2617   // of the cast are GEP instructions, then the cast does not need to be
2618   // generated explicitly, it will be folded into the GEP.
2619   if (DestClass == cLong && SrcClass == cInt) {
2620     bool AllUsesAreGEPs = true;
2621     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
2622       if (!isa<GetElementPtrInst>(*I)) {
2623         AllUsesAreGEPs = false;
2624         break;
2625       }
2626     if (AllUsesAreGEPs) return;
2627   }
2628
2629   unsigned DestReg = getReg(CI);
2630   MachineBasicBlock::iterator MI = BB->end();
2631
2632   // If this is a cast from an byte, short, or int to an integer type of equal
2633   // or lesser width, and all uses of the cast are store instructions then dont
2634   // emit them, as the store instruction will implicitly not store the zero or
2635   // sign extended bytes.
2636   if (SrcClass <= cInt && SrcClass >= DestClass) {
2637     bool AllUsesAreStoresOrSetCC = true;
2638     for (Value::use_iterator I = CI.use_begin(), E = CI.use_end(); I != E; ++I)
2639       if (!isa<StoreInst>(*I) && !isa<SetCondInst>(*I)) {
2640         AllUsesAreStoresOrSetCC = false;
2641         break;
2642       }
2643     // Turn this cast directly into a move instruction, which the register
2644     // allocator will deal with.
2645     if (AllUsesAreStoresOrSetCC) {
2646       unsigned SrcReg = getReg(Op, BB, MI);
2647       BuildMI(*BB, MI, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
2648       return;
2649     }
2650   }
2651   emitCastOperation(BB, MI, Op, CI.getType(), DestReg);
2652 }
2653
2654 /// emitCastOperation - Common code shared between visitCastInst and constant
2655 /// expression cast support.
2656 ///
2657 void ISel::emitCastOperation(MachineBasicBlock *MBB,
2658                              MachineBasicBlock::iterator IP,
2659                              Value *Src, const Type *DestTy,
2660                              unsigned DestReg) {
2661   const Type *SrcTy = Src->getType();
2662   unsigned SrcClass = getClassB(SrcTy);
2663   unsigned DestClass = getClassB(DestTy);
2664   unsigned SrcReg = getReg(Src, MBB, IP);
2665
2666   // Implement casts to bool by using compare on the operand followed by set if
2667   // not zero on the result.
2668   if (DestTy == Type::BoolTy) {
2669     switch (SrcClass) {
2670     case cByte:
2671     case cShort:
2672     case cInt: {
2673       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2674       BuildMI(*MBB, IP, PPC::ADDIC, 2, TmpReg).addReg(SrcReg).addSImm(-1);
2675       BuildMI(*MBB, IP, PPC::SUBFE, 2, DestReg).addReg(TmpReg).addReg(SrcReg);
2676       break;
2677     }
2678     case cLong: {
2679       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2680       unsigned SrcReg2 = makeAnotherReg(Type::IntTy);
2681       BuildMI(*MBB, IP, PPC::OR, 2, SrcReg2).addReg(SrcReg).addReg(SrcReg+1);
2682       BuildMI(*MBB, IP, PPC::ADDIC, 2, TmpReg).addReg(SrcReg2).addSImm(-1);
2683       BuildMI(*MBB, IP, PPC::SUBFE, 2, DestReg).addReg(TmpReg)
2684         .addReg(SrcReg2);
2685       break;
2686     }
2687     case cFP32:
2688     case cFP64:
2689       unsigned TmpReg = makeAnotherReg(Type::IntTy);
2690       unsigned ConstZero = getReg(ConstantFP::get(Type::DoubleTy, 0.0), BB, IP);
2691       BuildMI(*MBB, IP, PPC::FCMPU, PPC::CR7).addReg(SrcReg).addReg(ConstZero);
2692       BuildMI(*MBB, IP, PPC::MFCR, TmpReg);
2693       BuildMI(*MBB, IP, PPC::RLWINM, DestReg).addReg(TmpReg).addImm(31)
2694         .addImm(31).addImm(31);
2695     }
2696     return;
2697   }
2698
2699   // Handle cast of Float -> Double
2700   if (SrcClass == cFP32 && DestClass == cFP64) {
2701     BuildMI(*MBB, IP, PPC::FMR, 1, DestReg).addReg(SrcReg);
2702     return;
2703   }
2704
2705   // Handle cast of Double -> Float
2706   if (SrcClass == cFP64 && DestClass == cFP32) {
2707     BuildMI(*MBB, IP, PPC::FRSP, 1, DestReg).addReg(SrcReg);
2708     return;
2709   }
2710
2711   // Handle casts from integer to floating point now...
2712   if (DestClass == cFP32 || DestClass == cFP64) {
2713
2714     // Emit a library call for long to float conversion
2715     if (SrcClass == cLong) {
2716       Function *floatFn = (DestClass == cFP32) ? __floatdisfFn : __floatdidfFn;
2717       if (SrcTy->isSigned()) {
2718         std::vector<ValueRecord> Args;
2719         Args.push_back(ValueRecord(SrcReg, SrcTy));
2720         MachineInstr *TheCall =
2721           BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(floatFn, true);
2722         doCall(ValueRecord(DestReg, DestTy), TheCall, Args, false);
2723         TM.CalledFunctions.insert(floatFn);
2724       } else {
2725         std::vector<ValueRecord> CmpArgs, ClrArgs, SetArgs;
2726         unsigned ZeroLong = getReg(ConstantUInt::get(SrcTy, 0));
2727         unsigned CondReg = makeAnotherReg(Type::IntTy);
2728
2729         // Update machine-CFG edges
2730         MachineBasicBlock *ClrMBB = new MachineBasicBlock(BB->getBasicBlock());
2731         MachineBasicBlock *SetMBB = new MachineBasicBlock(BB->getBasicBlock());
2732         MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
2733         MachineBasicBlock *OldMBB = BB;
2734         ilist<MachineBasicBlock>::iterator It = BB; ++It;
2735         F->getBasicBlockList().insert(It, ClrMBB);
2736         F->getBasicBlockList().insert(It, SetMBB);
2737         F->getBasicBlockList().insert(It, PhiMBB);
2738         BB->addSuccessor(ClrMBB);
2739         BB->addSuccessor(SetMBB);
2740
2741         CmpArgs.push_back(ValueRecord(SrcReg, SrcTy));
2742         CmpArgs.push_back(ValueRecord(ZeroLong, SrcTy));
2743         MachineInstr *TheCall =
2744           BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(__cmpdi2Fn, true);
2745         doCall(ValueRecord(CondReg, Type::IntTy), TheCall, CmpArgs, false);
2746         TM.CalledFunctions.insert(__cmpdi2Fn);
2747         BuildMI(*MBB, IP, PPC::CMPWI, 2, PPC::CR0).addReg(CondReg).addSImm(0);
2748         BuildMI(*MBB, IP, PPC::BLE, 2).addReg(PPC::CR0).addMBB(SetMBB);
2749
2750         // ClrMBB
2751         BB = ClrMBB;
2752         unsigned ClrReg = makeAnotherReg(DestTy);
2753         ClrArgs.push_back(ValueRecord(SrcReg, SrcTy));
2754         TheCall = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(floatFn, true);
2755         doCall(ValueRecord(ClrReg, DestTy), TheCall, ClrArgs, false);
2756         TM.CalledFunctions.insert(floatFn);
2757         BuildMI(BB, PPC::B, 1).addMBB(PhiMBB);
2758         BB->addSuccessor(PhiMBB);
2759
2760         // SetMBB
2761         BB = SetMBB;
2762         unsigned SetReg = makeAnotherReg(DestTy);
2763         unsigned CallReg = makeAnotherReg(DestTy);
2764         unsigned ShiftedReg = makeAnotherReg(SrcTy);
2765         ConstantSInt *Const1 = ConstantSInt::get(Type::IntTy, 1);
2766         emitShiftOperation(BB, BB->end(), Src, Const1, false, SrcTy, ShiftedReg);
2767         SetArgs.push_back(ValueRecord(ShiftedReg, SrcTy));
2768         TheCall = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(floatFn, true);
2769         doCall(ValueRecord(CallReg, DestTy), TheCall, SetArgs, false);
2770         TM.CalledFunctions.insert(floatFn);
2771         unsigned SetOpcode = (DestClass == cFP32) ? PPC::FADDS : PPC::FADD;
2772         BuildMI(BB, SetOpcode, 2, SetReg).addReg(CallReg).addReg(CallReg);
2773         BB->addSuccessor(PhiMBB);
2774
2775         // PhiMBB
2776         BB = PhiMBB;
2777         BuildMI(BB, PPC::PHI, 4, DestReg).addReg(ClrReg).addMBB(ClrMBB)
2778           .addReg(SetReg).addMBB(SetMBB);
2779       }
2780       return;
2781     }
2782
2783     // Make sure we're dealing with a full 32 bits
2784     unsigned TmpReg = makeAnotherReg(Type::IntTy);
2785     promote32(TmpReg, ValueRecord(SrcReg, SrcTy));
2786
2787     SrcReg = TmpReg;
2788
2789     // Spill the integer to memory and reload it from there.
2790     // Also spill room for a special conversion constant
2791     int ValueFrameIdx =
2792       F->getFrameInfo()->CreateStackObject(Type::DoubleTy, TM.getTargetData());
2793
2794     MachineConstantPool *CP = F->getConstantPool();
2795     unsigned constantHi = makeAnotherReg(Type::IntTy);
2796     unsigned TempF = makeAnotherReg(Type::DoubleTy);
2797
2798     if (!SrcTy->isSigned()) {
2799       ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, 0x1.000000p52);
2800       unsigned ConstF = getReg(CFP, BB, IP);
2801       BuildMI(*MBB, IP, PPC::LIS, 1, constantHi).addSImm(0x4330);
2802       addFrameReference(BuildMI(*MBB, IP, PPC::STW, 3).addReg(constantHi),
2803                         ValueFrameIdx);
2804       addFrameReference(BuildMI(*MBB, IP, PPC::STW, 3).addReg(SrcReg),
2805                         ValueFrameIdx, 4);
2806       addFrameReference(BuildMI(*MBB, IP, PPC::LFD, 2, TempF), ValueFrameIdx);
2807       BuildMI(*MBB, IP, PPC::FSUB, 2, DestReg).addReg(TempF).addReg(ConstF);
2808     } else {
2809       ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, 0x1.000008p52);
2810       unsigned ConstF = getReg(CFP, BB, IP);
2811       unsigned TempLo = makeAnotherReg(Type::IntTy);
2812       BuildMI(*MBB, IP, PPC::LIS, 1, constantHi).addSImm(0x4330);
2813       addFrameReference(BuildMI(*MBB, IP, PPC::STW, 3).addReg(constantHi),
2814                         ValueFrameIdx);
2815       BuildMI(*MBB, IP, PPC::XORIS, 2, TempLo).addReg(SrcReg).addImm(0x8000);
2816       addFrameReference(BuildMI(*MBB, IP, PPC::STW, 3).addReg(TempLo),
2817                         ValueFrameIdx, 4);
2818       addFrameReference(BuildMI(*MBB, IP, PPC::LFD, 2, TempF), ValueFrameIdx);
2819       BuildMI(*MBB, IP, PPC::FSUB, 2, DestReg).addReg(TempF).addReg(ConstF);
2820     }
2821     return;
2822   }
2823
2824   // Handle casts from floating point to integer now...
2825   if (SrcClass == cFP32 || SrcClass == cFP64) {
2826     static Function* const Funcs[] =
2827       { __fixsfdiFn, __fixdfdiFn, __fixunssfdiFn, __fixunsdfdiFn };
2828     // emit library call
2829     if (DestClass == cLong) {
2830       bool isDouble = SrcClass == cFP64;
2831       unsigned nameIndex = 2 * DestTy->isSigned() + isDouble;
2832       std::vector<ValueRecord> Args;
2833       Args.push_back(ValueRecord(SrcReg, SrcTy));
2834       Function *floatFn = Funcs[nameIndex];
2835       MachineInstr *TheCall =
2836         BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(floatFn, true);
2837       doCall(ValueRecord(DestReg, DestTy), TheCall, Args, false);
2838       TM.CalledFunctions.insert(floatFn);
2839       return;
2840     }
2841
2842     int ValueFrameIdx =
2843       F->getFrameInfo()->CreateStackObject(Type::DoubleTy, TM.getTargetData());
2844
2845     if (DestTy->isSigned()) {
2846       unsigned TempReg = makeAnotherReg(Type::DoubleTy);
2847
2848       // Convert to integer in the FP reg and store it to a stack slot
2849       BuildMI(*MBB, IP, PPC::FCTIWZ, 1, TempReg).addReg(SrcReg);
2850       addFrameReference(BuildMI(*MBB, IP, PPC::STFD, 3)
2851                           .addReg(TempReg), ValueFrameIdx);
2852
2853       // There is no load signed byte opcode, so we must emit a sign extend for
2854       // that particular size.  Make sure to source the new integer from the
2855       // correct offset.
2856       if (DestClass == cByte) {
2857         unsigned TempReg2 = makeAnotherReg(DestTy);
2858         addFrameReference(BuildMI(*MBB, IP, PPC::LBZ, 2, TempReg2),
2859                           ValueFrameIdx, 7);
2860         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(TempReg2);
2861       } else {
2862         int offset = (DestClass == cShort) ? 6 : 4;
2863         unsigned LoadOp = (DestClass == cShort) ? PPC::LHA : PPC::LWZ;
2864         addFrameReference(BuildMI(*MBB, IP, LoadOp, 2, DestReg),
2865                           ValueFrameIdx, offset);
2866       }
2867     } else {
2868       unsigned Zero = getReg(ConstantFP::get(Type::DoubleTy, 0.0f));
2869       double maxInt = (1LL << 32) - 1;
2870       unsigned MaxInt = getReg(ConstantFP::get(Type::DoubleTy, maxInt));
2871       double border = 1LL << 31;
2872       unsigned Border = getReg(ConstantFP::get(Type::DoubleTy, border));
2873       unsigned UseZero = makeAnotherReg(Type::DoubleTy);
2874       unsigned UseMaxInt = makeAnotherReg(Type::DoubleTy);
2875       unsigned UseChoice = makeAnotherReg(Type::DoubleTy);
2876       unsigned TmpReg = makeAnotherReg(Type::DoubleTy);
2877       unsigned TmpReg2 = makeAnotherReg(Type::DoubleTy);
2878       unsigned ConvReg = makeAnotherReg(Type::DoubleTy);
2879       unsigned IntTmp = makeAnotherReg(Type::IntTy);
2880       unsigned XorReg = makeAnotherReg(Type::IntTy);
2881       int FrameIdx =
2882         F->getFrameInfo()->CreateStackObject(SrcTy, TM.getTargetData());
2883       // Update machine-CFG edges
2884       MachineBasicBlock *XorMBB = new MachineBasicBlock(BB->getBasicBlock());
2885       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
2886       MachineBasicBlock *OldMBB = BB;
2887       ilist<MachineBasicBlock>::iterator It = BB; ++It;
2888       F->getBasicBlockList().insert(It, XorMBB);
2889       F->getBasicBlockList().insert(It, PhiMBB);
2890       BB->addSuccessor(XorMBB);
2891       BB->addSuccessor(PhiMBB);
2892
2893       // Convert from floating point to unsigned 32-bit value
2894       // Use 0 if incoming value is < 0.0
2895       BuildMI(*MBB, IP, PPC::FSEL, 3, UseZero).addReg(SrcReg).addReg(SrcReg)
2896         .addReg(Zero);
2897       // Use 2**32 - 1 if incoming value is >= 2**32
2898       BuildMI(*MBB, IP, PPC::FSUB, 2, UseMaxInt).addReg(MaxInt).addReg(SrcReg);
2899       BuildMI(*MBB, IP, PPC::FSEL, 3, UseChoice).addReg(UseMaxInt)
2900         .addReg(UseZero).addReg(MaxInt);
2901       // Subtract 2**31
2902       BuildMI(*MBB, IP, PPC::FSUB, 2, TmpReg).addReg(UseChoice).addReg(Border);
2903       // Use difference if >= 2**31
2904       BuildMI(*MBB, IP, PPC::FCMPU, 2, PPC::CR0).addReg(UseChoice)
2905         .addReg(Border);
2906       BuildMI(*MBB, IP, PPC::FSEL, 3, TmpReg2).addReg(TmpReg).addReg(TmpReg)
2907         .addReg(UseChoice);
2908       // Convert to integer
2909       BuildMI(*MBB, IP, PPC::FCTIWZ, 1, ConvReg).addReg(TmpReg2);
2910       addFrameReference(BuildMI(*MBB, IP, PPC::STFD, 3).addReg(ConvReg),
2911                         FrameIdx);
2912       if (DestClass == cByte) {
2913         addFrameReference(BuildMI(*MBB, IP, PPC::LBZ, 2, DestReg),
2914                           FrameIdx, 7);
2915       } else if (DestClass == cShort) {
2916         addFrameReference(BuildMI(*MBB, IP, PPC::LHZ, 2, DestReg),
2917                           FrameIdx, 6);
2918       } if (DestClass == cInt) {
2919         addFrameReference(BuildMI(*MBB, IP, PPC::LWZ, 2, IntTmp),
2920                           FrameIdx, 4);
2921         BuildMI(*MBB, IP, PPC::BLT, 2).addReg(PPC::CR0).addMBB(PhiMBB);
2922         BuildMI(*MBB, IP, PPC::B, 1).addMBB(XorMBB);
2923
2924         // XorMBB:
2925         //   add 2**31 if input was >= 2**31
2926         BB = XorMBB;
2927         BuildMI(BB, PPC::XORIS, 2, XorReg).addReg(IntTmp).addImm(0x8000);
2928         XorMBB->addSuccessor(PhiMBB);
2929
2930         // PhiMBB:
2931         //   DestReg = phi [ IntTmp, OldMBB ], [ XorReg, XorMBB ]
2932         BB = PhiMBB;
2933         BuildMI(BB, PPC::PHI, 4, DestReg).addReg(IntTmp).addMBB(OldMBB)
2934           .addReg(XorReg).addMBB(XorMBB);
2935       }
2936     }
2937     return;
2938   }
2939
2940   // Check our invariants
2941   assert((SrcClass <= cInt || SrcClass == cLong) &&
2942          "Unhandled source class for cast operation!");
2943   assert((DestClass <= cInt || DestClass == cLong) &&
2944          "Unhandled destination class for cast operation!");
2945
2946   bool sourceUnsigned = SrcTy->isUnsigned() || SrcTy == Type::BoolTy;
2947   bool destUnsigned = DestTy->isUnsigned();
2948
2949   // Unsigned -> Unsigned, clear if larger,
2950   if (sourceUnsigned && destUnsigned) {
2951     // handle long dest class now to keep switch clean
2952     if (DestClass == cLong) {
2953       if (SrcClass == cLong) {
2954         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
2955         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg+1)
2956           .addReg(SrcReg+1);
2957       } else {
2958         BuildMI(*MBB, IP, PPC::LI, 1, DestReg).addSImm(0);
2959         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg)
2960           .addReg(SrcReg);
2961       }
2962       return;
2963     }
2964
2965     // handle u{ byte, short, int } x u{ byte, short, int }
2966     unsigned clearBits = (SrcClass == cByte || DestClass == cByte) ? 24 : 16;
2967     switch (SrcClass) {
2968     case cByte:
2969     case cShort:
2970       if (SrcClass == DestClass)
2971         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
2972       else
2973         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
2974           .addImm(0).addImm(clearBits).addImm(31);
2975       break;
2976     case cLong:
2977       ++SrcReg;
2978       // Fall through
2979     case cInt:
2980       if (DestClass == cInt)
2981         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
2982       else
2983         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
2984           .addImm(0).addImm(clearBits).addImm(31);
2985       break;
2986     }
2987     return;
2988   }
2989
2990   // Signed -> Signed
2991   if (!sourceUnsigned && !destUnsigned) {
2992     // handle long dest class now to keep switch clean
2993     if (DestClass == cLong) {
2994       if (SrcClass == cLong) {
2995         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
2996         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg+1)
2997           .addReg(SrcReg+1);
2998       } else {
2999         BuildMI(*MBB, IP, PPC::SRAWI, 2, DestReg).addReg(SrcReg).addImm(31);
3000         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg)
3001           .addReg(SrcReg);
3002       }
3003       return;
3004     }
3005
3006     // handle { byte, short, int } x { byte, short, int }
3007     switch (SrcClass) {
3008     case cByte:
3009       if (DestClass == cByte)
3010         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3011       else
3012         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(SrcReg);
3013       break;
3014     case cShort:
3015       if (DestClass == cByte)
3016         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(SrcReg);
3017       else if (DestClass == cShort)
3018         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3019       else
3020         BuildMI(*MBB, IP, PPC::EXTSH, 1, DestReg).addReg(SrcReg);
3021       break;
3022     case cLong:
3023       ++SrcReg;
3024       // Fall through
3025     case cInt:
3026       if (DestClass == cByte)
3027         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(SrcReg);
3028       else if (DestClass == cShort)
3029         BuildMI(*MBB, IP, PPC::EXTSH, 1, DestReg).addReg(SrcReg);
3030       else
3031         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3032       break;
3033     }
3034     return;
3035   }
3036
3037   // Unsigned -> Signed
3038   if (sourceUnsigned && !destUnsigned) {
3039     // handle long dest class now to keep switch clean
3040     if (DestClass == cLong) {
3041       if (SrcClass == cLong) {
3042         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3043         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg+1).
3044           addReg(SrcReg+1);
3045       } else {
3046         BuildMI(*MBB, IP, PPC::LI, 1, DestReg).addSImm(0);
3047         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg)
3048           .addReg(SrcReg);
3049       }
3050       return;
3051     }
3052
3053     // handle u{ byte, short, int } -> { byte, short, int }
3054     switch (SrcClass) {
3055     case cByte:
3056       if (DestClass == cByte)
3057         // uByte 255 -> signed byte == -1
3058         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(SrcReg);
3059       else
3060         // uByte 255 -> signed short/int == 255
3061         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg).addImm(0)
3062           .addImm(24).addImm(31);
3063       break;
3064     case cShort:
3065       if (DestClass == cByte)
3066         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(SrcReg);
3067       else if (DestClass == cShort)
3068         BuildMI(*MBB, IP, PPC::EXTSH, 1, DestReg).addReg(SrcReg);
3069       else
3070         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg).addImm(0)
3071           .addImm(16).addImm(31);
3072       break;
3073     case cLong:
3074       ++SrcReg;
3075       // Fall through
3076     case cInt:
3077       if (DestClass == cByte)
3078         BuildMI(*MBB, IP, PPC::EXTSB, 1, DestReg).addReg(SrcReg);
3079       else if (DestClass == cShort)
3080         BuildMI(*MBB, IP, PPC::EXTSH, 1, DestReg).addReg(SrcReg);
3081       else
3082         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3083       break;
3084     }
3085     return;
3086   }
3087
3088   // Signed -> Unsigned
3089   if (!sourceUnsigned && destUnsigned) {
3090     // handle long dest class now to keep switch clean
3091     if (DestClass == cLong) {
3092       if (SrcClass == cLong) {
3093         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3094         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg+1)
3095           .addReg(SrcReg+1);
3096       } else {
3097         BuildMI(*MBB, IP, PPC::SRAWI, 2, DestReg).addReg(SrcReg).addImm(31);
3098         BuildMI(*MBB, IP, PPC::OR, 2, DestReg+1).addReg(SrcReg)
3099           .addReg(SrcReg);
3100       }
3101       return;
3102     }
3103
3104     // handle { byte, short, int } -> u{ byte, short, int }
3105     unsigned clearBits = (DestClass == cByte) ? 24 : 16;
3106     switch (SrcClass) {
3107     case cByte:
3108     case cShort:
3109       if (DestClass == cByte || DestClass == cShort)
3110         // sbyte -1 -> ubyte 0x000000FF
3111         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
3112           .addImm(0).addImm(clearBits).addImm(31);
3113       else
3114         // sbyte -1 -> ubyte 0xFFFFFFFF
3115         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3116       break;
3117     case cLong:
3118       ++SrcReg;
3119       // Fall through
3120     case cInt:
3121       if (DestClass == cInt)
3122         BuildMI(*MBB, IP, PPC::OR, 2, DestReg).addReg(SrcReg).addReg(SrcReg);
3123       else
3124         BuildMI(*MBB, IP, PPC::RLWINM, 4, DestReg).addReg(SrcReg)
3125           .addImm(0).addImm(clearBits).addImm(31);
3126       break;
3127     }
3128     return;
3129   }
3130
3131   // Anything we haven't handled already, we can't (yet) handle at all.
3132   std::cerr << "Unhandled cast from " << SrcTy->getDescription()
3133             << "to " << DestTy->getDescription() << '\n';
3134   abort();
3135 }
3136
3137 /// visitVANextInst - Implement the va_next instruction...
3138 ///
3139 void ISel::visitVANextInst(VANextInst &I) {
3140   unsigned VAList = getReg(I.getOperand(0));
3141   unsigned DestReg = getReg(I);
3142
3143   unsigned Size;
3144   switch (I.getArgType()->getTypeID()) {
3145   default:
3146     std::cerr << I;
3147     assert(0 && "Error: bad type for va_next instruction!");
3148     return;
3149   case Type::PointerTyID:
3150   case Type::UIntTyID:
3151   case Type::IntTyID:
3152     Size = 4;
3153     break;
3154   case Type::ULongTyID:
3155   case Type::LongTyID:
3156   case Type::DoubleTyID:
3157     Size = 8;
3158     break;
3159   }
3160
3161   // Increment the VAList pointer...
3162   BuildMI(BB, PPC::ADDI, 2, DestReg).addReg(VAList).addSImm(Size);
3163 }
3164
3165 void ISel::visitVAArgInst(VAArgInst &I) {
3166   unsigned VAList = getReg(I.getOperand(0));
3167   unsigned DestReg = getReg(I);
3168
3169   switch (I.getType()->getTypeID()) {
3170   default:
3171     std::cerr << I;
3172     assert(0 && "Error: bad type for va_next instruction!");
3173     return;
3174   case Type::PointerTyID:
3175   case Type::UIntTyID:
3176   case Type::IntTyID:
3177     BuildMI(BB, PPC::LWZ, 2, DestReg).addSImm(0).addReg(VAList);
3178     break;
3179   case Type::ULongTyID:
3180   case Type::LongTyID:
3181     BuildMI(BB, PPC::LWZ, 2, DestReg).addSImm(0).addReg(VAList);
3182     BuildMI(BB, PPC::LWZ, 2, DestReg+1).addSImm(4).addReg(VAList);
3183     break;
3184   case Type::FloatTyID:
3185     BuildMI(BB, PPC::LFS, 2, DestReg).addSImm(0).addReg(VAList);
3186     break;
3187   case Type::DoubleTyID:
3188     BuildMI(BB, PPC::LFD, 2, DestReg).addSImm(0).addReg(VAList);
3189     break;
3190   }
3191 }
3192
3193 /// visitGetElementPtrInst - instruction-select GEP instructions
3194 ///
3195 void ISel::visitGetElementPtrInst(GetElementPtrInst &I) {
3196   if (canFoldGEPIntoLoadOrStore(&I))
3197     return;
3198
3199   unsigned outputReg = getReg(I);
3200   emitGEPOperation(BB, BB->end(), I.getOperand(0), I.op_begin()+1, I.op_end(),
3201                    outputReg, false, 0, 0);
3202 }
3203
3204 /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
3205 /// constant expression GEP support.
3206 ///
3207 void ISel::emitGEPOperation(MachineBasicBlock *MBB,
3208                             MachineBasicBlock::iterator IP,
3209                             Value *Src, User::op_iterator IdxBegin,
3210                             User::op_iterator IdxEnd, unsigned TargetReg,
3211                             bool GEPIsFolded, ConstantSInt **RemainderPtr,
3212                             unsigned *PendingAddReg) {
3213   const TargetData &TD = TM.getTargetData();
3214   const Type *Ty = Src->getType();
3215   unsigned basePtrReg = getReg(Src, MBB, IP);
3216   int64_t constValue = 0;
3217
3218   // Record the operations to emit the GEP in a vector so that we can emit them
3219   // after having analyzed the entire instruction.
3220   std::vector<CollapsedGepOp> ops;
3221
3222   // GEPs have zero or more indices; we must perform a struct access
3223   // or array access for each one.
3224   for (GetElementPtrInst::op_iterator oi = IdxBegin, oe = IdxEnd; oi != oe;
3225        ++oi) {
3226     Value *idx = *oi;
3227     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
3228       // It's a struct access.  idx is the index into the structure,
3229       // which names the field. Use the TargetData structure to
3230       // pick out what the layout of the structure is in memory.
3231       // Use the (constant) structure index's value to find the
3232       // right byte offset from the StructLayout class's list of
3233       // structure member offsets.
3234       unsigned fieldIndex = cast<ConstantUInt>(idx)->getValue();
3235       unsigned memberOffset =
3236         TD.getStructLayout(StTy)->MemberOffsets[fieldIndex];
3237
3238       // StructType member offsets are always constant values.  Add it to the
3239       // running total.
3240       constValue += memberOffset;
3241
3242       // The next type is the member of the structure selected by the
3243       // index.
3244       Ty = StTy->getElementType (fieldIndex);
3245     } else if (const SequentialType *SqTy = dyn_cast<SequentialType> (Ty)) {
3246       // Many GEP instructions use a [cast (int/uint) to LongTy] as their
3247       // operand.  Handle this case directly now...
3248       if (CastInst *CI = dyn_cast<CastInst>(idx))
3249         if (CI->getOperand(0)->getType() == Type::IntTy ||
3250             CI->getOperand(0)->getType() == Type::UIntTy)
3251           idx = CI->getOperand(0);
3252
3253       // It's an array or pointer access: [ArraySize x ElementType].
3254       // We want to add basePtrReg to (idxReg * sizeof ElementType). First, we
3255       // must find the size of the pointed-to type (Not coincidentally, the next
3256       // type is the type of the elements in the array).
3257       Ty = SqTy->getElementType();
3258       unsigned elementSize = TD.getTypeSize(Ty);
3259
3260       if (ConstantInt *C = dyn_cast<ConstantInt>(idx)) {
3261         if (ConstantSInt *CS = dyn_cast<ConstantSInt>(C))
3262           constValue += CS->getValue() * elementSize;
3263         else if (ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
3264           constValue += CU->getValue() * elementSize;
3265         else
3266           assert(0 && "Invalid ConstantInt GEP index type!");
3267       } else {
3268         // Push current gep state to this point as an add
3269         ops.push_back(CollapsedGepOp(false, 0,
3270           ConstantSInt::get(Type::IntTy,constValue)));
3271
3272         // Push multiply gep op and reset constant value
3273         ops.push_back(CollapsedGepOp(true, idx,
3274           ConstantSInt::get(Type::IntTy, elementSize)));
3275
3276         constValue = 0;
3277       }
3278     }
3279   }
3280   // Emit instructions for all the collapsed ops
3281   bool pendingAdd = false;
3282   unsigned pendingAddReg = 0;
3283
3284   for(std::vector<CollapsedGepOp>::iterator cgo_i = ops.begin(),
3285       cgo_e = ops.end(); cgo_i != cgo_e; ++cgo_i) {
3286     CollapsedGepOp& cgo = *cgo_i;
3287     unsigned nextBasePtrReg = makeAnotherReg(Type::IntTy);
3288
3289     // If we didn't emit an add last time through the loop, we need to now so
3290     // that the base reg is updated appropriately.
3291     if (pendingAdd) {
3292       assert(pendingAddReg != 0 && "Uninitialized register in pending add!");
3293       BuildMI(*MBB, IP, PPC::ADD, 2, nextBasePtrReg).addReg(basePtrReg)
3294         .addReg(pendingAddReg);
3295       basePtrReg = nextBasePtrReg;
3296       nextBasePtrReg = makeAnotherReg(Type::IntTy);
3297       pendingAddReg = 0;
3298       pendingAdd = false;
3299     }
3300
3301     if (cgo.isMul) {
3302       // We know the elementSize is a constant, so we can emit a constant mul
3303       unsigned TmpReg = makeAnotherReg(Type::IntTy);
3304       doMultiplyConst(MBB, IP, nextBasePtrReg, cgo.index, cgo.size);
3305       pendingAddReg = basePtrReg;
3306       pendingAdd = true;
3307     } else {
3308       // Try and generate an immediate addition if possible
3309       if (cgo.size->isNullValue()) {
3310         BuildMI(*MBB, IP, PPC::OR, 2, nextBasePtrReg).addReg(basePtrReg)
3311           .addReg(basePtrReg);
3312       } else if (canUseAsImmediateForOpcode(cgo.size, 0)) {
3313         BuildMI(*MBB, IP, PPC::ADDI, 2, nextBasePtrReg).addReg(basePtrReg)
3314           .addSImm(cgo.size->getValue());
3315       } else {
3316         unsigned Op1r = getReg(cgo.size, MBB, IP);
3317         BuildMI(*MBB, IP, PPC::ADD, 2, nextBasePtrReg).addReg(basePtrReg)
3318           .addReg(Op1r);
3319       }
3320     }
3321
3322     basePtrReg = nextBasePtrReg;
3323   }
3324   // Add the current base register plus any accumulated constant value
3325   ConstantSInt *remainder = ConstantSInt::get(Type::IntTy, constValue);
3326
3327   // If we are emitting this during a fold, copy the current base register to
3328   // the target, and save the current constant offset so the folding load or
3329   // store can try and use it as an immediate.
3330   if (GEPIsFolded) {
3331     // If this is a folded GEP and the last element was an index, then we need
3332     // to do some extra work to turn a shift/add/stw into a shift/stwx
3333     if (pendingAdd && 0 == remainder->getValue()) {
3334       assert(pendingAddReg != 0 && "Uninitialized register in pending add!");
3335       *PendingAddReg = pendingAddReg;
3336     } else {
3337       *PendingAddReg = 0;
3338       if (pendingAdd) {
3339         unsigned nextBasePtrReg = makeAnotherReg(Type::IntTy);
3340         assert(pendingAddReg != 0 && "Uninitialized register in pending add!");
3341         BuildMI(*MBB, IP, PPC::ADD, 2, nextBasePtrReg).addReg(basePtrReg)
3342           .addReg(pendingAddReg);
3343         basePtrReg = nextBasePtrReg;
3344       }
3345     }
3346     BuildMI (*MBB, IP, PPC::OR, 2, TargetReg).addReg(basePtrReg)
3347       .addReg(basePtrReg);
3348     *RemainderPtr = remainder;
3349     return;
3350   }
3351
3352   // If we still have a pending add at this point, emit it now
3353   if (pendingAdd) {
3354     unsigned TmpReg = makeAnotherReg(Type::IntTy);
3355     BuildMI(*MBB, IP, PPC::ADD, 2, TmpReg).addReg(pendingAddReg)
3356       .addReg(basePtrReg);
3357     basePtrReg = TmpReg;
3358   }
3359
3360   // After we have processed all the indices, the result is left in
3361   // basePtrReg.  Move it to the register where we were expected to
3362   // put the answer.
3363   if (remainder->isNullValue()) {
3364     BuildMI (*MBB, IP, PPC::OR, 2, TargetReg).addReg(basePtrReg)
3365       .addReg(basePtrReg);
3366   } else if (canUseAsImmediateForOpcode(remainder, 0)) {
3367     BuildMI(*MBB, IP, PPC::ADDI, 2, TargetReg).addReg(basePtrReg)
3368       .addSImm(remainder->getValue());
3369   } else {
3370     unsigned Op1r = getReg(remainder, MBB, IP);
3371     BuildMI(*MBB, IP, PPC::ADD, 2, TargetReg).addReg(basePtrReg).addReg(Op1r);
3372   }
3373 }
3374
3375 /// visitAllocaInst - If this is a fixed size alloca, allocate space from the
3376 /// frame manager, otherwise do it the hard way.
3377 ///
3378 void ISel::visitAllocaInst(AllocaInst &I) {
3379   // If this is a fixed size alloca in the entry block for the function, we
3380   // statically stack allocate the space, so we don't need to do anything here.
3381   //
3382   if (dyn_castFixedAlloca(&I)) return;
3383
3384   // Find the data size of the alloca inst's getAllocatedType.
3385   const Type *Ty = I.getAllocatedType();
3386   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
3387
3388   // Create a register to hold the temporary result of multiplying the type size
3389   // constant by the variable amount.
3390   unsigned TotalSizeReg = makeAnotherReg(Type::UIntTy);
3391
3392   // TotalSizeReg = mul <numelements>, <TypeSize>
3393   MachineBasicBlock::iterator MBBI = BB->end();
3394   ConstantUInt *CUI = ConstantUInt::get(Type::UIntTy, TySize);
3395   doMultiplyConst(BB, MBBI, TotalSizeReg, I.getArraySize(), CUI);
3396
3397   // AddedSize = add <TotalSizeReg>, 15
3398   unsigned AddedSizeReg = makeAnotherReg(Type::UIntTy);
3399   BuildMI(BB, PPC::ADDI, 2, AddedSizeReg).addReg(TotalSizeReg).addSImm(15);
3400
3401   // AlignedSize = and <AddedSize>, ~15
3402   unsigned AlignedSize = makeAnotherReg(Type::UIntTy);
3403   BuildMI(BB, PPC::RLWINM, 4, AlignedSize).addReg(AddedSizeReg).addImm(0)
3404     .addImm(0).addImm(27);
3405
3406   // Subtract size from stack pointer, thereby allocating some space.
3407   BuildMI(BB, PPC::SUB, 2, PPC::R1).addReg(PPC::R1).addReg(AlignedSize);
3408
3409   // Put a pointer to the space into the result register, by copying
3410   // the stack pointer.
3411   BuildMI(BB, PPC::OR, 2, getReg(I)).addReg(PPC::R1).addReg(PPC::R1);
3412
3413   // Inform the Frame Information that we have just allocated a variable-sized
3414   // object.
3415   F->getFrameInfo()->CreateVariableSizedObject();
3416 }
3417
3418 /// visitMallocInst - Malloc instructions are code generated into direct calls
3419 /// to the library malloc.
3420 ///
3421 void ISel::visitMallocInst(MallocInst &I) {
3422   unsigned AllocSize = TM.getTargetData().getTypeSize(I.getAllocatedType());
3423   unsigned Arg;
3424
3425   if (ConstantUInt *C = dyn_cast<ConstantUInt>(I.getOperand(0))) {
3426     Arg = getReg(ConstantUInt::get(Type::UIntTy, C->getValue() * AllocSize));
3427   } else {
3428     Arg = makeAnotherReg(Type::UIntTy);
3429     MachineBasicBlock::iterator MBBI = BB->end();
3430     ConstantUInt *CUI = ConstantUInt::get(Type::UIntTy, AllocSize);
3431     doMultiplyConst(BB, MBBI, Arg, I.getOperand(0), CUI);
3432   }
3433
3434   std::vector<ValueRecord> Args;
3435   Args.push_back(ValueRecord(Arg, Type::UIntTy));
3436   MachineInstr *TheCall =
3437     BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(mallocFn, true);
3438   doCall(ValueRecord(getReg(I), I.getType()), TheCall, Args, false);
3439   TM.CalledFunctions.insert(mallocFn);
3440 }
3441
3442
3443 /// visitFreeInst - Free instructions are code gen'd to call the free libc
3444 /// function.
3445 ///
3446 void ISel::visitFreeInst(FreeInst &I) {
3447   std::vector<ValueRecord> Args;
3448   Args.push_back(ValueRecord(I.getOperand(0)));
3449   MachineInstr *TheCall =
3450     BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(freeFn, true);
3451   doCall(ValueRecord(0, Type::VoidTy), TheCall, Args, false);
3452   TM.CalledFunctions.insert(freeFn);
3453 }
3454
3455 /// createPPC32ISelSimple - This pass converts an LLVM function into a machine
3456 /// code representation is a very simple peep-hole fashion.
3457 ///
3458 FunctionPass *llvm::createPPC32ISelSimple(TargetMachine &TM) {
3459   return new ISel(TM);
3460 }