lib/Target/PowerPC/PPCISelPattern.cpp

   1 //===-- PPC32ISelPattern.cpp - A pattern matching inst selector for PPC32 -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nate Begeman and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a pattern matching instruction selector for 32 bit PowerPC.
  11 // Magic number generation for integer divide from the PowerPC Compiler Writer's
  12 // Guide, section 3.2.3.5
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "PowerPC.h"
  17 #include "PowerPCInstrBuilder.h"
  18 #include "PowerPCInstrInfo.h"
  19 #include "PPC32TargetMachine.h"
  20 #include "llvm/Constants.h"                   // FIXME: REMOVE
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/SelectionDAG.h"
  26 #include "llvm/CodeGen/SelectionDAGISel.h"
  27 #include "llvm/CodeGen/SSARegMap.h"
  28 #include "llvm/Target/TargetData.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetOptions.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include <set>
  35 #include <algorithm>
  36 using namespace llvm;
  37
  38 //===----------------------------------------------------------------------===//
  39 //  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
  40 namespace {
  41   class PPC32TargetLowering : public TargetLowering {
  42     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  43     int ReturnAddrIndex;              // FrameIndex for return slot.
  44   public:
  45     PPC32TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  46       // Set up the register classes.
  47       addRegisterClass(MVT::i32, PPC32::GPRCRegisterClass);
  48       addRegisterClass(MVT::f32, PPC32::FPRCRegisterClass);
  49       addRegisterClass(MVT::f64, PPC32::FPRCRegisterClass);
  50
  51       // PowerPC has no intrinsics for these particular operations
  52       setOperationAction(ISD::MEMMOVE, MVT::Other, Expand);
  53       setOperationAction(ISD::MEMSET, MVT::Other, Expand);
  54       setOperationAction(ISD::MEMCPY, MVT::Other, Expand);
  55
  56       // PowerPC has an i16 but no i8 (or i1) SEXTLOAD
  57       setOperationAction(ISD::SEXTLOAD, MVT::i1, Expand);
  58       setOperationAction(ISD::SEXTLOAD, MVT::i8, Expand);
  59
  60       // PowerPC has no SREM/UREM instructions
  61       setOperationAction(ISD::SREM, MVT::i32, Expand);
  62       setOperationAction(ISD::UREM, MVT::i32, Expand);
  63
  64       setSetCCResultContents(ZeroOrOneSetCCResult);
  65       addLegalFPImmediate(+0.0); // Necessary for FSEL
  66       addLegalFPImmediate(-0.0); //
  67
  68       computeRegisterProperties();
  69     }
  70
  71     /// LowerArguments - This hook must be implemented to indicate how we should
  72     /// lower the arguments for the specified function, into the specified DAG.
  73     virtual std::vector<SDOperand>
  74     LowerArguments(Function &F, SelectionDAG &DAG);
  75
  76     /// LowerCallTo - This hook lowers an abstract call to a function into an
  77     /// actual call.
  78     virtual std::pair<SDOperand, SDOperand>
  79     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg,
  80                 SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
  81
  82     virtual std::pair<SDOperand, SDOperand>
  83     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
  84
  85     virtual std::pair<SDOperand,SDOperand>
  86     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
  87                    const Type *ArgTy, SelectionDAG &DAG);
  88
  89     virtual std::pair<SDOperand, SDOperand>
  90     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
  91                             SelectionDAG &DAG);
  92   };
  93 }
  94
  95
  96 std::vector<SDOperand>
  97 PPC32TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
  98   //
  99   // add beautiful description of PPC stack frame format, or at least some docs
 100   //
 101   MachineFunction &MF = DAG.getMachineFunction();
 102   MachineFrameInfo *MFI = MF.getFrameInfo();
 103   MachineBasicBlock& BB = MF.front();
 104   std::vector<SDOperand> ArgValues;
 105
 106   // Due to the rather complicated nature of the PowerPC ABI, rather than a
 107   // fixed size array of physical args, for the sake of simplicity let the STL
 108   // handle tracking them for us.
 109   std::vector<unsigned> argVR, argPR, argOp;
 110   unsigned ArgOffset = 24;
 111   unsigned GPR_remaining = 8;
 112   unsigned FPR_remaining = 13;
 113   unsigned GPR_idx = 0, FPR_idx = 0;
 114   static const unsigned GPR[] = {
 115     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 116     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 117   };
 118   static const unsigned FPR[] = {
 119     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 120     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 121   };
 122
 123   // Add DAG nodes to load the arguments...  On entry to a function on PPC,
 124   // the arguments start at offset 24, although they are likely to be passed
 125   // in registers.
 126   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 127     SDOperand newroot, argt;
 128     unsigned ObjSize;
 129     bool needsLoad = false;
 130     bool ArgLive = !I->use_empty();
 131     MVT::ValueType ObjectVT = getValueType(I->getType());
 132
 133     switch (ObjectVT) {
 134     default: assert(0 && "Unhandled argument type!");
 135     case MVT::i1:
 136     case MVT::i8:
 137     case MVT::i16:
 138     case MVT::i32:
 139       ObjSize = 4;
 140       if (!ArgLive) break;
 141       if (GPR_remaining > 0) {
 142         MF.addLiveIn(GPR[GPR_idx]);
 143         argt = newroot = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
 144                                             DAG.getRoot());
 145         if (ObjectVT != MVT::i32)
 146           argt = DAG.getNode(ISD::TRUNCATE, ObjectVT, newroot);
 147       } else {
 148         needsLoad = true;
 149       }
 150       break;
 151       case MVT::i64: ObjSize = 8;
 152       if (!ArgLive) break;
 153       if (GPR_remaining > 0) {
 154         SDOperand argHi, argLo;
 155         MF.addLiveIn(GPR[GPR_idx]);
 156         argHi = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32, DAG.getRoot());
 157         // If we have two or more remaining argument registers, then both halves
 158         // of the i64 can be sourced from there.  Otherwise, the lower half will
 159         // have to come off the stack.  This can happen when an i64 is preceded
 160         // by 28 bytes of arguments.
 161         if (GPR_remaining > 1) {
 162           MF.addLiveIn(GPR[GPR_idx+1]);
 163           argLo = DAG.getCopyFromReg(GPR[GPR_idx+1], MVT::i32, argHi);
 164         } else {
 165           int FI = MFI->CreateFixedObject(4, ArgOffset+4);
 166           SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 167           argLo = DAG.getLoad(MVT::i32, DAG.getEntryNode(), FIN);
 168         }
 169         // Build the outgoing arg thingy
 170         argt = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, argLo, argHi);
 171         newroot = argLo;
 172       } else {
 173         needsLoad = true;
 174       }
 175       break;
 176       case MVT::f32:
 177       case MVT::f64:
 178       ObjSize = (ObjectVT == MVT::f64) ? 8 : 4;
 179       if (!ArgLive) break;
 180       if (FPR_remaining > 0) {
 181         MF.addLiveIn(FPR[FPR_idx]);
 182         argt = newroot = DAG.getCopyFromReg(FPR[FPR_idx], ObjectVT,
 183                                             DAG.getRoot());
 184         --FPR_remaining;
 185         ++FPR_idx;
 186       } else {
 187         needsLoad = true;
 188       }
 189       break;
 190     }
 191
 192     // We need to load the argument to a virtual register if we determined above
 193     // that we ran out of physical registers of the appropriate type
 194     if (needsLoad) {
 195       unsigned SubregOffset = 0;
 196       if (ObjectVT == MVT::i8 || ObjectVT == MVT::i1) SubregOffset = 3;
 197       if (ObjectVT == MVT::i16) SubregOffset = 2;
 198       int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 199       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 200       FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN,
 201                         DAG.getConstant(SubregOffset, MVT::i32));
 202       argt = newroot = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
 203     }
 204
 205     // Every 4 bytes of argument space consumes one of the GPRs available for
 206     // argument passing.
 207     if (GPR_remaining > 0) {
 208       unsigned delta = (GPR_remaining > 1 && ObjSize == 8) ? 2 : 1;
 209       GPR_remaining -= delta;
 210       GPR_idx += delta;
 211     }
 212     ArgOffset += ObjSize;
 213     if (newroot.Val)
 214       DAG.setRoot(newroot.getValue(1));
 215
 216     ArgValues.push_back(argt);
 217   }
 218
 219   // If the function takes variable number of arguments, make a frame index for
 220   // the start of the first vararg value... for expansion of llvm.va_start.
 221   if (F.isVarArg()) {
 222     VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
 223     SDOperand FIN = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32);
 224     // If this function is vararg, store any remaining integer argument regs
 225     // to their spots on the stack so that they may be loaded by deferencing the
 226     // result of va_next.
 227     std::vector<SDOperand> MemOps;
 228     for (; GPR_remaining > 0; --GPR_remaining, ++GPR_idx) {
 229       MF.addLiveIn(GPR[GPR_idx]);
 230       SDOperand Val = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32, DAG.getRoot());
 231       SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1),
 232                                     Val, FIN);
 233       MemOps.push_back(Store);
 234       // Increment the address by four for the next argument to store
 235       SDOperand PtrOff = DAG.getConstant(4, getPointerTy());
 236       FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN, PtrOff);
 237     }
 238     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps));
 239   }
 240
 241   // Finally, inform the code generator which regs we return values in.
 242   switch (getValueType(F.getReturnType())) {
 243   default: assert(0 && "Unknown type!");
 244   case MVT::isVoid: break;
 245   case MVT::i1:
 246   case MVT::i8:
 247   case MVT::i16:
 248   case MVT::i32:
 249     MF.addLiveOut(PPC::R3);
 250     break;
 251   case MVT::i64:
 252     MF.addLiveOut(PPC::R3);
 253     MF.addLiveOut(PPC::R4);
 254     break;
 255   case MVT::f32:
 256   case MVT::f64:
 257     MF.addLiveOut(PPC::F1);
 258     break;
 259   }
 260
 261   return ArgValues;
 262 }
 263
 264 std::pair<SDOperand, SDOperand>
 265 PPC32TargetLowering::LowerCallTo(SDOperand Chain,
 266                                  const Type *RetTy, bool isVarArg,
 267          SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG) {
 268   // args_to_use will accumulate outgoing args for the ISD::CALL case in
 269   // SelectExpr to use to put the arguments in the appropriate registers.
 270   std::vector<SDOperand> args_to_use;
 271
 272   // Count how many bytes are to be pushed on the stack, including the linkage
 273   // area, and parameter passing area.
 274   unsigned NumBytes = 24;
 275
 276   if (Args.empty()) {
 277     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 278                         DAG.getConstant(NumBytes, getPointerTy()));
 279   } else {
 280     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 281       switch (getValueType(Args[i].second)) {
 282       default: assert(0 && "Unknown value type!");
 283       case MVT::i1:
 284       case MVT::i8:
 285       case MVT::i16:
 286       case MVT::i32:
 287       case MVT::f32:
 288         NumBytes += 4;
 289         break;
 290       case MVT::i64:
 291       case MVT::f64:
 292         NumBytes += 8;
 293         break;
 294       }
 295
 296     // Just to be safe, we'll always reserve the full 24 bytes of linkage area
 297     // plus 32 bytes of argument space in case any called code gets funky on us.
 298     if (NumBytes < 56) NumBytes = 56;
 299
 300     // Adjust the stack pointer for the new arguments...
 301     // These operations are automatically eliminated by the prolog/epilog pass
 302     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 303                         DAG.getConstant(NumBytes, getPointerTy()));
 304
 305     // Set up a copy of the stack pointer for use loading and storing any
 306     // arguments that may not fit in the registers available for argument
 307     // passing.
 308     SDOperand StackPtr = DAG.getCopyFromReg(PPC::R1, MVT::i32,
 309                                             DAG.getEntryNode());
 310
 311     // Figure out which arguments are going to go in registers, and which in
 312     // memory.  Also, if this is a vararg function, floating point operations
 313     // must be stored to our stack, and loaded into integer regs as well, if
 314     // any integer regs are available for argument passing.
 315     unsigned ArgOffset = 24;
 316     unsigned GPR_remaining = 8;
 317     unsigned FPR_remaining = 13;
 318
 319     std::vector<SDOperand> MemOps;
 320     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 321       // PtrOff will be used to store the current argument to the stack if a
 322       // register cannot be found for it.
 323       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 324       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 325       MVT::ValueType ArgVT = getValueType(Args[i].second);
 326
 327       switch (ArgVT) {
 328       default: assert(0 && "Unexpected ValueType for argument!");
 329       case MVT::i1:
 330       case MVT::i8:
 331       case MVT::i16:
 332         // Promote the integer to 32 bits.  If the input type is signed use a
 333         // sign extend, otherwise use a zero extend.
 334         if (Args[i].second->isSigned())
 335           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 336         else
 337           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 338         // FALL THROUGH
 339       case MVT::i32:
 340         if (GPR_remaining > 0) {
 341           args_to_use.push_back(Args[i].first);
 342           --GPR_remaining;
 343         } else {
 344           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 345                                           Args[i].first, PtrOff));
 346         }
 347         ArgOffset += 4;
 348         break;
 349       case MVT::i64:
 350         // If we have one free GPR left, we can place the upper half of the i64
 351         // in it, and store the other half to the stack.  If we have two or more
 352         // free GPRs, then we can pass both halves of the i64 in registers.
 353         if (GPR_remaining > 0) {
 354           SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 355             Args[i].first, DAG.getConstant(1, MVT::i32));
 356           SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 357             Args[i].first, DAG.getConstant(0, MVT::i32));
 358           args_to_use.push_back(Hi);
 359           --GPR_remaining;
 360           if (GPR_remaining > 0) {
 361             args_to_use.push_back(Lo);
 362             --GPR_remaining;
 363           } else {
 364             SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
 365             PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
 366             MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 367                                             Lo, PtrOff));
 368           }
 369         } else {
 370           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 371                                           Args[i].first, PtrOff));
 372         }
 373         ArgOffset += 8;
 374         break;
 375       case MVT::f32:
 376       case MVT::f64:
 377         if (FPR_remaining > 0) {
 378           args_to_use.push_back(Args[i].first);
 379           --FPR_remaining;
 380           if (isVarArg) {
 381             SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 382                                           Args[i].first, PtrOff);
 383             MemOps.push_back(Store);
 384             // Float varargs are always shadowed in available integer registers
 385             if (GPR_remaining > 0) {
 386               SDOperand Load = DAG.getLoad(MVT::i32, Store, PtrOff);
 387               MemOps.push_back(Load);
 388               args_to_use.push_back(Load);
 389               --GPR_remaining;
 390             }
 391             if (GPR_remaining > 0 && MVT::f64 == ArgVT) {
 392               SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
 393               PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
 394               SDOperand Load = DAG.getLoad(MVT::i32, Store, PtrOff);
 395               MemOps.push_back(Load);
 396               args_to_use.push_back(Load);
 397               --GPR_remaining;
 398             }
 399           } else {
 400             // If we have any FPRs remaining, we may also have GPRs remaining.
 401             // Args passed in FPRs consume either 1 (f32) or 2 (f64) available
 402             // GPRs.
 403             if (GPR_remaining > 0) {
 404               args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
 405               --GPR_remaining;
 406             }
 407             if (GPR_remaining > 0 && MVT::f64 == ArgVT) {
 408               args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
 409               --GPR_remaining;
 410             }
 411           }
 412         } else {
 413           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 414                                           Args[i].first, PtrOff));
 415         }
 416         ArgOffset += (ArgVT == MVT::f32) ? 4 : 8;
 417         break;
 418       }
 419     }
 420     if (!MemOps.empty())
 421       Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps);
 422   }
 423
 424   std::vector<MVT::ValueType> RetVals;
 425   MVT::ValueType RetTyVT = getValueType(RetTy);
 426   if (RetTyVT != MVT::isVoid)
 427     RetVals.push_back(RetTyVT);
 428   RetVals.push_back(MVT::Other);
 429
 430   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 431                                             Chain, Callee, args_to_use), 0);
 432   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 433   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 434                       DAG.getConstant(NumBytes, getPointerTy()));
 435   return std::make_pair(TheCall, Chain);
 436 }
 437
 438 std::pair<SDOperand, SDOperand>
 439 PPC32TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 440   //vastart just returns the address of the VarArgsFrameIndex slot.
 441   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 442 }
 443
 444 std::pair<SDOperand,SDOperand> PPC32TargetLowering::
 445 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 446                const Type *ArgTy, SelectionDAG &DAG) {
 447   MVT::ValueType ArgVT = getValueType(ArgTy);
 448   SDOperand Result;
 449   if (!isVANext) {
 450     Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList);
 451   } else {
 452     unsigned Amt;
 453     if (ArgVT == MVT::i32 || ArgVT == MVT::f32)
 454       Amt = 4;
 455     else {
 456       assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 457              "Other types should have been promoted for varargs!");
 458       Amt = 8;
 459     }
 460     Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
 461                          DAG.getConstant(Amt, VAList.getValueType()));
 462   }
 463   return std::make_pair(Result, Chain);
 464 }
 465
 466
 467 std::pair<SDOperand, SDOperand> PPC32TargetLowering::
 468 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 469                         SelectionDAG &DAG) {
 470   assert(0 && "LowerFrameReturnAddress unimplemented");
 471   abort();
 472 }
 473
 474 namespace {
 475 Statistic<>Recorded("ppc-codegen", "Number of recording ops emitted");
 476 Statistic<>FusedFP("ppc-codegen", "Number of fused fp operations");
 477 Statistic<>MultiBranch("ppc-codegen", "Number of setcc logical ops collapsed");
 478 //===--------------------------------------------------------------------===//
 479 /// ISel - PPC32 specific code to select PPC32 machine instructions for
 480 /// SelectionDAG operations.
 481 //===--------------------------------------------------------------------===//
 482 class ISel : public SelectionDAGISel {
 483   PPC32TargetLowering PPC32Lowering;
 484   SelectionDAG *ISelDAG;  // Hack to support us having a dag->dag transform
 485                           // for sdiv and udiv until it is put into the future
 486                           // dag combiner.
 487
 488   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 489   /// vreg the value is produced in, so we only emit one copy of each compiled
 490   /// tree.
 491   std::map<SDOperand, unsigned> ExprMap;
 492
 493   unsigned GlobalBaseReg;
 494   bool GlobalBaseInitialized;
 495   bool RecordSuccess;
 496 public:
 497   ISel(TargetMachine &TM) : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM),
 498                             ISelDAG(0) {}
 499
 500   /// runOnFunction - Override this function in order to reset our per-function
 501   /// variables.
 502   virtual bool runOnFunction(Function &Fn) {
 503     // Make sure we re-emit a set of the global base reg if necessary
 504     GlobalBaseInitialized = false;
 505     return SelectionDAGISel::runOnFunction(Fn);
 506   }
 507
 508   /// InstructionSelectBasicBlock - This callback is invoked by
 509   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 510   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 511     DEBUG(BB->dump());
 512     // Codegen the basic block.
 513     ISelDAG = &DAG;
 514     Select(DAG.getRoot());
 515
 516     // Clear state used for selection.
 517     ExprMap.clear();
 518     ISelDAG = 0;
 519   }
 520
 521   // dag -> dag expanders for integer divide by constant
 522   SDOperand BuildSDIVSequence(SDOperand N);
 523   SDOperand BuildUDIVSequence(SDOperand N);
 524
 525   unsigned getGlobalBaseReg();
 526   unsigned getConstDouble(double floatVal, unsigned Result);
 527   void MoveCRtoGPR(unsigned CCReg, bool Inv, unsigned Idx, unsigned Result);
 528   bool SelectBitfieldInsert(SDOperand OR, unsigned Result);
 529   unsigned FoldIfWideZeroExtend(SDOperand N);
 530   unsigned SelectCC(SDOperand CC, unsigned &Opc, bool &Inv, unsigned &Idx);
 531   unsigned SelectCCExpr(SDOperand N, unsigned& Opc, bool &Inv, unsigned &Idx);
 532   unsigned SelectExpr(SDOperand N, bool Recording=false);
 533   unsigned SelectExprFP(SDOperand N, unsigned Result);
 534   void Select(SDOperand N);
 535
 536   bool SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 537   void SelectBranchCC(SDOperand N);
 538 };
 539
 540 /// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
 541 /// returns zero when the input is not exactly a power of two.
 542 static unsigned ExactLog2(unsigned Val) {
 543   if (Val == 0 || (Val & (Val-1))) return 0;
 544   unsigned Count = 0;
 545   while (Val != 1) {
 546     Val >>= 1;
 547     ++Count;
 548   }
 549   return Count;
 550 }
 551
 552 // IsRunOfOnes - returns true if Val consists of one contiguous run of 1's with
 553 // any number of 0's on either side.  the 1's are allowed to wrap from LSB to
 554 // MSB.  so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 555 // not, since all 1's are not contiguous.
 556 static bool IsRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 557   bool isRun = true;
 558   MB = 0;
 559   ME = 0;
 560
 561   // look for first set bit
 562   int i = 0;
 563   for (; i < 32; i++) {
 564     if ((Val & (1 << (31 - i))) != 0) {
 565       MB = i;
 566       ME = i;
 567       break;
 568     }
 569   }
 570
 571   // look for last set bit
 572   for (; i < 32; i++) {
 573     if ((Val & (1 << (31 - i))) == 0)
 574       break;
 575     ME = i;
 576   }
 577
 578   // look for next set bit
 579   for (; i < 32; i++) {
 580     if ((Val & (1 << (31 - i))) != 0)
 581       break;
 582   }
 583
 584   // if we exhausted all the bits, we found a match at this point for 0*1*0*
 585   if (i == 32)
 586     return true;
 587
 588   // since we just encountered more 1's, if it doesn't wrap around to the
 589   // most significant bit of the word, then we did not find a match to 1*0*1* so
 590   // exit.
 591   if (MB != 0)
 592     return false;
 593
 594   // look for last set bit
 595   for (MB = i; i < 32; i++) {
 596     if ((Val & (1 << (31 - i))) == 0)
 597       break;
 598   }
 599
 600   // if we exhausted all the bits, then we found a match for 1*0*1*, otherwise,
 601   // the value is not a run of ones.
 602   if (i == 32)
 603     return true;
 604   return false;
 605 }
 606
 607 /// getImmediateForOpcode - This method returns a value indicating whether
 608 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 609 /// values are either 0, 1 or 2.  0 indicates that either N is not a
 610 /// ConstantSDNode, or is not suitable for use by that opcode.
 611 /// Return value codes for turning into an enum someday:
 612 /// 1: constant may be used in normal immediate form.
 613 /// 2: constant may be used in shifted immediate form.
 614 /// 3: log base 2 of the constant may be used.
 615 /// 4: constant is suitable for integer division conversion
 616 /// 5: constant is a bitfield mask
 617 ///
 618 static unsigned getImmediateForOpcode(SDOperand N, unsigned Opcode,
 619                                       unsigned& Imm, bool U = false) {
 620   if (N.getOpcode() != ISD::Constant) return 0;
 621
 622   int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 623
 624   switch(Opcode) {
 625   default: return 0;
 626   case ISD::ADD:
 627     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 628     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 629     break;
 630   case ISD::AND: {
 631     unsigned MB, ME;
 632     if (IsRunOfOnes(v, MB, ME)) { Imm = MB << 16 | ME & 0xFFFF; return 5; }
 633     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 634     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 635     break;
 636   }
 637   case ISD::XOR:
 638   case ISD::OR:
 639     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 640     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 641     break;
 642   case ISD::MUL:
 643   case ISD::SUB:
 644     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 645     break;
 646   case ISD::SETCC:
 647     if (U && (v >= 0 && v <= 65535)) { Imm = v & 0xFFFF; return 1; }
 648     if (!U && (v <= 32767 && v >= -32768)) { Imm = v & 0xFFFF; return 1; }
 649     break;
 650   case ISD::SDIV:
 651     if ((Imm = ExactLog2(v))) { return 3; }
 652     if ((Imm = ExactLog2(-v))) { Imm = -Imm; return 3; }
 653     if (v <= -2 || v >= 2) { return 4; }
 654     break;
 655   case ISD::UDIV:
 656     if (v > 1) { return 4; }
 657     break;
 658   }
 659   return 0;
 660 }
 661
 662 /// NodeHasRecordingVariant - If SelectExpr can always produce code for
 663 /// NodeOpcode that also sets CR0 as a side effect, return true.  Otherwise,
 664 /// return false.
 665 static bool NodeHasRecordingVariant(unsigned NodeOpcode) {
 666   switch(NodeOpcode) {
 667   default: return false;
 668   case ISD::AND:
 669   case ISD::OR:
 670     return true;
 671   }
 672 }
 673
 674 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 675 /// to Condition.  If the Condition is unordered or unsigned, the bool argument
 676 /// U is set to true, otherwise it is set to false.
 677 static unsigned getBCCForSetCC(unsigned Condition, bool& U) {
 678   U = false;
 679   switch (Condition) {
 680   default: assert(0 && "Unknown condition!"); abort();
 681   case ISD::SETEQ:  return PPC::BEQ;
 682   case ISD::SETNE:  return PPC::BNE;
 683   case ISD::SETULT: U = true;
 684   case ISD::SETLT:  return PPC::BLT;
 685   case ISD::SETULE: U = true;
 686   case ISD::SETLE:  return PPC::BLE;
 687   case ISD::SETUGT: U = true;
 688   case ISD::SETGT:  return PPC::BGT;
 689   case ISD::SETUGE: U = true;
 690   case ISD::SETGE:  return PPC::BGE;
 691   }
 692   return 0;
 693 }
 694
 695 /// getCROpForOp - Return the condition register opcode (or inverted opcode)
 696 /// associated with the SelectionDAG opcode.
 697 static unsigned getCROpForSetCC(unsigned Opcode, bool Inv1, bool Inv2) {
 698   switch (Opcode) {
 699   default: assert(0 && "Unknown opcode!"); abort();
 700   case ISD::AND:
 701     if (Inv1 && Inv2) return PPC::CRNOR; // De Morgan's Law
 702     if (!Inv1 && !Inv2) return PPC::CRAND;
 703     if (Inv1 ^ Inv2) return PPC::CRANDC;
 704   case ISD::OR:
 705     if (Inv1 && Inv2) return PPC::CRNAND; // De Morgan's Law
 706     if (!Inv1 && !Inv2) return PPC::CROR;
 707     if (Inv1 ^ Inv2) return PPC::CRORC;
 708   }
 709   return 0;
 710 }
 711
 712 /// getCRIdxForSetCC - Return the index of the condition register field
 713 /// associated with the SetCC condition, and whether or not the field is
 714 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 715 static unsigned getCRIdxForSetCC(unsigned Condition, bool& Inv) {
 716   switch (Condition) {
 717   default: assert(0 && "Unknown condition!"); abort();
 718   case ISD::SETULT:
 719   case ISD::SETLT:  Inv = false;  return 0;
 720   case ISD::SETUGE:
 721   case ISD::SETGE:  Inv = true;   return 0;
 722   case ISD::SETUGT:
 723   case ISD::SETGT:  Inv = false;  return 1;
 724   case ISD::SETULE:
 725   case ISD::SETLE:  Inv = true;   return 1;
 726   case ISD::SETEQ:  Inv = false;  return 2;
 727   case ISD::SETNE:  Inv = true;   return 2;
 728   }
 729   return 0;
 730 }
 731
 732 /// IndexedOpForOp - Return the indexed variant for each of the PowerPC load
 733 /// and store immediate instructions.
 734 static unsigned IndexedOpForOp(unsigned Opcode) {
 735   switch(Opcode) {
 736   default: assert(0 && "Unknown opcode!"); abort();
 737   case PPC::LBZ: return PPC::LBZX;  case PPC::STB: return PPC::STBX;
 738   case PPC::LHZ: return PPC::LHZX;  case PPC::STH: return PPC::STHX;
 739   case PPC::LHA: return PPC::LHAX;  case PPC::STW: return PPC::STWX;
 740   case PPC::LWZ: return PPC::LWZX;  case PPC::STFS: return PPC::STFSX;
 741   case PPC::LFS: return PPC::LFSX;  case PPC::STFD: return PPC::STFDX;
 742   case PPC::LFD: return PPC::LFDX;
 743   }
 744   return 0;
 745 }
 746
 747 // Structure used to return the necessary information to codegen an SDIV as
 748 // a multiply.
 749 struct ms {
 750   int m; // magic number
 751   int s; // shift amount
 752 };
 753
 754 struct mu {
 755   unsigned int m; // magic number
 756   int a;          // add indicator
 757   int s;          // shift amount
 758 };
 759
 760 /// magic - calculate the magic numbers required to codegen an integer sdiv as
 761 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
 762 /// or -1.
 763 static struct ms magic(int d) {
 764   int p;
 765   unsigned int ad, anc, delta, q1, r1, q2, r2, t;
 766   const unsigned int two31 = 2147483648U; // 2^31
 767   struct ms mag;
 768
 769   ad = abs(d);
 770   t = two31 + ((unsigned int)d >> 31);
 771   anc = t - 1 - t%ad;   // absolute value of nc
 772   p = 31;               // initialize p
 773   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
 774   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
 775   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
 776   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
 777   do {
 778     p = p + 1;
 779     q1 = 2*q1;        // update q1 = 2p/abs(nc)
 780     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
 781     if (r1 >= anc) {  // must be unsigned comparison
 782       q1 = q1 + 1;
 783       r1 = r1 - anc;
 784     }
 785     q2 = 2*q2;        // update q2 = 2p/abs(d)
 786     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
 787     if (r2 >= ad) {   // must be unsigned comparison
 788       q2 = q2 + 1;
 789       r2 = r2 - ad;
 790     }
 791     delta = ad - r2;
 792   } while (q1 < delta || (q1 == delta && r1 == 0));
 793
 794   mag.m = q2 + 1;
 795   if (d < 0) mag.m = -mag.m; // resulting magic number
 796   mag.s = p - 32;            // resulting shift
 797   return mag;
 798 }
 799
 800 /// magicu - calculate the magic numbers required to codegen an integer udiv as
 801 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
 802 static struct mu magicu(unsigned d)
 803 {
 804   int p;
 805   unsigned int nc, delta, q1, r1, q2, r2;
 806   struct mu magu;
 807   magu.a = 0;               // initialize "add" indicator
 808   nc = - 1 - (-d)%d;
 809   p = 31;                   // initialize p
 810   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
 811   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
 812   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
 813   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
 814   do {
 815     p = p + 1;
 816     if (r1 >= nc - r1 ) {
 817       q1 = 2*q1 + 1;  // update q1
 818       r1 = 2*r1 - nc; // update r1
 819     }
 820     else {
 821       q1 = 2*q1; // update q1
 822       r1 = 2*r1; // update r1
 823     }
 824     if (r2 + 1 >= d - r2) {
 825       if (q2 >= 0x7FFFFFFF) magu.a = 1;
 826       q2 = 2*q2 + 1;     // update q2
 827       r2 = 2*r2 + 1 - d; // update r2
 828     }
 829     else {
 830       if (q2 >= 0x80000000) magu.a = 1;
 831       q2 = 2*q2;     // update q2
 832       r2 = 2*r2 + 1; // update r2
 833     }
 834     delta = d - 1 - r2;
 835   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
 836   magu.m = q2 + 1; // resulting magic number
 837   magu.s = p - 32;  // resulting shift
 838   return magu;
 839 }
 840 }
 841
 842 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
 843 /// return a DAG expression to select that will generate the same value by
 844 /// multiplying by a magic number.  See:
 845 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 846 SDOperand ISel::BuildSDIVSequence(SDOperand N) {
 847   int d = (int)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 848   ms magics = magic(d);
 849   // Multiply the numerator (operand 0) by the magic value
 850   SDOperand Q = ISelDAG->getNode(ISD::MULHS, MVT::i32, N.getOperand(0),
 851                                  ISelDAG->getConstant(magics.m, MVT::i32));
 852   // If d > 0 and m < 0, add the numerator
 853   if (d > 0 && magics.m < 0)
 854     Q = ISelDAG->getNode(ISD::ADD, MVT::i32, Q, N.getOperand(0));
 855   // If d < 0 and m > 0, subtract the numerator.
 856   if (d < 0 && magics.m > 0)
 857     Q = ISelDAG->getNode(ISD::SUB, MVT::i32, Q, N.getOperand(0));
 858   // Shift right algebraic if shift value is nonzero
 859   if (magics.s > 0)
 860     Q = ISelDAG->getNode(ISD::SRA, MVT::i32, Q,
 861                          ISelDAG->getConstant(magics.s, MVT::i32));
 862   // Extract the sign bit and add it to the quotient
 863   SDOperand T =
 864     ISelDAG->getNode(ISD::SRL, MVT::i32, Q, ISelDAG->getConstant(31, MVT::i32));
 865   return ISelDAG->getNode(ISD::ADD, MVT::i32, Q, T);
 866 }
 867
 868 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
 869 /// return a DAG expression to select that will generate the same value by
 870 /// multiplying by a magic number.  See:
 871 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 872 SDOperand ISel::BuildUDIVSequence(SDOperand N) {
 873   unsigned d =
 874     (unsigned)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 875   mu magics = magicu(d);
 876   // Multiply the numerator (operand 0) by the magic value
 877   SDOperand Q = ISelDAG->getNode(ISD::MULHU, MVT::i32, N.getOperand(0),
 878                                  ISelDAG->getConstant(magics.m, MVT::i32));
 879   if (magics.a == 0) {
 880     Q = ISelDAG->getNode(ISD::SRL, MVT::i32, Q,
 881                          ISelDAG->getConstant(magics.s, MVT::i32));
 882   } else {
 883     SDOperand NPQ = ISelDAG->getNode(ISD::SUB, MVT::i32, N.getOperand(0), Q);
 884     NPQ = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 885                            ISelDAG->getConstant(1, MVT::i32));
 886     NPQ = ISelDAG->getNode(ISD::ADD, MVT::i32, NPQ, Q);
 887     Q = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 888                            ISelDAG->getConstant(magics.s-1, MVT::i32));
 889   }
 890   return Q;
 891 }
 892
 893 /// getGlobalBaseReg - Output the instructions required to put the
 894 /// base address to use for accessing globals into a register.
 895 ///
 896 unsigned ISel::getGlobalBaseReg() {
 897   if (!GlobalBaseInitialized) {
 898     // Insert the set of GlobalBaseReg into the first MBB of the function
 899     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 900     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 901     GlobalBaseReg = MakeReg(MVT::i32);
 902     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 903     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg).addReg(PPC::LR);
 904     GlobalBaseInitialized = true;
 905   }
 906   return GlobalBaseReg;
 907 }
 908
 909 /// getConstDouble - Loads a floating point value into a register, via the
 910 /// Constant Pool.  Optionally takes a register in which to load the value.
 911 unsigned ISel::getConstDouble(double doubleVal, unsigned Result=0) {
 912   unsigned Tmp1 = MakeReg(MVT::i32);
 913   if (0 == Result) Result = MakeReg(MVT::f64);
 914   MachineConstantPool *CP = BB->getParent()->getConstantPool();
 915   ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, doubleVal);
 916   unsigned CPI = CP->getConstantPoolIndex(CFP);
 917   BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
 918     .addConstantPoolIndex(CPI);
 919   BuildMI(BB, PPC::LFD, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 920   return Result;
 921 }
 922
 923 /// MoveCRtoGPR - Move CCReg[Idx] to the least significant bit of Result.  If
 924 /// Inv is true, then invert the result.
 925 void ISel::MoveCRtoGPR(unsigned CCReg, bool Inv, unsigned Idx, unsigned Result){
 926   unsigned IntCR = MakeReg(MVT::i32);
 927   BuildMI(BB, PPC::MCRF, 1, PPC::CR7).addReg(CCReg);
 928   BuildMI(BB, PPC::MFCR, 1, IntCR).addReg(PPC::CR7);
 929   if (Inv) {
 930     unsigned Tmp1 = MakeReg(MVT::i32);
 931     BuildMI(BB, PPC::RLWINM, 4, Tmp1).addReg(IntCR).addImm(32-(3-Idx))
 932       .addImm(31).addImm(31);
 933     BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp1).addImm(1);
 934   } else {
 935     BuildMI(BB, PPC::RLWINM, 4, Result).addReg(IntCR).addImm(32-(3-Idx))
 936       .addImm(31).addImm(31);
 937   }
 938 }
 939
 940 /// SelectBitfieldInsert - turn an or of two masked values into
 941 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 942 /// Returns true on success, false if the caller still needs to select OR.
 943 ///
 944 /// Patterns matched:
 945 /// 1. or shl, and   5. or and, and
 946 /// 2. or and, shl   6. or shl, shr
 947 /// 3. or shr, and   7. or shr, shl
 948 /// 4. or and, shr
 949 bool ISel::SelectBitfieldInsert(SDOperand OR, unsigned Result) {
 950   bool IsRotate = false;
 951   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, Amount = 0;
 952   unsigned Op0Opc = OR.getOperand(0).getOpcode();
 953   unsigned Op1Opc = OR.getOperand(1).getOpcode();
 954
 955   // Verify that we have the correct opcodes
 956   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
 957     return false;
 958   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
 959     return false;
 960
 961   // Generate Mask value for Target
 962   if (ConstantSDNode *CN =
 963       dyn_cast<ConstantSDNode>(OR.getOperand(0).getOperand(1).Val)) {
 964     switch(Op0Opc) {
 965     case ISD::SHL: TgtMask <<= (unsigned)CN->getValue(); break;
 966     case ISD::SRL: TgtMask >>= (unsigned)CN->getValue(); break;
 967     case ISD::AND: TgtMask &= (unsigned)CN->getValue(); break;
 968     }
 969   } else {
 970     return false;
 971   }
 972
 973   // Generate Mask value for Insert
 974   if (ConstantSDNode *CN =
 975       dyn_cast<ConstantSDNode>(OR.getOperand(1).getOperand(1).Val)) {
 976     switch(Op1Opc) {
 977     case ISD::SHL:
 978       Amount = CN->getValue();
 979       InsMask <<= Amount;
 980       if (Op0Opc == ISD::SRL) IsRotate = true;
 981       break;
 982     case ISD::SRL:
 983       Amount = CN->getValue();
 984       InsMask >>= Amount;
 985       Amount = 32-Amount;
 986       if (Op0Opc == ISD::SHL) IsRotate = true;
 987       break;
 988     case ISD::AND:
 989       InsMask &= (unsigned)CN->getValue();
 990       break;
 991     }
 992   } else {
 993     return false;
 994   }
 995
 996   // Verify that the Target mask and Insert mask together form a full word mask
 997   // and that the Insert mask is a run of set bits (which implies both are runs
 998   // of set bits).  Given that, Select the arguments and generate the rlwimi
 999   // instruction.
1000   unsigned MB, ME;
1001   if (((TgtMask ^ InsMask) == 0xFFFFFFFF) && IsRunOfOnes(InsMask, MB, ME)) {
1002     unsigned Tmp1, Tmp2;
1003     // Check for rotlwi / rotrwi here, a special case of bitfield insert
1004     // where both bitfield halves are sourced from the same value.
1005     if (IsRotate &&
1006         OR.getOperand(0).getOperand(0) == OR.getOperand(1).getOperand(0)) {
1007       Tmp1 = SelectExpr(OR.getOperand(0).getOperand(0));
1008       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Amount)
1009         .addImm(0).addImm(31);
1010       return true;
1011     }
1012     if (Op0Opc == ISD::AND)
1013       Tmp1 = SelectExpr(OR.getOperand(0).getOperand(0));
1014     else
1015       Tmp1 = SelectExpr(OR.getOperand(0));
1016     Tmp2 = SelectExpr(OR.getOperand(1).getOperand(0));
1017     BuildMI(BB, PPC::RLWIMI, 5, Result).addReg(Tmp1).addReg(Tmp2)
1018       .addImm(Amount).addImm(MB).addImm(ME);
1019     return true;
1020   }
1021   return false;
1022 }
1023
1024 /// FoldIfWideZeroExtend - 32 bit PowerPC implicit masks shift amounts to the
1025 /// low six bits.  If the shift amount is an ISD::AND node with a mask that is
1026 /// wider than the implicit mask, then we can get rid of the AND and let the
1027 /// shift do the mask.
1028 unsigned ISel::FoldIfWideZeroExtend(SDOperand N) {
1029   unsigned C;
1030   if (N.getOpcode() == ISD::AND &&
1031       5 == getImmediateForOpcode(N.getOperand(1), ISD::AND, C) && // isMask
1032       31 == (C & 0xFFFF) && // ME
1033       26 >= (C >> 16))      // MB
1034     return SelectExpr(N.getOperand(0));
1035   else
1036     return SelectExpr(N);
1037 }
1038
1039 unsigned ISel::SelectCC(SDOperand CC, unsigned& Opc, bool &Inv, unsigned& Idx) {
1040   unsigned Result, Tmp1, Tmp2;
1041   bool AlreadySelected = false;
1042   static const unsigned CompareOpcodes[] =
1043     { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
1044
1045   // Allocate a condition register for this expression
1046   Result = RegMap->createVirtualRegister(PPC32::CRRCRegisterClass);
1047
1048   // If the first operand to the select is a SETCC node, then we can fold it
1049   // into the branch that selects which value to return.
1050   if (SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val)) {
1051     bool U;
1052     Opc = getBCCForSetCC(SetCC->getCondition(), U);
1053     Idx = getCRIdxForSetCC(SetCC->getCondition(), Inv);
1054
1055     // Pass the optional argument U to getImmediateForOpcode for SETCC,
1056     // so that it knows whether the SETCC immediate range is signed or not.
1057     if (1 == getImmediateForOpcode(SetCC->getOperand(1), ISD::SETCC,
1058                                    Tmp2, U)) {
1059       // For comparisons against zero, we can implicity set CR0 if a recording
1060       // variant (e.g. 'or.' instead of 'or') of the instruction that defines
1061       // operand zero of the SetCC node is available.
1062       if (0 == Tmp2 &&
1063           NodeHasRecordingVariant(SetCC->getOperand(0).getOpcode()) &&
1064           SetCC->getOperand(0).Val->hasOneUse()) {
1065         RecordSuccess = false;
1066         Tmp1 = SelectExpr(SetCC->getOperand(0), true);
1067         if (RecordSuccess) {
1068           ++Recorded;
1069           BuildMI(BB, PPC::MCRF, 1, Result).addReg(PPC::CR0);
1070           return Result;
1071         }
1072         AlreadySelected = true;
1073       }
1074       // If we could not implicitly set CR0, then emit a compare immediate
1075       // instead.
1076       if (!AlreadySelected) Tmp1 = SelectExpr(SetCC->getOperand(0));
1077       if (U)
1078         BuildMI(BB, PPC::CMPLWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1079       else
1080         BuildMI(BB, PPC::CMPWI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1081     } else {
1082       bool IsInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
1083       unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
1084       Tmp1 = SelectExpr(SetCC->getOperand(0));
1085       Tmp2 = SelectExpr(SetCC->getOperand(1));
1086       BuildMI(BB, CompareOpc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1087     }
1088   } else {
1089     if (PPCCRopts)
1090       return SelectCCExpr(CC, Opc, Inv, Idx);
1091     // If this isn't a SetCC, then select the value and compare it against zero,
1092     // treating it as if it were a boolean.
1093     Opc = PPC::BNE;
1094     Idx = getCRIdxForSetCC(ISD::SETNE, Inv);
1095     Tmp1 = SelectExpr(CC);
1096     BuildMI(BB, PPC::CMPLWI, 2, Result).addReg(Tmp1).addImm(0);
1097   }
1098   return Result;
1099 }
1100
1101 unsigned ISel::SelectCCExpr(SDOperand N, unsigned& Opc, bool &Inv,
1102                             unsigned &Idx) {
1103   bool Inv0, Inv1;
1104   unsigned Idx0, Idx1, CROpc, Opc1, Tmp1, Tmp2;
1105
1106   // Allocate a condition register for this expression
1107   unsigned Result = RegMap->createVirtualRegister(PPC32::CRRCRegisterClass);
1108
1109   // Check for the operations we support:
1110   switch(N.getOpcode()) {
1111   default:
1112     Opc = PPC::BNE;
1113     Idx = getCRIdxForSetCC(ISD::SETNE, Inv);
1114     Tmp1 = SelectExpr(N);
1115     BuildMI(BB, PPC::CMPLWI, 2, Result).addReg(Tmp1).addImm(0);
1116     break;
1117   case ISD::OR:
1118   case ISD::AND:
1119     ++MultiBranch;
1120     Tmp1 = SelectCCExpr(N.getOperand(0), Opc, Inv0, Idx0);
1121     Tmp2 = SelectCCExpr(N.getOperand(1), Opc1, Inv1, Idx1);
1122     CROpc = getCROpForSetCC(N.getOpcode(), Inv0, Inv1);
1123     if (Inv0 && !Inv1) {
1124       std::swap(Tmp1, Tmp2);
1125       std::swap(Idx0, Idx1);
1126       Opc = Opc1;
1127     }
1128     if (Inv0 && Inv1) Opc = PPC32InstrInfo::invertPPCBranchOpcode(Opc);
1129     BuildMI(BB, CROpc, 5, Result).addImm(Idx0).addReg(Tmp1).addImm(Idx0)
1130       .addReg(Tmp2).addImm(Idx1);
1131     Inv = false;
1132     Idx = Idx0;
1133     break;
1134   case ISD::SETCC:
1135     Tmp1 = SelectCC(N, Opc, Inv, Idx);
1136     Result = Tmp1;
1137     break;
1138   }
1139   return Result;
1140 }
1141
1142 /// Check to see if the load is a constant offset from a base register
1143 bool ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
1144 {
1145   unsigned imm = 0, opcode = N.getOpcode();
1146   if (N.getOpcode() == ISD::ADD) {
1147     Reg = SelectExpr(N.getOperand(0));
1148     if (1 == getImmediateForOpcode(N.getOperand(1), opcode, imm)) {
1149       offset = imm;
1150       return false;
1151     }
1152     offset = SelectExpr(N.getOperand(1));
1153     return true;
1154   }
1155   Reg = SelectExpr(N);
1156   offset = 0;
1157   return false;
1158 }
1159
1160 void ISel::SelectBranchCC(SDOperand N)
1161 {
1162   MachineBasicBlock *Dest =
1163     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
1164
1165   bool Inv;
1166   unsigned Opc, CCReg, Idx;
1167   Select(N.getOperand(0));  //chain
1168   CCReg = SelectCC(N.getOperand(1), Opc, Inv, Idx);
1169
1170   // Iterate to the next basic block, unless we're already at the end of the
1171   ilist<MachineBasicBlock>::iterator It = BB, E = BB->getParent()->end();
1172   if (++It == E) It = BB;
1173
1174   // If this is a two way branch, then grab the fallthrough basic block argument
1175   // and build a PowerPC branch pseudo-op, suitable for long branch conversion
1176   // if necessary by the branch selection pass.  Otherwise, emit a standard
1177   // conditional branch.
1178   if (N.getOpcode() == ISD::BRCONDTWOWAY) {
1179     MachineBasicBlock *Fallthrough =
1180       cast<BasicBlockSDNode>(N.getOperand(3))->getBasicBlock();
1181     if (Dest != It) {
1182       BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
1183         .addMBB(Dest).addMBB(Fallthrough);
1184       if (Fallthrough != It)
1185         BuildMI(BB, PPC::B, 1).addMBB(Fallthrough);
1186     } else {
1187       if (Fallthrough != It) {
1188         Opc = PPC32InstrInfo::invertPPCBranchOpcode(Opc);
1189         BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
1190           .addMBB(Fallthrough).addMBB(Dest);
1191       }
1192     }
1193   } else {
1194     BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
1195       .addMBB(Dest).addMBB(It);
1196   }
1197   return;
1198 }
1199
1200 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
1201 {
1202   unsigned Tmp1, Tmp2, Tmp3;
1203   unsigned Opc = 0;
1204   SDNode *Node = N.Val;
1205   MVT::ValueType DestType = N.getValueType();
1206   unsigned opcode = N.getOpcode();
1207
1208   switch (opcode) {
1209   default:
1210     Node->dump();
1211     assert(0 && "Node not handled!\n");
1212
1213   case ISD::SELECT: {
1214     // Attempt to generate FSEL.  We can do this whenever we have an FP result,
1215     // and an FP comparison in the SetCC node.
1216     SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(N.getOperand(0).Val);
1217     if (SetCC && N.getOperand(0).getOpcode() == ISD::SETCC &&
1218         !MVT::isInteger(SetCC->getOperand(0).getValueType()) &&
1219         SetCC->getCondition() != ISD::SETEQ &&
1220         SetCC->getCondition() != ISD::SETNE) {
1221       MVT::ValueType VT = SetCC->getOperand(0).getValueType();
1222       unsigned TV = SelectExpr(N.getOperand(1)); // Use if TRUE
1223       unsigned FV = SelectExpr(N.getOperand(2)); // Use if FALSE
1224
1225       ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1));
1226       if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
1227         switch(SetCC->getCondition()) {
1228         default: assert(0 && "Invalid FSEL condition"); abort();
1229         case ISD::SETULT:
1230         case ISD::SETLT:
1231           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1232         case ISD::SETUGE:
1233         case ISD::SETGE:
1234           Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
1235           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
1236           return Result;
1237         case ISD::SETUGT:
1238         case ISD::SETGT:
1239           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1240         case ISD::SETULE:
1241         case ISD::SETLE: {
1242           if (SetCC->getOperand(0).getOpcode() == ISD::FNEG) {
1243             Tmp2 = SelectExpr(SetCC->getOperand(0).getOperand(0));
1244           } else {
1245             Tmp2 = MakeReg(VT);
1246             Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
1247             BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
1248           }
1249           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
1250           return Result;
1251         }
1252         }
1253       } else {
1254         Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
1255         Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
1256         Tmp2 = SelectExpr(SetCC->getOperand(1));
1257         Tmp3 =  MakeReg(VT);
1258         switch(SetCC->getCondition()) {
1259         default: assert(0 && "Invalid FSEL condition"); abort();
1260         case ISD::SETULT:
1261         case ISD::SETLT:
1262           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1263           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1264           return Result;
1265         case ISD::SETUGE:
1266         case ISD::SETGE:
1267           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1268           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1269           return Result;
1270         case ISD::SETUGT:
1271         case ISD::SETGT:
1272           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1273           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1274           return Result;
1275         case ISD::SETULE:
1276         case ISD::SETLE:
1277           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1278           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1279           return Result;
1280         }
1281       }
1282       assert(0 && "Should never get here");
1283       return 0;
1284     }
1285
1286     bool Inv;
1287     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
1288     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
1289     unsigned CCReg = SelectCC(N.getOperand(0), Opc, Inv, Tmp3);
1290
1291     // Create an iterator with which to insert the MBB for copying the false
1292     // value and the MBB to hold the PHI instruction for this SetCC.
1293     MachineBasicBlock *thisMBB = BB;
1294     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1295     ilist<MachineBasicBlock>::iterator It = BB;
1296     ++It;
1297
1298     //  thisMBB:
1299     //  ...
1300     //   TrueVal = ...
1301     //   cmpTY ccX, r1, r2
1302     //   bCC copy1MBB
1303     //   fallthrough --> copy0MBB
1304     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1305     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1306     BuildMI(BB, Opc, 2).addReg(CCReg).addMBB(sinkMBB);
1307     MachineFunction *F = BB->getParent();
1308     F->getBasicBlockList().insert(It, copy0MBB);
1309     F->getBasicBlockList().insert(It, sinkMBB);
1310     // Update machine-CFG edges
1311     BB->addSuccessor(copy0MBB);
1312     BB->addSuccessor(sinkMBB);
1313
1314     //  copy0MBB:
1315     //   %FalseValue = ...
1316     //   # fallthrough to sinkMBB
1317     BB = copy0MBB;
1318     // Update machine-CFG edges
1319     BB->addSuccessor(sinkMBB);
1320
1321     //  sinkMBB:
1322     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1323     //  ...
1324     BB = sinkMBB;
1325     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1326       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1327     return Result;
1328   }
1329
1330   case ISD::FNEG:
1331     if (!NoExcessFPPrecision &&
1332         ISD::ADD == N.getOperand(0).getOpcode() &&
1333         N.getOperand(0).Val->hasOneUse() &&
1334         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
1335         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
1336       ++FusedFP; // Statistic
1337       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
1338       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
1339       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
1340       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1341       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1342     } else if (!NoExcessFPPrecision &&
1343         ISD::ADD == N.getOperand(0).getOpcode() &&
1344         N.getOperand(0).Val->hasOneUse() &&
1345         ISD::MUL == N.getOperand(0).getOperand(1).getOpcode() &&
1346         N.getOperand(0).getOperand(1).Val->hasOneUse()) {
1347       ++FusedFP; // Statistic
1348       Tmp1 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(0));
1349       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(1));
1350       Tmp3 = SelectExpr(N.getOperand(0).getOperand(0));
1351       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1352       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1353     } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
1354       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1355       BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
1356     } else {
1357       Tmp1 = SelectExpr(N.getOperand(0));
1358       BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
1359     }
1360     return Result;
1361
1362   case ISD::FABS:
1363     Tmp1 = SelectExpr(N.getOperand(0));
1364     BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
1365     return Result;
1366
1367   case ISD::FP_ROUND:
1368     assert (DestType == MVT::f32 &&
1369             N.getOperand(0).getValueType() == MVT::f64 &&
1370             "only f64 to f32 conversion supported here");
1371     Tmp1 = SelectExpr(N.getOperand(0));
1372     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
1373     return Result;
1374
1375   case ISD::FP_EXTEND:
1376     assert (DestType == MVT::f64 &&
1377             N.getOperand(0).getValueType() == MVT::f32 &&
1378             "only f32 to f64 conversion supported here");
1379     Tmp1 = SelectExpr(N.getOperand(0));
1380     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1381     return Result;
1382
1383   case ISD::CopyFromReg:
1384     if (Result == 1)
1385       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1386     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
1387     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1388     return Result;
1389
1390   case ISD::ConstantFP: {
1391     ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
1392     Result = getConstDouble(CN->getValue(), Result);
1393     return Result;
1394   }
1395
1396   case ISD::ADD:
1397     if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1398         N.getOperand(0).Val->hasOneUse()) {
1399       ++FusedFP; // Statistic
1400       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1401       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1402       Tmp3 = SelectExpr(N.getOperand(1));
1403       Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1404       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1405       return Result;
1406     }
1407     if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1408         N.getOperand(1).Val->hasOneUse()) {
1409       ++FusedFP; // Statistic
1410       Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1411       Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1412       Tmp3 = SelectExpr(N.getOperand(0));
1413       Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1414       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1415       return Result;
1416     }
1417     Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
1418     Tmp1 = SelectExpr(N.getOperand(0));
1419     Tmp2 = SelectExpr(N.getOperand(1));
1420     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1421     return Result;
1422
1423   case ISD::SUB:
1424     if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1425         N.getOperand(0).Val->hasOneUse()) {
1426       ++FusedFP; // Statistic
1427       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1428       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1429       Tmp3 = SelectExpr(N.getOperand(1));
1430       Opc = DestType == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS;
1431       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1432       return Result;
1433     }
1434     if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1435         N.getOperand(1).Val->hasOneUse()) {
1436       ++FusedFP; // Statistic
1437       Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1438       Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1439       Tmp3 = SelectExpr(N.getOperand(0));
1440       Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
1441       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1442       return Result;
1443     }
1444     Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS;
1445     Tmp1 = SelectExpr(N.getOperand(0));
1446     Tmp2 = SelectExpr(N.getOperand(1));
1447     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1448     return Result;
1449
1450   case ISD::MUL:
1451   case ISD::SDIV:
1452     switch( opcode ) {
1453     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
1454     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
1455     };
1456     Tmp1 = SelectExpr(N.getOperand(0));
1457     Tmp2 = SelectExpr(N.getOperand(1));
1458     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1459     return Result;
1460
1461   case ISD::UINT_TO_FP:
1462   case ISD::SINT_TO_FP: {
1463     assert (N.getOperand(0).getValueType() == MVT::i32
1464             && "int to float must operate on i32");
1465     bool IsUnsigned = (ISD::UINT_TO_FP == opcode);
1466     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1467     Tmp2 = MakeReg(MVT::f64); // temp reg to load the integer value into
1468     Tmp3 = MakeReg(MVT::i32); // temp reg to hold the conversion constant
1469
1470     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1471     MachineConstantPool *CP = BB->getParent()->getConstantPool();
1472
1473     if (IsUnsigned) {
1474       unsigned ConstF = getConstDouble(0x1.000000p52);
1475       // Store the hi & low halves of the fp value, currently in int regs
1476       BuildMI(BB, PPC::LIS, 1, Tmp3).addSImm(0x4330);
1477       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp3), FrameIdx);
1478       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp1), FrameIdx, 4);
1479       addFrameReference(BuildMI(BB, PPC::LFD, 2, Tmp2), FrameIdx);
1480       // Generate the return value with a subtract
1481       BuildMI(BB, PPC::FSUB, 2, Result).addReg(Tmp2).addReg(ConstF);
1482     } else {
1483       unsigned ConstF = getConstDouble(0x1.000008p52);
1484       unsigned TmpL = MakeReg(MVT::i32);
1485       // Store the hi & low halves of the fp value, currently in int regs
1486       BuildMI(BB, PPC::LIS, 1, Tmp3).addSImm(0x4330);
1487       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp3), FrameIdx);
1488       BuildMI(BB, PPC::XORIS, 2, TmpL).addReg(Tmp1).addImm(0x8000);
1489       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(TmpL), FrameIdx, 4);
1490       addFrameReference(BuildMI(BB, PPC::LFD, 2, Tmp2), FrameIdx);
1491       // Generate the return value with a subtract
1492       BuildMI(BB, PPC::FSUB, 2, Result).addReg(Tmp2).addReg(ConstF);
1493     }
1494     return Result;
1495   }
1496   }
1497   assert(0 && "Should never get here");
1498   return 0;
1499 }
1500
1501 unsigned ISel::SelectExpr(SDOperand N, bool Recording) {
1502   unsigned Result;
1503   unsigned Tmp1, Tmp2, Tmp3;
1504   unsigned Opc = 0;
1505   unsigned opcode = N.getOpcode();
1506
1507   SDNode *Node = N.Val;
1508   MVT::ValueType DestType = N.getValueType();
1509
1510   unsigned &Reg = ExprMap[N];
1511   if (Reg) return Reg;
1512
1513   switch (N.getOpcode()) {
1514   default:
1515     Reg = Result = (N.getValueType() != MVT::Other) ?
1516                             MakeReg(N.getValueType()) : 1;
1517     break;
1518   case ISD::CALL:
1519     // If this is a call instruction, make sure to prepare ALL of the result
1520     // values as well as the chain.
1521     if (Node->getNumValues() == 1)
1522       Reg = Result = 1;  // Void call, just a chain.
1523     else {
1524       Result = MakeReg(Node->getValueType(0));
1525       ExprMap[N.getValue(0)] = Result;
1526       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
1527         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
1528       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
1529     }
1530     break;
1531   case ISD::ADD_PARTS:
1532   case ISD::SUB_PARTS:
1533   case ISD::SHL_PARTS:
1534   case ISD::SRL_PARTS:
1535   case ISD::SRA_PARTS:
1536     Result = MakeReg(Node->getValueType(0));
1537     ExprMap[N.getValue(0)] = Result;
1538     for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
1539       ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
1540     break;
1541   }
1542
1543   if (ISD::CopyFromReg == opcode)
1544     DestType = N.getValue(0).getValueType();
1545
1546   if (DestType == MVT::f64 || DestType == MVT::f32)
1547     if (ISD::LOAD != opcode && ISD::EXTLOAD != opcode &&
1548         ISD::UNDEF != opcode && ISD::CALL != opcode)
1549       return SelectExprFP(N, Result);
1550
1551   switch (opcode) {
1552   default:
1553     Node->dump();
1554     assert(0 && "Node not handled!\n");
1555   case ISD::UNDEF:
1556     BuildMI(BB, PPC::IMPLICIT_DEF, 0, Result);
1557     return Result;
1558   case ISD::DYNAMIC_STACKALLOC:
1559     // Generate both result values.  FIXME: Need a better commment here?
1560     if (Result != 1)
1561       ExprMap[N.getValue(1)] = 1;
1562     else
1563       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1564
1565     // FIXME: We are currently ignoring the requested alignment for handling
1566     // greater than the stack alignment.  This will need to be revisited at some
1567     // point.  Align = N.getOperand(2);
1568     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1569         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1570       std::cerr << "Cannot allocate stack object with greater alignment than"
1571                 << " the stack alignment yet!";
1572       abort();
1573     }
1574     Select(N.getOperand(0));
1575     Tmp1 = SelectExpr(N.getOperand(1));
1576     // Subtract size from stack pointer, thereby allocating some space.
1577     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
1578     // Put a pointer to the space into the result register by copying the SP
1579     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
1580     return Result;
1581
1582   case ISD::ConstantPool:
1583     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
1584     Tmp2 = MakeReg(MVT::i32);
1585     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp2).addReg(getGlobalBaseReg())
1586       .addConstantPoolIndex(Tmp1);
1587     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
1588     return Result;
1589
1590   case ISD::FrameIndex:
1591     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
1592     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
1593     return Result;
1594
1595   case ISD::GlobalAddress: {
1596     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
1597     Tmp1 = MakeReg(MVT::i32);
1598     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
1599       .addGlobalAddress(GV);
1600     if (GV->hasWeakLinkage() || GV->isExternal()) {
1601       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
1602     } else {
1603       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
1604     }
1605     return Result;
1606   }
1607
1608   case ISD::LOAD:
1609   case ISD::EXTLOAD:
1610   case ISD::ZEXTLOAD:
1611   case ISD::SEXTLOAD: {
1612     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
1613       Node->getValueType(0) : cast<MVTSDNode>(Node)->getExtraValueType();
1614     bool sext = (ISD::SEXTLOAD == opcode);
1615
1616     // Make sure we generate both values.
1617     if (Result != 1)
1618       ExprMap[N.getValue(1)] = 1;   // Generate the token
1619     else
1620       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1621
1622     SDOperand Chain   = N.getOperand(0);
1623     SDOperand Address = N.getOperand(1);
1624     Select(Chain);
1625
1626     switch (TypeBeingLoaded) {
1627     default: Node->dump(); assert(0 && "Cannot load this type!");
1628     case MVT::i1:  Opc = PPC::LBZ; break;
1629     case MVT::i8:  Opc = PPC::LBZ; break;
1630     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
1631     case MVT::i32: Opc = PPC::LWZ; break;
1632     case MVT::f32: Opc = PPC::LFS; break;
1633     case MVT::f64: Opc = PPC::LFD; break;
1634     }
1635
1636     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
1637       Tmp1 = MakeReg(MVT::i32);
1638       int CPI = CP->getIndex();
1639       BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
1640         .addConstantPoolIndex(CPI);
1641       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
1642     }
1643     else if(Address.getOpcode() == ISD::FrameIndex) {
1644       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
1645       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
1646     } else {
1647       int offset;
1648       bool idx = SelectAddr(Address, Tmp1, offset);
1649       if (idx) {
1650         Opc = IndexedOpForOp(Opc);
1651         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(offset);
1652       } else {
1653         BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
1654       }
1655     }
1656     return Result;
1657   }
1658
1659   case ISD::CALL: {
1660     unsigned GPR_idx = 0, FPR_idx = 0;
1661     static const unsigned GPR[] = {
1662       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
1663       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
1664     };
1665     static const unsigned FPR[] = {
1666       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
1667       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
1668     };
1669
1670     // Lower the chain for this call.
1671     Select(N.getOperand(0));
1672     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
1673
1674     MachineInstr *CallMI;
1675     // Emit the correct call instruction based on the type of symbol called.
1676     if (GlobalAddressSDNode *GASD =
1677         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
1678       CallMI = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(),
1679                                                            true);
1680     } else if (ExternalSymbolSDNode *ESSDN =
1681                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
1682       CallMI = BuildMI(PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(),
1683                                                             true);
1684     } else {
1685       Tmp1 = SelectExpr(N.getOperand(1));
1686       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
1687       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
1688       CallMI = BuildMI(PPC::CALLindirect, 3).addImm(20).addImm(0)
1689         .addReg(PPC::R12);
1690     }
1691
1692     // Load the register args to virtual regs
1693     std::vector<unsigned> ArgVR;
1694     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
1695       ArgVR.push_back(SelectExpr(N.getOperand(i)));
1696
1697     // Copy the virtual registers into the appropriate argument register
1698     for(int i = 0, e = ArgVR.size(); i < e; ++i) {
1699       switch(N.getOperand(i+2).getValueType()) {
1700       default: Node->dump(); assert(0 && "Unknown value type for call");
1701       case MVT::i1:
1702       case MVT::i8:
1703       case MVT::i16:
1704       case MVT::i32:
1705         assert(GPR_idx < 8 && "Too many int args");
1706         if (N.getOperand(i+2).getOpcode() != ISD::UNDEF) {
1707           BuildMI(BB, PPC::OR,2,GPR[GPR_idx]).addReg(ArgVR[i]).addReg(ArgVR[i]);
1708           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1709         }
1710         ++GPR_idx;
1711         break;
1712       case MVT::f64:
1713       case MVT::f32:
1714         assert(FPR_idx < 13 && "Too many fp args");
1715         BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgVR[i]);
1716         CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1717         ++FPR_idx;
1718         break;
1719       }
1720     }
1721
1722     // Put the call instruction in the correct place in the MachineBasicBlock
1723     BB->push_back(CallMI);
1724
1725     switch (Node->getValueType(0)) {
1726     default: assert(0 && "Unknown value type for call result!");
1727     case MVT::Other: return 1;
1728     case MVT::i1:
1729     case MVT::i8:
1730     case MVT::i16:
1731     case MVT::i32:
1732       if (Node->getValueType(1) == MVT::i32) {
1733         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R3).addReg(PPC::R3);
1734         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R4).addReg(PPC::R4);
1735       } else {
1736         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
1737       }
1738       break;
1739     case MVT::f32:
1740     case MVT::f64:
1741       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
1742       break;
1743     }
1744     return Result+N.ResNo;
1745   }
1746
1747   case ISD::SIGN_EXTEND:
1748   case ISD::SIGN_EXTEND_INREG:
1749     Tmp1 = SelectExpr(N.getOperand(0));
1750     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
1751     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
1752     case MVT::i16:
1753       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
1754       break;
1755     case MVT::i8:
1756       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
1757       break;
1758     case MVT::i1:
1759       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp1).addSImm(0);
1760       break;
1761     }
1762     return Result;
1763
1764   case ISD::CopyFromReg:
1765     if (Result == 1)
1766       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1767     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
1768     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1769     return Result;
1770
1771   case ISD::SHL:
1772     Tmp1 = SelectExpr(N.getOperand(0));
1773     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1774       Tmp2 = CN->getValue() & 0x1F;
1775       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
1776         .addImm(31-Tmp2);
1777     } else {
1778       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1779       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1780     }
1781     return Result;
1782
1783   case ISD::SRL:
1784     Tmp1 = SelectExpr(N.getOperand(0));
1785     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1786       Tmp2 = CN->getValue() & 0x1F;
1787       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(32-Tmp2)
1788         .addImm(Tmp2).addImm(31);
1789     } else {
1790       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1791       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1792     }
1793     return Result;
1794
1795   case ISD::SRA:
1796     Tmp1 = SelectExpr(N.getOperand(0));
1797     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1798       Tmp2 = CN->getValue() & 0x1F;
1799       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1800     } else {
1801       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1802       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1803     }
1804     return Result;
1805
1806   case ISD::ADD:
1807     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
1808     Tmp1 = SelectExpr(N.getOperand(0));
1809     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1810       default: assert(0 && "unhandled result code");
1811       case 0: // No immediate
1812         Tmp2 = SelectExpr(N.getOperand(1));
1813         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1814         break;
1815       case 1: // Low immediate
1816         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1817         break;
1818       case 2: // Shifted immediate
1819         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1820         break;
1821     }
1822     return Result;
1823
1824   case ISD::AND:
1825     if (PPCCRopts) {
1826       if (N.getOperand(0).getOpcode() == ISD::SETCC ||
1827           N.getOperand(1).getOpcode() == ISD::SETCC) {
1828         bool Inv;
1829         Tmp1 = SelectCCExpr(N, Opc, Inv, Tmp2);
1830         MoveCRtoGPR(Tmp1, Inv, Tmp2, Result);
1831         return Result;
1832       }
1833     }
1834     Tmp1 = SelectExpr(N.getOperand(0));
1835     // FIXME: should add check in getImmediateForOpcode to return a value
1836     // indicating the immediate is a run of set bits so we can emit a bitfield
1837     // clear with RLWINM instead.
1838     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1839       default: assert(0 && "unhandled result code");
1840       case 0: // No immediate
1841         Tmp2 = SelectExpr(N.getOperand(1));
1842         Opc = Recording ? PPC::ANDo : PPC::AND;
1843         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1844         break;
1845       case 1: // Low immediate
1846         BuildMI(BB, PPC::ANDIo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1847         break;
1848       case 2: // Shifted immediate
1849         BuildMI(BB, PPC::ANDISo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1850         break;
1851       case 5: // Bitfield mask
1852         Opc = Recording ? PPC::RLWINMo : PPC::RLWINM;
1853         Tmp3 = Tmp2 >> 16;  // MB
1854         Tmp2 &= 0xFFFF;     // ME
1855         BuildMI(BB, Opc, 4, Result).addReg(Tmp1).addImm(0)
1856           .addImm(Tmp3).addImm(Tmp2);
1857         break;
1858     }
1859     RecordSuccess = true;
1860     return Result;
1861
1862   case ISD::OR:
1863     if (SelectBitfieldInsert(N, Result))
1864       return Result;
1865     if (PPCCRopts) {
1866       if (N.getOperand(0).getOpcode() == ISD::SETCC ||
1867           N.getOperand(1).getOpcode() == ISD::SETCC) {
1868         bool Inv;
1869         Tmp1 = SelectCCExpr(N, Opc, Inv, Tmp2);
1870         MoveCRtoGPR(Tmp1, Inv, Tmp2, Result);
1871         return Result;
1872       }
1873     }
1874     Tmp1 = SelectExpr(N.getOperand(0));
1875     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1876       default: assert(0 && "unhandled result code");
1877       case 0: // No immediate
1878         Tmp2 = SelectExpr(N.getOperand(1));
1879         Opc = Recording ? PPC::ORo : PPC::OR;
1880         RecordSuccess = true;
1881         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1882         break;
1883       case 1: // Low immediate
1884         BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1885         break;
1886       case 2: // Shifted immediate
1887         BuildMI(BB, PPC::ORIS, 2, Result).addReg(Tmp1).addImm(Tmp2);
1888         break;
1889     }
1890     return Result;
1891
1892   case ISD::XOR: {
1893     // Check for EQV: xor, (xor a, -1), b
1894     if (N.getOperand(0).getOpcode() == ISD::XOR &&
1895         N.getOperand(0).getOperand(1).getOpcode() == ISD::Constant &&
1896         cast<ConstantSDNode>(N.getOperand(0).getOperand(1))->isAllOnesValue()) {
1897       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1898       Tmp2 = SelectExpr(N.getOperand(1));
1899       BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1900       return Result;
1901     }
1902     // Check for NOT, NOR, EQV, and NAND: xor (copy, or, xor, and), -1
1903     if (N.getOperand(1).getOpcode() == ISD::Constant &&
1904         cast<ConstantSDNode>(N.getOperand(1))->isAllOnesValue()) {
1905       switch(N.getOperand(0).getOpcode()) {
1906       case ISD::OR:
1907         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1908         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1909         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1910         break;
1911       case ISD::AND:
1912         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1913         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1914         BuildMI(BB, PPC::NAND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1915         break;
1916       case ISD::XOR:
1917         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1918         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1919         BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1920         break;
1921       default:
1922         Tmp1 = SelectExpr(N.getOperand(0));
1923         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1924         break;
1925       }
1926       return Result;
1927     }
1928     Tmp1 = SelectExpr(N.getOperand(0));
1929     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1930       default: assert(0 && "unhandled result code");
1931       case 0: // No immediate
1932         Tmp2 = SelectExpr(N.getOperand(1));
1933         BuildMI(BB, PPC::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1934         break;
1935       case 1: // Low immediate
1936         BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1937         break;
1938       case 2: // Shifted immediate
1939         BuildMI(BB, PPC::XORIS, 2, Result).addReg(Tmp1).addImm(Tmp2);
1940         break;
1941     }
1942     return Result;
1943   }
1944
1945   case ISD::SUB:
1946     Tmp2 = SelectExpr(N.getOperand(1));
1947     if (1 == getImmediateForOpcode(N.getOperand(0), opcode, Tmp1))
1948       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp2).addSImm(Tmp1);
1949     else {
1950       Tmp1 = SelectExpr(N.getOperand(0));
1951       BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1952     }
1953     return Result;
1954
1955   case ISD::MUL:
1956     Tmp1 = SelectExpr(N.getOperand(0));
1957     if (1 == getImmediateForOpcode(N.getOperand(1), opcode, Tmp2))
1958       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1959     else {
1960       Tmp2 = SelectExpr(N.getOperand(1));
1961       BuildMI(BB, PPC::MULLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1962     }
1963     return Result;
1964
1965   case ISD::MULHS:
1966   case ISD::MULHU:
1967     Tmp1 = SelectExpr(N.getOperand(0));
1968     Tmp2 = SelectExpr(N.getOperand(1));
1969     Opc = (ISD::MULHU == opcode) ? PPC::MULHWU : PPC::MULHW;
1970     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1971     return Result;
1972
1973   case ISD::SDIV:
1974   case ISD::UDIV:
1975     switch (getImmediateForOpcode(N.getOperand(1), opcode, Tmp3)) {
1976     default: break;
1977     // If this is an sdiv by a power of two, we can use an srawi/addze pair.
1978     case 3:
1979       Tmp1 = MakeReg(MVT::i32);
1980       Tmp2 = SelectExpr(N.getOperand(0));
1981       if ((int)Tmp3 < 0) {
1982         unsigned Tmp4 = MakeReg(MVT::i32);
1983         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(-Tmp3);
1984         BuildMI(BB, PPC::ADDZE, 1, Tmp4).addReg(Tmp1);
1985         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp4);
1986       } else {
1987         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1988         BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp1);
1989       }
1990       return Result;
1991     // If this is a divide by constant, we can emit code using some magic
1992     // constants to implement it as a multiply instead.
1993     case 4:
1994       ExprMap.erase(N);
1995       if (opcode == ISD::SDIV)
1996         return SelectExpr(BuildSDIVSequence(N));
1997       else
1998         return SelectExpr(BuildUDIVSequence(N));
1999     }
2000     Tmp1 = SelectExpr(N.getOperand(0));
2001     Tmp2 = SelectExpr(N.getOperand(1));
2002     Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW;
2003     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
2004     return Result;
2005
2006   case ISD::ADD_PARTS:
2007   case ISD::SUB_PARTS: {
2008     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
2009            "Not an i64 add/sub!");
2010     // Emit all of the operands.
2011     std::vector<unsigned> InVals;
2012     for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)
2013       InVals.push_back(SelectExpr(N.getOperand(i)));
2014     if (N.getOpcode() == ISD::ADD_PARTS) {
2015       BuildMI(BB, PPC::ADDC, 2, Result).addReg(InVals[0]).addReg(InVals[2]);
2016       BuildMI(BB, PPC::ADDE, 2, Result+1).addReg(InVals[1]).addReg(InVals[3]);
2017     } else {
2018       BuildMI(BB, PPC::SUBFC, 2, Result).addReg(InVals[2]).addReg(InVals[0]);
2019       BuildMI(BB, PPC::SUBFE, 2, Result+1).addReg(InVals[3]).addReg(InVals[1]);
2020     }
2021     return Result+N.ResNo;
2022   }
2023
2024   case ISD::SHL_PARTS:
2025   case ISD::SRA_PARTS:
2026   case ISD::SRL_PARTS: {
2027     assert(N.getNumOperands() == 3 && N.getValueType() == MVT::i32 &&
2028            "Not an i64 shift!");
2029     unsigned ShiftOpLo = SelectExpr(N.getOperand(0));
2030     unsigned ShiftOpHi = SelectExpr(N.getOperand(1));
2031     unsigned SHReg = FoldIfWideZeroExtend(N.getOperand(2));
2032     Tmp1 = MakeReg(MVT::i32);
2033     Tmp2 = MakeReg(MVT::i32);
2034     Tmp3 = MakeReg(MVT::i32);
2035     unsigned Tmp4 = MakeReg(MVT::i32);
2036     unsigned Tmp5 = MakeReg(MVT::i32);
2037     unsigned Tmp6 = MakeReg(MVT::i32);
2038     BuildMI(BB, PPC::SUBFIC, 2, Tmp1).addReg(SHReg).addSImm(32);
2039     if (ISD::SHL_PARTS == opcode) {
2040       BuildMI(BB, PPC::SLW, 2, Tmp2).addReg(ShiftOpHi).addReg(SHReg);
2041       BuildMI(BB, PPC::SRW, 2, Tmp3).addReg(ShiftOpLo).addReg(Tmp1);
2042       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
2043       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
2044       BuildMI(BB, PPC::SLW, 2, Tmp6).addReg(ShiftOpLo).addReg(Tmp5);
2045       BuildMI(BB, PPC::OR, 2, Result+1).addReg(Tmp4).addReg(Tmp6);
2046       BuildMI(BB, PPC::SLW, 2, Result).addReg(ShiftOpLo).addReg(SHReg);
2047     } else if (ISD::SRL_PARTS == opcode) {
2048       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
2049       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
2050       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
2051       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
2052       BuildMI(BB, PPC::SRW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
2053       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp4).addReg(Tmp6);
2054       BuildMI(BB, PPC::SRW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
2055     } else {
2056       MachineBasicBlock *TmpMBB = new MachineBasicBlock(BB->getBasicBlock());
2057       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
2058       MachineBasicBlock *OldMBB = BB;
2059       MachineFunction *F = BB->getParent();
2060       ilist<MachineBasicBlock>::iterator It = BB; ++It;
2061       F->getBasicBlockList().insert(It, TmpMBB);
2062       F->getBasicBlockList().insert(It, PhiMBB);
2063       BB->addSuccessor(TmpMBB);
2064       BB->addSuccessor(PhiMBB);
2065       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
2066       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
2067       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
2068       BuildMI(BB, PPC::ADDICo, 2, Tmp5).addReg(SHReg).addSImm(-32);
2069       BuildMI(BB, PPC::SRAW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
2070       BuildMI(BB, PPC::SRAW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
2071       BuildMI(BB, PPC::BLE, 2).addReg(PPC::CR0).addMBB(PhiMBB);
2072       // Select correct least significant half if the shift amount > 32
2073       BB = TmpMBB;
2074       unsigned Tmp7 = MakeReg(MVT::i32);
2075       BuildMI(BB, PPC::OR, 2, Tmp7).addReg(Tmp6).addReg(Tmp6);
2076       TmpMBB->addSuccessor(PhiMBB);
2077       BB = PhiMBB;
2078       BuildMI(BB, PPC::PHI, 4, Result).addReg(Tmp4).addMBB(OldMBB)
2079         .addReg(Tmp7).addMBB(TmpMBB);
2080     }
2081     return Result+N.ResNo;
2082   }
2083
2084   case ISD::FP_TO_UINT:
2085   case ISD::FP_TO_SINT: {
2086     bool U = (ISD::FP_TO_UINT == opcode);
2087     Tmp1 = SelectExpr(N.getOperand(0));
2088     if (!U) {
2089       Tmp2 = MakeReg(MVT::f64);
2090       BuildMI(BB, PPC::FCTIWZ, 1, Tmp2).addReg(Tmp1);
2091       int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
2092       addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(Tmp2), FrameIdx);
2093       addFrameReference(BuildMI(BB, PPC::LWZ, 2, Result), FrameIdx, 4);
2094       return Result;
2095     } else {
2096       unsigned Zero = getConstDouble(0.0);
2097       unsigned MaxInt = getConstDouble((1LL << 32) - 1);
2098       unsigned Border = getConstDouble(1LL << 31);
2099       unsigned UseZero = MakeReg(MVT::f64);
2100       unsigned UseMaxInt = MakeReg(MVT::f64);
2101       unsigned UseChoice = MakeReg(MVT::f64);
2102       unsigned TmpReg = MakeReg(MVT::f64);
2103       unsigned TmpReg2 = MakeReg(MVT::f64);
2104       unsigned ConvReg = MakeReg(MVT::f64);
2105       unsigned IntTmp = MakeReg(MVT::i32);
2106       unsigned XorReg = MakeReg(MVT::i32);
2107       MachineFunction *F = BB->getParent();
2108       int FrameIdx = F->getFrameInfo()->CreateStackObject(8, 8);
2109       // Update machine-CFG edges
2110       MachineBasicBlock *XorMBB = new MachineBasicBlock(BB->getBasicBlock());
2111       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
2112       MachineBasicBlock *OldMBB = BB;
2113       ilist<MachineBasicBlock>::iterator It = BB; ++It;
2114       F->getBasicBlockList().insert(It, XorMBB);
2115       F->getBasicBlockList().insert(It, PhiMBB);
2116       BB->addSuccessor(XorMBB);
2117       BB->addSuccessor(PhiMBB);
2118       // Convert from floating point to unsigned 32-bit value
2119       // Use 0 if incoming value is < 0.0
2120       BuildMI(BB, PPC::FSEL, 3, UseZero).addReg(Tmp1).addReg(Tmp1).addReg(Zero);
2121       // Use 2**32 - 1 if incoming value is >= 2**32
2122       BuildMI(BB, PPC::FSUB, 2, UseMaxInt).addReg(MaxInt).addReg(Tmp1);
2123       BuildMI(BB, PPC::FSEL, 3, UseChoice).addReg(UseMaxInt).addReg(UseZero)
2124         .addReg(MaxInt);
2125       // Subtract 2**31
2126       BuildMI(BB, PPC::FSUB, 2, TmpReg).addReg(UseChoice).addReg(Border);
2127       // Use difference if >= 2**31
2128       BuildMI(BB, PPC::FCMPU, 2, PPC::CR0).addReg(UseChoice).addReg(Border);
2129       BuildMI(BB, PPC::FSEL, 3, TmpReg2).addReg(TmpReg).addReg(TmpReg)
2130         .addReg(UseChoice);
2131       // Convert to integer
2132       BuildMI(BB, PPC::FCTIWZ, 1, ConvReg).addReg(TmpReg2);
2133       addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(ConvReg), FrameIdx);
2134       addFrameReference(BuildMI(BB, PPC::LWZ, 2, IntTmp), FrameIdx, 4);
2135       BuildMI(BB, PPC::BLT, 2).addReg(PPC::CR0).addMBB(PhiMBB);
2136       BuildMI(BB, PPC::B, 1).addMBB(XorMBB);
2137
2138       // XorMBB:
2139       //   add 2**31 if input was >= 2**31
2140       BB = XorMBB;
2141       BuildMI(BB, PPC::XORIS, 2, XorReg).addReg(IntTmp).addImm(0x8000);
2142       XorMBB->addSuccessor(PhiMBB);
2143
2144       // PhiMBB:
2145       //   DestReg = phi [ IntTmp, OldMBB ], [ XorReg, XorMBB ]
2146       BB = PhiMBB;
2147       BuildMI(BB, PPC::PHI, 4, Result).addReg(IntTmp).addMBB(OldMBB)
2148         .addReg(XorReg).addMBB(XorMBB);
2149       return Result;
2150     }
2151     assert(0 && "Should never get here");
2152     return 0;
2153   }
2154
2155   case ISD::SETCC:
2156     if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Node)) {
2157       if (ConstantSDNode *CN =
2158           dyn_cast<ConstantSDNode>(SetCC->getOperand(1).Val)) {
2159         // We can codegen setcc op, imm very efficiently compared to a brcond.
2160         // Check for those cases here.
2161         // setcc op, 0
2162         if (CN->getValue() == 0) {
2163           Tmp1 = SelectExpr(SetCC->getOperand(0));
2164           switch (SetCC->getCondition()) {
2165           default: SetCC->dump(); assert(0 && "Unhandled SetCC condition"); abort();
2166           case ISD::SETEQ:
2167             Tmp2 = MakeReg(MVT::i32);
2168             BuildMI(BB, PPC::CNTLZW, 1, Tmp2).addReg(Tmp1);
2169             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp2).addImm(27)
2170               .addImm(5).addImm(31);
2171             break;
2172           case ISD::SETNE:
2173             Tmp2 = MakeReg(MVT::i32);
2174             BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
2175             BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
2176             break;
2177           case ISD::SETLT:
2178             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(1)
2179               .addImm(31).addImm(31);
2180             break;
2181           case ISD::SETGT:
2182             Tmp2 = MakeReg(MVT::i32);
2183             Tmp3 = MakeReg(MVT::i32);
2184             BuildMI(BB, PPC::NEG, 2, Tmp2).addReg(Tmp1);
2185             BuildMI(BB, PPC::ANDC, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
2186             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
2187               .addImm(31).addImm(31);
2188             break;
2189           }
2190           return Result;
2191         }
2192         // setcc op, -1
2193         if (CN->isAllOnesValue()) {
2194           Tmp1 = SelectExpr(SetCC->getOperand(0));
2195           switch (SetCC->getCondition()) {
2196           default: assert(0 && "Unhandled SetCC condition"); abort();
2197           case ISD::SETEQ:
2198             Tmp2 = MakeReg(MVT::i32);
2199             Tmp3 = MakeReg(MVT::i32);
2200             BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(1);
2201             BuildMI(BB, PPC::LI, 1, Tmp3).addSImm(0);
2202             BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp3);
2203             break;
2204           case ISD::SETNE:
2205             Tmp2 = MakeReg(MVT::i32);
2206             Tmp3 = MakeReg(MVT::i32);
2207             BuildMI(BB, PPC::NOR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
2208             BuildMI(BB, PPC::ADDIC, 2, Tmp3).addReg(Tmp2).addSImm(-1);
2209             BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp3).addReg(Tmp2);
2210             break;
2211           case ISD::SETLT:
2212             Tmp2 = MakeReg(MVT::i32);
2213             Tmp3 = MakeReg(MVT::i32);
2214             BuildMI(BB, PPC::ADDI, 2, Tmp2).addReg(Tmp1).addSImm(1);
2215             BuildMI(BB, PPC::AND, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
2216             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
2217               .addImm(31).addImm(31);
2218             break;
2219           case ISD::SETGT:
2220             Tmp2 = MakeReg(MVT::i32);
2221             BuildMI(BB, PPC::RLWINM, 4, Tmp2).addReg(Tmp1).addImm(1)
2222               .addImm(31).addImm(31);
2223             BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp2).addImm(1);
2224             break;
2225           }
2226           return Result;
2227         }
2228       }
2229
2230       bool Inv;
2231       unsigned CCReg = SelectCC(N, Opc, Inv, Tmp2);
2232       MoveCRtoGPR(CCReg, Inv, Tmp2, Result);
2233       return Result;
2234     }
2235     assert(0 && "Is this legal?");
2236     return 0;
2237
2238   case ISD::SELECT: {
2239     bool Inv;
2240     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
2241     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
2242     unsigned CCReg = SelectCC(N.getOperand(0), Opc, Inv, Tmp3);
2243
2244     // Create an iterator with which to insert the MBB for copying the false
2245     // value and the MBB to hold the PHI instruction for this SetCC.
2246     MachineBasicBlock *thisMBB = BB;
2247     const BasicBlock *LLVM_BB = BB->getBasicBlock();
2248     ilist<MachineBasicBlock>::iterator It = BB;
2249     ++It;
2250
2251     //  thisMBB:
2252     //  ...
2253     //   TrueVal = ...
2254     //   cmpTY ccX, r1, r2
2255     //   bCC copy1MBB
2256     //   fallthrough --> copy0MBB
2257     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
2258     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
2259     BuildMI(BB, Opc, 2).addReg(CCReg).addMBB(sinkMBB);
2260     MachineFunction *F = BB->getParent();
2261     F->getBasicBlockList().insert(It, copy0MBB);
2262     F->getBasicBlockList().insert(It, sinkMBB);
2263     // Update machine-CFG edges
2264     BB->addSuccessor(copy0MBB);
2265     BB->addSuccessor(sinkMBB);
2266
2267     //  copy0MBB:
2268     //   %FalseValue = ...
2269     //   # fallthrough to sinkMBB
2270     BB = copy0MBB;
2271     // Update machine-CFG edges
2272     BB->addSuccessor(sinkMBB);
2273
2274     //  sinkMBB:
2275     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
2276     //  ...
2277     BB = sinkMBB;
2278     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
2279       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
2280     return Result;
2281   }
2282
2283   case ISD::Constant:
2284     switch (N.getValueType()) {
2285     default: assert(0 && "Cannot use constants of this type!");
2286     case MVT::i1:
2287       BuildMI(BB, PPC::LI, 1, Result)
2288         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
2289       break;
2290     case MVT::i32:
2291       {
2292         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
2293         if (v < 32768 && v >= -32768) {
2294           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
2295         } else {
2296           Tmp1 = MakeReg(MVT::i32);
2297           BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
2298           BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(v & 0xFFFF);
2299         }
2300       }
2301     }
2302     return Result;
2303   }
2304
2305   return 0;
2306 }
2307
2308 void ISel::Select(SDOperand N) {
2309   unsigned Tmp1, Tmp2, Opc;
2310   unsigned opcode = N.getOpcode();
2311
2312   if (!ExprMap.insert(std::make_pair(N, 1)).second)
2313     return;  // Already selected.
2314
2315   SDNode *Node = N.Val;
2316
2317   switch (Node->getOpcode()) {
2318   default:
2319     Node->dump(); std::cerr << "\n";
2320     assert(0 && "Node not handled yet!");
2321   case ISD::EntryToken: return;  // Noop
2322   case ISD::TokenFactor:
2323     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
2324       Select(Node->getOperand(i));
2325     return;
2326   case ISD::ADJCALLSTACKDOWN:
2327   case ISD::ADJCALLSTACKUP:
2328     Select(N.getOperand(0));
2329     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
2330     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? PPC::ADJCALLSTACKDOWN :
2331       PPC::ADJCALLSTACKUP;
2332     BuildMI(BB, Opc, 1).addImm(Tmp1);
2333     return;
2334   case ISD::BR: {
2335     MachineBasicBlock *Dest =
2336       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
2337     Select(N.getOperand(0));
2338     BuildMI(BB, PPC::B, 1).addMBB(Dest);
2339     return;
2340   }
2341   case ISD::BRCOND:
2342   case ISD::BRCONDTWOWAY:
2343     SelectBranchCC(N);
2344     return;
2345   case ISD::CopyToReg:
2346     Select(N.getOperand(0));
2347     Tmp1 = SelectExpr(N.getOperand(1));
2348     Tmp2 = cast<RegSDNode>(N)->getReg();
2349
2350     if (Tmp1 != Tmp2) {
2351       if (N.getOperand(1).getValueType() == MVT::f64 ||
2352           N.getOperand(1).getValueType() == MVT::f32)
2353         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
2354       else
2355         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
2356     }
2357     return;
2358   case ISD::ImplicitDef:
2359     Select(N.getOperand(0));
2360     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
2361     return;
2362   case ISD::RET:
2363     switch (N.getNumOperands()) {
2364     default:
2365       assert(0 && "Unknown return instruction!");
2366     case 3:
2367       assert(N.getOperand(1).getValueType() == MVT::i32 &&
2368              N.getOperand(2).getValueType() == MVT::i32 &&
2369                    "Unknown two-register value!");
2370       Select(N.getOperand(0));
2371       Tmp1 = SelectExpr(N.getOperand(1));
2372       Tmp2 = SelectExpr(N.getOperand(2));
2373       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp2).addReg(Tmp2);
2374       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp1).addReg(Tmp1);
2375       break;
2376     case 2:
2377       Select(N.getOperand(0));
2378       Tmp1 = SelectExpr(N.getOperand(1));
2379       switch (N.getOperand(1).getValueType()) {
2380         default:
2381           assert(0 && "Unknown return type!");
2382         case MVT::f64:
2383         case MVT::f32:
2384           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
2385           break;
2386         case MVT::i32:
2387           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
2388           break;
2389       }
2390     case 1:
2391       Select(N.getOperand(0));
2392       break;
2393     }
2394     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
2395     return;
2396   case ISD::TRUNCSTORE:
2397   case ISD::STORE:
2398     {
2399       SDOperand Chain   = N.getOperand(0);
2400       SDOperand Value   = N.getOperand(1);
2401       SDOperand Address = N.getOperand(2);
2402       Select(Chain);
2403
2404       Tmp1 = SelectExpr(Value); //value
2405
2406       if (opcode == ISD::STORE) {
2407         switch(Value.getValueType()) {
2408         default: assert(0 && "unknown Type in store");
2409         case MVT::i32: Opc = PPC::STW; break;
2410         case MVT::f64: Opc = PPC::STFD; break;
2411         case MVT::f32: Opc = PPC::STFS; break;
2412         }
2413       } else { //ISD::TRUNCSTORE
2414         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
2415         default: assert(0 && "unknown Type in store");
2416         case MVT::i1:
2417         case MVT::i8: Opc  = PPC::STB; break;
2418         case MVT::i16: Opc = PPC::STH; break;
2419         }
2420       }
2421
2422       if(Address.getOpcode() == ISD::FrameIndex)
2423       {
2424         Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
2425         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
2426       }
2427       else
2428       {
2429         int offset;
2430         bool idx = SelectAddr(Address, Tmp2, offset);
2431         if (idx) {
2432           Opc = IndexedOpForOp(Opc);
2433           BuildMI(BB, Opc, 3).addReg(Tmp1).addReg(Tmp2).addReg(offset);
2434         } else {
2435           BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
2436         }
2437       }
2438       return;
2439     }
2440   case ISD::EXTLOAD:
2441   case ISD::SEXTLOAD:
2442   case ISD::ZEXTLOAD:
2443   case ISD::LOAD:
2444   case ISD::CopyFromReg:
2445   case ISD::CALL:
2446   case ISD::DYNAMIC_STACKALLOC:
2447     ExprMap.erase(N);
2448     SelectExpr(N);
2449     return;
2450   }
2451   assert(0 && "Should not be reached!");
2452 }
2453
2454
2455 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
2456 /// into a machine code representation using pattern matching and a machine
2457 /// description file.
2458 ///
2459 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
2460   return new ISel(TM);
2461 }
2462