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