lib/Target/PowerPC/PPCISelDAGToDAG.cpp

   1 //===-- PPC32ISelDAGToDAG.cpp - PPC32 pattern matching inst selector ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner 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 // converting from a legalized dag to a PPC dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "PowerPC.h"
  16 #include "PPC32TargetMachine.h"
  17 #include "PPC32ISelLowering.h"
  18 #include "llvm/CodeGen/MachineInstrBuilder.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/CodeGen/SelectionDAG.h"
  22 #include "llvm/CodeGen/SelectionDAGISel.h"
  23 #include "llvm/Target/TargetOptions.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/GlobalValue.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/MathExtras.h"
  29 using namespace llvm;
  30
  31 namespace {
  32   Statistic<> FusedFP ("ppc-codegen", "Number of fused fp operations");
  33   Statistic<> FrameOff("ppc-codegen", "Number of frame idx offsets collapsed");
  34
  35   //===--------------------------------------------------------------------===//
  36   /// PPC32DAGToDAGISel - PPC32 specific code to select PPC32 machine
  37   /// instructions for SelectionDAG operations.
  38   ///
  39   class PPC32DAGToDAGISel : public SelectionDAGISel {
  40     PPC32TargetLowering PPC32Lowering;
  41     unsigned GlobalBaseReg;
  42   public:
  43     PPC32DAGToDAGISel(TargetMachine &TM)
  44       : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM) {}
  45
  46     virtual bool runOnFunction(Function &Fn) {
  47       // Make sure we re-emit a set of the global base reg if necessary
  48       GlobalBaseReg = 0;
  49       return SelectionDAGISel::runOnFunction(Fn);
  50     }
  51
  52     /// getI32Imm - Return a target constant with the specified value, of type
  53     /// i32.
  54     inline SDOperand getI32Imm(unsigned Imm) {
  55       return CurDAG->getTargetConstant(Imm, MVT::i32);
  56     }
  57
  58     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
  59     /// base register.  Return the virtual register that holds this value.
  60     SDOperand getGlobalBaseReg();
  61
  62     // Select - Convert the specified operand from a target-independent to a
  63     // target-specific node if it hasn't already been changed.
  64     SDOperand Select(SDOperand Op);
  65
  66     SDNode *SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
  67                                    unsigned OCHi, unsigned OCLo,
  68                                    bool IsArithmetic = false,
  69                                    bool Negate = false);
  70     SDNode *SelectBitfieldInsert(SDNode *N);
  71
  72     /// SelectCC - Select a comparison of the specified values with the
  73     /// specified condition code, returning the CR# of the expression.
  74     SDOperand SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC);
  75
  76     /// SelectAddr - Given the specified address, return the two operands for a
  77     /// load/store instruction, and return true if it should be an indexed [r+r]
  78     /// operation.
  79     bool SelectAddr(SDOperand Addr, SDOperand &Op1, SDOperand &Op2);
  80
  81     SDOperand BuildSDIVSequence(SDNode *N);
  82     SDOperand BuildUDIVSequence(SDNode *N);
  83
  84     /// InstructionSelectBasicBlock - This callback is invoked by
  85     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  86     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
  87
  88     virtual const char *getPassName() const {
  89       return "PowerPC DAG->DAG Pattern Instruction Selection";
  90     }
  91
  92 // Include the pieces autogenerated from the target description.
  93 #include "PPC32GenDAGISel.inc"
  94
  95 private:
  96     SDOperand SelectDYNAMIC_STACKALLOC(SDOperand Op);
  97     SDOperand SelectADD_PARTS(SDOperand Op);
  98     SDOperand SelectSUB_PARTS(SDOperand Op);
  99     SDOperand SelectSETCC(SDOperand Op);
 100     SDOperand SelectCALL(SDOperand Op);
 101   };
 102 }
 103
 104 /// InstructionSelectBasicBlock - This callback is invoked by
 105 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 106 void PPC32DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 107   DEBUG(BB->dump());
 108
 109   // The selection process is inherently a bottom-up recursive process (users
 110   // select their uses before themselves).  Given infinite stack space, we
 111   // could just start selecting on the root and traverse the whole graph.  In
 112   // practice however, this causes us to run out of stack space on large basic
 113   // blocks.  To avoid this problem, select the entry node, then all its uses,
 114   // iteratively instead of recursively.
 115   std::vector<SDOperand> Worklist;
 116   Worklist.push_back(DAG.getEntryNode());
 117
 118   // Note that we can do this in the PPC target (scanning forward across token
 119   // chain edges) because no nodes ever get folded across these edges.  On a
 120   // target like X86 which supports load/modify/store operations, this would
 121   // have to be more careful.
 122   while (!Worklist.empty()) {
 123     SDOperand Node = Worklist.back();
 124     Worklist.pop_back();
 125
 126     // Chose from the least deep of the top two nodes.
 127     if (!Worklist.empty() &&
 128         Worklist.back().Val->getNodeDepth() < Node.Val->getNodeDepth())
 129       std::swap(Worklist.back(), Node);
 130
 131     if ((Node.Val->getOpcode() >= ISD::BUILTIN_OP_END &&
 132          Node.Val->getOpcode() < PPCISD::FIRST_NUMBER) ||
 133         CodeGenMap.count(Node)) continue;
 134
 135     for (SDNode::use_iterator UI = Node.Val->use_begin(),
 136          E = Node.Val->use_end(); UI != E; ++UI) {
 137       // Scan the values.  If this use has a value that is a token chain, add it
 138       // to the worklist.
 139       SDNode *User = *UI;
 140       for (unsigned i = 0, e = User->getNumValues(); i != e; ++i)
 141         if (User->getValueType(i) == MVT::Other) {
 142           Worklist.push_back(SDOperand(User, i));
 143           break;
 144         }
 145     }
 146
 147     // Finally, legalize this node.
 148     Select(Node);
 149   }
 150
 151   // Select target instructions for the DAG.
 152   DAG.setRoot(Select(DAG.getRoot()));
 153   CodeGenMap.clear();
 154   DAG.RemoveDeadNodes();
 155
 156   // Emit machine code to BB.
 157   ScheduleAndEmitDAG(DAG);
 158 }
 159
 160 /// getGlobalBaseReg - Output the instructions required to put the
 161 /// base address to use for accessing globals into a register.
 162 ///
 163 SDOperand PPC32DAGToDAGISel::getGlobalBaseReg() {
 164   if (!GlobalBaseReg) {
 165     // Insert the set of GlobalBaseReg into the first MBB of the function
 166     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 167     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 168     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 169     GlobalBaseReg = RegMap->createVirtualRegister(PPC32::GPRCRegisterClass);
 170     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 171     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg);
 172   }
 173   return CurDAG->getRegister(GlobalBaseReg, MVT::i32);
 174 }
 175
 176
 177 // isIntImmediate - This method tests to see if a constant operand.
 178 // If so Imm will receive the 32 bit value.
 179 static bool isIntImmediate(SDNode *N, unsigned& Imm) {
 180   if (N->getOpcode() == ISD::Constant) {
 181     Imm = cast<ConstantSDNode>(N)->getValue();
 182     return true;
 183   }
 184   return false;
 185 }
 186
 187 // isOprShiftImm - Returns true if the specified operand is a shift opcode with
 188 // a immediate shift count less than 32.
 189 static bool isOprShiftImm(SDNode *N, unsigned& Opc, unsigned& SH) {
 190   Opc = N->getOpcode();
 191   return (Opc == ISD::SHL || Opc == ISD::SRL || Opc == ISD::SRA) &&
 192     isIntImmediate(N->getOperand(1).Val, SH) && SH < 32;
 193 }
 194
 195 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
 196 // any number of 0s on either side.  The 1s are allowed to wrap from LSB to
 197 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 198 // not, since all 1s are not contiguous.
 199 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 200   if (isShiftedMask_32(Val)) {
 201     // look for the first non-zero bit
 202     MB = CountLeadingZeros_32(Val);
 203     // look for the first zero bit after the run of ones
 204     ME = CountLeadingZeros_32((Val - 1) ^ Val);
 205     return true;
 206   } else {
 207     Val = ~Val; // invert mask
 208     if (isShiftedMask_32(Val)) {
 209       // effectively look for the first zero bit
 210       ME = CountLeadingZeros_32(Val) - 1;
 211       // effectively look for the first one bit after the run of zeros
 212       MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
 213       return true;
 214     }
 215   }
 216   // no run present
 217   return false;
 218 }
 219
 220 // isRotateAndMask - Returns true if Mask and Shift can be folded in to a rotate
 221 // and mask opcode and mask operation.
 222 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
 223                             unsigned &SH, unsigned &MB, unsigned &ME) {
 224   unsigned Shift  = 32;
 225   unsigned Indeterminant = ~0;  // bit mask marking indeterminant results
 226   unsigned Opcode = N->getOpcode();
 227   if (N->getNumOperands() != 2 ||
 228       !isIntImmediate(N->getOperand(1).Val, Shift) || (Shift > 31))
 229     return false;
 230
 231   if (Opcode == ISD::SHL) {
 232     // apply shift left to mask if it comes first
 233     if (IsShiftMask) Mask = Mask << Shift;
 234     // determine which bits are made indeterminant by shift
 235     Indeterminant = ~(0xFFFFFFFFu << Shift);
 236   } else if (Opcode == ISD::SRA || Opcode == ISD::SRL) {
 237     // apply shift right to mask if it comes first
 238     if (IsShiftMask) Mask = Mask >> Shift;
 239     // determine which bits are made indeterminant by shift
 240     Indeterminant = ~(0xFFFFFFFFu >> Shift);
 241     // adjust for the left rotate
 242     Shift = 32 - Shift;
 243   } else {
 244     return false;
 245   }
 246
 247   // if the mask doesn't intersect any Indeterminant bits
 248   if (Mask && !(Mask & Indeterminant)) {
 249     SH = Shift;
 250     // make sure the mask is still a mask (wrap arounds may not be)
 251     return isRunOfOnes(Mask, MB, ME);
 252   }
 253   return false;
 254 }
 255
 256 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 257 // opcode and that it has a immediate integer right operand.
 258 // If so Imm will receive the 32 bit value.
 259 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
 260   return N->getOpcode() == Opc && isIntImmediate(N->getOperand(1).Val, Imm);
 261 }
 262
 263 // isOprNot - Returns true if the specified operand is an xor with immediate -1.
 264 static bool isOprNot(SDNode *N) {
 265   unsigned Imm;
 266   return isOpcWithIntImmediate(N, ISD::XOR, Imm) && (signed)Imm == -1;
 267 }
 268
 269 // Immediate constant composers.
 270 // Lo16 - grabs the lo 16 bits from a 32 bit constant.
 271 // Hi16 - grabs the hi 16 bits from a 32 bit constant.
 272 // HA16 - computes the hi bits required if the lo bits are add/subtracted in
 273 // arithmethically.
 274 static unsigned Lo16(unsigned x)  { return x & 0x0000FFFF; }
 275 static unsigned Hi16(unsigned x)  { return Lo16(x >> 16); }
 276 static unsigned HA16(unsigned x)  { return Hi16((signed)x - (signed short)x); }
 277
 278 // isIntImmediate - This method tests to see if a constant operand.
 279 // If so Imm will receive the 32 bit value.
 280 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
 281   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 282     Imm = (unsigned)CN->getSignExtended();
 283     return true;
 284   }
 285   return false;
 286 }
 287
 288 /// SelectBitfieldInsert - turn an or of two masked values into
 289 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 290 /// Returns true on success, false if the caller still needs to select OR.
 291 ///
 292 /// Patterns matched:
 293 /// 1. or shl, and   5. or and, and
 294 /// 2. or and, shl   6. or shl, shr
 295 /// 3. or shr, and   7. or shr, shl
 296 /// 4. or and, shr
 297 SDNode *PPC32DAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
 298   bool IsRotate = false;
 299   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, SH = 0;
 300   unsigned Value;
 301
 302   SDOperand Op0 = N->getOperand(0);
 303   SDOperand Op1 = N->getOperand(1);
 304
 305   unsigned Op0Opc = Op0.getOpcode();
 306   unsigned Op1Opc = Op1.getOpcode();
 307
 308   // Verify that we have the correct opcodes
 309   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
 310     return false;
 311   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
 312     return false;
 313
 314   // Generate Mask value for Target
 315   if (isIntImmediate(Op0.getOperand(1), Value)) {
 316     switch(Op0Opc) {
 317     case ISD::SHL: TgtMask <<= Value; break;
 318     case ISD::SRL: TgtMask >>= Value; break;
 319     case ISD::AND: TgtMask &= Value; break;
 320     }
 321   } else {
 322     return 0;
 323   }
 324
 325   // Generate Mask value for Insert
 326   if (!isIntImmediate(Op1.getOperand(1), Value))
 327     return 0;
 328
 329   switch(Op1Opc) {
 330   case ISD::SHL:
 331     SH = Value;
 332     InsMask <<= SH;
 333     if (Op0Opc == ISD::SRL) IsRotate = true;
 334     break;
 335   case ISD::SRL:
 336     SH = Value;
 337     InsMask >>= SH;
 338     SH = 32-SH;
 339     if (Op0Opc == ISD::SHL) IsRotate = true;
 340     break;
 341   case ISD::AND:
 342     InsMask &= Value;
 343     break;
 344   }
 345
 346   // If both of the inputs are ANDs and one of them has a logical shift by
 347   // constant as its input, make that AND the inserted value so that we can
 348   // combine the shift into the rotate part of the rlwimi instruction
 349   bool IsAndWithShiftOp = false;
 350   if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 351     if (Op1.getOperand(0).getOpcode() == ISD::SHL ||
 352         Op1.getOperand(0).getOpcode() == ISD::SRL) {
 353       if (isIntImmediate(Op1.getOperand(0).getOperand(1), Value)) {
 354         SH = Op1.getOperand(0).getOpcode() == ISD::SHL ? Value : 32 - Value;
 355         IsAndWithShiftOp = true;
 356       }
 357     } else if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 358                Op0.getOperand(0).getOpcode() == ISD::SRL) {
 359       if (isIntImmediate(Op0.getOperand(0).getOperand(1), Value)) {
 360         std::swap(Op0, Op1);
 361         std::swap(TgtMask, InsMask);
 362         SH = Op1.getOperand(0).getOpcode() == ISD::SHL ? Value : 32 - Value;
 363         IsAndWithShiftOp = true;
 364       }
 365     }
 366   }
 367
 368   // Verify that the Target mask and Insert mask together form a full word mask
 369   // and that the Insert mask is a run of set bits (which implies both are runs
 370   // of set bits).  Given that, Select the arguments and generate the rlwimi
 371   // instruction.
 372   unsigned MB, ME;
 373   if (((TgtMask & InsMask) == 0) && isRunOfOnes(InsMask, MB, ME)) {
 374     bool fullMask = (TgtMask ^ InsMask) == 0xFFFFFFFF;
 375     bool Op0IsAND = Op0Opc == ISD::AND;
 376     // Check for rotlwi / rotrwi here, a special case of bitfield insert
 377     // where both bitfield halves are sourced from the same value.
 378     if (IsRotate && fullMask &&
 379         N->getOperand(0).getOperand(0) == N->getOperand(1).getOperand(0)) {
 380       Op0 = CurDAG->getTargetNode(PPC::RLWINM, MVT::i32,
 381                                   Select(N->getOperand(0).getOperand(0)),
 382                                   getI32Imm(SH), getI32Imm(0), getI32Imm(31));
 383       return Op0.Val;
 384     }
 385     SDOperand Tmp1 = (Op0IsAND && fullMask) ? Select(Op0.getOperand(0))
 386                                             : Select(Op0);
 387     SDOperand Tmp2 = IsAndWithShiftOp ? Select(Op1.getOperand(0).getOperand(0))
 388                                       : Select(Op1.getOperand(0));
 389     Op0 = CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Tmp1, Tmp2,
 390                                 getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
 391     return Op0.Val;
 392   }
 393   return 0;
 394 }
 395
 396 // SelectIntImmediateExpr - Choose code for integer operations with an immediate
 397 // operand.
 398 SDNode *PPC32DAGToDAGISel::SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
 399                                                   unsigned OCHi, unsigned OCLo,
 400                                                   bool IsArithmetic,
 401                                                   bool Negate) {
 402   // Check to make sure this is a constant.
 403   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS);
 404   // Exit if not a constant.
 405   if (!CN) return 0;
 406   // Extract immediate.
 407   unsigned C = (unsigned)CN->getValue();
 408   // Negate if required (ISD::SUB).
 409   if (Negate) C = -C;
 410   // Get the hi and lo portions of constant.
 411   unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
 412   unsigned Lo = Lo16(C);
 413
 414   // If two instructions are needed and usage indicates it would be better to
 415   // load immediate into a register, bail out.
 416   if (Hi && Lo && CN->use_size() > 2) return false;
 417
 418   // Select the first operand.
 419   SDOperand Opr0 = Select(LHS);
 420
 421   if (Lo)  // Add in the lo-part.
 422     Opr0 = CurDAG->getTargetNode(OCLo, MVT::i32, Opr0, getI32Imm(Lo));
 423   if (Hi)  // Add in the hi-part.
 424     Opr0 = CurDAG->getTargetNode(OCHi, MVT::i32, Opr0, getI32Imm(Hi));
 425   return Opr0.Val;
 426 }
 427
 428 /// SelectAddr - Given the specified address, return the two operands for a
 429 /// load/store instruction, and return true if it should be an indexed [r+r]
 430 /// operation.
 431 bool PPC32DAGToDAGISel::SelectAddr(SDOperand Addr, SDOperand &Op1,
 432                                    SDOperand &Op2) {
 433   unsigned imm = 0;
 434   if (Addr.getOpcode() == ISD::ADD) {
 435     if (isIntImmediate(Addr.getOperand(1), imm) && isInt16(imm)) {
 436       Op1 = getI32Imm(Lo16(imm));
 437       if (FrameIndexSDNode *FI =
 438             dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) {
 439         ++FrameOff;
 440         Op2 = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
 441       } else {
 442         Op2 = Select(Addr.getOperand(0));
 443       }
 444       return false;
 445     } else {
 446       Op1 = Select(Addr.getOperand(0));
 447       Op2 = Select(Addr.getOperand(1));
 448       return true;   // [r+r]
 449     }
 450   }
 451
 452   // Now check if we're dealing with a global, and whether or not we should emit
 453   // an optimized load or store for statics.
 454   if (GlobalAddressSDNode *GN = dyn_cast<GlobalAddressSDNode>(Addr)) {
 455     GlobalValue *GV = GN->getGlobal();
 456     if (!GV->hasWeakLinkage() && !GV->isExternal()) {
 457       Op1 = CurDAG->getTargetGlobalAddress(GV, MVT::i32);
 458       if (PICEnabled)
 459         Op2 = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),
 460                                     Op1);
 461       else
 462         Op2 = CurDAG->getTargetNode(PPC::LIS, MVT::i32, Op1);
 463       return false;
 464     }
 465   } else if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Addr)) {
 466     Op1 = getI32Imm(0);
 467     Op2 = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
 468     return false;
 469   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Addr)) {
 470     Op1 = Addr;
 471     if (PICEnabled)
 472       Op2 = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),Op1);
 473     else
 474       Op2 = CurDAG->getTargetNode(PPC::LIS, MVT::i32, Op1);
 475     return false;
 476   }
 477   Op1 = getI32Imm(0);
 478   Op2 = Select(Addr);
 479   return false;
 480 }
 481
 482 /// SelectCC - Select a comparison of the specified values with the specified
 483 /// condition code, returning the CR# of the expression.
 484 SDOperand PPC32DAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
 485                                       ISD::CondCode CC) {
 486   // Always select the LHS.
 487   LHS = Select(LHS);
 488
 489   // Use U to determine whether the SETCC immediate range is signed or not.
 490   if (MVT::isInteger(LHS.getValueType())) {
 491     bool U = ISD::isUnsignedIntSetCC(CC);
 492     unsigned Imm;
 493     if (isIntImmediate(RHS, Imm) &&
 494         ((U && isUInt16(Imm)) || (!U && isInt16(Imm))))
 495       return CurDAG->getTargetNode(U ? PPC::CMPLWI : PPC::CMPWI, MVT::i32,
 496                                    LHS, getI32Imm(Lo16(Imm)));
 497     return CurDAG->getTargetNode(U ? PPC::CMPLW : PPC::CMPW, MVT::i32,
 498                                  LHS, Select(RHS));
 499   } else if (LHS.getValueType() == MVT::f32) {
 500     return CurDAG->getTargetNode(PPC::FCMPUS, MVT::i32, LHS, Select(RHS));
 501   } else {
 502     return CurDAG->getTargetNode(PPC::FCMPUD, MVT::i32, LHS, Select(RHS));
 503   }
 504 }
 505
 506 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 507 /// to Condition.
 508 static unsigned getBCCForSetCC(ISD::CondCode CC) {
 509   switch (CC) {
 510   default: assert(0 && "Unknown condition!"); abort();
 511   case ISD::SETEQ:  return PPC::BEQ;
 512   case ISD::SETNE:  return PPC::BNE;
 513   case ISD::SETULT:
 514   case ISD::SETLT:  return PPC::BLT;
 515   case ISD::SETULE:
 516   case ISD::SETLE:  return PPC::BLE;
 517   case ISD::SETUGT:
 518   case ISD::SETGT:  return PPC::BGT;
 519   case ISD::SETUGE:
 520   case ISD::SETGE:  return PPC::BGE;
 521   }
 522   return 0;
 523 }
 524
 525 /// getCRIdxForSetCC - Return the index of the condition register field
 526 /// associated with the SetCC condition, and whether or not the field is
 527 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 528 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool& Inv) {
 529   switch (CC) {
 530   default: assert(0 && "Unknown condition!"); abort();
 531   case ISD::SETULT:
 532   case ISD::SETLT:  Inv = false;  return 0;
 533   case ISD::SETUGE:
 534   case ISD::SETGE:  Inv = true;   return 0;
 535   case ISD::SETUGT:
 536   case ISD::SETGT:  Inv = false;  return 1;
 537   case ISD::SETULE:
 538   case ISD::SETLE:  Inv = true;   return 1;
 539   case ISD::SETEQ:  Inv = false;  return 2;
 540   case ISD::SETNE:  Inv = true;   return 2;
 541   }
 542   return 0;
 543 }
 544
 545 // Structure used to return the necessary information to codegen an SDIV as
 546 // a multiply.
 547 struct ms {
 548   int m; // magic number
 549   int s; // shift amount
 550 };
 551
 552 struct mu {
 553   unsigned int m; // magic number
 554   int a;          // add indicator
 555   int s;          // shift amount
 556 };
 557
 558 /// magic - calculate the magic numbers required to codegen an integer sdiv as
 559 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
 560 /// or -1.
 561 static struct ms magic(int d) {
 562   int p;
 563   unsigned int ad, anc, delta, q1, r1, q2, r2, t;
 564   const unsigned int two31 = 0x80000000U;
 565   struct ms mag;
 566
 567   ad = abs(d);
 568   t = two31 + ((unsigned int)d >> 31);
 569   anc = t - 1 - t%ad;   // absolute value of nc
 570   p = 31;               // initialize p
 571   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
 572   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
 573   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
 574   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
 575   do {
 576     p = p + 1;
 577     q1 = 2*q1;        // update q1 = 2p/abs(nc)
 578     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
 579     if (r1 >= anc) {  // must be unsigned comparison
 580       q1 = q1 + 1;
 581       r1 = r1 - anc;
 582     }
 583     q2 = 2*q2;        // update q2 = 2p/abs(d)
 584     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
 585     if (r2 >= ad) {   // must be unsigned comparison
 586       q2 = q2 + 1;
 587       r2 = r2 - ad;
 588     }
 589     delta = ad - r2;
 590   } while (q1 < delta || (q1 == delta && r1 == 0));
 591
 592   mag.m = q2 + 1;
 593   if (d < 0) mag.m = -mag.m; // resulting magic number
 594   mag.s = p - 32;            // resulting shift
 595   return mag;
 596 }
 597
 598 /// magicu - calculate the magic numbers required to codegen an integer udiv as
 599 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
 600 static struct mu magicu(unsigned d)
 601 {
 602   int p;
 603   unsigned int nc, delta, q1, r1, q2, r2;
 604   struct mu magu;
 605   magu.a = 0;               // initialize "add" indicator
 606   nc = - 1 - (-d)%d;
 607   p = 31;                   // initialize p
 608   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
 609   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
 610   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
 611   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
 612   do {
 613     p = p + 1;
 614     if (r1 >= nc - r1 ) {
 615       q1 = 2*q1 + 1;  // update q1
 616       r1 = 2*r1 - nc; // update r1
 617     }
 618     else {
 619       q1 = 2*q1; // update q1
 620       r1 = 2*r1; // update r1
 621     }
 622     if (r2 + 1 >= d - r2) {
 623       if (q2 >= 0x7FFFFFFF) magu.a = 1;
 624       q2 = 2*q2 + 1;     // update q2
 625       r2 = 2*r2 + 1 - d; // update r2
 626     }
 627     else {
 628       if (q2 >= 0x80000000) magu.a = 1;
 629       q2 = 2*q2;     // update q2
 630       r2 = 2*r2 + 1; // update r2
 631     }
 632     delta = d - 1 - r2;
 633   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
 634   magu.m = q2 + 1; // resulting magic number
 635   magu.s = p - 32;  // resulting shift
 636   return magu;
 637 }
 638
 639 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
 640 /// return a DAG expression to select that will generate the same value by
 641 /// multiplying by a magic number.  See:
 642 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 643 SDOperand PPC32DAGToDAGISel::BuildSDIVSequence(SDNode *N) {
 644   int d = (int)cast<ConstantSDNode>(N->getOperand(1))->getValue();
 645   ms magics = magic(d);
 646   // Multiply the numerator (operand 0) by the magic value
 647   SDOperand Q = CurDAG->getNode(ISD::MULHS, MVT::i32, N->getOperand(0),
 648                                 CurDAG->getConstant(magics.m, MVT::i32));
 649   // If d > 0 and m < 0, add the numerator
 650   if (d > 0 && magics.m < 0)
 651     Q = CurDAG->getNode(ISD::ADD, MVT::i32, Q, N->getOperand(0));
 652   // If d < 0 and m > 0, subtract the numerator.
 653   if (d < 0 && magics.m > 0)
 654     Q = CurDAG->getNode(ISD::SUB, MVT::i32, Q, N->getOperand(0));
 655   // Shift right algebraic if shift value is nonzero
 656   if (magics.s > 0)
 657     Q = CurDAG->getNode(ISD::SRA, MVT::i32, Q,
 658                         CurDAG->getConstant(magics.s, MVT::i32));
 659   // Extract the sign bit and add it to the quotient
 660   SDOperand T =
 661     CurDAG->getNode(ISD::SRL, MVT::i32, Q, CurDAG->getConstant(31, MVT::i32));
 662   return CurDAG->getNode(ISD::ADD, MVT::i32, Q, T);
 663 }
 664
 665 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
 666 /// return a DAG expression to select that will generate the same value by
 667 /// multiplying by a magic number.  See:
 668 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 669 SDOperand PPC32DAGToDAGISel::BuildUDIVSequence(SDNode *N) {
 670   unsigned d = (unsigned)cast<ConstantSDNode>(N->getOperand(1))->getValue();
 671   mu magics = magicu(d);
 672   // Multiply the numerator (operand 0) by the magic value
 673   SDOperand Q = CurDAG->getNode(ISD::MULHU, MVT::i32, N->getOperand(0),
 674                                 CurDAG->getConstant(magics.m, MVT::i32));
 675   if (magics.a == 0) {
 676     return CurDAG->getNode(ISD::SRL, MVT::i32, Q,
 677                            CurDAG->getConstant(magics.s, MVT::i32));
 678   } else {
 679     SDOperand NPQ = CurDAG->getNode(ISD::SUB, MVT::i32, N->getOperand(0), Q);
 680     NPQ = CurDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 681                            CurDAG->getConstant(1, MVT::i32));
 682     NPQ = CurDAG->getNode(ISD::ADD, MVT::i32, NPQ, Q);
 683     return CurDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 684                            CurDAG->getConstant(magics.s-1, MVT::i32));
 685   }
 686 }
 687
 688 SDOperand PPC32DAGToDAGISel::SelectDYNAMIC_STACKALLOC(SDOperand Op) {
 689   SDNode *N = Op.Val;
 690
 691   // FIXME: We are currently ignoring the requested alignment for handling
 692   // greater than the stack alignment.  This will need to be revisited at some
 693   // point.  Align = N.getOperand(2);
 694   if (!isa<ConstantSDNode>(N->getOperand(2)) ||
 695       cast<ConstantSDNode>(N->getOperand(2))->getValue() != 0) {
 696     std::cerr << "Cannot allocate stack object with greater alignment than"
 697     << " the stack alignment yet!";
 698     abort();
 699   }
 700   SDOperand Chain = Select(N->getOperand(0));
 701   SDOperand Amt   = Select(N->getOperand(1));
 702
 703   SDOperand R1Reg = CurDAG->getRegister(PPC::R1, MVT::i32);
 704
 705   SDOperand R1Val = CurDAG->getCopyFromReg(Chain, PPC::R1, MVT::i32);
 706   Chain = R1Val.getValue(1);
 707
 708   // Subtract the amount (guaranteed to be a multiple of the stack alignment)
 709   // from the stack pointer, giving us the result pointer.
 710   SDOperand Result = CurDAG->getTargetNode(PPC::SUBF, MVT::i32, Amt, R1Val);
 711
 712   // Copy this result back into R1.
 713   Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, R1Reg, Result);
 714
 715   // Copy this result back out of R1 to make sure we're not using the stack
 716   // space without decrementing the stack pointer.
 717   Result = CurDAG->getCopyFromReg(Chain, PPC::R1, MVT::i32);
 718
 719   // Finally, replace the DYNAMIC_STACKALLOC with the copyfromreg.
 720   CodeGenMap[Op.getValue(0)] = Result;
 721   CodeGenMap[Op.getValue(1)] = Result.getValue(1);
 722   return SDOperand(Result.Val, Op.ResNo);
 723 }
 724
 725 SDOperand PPC32DAGToDAGISel::SelectADD_PARTS(SDOperand Op) {
 726   SDNode *N = Op.Val;
 727   SDOperand LHSL = Select(N->getOperand(0));
 728   SDOperand LHSH = Select(N->getOperand(1));
 729
 730   unsigned Imm;
 731   bool ME = false, ZE = false;
 732   if (isIntImmediate(N->getOperand(3), Imm)) {
 733     ME = (signed)Imm == -1;
 734     ZE = Imm == 0;
 735   }
 736
 737   std::vector<SDOperand> Result;
 738   SDOperand CarryFromLo;
 739   if (isIntImmediate(N->getOperand(2), Imm) &&
 740       ((signed)Imm >= -32768 || (signed)Imm < 32768)) {
 741     // Codegen the low 32 bits of the add.  Interestingly, there is no
 742     // shifted form of add immediate carrying.
 743     CarryFromLo = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 744                                         LHSL, getI32Imm(Imm));
 745   } else {
 746     CarryFromLo = CurDAG->getTargetNode(PPC::ADDC, MVT::i32, MVT::Flag,
 747                                         LHSL, Select(N->getOperand(2)));
 748   }
 749   CarryFromLo = CarryFromLo.getValue(1);
 750
 751   // Codegen the high 32 bits, adding zero, minus one, or the full value
 752   // along with the carry flag produced by addc/addic.
 753   SDOperand ResultHi;
 754   if (ZE)
 755     ResultHi = CurDAG->getTargetNode(PPC::ADDZE, MVT::i32, LHSH, CarryFromLo);
 756   else if (ME)
 757     ResultHi = CurDAG->getTargetNode(PPC::ADDME, MVT::i32, LHSH, CarryFromLo);
 758   else
 759     ResultHi = CurDAG->getTargetNode(PPC::ADDE, MVT::i32, LHSH,
 760                                      Select(N->getOperand(3)), CarryFromLo);
 761   Result.push_back(CarryFromLo.getValue(0));
 762   Result.push_back(ResultHi);
 763
 764   CodeGenMap[Op.getValue(0)] = Result[0];
 765   CodeGenMap[Op.getValue(1)] = Result[1];
 766   return Result[Op.ResNo];
 767 }
 768 SDOperand PPC32DAGToDAGISel::SelectSUB_PARTS(SDOperand Op) {
 769   SDNode *N = Op.Val;
 770   SDOperand LHSL = Select(N->getOperand(0));
 771   SDOperand LHSH = Select(N->getOperand(1));
 772   SDOperand RHSL = Select(N->getOperand(2));
 773   SDOperand RHSH = Select(N->getOperand(3));
 774
 775   std::vector<SDOperand> Result;
 776   Result.push_back(CurDAG->getTargetNode(PPC::SUBFC, MVT::i32, MVT::Flag,
 777                                          RHSL, LHSL));
 778   Result.push_back(CurDAG->getTargetNode(PPC::SUBFE, MVT::i32, RHSH, LHSH,
 779                                          Result[0].getValue(1)));
 780   CodeGenMap[Op.getValue(0)] = Result[0];
 781   CodeGenMap[Op.getValue(1)] = Result[1];
 782   return Result[Op.ResNo];
 783 }
 784
 785 SDOperand PPC32DAGToDAGISel::SelectSETCC(SDOperand Op) {
 786   SDNode *N = Op.Val;
 787   unsigned Imm;
 788   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
 789   if (isIntImmediate(N->getOperand(1), Imm)) {
 790     // We can codegen setcc op, imm very efficiently compared to a brcond.
 791     // Check for those cases here.
 792     // setcc op, 0
 793     if (Imm == 0) {
 794       SDOperand Op = Select(N->getOperand(0));
 795       switch (CC) {
 796         default: assert(0 && "Unhandled SetCC condition"); abort();
 797         case ISD::SETEQ:
 798           Op = CurDAG->getTargetNode(PPC::CNTLZW, MVT::i32, Op);
 799           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(27),
 800                                getI32Imm(5), getI32Imm(31));
 801           break;
 802         case ISD::SETNE: {
 803           SDOperand AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 804                                                Op, getI32Imm(~0U));
 805           CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op, AD.getValue(1));
 806           break;
 807         }
 808         case ISD::SETLT:
 809           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(1),
 810                                getI32Imm(31), getI32Imm(31));
 811           break;
 812         case ISD::SETGT: {
 813           SDOperand T = CurDAG->getTargetNode(PPC::NEG, MVT::i32, Op);
 814           T = CurDAG->getTargetNode(PPC::ANDC, MVT::i32, T, Op);;
 815           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, T, getI32Imm(1),
 816                                getI32Imm(31), getI32Imm(31));
 817           break;
 818         }
 819       }
 820       return SDOperand(N, 0);
 821     } else if (Imm == ~0U) {        // setcc op, -1
 822       SDOperand Op = Select(N->getOperand(0));
 823       switch (CC) {
 824         default: assert(0 && "Unhandled SetCC condition"); abort();
 825         case ISD::SETEQ:
 826           Op = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 827                                      Op, getI32Imm(1));
 828           CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 829                                CurDAG->getTargetNode(PPC::LI, MVT::i32,
 830                                                      getI32Imm(0)),
 831                                Op.getValue(1));
 832           break;
 833         case ISD::SETNE: {
 834           Op = CurDAG->getTargetNode(PPC::NOR, MVT::i32, Op, Op);
 835           SDOperand AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 836                                                Op, getI32Imm(~0U));
 837           CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op, AD.getValue(1));
 838           break;
 839         }
 840         case ISD::SETLT: {
 841           SDOperand AD = CurDAG->getTargetNode(PPC::ADDI, MVT::i32, Op,
 842                                                getI32Imm(1));
 843           SDOperand AN = CurDAG->getTargetNode(PPC::AND, MVT::i32, AD, Op);
 844           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, AN, getI32Imm(1),
 845                                getI32Imm(31), getI32Imm(31));
 846           break;
 847         }
 848         case ISD::SETGT:
 849           Op = CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Op, getI32Imm(1),
 850                                      getI32Imm(31), getI32Imm(31));
 851           CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op, getI32Imm(1));
 852           break;
 853       }
 854       return SDOperand(N, 0);
 855     }
 856   }
 857
 858   bool Inv;
 859   unsigned Idx = getCRIdxForSetCC(CC, Inv);
 860   SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
 861   SDOperand IntCR;
 862
 863   // Force the ccreg into CR7.
 864   SDOperand CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
 865
 866   std::vector<MVT::ValueType> VTs;
 867   VTs.push_back(MVT::Other);
 868   VTs.push_back(MVT::Flag);    // NONSTANDARD CopyToReg node: defines a flag
 869   std::vector<SDOperand> Ops;
 870   Ops.push_back(CurDAG->getEntryNode());
 871   Ops.push_back(CR7Reg);
 872   Ops.push_back(CCReg);
 873   CCReg = CurDAG->getNode(ISD::CopyToReg, VTs, Ops).getValue(1);
 874
 875   if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
 876     IntCR = CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32, CR7Reg, CCReg);
 877   else
 878     IntCR = CurDAG->getTargetNode(PPC::MFCR, MVT::i32, CCReg);
 879
 880   if (!Inv) {
 881     CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, IntCR,
 882                          getI32Imm(32-(3-Idx)), getI32Imm(31), getI32Imm(31));
 883   } else {
 884     SDOperand Tmp =
 885     CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, IntCR,
 886                           getI32Imm(32-(3-Idx)), getI32Imm(31),getI32Imm(31));
 887     CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1));
 888   }
 889
 890   return SDOperand(N, 0);
 891 }
 892
 893 SDOperand PPC32DAGToDAGISel::SelectCALL(SDOperand Op) {
 894   SDNode *N = Op.Val;
 895   SDOperand Chain = Select(N->getOperand(0));
 896
 897   unsigned CallOpcode;
 898   std::vector<SDOperand> CallOperands;
 899
 900   if (GlobalAddressSDNode *GASD =
 901       dyn_cast<GlobalAddressSDNode>(N->getOperand(1))) {
 902     CallOpcode = PPC::CALLpcrel;
 903     CallOperands.push_back(CurDAG->getTargetGlobalAddress(GASD->getGlobal(),
 904                                                           MVT::i32));
 905   } else if (ExternalSymbolSDNode *ESSDN =
 906              dyn_cast<ExternalSymbolSDNode>(N->getOperand(1))) {
 907     CallOpcode = PPC::CALLpcrel;
 908     CallOperands.push_back(N->getOperand(1));
 909   } else {
 910     // Copy the callee address into the CTR register.
 911     SDOperand Callee = Select(N->getOperand(1));
 912     Chain = CurDAG->getTargetNode(PPC::MTCTR, MVT::Other, Callee, Chain);
 913
 914     // Copy the callee address into R12 on darwin.
 915     SDOperand R12 = CurDAG->getRegister(PPC::R12, MVT::i32);
 916     Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, R12, Callee);
 917
 918     CallOperands.push_back(getI32Imm(20));  // Information to encode indcall
 919     CallOperands.push_back(getI32Imm(0));   // Information to encode indcall
 920     CallOperands.push_back(R12);
 921     CallOpcode = PPC::CALLindirect;
 922   }
 923
 924   unsigned GPR_idx = 0, FPR_idx = 0;
 925   static const unsigned GPR[] = {
 926     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 927     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 928   };
 929   static const unsigned FPR[] = {
 930     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 931     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 932   };
 933
 934   SDOperand InFlag;  // Null incoming flag value.
 935
 936   for (unsigned i = 2, e = N->getNumOperands(); i != e; ++i) {
 937     unsigned DestReg = 0;
 938     MVT::ValueType RegTy = N->getOperand(i).getValueType();
 939     if (RegTy == MVT::i32) {
 940       assert(GPR_idx < 8 && "Too many int args");
 941       DestReg = GPR[GPR_idx++];
 942     } else {
 943       assert(MVT::isFloatingPoint(N->getOperand(i).getValueType()) &&
 944              "Unpromoted integer arg?");
 945       assert(FPR_idx < 13 && "Too many fp args");
 946       DestReg = FPR[FPR_idx++];
 947     }
 948
 949     if (N->getOperand(i).getOpcode() != ISD::UNDEF) {
 950       SDOperand Val = Select(N->getOperand(i));
 951       Chain = CurDAG->getCopyToReg(Chain, DestReg, Val, InFlag);
 952       InFlag = Chain.getValue(1);
 953       CallOperands.push_back(CurDAG->getRegister(DestReg, RegTy));
 954     }
 955   }
 956
 957   // Finally, once everything is in registers to pass to the call, emit the
 958   // call itself.
 959   if (InFlag.Val)
 960     CallOperands.push_back(InFlag);   // Strong dep on register copies.
 961   else
 962     CallOperands.push_back(Chain);    // Weak dep on whatever occurs before
 963   Chain = CurDAG->getTargetNode(CallOpcode, MVT::Other, MVT::Flag,
 964                                 CallOperands);
 965
 966   std::vector<SDOperand> CallResults;
 967
 968   // If the call has results, copy the values out of the ret val registers.
 969   switch (N->getValueType(0)) {
 970     default: assert(0 && "Unexpected ret value!");
 971     case MVT::Other: break;
 972     case MVT::i32:
 973       if (N->getValueType(1) == MVT::i32) {
 974         Chain = CurDAG->getCopyFromReg(Chain, PPC::R4, MVT::i32,
 975                                        Chain.getValue(1)).getValue(1);
 976         CallResults.push_back(Chain.getValue(0));
 977         Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32,
 978                                        Chain.getValue(2)).getValue(1);
 979         CallResults.push_back(Chain.getValue(0));
 980       } else {
 981         Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32,
 982                                        Chain.getValue(1)).getValue(1);
 983         CallResults.push_back(Chain.getValue(0));
 984       }
 985       break;
 986     case MVT::f32:
 987     case MVT::f64:
 988       Chain = CurDAG->getCopyFromReg(Chain, PPC::F1, N->getValueType(0),
 989                                      Chain.getValue(1)).getValue(1);
 990       CallResults.push_back(Chain.getValue(0));
 991       break;
 992   }
 993
 994   CallResults.push_back(Chain);
 995   for (unsigned i = 0, e = CallResults.size(); i != e; ++i)
 996     CodeGenMap[Op.getValue(i)] = CallResults[i];
 997   return CallResults[Op.ResNo];
 998 }
 999
1000 // Select - Convert the specified operand from a target-independent to a
1001 // target-specific node if it hasn't already been changed.
1002 SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
1003   SDNode *N = Op.Val;
1004   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
1005       N->getOpcode() < PPCISD::FIRST_NUMBER)
1006     return Op;   // Already selected.
1007
1008   // If this has already been converted, use it.
1009   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
1010   if (CGMI != CodeGenMap.end()) return CGMI->second;
1011
1012   switch (N->getOpcode()) {
1013   default: break;
1014   case ISD::DYNAMIC_STACKALLOC: return SelectDYNAMIC_STACKALLOC(Op);
1015   case ISD::ADD_PARTS:          return SelectADD_PARTS(Op);
1016   case ISD::SUB_PARTS:          return SelectSUB_PARTS(Op);
1017   case ISD::SETCC:              return SelectSETCC(Op);
1018   case ISD::CALL:               return SelectCALL(Op);
1019   case ISD::TAILCALL:           return SelectCALL(Op);
1020
1021   case ISD::TokenFactor: {
1022     SDOperand New;
1023     if (N->getNumOperands() == 2) {
1024       SDOperand Op0 = Select(N->getOperand(0));
1025       SDOperand Op1 = Select(N->getOperand(1));
1026       New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);
1027     } else {
1028       std::vector<SDOperand> Ops;
1029       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1030         Ops.push_back(Select(N->getOperand(i)));
1031       New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);
1032     }
1033
1034     CodeGenMap[Op] = New;
1035     return New;
1036   }
1037   case ISD::CopyFromReg: {
1038     SDOperand Chain = Select(N->getOperand(0));
1039     if (Chain == N->getOperand(0)) return Op; // No change
1040     SDOperand New = CurDAG->getCopyFromReg(Chain,
1041          cast<RegisterSDNode>(N->getOperand(1))->getReg(), N->getValueType(0));
1042     return New.getValue(Op.ResNo);
1043   }
1044   case ISD::CopyToReg: {
1045     SDOperand Chain = Select(N->getOperand(0));
1046     SDOperand Reg = N->getOperand(1);
1047     SDOperand Val = Select(N->getOperand(2));
1048     SDOperand New = CurDAG->getNode(ISD::CopyToReg, MVT::Other,
1049                                     Chain, Reg, Val);
1050     CodeGenMap[Op] = New;
1051     return New;
1052   }
1053   case ISD::UNDEF:
1054     if (N->getValueType(0) == MVT::i32)
1055       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_GPR, MVT::i32);
1056     else if (N->getValueType(0) == MVT::f32)
1057       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_F4, MVT::f32);
1058     else
1059       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_F8, MVT::f64);
1060     return SDOperand(N, 0);
1061   case ISD::FrameIndex: {
1062     int FI = cast<FrameIndexSDNode>(N)->getIndex();
1063     CurDAG->SelectNodeTo(N, PPC::ADDI, MVT::i32,
1064                          CurDAG->getTargetFrameIndex(FI, MVT::i32),
1065                          getI32Imm(0));
1066     return SDOperand(N, 0);
1067   }
1068   case ISD::ConstantPool: {
1069     Constant *C = cast<ConstantPoolSDNode>(N)->get();
1070     SDOperand Tmp, CPI = CurDAG->getTargetConstantPool(C, MVT::i32);
1071     if (PICEnabled)
1072       Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),CPI);
1073     else
1074       Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, CPI);
1075     CurDAG->SelectNodeTo(N, PPC::LA, MVT::i32, Tmp, CPI);
1076     return SDOperand(N, 0);
1077   }
1078   case ISD::GlobalAddress: {
1079     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
1080     SDOperand Tmp;
1081     SDOperand GA = CurDAG->getTargetGlobalAddress(GV, MVT::i32);
1082     if (PICEnabled)
1083       Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(), GA);
1084     else
1085       Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, GA);
1086
1087     if (GV->hasWeakLinkage() || GV->isExternal())
1088       CurDAG->SelectNodeTo(N, PPC::LWZ, MVT::i32, GA, Tmp);
1089     else
1090       CurDAG->SelectNodeTo(N, PPC::LA, MVT::i32, Tmp, GA);
1091     return SDOperand(N, 0);
1092   }
1093
1094   case PPCISD::FSEL: {
1095     SDOperand Comparison = Select(N->getOperand(0));
1096     // Extend the comparison to 64-bits.
1097     if (Comparison.getValueType() == MVT::f32)
1098       Comparison = CurDAG->getTargetNode(PPC::FMRSD, MVT::f64, Comparison);
1099
1100     unsigned Opc = N->getValueType(0) == MVT::f32 ? PPC::FSELS : PPC::FSELD;
1101     CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), Comparison,
1102                          Select(N->getOperand(1)), Select(N->getOperand(2)));
1103     return SDOperand(N, 0);
1104   }
1105   case PPCISD::FCFID:
1106     CurDAG->SelectNodeTo(N, PPC::FCFID, N->getValueType(0),
1107                          Select(N->getOperand(0)));
1108     return SDOperand(N, 0);
1109   case PPCISD::FCTIDZ:
1110     CurDAG->SelectNodeTo(N, PPC::FCTIDZ, N->getValueType(0),
1111                          Select(N->getOperand(0)));
1112     return SDOperand(N, 0);
1113   case PPCISD::FCTIWZ:
1114     CurDAG->SelectNodeTo(N, PPC::FCTIWZ, N->getValueType(0),
1115                          Select(N->getOperand(0)));
1116     return SDOperand(N, 0);
1117   case ISD::FADD: {
1118     MVT::ValueType Ty = N->getValueType(0);
1119     if (!NoExcessFPPrecision) {  // Match FMA ops
1120       if (N->getOperand(0).getOpcode() == ISD::FMUL &&
1121           N->getOperand(0).Val->hasOneUse()) {
1122         ++FusedFP; // Statistic
1123         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS, Ty,
1124                              Select(N->getOperand(0).getOperand(0)),
1125                              Select(N->getOperand(0).getOperand(1)),
1126                              Select(N->getOperand(1)));
1127         return SDOperand(N, 0);
1128       } else if (N->getOperand(1).getOpcode() == ISD::FMUL &&
1129                  N->getOperand(1).hasOneUse()) {
1130         ++FusedFP; // Statistic
1131         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS, Ty,
1132                              Select(N->getOperand(1).getOperand(0)),
1133                              Select(N->getOperand(1).getOperand(1)),
1134                              Select(N->getOperand(0)));
1135         return SDOperand(N, 0);
1136       }
1137     }
1138
1139     CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FADD : PPC::FADDS, Ty,
1140                          Select(N->getOperand(0)), Select(N->getOperand(1)));
1141     return SDOperand(N, 0);
1142   }
1143   case ISD::FSUB: {
1144     MVT::ValueType Ty = N->getValueType(0);
1145
1146     if (!NoExcessFPPrecision) {  // Match FMA ops
1147       if (N->getOperand(0).getOpcode() == ISD::FMUL &&
1148           N->getOperand(0).Val->hasOneUse()) {
1149         ++FusedFP; // Statistic
1150         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS, Ty,
1151                              Select(N->getOperand(0).getOperand(0)),
1152                              Select(N->getOperand(0).getOperand(1)),
1153                              Select(N->getOperand(1)));
1154         return SDOperand(N, 0);
1155       } else if (N->getOperand(1).getOpcode() == ISD::FMUL &&
1156                  N->getOperand(1).Val->hasOneUse()) {
1157         ++FusedFP; // Statistic
1158         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS, Ty,
1159                              Select(N->getOperand(1).getOperand(0)),
1160                              Select(N->getOperand(1).getOperand(1)),
1161                              Select(N->getOperand(0)));
1162         return SDOperand(N, 0);
1163       }
1164     }
1165     CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FSUB : PPC::FSUBS, Ty,
1166                          Select(N->getOperand(0)),
1167                          Select(N->getOperand(1)));
1168     return SDOperand(N, 0);
1169   }
1170   case ISD::SDIV: {
1171     unsigned Imm;
1172     if (isIntImmediate(N->getOperand(1), Imm)) {
1173       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
1174         SDOperand Op =
1175           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
1176                                 Select(N->getOperand(0)),
1177                                 getI32Imm(Log2_32(Imm)));
1178         CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
1179                              Op.getValue(0), Op.getValue(1));
1180         return SDOperand(N, 0);
1181       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
1182         SDOperand Op =
1183           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
1184                                 Select(N->getOperand(0)),
1185                                 getI32Imm(Log2_32(-Imm)));
1186         SDOperand PT =
1187           CurDAG->getTargetNode(PPC::ADDZE, MVT::i32, Op.getValue(0),
1188                                 Op.getValue(1));
1189         CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT);
1190         return SDOperand(N, 0);
1191       } else if (Imm) {
1192         SDOperand Result = Select(BuildSDIVSequence(N));
1193         CodeGenMap[Op] = Result;
1194         return Result;
1195       }
1196     }
1197
1198     // Other cases are autogenerated.
1199     break;
1200   }
1201   case ISD::UDIV: {
1202     // If this is a divide by constant, we can emit code using some magic
1203     // constants to implement it as a multiply instead.
1204     unsigned Imm;
1205     if (isIntImmediate(N->getOperand(1), Imm) && Imm) {
1206       SDOperand Result = Select(BuildUDIVSequence(N));
1207       CodeGenMap[Op] = Result;
1208       return Result;
1209     }
1210
1211     // Other cases are autogenerated.
1212     break;
1213   }
1214   case ISD::AND: {
1215     unsigned Imm;
1216     // If this is an and of a value rotated between 0 and 31 bits and then and'd
1217     // with a mask, emit rlwinm
1218     if (isIntImmediate(N->getOperand(1), Imm) && (isShiftedMask_32(Imm) ||
1219                                                   isShiftedMask_32(~Imm))) {
1220       SDOperand Val;
1221       unsigned SH, MB, ME;
1222       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
1223         Val = Select(N->getOperand(0).getOperand(0));
1224       } else {
1225         Val = Select(N->getOperand(0));
1226         isRunOfOnes(Imm, MB, ME);
1227         SH = 0;
1228       }
1229       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Val, getI32Imm(SH),
1230                            getI32Imm(MB), getI32Imm(ME));
1231       return SDOperand(N, 0);
1232     }
1233
1234     // Other cases are autogenerated.
1235     break;
1236   }
1237   case ISD::OR:
1238     if (SDNode *I = SelectBitfieldInsert(N))
1239       return CodeGenMap[Op] = SDOperand(I, 0);
1240
1241     if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
1242                                            N->getOperand(1),
1243                                            PPC::ORIS, PPC::ORI))
1244       return CodeGenMap[Op] = SDOperand(I, 0);
1245
1246     // Other cases are autogenerated.
1247     break;
1248   case ISD::SHL: {
1249     unsigned Imm, SH, MB, ME;
1250     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1251         isRotateAndMask(N, Imm, true, SH, MB, ME))
1252       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1253                            Select(N->getOperand(0).getOperand(0)),
1254                            getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
1255     else if (isIntImmediate(N->getOperand(1), Imm))
1256       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Select(N->getOperand(0)),
1257                            getI32Imm(Imm), getI32Imm(0), getI32Imm(31-Imm));
1258     else
1259       CurDAG->SelectNodeTo(N, PPC::SLW, MVT::i32, Select(N->getOperand(0)),
1260                            Select(N->getOperand(1)));
1261     return SDOperand(N, 0);
1262   }
1263   case ISD::SRL: {
1264     unsigned Imm, SH, MB, ME;
1265     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1266         isRotateAndMask(N, Imm, true, SH, MB, ME))
1267       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1268                            Select(N->getOperand(0).getOperand(0)),
1269                            getI32Imm(SH & 0x1F), getI32Imm(MB), getI32Imm(ME));
1270     else if (isIntImmediate(N->getOperand(1), Imm))
1271       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Select(N->getOperand(0)),
1272                            getI32Imm((32-Imm) & 0x1F), getI32Imm(Imm),
1273                            getI32Imm(31));
1274     else
1275       CurDAG->SelectNodeTo(N, PPC::SRW, MVT::i32, Select(N->getOperand(0)),
1276                            Select(N->getOperand(1)));
1277     return SDOperand(N, 0);
1278   }
1279   case ISD::SRA: {
1280     unsigned Imm, SH, MB, ME;
1281     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1282         isRotateAndMask(N, Imm, true, SH, MB, ME))
1283       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1284                            Select(N->getOperand(0).getOperand(0)),
1285                            getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
1286     else if (isIntImmediate(N->getOperand(1), Imm))
1287       CurDAG->SelectNodeTo(N, PPC::SRAWI, MVT::i32, Select(N->getOperand(0)),
1288                            getI32Imm(Imm));
1289     else
1290       CurDAG->SelectNodeTo(N, PPC::SRAW, MVT::i32, Select(N->getOperand(0)),
1291                            Select(N->getOperand(1)));
1292     return SDOperand(N, 0);
1293   }
1294   case ISD::FMUL: {
1295     unsigned Opc = N->getValueType(0) == MVT::f32 ? PPC::FMULS : PPC::FMUL;
1296     CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), Select(N->getOperand(0)),
1297                          Select(N->getOperand(1)));
1298     return SDOperand(N, 0);
1299   }
1300   case ISD::FDIV: {
1301     unsigned Opc = N->getValueType(0) == MVT::f32 ? PPC::FDIVS : PPC::FDIV;
1302     CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), Select(N->getOperand(0)),
1303                          Select(N->getOperand(1)));
1304     return SDOperand(N, 0);
1305   }
1306   case ISD::FABS:
1307     if (N->getValueType(0) == MVT::f32)
1308       CurDAG->SelectNodeTo(N, PPC::FABSS, MVT::f32, Select(N->getOperand(0)));
1309     else
1310       CurDAG->SelectNodeTo(N, PPC::FABSD, MVT::f64, Select(N->getOperand(0)));
1311     return SDOperand(N, 0);
1312   case ISD::FP_EXTEND:
1313     assert(MVT::f64 == N->getValueType(0) &&
1314            MVT::f32 == N->getOperand(0).getValueType() && "Illegal FP_EXTEND");
1315     // We need to emit an FMR to make sure that the result has the right value
1316     // type.
1317     CurDAG->SelectNodeTo(N, PPC::FMRSD, MVT::f64, Select(N->getOperand(0)));
1318     return SDOperand(N, 0);
1319   case ISD::FP_ROUND:
1320     assert(MVT::f32 == N->getValueType(0) &&
1321            MVT::f64 == N->getOperand(0).getValueType() && "Illegal FP_ROUND");
1322     CurDAG->SelectNodeTo(N, PPC::FRSP, MVT::f32, Select(N->getOperand(0)));
1323     return SDOperand(N, 0);
1324   case ISD::FNEG: {
1325     SDOperand Val = Select(N->getOperand(0));
1326     MVT::ValueType Ty = N->getValueType(0);
1327     if (Val.Val->hasOneUse()) {
1328       unsigned Opc;
1329       switch (Val.isTargetOpcode() ? Val.getTargetOpcode() : 0) {
1330       default:          Opc = 0;            break;
1331       case PPC::FABSS:  Opc = PPC::FNABSS;  break;
1332       case PPC::FABSD:  Opc = PPC::FNABSD;  break;
1333       case PPC::FMADD:  Opc = PPC::FNMADD;  break;
1334       case PPC::FMADDS: Opc = PPC::FNMADDS; break;
1335       case PPC::FMSUB:  Opc = PPC::FNMSUB;  break;
1336       case PPC::FMSUBS: Opc = PPC::FNMSUBS; break;
1337       }
1338       // If we inverted the opcode, then emit the new instruction with the
1339       // inverted opcode and the original instruction's operands.  Otherwise,
1340       // fall through and generate a fneg instruction.
1341       if (Opc) {
1342         if (Opc == PPC::FNABSS || Opc == PPC::FNABSD)
1343           CurDAG->SelectNodeTo(N, Opc, Ty, Val.getOperand(0));
1344         else
1345           CurDAG->SelectNodeTo(N, Opc, Ty, Val.getOperand(0),
1346                                Val.getOperand(1), Val.getOperand(2));
1347         return SDOperand(N, 0);
1348       }
1349     }
1350     if (Ty == MVT::f32)
1351       CurDAG->SelectNodeTo(N, PPC::FNEGS, MVT::f32, Val);
1352     else
1353       CurDAG->SelectNodeTo(N, PPC::FNEGD, MVT::f64, Val);
1354     return SDOperand(N, 0);
1355   }
1356   case ISD::FSQRT: {
1357     MVT::ValueType Ty = N->getValueType(0);
1358     CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS, Ty,
1359                          Select(N->getOperand(0)));
1360     return SDOperand(N, 0);
1361   }
1362   case ISD::LOAD:
1363   case ISD::EXTLOAD:
1364   case ISD::ZEXTLOAD:
1365   case ISD::SEXTLOAD: {
1366     SDOperand Op1, Op2;
1367     bool isIdx = SelectAddr(N->getOperand(1), Op1, Op2);
1368
1369     MVT::ValueType TypeBeingLoaded = (N->getOpcode() == ISD::LOAD) ?
1370       N->getValueType(0) : cast<VTSDNode>(N->getOperand(3))->getVT();
1371     unsigned Opc;
1372     switch (TypeBeingLoaded) {
1373     default: N->dump(); assert(0 && "Cannot load this type!");
1374     case MVT::i1:
1375     case MVT::i8:  Opc = isIdx ? PPC::LBZX : PPC::LBZ; break;
1376     case MVT::i16:
1377       if (N->getOpcode() == ISD::SEXTLOAD) { // SEXT load?
1378         Opc = isIdx ? PPC::LHAX : PPC::LHA;
1379       } else {
1380         Opc = isIdx ? PPC::LHZX : PPC::LHZ;
1381       }
1382       break;
1383     case MVT::i32: Opc = isIdx ? PPC::LWZX : PPC::LWZ; break;
1384     case MVT::f32: Opc = isIdx ? PPC::LFSX : PPC::LFS; break;
1385     case MVT::f64: Opc = isIdx ? PPC::LFDX : PPC::LFD; break;
1386     }
1387
1388     // If this is an f32 -> f64 load, emit the f32 load, then use an 'extending
1389     // copy'.
1390     if (TypeBeingLoaded != MVT::f32 || N->getOpcode() == ISD::LOAD) {
1391         CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), MVT::Other,
1392                              Op1, Op2, Select(N->getOperand(0)));
1393       return SDOperand(N, Op.ResNo);
1394     } else {
1395       std::vector<SDOperand> Ops;
1396       Ops.push_back(Op1);
1397       Ops.push_back(Op2);
1398       Ops.push_back(Select(N->getOperand(0)));
1399       SDOperand Res = CurDAG->getTargetNode(Opc, MVT::f32, MVT::Other, Ops);
1400       SDOperand Ext = CurDAG->getTargetNode(PPC::FMRSD, MVT::f64, Res);
1401       CodeGenMap[Op.getValue(0)] = Ext;
1402       CodeGenMap[Op.getValue(1)] = Res.getValue(1);
1403       if (Op.ResNo)
1404         return Res.getValue(1);
1405       else
1406         return Ext;
1407     }
1408   }
1409   case ISD::TRUNCSTORE:
1410   case ISD::STORE: {
1411     SDOperand AddrOp1, AddrOp2;
1412     bool isIdx = SelectAddr(N->getOperand(2), AddrOp1, AddrOp2);
1413
1414     unsigned Opc;
1415     if (N->getOpcode() == ISD::STORE) {
1416       switch (N->getOperand(1).getValueType()) {
1417       default: assert(0 && "unknown Type in store");
1418       case MVT::i32: Opc = isIdx ? PPC::STWX  : PPC::STW; break;
1419       case MVT::f64: Opc = isIdx ? PPC::STFDX : PPC::STFD; break;
1420       case MVT::f32: Opc = isIdx ? PPC::STFSX : PPC::STFS; break;
1421       }
1422     } else { //ISD::TRUNCSTORE
1423       switch(cast<VTSDNode>(N->getOperand(4))->getVT()) {
1424       default: assert(0 && "unknown Type in store");
1425       case MVT::i8:  Opc = isIdx ? PPC::STBX : PPC::STB; break;
1426       case MVT::i16: Opc = isIdx ? PPC::STHX : PPC::STH; break;
1427       }
1428     }
1429
1430     CurDAG->SelectNodeTo(N, Opc, MVT::Other, Select(N->getOperand(1)),
1431                          AddrOp1, AddrOp2, Select(N->getOperand(0)));
1432     return SDOperand(N, 0);
1433   }
1434
1435   case ISD::SELECT_CC: {
1436     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
1437
1438     // handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1439     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1440       if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
1441         if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
1442           if (N1C->isNullValue() && N3C->isNullValue() &&
1443               N2C->getValue() == 1ULL && CC == ISD::SETNE) {
1444             SDOperand LHS = Select(N->getOperand(0));
1445             SDOperand Tmp =
1446               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1447                                     LHS, getI32Imm(~0U));
1448             CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, Tmp, LHS,
1449                                  Tmp.getValue(1));
1450             return SDOperand(N, 0);
1451           }
1452
1453     SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
1454     unsigned BROpc = getBCCForSetCC(CC);
1455
1456     bool isFP = MVT::isFloatingPoint(N->getValueType(0));
1457     unsigned SelectCCOp;
1458     if (MVT::isInteger(N->getValueType(0)))
1459       SelectCCOp = PPC::SELECT_CC_Int;
1460     else if (N->getValueType(0) == MVT::f32)
1461       SelectCCOp = PPC::SELECT_CC_F4;
1462     else
1463       SelectCCOp = PPC::SELECT_CC_F8;
1464     CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), CCReg,
1465                          Select(N->getOperand(2)), Select(N->getOperand(3)),
1466                          getI32Imm(BROpc));
1467     return SDOperand(N, 0);
1468   }
1469
1470   case ISD::CALLSEQ_START:
1471   case ISD::CALLSEQ_END: {
1472     unsigned Amt = cast<ConstantSDNode>(N->getOperand(1))->getValue();
1473     unsigned Opc = N->getOpcode() == ISD::CALLSEQ_START ?
1474                        PPC::ADJCALLSTACKDOWN : PPC::ADJCALLSTACKUP;
1475     CurDAG->SelectNodeTo(N, Opc, MVT::Other,
1476                          getI32Imm(Amt), Select(N->getOperand(0)));
1477     return SDOperand(N, 0);
1478   }
1479   case ISD::RET: {
1480     SDOperand Chain = Select(N->getOperand(0));     // Token chain.
1481
1482     if (N->getNumOperands() == 2) {
1483       SDOperand Val = Select(N->getOperand(1));
1484       if (N->getOperand(1).getValueType() == MVT::i32) {
1485         Chain = CurDAG->getCopyToReg(Chain, PPC::R3, Val);
1486       } else {
1487         assert(MVT::isFloatingPoint(N->getOperand(1).getValueType()));
1488         Chain = CurDAG->getCopyToReg(Chain, PPC::F1, Val);
1489       }
1490     } else if (N->getNumOperands() > 1) {
1491       assert(N->getOperand(1).getValueType() == MVT::i32 &&
1492              N->getOperand(2).getValueType() == MVT::i32 &&
1493              N->getNumOperands() == 3 && "Unknown two-register ret value!");
1494       Chain = CurDAG->getCopyToReg(Chain, PPC::R4, Select(N->getOperand(1)));
1495       Chain = CurDAG->getCopyToReg(Chain, PPC::R3, Select(N->getOperand(2)));
1496     }
1497
1498     // Finally, select this to a blr (return) instruction.
1499     CurDAG->SelectNodeTo(N, PPC::BLR, MVT::Other, Chain);
1500     return SDOperand(N, 0);
1501   }
1502   case ISD::BR:
1503     CurDAG->SelectNodeTo(N, PPC::B, MVT::Other, N->getOperand(1),
1504                          Select(N->getOperand(0)));
1505     return SDOperand(N, 0);
1506   case ISD::BR_CC:
1507   case ISD::BRTWOWAY_CC: {
1508     SDOperand Chain = Select(N->getOperand(0));
1509     MachineBasicBlock *Dest =
1510       cast<BasicBlockSDNode>(N->getOperand(4))->getBasicBlock();
1511     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
1512     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
1513
1514     // If this is a two way branch, then grab the fallthrough basic block
1515     // argument and build a PowerPC branch pseudo-op, suitable for long branch
1516     // conversion if necessary by the branch selection pass.  Otherwise, emit a
1517     // standard conditional branch.
1518     if (N->getOpcode() == ISD::BRTWOWAY_CC) {
1519       SDOperand CondTrueBlock = N->getOperand(4);
1520       SDOperand CondFalseBlock = N->getOperand(5);
1521
1522       // If the false case is the current basic block, then this is a self loop.
1523       // We do not want to emit "Loop: ... brcond Out; br Loop", as it adds an
1524       // extra dispatch group to the loop.  Instead, invert the condition and
1525       // emit "Loop: ... br!cond Loop; br Out
1526       if (cast<BasicBlockSDNode>(CondFalseBlock)->getBasicBlock() == BB) {
1527         std::swap(CondTrueBlock, CondFalseBlock);
1528         CC = getSetCCInverse(CC,
1529                              MVT::isInteger(N->getOperand(2).getValueType()));
1530       }
1531
1532       unsigned Opc = getBCCForSetCC(CC);
1533       SDOperand CB = CurDAG->getTargetNode(PPC::COND_BRANCH, MVT::Other,
1534                                            CondCode, getI32Imm(Opc),
1535                                            CondTrueBlock, CondFalseBlock,
1536                                            Chain);
1537       CurDAG->SelectNodeTo(N, PPC::B, MVT::Other, CondFalseBlock, CB);
1538     } else {
1539       // Iterate to the next basic block
1540       ilist<MachineBasicBlock>::iterator It = BB;
1541       ++It;
1542
1543       // If the fallthrough path is off the end of the function, which would be
1544       // undefined behavior, set it to be the same as the current block because
1545       // we have nothing better to set it to, and leaving it alone will cause
1546       // the PowerPC Branch Selection pass to crash.
1547       if (It == BB->getParent()->end()) It = Dest;
1548       CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other, CondCode,
1549                            getI32Imm(getBCCForSetCC(CC)), N->getOperand(4),
1550                            CurDAG->getBasicBlock(It), Chain);
1551     }
1552     return SDOperand(N, 0);
1553   }
1554   }
1555
1556   return SelectCode(Op);
1557 }
1558
1559
1560 /// createPPC32ISelDag - This pass converts a legalized DAG into a
1561 /// PowerPC-specific DAG, ready for instruction scheduling.
1562 ///
1563 FunctionPass *llvm::createPPC32ISelDag(TargetMachine &TM) {
1564   return new PPC32DAGToDAGISel(TM);
1565 }
1566