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