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