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 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "PowerPC.h"
  15 #include "PowerPCInstrBuilder.h"
  16 #include "PowerPCInstrInfo.h"
  17 #include "PPC32RegisterInfo.h"
  18 #include "llvm/Constants.h"                   // FIXME: REMOVE
  19 #include "llvm/Function.h"
  20 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/SelectionDAG.h"
  24 #include "llvm/CodeGen/SelectionDAGISel.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/TargetData.h"
  27 #include "llvm/Target/TargetLowering.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/MathExtras.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include <set>
  32 #include <algorithm>
  33 using namespace llvm;
  34
  35 //===----------------------------------------------------------------------===//
  36 //  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
  37 namespace {
  38   class PPC32TargetLowering : public TargetLowering {
  39     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  40     int ReturnAddrIndex;              // FrameIndex for return slot.
  41   public:
  42     PPC32TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  43       // Set up the TargetLowering object.
  44
  45       // Set up the register classes.
  46       addRegisterClass(MVT::i32, PPC32::GPRCRegisterClass);
  47       addRegisterClass(MVT::f32, PPC32::FPRCRegisterClass);
  48       addRegisterClass(MVT::f64, PPC32::FPRCRegisterClass);
  49
  50       setOperationAction(ISD::MEMMOVE, MVT::Other, Expand);
  51       setOperationAction(ISD::MEMSET, MVT::Other, Expand);
  52       setOperationAction(ISD::MEMCPY, MVT::Other, Expand);
  53
  54       computeRegisterProperties();
  55     }
  56
  57     /// LowerArguments - This hook must be implemented to indicate how we should
  58     /// lower the arguments for the specified function, into the specified DAG.
  59     virtual std::vector<SDOperand>
  60     LowerArguments(Function &F, SelectionDAG &DAG);
  61
  62     /// LowerCallTo - This hook lowers an abstract call to a function into an
  63     /// actual call.
  64     virtual std::pair<SDOperand, SDOperand>
  65     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg,
  66                 SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
  67
  68     virtual std::pair<SDOperand, SDOperand>
  69     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
  70
  71     virtual std::pair<SDOperand,SDOperand>
  72     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
  73                    const Type *ArgTy, SelectionDAG &DAG);
  74
  75     virtual std::pair<SDOperand, SDOperand>
  76     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
  77                             SelectionDAG &DAG);
  78   };
  79 }
  80
  81
  82 std::vector<SDOperand>
  83 PPC32TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
  84   //
  85   // add beautiful description of PPC stack frame format, or at least some docs
  86   //
  87   MachineFunction &MF = DAG.getMachineFunction();
  88   MachineFrameInfo *MFI = MF.getFrameInfo();
  89   MachineBasicBlock& BB = MF.front();
  90   std::vector<SDOperand> ArgValues;
  91
  92   // Due to the rather complicated nature of the PowerPC ABI, rather than a
  93   // fixed size array of physical args, for the sake of simplicity let the STL
  94   // handle tracking them for us.
  95   std::vector<unsigned> argVR, argPR, argOp;
  96   unsigned ArgOffset = 24;
  97   unsigned GPR_remaining = 8;
  98   unsigned FPR_remaining = 13;
  99   unsigned GPR_idx = 0, FPR_idx = 0;
 100   static const unsigned GPR[] = {
 101     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 102     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 103   };
 104   static const unsigned FPR[] = {
 105     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 106     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 107   };
 108
 109   // Add DAG nodes to load the arguments...  On entry to a function on PPC,
 110   // the arguments start at offset 24, although they are likely to be passed
 111   // in registers.
 112   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 113     SDOperand newroot, argt;
 114     unsigned ObjSize;
 115     bool needsLoad = false;
 116     MVT::ValueType ObjectVT = getValueType(I->getType());
 117
 118     switch (ObjectVT) {
 119     default: assert(0 && "Unhandled argument type!");
 120     case MVT::i1:
 121     case MVT::i8:
 122     case MVT::i16:
 123     case MVT::i32:
 124       ObjSize = 4;
 125       if (GPR_remaining > 0) {
 126         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 127         argt = newroot = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
 128                                             DAG.getRoot());
 129         if (ObjectVT != MVT::i32)
 130           argt = DAG.getNode(ISD::TRUNCATE, ObjectVT, newroot);
 131       } else {
 132         needsLoad = true;
 133       }
 134       break;
 135       case MVT::i64: ObjSize = 8;
 136       // FIXME: can split 64b load between reg/mem if it is last arg in regs
 137       if (GPR_remaining > 1) {
 138         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 139         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx+1]);
 140         // Copy the extracted halves into the virtual registers
 141         SDOperand argHi = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
 142                                              DAG.getRoot());
 143         SDOperand argLo = DAG.getCopyFromReg(GPR[GPR_idx+1], MVT::i32, argHi);
 144         // Build the outgoing arg thingy
 145         argt = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, argLo, argHi);
 146         newroot = argLo;
 147       } else {
 148         needsLoad = true;
 149       }
 150       break;
 151       case MVT::f32: ObjSize = 4;
 152       case MVT::f64: ObjSize = 8;
 153       if (FPR_remaining > 0) {
 154         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, FPR[FPR_idx]);
 155         argt = newroot = DAG.getCopyFromReg(FPR[FPR_idx], ObjectVT,
 156                                             DAG.getRoot());
 157         --FPR_remaining;
 158         ++FPR_idx;
 159       } else {
 160         needsLoad = true;
 161       }
 162       break;
 163     }
 164
 165     // We need to load the argument to a virtual register if we determined above
 166     // that we ran out of physical registers of the appropriate type
 167     if (needsLoad) {
 168       int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 169       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 170       argt = newroot = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
 171     }
 172
 173     // Every 4 bytes of argument space consumes one of the GPRs available for
 174     // argument passing.
 175     if (GPR_remaining > 0) {
 176       unsigned delta = (GPR_remaining > 1 && ObjSize == 8) ? 2 : 1;
 177       GPR_remaining -= delta;
 178       GPR_idx += delta;
 179     }
 180     ArgOffset += ObjSize;
 181
 182     DAG.setRoot(newroot.getValue(1));
 183     ArgValues.push_back(argt);
 184   }
 185
 186   // If the function takes variable number of arguments, make a frame index for
 187   // the start of the first vararg value... for expansion of llvm.va_start.
 188   if (F.isVarArg())
 189     VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
 190
 191   return ArgValues;
 192 }
 193
 194 std::pair<SDOperand, SDOperand>
 195 PPC32TargetLowering::LowerCallTo(SDOperand Chain,
 196                                  const Type *RetTy, bool isVarArg,
 197          SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG) {
 198   // args_to_use will accumulate outgoing args for the ISD::CALL case in
 199   // SelectExpr to use to put the arguments in the appropriate registers.
 200   std::vector<SDOperand> args_to_use;
 201
 202   // Count how many bytes are to be pushed on the stack, including the linkage
 203   // area, and parameter passing area.
 204   unsigned NumBytes = 24;
 205
 206   if (Args.empty()) {
 207     NumBytes = 0;    // Save zero bytes.
 208   } else {
 209     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 210       switch (getValueType(Args[i].second)) {
 211       default: assert(0 && "Unknown value type!");
 212       case MVT::i1:
 213       case MVT::i8:
 214       case MVT::i16:
 215       case MVT::i32:
 216       case MVT::f32:
 217         NumBytes += 4;
 218         break;
 219       case MVT::i64:
 220       case MVT::f64:
 221         NumBytes += 8;
 222         break;
 223       }
 224
 225     // Just to be safe, we'll always reserve the full 24 bytes of linkage area
 226     // plus 32 bytes of argument space in case any called code gets funky on us.
 227     if (NumBytes < 56) NumBytes = 56;
 228
 229     // Adjust the stack pointer for the new arguments...
 230     // These operations are automatically eliminated by the prolog/epilog pass
 231     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 232                         DAG.getConstant(NumBytes, getPointerTy()));
 233
 234     // Set up a copy of the stack pointer for use loading and storing any
 235     // arguments that may not fit in the registers available for argument
 236     // passing.
 237     SDOperand StackPtr = DAG.getCopyFromReg(PPC::R1, MVT::i32,
 238                                             DAG.getEntryNode());
 239
 240     // Figure out which arguments are going to go in registers, and which in
 241     // memory.  Also, if this is a vararg function, floating point operations
 242     // must be stored to our stack, and loaded into integer regs as well, if
 243     // any integer regs are available for argument passing.
 244     unsigned ArgOffset = 24;
 245     unsigned GPR_remaining = 8;
 246     unsigned FPR_remaining = 13;
 247     std::vector<SDOperand> Stores;
 248     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 249       // PtrOff will be used to store the current argument to the stack if a
 250       // register cannot be found for it.
 251       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 252       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 253       MVT::ValueType ArgVT = getValueType(Args[i].second);
 254
 255       switch (ArgVT) {
 256       default: assert(0 && "Unexpected ValueType for argument!");
 257       case MVT::i1:
 258       case MVT::i8:
 259       case MVT::i16:
 260         // Promote the integer to 32 bits.  If the input type is signed use a
 261         // sign extend, otherwise use a zero extend.
 262         if (Args[i].second->isSigned())
 263           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 264         else
 265           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 266         // FALL THROUGH
 267       case MVT::i32:
 268         if (GPR_remaining > 0) {
 269           args_to_use.push_back(Args[i].first);
 270           --GPR_remaining;
 271         } else {
 272           Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 273                                        Args[i].first, PtrOff));
 274         }
 275         ArgOffset += 4;
 276         break;
 277       case MVT::i64:
 278         // If we have one free GPR left, we can place the upper half of the i64
 279         // in it, and store the other half to the stack.  If we have two or more
 280         // free GPRs, then we can pass both halves of the i64 in registers.
 281         if (GPR_remaining > 0) {
 282           SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 283             Args[i].first, DAG.getConstant(1, MVT::i32));
 284           SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 285             Args[i].first, DAG.getConstant(0, MVT::i32));
 286           args_to_use.push_back(Hi);
 287           if (GPR_remaining > 1) {
 288             args_to_use.push_back(Lo);
 289             GPR_remaining -= 2;
 290           } else {
 291             SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
 292             PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
 293             Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 294                                          Lo, PtrOff));
 295             --GPR_remaining;
 296           }
 297         } else {
 298           Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 299                                        Args[i].first, PtrOff));
 300         }
 301         ArgOffset += 8;
 302         break;
 303       case MVT::f32:
 304       case MVT::f64:
 305         if (FPR_remaining > 0) {
 306           if (isVarArg) {
 307             // FIXME: Need FunctionType information so we can conditionally
 308             // store only the non-fixed arguments in a vararg function.
 309             Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 310                                          Args[i].first, PtrOff));
 311             // FIXME: Need a way to communicate to the ISD::CALL select code
 312             // that a particular argument is non-fixed so that we can load them
 313             // into the correct GPR to shadow the FPR
 314           }
 315           args_to_use.push_back(Args[i].first);
 316           --FPR_remaining;
 317           // If we have any FPRs remaining, we may also have GPRs remaining.
 318           // Args passed in FPRs consume either 1 (f32) or 2 (f64) available
 319           // GPRs.
 320           if (GPR_remaining > 0) --GPR_remaining;
 321           if (GPR_remaining > 0 && MVT::f64 == ArgVT) --GPR_remaining;
 322         } else {
 323           Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 324                                        Args[i].first, PtrOff));
 325         }
 326         ArgOffset += (ArgVT == MVT::f32) ? 4 : 8;
 327         break;
 328       }
 329     }
 330     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, Stores);
 331   }
 332
 333   std::vector<MVT::ValueType> RetVals;
 334   MVT::ValueType RetTyVT = getValueType(RetTy);
 335   if (RetTyVT != MVT::isVoid)
 336     RetVals.push_back(RetTyVT);
 337   RetVals.push_back(MVT::Other);
 338
 339   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 340                                             Chain, Callee, args_to_use), 0);
 341   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 342   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 343                       DAG.getConstant(NumBytes, getPointerTy()));
 344   return std::make_pair(TheCall, Chain);
 345 }
 346
 347 std::pair<SDOperand, SDOperand>
 348 PPC32TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 349   //vastart just returns the address of the VarArgsFrameIndex slot.
 350   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 351 }
 352
 353 std::pair<SDOperand,SDOperand> PPC32TargetLowering::
 354 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 355                const Type *ArgTy, SelectionDAG &DAG) {
 356   MVT::ValueType ArgVT = getValueType(ArgTy);
 357   SDOperand Result;
 358   if (!isVANext) {
 359     Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList);
 360   } else {
 361     unsigned Amt;
 362     if (ArgVT == MVT::i32 || ArgVT == MVT::f32)
 363       Amt = 4;
 364     else {
 365       assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 366              "Other types should have been promoted for varargs!");
 367       Amt = 8;
 368     }
 369     Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
 370                          DAG.getConstant(Amt, VAList.getValueType()));
 371   }
 372   return std::make_pair(Result, Chain);
 373 }
 374
 375
 376 std::pair<SDOperand, SDOperand> PPC32TargetLowering::
 377 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 378                         SelectionDAG &DAG) {
 379   assert(0 && "LowerFrameReturnAddress unimplemented");
 380   abort();
 381 }
 382
 383 namespace {
 384
 385 //===--------------------------------------------------------------------===//
 386 /// ISel - PPC32 specific code to select PPC32 machine instructions for
 387 /// SelectionDAG operations.
 388 //===--------------------------------------------------------------------===//
 389 class ISel : public SelectionDAGISel {
 390
 391   /// Comment Here.
 392   PPC32TargetLowering PPC32Lowering;
 393
 394   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 395   /// vreg the value is produced in, so we only emit one copy of each compiled
 396   /// tree.
 397   std::map<SDOperand, unsigned> ExprMap;
 398
 399   unsigned GlobalBaseReg;
 400   bool GlobalBaseInitialized;
 401
 402 public:
 403   ISel(TargetMachine &TM) : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM)
 404   {}
 405
 406   /// runOnFunction - Override this function in order to reset our per-function
 407   /// variables.
 408   virtual bool runOnFunction(Function &Fn) {
 409     // Make sure we re-emit a set of the global base reg if necessary
 410     GlobalBaseInitialized = false;
 411     return SelectionDAGISel::runOnFunction(Fn);
 412   }
 413
 414   /// InstructionSelectBasicBlock - This callback is invoked by
 415   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 416   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 417     DEBUG(BB->dump());
 418     // Codegen the basic block.
 419     Select(DAG.getRoot());
 420
 421     // Clear state used for selection.
 422     ExprMap.clear();
 423   }
 424
 425   unsigned ISel::getGlobalBaseReg();
 426   unsigned SelectExpr(SDOperand N);
 427   unsigned SelectExprFP(SDOperand N, unsigned Result);
 428   void Select(SDOperand N);
 429
 430   void SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 431   void SelectBranchCC(SDOperand N);
 432 };
 433
 434 /// canUseAsImmediateForOpcode - This method returns a value indicating whether
 435 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 436 /// values are either 0, 1 or 2.  0 indicates that either N is not a
 437 /// ConstantSDNode, or is not suitable for use by that opcode.  A return value
 438 /// of 1 indicates that the constant may be used in normal immediate form.  A
 439 /// return value of 2 indicates that the constant may be used in shifted
 440 /// immediate form.  If the return value is nonzero, the constant value is
 441 /// placed in Imm.
 442 ///
 443 static unsigned canUseAsImmediateForOpcode(SDOperand N, unsigned Opcode,
 444                                            unsigned& Imm) {
 445   if (N.getOpcode() != ISD::Constant) return 0;
 446
 447   int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 448
 449   switch(Opcode) {
 450   default: return 0;
 451   case ISD::ADD:
 452     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 453     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 454     break;
 455   case ISD::AND:
 456   case ISD::XOR:
 457   case ISD::OR:
 458     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 459     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 460     break;
 461   case ISD::MUL:
 462     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 463     break;
 464   }
 465   return 0;
 466 }
 467 }
 468
 469 /// getGlobalBaseReg - Output the instructions required to put the
 470 /// base address to use for accessing globals into a register.
 471 ///
 472 unsigned ISel::getGlobalBaseReg() {
 473   if (!GlobalBaseInitialized) {
 474     // Insert the set of GlobalBaseReg into the first MBB of the function
 475     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 476     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 477     GlobalBaseReg = MakeReg(MVT::i32);
 478     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 479     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg).addReg(PPC::LR);
 480     GlobalBaseInitialized = true;
 481   }
 482   return GlobalBaseReg;
 483 }
 484
 485 //Check to see if the load is a constant offset from a base register
 486 void ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 487 {
 488   Reg = SelectExpr(N);
 489   offset = 0;
 490   return;
 491 }
 492
 493 void ISel::SelectBranchCC(SDOperand N)
 494 {
 495   assert(N.getOpcode() == ISD::BRCOND && "Not a BranchCC???");
 496   MachineBasicBlock *Dest =
 497     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
 498   unsigned Opc;
 499
 500   Select(N.getOperand(0));  //chain
 501   SDOperand CC = N.getOperand(1);
 502
 503   //Give up and do the stupid thing
 504   unsigned Tmp1 = SelectExpr(CC);
 505   BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(0);
 506   BuildMI(BB, PPC::BNE, 2).addReg(PPC::CR0).addMBB(Dest);
 507   return;
 508 }
 509
 510 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
 511 {
 512   unsigned Tmp1, Tmp2, Tmp3;
 513   unsigned Opc = 0;
 514   SDNode *Node = N.Val;
 515   MVT::ValueType DestType = N.getValueType();
 516   unsigned opcode = N.getOpcode();
 517
 518   switch (opcode) {
 519   default:
 520     Node->dump();
 521     assert(0 && "Node not handled!\n");
 522
 523   case ISD::SELECT: {
 524     Tmp1 = SelectExpr(N.getOperand(0)); //Cond
 525
 526     // FIXME: generate FSEL here
 527
 528     // Create an iterator with which to insert the MBB for copying the false
 529     // value and the MBB to hold the PHI instruction for this SetCC.
 530     MachineBasicBlock *thisMBB = BB;
 531     const BasicBlock *LLVM_BB = BB->getBasicBlock();
 532     ilist<MachineBasicBlock>::iterator It = BB;
 533     ++It;
 534
 535     //  thisMBB:
 536     //  ...
 537     //   TrueVal = ...
 538     //   cmpTY cr0, r1, r2
 539     //   bCC copy1MBB
 540     //   fallthrough --> copy0MBB
 541     BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(0);
 542     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
 543     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
 544     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
 545     BuildMI(BB, PPC::BNE, 2).addReg(PPC::CR0).addMBB(sinkMBB);
 546     MachineFunction *F = BB->getParent();
 547     F->getBasicBlockList().insert(It, copy0MBB);
 548     F->getBasicBlockList().insert(It, sinkMBB);
 549     // Update machine-CFG edges
 550     BB->addSuccessor(copy0MBB);
 551     BB->addSuccessor(sinkMBB);
 552
 553     //  copy0MBB:
 554     //   %FalseValue = ...
 555     //   # fallthrough to sinkMBB
 556     BB = copy0MBB;
 557     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
 558     // Update machine-CFG edges
 559     BB->addSuccessor(sinkMBB);
 560
 561     //  sinkMBB:
 562     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
 563     //  ...
 564     BB = sinkMBB;
 565     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
 566       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
 567     return Result;
 568   }
 569
 570   case ISD::FP_ROUND:
 571     assert (DestType == MVT::f32 &&
 572             N.getOperand(0).getValueType() == MVT::f64 &&
 573             "only f64 to f32 conversion supported here");
 574     Tmp1 = SelectExpr(N.getOperand(0));
 575     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
 576     return Result;
 577
 578   case ISD::FP_EXTEND:
 579     assert (DestType == MVT::f64 &&
 580             N.getOperand(0).getValueType() == MVT::f32 &&
 581             "only f32 to f64 conversion supported here");
 582     Tmp1 = SelectExpr(N.getOperand(0));
 583     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
 584     return Result;
 585
 586   case ISD::CopyFromReg:
 587     if (Result == 1)
 588       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 589     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
 590     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
 591     return Result;
 592
 593   case ISD::LOAD:
 594   case ISD::EXTLOAD: {
 595     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
 596       Node->getValueType(0) : cast<MVTSDNode>(Node)->getExtraValueType();
 597
 598     // Make sure we generate both values.
 599     if (Result != 1)
 600       ExprMap[N.getValue(1)] = 1;   // Generate the token
 601     else
 602       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 603
 604     SDOperand Chain   = N.getOperand(0);
 605     SDOperand Address = N.getOperand(1);
 606     Select(Chain);
 607
 608     switch (TypeBeingLoaded) {
 609     default: assert(0 && "Cannot fp load this type!");
 610     case MVT::f32:  Opc = PPC::LFS; break;
 611     case MVT::f64:  Opc = PPC::LFD; break;
 612     }
 613
 614     if(Address.getOpcode() == ISD::FrameIndex) {
 615       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
 616       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
 617     } else {
 618       int offset;
 619       SelectAddr(Address, Tmp1, offset);
 620       BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 621     }
 622     return Result;
 623   }
 624
 625   case ISD::ConstantFP:
 626     assert(0 && "ISD::ConstantFP Unimplemented");
 627     abort();
 628
 629   case ISD::MUL:
 630   case ISD::ADD:
 631   case ISD::SUB:
 632   case ISD::SDIV:
 633     switch( opcode ) {
 634     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
 635     case ISD::ADD:  Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS; break;
 636     case ISD::SUB:  Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS; break;
 637     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
 638     };
 639     Tmp1 = SelectExpr(N.getOperand(0));
 640     Tmp2 = SelectExpr(N.getOperand(1));
 641     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 642     return Result;
 643
 644   case ISD::UINT_TO_FP:
 645   case ISD::SINT_TO_FP:
 646     assert(0 && "ISD::U/SINT_TO_FP Unimplemented");
 647     abort();
 648   }
 649   assert(0 && "should not get here");
 650   return 0;
 651 }
 652
 653 unsigned ISel::SelectExpr(SDOperand N) {
 654   unsigned Result;
 655   unsigned Tmp1, Tmp2, Tmp3;
 656   unsigned Opc = 0;
 657   unsigned opcode = N.getOpcode();
 658
 659   SDNode *Node = N.Val;
 660   MVT::ValueType DestType = N.getValueType();
 661
 662   unsigned &Reg = ExprMap[N];
 663   if (Reg) return Reg;
 664
 665   if (N.getOpcode() != ISD::CALL && N.getOpcode() != ISD::ADD_PARTS &&
 666       N.getOpcode() != ISD::SUB_PARTS)
 667     Reg = Result = (N.getValueType() != MVT::Other) ?
 668       MakeReg(N.getValueType()) : 1;
 669   else {
 670     // If this is a call instruction, make sure to prepare ALL of the result
 671     // values as well as the chain.
 672     if (N.getOpcode() == ISD::CALL) {
 673       if (Node->getNumValues() == 1)
 674         Reg = Result = 1;  // Void call, just a chain.
 675       else {
 676         Result = MakeReg(Node->getValueType(0));
 677         ExprMap[N.getValue(0)] = Result;
 678         for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 679           ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 680         ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 681       }
 682     } else {
 683       Result = MakeReg(Node->getValueType(0));
 684       ExprMap[N.getValue(0)] = Result;
 685       for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
 686         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 687     }
 688   }
 689
 690   if (DestType == MVT::f64 || DestType == MVT::f32)
 691     return SelectExprFP(N, Result);
 692
 693   switch (opcode) {
 694   default:
 695     Node->dump();
 696     assert(0 && "Node not handled!\n");
 697
 698   case ISD::DYNAMIC_STACKALLOC:
 699     // Generate both result values.  FIXME: Need a better commment here?
 700     if (Result != 1)
 701       ExprMap[N.getValue(1)] = 1;
 702     else
 703       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 704
 705     // FIXME: We are currently ignoring the requested alignment for handling
 706     // greater than the stack alignment.  This will need to be revisited at some
 707     // point.  Align = N.getOperand(2);
 708     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 709         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 710       std::cerr << "Cannot allocate stack object with greater alignment than"
 711                 << " the stack alignment yet!";
 712       abort();
 713     }
 714     Select(N.getOperand(0));
 715     Tmp1 = SelectExpr(N.getOperand(1));
 716     // Subtract size from stack pointer, thereby allocating some space.
 717     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 718     // Put a pointer to the space into the result register by copying the SP
 719     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 720     return Result;
 721
 722   case ISD::ConstantPool:
 723     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 724     Tmp2 = MakeReg(MVT::i32);
 725     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp2).addReg(getGlobalBaseReg())
 726       .addConstantPoolIndex(Tmp1);
 727     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
 728     return Result;
 729
 730   case ISD::FrameIndex:
 731     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 732     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
 733     return Result;
 734
 735   case ISD::GlobalAddress: {
 736     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 737     Tmp1 = MakeReg(MVT::i32);
 738     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
 739       .addGlobalAddress(GV);
 740     if (GV->hasWeakLinkage() || GV->isExternal()) {
 741       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 742     } else {
 743       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
 744     }
 745     return Result;
 746   }
 747
 748   case ISD::LOAD:
 749   case ISD::EXTLOAD:
 750   case ISD::ZEXTLOAD:
 751   case ISD::SEXTLOAD: {
 752     bool sext = (ISD::SEXTLOAD == opcode);
 753     bool byte = (MVT::i8 == Node->getValueType(0));
 754     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
 755       Node->getValueType(0) : cast<MVTSDNode>(Node)->getExtraValueType();
 756
 757     // Make sure we generate both values.
 758     if (Result != 1)
 759       ExprMap[N.getValue(1)] = 1;   // Generate the token
 760     else
 761       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 762
 763     SDOperand Chain   = N.getOperand(0);
 764     SDOperand Address = N.getOperand(1);
 765     Select(Chain);
 766
 767     switch (TypeBeingLoaded) {
 768     default: assert(0 && "Cannot load this type!");
 769     case MVT::i1:  Opc = PPC::LBZ; break;
 770     case MVT::i8:  Opc = PPC::LBZ; break;
 771     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
 772     case MVT::i32: Opc = PPC::LWZ; break;
 773     }
 774
 775     // Since there's no load byte & sign extend instruction we have to split
 776     // byte SEXTLOADs into lbz + extsb.  This requires we make a temp register.
 777     if (sext && byte) {
 778       Tmp3 = Result;
 779       Result = MakeReg(MVT::i32);
 780     } else {
 781       Tmp3 = 0;  // Silence GCC warning.
 782     }
 783     if(Address.getOpcode() == ISD::FrameIndex) {
 784       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
 785       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
 786     } else {
 787       int offset;
 788       SelectAddr(Address, Tmp1, offset);
 789       BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 790     }
 791     if (sext && byte) {
 792       BuildMI(BB, PPC::EXTSB, 1, Tmp3).addReg(Result);
 793       Result = Tmp3;
 794     }
 795     return Result;
 796   }
 797
 798   case ISD::CALL: {
 799     // Lower the chain for this call.
 800     Select(N.getOperand(0));
 801     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
 802
 803     // get the virtual reg for each argument
 804     std::vector<unsigned> VRegs;
 805     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
 806       VRegs.push_back(SelectExpr(N.getOperand(i)));
 807
 808     // The ABI specifies that the first 32 bytes of args may be passed in GPRs,
 809     // and that 13 FPRs may also be used for passing any floating point args.
 810     int GPR_remaining = 8, FPR_remaining = 13;
 811     unsigned GPR_idx = 0, FPR_idx = 0;
 812     static const unsigned GPR[] = {
 813       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 814       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 815     };
 816     static const unsigned FPR[] = {
 817       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6,
 818       PPC::F7, PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12,
 819       PPC::F13
 820     };
 821
 822     // move the vregs into the appropriate architected register or stack slot
 823     for(int i = 0, e = VRegs.size(); i < e; ++i) {
 824         unsigned OperandType = N.getOperand(i+2).getValueType();
 825         switch(OperandType) {
 826         default:
 827           Node->dump();
 828           N.getOperand(i).Val->dump();
 829           std::cerr << "Type for " << i << " is: " <<
 830             N.getOperand(i+2).getValueType() << "\n";
 831           assert(0 && "Unknown value type for call");
 832         case MVT::i1:
 833         case MVT::i8:
 834         case MVT::i16:
 835         case MVT::i32:
 836           if (GPR_remaining > 0)
 837             BuildMI(BB, PPC::OR, 2, GPR[GPR_idx]).addReg(VRegs[i])
 838               .addReg(VRegs[i]);
 839           break;
 840         case MVT::f32:
 841         case MVT::f64:
 842           if (FPR_remaining > 0) {
 843             BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(VRegs[i]);
 844             ++FPR_idx;
 845             --FPR_remaining;
 846           }
 847           break;
 848         }
 849         // All arguments consume GPRs available for argument passing
 850         if (GPR_remaining > 0) {
 851           ++GPR_idx;
 852           --GPR_remaining;
 853         }
 854         if (MVT::f64 == OperandType && GPR_remaining > 0) {
 855           ++GPR_idx;
 856           --GPR_remaining;
 857         }
 858     }
 859
 860     // Emit the correct call instruction based on the type of symbol called.
 861     if (GlobalAddressSDNode *GASD =
 862         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
 863       BuildMI(BB, PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(), true);
 864     } else if (ExternalSymbolSDNode *ESSDN =
 865                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
 866       BuildMI(BB, PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(), true);
 867     } else {
 868       Tmp1 = SelectExpr(N.getOperand(1));
 869       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
 870       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
 871       BuildMI(BB, PPC::CALLindirect, 3).addImm(20).addImm(0).addReg(PPC::R12);
 872     }
 873
 874     switch (Node->getValueType(0)) {
 875     default: assert(0 && "Unknown value type for call result!");
 876     case MVT::Other: return 1;
 877     case MVT::i1:
 878     case MVT::i8:
 879     case MVT::i16:
 880     case MVT::i32:
 881       BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
 882       if (Node->getValueType(1) == MVT::i32)
 883         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R4).addReg(PPC::R4);
 884       break;
 885     case MVT::f32:
 886     case MVT::f64:
 887       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
 888       break;
 889     }
 890     return Result+N.ResNo;
 891   }
 892
 893   case ISD::SIGN_EXTEND:
 894   case ISD::SIGN_EXTEND_INREG:
 895     Tmp1 = SelectExpr(N.getOperand(0));
 896     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 897     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
 898     case MVT::i16:
 899       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
 900       break;
 901     case MVT::i8:
 902       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
 903       break;
 904     case MVT::i1:
 905       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp1).addSImm(0);
 906       break;
 907     }
 908     return Result;
 909
 910   case ISD::ZERO_EXTEND_INREG:
 911     Tmp1 = SelectExpr(N.getOperand(0));
 912     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 913     default: Node->dump(); assert(0 && "Unhandled ZERO_EXTEND type"); break;
 914     case MVT::i16:  Tmp2 = 16; break;
 915     case MVT::i8:   Tmp2 = 24; break;
 916     case MVT::i1:   Tmp2 = 31; break;
 917     }
 918     BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(0).addImm(Tmp2)
 919       .addImm(31);
 920     return Result;
 921
 922   case ISD::CopyFromReg:
 923     if (Result == 1)
 924       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 925     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
 926     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
 927     return Result;
 928
 929   case ISD::SHL:
 930     Tmp1 = SelectExpr(N.getOperand(0));
 931     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 932       Tmp2 = CN->getValue() & 0x1F;
 933       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
 934         .addImm(31-Tmp2);
 935     } else {
 936       Tmp2 = SelectExpr(N.getOperand(1));
 937       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 938     }
 939     return Result;
 940
 941   case ISD::SRL:
 942     Tmp1 = SelectExpr(N.getOperand(0));
 943     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 944       Tmp2 = CN->getValue() & 0x1F;
 945       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(32-Tmp2)
 946         .addImm(Tmp2).addImm(31);
 947     } else {
 948       Tmp2 = SelectExpr(N.getOperand(1));
 949       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 950     }
 951     return Result;
 952
 953   case ISD::SRA:
 954     Tmp1 = SelectExpr(N.getOperand(0));
 955     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 956       Tmp2 = CN->getValue() & 0x1F;
 957       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
 958     } else {
 959       Tmp2 = SelectExpr(N.getOperand(1));
 960       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 961     }
 962     return Result;
 963
 964   case ISD::ADD:
 965     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 966     Tmp1 = SelectExpr(N.getOperand(0));
 967     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 968       default: assert(0 && "unhandled result code");
 969       case 0: // No immediate
 970         Tmp2 = SelectExpr(N.getOperand(1));
 971         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
 972         break;
 973       case 1: // Low immediate
 974         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 975         break;
 976       case 2: // Shifted immediate
 977         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 978         break;
 979     }
 980     return Result;
 981
 982   case ISD::AND:
 983   case ISD::OR:
 984   case ISD::XOR:
 985     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 986     Tmp1 = SelectExpr(N.getOperand(0));
 987     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 988       default: assert(0 && "unhandled result code");
 989       case 0: // No immediate
 990         Tmp2 = SelectExpr(N.getOperand(1));
 991         switch (opcode) {
 992         case ISD::AND: Opc = PPC::AND; break;
 993         case ISD::OR:  Opc = PPC::OR;  break;
 994         case ISD::XOR: Opc = PPC::XOR; break;
 995         }
 996         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 997         break;
 998       case 1: // Low immediate
 999         switch (opcode) {
1000         case ISD::AND: Opc = PPC::ANDIo; break;
1001         case ISD::OR:  Opc = PPC::ORI;   break;
1002         case ISD::XOR: Opc = PPC::XORI;  break;
1003         }
1004         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1005         break;
1006       case 2: // Shifted immediate
1007         switch (opcode) {
1008         case ISD::AND: Opc = PPC::ANDISo;  break;
1009         case ISD::OR:  Opc = PPC::ORIS;    break;
1010         case ISD::XOR: Opc = PPC::XORIS;   break;
1011         }
1012         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1013         break;
1014     }
1015     return Result;
1016
1017   case ISD::SUB:
1018     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
1019     Tmp1 = SelectExpr(N.getOperand(0));
1020     Tmp2 = SelectExpr(N.getOperand(1));
1021     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1022     return Result;
1023
1024   case ISD::MUL:
1025     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
1026     Tmp1 = SelectExpr(N.getOperand(0));
1027     if (1 == canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2))
1028       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1029     else {
1030       Tmp2 = SelectExpr(N.getOperand(1));
1031       BuildMI(BB, PPC::MULLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1032     }
1033     return Result;
1034
1035   case ISD::SDIV:
1036   case ISD::UDIV:
1037     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
1038     Tmp1 = SelectExpr(N.getOperand(0));
1039     Tmp2 = SelectExpr(N.getOperand(1));
1040     Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW;
1041     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1042     return Result;
1043
1044   case ISD::UREM:
1045   case ISD::SREM: {
1046     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
1047     Tmp1 = SelectExpr(N.getOperand(0));
1048     Tmp2 = SelectExpr(N.getOperand(1));
1049     Tmp3 = MakeReg(MVT::i32);
1050     unsigned Tmp4 = MakeReg(MVT::i32);
1051     Opc = (ISD::UREM == opcode) ? PPC::DIVWU : PPC::DIVW;
1052     BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1053     BuildMI(BB, PPC::MULLW, 2, Tmp4).addReg(Tmp3).addReg(Tmp2);
1054     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp4).addReg(Tmp1);
1055     return Result;
1056   }
1057
1058   case ISD::ADD_PARTS:
1059   case ISD::SUB_PARTS: {
1060     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
1061            "Not an i64 add/sub!");
1062     // Emit all of the operands.
1063     std::vector<unsigned> InVals;
1064     for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)
1065       InVals.push_back(SelectExpr(N.getOperand(i)));
1066     if (N.getOpcode() == ISD::ADD_PARTS) {
1067       BuildMI(BB, PPC::ADDC, 2, Result+1).addReg(InVals[0]).addReg(InVals[2]);
1068       BuildMI(BB, PPC::ADDE, 2, Result).addReg(InVals[1]).addReg(InVals[3]);
1069     } else {
1070       BuildMI(BB, PPC::SUBFC, 2, Result+1).addReg(InVals[2]).addReg(InVals[0]);
1071       BuildMI(BB, PPC::SUBFE, 2, Result).addReg(InVals[3]).addReg(InVals[1]);
1072     }
1073     return Result+N.ResNo;
1074   }
1075
1076   case ISD::FP_TO_UINT:
1077   case ISD::FP_TO_SINT:
1078     assert(0 && "FP_TO_S/UINT unimplemented");
1079     abort();
1080
1081   case ISD::SETCC:
1082     if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Node)) {
1083       bool U = false;
1084       bool IsInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
1085
1086       switch (SetCC->getCondition()) {
1087       default: Node->dump(); assert(0 && "Unknown comparison!");
1088       case ISD::SETEQ:  Opc = PPC::BEQ; break;
1089       case ISD::SETNE:  Opc = PPC::BNE; break;
1090       case ISD::SETULT: U = true;
1091       case ISD::SETLT:  Opc = PPC::BLT; break;
1092       case ISD::SETULE: U = true;
1093       case ISD::SETLE:  Opc = PPC::BLE; break;
1094       case ISD::SETUGT: U = true;
1095       case ISD::SETGT:  Opc = PPC::BGT; break;
1096       case ISD::SETUGE: U = true;
1097       case ISD::SETGE:  Opc = PPC::BGE; break;
1098       }
1099
1100       // FIXME: Is there a situation in which we would ever need to emit fcmpo?
1101       static const unsigned CompareOpcodes[] =
1102         { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
1103       unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
1104
1105       // Create an iterator with which to insert the MBB for copying the false
1106       // value and the MBB to hold the PHI instruction for this SetCC.
1107       MachineBasicBlock *thisMBB = BB;
1108       const BasicBlock *LLVM_BB = BB->getBasicBlock();
1109       ilist<MachineBasicBlock>::iterator It = BB;
1110       ++It;
1111
1112       //  thisMBB:
1113       //  ...
1114       //   cmpTY cr0, r1, r2
1115       //   %TrueValue = li 1
1116       //   bCC sinkMBB
1117       Tmp1 = SelectExpr(N.getOperand(0));
1118       Tmp2 = SelectExpr(N.getOperand(1));
1119       BuildMI(BB, CompareOpc, 2, PPC::CR0).addReg(Tmp1).addReg(Tmp2);
1120       unsigned TrueValue = MakeReg(MVT::i32);
1121       BuildMI(BB, PPC::LI, 1, TrueValue).addSImm(1);
1122       MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1123       MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1124       BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
1125       MachineFunction *F = BB->getParent();
1126       F->getBasicBlockList().insert(It, copy0MBB);
1127       F->getBasicBlockList().insert(It, sinkMBB);
1128       // Update machine-CFG edges
1129       BB->addSuccessor(copy0MBB);
1130       BB->addSuccessor(sinkMBB);
1131
1132       //  copy0MBB:
1133       //   %FalseValue = li 0
1134       //   fallthrough
1135       BB = copy0MBB;
1136       unsigned FalseValue = MakeReg(MVT::i32);
1137       BuildMI(BB, PPC::LI, 1, FalseValue).addSImm(0);
1138       // Update machine-CFG edges
1139       BB->addSuccessor(sinkMBB);
1140
1141       //  sinkMBB:
1142       //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1143       //  ...
1144       BB = sinkMBB;
1145       BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1146         .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1147       return Result;
1148     }
1149     assert(0 && "Is this legal?");
1150     return 0;
1151
1152   case ISD::SELECT: {
1153     Tmp1 = SelectExpr(N.getOperand(0)); //Cond
1154
1155     // Create an iterator with which to insert the MBB for copying the false
1156     // value and the MBB to hold the PHI instruction for this SetCC.
1157     MachineBasicBlock *thisMBB = BB;
1158     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1159     ilist<MachineBasicBlock>::iterator It = BB;
1160     ++It;
1161
1162     //  thisMBB:
1163     //  ...
1164     //   TrueVal = ...
1165     //   cmpTY cr0, r1, r2
1166     //   bCC copy1MBB
1167     //   fallthrough --> copy0MBB
1168     BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(0);
1169     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1170     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1171     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
1172     BuildMI(BB, PPC::BNE, 2).addReg(PPC::CR0).addMBB(sinkMBB);
1173     MachineFunction *F = BB->getParent();
1174     F->getBasicBlockList().insert(It, copy0MBB);
1175     F->getBasicBlockList().insert(It, sinkMBB);
1176     // Update machine-CFG edges
1177     BB->addSuccessor(copy0MBB);
1178     BB->addSuccessor(sinkMBB);
1179
1180     //  copy0MBB:
1181     //   %FalseValue = ...
1182     //   # fallthrough to sinkMBB
1183     BB = copy0MBB;
1184     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
1185     // Update machine-CFG edges
1186     BB->addSuccessor(sinkMBB);
1187
1188     //  sinkMBB:
1189     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1190     //  ...
1191     BB = sinkMBB;
1192     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1193       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1194
1195     // FIXME: Select i64?
1196     return Result;
1197   }
1198
1199   case ISD::Constant:
1200     switch (N.getValueType()) {
1201     default: assert(0 && "Cannot use constants of this type!");
1202     case MVT::i1:
1203       BuildMI(BB, PPC::LI, 1, Result)
1204         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
1205       break;
1206     case MVT::i32:
1207       {
1208         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
1209         if (v < 32768 && v >= -32768) {
1210           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
1211         } else {
1212           Tmp1 = MakeReg(MVT::i32);
1213           BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
1214           BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(v & 0xFFFF);
1215         }
1216       }
1217     }
1218     return Result;
1219   }
1220
1221   return 0;
1222 }
1223
1224 void ISel::Select(SDOperand N) {
1225   unsigned Tmp1, Tmp2, Opc;
1226   unsigned opcode = N.getOpcode();
1227
1228   if (!ExprMap.insert(std::make_pair(N, 1)).second)
1229     return;  // Already selected.
1230
1231   SDNode *Node = N.Val;
1232
1233   switch (Node->getOpcode()) {
1234   default:
1235     Node->dump(); std::cerr << "\n";
1236     assert(0 && "Node not handled yet!");
1237   case ISD::EntryToken: return;  // Noop
1238   case ISD::TokenFactor:
1239     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1240       Select(Node->getOperand(i));
1241     return;
1242   case ISD::ADJCALLSTACKDOWN:
1243   case ISD::ADJCALLSTACKUP:
1244     Select(N.getOperand(0));
1245     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1246     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? PPC::ADJCALLSTACKDOWN :
1247       PPC::ADJCALLSTACKUP;
1248     BuildMI(BB, Opc, 1).addImm(Tmp1);
1249     return;
1250   case ISD::BR: {
1251     MachineBasicBlock *Dest =
1252       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1253     Select(N.getOperand(0));
1254     BuildMI(BB, PPC::B, 1).addMBB(Dest);
1255     return;
1256   }
1257   case ISD::BRCOND:
1258     SelectBranchCC(N);
1259     return;
1260   case ISD::CopyToReg:
1261     Select(N.getOperand(0));
1262     Tmp1 = SelectExpr(N.getOperand(1));
1263     Tmp2 = cast<RegSDNode>(N)->getReg();
1264
1265     if (Tmp1 != Tmp2) {
1266       if (N.getOperand(1).getValueType() == MVT::f64 ||
1267           N.getOperand(1).getValueType() == MVT::f32)
1268         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
1269       else
1270         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1271     }
1272     return;
1273   case ISD::ImplicitDef:
1274     Select(N.getOperand(0));
1275     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
1276     return;
1277   case ISD::RET:
1278     switch (N.getNumOperands()) {
1279     default:
1280       assert(0 && "Unknown return instruction!");
1281     case 3:
1282       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1283              N.getOperand(2).getValueType() == MVT::i32 &&
1284                    "Unknown two-register value!");
1285       Select(N.getOperand(0));
1286       Tmp1 = SelectExpr(N.getOperand(1));
1287       Tmp2 = SelectExpr(N.getOperand(2));
1288       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
1289       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp2).addReg(Tmp2);
1290       break;
1291     case 2:
1292       Select(N.getOperand(0));
1293       Tmp1 = SelectExpr(N.getOperand(1));
1294       switch (N.getOperand(1).getValueType()) {
1295         default:
1296           assert(0 && "Unknown return type!");
1297         case MVT::f64:
1298         case MVT::f32:
1299           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
1300           break;
1301         case MVT::i32:
1302           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
1303           break;
1304       }
1305     case 1:
1306       Select(N.getOperand(0));
1307       break;
1308     }
1309     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
1310     return;
1311   case ISD::TRUNCSTORE:
1312   case ISD::STORE:
1313     {
1314       SDOperand Chain   = N.getOperand(0);
1315       SDOperand Value   = N.getOperand(1);
1316       SDOperand Address = N.getOperand(2);
1317       Select(Chain);
1318
1319       Tmp1 = SelectExpr(Value); //value
1320
1321       if (opcode == ISD::STORE) {
1322         switch(Value.getValueType()) {
1323         default: assert(0 && "unknown Type in store");
1324         case MVT::i32: Opc = PPC::STW; break;
1325         case MVT::f64: Opc = PPC::STFD; break;
1326         case MVT::f32: Opc = PPC::STFS; break;
1327         }
1328       } else { //ISD::TRUNCSTORE
1329         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
1330         default: assert(0 && "unknown Type in store");
1331         case MVT::i1: //FIXME: DAG does not promote this load
1332         case MVT::i8: Opc  = PPC::STB; break;
1333         case MVT::i16: Opc = PPC::STH; break;
1334         }
1335       }
1336
1337       if (Address.getOpcode() == ISD::GlobalAddress)
1338       {
1339         BuildMI(BB, Opc, 2).addReg(Tmp1)
1340           .addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
1341       }
1342       else if(Address.getOpcode() == ISD::FrameIndex)
1343       {
1344         Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
1345         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
1346       }
1347       else
1348       {
1349         int offset;
1350         SelectAddr(Address, Tmp2, offset);
1351         BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
1352       }
1353       return;
1354     }
1355   case ISD::EXTLOAD:
1356   case ISD::SEXTLOAD:
1357   case ISD::ZEXTLOAD:
1358   case ISD::LOAD:
1359   case ISD::CopyFromReg:
1360   case ISD::CALL:
1361   case ISD::DYNAMIC_STACKALLOC:
1362     ExprMap.erase(N);
1363     SelectExpr(N);
1364     return;
1365   }
1366   assert(0 && "Should not be reached!");
1367 }
1368
1369
1370 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
1371 /// into a machine code representation using pattern matching and a machine
1372 /// description file.
1373 ///
1374 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
1375   return new ISel(TM);
1376 }
1377