lib/Target/PowerPC/PPC32ISelSimple.cpp

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