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