LLVM API Documentation

PPCISelDAGToDAG.cpp

Go to the documentation of this file.
00001 //===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Chris Lattner and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines a pattern matching instruction selector for PowerPC,
00011 // converting from a legalized dag to a PPC dag.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "PPC.h"
00016 #include "PPCTargetMachine.h"
00017 #include "PPCISelLowering.h"
00018 #include "PPCHazardRecognizers.h"
00019 #include "llvm/CodeGen/MachineInstrBuilder.h"
00020 #include "llvm/CodeGen/MachineFunction.h"
00021 #include "llvm/CodeGen/SSARegMap.h"
00022 #include "llvm/CodeGen/SelectionDAG.h"
00023 #include "llvm/CodeGen/SelectionDAGISel.h"
00024 #include "llvm/Target/TargetOptions.h"
00025 #include "llvm/ADT/Statistic.h"
00026 #include "llvm/Constants.h"
00027 #include "llvm/GlobalValue.h"
00028 #include "llvm/Intrinsics.h"
00029 #include "llvm/Support/Debug.h"
00030 #include "llvm/Support/MathExtras.h"
00031 #include <iostream>
00032 #include <set>
00033 using namespace llvm;
00034 
00035 namespace {
00036   Statistic<> FrameOff("ppc-codegen", "Number of frame idx offsets collapsed");
00037     
00038   //===--------------------------------------------------------------------===//
00039   /// PPCDAGToDAGISel - PPC specific code to select PPC machine
00040   /// instructions for SelectionDAG operations.
00041   ///
00042   class PPCDAGToDAGISel : public SelectionDAGISel {
00043     PPCTargetMachine &TM;
00044     PPCTargetLowering PPCLowering;
00045     unsigned GlobalBaseReg;
00046   public:
00047     PPCDAGToDAGISel(PPCTargetMachine &tm)
00048       : SelectionDAGISel(PPCLowering), TM(tm),
00049         PPCLowering(*TM.getTargetLowering()) {}
00050     
00051     virtual bool runOnFunction(Function &Fn) {
00052       // Make sure we re-emit a set of the global base reg if necessary
00053       GlobalBaseReg = 0;
00054       SelectionDAGISel::runOnFunction(Fn);
00055       
00056       InsertVRSaveCode(Fn);
00057       return true;
00058     }
00059    
00060     /// getI32Imm - Return a target constant with the specified value, of type
00061     /// i32.
00062     inline SDOperand getI32Imm(unsigned Imm) {
00063       return CurDAG->getTargetConstant(Imm, MVT::i32);
00064     }
00065 
00066     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
00067     /// base register.  Return the virtual register that holds this value.
00068     SDOperand getGlobalBaseReg();
00069     
00070     // Select - Convert the specified operand from a target-independent to a
00071     // target-specific node if it hasn't already been changed.
00072     void Select(SDOperand &Result, SDOperand Op);
00073     
00074     SDNode *SelectBitfieldInsert(SDNode *N);
00075 
00076     /// SelectCC - Select a comparison of the specified values with the
00077     /// specified condition code, returning the CR# of the expression.
00078     SDOperand SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC);
00079 
00080     /// SelectAddrImm - Returns true if the address N can be represented by
00081     /// a base register plus a signed 16-bit displacement [r+imm].
00082     bool SelectAddrImm(SDOperand N, SDOperand &Disp, SDOperand &Base);
00083       
00084     /// SelectAddrIdx - Given the specified addressed, check to see if it can be
00085     /// represented as an indexed [r+r] operation.  Returns false if it can
00086     /// be represented by [r+imm], which are preferred.
00087     bool SelectAddrIdx(SDOperand N, SDOperand &Base, SDOperand &Index);
00088     
00089     /// SelectAddrIdxOnly - Given the specified addressed, force it to be
00090     /// represented as an indexed [r+r] operation.
00091     bool SelectAddrIdxOnly(SDOperand N, SDOperand &Base, SDOperand &Index);
00092 
00093     /// SelectAddrImmShift - Returns true if the address N can be represented by
00094     /// a base register plus a signed 14-bit displacement [r+imm*4].  Suitable
00095     /// for use by STD and friends.
00096     bool SelectAddrImmShift(SDOperand N, SDOperand &Disp, SDOperand &Base);
00097     
00098     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
00099     /// inline asm expressions.
00100     virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op,
00101                                               char ConstraintCode,
00102                                               std::vector<SDOperand> &OutOps,
00103                                               SelectionDAG &DAG) {
00104       SDOperand Op0, Op1;
00105       switch (ConstraintCode) {
00106       default: return true;
00107       case 'm':   // memory
00108         if (!SelectAddrIdx(Op, Op0, Op1))
00109           SelectAddrImm(Op, Op0, Op1);
00110         break;
00111       case 'o':   // offsetable
00112         if (!SelectAddrImm(Op, Op0, Op1)) {
00113           Select(Op0, Op);     // r+0.
00114           Op1 = getI32Imm(0);
00115         }
00116         break;
00117       case 'v':   // not offsetable
00118         SelectAddrIdxOnly(Op, Op0, Op1);
00119         break;
00120       }
00121       
00122       OutOps.push_back(Op0);
00123       OutOps.push_back(Op1);
00124       return false;
00125     }
00126     
00127     SDOperand BuildSDIVSequence(SDNode *N);
00128     SDOperand BuildUDIVSequence(SDNode *N);
00129     
00130     /// InstructionSelectBasicBlock - This callback is invoked by
00131     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
00132     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
00133     
00134     void InsertVRSaveCode(Function &Fn);
00135 
00136     virtual const char *getPassName() const {
00137       return "PowerPC DAG->DAG Pattern Instruction Selection";
00138     } 
00139     
00140     /// CreateTargetHazardRecognizer - Return the hazard recognizer to use for this
00141     /// target when scheduling the DAG.
00142     virtual HazardRecognizer *CreateTargetHazardRecognizer() {
00143       // Should use subtarget info to pick the right hazard recognizer.  For
00144       // now, always return a PPC970 recognizer.
00145       const TargetInstrInfo *II = PPCLowering.getTargetMachine().getInstrInfo();
00146       assert(II && "No InstrInfo?");
00147       return new PPCHazardRecognizer970(*II); 
00148     }
00149 
00150 // Include the pieces autogenerated from the target description.
00151 #include "PPCGenDAGISel.inc"
00152     
00153 private:
00154     SDOperand SelectSETCC(SDOperand Op);
00155     SDOperand SelectCALL(SDOperand Op);
00156   };
00157 }
00158 
00159 /// InstructionSelectBasicBlock - This callback is invoked by
00160 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
00161 void PPCDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
00162   DEBUG(BB->dump());
00163   
00164   // The selection process is inherently a bottom-up recursive process (users
00165   // select their uses before themselves).  Given infinite stack space, we
00166   // could just start selecting on the root and traverse the whole graph.  In
00167   // practice however, this causes us to run out of stack space on large basic
00168   // blocks.  To avoid this problem, select the entry node, then all its uses,
00169   // iteratively instead of recursively.
00170   std::vector<SDOperand> Worklist;
00171   Worklist.push_back(DAG.getEntryNode());
00172   
00173   // Note that we can do this in the PPC target (scanning forward across token
00174   // chain edges) because no nodes ever get folded across these edges.  On a
00175   // target like X86 which supports load/modify/store operations, this would
00176   // have to be more careful.
00177   while (!Worklist.empty()) {
00178     SDOperand Node = Worklist.back();
00179     Worklist.pop_back();
00180     
00181     // Chose from the least deep of the top two nodes.
00182     if (!Worklist.empty() &&
00183         Worklist.back().Val->getNodeDepth() < Node.Val->getNodeDepth())
00184       std::swap(Worklist.back(), Node);
00185     
00186     if ((Node.Val->getOpcode() >= ISD::BUILTIN_OP_END &&
00187          Node.Val->getOpcode() < PPCISD::FIRST_NUMBER) ||
00188         CodeGenMap.count(Node)) continue;
00189     
00190     for (SDNode::use_iterator UI = Node.Val->use_begin(),
00191          E = Node.Val->use_end(); UI != E; ++UI) {
00192       // Scan the values.  If this use has a value that is a token chain, add it
00193       // to the worklist.
00194       SDNode *User = *UI;
00195       for (unsigned i = 0, e = User->getNumValues(); i != e; ++i)
00196         if (User->getValueType(i) == MVT::Other) {
00197           Worklist.push_back(SDOperand(User, i));
00198           break; 
00199         }
00200     }
00201 
00202     // Finally, legalize this node.
00203     SDOperand Dummy;
00204     Select(Dummy, Node);
00205   }
00206     
00207   // Select target instructions for the DAG.
00208   DAG.setRoot(SelectRoot(DAG.getRoot()));
00209   CodeGenMap.clear();
00210   DAG.RemoveDeadNodes();
00211   
00212   // Emit machine code to BB.
00213   ScheduleAndEmitDAG(DAG);
00214 }
00215 
00216 /// InsertVRSaveCode - Once the entire function has been instruction selected,
00217 /// all virtual registers are created and all machine instructions are built,
00218 /// check to see if we need to save/restore VRSAVE.  If so, do it.
00219 void PPCDAGToDAGISel::InsertVRSaveCode(Function &F) {
00220   // Check to see if this function uses vector registers, which means we have to
00221   // save and restore the VRSAVE register and update it with the regs we use.  
00222   //
00223   // In this case, there will be virtual registers of vector type type created
00224   // by the scheduler.  Detect them now.
00225   MachineFunction &Fn = MachineFunction::get(&F);
00226   SSARegMap *RegMap = Fn.getSSARegMap();
00227   bool HasVectorVReg = false;
00228   for (unsigned i = MRegisterInfo::FirstVirtualRegister, 
00229        e = RegMap->getLastVirtReg()+1; i != e; ++i)
00230     if (RegMap->getRegClass(i) == &PPC::VRRCRegClass) {
00231       HasVectorVReg = true;
00232       break;
00233     }
00234   if (!HasVectorVReg) return;  // nothing to do.
00235       
00236   // If we have a vector register, we want to emit code into the entry and exit
00237   // blocks to save and restore the VRSAVE register.  We do this here (instead
00238   // of marking all vector instructions as clobbering VRSAVE) for two reasons:
00239   //
00240   // 1. This (trivially) reduces the load on the register allocator, by not
00241   //    having to represent the live range of the VRSAVE register.
00242   // 2. This (more significantly) allows us to create a temporary virtual
00243   //    register to hold the saved VRSAVE value, allowing this temporary to be
00244   //    register allocated, instead of forcing it to be spilled to the stack.
00245 
00246   // Create two vregs - one to hold the VRSAVE register that is live-in to the
00247   // function and one for the value after having bits or'd into it.
00248   unsigned InVRSAVE = RegMap->createVirtualRegister(&PPC::GPRCRegClass);
00249   unsigned UpdatedVRSAVE = RegMap->createVirtualRegister(&PPC::GPRCRegClass);
00250   
00251   MachineBasicBlock &EntryBB = *Fn.begin();
00252   // Emit the following code into the entry block:
00253   // InVRSAVE = MFVRSAVE
00254   // UpdatedVRSAVE = UPDATE_VRSAVE InVRSAVE
00255   // MTVRSAVE UpdatedVRSAVE
00256   MachineBasicBlock::iterator IP = EntryBB.begin();  // Insert Point
00257   BuildMI(EntryBB, IP, PPC::MFVRSAVE, 0, InVRSAVE);
00258   BuildMI(EntryBB, IP, PPC::UPDATE_VRSAVE, 1, UpdatedVRSAVE).addReg(InVRSAVE);
00259   BuildMI(EntryBB, IP, PPC::MTVRSAVE, 1).addReg(UpdatedVRSAVE);
00260   
00261   // Find all return blocks, outputting a restore in each epilog.
00262   const TargetInstrInfo &TII = *TM.getInstrInfo();
00263   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
00264     if (!BB->empty() && TII.isReturn(BB->back().getOpcode())) {
00265       IP = BB->end(); --IP;
00266       
00267       // Skip over all terminator instructions, which are part of the return
00268       // sequence.
00269       MachineBasicBlock::iterator I2 = IP;
00270       while (I2 != BB->begin() && TII.isTerminatorInstr((--I2)->getOpcode()))
00271         IP = I2;
00272       
00273       // Emit: MTVRSAVE InVRSave
00274       BuildMI(*BB, IP, PPC::MTVRSAVE, 1).addReg(InVRSAVE);
00275     }        
00276   }
00277 }
00278 
00279 
00280 /// getGlobalBaseReg - Output the instructions required to put the
00281 /// base address to use for accessing globals into a register.
00282 ///
00283 SDOperand PPCDAGToDAGISel::getGlobalBaseReg() {
00284   if (!GlobalBaseReg) {
00285     // Insert the set of GlobalBaseReg into the first MBB of the function
00286     MachineBasicBlock &FirstMBB = BB->getParent()->front();
00287     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
00288     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
00289     // FIXME: when we get to LP64, we will need to create the appropriate
00290     // type of register here.
00291     GlobalBaseReg = RegMap->createVirtualRegister(PPC::GPRCRegisterClass);
00292     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
00293     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg);
00294   }
00295   return CurDAG->getRegister(GlobalBaseReg, MVT::i32);
00296 }
00297 
00298 
00299 // isIntImmediate - This method tests to see if a constant operand.
00300 // If so Imm will receive the 32 bit value.
00301 static bool isIntImmediate(SDNode *N, unsigned& Imm) {
00302   if (N->getOpcode() == ISD::Constant) {
00303     Imm = cast<ConstantSDNode>(N)->getValue();
00304     return true;
00305   }
00306   return false;
00307 }
00308 
00309 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
00310 // any number of 0s on either side.  The 1s are allowed to wrap from LSB to
00311 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
00312 // not, since all 1s are not contiguous.
00313 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
00314   if (isShiftedMask_32(Val)) {
00315     // look for the first non-zero bit
00316     MB = CountLeadingZeros_32(Val);
00317     // look for the first zero bit after the run of ones
00318     ME = CountLeadingZeros_32((Val - 1) ^ Val);
00319     return true;
00320   } else {
00321     Val = ~Val; // invert mask
00322     if (isShiftedMask_32(Val)) {
00323       // effectively look for the first zero bit
00324       ME = CountLeadingZeros_32(Val) - 1;
00325       // effectively look for the first one bit after the run of zeros
00326       MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
00327       return true;
00328     }
00329   }
00330   // no run present
00331   return false;
00332 }
00333 
00334 // isRotateAndMask - Returns true if Mask and Shift can be folded into a rotate
00335 // and mask opcode and mask operation.
00336 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
00337                             unsigned &SH, unsigned &MB, unsigned &ME) {
00338   // Don't even go down this path for i64, since different logic will be
00339   // necessary for rldicl/rldicr/rldimi.
00340   if (N->getValueType(0) != MVT::i32)
00341     return false;
00342 
00343   unsigned Shift  = 32;
00344   unsigned Indeterminant = ~0;  // bit mask marking indeterminant results
00345   unsigned Opcode = N->getOpcode();
00346   if (N->getNumOperands() != 2 ||
00347       !isIntImmediate(N->getOperand(1).Val, Shift) || (Shift > 31))
00348     return false;
00349   
00350   if (Opcode == ISD::SHL) {
00351     // apply shift left to mask if it comes first
00352     if (IsShiftMask) Mask = Mask << Shift;
00353     // determine which bits are made indeterminant by shift
00354     Indeterminant = ~(0xFFFFFFFFu << Shift);
00355   } else if (Opcode == ISD::SRL) { 
00356     // apply shift right to mask if it comes first
00357     if (IsShiftMask) Mask = Mask >> Shift;
00358     // determine which bits are made indeterminant by shift
00359     Indeterminant = ~(0xFFFFFFFFu >> Shift);
00360     // adjust for the left rotate
00361     Shift = 32 - Shift;
00362   } else {
00363     return false;
00364   }
00365   
00366   // if the mask doesn't intersect any Indeterminant bits
00367   if (Mask && !(Mask & Indeterminant)) {
00368     SH = Shift;
00369     // make sure the mask is still a mask (wrap arounds may not be)
00370     return isRunOfOnes(Mask, MB, ME);
00371   }
00372   return false;
00373 }
00374 
00375 // isOpcWithIntImmediate - This method tests to see if the node is a specific
00376 // opcode and that it has a immediate integer right operand.
00377 // If so Imm will receive the 32 bit value.
00378 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
00379   return N->getOpcode() == Opc && isIntImmediate(N->getOperand(1).Val, Imm);
00380 }
00381 
00382 // isIntImmediate - This method tests to see if a constant operand.
00383 // If so Imm will receive the 32 bit value.
00384 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
00385   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
00386     Imm = (unsigned)CN->getSignExtended();
00387     return true;
00388   }
00389   return false;
00390 }
00391 
00392 /// SelectBitfieldInsert - turn an or of two masked values into
00393 /// the rotate left word immediate then mask insert (rlwimi) instruction.
00394 /// Returns true on success, false if the caller still needs to select OR.
00395 ///
00396 /// Patterns matched:
00397 /// 1. or shl, and   5. or and, and
00398 /// 2. or and, shl   6. or shl, shr
00399 /// 3. or shr, and   7. or shr, shl
00400 /// 4. or and, shr
00401 SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
00402   bool IsRotate = false;
00403   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, SH = 0;
00404   unsigned Value;
00405   
00406   SDOperand Op0 = N->getOperand(0);
00407   SDOperand Op1 = N->getOperand(1);
00408   
00409   unsigned Op0Opc = Op0.getOpcode();
00410   unsigned Op1Opc = Op1.getOpcode();
00411   
00412   // Verify that we have the correct opcodes
00413   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
00414     return false;
00415   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
00416     return false;
00417   
00418   // Generate Mask value for Target
00419   if (isIntImmediate(Op0.getOperand(1), Value)) {
00420     switch(Op0Opc) {
00421     case ISD::SHL: TgtMask <<= Value; break;
00422     case ISD::SRL: TgtMask >>= Value; break;
00423     case ISD::AND: TgtMask &= Value; break;
00424     }
00425   } else {
00426     return 0;
00427   }
00428   
00429   // Generate Mask value for Insert
00430   if (!isIntImmediate(Op1.getOperand(1), Value))
00431     return 0;
00432   
00433   switch(Op1Opc) {
00434   case ISD::SHL:
00435     SH = Value;
00436     InsMask <<= SH;
00437     if (Op0Opc == ISD::SRL) IsRotate = true;
00438     break;
00439   case ISD::SRL:
00440     SH = Value;
00441     InsMask >>= SH;
00442     SH = 32-SH;
00443     if (Op0Opc == ISD::SHL) IsRotate = true;
00444     break;
00445   case ISD::AND:
00446     InsMask &= Value;
00447     break;
00448   }
00449   
00450   // If both of the inputs are ANDs and one of them has a logical shift by
00451   // constant as its input, make that AND the inserted value so that we can
00452   // combine the shift into the rotate part of the rlwimi instruction
00453   bool IsAndWithShiftOp = false;
00454   if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
00455     if (Op1.getOperand(0).getOpcode() == ISD::SHL ||
00456         Op1.getOperand(0).getOpcode() == ISD::SRL) {
00457       if (isIntImmediate(Op1.getOperand(0).getOperand(1), Value)) {
00458         SH = Op1.getOperand(0).getOpcode() == ISD::SHL ? Value : 32 - Value;
00459         IsAndWithShiftOp = true;
00460       }
00461     } else if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
00462                Op0.getOperand(0).getOpcode() == ISD::SRL) {
00463       if (isIntImmediate(Op0.getOperand(0).getOperand(1), Value)) {
00464         std::swap(Op0, Op1);
00465         std::swap(TgtMask, InsMask);
00466         SH = Op1.getOperand(0).getOpcode() == ISD::SHL ? Value : 32 - Value;
00467         IsAndWithShiftOp = true;
00468       }
00469     }
00470   }
00471   
00472   // Verify that the Target mask and Insert mask together form a full word mask
00473   // and that the Insert mask is a run of set bits (which implies both are runs
00474   // of set bits).  Given that, Select the arguments and generate the rlwimi
00475   // instruction.
00476   unsigned MB, ME;
00477   if (((TgtMask & InsMask) == 0) && isRunOfOnes(InsMask, MB, ME)) {
00478     bool fullMask = (TgtMask ^ InsMask) == 0xFFFFFFFF;
00479     bool Op0IsAND = Op0Opc == ISD::AND;
00480     // Check for rotlwi / rotrwi here, a special case of bitfield insert
00481     // where both bitfield halves are sourced from the same value.
00482     if (IsRotate && fullMask &&
00483         N->getOperand(0).getOperand(0) == N->getOperand(1).getOperand(0)) {
00484       SDOperand Tmp;
00485       Select(Tmp, N->getOperand(0).getOperand(0));
00486       return CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Tmp,
00487                                    getI32Imm(SH), getI32Imm(0), getI32Imm(31));
00488     }
00489     SDOperand Tmp1, Tmp2;
00490     Select(Tmp1, ((Op0IsAND && fullMask) ? Op0.getOperand(0) : Op0));
00491     Select(Tmp2, (IsAndWithShiftOp ? Op1.getOperand(0).getOperand(0)
00492                                    : Op1.getOperand(0)));
00493     return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Tmp1, Tmp2,
00494                                  getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
00495   }
00496   return 0;
00497 }
00498 
00499 /// SelectAddrImm - Returns true if the address N can be represented by
00500 /// a base register plus a signed 16-bit displacement [r+imm].
00501 bool PPCDAGToDAGISel::SelectAddrImm(SDOperand N, SDOperand &Disp, 
00502                                     SDOperand &Base) {
00503   // If this can be more profitably realized as r+r, fail.
00504   if (SelectAddrIdx(N, Disp, Base))
00505     return false;
00506 
00507   if (N.getOpcode() == ISD::ADD) {
00508     unsigned imm = 0;
00509     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm)) {
00510       Disp = getI32Imm(imm & 0xFFFF);
00511       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
00512         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
00513       } else {
00514         Base = N.getOperand(0);
00515       }
00516       return true; // [r+i]
00517     } else if (N.getOperand(1).getOpcode() == PPCISD::Lo) {
00518       // Match LOAD (ADD (X, Lo(G))).
00519       assert(!cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getValue()
00520              && "Cannot handle constant offsets yet!");
00521       Disp = N.getOperand(1).getOperand(0);  // The global address.
00522       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
00523              Disp.getOpcode() == ISD::TargetConstantPool);
00524       Base = N.getOperand(0);
00525       return true;  // [&g+r]
00526     }
00527   } else if (N.getOpcode() == ISD::OR) {
00528     unsigned imm = 0;
00529     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm)) {
00530       // If this is an or of disjoint bitfields, we can codegen this as an add
00531       // (for better address arithmetic) if the LHS and RHS of the OR are
00532       // provably disjoint.
00533       uint64_t LHSKnownZero, LHSKnownOne;
00534       PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
00535                                     LHSKnownZero, LHSKnownOne);
00536       if ((LHSKnownZero|~imm) == ~0U) {
00537         // If all of the bits are known zero on the LHS or RHS, the add won't
00538         // carry.
00539         Base = N.getOperand(0);
00540         Disp = getI32Imm(imm & 0xFFFF);
00541         return true;
00542       }
00543     }
00544   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
00545     // Loading from a constant address.
00546     int Addr = (int)CN->getValue();
00547     
00548     // If this address fits entirely in a 16-bit sext immediate field, codegen
00549     // this as "d, 0"
00550     if (Addr == (short)Addr) {
00551       Disp = getI32Imm(Addr);
00552       Base = CurDAG->getRegister(PPC::R0, MVT::i32);
00553       return true;
00554     }
00555     
00556     // Otherwise, break this down into an LIS + disp.
00557     Disp = getI32Imm((short)Addr);
00558     Base = CurDAG->getConstant(Addr - (signed short)Addr, MVT::i32);
00559     return true;
00560   }
00561   
00562   Disp = getI32Imm(0);
00563   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
00564     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
00565   else
00566     Base = N;
00567   return true;      // [r+0]
00568 }
00569 
00570 /// SelectAddrIdx - Given the specified addressed, check to see if it can be
00571 /// represented as an indexed [r+r] operation.  Returns false if it can
00572 /// be represented by [r+imm], which are preferred.
00573 bool PPCDAGToDAGISel::SelectAddrIdx(SDOperand N, SDOperand &Base, 
00574                                     SDOperand &Index) {
00575   unsigned imm = 0;
00576   if (N.getOpcode() == ISD::ADD) {
00577     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm))
00578       return false;    // r+i
00579     if (N.getOperand(1).getOpcode() == PPCISD::Lo)
00580       return false;    // r+i
00581     
00582     Base = N.getOperand(0);
00583     Index = N.getOperand(1);
00584     return true;
00585   } else if (N.getOpcode() == ISD::OR) {
00586     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm))
00587       return false;    // r+i can fold it if we can.
00588     
00589     // If this is an or of disjoint bitfields, we can codegen this as an add
00590     // (for better address arithmetic) if the LHS and RHS of the OR are provably
00591     // disjoint.
00592     uint64_t LHSKnownZero, LHSKnownOne;
00593     uint64_t RHSKnownZero, RHSKnownOne;
00594     PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
00595                                   LHSKnownZero, LHSKnownOne);
00596     
00597     if (LHSKnownZero) {
00598       PPCLowering.ComputeMaskedBits(N.getOperand(1), ~0U,
00599                                     RHSKnownZero, RHSKnownOne);
00600       // If all of the bits are known zero on the LHS or RHS, the add won't
00601       // carry.
00602       if ((LHSKnownZero | RHSKnownZero) == ~0U) {
00603         Base = N.getOperand(0);
00604         Index = N.getOperand(1);
00605         return true;
00606       }
00607     }
00608   }
00609   
00610   return false;
00611 }
00612 
00613 /// SelectAddrIdxOnly - Given the specified addressed, force it to be
00614 /// represented as an indexed [r+r] operation.
00615 bool PPCDAGToDAGISel::SelectAddrIdxOnly(SDOperand N, SDOperand &Base, 
00616                                         SDOperand &Index) {
00617   // Check to see if we can easily represent this as an [r+r] address.  This
00618   // will fail if it thinks that the address is more profitably represented as
00619   // reg+imm, e.g. where imm = 0.
00620   if (SelectAddrIdx(N, Base, Index))
00621     return true;
00622   
00623   // If the operand is an addition, always emit this as [r+r], since this is
00624   // better (for code size, and execution, as the memop does the add for free)
00625   // than emitting an explicit add.
00626   if (N.getOpcode() == ISD::ADD) {
00627     Base = N.getOperand(0);
00628     Index = N.getOperand(1);
00629     return true;
00630   }
00631   
00632   // Otherwise, do it the hard way, using R0 as the base register.
00633   Base = CurDAG->getRegister(PPC::R0, MVT::i32);
00634   Index = N;
00635   return true;
00636 }
00637 
00638 /// SelectAddrImmShift - Returns true if the address N can be represented by
00639 /// a base register plus a signed 14-bit displacement [r+imm*4].  Suitable
00640 /// for use by STD and friends.
00641 bool PPCDAGToDAGISel::SelectAddrImmShift(SDOperand N, SDOperand &Disp, 
00642                                          SDOperand &Base) {
00643   // If this can be more profitably realized as r+r, fail.
00644   if (SelectAddrIdx(N, Disp, Base))
00645     return false;
00646   
00647   if (N.getOpcode() == ISD::ADD) {
00648     unsigned imm = 0;
00649     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm) &&
00650         (imm & 3) == 0) {
00651       Disp = getI32Imm((imm & 0xFFFF) >> 2);
00652       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
00653         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
00654       } else {
00655         Base = N.getOperand(0);
00656       }
00657       return true; // [r+i]
00658     } else if (N.getOperand(1).getOpcode() == PPCISD::Lo) {
00659       // Match LOAD (ADD (X, Lo(G))).
00660       assert(!cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getValue()
00661              && "Cannot handle constant offsets yet!");
00662       Disp = N.getOperand(1).getOperand(0);  // The global address.
00663       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
00664              Disp.getOpcode() == ISD::TargetConstantPool);
00665       Base = N.getOperand(0);
00666       return true;  // [&g+r]
00667     }
00668   } else if (N.getOpcode() == ISD::OR) {
00669     unsigned imm = 0;
00670     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm) &&
00671         (imm & 3) == 0) {
00672       // If this is an or of disjoint bitfields, we can codegen this as an add
00673       // (for better address arithmetic) if the LHS and RHS of the OR are
00674       // provably disjoint.
00675       uint64_t LHSKnownZero, LHSKnownOne;
00676       PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
00677                                     LHSKnownZero, LHSKnownOne);
00678       if ((LHSKnownZero|~imm) == ~0U) {
00679         // If all of the bits are known zero on the LHS or RHS, the add won't
00680         // carry.
00681         Base = N.getOperand(0);
00682         Disp = getI32Imm((imm & 0xFFFF) >> 2);
00683         return true;
00684       }
00685     }
00686   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
00687     // Loading from a constant address.
00688     int Addr = (int)CN->getValue();
00689     if ((Addr & 3) == 0) {
00690       // If this address fits entirely in a 16-bit sext immediate field, codegen
00691       // this as "d, 0"
00692       if (Addr == (short)Addr) {
00693         Disp = getI32Imm(Addr >> 2);
00694         Base = CurDAG->getRegister(PPC::R0, MVT::i32);
00695         return true;
00696       }
00697       
00698       // Otherwise, break this down into an LIS + disp.
00699       Disp = getI32Imm((short)Addr >> 2);
00700       Base = CurDAG->getConstant(Addr - (signed short)Addr, MVT::i32);
00701       return true;
00702     }
00703   }
00704   
00705   Disp = getI32Imm(0);
00706   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
00707     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
00708   else
00709     Base = N;
00710   return true;      // [r+0]
00711 }
00712 
00713 
00714 /// SelectCC - Select a comparison of the specified values with the specified
00715 /// condition code, returning the CR# of the expression.
00716 SDOperand PPCDAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
00717                                     ISD::CondCode CC) {
00718   // Always select the LHS.
00719   Select(LHS, LHS);
00720 
00721   // Use U to determine whether the SETCC immediate range is signed or not.
00722   if (MVT::isInteger(LHS.getValueType())) {
00723     bool U = ISD::isUnsignedIntSetCC(CC);
00724     unsigned Imm;
00725     if (isIntImmediate(RHS, Imm) && 
00726         ((U && isUInt16(Imm)) || (!U && isInt16(Imm))))
00727       return SDOperand(CurDAG->getTargetNode(U ? PPC::CMPLWI : PPC::CMPWI,
00728                                     MVT::i32, LHS, getI32Imm(Imm & 0xFFFF)), 0);
00729     Select(RHS, RHS);
00730     return SDOperand(CurDAG->getTargetNode(U ? PPC::CMPLW : PPC::CMPW, MVT::i32,
00731                                            LHS, RHS), 0);
00732   } else if (LHS.getValueType() == MVT::f32) {
00733     Select(RHS, RHS);
00734     return SDOperand(CurDAG->getTargetNode(PPC::FCMPUS, MVT::i32, LHS, RHS), 0);
00735   } else {
00736     Select(RHS, RHS);
00737     return SDOperand(CurDAG->getTargetNode(PPC::FCMPUD, MVT::i32, LHS, RHS), 0);
00738   }
00739 }
00740 
00741 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
00742 /// to Condition.
00743 static unsigned getBCCForSetCC(ISD::CondCode CC) {
00744   switch (CC) {
00745   default: assert(0 && "Unknown condition!"); abort();
00746   case ISD::SETOEQ:    // FIXME: This is incorrect see PR642.
00747   case ISD::SETEQ:  return PPC::BEQ;
00748   case ISD::SETONE:    // FIXME: This is incorrect see PR642.
00749   case ISD::SETNE:  return PPC::BNE;
00750   case ISD::SETOLT:    // FIXME: This is incorrect see PR642.
00751   case ISD::SETULT:
00752   case ISD::SETLT:  return PPC::BLT;
00753   case ISD::SETOLE:    // FIXME: This is incorrect see PR642.
00754   case ISD::SETULE:
00755   case ISD::SETLE:  return PPC::BLE;
00756   case ISD::SETOGT:    // FIXME: This is incorrect see PR642.
00757   case ISD::SETUGT:
00758   case ISD::SETGT:  return PPC::BGT;
00759   case ISD::SETOGE:    // FIXME: This is incorrect see PR642.
00760   case ISD::SETUGE:
00761   case ISD::SETGE:  return PPC::BGE;
00762     
00763   case ISD::SETO:   return PPC::BUN;
00764   case ISD::SETUO:  return PPC::BNU;
00765   }
00766   return 0;
00767 }
00768 
00769 /// getCRIdxForSetCC - Return the index of the condition register field
00770 /// associated with the SetCC condition, and whether or not the field is
00771 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
00772 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool& Inv) {
00773   switch (CC) {
00774   default: assert(0 && "Unknown condition!"); abort();
00775   case ISD::SETOLT:  // FIXME: This is incorrect see PR642.
00776   case ISD::SETULT:
00777   case ISD::SETLT:  Inv = false;  return 0;
00778   case ISD::SETOGE:  // FIXME: This is incorrect see PR642.
00779   case ISD::SETUGE:
00780   case ISD::SETGE:  Inv = true;   return 0;
00781   case ISD::SETOGT:  // FIXME: This is incorrect see PR642.
00782   case ISD::SETUGT:
00783   case ISD::SETGT:  Inv = false;  return 1;
00784   case ISD::SETOLE:  // FIXME: This is incorrect see PR642.
00785   case ISD::SETULE:
00786   case ISD::SETLE:  Inv = true;   return 1;
00787   case ISD::SETOEQ:  // FIXME: This is incorrect see PR642.
00788   case ISD::SETEQ:  Inv = false;  return 2;
00789   case ISD::SETONE:  // FIXME: This is incorrect see PR642.
00790   case ISD::SETNE:  Inv = true;   return 2;
00791   case ISD::SETO:   Inv = true;   return 3;
00792   case ISD::SETUO:  Inv = false;  return 3;
00793   }
00794   return 0;
00795 }
00796 
00797 SDOperand PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
00798   SDNode *N = Op.Val;
00799   unsigned Imm;
00800   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
00801   if (isIntImmediate(N->getOperand(1), Imm)) {
00802     // We can codegen setcc op, imm very efficiently compared to a brcond.
00803     // Check for those cases here.
00804     // setcc op, 0
00805     if (Imm == 0) {
00806       SDOperand Op;
00807       Select(Op, N->getOperand(0));
00808       switch (CC) {
00809       default: break;
00810       case ISD::SETEQ:
00811         Op = SDOperand(CurDAG->getTargetNode(PPC::CNTLZW, MVT::i32, Op), 0);
00812         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(27),
00813                                     getI32Imm(5), getI32Imm(31));
00814       case ISD::SETNE: {
00815         SDOperand AD =
00816           SDOperand(CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
00817                                           Op, getI32Imm(~0U)), 0);
00818         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op, 
00819                                     AD.getValue(1));
00820       }
00821       case ISD::SETLT:
00822         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(1),
00823                                     getI32Imm(31), getI32Imm(31));
00824       case ISD::SETGT: {
00825         SDOperand T =
00826           SDOperand(CurDAG->getTargetNode(PPC::NEG, MVT::i32, Op), 0);
00827         T = SDOperand(CurDAG->getTargetNode(PPC::ANDC, MVT::i32, T, Op), 0);
00828         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, T, getI32Imm(1),
00829                                     getI32Imm(31), getI32Imm(31));
00830       }
00831       }
00832     } else if (Imm == ~0U) {        // setcc op, -1
00833       SDOperand Op;
00834       Select(Op, N->getOperand(0));
00835       switch (CC) {
00836       default: break;
00837       case ISD::SETEQ:
00838         Op = SDOperand(CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
00839                                              Op, getI32Imm(1)), 0);
00840         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32, 
00841                               SDOperand(CurDAG->getTargetNode(PPC::LI, MVT::i32,
00842                                                               getI32Imm(0)), 0),
00843                                     Op.getValue(1));
00844       case ISD::SETNE: {
00845         Op = SDOperand(CurDAG->getTargetNode(PPC::NOR, MVT::i32, Op, Op), 0);
00846         SDNode *AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
00847                                            Op, getI32Imm(~0U));
00848         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDOperand(AD, 0), Op, 
00849                                     SDOperand(AD, 1));
00850       }
00851       case ISD::SETLT: {
00852         SDOperand AD = SDOperand(CurDAG->getTargetNode(PPC::ADDI, MVT::i32, Op,
00853                                                        getI32Imm(1)), 0);
00854         SDOperand AN = SDOperand(CurDAG->getTargetNode(PPC::AND, MVT::i32, AD,
00855                                                        Op), 0);
00856         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, AN, getI32Imm(1),
00857                                     getI32Imm(31), getI32Imm(31));
00858       }
00859       case ISD::SETGT:
00860         Op = SDOperand(CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Op,
00861                                              getI32Imm(1), getI32Imm(31),
00862                                              getI32Imm(31)), 0);
00863         return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op, getI32Imm(1));
00864       }
00865     }
00866   }
00867   
00868   bool Inv;
00869   unsigned Idx = getCRIdxForSetCC(CC, Inv);
00870   SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
00871   SDOperand IntCR;
00872   
00873   // Force the ccreg into CR7.
00874   SDOperand CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
00875   
00876   SDOperand InFlag(0, 0);  // Null incoming flag value.
00877   CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), CR7Reg, CCReg, 
00878                                InFlag).getValue(1);
00879   
00880   if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
00881     IntCR = SDOperand(CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32, CR7Reg,
00882                                             CCReg), 0);
00883   else
00884     IntCR = SDOperand(CurDAG->getTargetNode(PPC::MFCR, MVT::i32, CCReg), 0);
00885   
00886   if (!Inv) {
00887     return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, IntCR,
00888                                 getI32Imm((32-(3-Idx)) & 31),
00889                                 getI32Imm(31), getI32Imm(31));
00890   } else {
00891     SDOperand Tmp =
00892       SDOperand(CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, IntCR,
00893                                       getI32Imm((32-(3-Idx)) & 31),
00894                                       getI32Imm(31),getI32Imm(31)), 0);
00895     return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1));
00896   }
00897 }
00898 
00899 /// isCallCompatibleAddress - Return true if the specified 32-bit value is
00900 /// representable in the immediate field of a Bx instruction.
00901 static bool isCallCompatibleAddress(ConstantSDNode *C) {
00902   int Addr = C->getValue();
00903   if (Addr & 3) return false;  // Low 2 bits are implicitly zero.
00904   return (Addr << 6 >> 6) == Addr;  // Top 6 bits have to be sext of immediate.
00905 }
00906 
00907 SDOperand PPCDAGToDAGISel::SelectCALL(SDOperand Op) {
00908   SDNode *N = Op.Val;
00909   SDOperand Chain;
00910   Select(Chain, N->getOperand(0));
00911   
00912   unsigned CallOpcode;
00913   std::vector<SDOperand> CallOperands;
00914   
00915   if (GlobalAddressSDNode *GASD =
00916       dyn_cast<GlobalAddressSDNode>(N->getOperand(1))) {
00917     CallOpcode = PPC::BL;
00918     CallOperands.push_back(N->getOperand(1));
00919   } else if (ExternalSymbolSDNode *ESSDN =
00920              dyn_cast<ExternalSymbolSDNode>(N->getOperand(1))) {
00921     CallOpcode = PPC::BL;
00922     CallOperands.push_back(N->getOperand(1));
00923   } else if (isa<ConstantSDNode>(N->getOperand(1)) &&
00924              isCallCompatibleAddress(cast<ConstantSDNode>(N->getOperand(1)))) {
00925     ConstantSDNode *C = cast<ConstantSDNode>(N->getOperand(1));
00926     CallOpcode = PPC::BLA;
00927     CallOperands.push_back(getI32Imm((int)C->getValue() >> 2));
00928   } else {
00929     // Copy the callee address into the CTR register.
00930     SDOperand Callee;
00931     Select(Callee, N->getOperand(1));
00932     Chain = SDOperand(CurDAG->getTargetNode(PPC::MTCTR, MVT::Other, Callee,
00933                                             Chain), 0);
00934     
00935     // Copy the callee address into R12 on darwin.
00936     SDOperand R12 = CurDAG->getRegister(PPC::R12, MVT::i32);
00937     Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, R12, Callee);
00938 
00939     CallOperands.push_back(R12);
00940     CallOpcode = PPC::BCTRL;
00941   }
00942   
00943   unsigned GPR_idx = 0, FPR_idx = 0;
00944   static const unsigned GPR[] = {
00945     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
00946     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
00947   };
00948   static const unsigned FPR[] = {
00949     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
00950     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
00951   };
00952   
00953   SDOperand InFlag;  // Null incoming flag value.
00954   
00955   for (unsigned i = 2, e = N->getNumOperands(); i != e; ++i) {
00956     unsigned DestReg = 0;
00957     MVT::ValueType RegTy = N->getOperand(i).getValueType();
00958     if (RegTy == MVT::i32) {
00959       assert(GPR_idx < 8 && "Too many int args");
00960       DestReg = GPR[GPR_idx++];
00961     } else {
00962       assert(MVT::isFloatingPoint(N->getOperand(i).getValueType()) &&
00963              "Unpromoted integer arg?");
00964       assert(FPR_idx < 13 && "Too many fp args");
00965       DestReg = FPR[FPR_idx++];
00966     }
00967     
00968     if (N->getOperand(i).getOpcode() != ISD::UNDEF) {
00969       SDOperand Val;
00970       Select(Val, N->getOperand(i));
00971       Chain = CurDAG->getCopyToReg(Chain, DestReg, Val, InFlag);
00972       InFlag = Chain.getValue(1);
00973       CallOperands.push_back(CurDAG->getRegister(DestReg, RegTy));
00974     }
00975   }
00976   
00977   // Finally, once everything is in registers to pass to the call, emit the
00978   // call itself.
00979   if (InFlag.Val)
00980     CallOperands.push_back(InFlag);   // Strong dep on register copies.
00981   else
00982     CallOperands.push_back(Chain);    // Weak dep on whatever occurs before
00983   Chain = SDOperand(CurDAG->getTargetNode(CallOpcode, MVT::Other, MVT::Flag,
00984                                           CallOperands), 0);
00985   
00986   std::vector<SDOperand> CallResults;
00987   
00988   // If the call has results, copy the values out of the ret val registers.
00989   switch (N->getValueType(0)) {
00990     default: assert(0 && "Unexpected ret value!");
00991     case MVT::Other: break;
00992     case MVT::i32:
00993       if (N->getValueType(1) == MVT::i32) {
00994         Chain = CurDAG->getCopyFromReg(Chain, PPC::R4, MVT::i32, 
00995                                        Chain.getValue(1)).getValue(1);
00996         CallResults.push_back(Chain.getValue(0));
00997         Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32,
00998                                        Chain.getValue(2)).getValue(1);
00999         CallResults.push_back(Chain.getValue(0));
01000       } else {
01001         Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32,
01002                                        Chain.getValue(1)).getValue(1);
01003         CallResults.push_back(Chain.getValue(0));
01004       }
01005       break;
01006     case MVT::f32:
01007     case MVT::f64:
01008       Chain = CurDAG->getCopyFromReg(Chain, PPC::F1, N->getValueType(0),
01009                                      Chain.getValue(1)).getValue(1);
01010       CallResults.push_back(Chain.getValue(0));
01011       break;
01012   }
01013   
01014   CallResults.push_back(Chain);
01015   for (unsigned i = 0, e = CallResults.size(); i != e; ++i)
01016     CodeGenMap[Op.getValue(i)] = CallResults[i];
01017   return CallResults[Op.ResNo];
01018 }
01019 
01020 // Select - Convert the specified operand from a target-independent to a
01021 // target-specific node if it hasn't already been changed.
01022 void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
01023   SDNode *N = Op.Val;
01024   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
01025       N->getOpcode() < PPCISD::FIRST_NUMBER) {
01026     Result = Op;
01027     return;   // Already selected.
01028   }
01029 
01030   // If this has already been converted, use it.
01031   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
01032   if (CGMI != CodeGenMap.end()) {
01033     Result = CGMI->second;
01034     return;
01035   }
01036   
01037   switch (N->getOpcode()) {
01038   default: break;
01039   case ISD::SETCC:
01040     Result = SelectSETCC(Op);
01041     return;
01042   case PPCISD::CALL:
01043     Result = SelectCALL(Op);
01044     return;
01045   case PPCISD::GlobalBaseReg:
01046     Result = getGlobalBaseReg();
01047     return;
01048     
01049   case ISD::FrameIndex: {
01050     int FI = cast<FrameIndexSDNode>(N)->getIndex();
01051     if (N->hasOneUse()) {
01052       Result = CurDAG->SelectNodeTo(N, PPC::ADDI, MVT::i32,
01053                                     CurDAG->getTargetFrameIndex(FI, MVT::i32),
01054                                     getI32Imm(0));
01055       return;
01056     }
01057     Result = CodeGenMap[Op] = 
01058       SDOperand(CurDAG->getTargetNode(PPC::ADDI, MVT::i32,
01059                                       CurDAG->getTargetFrameIndex(FI, MVT::i32),
01060                                       getI32Imm(0)), 0);
01061     return;
01062   }
01063 
01064   case PPCISD::MFCR: {
01065     SDOperand InFlag;
01066     Select(InFlag, N->getOperand(1));
01067     // Use MFOCRF if supported.
01068     if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
01069       Result = SDOperand(CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32,
01070                                                N->getOperand(0), InFlag), 0);
01071     else
01072       Result = SDOperand(CurDAG->getTargetNode(PPC::MFCR, MVT::i32, InFlag), 0);
01073     CodeGenMap[Op] = Result;
01074     return;
01075   }
01076     
01077   case ISD::SDIV: {
01078     // FIXME: since this depends on the setting of the carry flag from the srawi
01079     //        we should really be making notes about that for the scheduler.
01080     // FIXME: It sure would be nice if we could cheaply recognize the 
01081     //        srl/add/sra pattern the dag combiner will generate for this as
01082     //        sra/addze rather than having to handle sdiv ourselves.  oh well.
01083     unsigned Imm;
01084     if (isIntImmediate(N->getOperand(1), Imm)) {
01085       SDOperand N0;
01086       Select(N0, N->getOperand(0));
01087       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
01088         SDNode *Op =
01089           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
01090                                 N0, getI32Imm(Log2_32(Imm)));
01091         Result = CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32, 
01092                                       SDOperand(Op, 0), SDOperand(Op, 1));
01093       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
01094         SDNode *Op =
01095           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
01096                                 N0, getI32Imm(Log2_32(-Imm)));
01097         SDOperand PT =
01098           SDOperand(CurDAG->getTargetNode(PPC::ADDZE, MVT::i32,
01099                                           SDOperand(Op, 0), SDOperand(Op, 1)),
01100                     0);
01101         Result = CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT);
01102       }
01103       return;
01104     }
01105     
01106     // Other cases are autogenerated.
01107     break;
01108   }
01109   case ISD::AND: {
01110     unsigned Imm, Imm2;
01111     // If this is an and of a value rotated between 0 and 31 bits and then and'd
01112     // with a mask, emit rlwinm
01113     if (isIntImmediate(N->getOperand(1), Imm) && (isShiftedMask_32(Imm) ||
01114                                                   isShiftedMask_32(~Imm))) {
01115       SDOperand Val;
01116       unsigned SH, MB, ME;
01117       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
01118         Select(Val, N->getOperand(0).getOperand(0));
01119       } else if (Imm == 0) {
01120         // AND X, 0 -> 0, not "rlwinm 32".
01121         Select(Result, N->getOperand(1));
01122         return ;
01123       } else {        
01124         Select(Val, N->getOperand(0));
01125         isRunOfOnes(Imm, MB, ME);
01126         SH = 0;
01127       }
01128       Result = CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Val,
01129                                     getI32Imm(SH), getI32Imm(MB),
01130                                     getI32Imm(ME));
01131       return;
01132     }
01133     // ISD::OR doesn't get all the bitfield insertion fun.
01134     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) is a bitfield insert
01135     if (isIntImmediate(N->getOperand(1), Imm) && 
01136         N->getOperand(0).getOpcode() == ISD::OR &&
01137         isIntImmediate(N->getOperand(0).getOperand(1), Imm2)) {
01138       unsigned MB, ME;
01139       Imm = ~(Imm^Imm2);
01140       if (isRunOfOnes(Imm, MB, ME)) {
01141         SDOperand Tmp1, Tmp2;
01142         Select(Tmp1, N->getOperand(0).getOperand(0));
01143         Select(Tmp2, N->getOperand(0).getOperand(1));
01144         Result = SDOperand(CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32,
01145                                                  Tmp1, Tmp2,
01146                                                  getI32Imm(0), getI32Imm(MB),
01147                                                  getI32Imm(ME)), 0);
01148         return;
01149       }
01150     }
01151     
01152     // Other cases are autogenerated.
01153     break;
01154   }
01155   case ISD::OR:
01156     if (SDNode *I = SelectBitfieldInsert(N)) {
01157       Result = CodeGenMap[Op] = SDOperand(I, 0);
01158       return;
01159     }
01160       
01161     // Other cases are autogenerated.
01162     break;
01163   case ISD::SHL: {
01164     unsigned Imm, SH, MB, ME;
01165     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
01166         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
01167       SDOperand Val;
01168       Select(Val, N->getOperand(0).getOperand(0));
01169       Result = CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, 
01170                                     Val, getI32Imm(SH), getI32Imm(MB),
01171                                     getI32Imm(ME));
01172       return;
01173     }
01174     
01175     // Other cases are autogenerated.
01176     break;
01177   }
01178   case ISD::SRL: {
01179     unsigned Imm, SH, MB, ME;
01180     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
01181         isRotateAndMask(N, Imm, true, SH, MB, ME)) { 
01182       SDOperand Val;
01183       Select(Val, N->getOperand(0).getOperand(0));
01184       Result = CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, 
01185                                     Val, getI32Imm(SH & 0x1F), getI32Imm(MB),
01186                                     getI32Imm(ME));
01187       return;
01188     }
01189     
01190     // Other cases are autogenerated.
01191     break;
01192   }
01193   case ISD::SELECT_CC: {
01194     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
01195     
01196     // handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
01197     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
01198       if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
01199         if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
01200           if (N1C->isNullValue() && N3C->isNullValue() &&
01201               N2C->getValue() == 1ULL && CC == ISD::SETNE) {
01202             SDOperand LHS;
01203             Select(LHS, N->getOperand(0));
01204             SDNode *Tmp =
01205               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
01206                                     LHS, getI32Imm(~0U));
01207             Result = CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
01208                                           SDOperand(Tmp, 0), LHS,
01209                                           SDOperand(Tmp, 1));
01210             return;
01211           }
01212 
01213     SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
01214     unsigned BROpc = getBCCForSetCC(CC);
01215 
01216     bool isFP = MVT::isFloatingPoint(N->getValueType(0));
01217     unsigned SelectCCOp;
01218     if (MVT::isInteger(N->getValueType(0)))
01219       SelectCCOp = PPC::SELECT_CC_Int;
01220     else if (N->getValueType(0) == MVT::f32)
01221       SelectCCOp = PPC::SELECT_CC_F4;
01222     else if (N->getValueType(0) == MVT::f64)
01223       SelectCCOp = PPC::SELECT_CC_F8;
01224     else
01225       SelectCCOp = PPC::SELECT_CC_VRRC;
01226 
01227     SDOperand N2, N3;
01228     Select(N2, N->getOperand(2));
01229     Select(N3, N->getOperand(3));
01230     Result = CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), CCReg,
01231                                   N2, N3, getI32Imm(BROpc));
01232     return;
01233   }
01234   case ISD::BR_CC: {
01235     SDOperand Chain;
01236     Select(Chain, N->getOperand(0));
01237     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
01238     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
01239     Result = CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other, 
01240                                   CondCode, getI32Imm(getBCCForSetCC(CC)), 
01241                                   N->getOperand(4), Chain);
01242     return;
01243   }
01244   }
01245   
01246   SelectCode(Result, Op);
01247 }
01248 
01249 
01250 /// createPPCISelDag - This pass converts a legalized DAG into a 
01251 /// PowerPC-specific DAG, ready for instruction scheduling.
01252 ///
01253 FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
01254   return new PPCDAGToDAGISel(TM);
01255 }
01256