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::GPRCRegisterClass);
  48       addRegisterClass(MVT::f64, PPC32::FPRCRegisterClass);
  49
  50       computeRegisterProperties();
  51     }
  52
  53     /// LowerArguments - This hook must be implemented to indicate how we should
  54     /// lower the arguments for the specified function, into the specified DAG.
  55     virtual std::vector<SDOperand>
  56     LowerArguments(Function &F, SelectionDAG &DAG);
  57
  58     /// LowerCallTo - This hook lowers an abstract call to a function into an
  59     /// actual call.
  60     virtual std::pair<SDOperand, SDOperand>
  61     LowerCallTo(SDOperand Chain, const Type *RetTy, SDOperand Callee,
  62                 ArgListTy &Args, SelectionDAG &DAG);
  63
  64     virtual std::pair<SDOperand, SDOperand>
  65     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
  66
  67     virtual std::pair<SDOperand,SDOperand>
  68     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
  69                    const Type *ArgTy, SelectionDAG &DAG);
  70
  71     virtual std::pair<SDOperand, SDOperand>
  72     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
  73                             SelectionDAG &DAG);
  74   };
  75 }
  76
  77
  78 std::vector<SDOperand>
  79 PPC32TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
  80   //
  81   // add beautiful description of PPC stack frame format, or at least some docs
  82   //
  83   MachineFunction &MF = DAG.getMachineFunction();
  84   MachineFrameInfo *MFI = MF.getFrameInfo();
  85   MachineBasicBlock& BB = MF.front();
  86   std::vector<SDOperand> ArgValues;
  87
  88   // Due to the rather complicated nature of the PowerPC ABI, rather than a
  89   // fixed size array of physical args, for the sake of simplicity let the STL
  90   // handle tracking them for us.
  91   std::vector<unsigned> argVR, argPR, argOp;
  92   unsigned ArgOffset = 24;
  93   unsigned GPR_remaining = 8;
  94   unsigned FPR_remaining = 13;
  95   unsigned GPR_idx = 0, FPR_idx = 0;
  96   static const unsigned GPR[] = {
  97     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
  98     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
  99   };
 100   static const unsigned FPR[] = {
 101     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 102     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 103   };
 104
 105   // Add DAG nodes to load the arguments...  On entry to a function on PPC,
 106   // the arguments start at offset 24, although they are likely to be passed
 107   // in registers.
 108   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 109     SDOperand newroot, argt;
 110     unsigned ObjSize;
 111     bool needsLoad = false;
 112     MVT::ValueType ObjectVT = getValueType(I->getType());
 113
 114     switch (ObjectVT) {
 115     default: assert(0 && "Unhandled argument type!");
 116     case MVT::i1:
 117     case MVT::i8:
 118     case MVT::i16:
 119     case MVT::i32:
 120       ObjSize = 4;
 121       if (GPR_remaining > 0) {
 122         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 123         unsigned virtReg =
 124           MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i32));
 125         argt = newroot = DAG.getCopyFromReg(virtReg, MVT::i32, DAG.getRoot());
 126         if (ObjectVT != MVT::i32)
 127           argt = DAG.getNode(ISD::TRUNCATE, ObjectVT, newroot);
 128         argVR.push_back(virtReg);
 129         argPR.push_back(GPR[GPR_idx]);
 130         argOp.push_back(PPC::OR);
 131       } else {
 132         needsLoad = true;
 133       }
 134       break;
 135       case MVT::i64: ObjSize = 8;
 136       if (GPR_remaining > 1) {
 137         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 138         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx+1]);
 139         MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i32));
 140         unsigned virtReg =
 141           MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i32))-1;
 142         // FIXME: is this correct?
 143         argt = newroot = DAG.getCopyFromReg(virtReg, MVT::i32, DAG.getRoot());
 144         argt = DAG.getCopyFromReg(virtReg+1, MVT::i32, newroot);
 145         // Push the arguments for emitting into BB later
 146         argVR.push_back(virtReg);       argVR.push_back(virtReg+1);
 147         argPR.push_back(GPR[GPR_idx]);  argPR.push_back(GPR[GPR_idx+1]);
 148         argOp.push_back(PPC::OR);       argOp.push_back(PPC::OR);
 149       } else {
 150         needsLoad = true;
 151       }
 152       break;
 153       case MVT::f32: ObjSize = 4;
 154       case MVT::f64: ObjSize = 8;
 155       if (FPR_remaining > 0) {
 156         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, FPR[FPR_idx]);
 157         unsigned virtReg =
 158           MF.getSSARegMap()->createVirtualRegister(getRegClassFor(ObjectVT));
 159         argt = newroot = DAG.getCopyFromReg(virtReg, ObjectVT, DAG.getRoot());
 160         argVR.push_back(virtReg);
 161         argPR.push_back(FPR[FPR_idx]);
 162         argOp.push_back(PPC::FMR);
 163         --FPR_remaining;
 164         ++FPR_idx;
 165       } else {
 166         needsLoad = true;
 167       }
 168       break;
 169     }
 170
 171     // We need to load the argument to a virtual register if we determined above
 172     // that we ran out of physical registers of the appropriate type
 173     if (needsLoad) {
 174       int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 175       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 176       argt = newroot = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
 177     }
 178
 179     // Every 4 bytes of argument space consumes one of the GPRs available for
 180     // argument passing.
 181     if (GPR_remaining > 0) {
 182       unsigned delta = (GPR_remaining > 1 && ObjSize == 8) ? 2 : 1;
 183       GPR_remaining -= delta;
 184       GPR_idx += delta;
 185     }
 186     ArgOffset += ObjSize;
 187
 188     DAG.setRoot(newroot.getValue(1));
 189     ArgValues.push_back(argt);
 190   }
 191
 192   for (int i = 0, count = argVR.size(); i < count; ++i) {
 193     if (argOp[i] == PPC::FMR)
 194       BuildMI(&BB, argOp[i], 1, argVR[i]).addReg(argPR[i]);
 195     else
 196       BuildMI(&BB, argOp[i], 2, argVR[i]).addReg(argPR[i]).addReg(argPR[i]);
 197   }
 198
 199   // If the function takes variable number of arguments, make a frame index for
 200   // the start of the first vararg value... for expansion of llvm.va_start.
 201   if (F.isVarArg())
 202     VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
 203
 204   return ArgValues;
 205 }
 206
 207 std::pair<SDOperand, SDOperand>
 208 PPC32TargetLowering::LowerCallTo(SDOperand Chain,
 209                                  const Type *RetTy, SDOperand Callee,
 210                                  ArgListTy &Args, SelectionDAG &DAG) {
 211   // FIXME
 212   int NumBytes = 56;
 213
 214   Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 215                       DAG.getConstant(NumBytes, getPointerTy()));
 216   std::vector<SDOperand> args_to_use;
 217   for (unsigned i = 0, e = Args.size(); i != e; ++i)
 218   {
 219     switch (getValueType(Args[i].second)) {
 220     default: assert(0 && "Unexpected ValueType for argument!");
 221     case MVT::i1:
 222     case MVT::i8:
 223     case MVT::i16:
 224       // Promote the integer to 32 bits.  If the input type is signed use a
 225       // sign extend, otherwise use a zero extend.
 226       if (Args[i].second->isSigned())
 227         Args[i].first = DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 228       else
 229         Args[i].first = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 230       break;
 231     case MVT::i32:
 232     case MVT::f32:
 233     case MVT::f64:
 234       break;
 235     }
 236     args_to_use.push_back(Args[i].first);
 237   }
 238
 239   std::vector<MVT::ValueType> RetVals;
 240   MVT::ValueType RetTyVT = getValueType(RetTy);
 241   if (RetTyVT != MVT::isVoid)
 242     RetVals.push_back(RetTyVT);
 243   RetVals.push_back(MVT::Other);
 244
 245   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 246                                             Chain, Callee, args_to_use), 0);
 247   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 248   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 249                       DAG.getConstant(NumBytes, getPointerTy()));
 250   return std::make_pair(TheCall, Chain);
 251 }
 252
 253 std::pair<SDOperand, SDOperand>
 254 PPC32TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 255   //vastart just returns the address of the VarArgsFrameIndex slot.
 256   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 257 }
 258
 259 std::pair<SDOperand,SDOperand> PPC32TargetLowering::
 260 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 261                const Type *ArgTy, SelectionDAG &DAG) {
 262   abort();
 263 }
 264
 265
 266 std::pair<SDOperand, SDOperand> PPC32TargetLowering::
 267 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 268                         SelectionDAG &DAG) {
 269   abort();
 270 }
 271
 272 namespace {
 273
 274 //===--------------------------------------------------------------------===//
 275 /// ISel - PPC32 specific code to select PPC32 machine instructions for
 276 /// SelectionDAG operations.
 277 //===--------------------------------------------------------------------===//
 278 class ISel : public SelectionDAGISel {
 279
 280   /// Comment Here.
 281   PPC32TargetLowering PPC32Lowering;
 282
 283   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 284   /// vreg the value is produced in, so we only emit one copy of each compiled
 285   /// tree.
 286   std::map<SDOperand, unsigned> ExprMap;
 287
 288 public:
 289   ISel(TargetMachine &TM) : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM)
 290   {}
 291
 292   /// InstructionSelectBasicBlock - This callback is invoked by
 293   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 294   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 295     DEBUG(BB->dump());
 296     // Codegen the basic block.
 297     Select(DAG.getRoot());
 298
 299     // Clear state used for selection.
 300     ExprMap.clear();
 301   }
 302
 303   unsigned SelectExpr(SDOperand N);
 304   unsigned SelectExprFP(SDOperand N, unsigned Result);
 305   void Select(SDOperand N);
 306
 307   void SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 308   void SelectBranchCC(SDOperand N);
 309 };
 310
 311 /// canUseAsImmediateForOpcode - This method returns a value indicating whether
 312 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 313 /// values are either 0, 1 or 2.  0 indicates that either N is not a
 314 /// ConstantSDNode, or is not suitable for use by that opcode.  A return value
 315 /// of 1 indicates that the constant may be used in normal immediate form.  A
 316 /// return value of 2 indicates that the constant may be used in shifted
 317 /// immediate form.  If the return value is nonzero, the constant value is
 318 /// placed in Imm.
 319 ///
 320 static unsigned canUseAsImmediateForOpcode(SDOperand N, unsigned Opcode,
 321                                            unsigned& Imm) {
 322   if (N.getOpcode() != ISD::Constant) return 0;
 323
 324   int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 325
 326   switch(Opcode) {
 327   default: return 0;
 328   case ISD::ADD:
 329     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 330     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 331     break;
 332   case ISD::AND:
 333   case ISD::XOR:
 334   case ISD::OR:
 335     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 336     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 337     break;
 338   }
 339   return 0;
 340 }
 341 }
 342
 343 //Check to see if the load is a constant offset from a base register
 344 void ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 345 {
 346   Reg = SelectExpr(N);
 347   offset = 0;
 348   return;
 349 }
 350
 351 void ISel::SelectBranchCC(SDOperand N)
 352 {
 353   assert(N.getOpcode() == ISD::BRCOND && "Not a BranchCC???");
 354   MachineBasicBlock *Dest =
 355     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
 356   unsigned Opc;
 357
 358   Select(N.getOperand(0));  //chain
 359   SDOperand CC = N.getOperand(1);
 360
 361   //Giveup and do the stupid thing
 362   unsigned Tmp1 = SelectExpr(CC);
 363   BuildMI(BB, PPC::BNE, 2).addReg(Tmp1).addMBB(Dest);
 364   return;
 365 }
 366
 367 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
 368 {
 369   unsigned Tmp1, Tmp2, Tmp3;
 370   unsigned Opc = 0;
 371   SDNode *Node = N.Val;
 372   MVT::ValueType DestType = N.getValueType();
 373   unsigned opcode = N.getOpcode();
 374
 375   switch (opcode) {
 376   default:
 377     Node->dump();
 378     assert(0 && "Node not handled!\n");
 379
 380   case ISD::SELECT:
 381     abort();
 382
 383   case ISD::FP_ROUND:
 384     assert (DestType == MVT::f32 &&
 385             N.getOperand(0).getValueType() == MVT::f64 &&
 386             "only f64 to f32 conversion supported here");
 387     Tmp1 = SelectExpr(N.getOperand(0));
 388     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
 389     return Result;
 390
 391   case ISD::FP_EXTEND:
 392     assert (DestType == MVT::f64 &&
 393             N.getOperand(0).getValueType() == MVT::f32 &&
 394             "only f32 to f64 conversion supported here");
 395     Tmp1 = SelectExpr(N.getOperand(0));
 396     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
 397     return Result;
 398
 399   case ISD::CopyFromReg:
 400     // FIXME: Handle copy from physregs!
 401     // Just use the specified register as our input.
 402     return dyn_cast<RegSDNode>(Node)->getReg();
 403
 404   case ISD::LOAD:
 405   case ISD::EXTLOAD:
 406     abort();
 407
 408   case ISD::ConstantFP:
 409     abort();
 410
 411   case ISD::MUL:
 412   case ISD::ADD:
 413   case ISD::SUB:
 414   case ISD::SDIV:
 415     switch( opcode ) {
 416     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
 417     case ISD::ADD:  Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS; break;
 418     case ISD::SUB:  Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS; break;
 419     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
 420     };
 421
 422     Tmp1 = SelectExpr(N.getOperand(0));
 423     Tmp2 = SelectExpr(N.getOperand(1));
 424     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 425     return Result;
 426
 427   case ISD::UINT_TO_FP:
 428   case ISD::SINT_TO_FP:
 429     abort();
 430   }
 431   assert(0 && "should not get here");
 432   return 0;
 433 }
 434
 435 unsigned ISel::SelectExpr(SDOperand N) {
 436   unsigned Result;
 437   unsigned Tmp1, Tmp2, Tmp3;
 438   unsigned Opc = 0;
 439   unsigned opcode = N.getOpcode();
 440
 441   SDNode *Node = N.Val;
 442   MVT::ValueType DestType = N.getValueType();
 443
 444   unsigned &Reg = ExprMap[N];
 445   if (Reg) return Reg;
 446
 447   if (N.getOpcode() != ISD::CALL && N.getOpcode() != ISD::ADD_PARTS &&
 448       N.getOpcode() != ISD::SUB_PARTS)
 449     Reg = Result = (N.getValueType() != MVT::Other) ?
 450       MakeReg(N.getValueType()) : 1;
 451   else {
 452     // If this is a call instruction, make sure to prepare ALL of the result
 453     // values as well as the chain.
 454     if (N.getOpcode() == ISD::CALL) {
 455       if (Node->getNumValues() == 1)
 456         Reg = Result = 1;  // Void call, just a chain.
 457       else {
 458         Result = MakeReg(Node->getValueType(0));
 459         ExprMap[N.getValue(0)] = Result;
 460         for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 461           ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 462         ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 463       }
 464     } else {
 465       Result = MakeReg(Node->getValueType(0));
 466       ExprMap[N.getValue(0)] = Result;
 467       for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
 468         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 469     }
 470   }
 471
 472   if (DestType == MVT::f64 || DestType == MVT::f32)
 473     return SelectExprFP(N, Result);
 474
 475   switch (opcode) {
 476   default:
 477     Node->dump();
 478     assert(0 && "Node not handled!\n");
 479
 480   case ISD::DYNAMIC_STACKALLOC:
 481     // Generate both result values.  FIXME: Need a better commment here?
 482     if (Result != 1)
 483       ExprMap[N.getValue(1)] = 1;
 484     else
 485       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 486
 487     // FIXME: We are currently ignoring the requested alignment for handling
 488     // greater than the stack alignment.  This will need to be revisited at some
 489     // point.  Align = N.getOperand(2);
 490     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 491         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 492       std::cerr << "Cannot allocate stack object with greater alignment than"
 493                 << " the stack alignment yet!";
 494       abort();
 495     }
 496     Select(N.getOperand(0));
 497     Tmp1 = SelectExpr(N.getOperand(1));
 498     // Subtract size from stack pointer, thereby allocating some space.
 499     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 500     // Put a pointer to the space into the result register by copying the SP
 501     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 502     return Result;
 503
 504   case ISD::ConstantPool:
 505     abort();
 506
 507   case ISD::FrameIndex:
 508     abort();
 509
 510   case ISD::GlobalAddress: {
 511     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 512     unsigned Tmp1 = MakeReg(MVT::i32);
 513     // FIXME: R1 is incorrect, we need the getGlobalBaseReg() functionality
 514     // from the simple isel
 515     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(PPC::R1).addGlobalAddress(GV);
 516     if (GV->hasWeakLinkage() || GV->isExternal()) {
 517       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 518     } else {
 519       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
 520     }
 521     return Result;
 522   }
 523
 524   case ISD::LOAD:
 525   case ISD::EXTLOAD:
 526   case ISD::ZEXTLOAD:
 527   case ISD::SEXTLOAD: {
 528     // Make sure we generate both values.
 529     if (Result != 1)
 530       ExprMap[N.getValue(1)] = 1;   // Generate the token
 531     else
 532       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 533
 534     SDOperand Chain   = N.getOperand(0);
 535     SDOperand Address = N.getOperand(1);
 536     Select(Chain);
 537
 538     switch (Node->getValueType(0)) {
 539     default: assert(0 && "Cannot load this type!");
 540     case MVT::i1:  Opc = PPC::LBZ; Tmp3 = 0; break;
 541     case MVT::i8:  Opc = PPC::LBZ; Tmp3 = 1; break;
 542     case MVT::i16: Opc = PPC::LHZ; Tmp3 = 0; break;
 543     case MVT::i32: Opc = PPC::LWZ; Tmp3 = 0; break;
 544     }
 545
 546     if(Address.getOpcode() == ISD::FrameIndex) {
 547       BuildMI(BB, Opc, 2, Result)
 548       .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex())
 549       .addReg(PPC::R1);
 550     } else {
 551       int offset;
 552       SelectAddr(Address, Tmp1, offset);
 553       BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 554     }
 555     return Result;
 556   }
 557
 558   case ISD::CALL: {
 559     // Lower the chain for this call.
 560     Select(N.getOperand(0));
 561     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
 562
 563     // get the virtual reg for each argument
 564     std::vector<unsigned> VRegs;
 565     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
 566       VRegs.push_back(SelectExpr(N.getOperand(i)));
 567
 568     // The ABI specifies that the first 32 bytes of args may be passed in GPRs,
 569     // and that 13 FPRs may also be used for passing any floating point args.
 570     int GPR_remaining = 8, FPR_remaining = 13;
 571     unsigned GPR_idx = 0, FPR_idx = 0;
 572     static const unsigned GPR[] = {
 573       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 574       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 575     };
 576     static const unsigned FPR[] = {
 577       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6,
 578       PPC::F7, PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12,
 579       PPC::F13
 580     };
 581
 582     // move the vregs into the appropriate architected register or stack slot
 583     for(int i = 0, e = VRegs.size(); i < e; ++i) {
 584         unsigned OperandType = N.getOperand(i+2).getValueType();
 585         switch(OperandType) {
 586         default:
 587           Node->dump();
 588           N.getOperand(i).Val->dump();
 589           std::cerr << "Type for " << i << " is: " <<
 590             N.getOperand(i+2).getValueType() << "\n";
 591           assert(0 && "Unknown value type for call");
 592         case MVT::i1:
 593         case MVT::i8:
 594         case MVT::i16:
 595         case MVT::i32:
 596           if (GPR_remaining > 0)
 597             BuildMI(BB, PPC::OR, 2, GPR[GPR_idx]).addReg(VRegs[i])
 598               .addReg(VRegs[i]);
 599           break;
 600         case MVT::f32:
 601         case MVT::f64:
 602           if (FPR_remaining > 0) {
 603             BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(VRegs[i]);
 604             --FPR_remaining;
 605           }
 606           break;
 607         }
 608         // All arguments consume GPRs available for argument passing
 609         if (GPR_remaining > 0) --GPR_remaining;
 610         if (MVT::f64 == OperandType && GPR_remaining > 0) --GPR_remaining;
 611     }
 612
 613     // Emit the correct call instruction based on the type of symbol called.
 614     if (GlobalAddressSDNode *GASD =
 615         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
 616       BuildMI(BB, PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(), true);
 617     } else if (ExternalSymbolSDNode *ESSDN =
 618                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
 619       BuildMI(BB, PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(), true);
 620     } else {
 621       Tmp1 = SelectExpr(N.getOperand(1));
 622       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
 623       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
 624       BuildMI(BB, PPC::CALLindirect, 3).addImm(20).addImm(0).addReg(PPC::R12);
 625     }
 626
 627     switch (Node->getValueType(0)) {
 628     default: assert(0 && "Unknown value type for call result!");
 629     case MVT::Other: return 1;
 630     case MVT::i1:
 631     case MVT::i8:
 632     case MVT::i16:
 633     case MVT::i32:
 634       BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3);
 635       if (Node->getValueType(1) == MVT::i32)
 636         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R4);
 637       break;
 638     case MVT::f32:
 639     case MVT::f64:
 640       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
 641       break;
 642     }
 643     return Result+N.ResNo;
 644   }
 645
 646   case ISD::SIGN_EXTEND:
 647   case ISD::SIGN_EXTEND_INREG:
 648     Tmp1 = SelectExpr(N.getOperand(0));
 649     BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
 650     return Result;
 651
 652   case ISD::ZERO_EXTEND_INREG:
 653     Tmp1 = SelectExpr(N.getOperand(0));
 654     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 655     default:
 656       Node->dump();
 657       assert(0 && "Zero Extend InReg not there yet");
 658       break;
 659     case MVT::i16:  Tmp2 = 16; break;
 660     case MVT::i8:   Tmp2 = 24; break;
 661     case MVT::i1:   Tmp2 = 31; break;
 662     }
 663     BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(0).addImm(0)
 664       .addImm(Tmp2).addImm(31);
 665     return Result;
 666
 667   case ISD::CopyFromReg:
 668     if (Result == 1)
 669       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 670     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
 671     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
 672     return Result;
 673
 674   case ISD::SHL:
 675     Tmp1 = SelectExpr(N.getOperand(0));
 676     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 677       Tmp2 = CN->getValue() & 0x1F;
 678       BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
 679         .addImm(31-Tmp2);
 680     } else {
 681       Tmp2 = SelectExpr(N.getOperand(1));
 682       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 683     }
 684     return Result;
 685
 686   case ISD::SRL:
 687     Tmp1 = SelectExpr(N.getOperand(0));
 688     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 689       Tmp2 = CN->getValue() & 0x1F;
 690       BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(32-Tmp2)
 691         .addImm(Tmp2).addImm(31);
 692     } else {
 693       Tmp2 = SelectExpr(N.getOperand(1));
 694       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 695     }
 696     return Result;
 697
 698   case ISD::SRA:
 699     Tmp1 = SelectExpr(N.getOperand(0));
 700     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 701       Tmp2 = CN->getValue() & 0x1F;
 702       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
 703     } else {
 704       Tmp2 = SelectExpr(N.getOperand(1));
 705       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 706     }
 707     return Result;
 708
 709   case ISD::ADD:
 710     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 711     Tmp1 = SelectExpr(N.getOperand(0));
 712     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 713       default: assert(0 && "unhandled result code");
 714       case 0: // No immediate
 715         Tmp2 = SelectExpr(N.getOperand(1));
 716         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
 717         break;
 718       case 1: // Low immediate
 719         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 720         break;
 721       case 2: // Shifted immediate
 722         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 723         break;
 724     }
 725     return Result;
 726
 727   case ISD::AND:
 728   case ISD::OR:
 729   case ISD::XOR:
 730     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 731     Tmp1 = SelectExpr(N.getOperand(0));
 732     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 733       default: assert(0 && "unhandled result code");
 734       case 0: // No immediate
 735         Tmp2 = SelectExpr(N.getOperand(1));
 736         switch (opcode) {
 737         case ISD::AND: Opc = PPC::AND; break;
 738         case ISD::OR:  Opc = PPC::OR;  break;
 739         case ISD::XOR: Opc = PPC::XOR; break;
 740         }
 741         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 742         break;
 743       case 1: // Low immediate
 744         switch (opcode) {
 745         case ISD::AND: Opc = PPC::ANDIo; break;
 746         case ISD::OR:  Opc = PPC::ORI;   break;
 747         case ISD::XOR: Opc = PPC::XORI;  break;
 748         }
 749         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
 750         break;
 751       case 2: // Shifted immediate
 752         switch (opcode) {
 753         case ISD::AND: Opc = PPC::ANDISo;  break;
 754         case ISD::OR:  Opc = PPC::ORIS;    break;
 755         case ISD::XOR: Opc = PPC::XORIS;   break;
 756         }
 757         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
 758         break;
 759     }
 760     return Result;
 761
 762   case ISD::SUB:
 763     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 764     Tmp1 = SelectExpr(N.getOperand(0));
 765     Tmp2 = SelectExpr(N.getOperand(1));
 766     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
 767     return Result;
 768
 769   case ISD::MUL:
 770     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 771     Tmp1 = SelectExpr(N.getOperand(0));
 772     Tmp2 = SelectExpr(N.getOperand(1));
 773     BuildMI(BB, PPC::MULLW, 2, Result).addReg(Tmp2).addReg(Tmp1);
 774     return Result;
 775
 776   case ISD::ADD_PARTS:
 777   case ISD::SUB_PARTS:
 778   case ISD::UREM:
 779   case ISD::SREM:
 780   case ISD::SDIV:
 781   case ISD::UDIV:
 782     abort();
 783
 784   case ISD::FP_TO_UINT:
 785   case ISD::FP_TO_SINT:
 786     abort();
 787
 788   case ISD::SETCC:
 789     abort();
 790
 791   case ISD::SELECT:
 792     abort();
 793
 794   case ISD::Constant:
 795     switch (N.getValueType()) {
 796     default: assert(0 && "Cannot use constants of this type!");
 797     case MVT::i1:
 798       BuildMI(BB, PPC::LI, 1, Result)
 799         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
 800       break;
 801     case MVT::i32:
 802       {
 803         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 804         if (v < 32768 && v >= -32768) {
 805           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
 806         } else {
 807           Tmp1 = MakeReg(MVT::i32);
 808           BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
 809           BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(v & 0xFFFF);
 810         }
 811       }
 812     }
 813     return Result;
 814   }
 815
 816   return 0;
 817 }
 818
 819 void ISel::Select(SDOperand N) {
 820   unsigned Tmp1, Tmp2, Opc;
 821   unsigned opcode = N.getOpcode();
 822
 823   if (!ExprMap.insert(std::make_pair(N, 1)).second)
 824     return;  // Already selected.
 825
 826   SDNode *Node = N.Val;
 827
 828   switch (Node->getOpcode()) {
 829   default:
 830     Node->dump(); std::cerr << "\n";
 831     assert(0 && "Node not handled yet!");
 832   case ISD::EntryToken: return;  // Noop
 833   case ISD::TokenFactor:
 834     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 835       Select(Node->getOperand(i));
 836     return;
 837   case ISD::ADJCALLSTACKDOWN:
 838   case ISD::ADJCALLSTACKUP:
 839     Select(N.getOperand(0));
 840     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
 841     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? PPC::ADJCALLSTACKDOWN :
 842       PPC::ADJCALLSTACKUP;
 843     BuildMI(BB, Opc, 1).addImm(Tmp1);
 844     return;
 845   case ISD::BR: {
 846     MachineBasicBlock *Dest =
 847       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
 848     Select(N.getOperand(0));
 849     BuildMI(BB, PPC::B, 1).addMBB(Dest);
 850     return;
 851   }
 852   case ISD::BRCOND:
 853     SelectBranchCC(N);
 854     return;
 855   case ISD::CopyToReg:
 856     Select(N.getOperand(0));
 857     Tmp1 = SelectExpr(N.getOperand(1));
 858     Tmp2 = cast<RegSDNode>(N)->getReg();
 859
 860     if (Tmp1 != Tmp2) {
 861       if (N.getOperand(1).getValueType() == MVT::f64 ||
 862           N.getOperand(1).getValueType() == MVT::f32)
 863         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
 864       else
 865         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
 866     }
 867     return;
 868   case ISD::ImplicitDef:
 869     Select(N.getOperand(0));
 870     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
 871     return;
 872   case ISD::RET:
 873     switch (N.getNumOperands()) {
 874     default:
 875       assert(0 && "Unknown return instruction!");
 876     case 3:
 877       assert(N.getOperand(1).getValueType() == MVT::i32 &&
 878              N.getOperand(2).getValueType() == MVT::i32 &&
 879                    "Unknown two-register value!");
 880       Select(N.getOperand(0));
 881       Tmp1 = SelectExpr(N.getOperand(1));
 882       Tmp2 = SelectExpr(N.getOperand(2));
 883       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
 884       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp2).addReg(Tmp2);
 885       break;
 886     case 2:
 887       Select(N.getOperand(0));
 888       Tmp1 = SelectExpr(N.getOperand(1));
 889       switch (N.getOperand(1).getValueType()) {
 890         default:
 891           assert(0 && "Unknown return type!");
 892         case MVT::f64:
 893         case MVT::f32:
 894           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
 895           break;
 896         case MVT::i32:
 897           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
 898           break;
 899       }
 900     case 1:
 901       Select(N.getOperand(0));
 902       break;
 903     }
 904     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
 905     return;
 906   case ISD::TRUNCSTORE:
 907   case ISD::STORE:
 908     {
 909       SDOperand Chain   = N.getOperand(0);
 910       SDOperand Value   = N.getOperand(1);
 911       SDOperand Address = N.getOperand(2);
 912       Select(Chain);
 913
 914       Tmp1 = SelectExpr(Value); //value
 915
 916       if (opcode == ISD::STORE) {
 917         switch(Value.getValueType()) {
 918         default: assert(0 && "unknown Type in store");
 919         case MVT::i32: Opc = PPC::STW; break;
 920         case MVT::f64: Opc = PPC::STFD; break;
 921         case MVT::f32: Opc = PPC::STFS; break;
 922         }
 923       } else { //ISD::TRUNCSTORE
 924         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 925         default: assert(0 && "unknown Type in store");
 926         case MVT::i1: //FIXME: DAG does not promote this load
 927         case MVT::i8: Opc  = PPC::STB; break;
 928         case MVT::i16: Opc = PPC::STH; break;
 929         }
 930       }
 931
 932       if (Address.getOpcode() == ISD::GlobalAddress)
 933       {
 934         BuildMI(BB, Opc, 2).addReg(Tmp1)
 935           .addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
 936       }
 937       else if(Address.getOpcode() == ISD::FrameIndex)
 938       {
 939         BuildMI(BB, Opc, 2).addReg(Tmp1)
 940           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex());
 941       }
 942       else
 943       {
 944         int offset;
 945         SelectAddr(Address, Tmp2, offset);
 946         BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
 947       }
 948       return;
 949     }
 950   case ISD::EXTLOAD:
 951   case ISD::SEXTLOAD:
 952   case ISD::ZEXTLOAD:
 953   case ISD::LOAD:
 954   case ISD::CopyFromReg:
 955   case ISD::CALL:
 956   case ISD::DYNAMIC_STACKALLOC:
 957     ExprMap.erase(N);
 958     SelectExpr(N);
 959     return;
 960   }
 961   assert(0 && "Should not be reached!");
 962 }
 963
 964
 965 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
 966 /// into a machine code representation using pattern matching and a machine
 967 /// description file.
 968 ///
 969 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
 970   return new ISel(TM);
 971 }
 972