lib/Target/PowerPC/PowerPCISelSimple.cpp

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