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     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   case ISD::EXTLOAD:
 400     abort();
 401
 402   case ISD::ConstantFP:
 403     abort();
 404
 405   case ISD::MUL:
 406   case ISD::ADD:
 407   case ISD::SUB:
 408   case ISD::SDIV:
 409     switch( opcode ) {
 410     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
 411     case ISD::ADD:  Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS; break;
 412     case ISD::SUB:  Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS; break;
 413     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
 414     };
 415
 416     Tmp1 = SelectExpr(N.getOperand(0));
 417     Tmp2 = SelectExpr(N.getOperand(1));
 418     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 419     return Result;
 420
 421   case ISD::UINT_TO_FP:
 422   case ISD::SINT_TO_FP:
 423     abort();
 424   }
 425   assert(0 && "should not get here");
 426   return 0;
 427 }
 428
 429 unsigned ISel::SelectExpr(SDOperand N) {
 430   unsigned Result;
 431   unsigned Tmp1, Tmp2, Tmp3;
 432   unsigned Opc = 0;
 433   unsigned opcode = N.getOpcode();
 434
 435   SDNode *Node = N.Val;
 436   MVT::ValueType DestType = N.getValueType();
 437
 438   unsigned &Reg = ExprMap[N];
 439   if (Reg) return Reg;
 440
 441   if (DestType == MVT::f64 || DestType == MVT::f32)
 442     return SelectExprFP(N, Result);
 443
 444   if (N.getOpcode() != ISD::CALL)
 445     Reg = Result = (N.getValueType() != MVT::Other) ?
 446       MakeReg(N.getValueType()) : 1;
 447   else
 448     abort(); // FIXME: Implement Call
 449
 450   switch (opcode) {
 451   default:
 452     Node->dump();
 453     assert(0 && "Node not handled!\n");
 454
 455   case ISD::DYNAMIC_STACKALLOC:
 456     // Generate both result values.  FIXME: Need a better commment here?
 457     if (Result != 1)
 458       ExprMap[N.getValue(1)] = 1;
 459     else
 460       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 461
 462     // FIXME: We are currently ignoring the requested alignment for handling
 463     // greater than the stack alignment.  This will need to be revisited at some
 464     // point.  Align = N.getOperand(2);
 465     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 466         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 467       std::cerr << "Cannot allocate stack object with greater alignment than"
 468                 << " the stack alignment yet!";
 469       abort();
 470     }
 471     Select(N.getOperand(0));
 472     Tmp1 = SelectExpr(N.getOperand(1));
 473     // Subtract size from stack pointer, thereby allocating some space.
 474     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 475     // Put a pointer to the space into the result register by copying the SP
 476     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 477     return Result;
 478
 479   case ISD::ConstantPool:
 480     abort();
 481
 482   case ISD::FrameIndex:
 483     abort();
 484
 485   case ISD::LOAD:
 486   case ISD::EXTLOAD:
 487   case ISD::ZEXTLOAD:
 488   {
 489     // Make sure we generate both values.
 490     if (Result != 1)
 491       ExprMap[N.getValue(1)] = 1;   // Generate the token
 492     else
 493       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 494
 495     SDOperand Chain   = N.getOperand(0);
 496     SDOperand Address = N.getOperand(1);
 497     Select(Chain);
 498
 499     switch (Node->getValueType(0)) {
 500     default: assert(0 && "Cannot load this type!");
 501     case MVT::i1:
 502     case MVT::i8:  Opc = PPC::LBZ; break;
 503     case MVT::i16: Opc = PPC::LHZ; break;
 504     case MVT::i32: Opc = PPC::LWZ; break;
 505     }
 506
 507     if (Address.getOpcode() == ISD::GlobalAddress) {  // FIXME
 508       BuildMI(BB, Opc, 2, Result)
 509         .addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal())
 510         .addReg(PPC::R1);
 511     }
 512     else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
 513       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CP->getIndex())
 514         .addReg(PPC::R1);
 515     }
 516     else if(Address.getOpcode() == ISD::FrameIndex) {
 517       BuildMI(BB, Opc, 2, Result)
 518       .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex())
 519       .addReg(PPC::R1);
 520     } else {
 521       int offset;
 522       SelectAddr(Address, Tmp1, offset);
 523       BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 524     }
 525     return Result;
 526   }
 527
 528   case ISD::SEXTLOAD:
 529   case ISD::GlobalAddress:
 530   case ISD::CALL:
 531     abort();
 532
 533   case ISD::SIGN_EXTEND:
 534   case ISD::SIGN_EXTEND_INREG:
 535     Tmp1 = SelectExpr(N.getOperand(0));
 536     BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
 537     return Result;
 538
 539   case ISD::ZERO_EXTEND_INREG:
 540     Tmp1 = SelectExpr(N.getOperand(0));
 541     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 542     default:
 543       Node->dump();
 544       assert(0 && "Zero Extend InReg not there yet");
 545       break;
 546     case MVT::i16:  Tmp2 = 16; break;
 547     case MVT::i8:   Tmp2 = 24; break;
 548     case MVT::i1:   Tmp2 = 31; break;
 549     }
 550     BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(0).addImm(0)
 551       .addImm(Tmp2).addImm(31);
 552     return Result;
 553
 554   case ISD::SETCC:
 555     abort();
 556
 557   case ISD::CopyFromReg:
 558     if (Result == 1)
 559       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 560     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
 561     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
 562     return Result;
 563
 564   case ISD::SHL:
 565     Tmp1 = SelectExpr(N.getOperand(0));
 566     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 567       Tmp2 = CN->getValue() & 0x1F;
 568       BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
 569         .addImm(31-Tmp2);
 570     } else {
 571       Tmp2 = SelectExpr(N.getOperand(1));
 572       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 573     }
 574     return Result;
 575
 576   case ISD::SRL:
 577     Tmp1 = SelectExpr(N.getOperand(0));
 578     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 579       Tmp2 = CN->getValue() & 0x1F;
 580       BuildMI(BB, PPC::RLWINM, 5, Result).addReg(Tmp1).addImm(32-Tmp2)
 581         .addImm(Tmp2).addImm(31);
 582     } else {
 583       Tmp2 = SelectExpr(N.getOperand(1));
 584       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 585     }
 586     return Result;
 587
 588   case ISD::SRA:
 589     Tmp1 = SelectExpr(N.getOperand(0));
 590     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 591       Tmp2 = CN->getValue() & 0x1F;
 592       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
 593     } else {
 594       Tmp2 = SelectExpr(N.getOperand(1));
 595       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
 596     }
 597     return Result;
 598
 599   case ISD::ADD:
 600     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 601     Tmp1 = SelectExpr(N.getOperand(0));
 602     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 603       default: assert(0 && "unhandled result code");
 604       case 0: // No immediate
 605         Tmp2 = SelectExpr(N.getOperand(1));
 606         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
 607         break;
 608       case 1: // Low immediate
 609         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 610         break;
 611       case 2: // Shifted immediate
 612         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 613         break;
 614     }
 615     return Result;
 616
 617   case ISD::SUB:
 618     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 619     Tmp1 = SelectExpr(N.getOperand(0));
 620     Tmp2 = SelectExpr(N.getOperand(1));
 621     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
 622     return Result;
 623
 624   case ISD::AND:
 625   case ISD::OR:
 626   case ISD::XOR:
 627     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
 628     Tmp1 = SelectExpr(N.getOperand(0));
 629     switch(canUseAsImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
 630       default: assert(0 && "unhandled result code");
 631       case 0: // No immediate
 632         Tmp2 = SelectExpr(N.getOperand(1));
 633         switch (opcode) {
 634         case ISD::AND: Opc = PPC::AND; break;
 635         case ISD::OR:  Opc = PPC::OR;  break;
 636         case ISD::XOR: Opc = PPC::XOR; break;
 637         }
 638         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 639         break;
 640       case 1: // Low immediate
 641         switch (opcode) {
 642         case ISD::AND: Opc = PPC::ANDIo; break;
 643         case ISD::OR:  Opc = PPC::ORI;   break;
 644         case ISD::XOR: Opc = PPC::XORI;  break;
 645         }
 646         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
 647         break;
 648       case 2: // Shifted immediate
 649         switch (opcode) {
 650         case ISD::AND: Opc = PPC::ANDISo;  break;
 651         case ISD::OR:  Opc = PPC::ORIS;    break;
 652         case ISD::XOR: Opc = PPC::XORIS;   break;
 653         }
 654         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
 655         break;
 656     }
 657     return Result;
 658
 659   case ISD::MUL:
 660   case ISD::UREM:
 661   case ISD::SREM:
 662   case ISD::SDIV:
 663   case ISD::UDIV:
 664     abort();
 665
 666   case ISD::FP_TO_UINT:
 667   case ISD::FP_TO_SINT:
 668     abort();
 669
 670   case ISD::SELECT:
 671     abort();
 672
 673   case ISD::Constant:
 674     switch (N.getValueType()) {
 675     default: assert(0 && "Cannot use constants of this type!");
 676     case MVT::i1:
 677       BuildMI(BB, PPC::LI, 1, Result)
 678         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
 679       break;
 680     case MVT::i32:
 681       {
 682         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 683         if (v < 32768 && v >= -32768) {
 684           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
 685         } else {
 686           Tmp1 = MakeReg(MVT::i32);
 687           BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
 688           BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(v & 0xFFFF);
 689         }
 690       }
 691     }
 692     return Result;
 693   }
 694
 695   return 0;
 696 }
 697
 698 void ISel::Select(SDOperand N) {
 699   unsigned Tmp1, Tmp2, Opc;
 700   unsigned opcode = N.getOpcode();
 701
 702   if (!ExprMap.insert(std::make_pair(N, 1)).second)
 703     return;  // Already selected.
 704
 705   SDNode *Node = N.Val;
 706
 707   switch (Node->getOpcode()) {
 708   default:
 709     Node->dump(); std::cerr << "\n";
 710     assert(0 && "Node not handled yet!");
 711   case ISD::EntryToken: return;  // Noop
 712   case ISD::TokenFactor:
 713     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 714       Select(Node->getOperand(i));
 715     return;
 716   case ISD::ADJCALLSTACKDOWN:
 717   case ISD::ADJCALLSTACKUP:
 718     Select(N.getOperand(0));
 719     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
 720     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? PPC::ADJCALLSTACKDOWN :
 721       PPC::ADJCALLSTACKUP;
 722     BuildMI(BB, Opc, 1).addImm(Tmp1);
 723     return;
 724   case ISD::BR: {
 725     MachineBasicBlock *Dest =
 726       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
 727     Select(N.getOperand(0));
 728     BuildMI(BB, PPC::B, 1).addMBB(Dest);
 729     return;
 730   }
 731   case ISD::BRCOND:
 732     SelectBranchCC(N);
 733     return;
 734   case ISD::CopyToReg:
 735     Select(N.getOperand(0));
 736     Tmp1 = SelectExpr(N.getOperand(1));
 737     Tmp2 = cast<RegSDNode>(N)->getReg();
 738
 739     if (Tmp1 != Tmp2) {
 740       if (N.getOperand(1).getValueType() == MVT::f64 ||
 741           N.getOperand(1).getValueType() == MVT::f32)
 742         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
 743       else
 744         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
 745     }
 746     return;
 747   case ISD::ImplicitDef:
 748     Select(N.getOperand(0));
 749     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
 750     return;
 751   case ISD::RET:
 752     switch (N.getNumOperands()) {
 753     default:
 754       assert(0 && "Unknown return instruction!");
 755     case 3:
 756       assert(N.getOperand(1).getValueType() == MVT::i32 &&
 757              N.getOperand(2).getValueType() == MVT::i32 &&
 758                    "Unknown two-register value!");
 759       Select(N.getOperand(0));
 760       Tmp1 = SelectExpr(N.getOperand(1));
 761       Tmp2 = SelectExpr(N.getOperand(2));
 762       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
 763       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp2).addReg(Tmp2);
 764       break;
 765     case 2:
 766       Select(N.getOperand(0));
 767       Tmp1 = SelectExpr(N.getOperand(1));
 768       switch (N.getOperand(1).getValueType()) {
 769         default:
 770           assert(0 && "Unknown return type!");
 771         case MVT::f64:
 772         case MVT::f32:
 773           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
 774           break;
 775         case MVT::i32:
 776           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
 777           break;
 778       }
 779     }
 780     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
 781     return;
 782   case ISD::TRUNCSTORE:
 783   case ISD::STORE:
 784     {
 785       SDOperand Chain   = N.getOperand(0);
 786       SDOperand Value   = N.getOperand(1);
 787       SDOperand Address = N.getOperand(2);
 788       Select(Chain);
 789
 790       Tmp1 = SelectExpr(Value); //value
 791
 792       if (opcode == ISD::STORE) {
 793         switch(Value.getValueType()) {
 794         default: assert(0 && "unknown Type in store");
 795         case MVT::i32: Opc = PPC::STW; break;
 796         case MVT::f64: Opc = PPC::STFD; break;
 797         case MVT::f32: Opc = PPC::STFS; break;
 798         }
 799       } else { //ISD::TRUNCSTORE
 800         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
 801         default: assert(0 && "unknown Type in store");
 802         case MVT::i1: //FIXME: DAG does not promote this load
 803         case MVT::i8: Opc  = PPC::STB; break;
 804         case MVT::i16: Opc = PPC::STH; break;
 805         }
 806       }
 807
 808       if (Address.getOpcode() == ISD::GlobalAddress)
 809       {
 810         BuildMI(BB, Opc, 2).addReg(Tmp1)
 811           .addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
 812       }
 813       else if(Address.getOpcode() == ISD::FrameIndex)
 814       {
 815         BuildMI(BB, Opc, 2).addReg(Tmp1)
 816           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex());
 817       }
 818       else
 819       {
 820         int offset;
 821         SelectAddr(Address, Tmp2, offset);
 822         BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
 823       }
 824       return;
 825     }
 826   case ISD::EXTLOAD:
 827   case ISD::SEXTLOAD:
 828   case ISD::ZEXTLOAD:
 829   case ISD::LOAD:
 830   case ISD::CopyFromReg:
 831   case ISD::CALL:
 832   case ISD::DYNAMIC_STACKALLOC:
 833     ExprMap.erase(N);
 834     SelectExpr(N);
 835     return;
 836   }
 837   assert(0 && "Should not be reached!");
 838 }
 839
 840
 841 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
 842 /// into a machine code representation using pattern matching and a machine
 843 /// description file.
 844 ///
 845 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
 846   return new ISel(TM);
 847 }
 848