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