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 the LLVM research group 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     case MVT::i32:
 225     case MVT::i64:
 226     case MVT::f64:
 227     case MVT::f32:
 228       break;
 229     }
 230     args_to_use.push_back(Args[i].first);
 231   }
 232
 233   std::vector<MVT::ValueType> RetVals;
 234   MVT::ValueType RetTyVT = getValueType(RetTy);
 235   if (RetTyVT != MVT::isVoid)
 236     RetVals.push_back(RetTyVT);
 237   RetVals.push_back(MVT::Other);
 238
 239   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 240                                             Chain, Callee, args_to_use), 0);
 241   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 242   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 243                       DAG.getConstant(NumBytes, getPointerTy()));
 244   return std::make_pair(TheCall, Chain);
 245 }
 246
 247 std::pair<SDOperand, SDOperand>
 248 PPC32TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 249   //vastart just returns the address of the VarArgsFrameIndex slot.
 250   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 251 }
 252
 253 std::pair<SDOperand,SDOperand> PPC32TargetLowering::
 254 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 255                const Type *ArgTy, SelectionDAG &DAG) {
 256   abort();
 257 }
 258
 259
 260 std::pair<SDOperand, SDOperand> PPC32TargetLowering::
 261 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 262                         SelectionDAG &DAG) {
 263   abort();
 264 }
 265
 266 namespace {
 267
 268 //===--------------------------------------------------------------------===//
 269 /// ISel - PPC32 specific code to select PPC32 machine instructions for
 270 /// SelectionDAG operations.
 271 //===--------------------------------------------------------------------===//
 272 class ISel : public SelectionDAGISel {
 273
 274   /// Comment Here.
 275   PPC32TargetLowering PPC32Lowering;
 276
 277   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 278   /// vreg the value is produced in, so we only emit one copy of each compiled
 279   /// tree.
 280   std::map<SDOperand, unsigned> ExprMap;
 281
 282 public:
 283   ISel(TargetMachine &TM) : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM)
 284   {}
 285
 286   /// InstructionSelectBasicBlock - This callback is invoked by
 287   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 288   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 289     DEBUG(BB->dump());
 290     // Codegen the basic block.
 291     Select(DAG.getRoot());
 292
 293     // Clear state used for selection.
 294     ExprMap.clear();
 295   }
 296
 297   unsigned SelectExpr(SDOperand N);
 298   unsigned SelectExprFP(SDOperand N, unsigned Result);
 299   void Select(SDOperand N);
 300
 301   void SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 302   void SelectBranchCC(SDOperand N);
 303 };
 304
 305 /// canUseAsImmediateForOpcode - This method returns a value indicating whether
 306 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 307 /// values are either 0, 1 or 2.  0 indicates that either N is not a
 308 /// ConstantSDNode, or is not suitable for use by that opcode.  A return value
 309 /// of 1 indicates that the constant may be used in normal immediate form.  A
 310 /// return value of 2 indicates that the constant may be used in shifted
 311 /// immediate form.  If the return value is nonzero, the constant value is
 312 /// placed in Imm.
 313 ///
 314 static unsigned canUseAsImmediateForOpcode(SDOperand N, unsigned Opcode,
 315                                            unsigned& Imm) {
 316   if (N.getOpcode() != ISD::Constant) return 0;
 317
 318   int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 319
 320   switch(Opcode) {
 321   default: return 0;
 322   case ISD::ADD:
 323     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 324     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 325     break;
 326   case ISD::AND:
 327   case ISD::XOR:
 328   case ISD::OR:
 329     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 330     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 331     break;
 332   }
 333   return 0;
 334 }
 335 }
 336
 337 //Check to see if the load is a constant offset from a base register
 338 void ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 339 {
 340   Reg = SelectExpr(N);
 341   offset = 0;
 342   return;
 343 }
 344
 345 void ISel::SelectBranchCC(SDOperand N)
 346 {
 347   assert(N.getOpcode() == ISD::BRCOND && "Not a BranchCC???");
 348   MachineBasicBlock *Dest =
 349     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
 350   unsigned Opc;
 351
 352   Select(N.getOperand(0));  //chain
 353   SDOperand CC = N.getOperand(1);
 354
 355   //Giveup and do the stupid thing
 356   unsigned Tmp1 = SelectExpr(CC);
 357   BuildMI(BB, PPC::BNE, 2).addReg(Tmp1).addMBB(Dest);
 358   return;
 359 }
 360
 361 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
 362 {
 363   unsigned Tmp1, Tmp2, Tmp3;
 364   unsigned Opc = 0;
 365   SDNode *Node = N.Val;
 366   MVT::ValueType DestType = N.getValueType();
 367   unsigned opcode = N.getOpcode();
 368
 369   switch (opcode) {
 370   default:
 371     Node->dump();
 372     assert(0 && "Node not handled!\n");
 373
 374   case ISD::SELECT:
 375     abort();
 376
 377   case ISD::FP_ROUND:
 378     assert (DestType == MVT::f32 &&
 379             N.getOperand(0).getValueType() == MVT::f64 &&
 380             "only f64 to f32 conversion supported here");
 381     Tmp1 = SelectExpr(N.getOperand(0));
 382     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
 383     return Result;
 384
 385   case ISD::FP_EXTEND:
 386     assert (DestType == MVT::f64 &&
 387             N.getOperand(0).getValueType() == MVT::f32 &&
 388             "only f32 to f64 conversion supported here");
 389     Tmp1 = SelectExpr(N.getOperand(0));
 390     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
 391     return Result;
 392
 393   case ISD::CopyFromReg:
 394     // FIXME: Handle copy from physregs!
 395     // Just use the specified register as our input.
 396     return dyn_cast<RegSDNode>(Node)->getReg();
 397
 398   case ISD::LOAD:
 399     abort();
 400
 401   case ISD::ConstantFP:
 402     abort();
 403
 404   case ISD::MUL:
 405   case ISD::ADD:
 406   case ISD::SUB:
 407   case ISD::SDIV:
 408     switch( opcode ) {
 409     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
 410     case ISD::ADD:  Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS; break;
 411     case ISD::SUB:  Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS; break;
 412     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
 413     };
 414
 415     Tmp1 = SelectExpr(N.getOperand(0));
 416     Tmp2 = SelectExpr(N.getOperand(1));
 417     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 418     return Result;
 419
 420   case ISD::EXTLOAD:
 421     abort();
 422
 423   case ISD::UINT_TO_FP:
 424   case ISD::SINT_TO_FP:
 425     abort();
 426   }
 427   assert(0 && "should not get here");
 428   return 0;
 429 }
 430
 431 unsigned ISel::SelectExpr(SDOperand N) {
 432   unsigned Result;
 433   unsigned Tmp1, Tmp2, Tmp3;
 434   unsigned Opc = 0;
 435   unsigned opcode = N.getOpcode();
 436
 437   SDNode *Node = N.Val;
 438   MVT::ValueType DestType = N.getValueType();
 439
 440   unsigned &Reg = ExprMap[N];
 441   if (Reg) return Reg;
 442
 443   if (DestType == MVT::f64 || DestType == MVT::f32)
 444     return SelectExprFP(N, Result);
 445
 446   if (N.getOpcode() != ISD::CALL)
 447     Reg = Result = (N.getValueType() != MVT::Other) ?
 448       MakeReg(N.getValueType()) : 1;
 449   else
 450     abort(); // FIXME: Implement Call
 451
 452   switch (opcode) {
 453   default:
 454     Node->dump();
 455     assert(0 && "Node not handled!\n");
 456
 457   case ISD::DYNAMIC_STACKALLOC:
 458     abort();
 459
 460   case ISD::ConstantPool:
 461     abort();
 462
 463   case ISD::FrameIndex:
 464     abort();
 465
 466   case ISD::EXTLOAD:
 467   case ISD::ZEXTLOAD:
 468   case ISD::SEXTLOAD:
 469   case ISD::LOAD:
 470   case ISD::GlobalAddress:
 471   case ISD::CALL:
 472     abort();
 473
 474   case ISD::SIGN_EXTEND:
 475   case ISD::SIGN_EXTEND_INREG:
 476     Tmp1 = SelectExpr(N.getOperand(0));
 477     BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
 478     return Result;
 479
 480   case ISD::ZERO_EXTEND_INREG:
 481     Tmp1 = SelectExpr(N.getOperand(0));
 482     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 483     default:
 484       Node->dump();
 485       assert(0 && "Zero Extend InReg not there yet");
 486       break;
 487     case MVT::i16:  Tmp2 = 16; break;
 488     case MVT::i8:   Tmp2 = 24; break;
 489     case MVT::i1:   Tmp2 = 31; break;
 490     }
 491     BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(0).addImm(0)
 492       .addImm(Tmp2).addImm(31);
 493     return Result;
 494
 495   case ISD::SETCC:
 496     abort();
 497
 498   case ISD::CopyFromReg:
 499     if (Result == 1)
 500       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 501     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
 502     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
 503     return Result;
 504
 505   case ISD::SHL:
 506   case ISD::SRL:
 507   case ISD::SRA:
 508   case ISD::MUL:
 509     abort();
 510
 511   case ISD::ADD:
 512     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 513     Tmp1 = SelectExpr(N.getOperand(0));
 514     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 515       default: assert(0 && "unhandled result code");
 516       case 0: // No immediate
 517         Tmp2 = SelectExpr(N.getOperand(1));
 518         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
 519         break;
 520       case 1: // Low immediate
 521         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 522         break;
 523       case 2: // Shifted immediate
 524         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 525         break;
 526     }
 527     return Result;
 528
 529   case ISD::SUB:
 530     abort();
 531
 532   case ISD::AND:
 533   case ISD::OR:
 534   case ISD::XOR:
 535     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 536     Tmp1 = SelectExpr(N.getOperand(0));
 537     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 538       default: assert(0 && "unhandled result code");
 539       case 0: // No immediate
 540         Tmp2 = SelectExpr(N.getOperand(1));
 541         switch (opcode) {
 542         case ISD::AND: Tmp3 = PPC::AND; break;
 543         case ISD::OR:  Tmp3 = PPC::OR;  break;
 544         case ISD::XOR: Tmp3 = PPC::XOR; break;
 545         }
 546         BuildMI(BB, Tmp3, 2, Result).addReg(Tmp1).addReg(Tmp2);
 547         break;
 548       case 1: // Low immediate
 549         switch (opcode) {
 550         case ISD::AND: Tmp3 = PPC::ANDIo; break;
 551         case ISD::OR:  Tmp3 = PPC::ORI;   break;
 552         case ISD::XOR: Tmp3 = PPC::XORI;  break;
 553         }
 554         BuildMI(BB, Tmp3, 2, Result).addReg(Tmp1).addImm(Tmp2);
 555         break;
 556       case 2: // Shifted immediate
 557         switch (opcode) {
 558         case ISD::AND: Tmp3 = PPC::ANDISo;  break;
 559         case ISD::OR:  Tmp3 = PPC::ORIS;    break;
 560         case ISD::XOR: Tmp3 = PPC::XORIS;   break;
 561         }
 562         BuildMI(BB, Tmp3, 2, Result).addReg(Tmp1).addImm(Tmp2);
 563         break;
 564     }
 565     return Result;
 566
 567   case ISD::UREM:
 568   case ISD::SREM:
 569   case ISD::SDIV:
 570   case ISD::UDIV:
 571     abort();
 572
 573   case ISD::FP_TO_UINT:
 574   case ISD::FP_TO_SINT:
 575     abort();
 576
 577   case ISD::SELECT:
 578     abort();
 579
 580   case ISD::Constant:
 581     switch (N.getValueType()) {
 582     default: assert(0 && "Cannot use constants of this type!");
 583     case MVT::i1:
 584       BuildMI(BB, PPC::LI, 1, Result)
 585         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
 586       break;
 587     case MVT::i32:
 588       {
 589         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 590         if (v < 32768 && v >= -32768) {
 591           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
 592         } else {
 593           unsigned Temp = MakeReg(MVT::i32);
 594           BuildMI(BB, PPC::LIS, 1, Temp).addSImm(v >> 16);
 595           BuildMI(BB, PPC::ORI, 2, Result).addReg(Temp).addImm(v & 0xFFFF);
 596         }
 597       }
 598     }
 599     return Result;
 600   }
 601
 602   return 0;
 603 }
 604
 605 void ISel::Select(SDOperand N) {
 606   unsigned Tmp1, Tmp2, Opc;
 607   unsigned opcode = N.getOpcode();
 608
 609   if (!ExprMap.insert(std::make_pair(N, 1)).second)
 610     return;  // Already selected.
 611
 612   SDNode *Node = N.Val;
 613
 614   switch (Node->getOpcode()) {
 615   default:
 616     Node->dump(); std::cerr << "\n";
 617     assert(0 && "Node not handled yet!");
 618   case ISD::EntryToken: return;  // Noop
 619   case ISD::TokenFactor:
 620     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 621       Select(Node->getOperand(i));
 622     return;
 623   case ISD::ADJCALLSTACKDOWN:
 624   case ISD::ADJCALLSTACKUP:
 625     Select(N.getOperand(0));
 626     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
 627     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? PPC::ADJCALLSTACKDOWN :
 628       PPC::ADJCALLSTACKUP;
 629     BuildMI(BB, Opc, 1).addImm(Tmp1);
 630     return;
 631   case ISD::BR: {
 632     MachineBasicBlock *Dest =
 633       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
 634
 635     Select(N.getOperand(0));
 636     BuildMI(BB, PPC::B, 1).addMBB(Dest);
 637     return;
 638   }
 639   case ISD::BRCOND:
 640     SelectBranchCC(N);
 641     return;
 642   case ISD::CopyToReg:
 643     Select(N.getOperand(0));
 644     Tmp1 = SelectExpr(N.getOperand(1));
 645     Tmp2 = cast<RegSDNode>(N)->getReg();
 646
 647     if (Tmp1 != Tmp2) {
 648       if (N.getOperand(1).getValueType() == MVT::f64 ||
 649           N.getOperand(1).getValueType() == MVT::f32)
 650         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
 651       else
 652         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
 653     }
 654     return;
 655   case ISD::ImplicitDef:
 656     Select(N.getOperand(0));
 657     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
 658     return;
 659   case ISD::RET:
 660     switch (N.getNumOperands()) {
 661     default:
 662       assert(0 && "Unknown return instruction!");
 663     case 3:
 664       assert(N.getOperand(1).getValueType() == MVT::i32 &&
 665              N.getOperand(2).getValueType() == MVT::i32 &&
 666                    "Unknown two-register value!");
 667       Select(N.getOperand(0));
 668       Tmp1 = SelectExpr(N.getOperand(1));
 669       Tmp2 = SelectExpr(N.getOperand(2));
 670       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
 671       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp2).addReg(Tmp2);
 672       break;
 673     case 2:
 674       Select(N.getOperand(0));
 675       Tmp1 = SelectExpr(N.getOperand(1));
 676       switch (N.getOperand(1).getValueType()) {
 677         default:
 678           assert(0 && "Unknown return type!");
 679         case MVT::f64:
 680         case MVT::f32:
 681           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
 682           break;
 683         case MVT::i32:
 684           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
 685           break;
 686       }
 687     }
 688     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
 689     return;
 690
 691   case ISD::TRUNCSTORE:
 692   case ISD::STORE:
 693     {
 694       SDOperand Chain   = N.getOperand(0);
 695       SDOperand Value   = N.getOperand(1);
 696       SDOperand Address = N.getOperand(2);
 697       Select(Chain);
 698
 699       Tmp1 = SelectExpr(Value); //value
 700
 701       if (opcode == ISD::STORE) {
 702         switch(Value.getValueType()) {
 703         default: assert(0 && "unknown Type in store");
 704         case MVT::i32: Opc = PPC::STW; break;
 705         case MVT::f64: Opc = PPC::STFD; break;
 706         case MVT::f32: Opc = PPC::STFS; break;
 707         }
 708       } else { //ISD::TRUNCSTORE
 709         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 710         default: assert(0 && "unknown Type in store");
 711         case MVT::i1: //FIXME: DAG does not promote this load
 712         case MVT::i8: Opc  = PPC::STB; break;
 713         case MVT::i16: Opc = PPC::STH; break;
 714         }
 715       }
 716
 717       if (Address.getOpcode() == ISD::GlobalAddress)
 718       {
 719         BuildMI(BB, Opc, 2).addReg(Tmp1)
 720           .addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
 721       }
 722       else if(Address.getOpcode() == ISD::FrameIndex)
 723       {
 724         BuildMI(BB, Opc, 2).addReg(Tmp1)
 725           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex());
 726       }
 727       else
 728       {
 729         int offset;
 730         SelectAddr(Address, Tmp2, offset);
 731         BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
 732       }
 733       return;
 734     }
 735   case ISD::EXTLOAD:
 736   case ISD::SEXTLOAD:
 737   case ISD::ZEXTLOAD:
 738   case ISD::LOAD:
 739   case ISD::CopyFromReg:
 740   case ISD::CALL:
 741   case ISD::DYNAMIC_STACKALLOC:
 742     ExprMap.erase(N);
 743     SelectExpr(N);
 744     return;
 745   }
 746   assert(0 && "Should not be reached!");
 747 }
 748
 749
 750 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
 751 /// into a machine code representation using pattern matching and a machine
 752 /// description file.
 753 ///
 754 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
 755   return new ISel(TM);
 756 }
 757