lib/Target/PowerPC/PPCISelDAGToDAG.cpp

   1 //===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a pattern matching instruction selector for PowerPC,
  11 // converting from a legalized dag to a PPC dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "PPC.h"
  16 #include "MCTargetDesc/PPCPredicates.h"
  17 #include "PPCMachineFunctionInfo.h"
  18 #include "PPCTargetMachine.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineInstrBuilder.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/IR/Constants.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/GlobalAlias.h"
  27 #include "llvm/IR/GlobalValue.h"
  28 #include "llvm/IR/GlobalVariable.h"
  29 #include "llvm/IR/Intrinsics.h"
  30 #include "llvm/IR/Module.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34 #include "llvm/Support/MathExtras.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include "llvm/Target/TargetOptions.h"
  37 using namespace llvm;
  38
  39 #define DEBUG_TYPE "ppc-codegen"
  40
  41 // FIXME: Remove this once the bug has been fixed!
  42 cl::opt<bool> ANDIGlueBug("expose-ppc-andi-glue-bug",
  43 cl::desc("expose the ANDI glue bug on PPC"), cl::Hidden);
  44
  45 cl::opt<bool> UseBitPermRewriter("ppc-use-bit-perm-rewriter", cl::init(true),
  46   cl::desc("use aggressive ppc isel for bit permutations"), cl::Hidden);
  47 cl::opt<bool> BPermRewriterNoMasking("ppc-bit-perm-rewriter-stress-rotates",
  48   cl::desc("stress rotate selection in aggressive ppc isel for "
  49            "bit permutations"), cl::Hidden);
  50
  51 namespace llvm {
  52   void initializePPCDAGToDAGISelPass(PassRegistry&);
  53 }
  54
  55 namespace {
  56   //===--------------------------------------------------------------------===//
  57   /// PPCDAGToDAGISel - PPC specific code to select PPC machine
  58   /// instructions for SelectionDAG operations.
  59   ///
  60   class PPCDAGToDAGISel : public SelectionDAGISel {
  61     const PPCTargetMachine &TM;
  62     const PPCTargetLowering *PPCLowering;
  63     const PPCSubtarget *PPCSubTarget;
  64     unsigned GlobalBaseReg;
  65   public:
  66     explicit PPCDAGToDAGISel(PPCTargetMachine &tm)
  67         : SelectionDAGISel(tm), TM(tm),
  68           PPCLowering(TM.getSubtargetImpl()->getTargetLowering()),
  69           PPCSubTarget(TM.getSubtargetImpl()) {
  70       initializePPCDAGToDAGISelPass(*PassRegistry::getPassRegistry());
  71     }
  72
  73     bool runOnMachineFunction(MachineFunction &MF) override {
  74       // Make sure we re-emit a set of the global base reg if necessary
  75       GlobalBaseReg = 0;
  76       PPCLowering = TM.getSubtargetImpl()->getTargetLowering();
  77       PPCSubTarget = TM.getSubtargetImpl();
  78       SelectionDAGISel::runOnMachineFunction(MF);
  79
  80       if (!PPCSubTarget->isSVR4ABI())
  81         InsertVRSaveCode(MF);
  82
  83       return true;
  84     }
  85
  86     void PostprocessISelDAG() override;
  87
  88     /// getI32Imm - Return a target constant with the specified value, of type
  89     /// i32.
  90     inline SDValue getI32Imm(unsigned Imm) {
  91       return CurDAG->getTargetConstant(Imm, MVT::i32);
  92     }
  93
  94     /// getI64Imm - Return a target constant with the specified value, of type
  95     /// i64.
  96     inline SDValue getI64Imm(uint64_t Imm) {
  97       return CurDAG->getTargetConstant(Imm, MVT::i64);
  98     }
  99
 100     /// getSmallIPtrImm - Return a target constant of pointer type.
 101     inline SDValue getSmallIPtrImm(unsigned Imm) {
 102       return CurDAG->getTargetConstant(Imm, PPCLowering->getPointerTy());
 103     }
 104
 105     /// isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s
 106     /// with any number of 0s on either side.  The 1s are allowed to wrap from
 107     /// LSB to MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.
 108     /// 0x0F0F0000 is not, since all 1s are not contiguous.
 109     static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME);
 110
 111
 112     /// isRotateAndMask - Returns true if Mask and Shift can be folded into a
 113     /// rotate and mask opcode and mask operation.
 114     static bool isRotateAndMask(SDNode *N, unsigned Mask, bool isShiftMask,
 115                                 unsigned &SH, unsigned &MB, unsigned &ME);
 116
 117     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
 118     /// base register.  Return the virtual register that holds this value.
 119     SDNode *getGlobalBaseReg();
 120
 121     SDNode *getFrameIndex(SDNode *SN, SDNode *N, unsigned Offset = 0);
 122
 123     // Select - Convert the specified operand from a target-independent to a
 124     // target-specific node if it hasn't already been changed.
 125     SDNode *Select(SDNode *N) override;
 126
 127     SDNode *SelectBitfieldInsert(SDNode *N);
 128     SDNode *SelectBitPermutation(SDNode *N);
 129
 130     /// SelectCC - Select a comparison of the specified values with the
 131     /// specified condition code, returning the CR# of the expression.
 132     SDValue SelectCC(SDValue LHS, SDValue RHS, ISD::CondCode CC, SDLoc dl);
 133
 134     /// SelectAddrImm - Returns true if the address N can be represented by
 135     /// a base register plus a signed 16-bit displacement [r+imm].
 136     bool SelectAddrImm(SDValue N, SDValue &Disp,
 137                        SDValue &Base) {
 138       return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, false);
 139     }
 140
 141     /// SelectAddrImmOffs - Return true if the operand is valid for a preinc
 142     /// immediate field.  Note that the operand at this point is already the
 143     /// result of a prior SelectAddressRegImm call.
 144     bool SelectAddrImmOffs(SDValue N, SDValue &Out) const {
 145       if (N.getOpcode() == ISD::TargetConstant ||
 146           N.getOpcode() == ISD::TargetGlobalAddress) {
 147         Out = N;
 148         return true;
 149       }
 150
 151       return false;
 152     }
 153
 154     /// SelectAddrIdx - Given the specified addressed, check to see if it can be
 155     /// represented as an indexed [r+r] operation.  Returns false if it can
 156     /// be represented by [r+imm], which are preferred.
 157     bool SelectAddrIdx(SDValue N, SDValue &Base, SDValue &Index) {
 158       return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG);
 159     }
 160
 161     /// SelectAddrIdxOnly - Given the specified addressed, force it to be
 162     /// represented as an indexed [r+r] operation.
 163     bool SelectAddrIdxOnly(SDValue N, SDValue &Base, SDValue &Index) {
 164       return PPCLowering->SelectAddressRegRegOnly(N, Base, Index, *CurDAG);
 165     }
 166
 167     /// SelectAddrImmX4 - Returns true if the address N can be represented by
 168     /// a base register plus a signed 16-bit displacement that is a multiple of 4.
 169     /// Suitable for use by STD and friends.
 170     bool SelectAddrImmX4(SDValue N, SDValue &Disp, SDValue &Base) {
 171       return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, true);
 172     }
 173
 174     // Select an address into a single register.
 175     bool SelectAddr(SDValue N, SDValue &Base) {
 176       Base = N;
 177       return true;
 178     }
 179
 180     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
 181     /// inline asm expressions.  It is always correct to compute the value into
 182     /// a register.  The case of adding a (possibly relocatable) constant to a
 183     /// register can be improved, but it is wrong to substitute Reg+Reg for
 184     /// Reg in an asm, because the load or store opcode would have to change.
 185     bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 186                                       char ConstraintCode,
 187                                       std::vector<SDValue> &OutOps) override {
 188       // We need to make sure that this one operand does not end up in r0
 189       // (because we might end up lowering this as 0(%op)).
 190       const TargetRegisterInfo *TRI = TM.getSubtargetImpl()->getRegisterInfo();
 191       const TargetRegisterClass *TRC = TRI->getPointerRegClass(*MF, /*Kind=*/1);
 192       SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32);
 193       SDValue NewOp =
 194         SDValue(CurDAG->getMachineNode(TargetOpcode::COPY_TO_REGCLASS,
 195                                        SDLoc(Op), Op.getValueType(),
 196                                        Op, RC), 0);
 197
 198       OutOps.push_back(NewOp);
 199       return false;
 200     }
 201
 202     void InsertVRSaveCode(MachineFunction &MF);
 203
 204     const char *getPassName() const override {
 205       return "PowerPC DAG->DAG Pattern Instruction Selection";
 206     }
 207
 208 // Include the pieces autogenerated from the target description.
 209 #include "PPCGenDAGISel.inc"
 210
 211 private:
 212     SDNode *SelectSETCC(SDNode *N);
 213
 214     void PeepholePPC64();
 215     void PeepholePPC64ZExt();
 216     void PeepholeCROps();
 217
 218     bool AllUsersSelectZero(SDNode *N);
 219     void SwapAllSelectUsers(SDNode *N);
 220   };
 221 }
 222
 223 /// InsertVRSaveCode - Once the entire function has been instruction selected,
 224 /// all virtual registers are created and all machine instructions are built,
 225 /// check to see if we need to save/restore VRSAVE.  If so, do it.
 226 void PPCDAGToDAGISel::InsertVRSaveCode(MachineFunction &Fn) {
 227   // Check to see if this function uses vector registers, which means we have to
 228   // save and restore the VRSAVE register and update it with the regs we use.
 229   //
 230   // In this case, there will be virtual registers of vector type created
 231   // by the scheduler.  Detect them now.
 232   bool HasVectorVReg = false;
 233   for (unsigned i = 0, e = RegInfo->getNumVirtRegs(); i != e; ++i) {
 234     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 235     if (RegInfo->getRegClass(Reg) == &PPC::VRRCRegClass) {
 236       HasVectorVReg = true;
 237       break;
 238     }
 239   }
 240   if (!HasVectorVReg) return;  // nothing to do.
 241
 242   // If we have a vector register, we want to emit code into the entry and exit
 243   // blocks to save and restore the VRSAVE register.  We do this here (instead
 244   // of marking all vector instructions as clobbering VRSAVE) for two reasons:
 245   //
 246   // 1. This (trivially) reduces the load on the register allocator, by not
 247   //    having to represent the live range of the VRSAVE register.
 248   // 2. This (more significantly) allows us to create a temporary virtual
 249   //    register to hold the saved VRSAVE value, allowing this temporary to be
 250   //    register allocated, instead of forcing it to be spilled to the stack.
 251
 252   // Create two vregs - one to hold the VRSAVE register that is live-in to the
 253   // function and one for the value after having bits or'd into it.
 254   unsigned InVRSAVE = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
 255   unsigned UpdatedVRSAVE = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
 256
 257   const TargetInstrInfo &TII = *TM.getSubtargetImpl()->getInstrInfo();
 258   MachineBasicBlock &EntryBB = *Fn.begin();
 259   DebugLoc dl;
 260   // Emit the following code into the entry block:
 261   // InVRSAVE = MFVRSAVE
 262   // UpdatedVRSAVE = UPDATE_VRSAVE InVRSAVE
 263   // MTVRSAVE UpdatedVRSAVE
 264   MachineBasicBlock::iterator IP = EntryBB.begin();  // Insert Point
 265   BuildMI(EntryBB, IP, dl, TII.get(PPC::MFVRSAVE), InVRSAVE);
 266   BuildMI(EntryBB, IP, dl, TII.get(PPC::UPDATE_VRSAVE),
 267           UpdatedVRSAVE).addReg(InVRSAVE);
 268   BuildMI(EntryBB, IP, dl, TII.get(PPC::MTVRSAVE)).addReg(UpdatedVRSAVE);
 269
 270   // Find all return blocks, outputting a restore in each epilog.
 271   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 272     if (!BB->empty() && BB->back().isReturn()) {
 273       IP = BB->end(); --IP;
 274
 275       // Skip over all terminator instructions, which are part of the return
 276       // sequence.
 277       MachineBasicBlock::iterator I2 = IP;
 278       while (I2 != BB->begin() && (--I2)->isTerminator())
 279         IP = I2;
 280
 281       // Emit: MTVRSAVE InVRSave
 282       BuildMI(*BB, IP, dl, TII.get(PPC::MTVRSAVE)).addReg(InVRSAVE);
 283     }
 284   }
 285 }
 286
 287
 288 /// getGlobalBaseReg - Output the instructions required to put the
 289 /// base address to use for accessing globals into a register.
 290 ///
 291 SDNode *PPCDAGToDAGISel::getGlobalBaseReg() {
 292   if (!GlobalBaseReg) {
 293     const TargetInstrInfo &TII = *TM.getSubtargetImpl()->getInstrInfo();
 294     // Insert the set of GlobalBaseReg into the first MBB of the function
 295     MachineBasicBlock &FirstMBB = MF->front();
 296     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 297     const Module *M = MF->getFunction()->getParent();
 298     DebugLoc dl;
 299
 300     if (PPCLowering->getPointerTy() == MVT::i32) {
 301       if (PPCSubTarget->isTargetELF()) {
 302         GlobalBaseReg = PPC::R30;
 303         if (M->getPICLevel() == PICLevel::Small) {
 304           BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MoveGOTtoLR));
 305           BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
 306         } else {
 307           BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
 308           BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
 309           unsigned TempReg = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
 310           BuildMI(FirstMBB, MBBI, dl,
 311                   TII.get(PPC::UpdateGBR)).addReg(GlobalBaseReg)
 312                   .addReg(TempReg, RegState::Define).addReg(GlobalBaseReg);
 313           MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
 314         }
 315       } else {
 316         GlobalBaseReg =
 317           RegInfo->createVirtualRegister(&PPC::GPRC_NOR0RegClass);
 318         BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
 319         BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
 320       }
 321     } else {
 322       GlobalBaseReg = RegInfo->createVirtualRegister(&PPC::G8RC_NOX0RegClass);
 323       BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR8));
 324       BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR8), GlobalBaseReg);
 325     }
 326   }
 327   return CurDAG->getRegister(GlobalBaseReg,
 328                              PPCLowering->getPointerTy()).getNode();
 329 }
 330
 331 /// isIntS16Immediate - This method tests to see if the node is either a 32-bit
 332 /// or 64-bit immediate, and if the value can be accurately represented as a
 333 /// sign extension from a 16-bit value.  If so, this returns true and the
 334 /// immediate.
 335 static bool isIntS16Immediate(SDNode *N, short &Imm) {
 336   if (N->getOpcode() != ISD::Constant)
 337     return false;
 338
 339   Imm = (short)cast<ConstantSDNode>(N)->getZExtValue();
 340   if (N->getValueType(0) == MVT::i32)
 341     return Imm == (int32_t)cast<ConstantSDNode>(N)->getZExtValue();
 342   else
 343     return Imm == (int64_t)cast<ConstantSDNode>(N)->getZExtValue();
 344 }
 345
 346 static bool isIntS16Immediate(SDValue Op, short &Imm) {
 347   return isIntS16Immediate(Op.getNode(), Imm);
 348 }
 349
 350
 351 /// isInt32Immediate - This method tests to see if the node is a 32-bit constant
 352 /// operand. If so Imm will receive the 32-bit value.
 353 static bool isInt32Immediate(SDNode *N, unsigned &Imm) {
 354   if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
 355     Imm = cast<ConstantSDNode>(N)->getZExtValue();
 356     return true;
 357   }
 358   return false;
 359 }
 360
 361 /// isInt64Immediate - This method tests to see if the node is a 64-bit constant
 362 /// operand.  If so Imm will receive the 64-bit value.
 363 static bool isInt64Immediate(SDNode *N, uint64_t &Imm) {
 364   if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i64) {
 365     Imm = cast<ConstantSDNode>(N)->getZExtValue();
 366     return true;
 367   }
 368   return false;
 369 }
 370
 371 // isInt32Immediate - This method tests to see if a constant operand.
 372 // If so Imm will receive the 32 bit value.
 373 static bool isInt32Immediate(SDValue N, unsigned &Imm) {
 374   return isInt32Immediate(N.getNode(), Imm);
 375 }
 376
 377
 378 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 379 // opcode and that it has a immediate integer right operand.
 380 // If so Imm will receive the 32 bit value.
 381 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
 382   return N->getOpcode() == Opc
 383          && isInt32Immediate(N->getOperand(1).getNode(), Imm);
 384 }
 385
 386 SDNode *PPCDAGToDAGISel::getFrameIndex(SDNode *SN, SDNode *N, unsigned Offset) {
 387   SDLoc dl(SN);
 388   int FI = cast<FrameIndexSDNode>(N)->getIndex();
 389   SDValue TFI = CurDAG->getTargetFrameIndex(FI, N->getValueType(0));
 390   unsigned Opc = N->getValueType(0) == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
 391   if (SN->hasOneUse())
 392     return CurDAG->SelectNodeTo(SN, Opc, N->getValueType(0), TFI,
 393                                 getSmallIPtrImm(Offset));
 394   return CurDAG->getMachineNode(Opc, dl, N->getValueType(0), TFI,
 395                                 getSmallIPtrImm(Offset));
 396 }
 397
 398 bool PPCDAGToDAGISel::isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 399   if (!Val)
 400     return false;
 401
 402   if (isShiftedMask_32(Val)) {
 403     // look for the first non-zero bit
 404     MB = countLeadingZeros(Val);
 405     // look for the first zero bit after the run of ones
 406     ME = countLeadingZeros((Val - 1) ^ Val);
 407     return true;
 408   } else {
 409     Val = ~Val; // invert mask
 410     if (isShiftedMask_32(Val)) {
 411       // effectively look for the first zero bit
 412       ME = countLeadingZeros(Val) - 1;
 413       // effectively look for the first one bit after the run of zeros
 414       MB = countLeadingZeros((Val - 1) ^ Val) + 1;
 415       return true;
 416     }
 417   }
 418   // no run present
 419   return false;
 420 }
 421
 422 bool PPCDAGToDAGISel::isRotateAndMask(SDNode *N, unsigned Mask,
 423                                       bool isShiftMask, unsigned &SH,
 424                                       unsigned &MB, unsigned &ME) {
 425   // Don't even go down this path for i64, since different logic will be
 426   // necessary for rldicl/rldicr/rldimi.
 427   if (N->getValueType(0) != MVT::i32)
 428     return false;
 429
 430   unsigned Shift  = 32;
 431   unsigned Indeterminant = ~0;  // bit mask marking indeterminant results
 432   unsigned Opcode = N->getOpcode();
 433   if (N->getNumOperands() != 2 ||
 434       !isInt32Immediate(N->getOperand(1).getNode(), Shift) || (Shift > 31))
 435     return false;
 436
 437   if (Opcode == ISD::SHL) {
 438     // apply shift left to mask if it comes first
 439     if (isShiftMask) Mask = Mask << Shift;
 440     // determine which bits are made indeterminant by shift
 441     Indeterminant = ~(0xFFFFFFFFu << Shift);
 442   } else if (Opcode == ISD::SRL) {
 443     // apply shift right to mask if it comes first
 444     if (isShiftMask) Mask = Mask >> Shift;
 445     // determine which bits are made indeterminant by shift
 446     Indeterminant = ~(0xFFFFFFFFu >> Shift);
 447     // adjust for the left rotate
 448     Shift = 32 - Shift;
 449   } else if (Opcode == ISD::ROTL) {
 450     Indeterminant = 0;
 451   } else {
 452     return false;
 453   }
 454
 455   // if the mask doesn't intersect any Indeterminant bits
 456   if (Mask && !(Mask & Indeterminant)) {
 457     SH = Shift & 31;
 458     // make sure the mask is still a mask (wrap arounds may not be)
 459     return isRunOfOnes(Mask, MB, ME);
 460   }
 461   return false;
 462 }
 463
 464 /// SelectBitfieldInsert - turn an or of two masked values into
 465 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 466 SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
 467   SDValue Op0 = N->getOperand(0);
 468   SDValue Op1 = N->getOperand(1);
 469   SDLoc dl(N);
 470
 471   APInt LKZ, LKO, RKZ, RKO;
 472   CurDAG->computeKnownBits(Op0, LKZ, LKO);
 473   CurDAG->computeKnownBits(Op1, RKZ, RKO);
 474
 475   unsigned TargetMask = LKZ.getZExtValue();
 476   unsigned InsertMask = RKZ.getZExtValue();
 477
 478   if ((TargetMask | InsertMask) == 0xFFFFFFFF) {
 479     unsigned Op0Opc = Op0.getOpcode();
 480     unsigned Op1Opc = Op1.getOpcode();
 481     unsigned Value, SH = 0;
 482     TargetMask = ~TargetMask;
 483     InsertMask = ~InsertMask;
 484
 485     // If the LHS has a foldable shift and the RHS does not, then swap it to the
 486     // RHS so that we can fold the shift into the insert.
 487     if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 488       if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 489           Op0.getOperand(0).getOpcode() == ISD::SRL) {
 490         if (Op1.getOperand(0).getOpcode() != ISD::SHL &&
 491             Op1.getOperand(0).getOpcode() != ISD::SRL) {
 492           std::swap(Op0, Op1);
 493           std::swap(Op0Opc, Op1Opc);
 494           std::swap(TargetMask, InsertMask);
 495         }
 496       }
 497     } else if (Op0Opc == ISD::SHL || Op0Opc == ISD::SRL) {
 498       if (Op1Opc == ISD::AND && Op1.getOperand(0).getOpcode() != ISD::SHL &&
 499           Op1.getOperand(0).getOpcode() != ISD::SRL) {
 500         std::swap(Op0, Op1);
 501         std::swap(Op0Opc, Op1Opc);
 502         std::swap(TargetMask, InsertMask);
 503       }
 504     }
 505
 506     unsigned MB, ME;
 507     if (isRunOfOnes(InsertMask, MB, ME)) {
 508       SDValue Tmp1, Tmp2;
 509
 510       if ((Op1Opc == ISD::SHL || Op1Opc == ISD::SRL) &&
 511           isInt32Immediate(Op1.getOperand(1), Value)) {
 512         Op1 = Op1.getOperand(0);
 513         SH  = (Op1Opc == ISD::SHL) ? Value : 32 - Value;
 514       }
 515       if (Op1Opc == ISD::AND) {
 516        // The AND mask might not be a constant, and we need to make sure that
 517        // if we're going to fold the masking with the insert, all bits not
 518        // know to be zero in the mask are known to be one.
 519         APInt MKZ, MKO;
 520         CurDAG->computeKnownBits(Op1.getOperand(1), MKZ, MKO);
 521         bool CanFoldMask = InsertMask == MKO.getZExtValue();
 522
 523         unsigned SHOpc = Op1.getOperand(0).getOpcode();
 524         if ((SHOpc == ISD::SHL || SHOpc == ISD::SRL) && CanFoldMask &&
 525             isInt32Immediate(Op1.getOperand(0).getOperand(1), Value)) {
 526           // Note that Value must be in range here (less than 32) because
 527           // otherwise there would not be any bits set in InsertMask.
 528           Op1 = Op1.getOperand(0).getOperand(0);
 529           SH  = (SHOpc == ISD::SHL) ? Value : 32 - Value;
 530         }
 531       }
 532
 533       SH &= 31;
 534       SDValue Ops[] = { Op0, Op1, getI32Imm(SH), getI32Imm(MB),
 535                           getI32Imm(ME) };
 536       return CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops);
 537     }
 538   }
 539   return nullptr;
 540 }
 541
 542 // Predict the number of instructions that would be generated by calling
 543 // SelectInt64(N).
 544 static unsigned SelectInt64Count(int64_t Imm) {
 545   // Assume no remaining bits.
 546   unsigned Remainder = 0;
 547   // Assume no shift required.
 548   unsigned Shift = 0;
 549
 550   // If it can't be represented as a 32 bit value.
 551   if (!isInt<32>(Imm)) {
 552     Shift = countTrailingZeros<uint64_t>(Imm);
 553     int64_t ImmSh = static_cast<uint64_t>(Imm) >> Shift;
 554
 555     // If the shifted value fits 32 bits.
 556     if (isInt<32>(ImmSh)) {
 557       // Go with the shifted value.
 558       Imm = ImmSh;
 559     } else {
 560       // Still stuck with a 64 bit value.
 561       Remainder = Imm;
 562       Shift = 32;
 563       Imm >>= 32;
 564     }
 565   }
 566
 567   // Intermediate operand.
 568   unsigned Result = 0;
 569
 570   // Handle first 32 bits.
 571   unsigned Lo = Imm & 0xFFFF;
 572   unsigned Hi = (Imm >> 16) & 0xFFFF;
 573
 574   // Simple value.
 575   if (isInt<16>(Imm)) {
 576     // Just the Lo bits.
 577     ++Result;
 578   } else if (Lo) {
 579     // Handle the Hi bits and Lo bits.
 580     Result += 2;
 581   } else {
 582     // Just the Hi bits.
 583     ++Result;
 584   }
 585
 586   // If no shift, we're done.
 587   if (!Shift) return Result;
 588
 589   // Shift for next step if the upper 32-bits were not zero.
 590   if (Imm)
 591     ++Result;
 592
 593   // Add in the last bits as required.
 594   if ((Hi = (Remainder >> 16) & 0xFFFF))
 595     ++Result;
 596   if ((Lo = Remainder & 0xFFFF))
 597     ++Result;
 598
 599   return Result;
 600 }
 601
 602 // Select a 64-bit constant. For cost-modeling purposes, SelectInt64Count
 603 // (above) needs to be kept in sync with this function.
 604 static SDNode *SelectInt64(SelectionDAG *CurDAG, SDLoc dl, int64_t Imm) {
 605   // Assume no remaining bits.
 606   unsigned Remainder = 0;
 607   // Assume no shift required.
 608   unsigned Shift = 0;
 609
 610   // If it can't be represented as a 32 bit value.
 611   if (!isInt<32>(Imm)) {
 612     Shift = countTrailingZeros<uint64_t>(Imm);
 613     int64_t ImmSh = static_cast<uint64_t>(Imm) >> Shift;
 614
 615     // If the shifted value fits 32 bits.
 616     if (isInt<32>(ImmSh)) {
 617       // Go with the shifted value.
 618       Imm = ImmSh;
 619     } else {
 620       // Still stuck with a 64 bit value.
 621       Remainder = Imm;
 622       Shift = 32;
 623       Imm >>= 32;
 624     }
 625   }
 626
 627   // Intermediate operand.
 628   SDNode *Result;
 629
 630   // Handle first 32 bits.
 631   unsigned Lo = Imm & 0xFFFF;
 632   unsigned Hi = (Imm >> 16) & 0xFFFF;
 633
 634   auto getI32Imm = [CurDAG](unsigned Imm) {
 635       return CurDAG->getTargetConstant(Imm, MVT::i32);
 636   };
 637
 638   // Simple value.
 639   if (isInt<16>(Imm)) {
 640     // Just the Lo bits.
 641     Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, getI32Imm(Lo));
 642   } else if (Lo) {
 643     // Handle the Hi bits.
 644     unsigned OpC = Hi ? PPC::LIS8 : PPC::LI8;
 645     Result = CurDAG->getMachineNode(OpC, dl, MVT::i64, getI32Imm(Hi));
 646     // And Lo bits.
 647     Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
 648                                     SDValue(Result, 0), getI32Imm(Lo));
 649   } else {
 650     // Just the Hi bits.
 651     Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64, getI32Imm(Hi));
 652   }
 653
 654   // If no shift, we're done.
 655   if (!Shift) return Result;
 656
 657   // Shift for next step if the upper 32-bits were not zero.
 658   if (Imm) {
 659     Result = CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64,
 660                                     SDValue(Result, 0),
 661                                     getI32Imm(Shift),
 662                                     getI32Imm(63 - Shift));
 663   }
 664
 665   // Add in the last bits as required.
 666   if ((Hi = (Remainder >> 16) & 0xFFFF)) {
 667     Result = CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64,
 668                                     SDValue(Result, 0), getI32Imm(Hi));
 669   }
 670   if ((Lo = Remainder & 0xFFFF)) {
 671     Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
 672                                     SDValue(Result, 0), getI32Imm(Lo));
 673   }
 674
 675   return Result;
 676 }
 677
 678 // Select a 64-bit constant.
 679 static SDNode *SelectInt64(SelectionDAG *CurDAG, SDNode *N) {
 680   SDLoc dl(N);
 681
 682   // Get 64 bit value.
 683   int64_t Imm = cast<ConstantSDNode>(N)->getZExtValue();
 684   return SelectInt64(CurDAG, dl, Imm);
 685 }
 686
 687
 688 namespace {
 689 class BitPermutationSelector {
 690   struct ValueBit {
 691     SDValue V;
 692
 693     // The bit number in the value, using a convention where bit 0 is the
 694     // lowest-order bit.
 695     unsigned Idx;
 696
 697     enum Kind {
 698       ConstZero,
 699       Variable
 700     } K;
 701
 702     ValueBit(SDValue V, unsigned I, Kind K = Variable)
 703       : V(V), Idx(I), K(K) {}
 704     ValueBit(Kind K = Variable)
 705       : V(SDValue(nullptr, 0)), Idx(UINT32_MAX), K(K) {}
 706
 707     bool isZero() const {
 708       return K == ConstZero;
 709     }
 710
 711     bool hasValue() const {
 712       return K == Variable;
 713     }
 714
 715     SDValue getValue() const {
 716       assert(hasValue() && "Cannot get the value of a constant bit");
 717       return V;
 718     }
 719
 720     unsigned getValueBitIndex() const {
 721       assert(hasValue() && "Cannot get the value bit index of a constant bit");
 722       return Idx;
 723     }
 724   };
 725
 726   // A bit group has the same underlying value and the same rotate factor.
 727   struct BitGroup {
 728     SDValue V;
 729     unsigned RLAmt;
 730     unsigned StartIdx, EndIdx;
 731
 732     // This rotation amount assumes that the lower 32 bits of the quantity are
 733     // replicated in the high 32 bits by the rotation operator (which is done
 734     // by rlwinm and friends in 64-bit mode).
 735     bool Repl32;
 736     // Did converting to Repl32 == true change the rotation factor? If it did,
 737     // it decreased it by 32.
 738     bool Repl32CR;
 739     // Was this group coalesced after setting Repl32 to true?
 740     bool Repl32Coalesced;
 741
 742     BitGroup(SDValue V, unsigned R, unsigned S, unsigned E)
 743       : V(V), RLAmt(R), StartIdx(S), EndIdx(E), Repl32(false), Repl32CR(false),
 744         Repl32Coalesced(false) {
 745       DEBUG(dbgs() << "\tbit group for " << V.getNode() << " RLAmt = " << R <<
 746                       " [" << S << ", " << E << "]\n");
 747     }
 748   };
 749
 750   // Information on each (Value, RLAmt) pair (like the number of groups
 751   // associated with each) used to choose the lowering method.
 752   struct ValueRotInfo {
 753     SDValue V;
 754     unsigned RLAmt;
 755     unsigned NumGroups;
 756     unsigned FirstGroupStartIdx;
 757     bool Repl32;
 758
 759     ValueRotInfo()
 760       : RLAmt(UINT32_MAX), NumGroups(0), FirstGroupStartIdx(UINT32_MAX),
 761         Repl32(false) {}
 762
 763     // For sorting (in reverse order) by NumGroups, and then by
 764     // FirstGroupStartIdx.
 765     bool operator < (const ValueRotInfo &Other) const {
 766       // We need to sort so that the non-Repl32 come first because, when we're
 767       // doing masking, the Repl32 bit groups might be subsumed into the 64-bit
 768       // masking operation.
 769       if (Repl32 < Other.Repl32)
 770         return true;
 771       else if (Repl32 > Other.Repl32)
 772         return false;
 773       else if (NumGroups > Other.NumGroups)
 774         return true;
 775       else if (NumGroups < Other.NumGroups)
 776         return false;
 777       else if (FirstGroupStartIdx < Other.FirstGroupStartIdx)
 778         return true;
 779       return false;
 780     }
 781   };
 782
 783   // Return true if something interesting was deduced, return false if we're
 784   // providing only a generic representation of V (or something else likewise
 785   // uninteresting for instruction selection).
 786   bool getValueBits(SDValue V, SmallVector<ValueBit, 64> &Bits) {
 787     switch (V.getOpcode()) {
 788     default: break;
 789     case ISD::ROTL:
 790       if (isa<ConstantSDNode>(V.getOperand(1))) {
 791         unsigned RotAmt = V.getConstantOperandVal(1);
 792
 793         SmallVector<ValueBit, 64> LHSBits(Bits.size());
 794         getValueBits(V.getOperand(0), LHSBits);
 795
 796         for (unsigned i = 0; i < Bits.size(); ++i)
 797           Bits[i] = LHSBits[i < RotAmt ? i + (Bits.size() - RotAmt) : i - RotAmt];
 798
 799         return true;
 800       }
 801       break;
 802     case ISD::SHL:
 803       if (isa<ConstantSDNode>(V.getOperand(1))) {
 804         unsigned ShiftAmt = V.getConstantOperandVal(1);
 805
 806         SmallVector<ValueBit, 64> LHSBits(Bits.size());
 807         getValueBits(V.getOperand(0), LHSBits);
 808
 809         for (unsigned i = ShiftAmt; i < Bits.size(); ++i)
 810           Bits[i] = LHSBits[i - ShiftAmt];
 811
 812         for (unsigned i = 0; i < ShiftAmt; ++i)
 813           Bits[i] = ValueBit(ValueBit::ConstZero);
 814
 815         return true;
 816       }
 817       break;
 818     case ISD::SRL:
 819       if (isa<ConstantSDNode>(V.getOperand(1))) {
 820         unsigned ShiftAmt = V.getConstantOperandVal(1);
 821
 822         SmallVector<ValueBit, 64> LHSBits(Bits.size());
 823         getValueBits(V.getOperand(0), LHSBits);
 824
 825         for (unsigned i = 0; i < Bits.size() - ShiftAmt; ++i)
 826           Bits[i] = LHSBits[i + ShiftAmt];
 827
 828         for (unsigned i = Bits.size() - ShiftAmt; i < Bits.size(); ++i)
 829           Bits[i] = ValueBit(ValueBit::ConstZero);
 830
 831         return true;
 832       }
 833       break;
 834     case ISD::AND:
 835       if (isa<ConstantSDNode>(V.getOperand(1))) {
 836         uint64_t Mask = V.getConstantOperandVal(1);
 837
 838         SmallVector<ValueBit, 64> LHSBits(Bits.size());
 839         bool LHSTrivial = getValueBits(V.getOperand(0), LHSBits);
 840
 841         for (unsigned i = 0; i < Bits.size(); ++i)
 842           if (((Mask >> i) & 1) == 1)
 843             Bits[i] = LHSBits[i];
 844           else
 845             Bits[i] = ValueBit(ValueBit::ConstZero);
 846
 847         // Mark this as interesting, only if the LHS was also interesting. This
 848         // prevents the overall procedure from matching a single immediate 'and'
 849         // (which is non-optimal because such an and might be folded with other
 850         // things if we don't select it here).
 851         return LHSTrivial;
 852       }
 853       break;
 854     case ISD::OR: {
 855       SmallVector<ValueBit, 64> LHSBits(Bits.size()), RHSBits(Bits.size());
 856       getValueBits(V.getOperand(0), LHSBits);
 857       getValueBits(V.getOperand(1), RHSBits);
 858
 859       bool AllDisjoint = true;
 860       for (unsigned i = 0; i < Bits.size(); ++i)
 861         if (LHSBits[i].isZero())
 862           Bits[i] = RHSBits[i];
 863         else if (RHSBits[i].isZero())
 864           Bits[i] = LHSBits[i];
 865         else {
 866           AllDisjoint = false;
 867           break;
 868         }
 869
 870       if (!AllDisjoint)
 871         break;
 872
 873       return true;
 874     }
 875     }
 876
 877     for (unsigned i = 0; i < Bits.size(); ++i)
 878       Bits[i] = ValueBit(V, i);
 879
 880     return false;
 881   }
 882
 883   // For each value (except the constant ones), compute the left-rotate amount
 884   // to get it from its original to final position.
 885   void computeRotationAmounts() {
 886     HasZeros = false;
 887     RLAmt.resize(Bits.size());
 888     for (unsigned i = 0; i < Bits.size(); ++i)
 889       if (Bits[i].hasValue()) {
 890         unsigned VBI = Bits[i].getValueBitIndex();
 891         if (i >= VBI)
 892           RLAmt[i] = i - VBI;
 893         else
 894           RLAmt[i] = Bits.size() - (VBI - i);
 895       } else if (Bits[i].isZero()) {
 896         HasZeros = true;
 897         RLAmt[i] = UINT32_MAX;
 898       } else {
 899         llvm_unreachable("Unknown value bit type");
 900       }
 901   }
 902
 903   // Collect groups of consecutive bits with the same underlying value and
 904   // rotation factor. If we're doing late masking, we ignore zeros, otherwise
 905   // they break up groups.
 906   void collectBitGroups(bool LateMask) {
 907     BitGroups.clear();
 908
 909     unsigned LastRLAmt = RLAmt[0];
 910     SDValue LastValue = Bits[0].hasValue() ? Bits[0].getValue() : SDValue();
 911     unsigned LastGroupStartIdx = 0;
 912     for (unsigned i = 1; i < Bits.size(); ++i) {
 913       unsigned ThisRLAmt = RLAmt[i];
 914       SDValue ThisValue = Bits[i].hasValue() ? Bits[i].getValue() : SDValue();
 915       if (LateMask && !ThisValue) {
 916         ThisValue = LastValue;
 917         ThisRLAmt = LastRLAmt;
 918         // If we're doing late masking, then the first bit group always starts
 919         // at zero (even if the first bits were zero).
 920         if (BitGroups.empty())
 921           LastGroupStartIdx = 0;
 922       }
 923
 924       // If this bit has the same underlying value and the same rotate factor as
 925       // the last one, then they're part of the same group.
 926       if (ThisRLAmt == LastRLAmt && ThisValue == LastValue)
 927         continue;
 928
 929       if (LastValue.getNode())
 930         BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
 931                                      i-1));
 932       LastRLAmt = ThisRLAmt;
 933       LastValue = ThisValue;
 934       LastGroupStartIdx = i;
 935     }
 936     if (LastValue.getNode())
 937       BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
 938                                    Bits.size()-1));
 939
 940     if (BitGroups.empty())
 941       return;
 942
 943     // We might be able to combine the first and last groups.
 944     if (BitGroups.size() > 1) {
 945       // If the first and last groups are the same, then remove the first group
 946       // in favor of the last group, making the ending index of the last group
 947       // equal to the ending index of the to-be-removed first group.
 948       if (BitGroups[0].StartIdx == 0 &&
 949           BitGroups[BitGroups.size()-1].EndIdx == Bits.size()-1 &&
 950           BitGroups[0].V == BitGroups[BitGroups.size()-1].V &&
 951           BitGroups[0].RLAmt == BitGroups[BitGroups.size()-1].RLAmt) {
 952         DEBUG(dbgs() << "\tcombining final bit group with inital one\n");
 953         BitGroups[BitGroups.size()-1].EndIdx = BitGroups[0].EndIdx;
 954         BitGroups.erase(BitGroups.begin());
 955       }
 956     }
 957   }
 958
 959   // Take all (SDValue, RLAmt) pairs and sort them by the number of groups
 960   // associated with each. If there is a degeneracy, pick the one that occurs
 961   // first (in the final value).
 962   void collectValueRotInfo() {
 963     ValueRots.clear();
 964
 965     for (auto &BG : BitGroups) {
 966       unsigned RLAmtKey = BG.RLAmt + (BG.Repl32 ? 64 : 0);
 967       ValueRotInfo &VRI = ValueRots[std::make_pair(BG.V, RLAmtKey)];
 968       VRI.V = BG.V;
 969       VRI.RLAmt = BG.RLAmt;
 970       VRI.Repl32 = BG.Repl32;
 971       VRI.NumGroups += 1;
 972       VRI.FirstGroupStartIdx = std::min(VRI.FirstGroupStartIdx, BG.StartIdx);
 973     }
 974
 975     // Now that we've collected the various ValueRotInfo instances, we need to
 976     // sort them.
 977     ValueRotsVec.clear();
 978     for (auto &I : ValueRots) {
 979       ValueRotsVec.push_back(I.second);
 980     }
 981     std::sort(ValueRotsVec.begin(), ValueRotsVec.end());
 982   }
 983
 984   // In 64-bit mode, rlwinm and friends have a rotation operator that
 985   // replicates the low-order 32 bits into the high-order 32-bits. The mask
 986   // indices of these instructions can only be in the lower 32 bits, so they
 987   // can only represent some 64-bit bit groups. However, when they can be used,
 988   // the 32-bit replication can be used to represent, as a single bit group,
 989   // otherwise separate bit groups. We'll convert to replicated-32-bit bit
 990   // groups when possible. Returns true if any of the bit groups were
 991   // converted.
 992   void assignRepl32BitGroups() {
 993     // If we have bits like this:
 994     //
 995     // Indices:    15 14 13 12 11 10 9 8  7  6  5  4  3  2  1  0
 996     // V bits: ... 7  6  5  4  3  2  1 0 31 30 29 28 27 26 25 24
 997     // Groups:    |      RLAmt = 8      |      RLAmt = 40       |
 998     //
 999     // But, making use of a 32-bit operation that replicates the low-order 32
1000     // bits into the high-order 32 bits, this can be one bit group with a RLAmt
1001     // of 8.
1002
1003     auto IsAllLow32 = [this](BitGroup & BG) {
1004       if (BG.StartIdx <= BG.EndIdx) {
1005         for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i) {
1006           if (!Bits[i].hasValue())
1007             continue;
1008           if (Bits[i].getValueBitIndex() >= 32)
1009             return false;
1010         }
1011       } else {
1012         for (unsigned i = BG.StartIdx; i < Bits.size(); ++i) {
1013           if (!Bits[i].hasValue())
1014             continue;
1015           if (Bits[i].getValueBitIndex() >= 32)
1016             return false;
1017         }
1018         for (unsigned i = 0; i <= BG.EndIdx; ++i) {
1019           if (!Bits[i].hasValue())
1020             continue;
1021           if (Bits[i].getValueBitIndex() >= 32)
1022             return false;
1023         }
1024       }
1025
1026       return true;
1027     };
1028
1029     for (auto &BG : BitGroups) {
1030       if (BG.StartIdx < 32 && BG.EndIdx < 32) {
1031         if (IsAllLow32(BG)) {
1032           if (BG.RLAmt >= 32) {
1033             BG.RLAmt -= 32;
1034             BG.Repl32CR = true;
1035           }
1036
1037           BG.Repl32 = true;
1038
1039           DEBUG(dbgs() << "\t32-bit replicated bit group for " <<
1040                           BG.V.getNode() << " RLAmt = " << BG.RLAmt <<
1041                           " [" << BG.StartIdx << ", " << BG.EndIdx << "]\n");
1042         }
1043       }
1044     }
1045
1046     // Now walk through the bit groups, consolidating where possible.
1047     for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1048       // We might want to remove this bit group by merging it with the previous
1049       // group (which might be the ending group).
1050       auto IP = (I == BitGroups.begin()) ?
1051                 std::prev(BitGroups.end()) : std::prev(I);
1052       if (I->Repl32 && IP->Repl32 && I->V == IP->V && I->RLAmt == IP->RLAmt &&
1053           I->StartIdx == (IP->EndIdx + 1) % 64 && I != IP) {
1054
1055         DEBUG(dbgs() << "\tcombining 32-bit replicated bit group for " <<
1056                         I->V.getNode() << " RLAmt = " << I->RLAmt <<
1057                         " [" << I->StartIdx << ", " << I->EndIdx <<
1058                         "] with group with range [" <<
1059                         IP->StartIdx << ", " << IP->EndIdx << "]\n");
1060
1061         IP->EndIdx = I->EndIdx;
1062         IP->Repl32CR = IP->Repl32CR || I->Repl32CR;
1063         IP->Repl32Coalesced = true;
1064         I = BitGroups.erase(I);
1065         continue;
1066       } else {
1067         // There is a special case worth handling: If there is a single group
1068         // covering the entire upper 32 bits, and it can be merged with both
1069         // the next and previous groups (which might be the same group), then
1070         // do so. If it is the same group (so there will be only one group in
1071         // total), then we need to reverse the order of the range so that it
1072         // covers the entire 64 bits.
1073         if (I->StartIdx == 32 && I->EndIdx == 63) {
1074           assert(std::next(I) == BitGroups.end() &&
1075                  "bit group ends at index 63 but there is another?");
1076           auto IN = BitGroups.begin();
1077
1078           if (IP->Repl32 && IN->Repl32 && I->V == IP->V && I->V == IN->V &&
1079               (I->RLAmt % 32) == IP->RLAmt && (I->RLAmt % 32) == IN->RLAmt &&
1080               IP->EndIdx == 31 && IN->StartIdx == 0 && I != IP &&
1081               IsAllLow32(*I)) {
1082
1083             DEBUG(dbgs() << "\tcombining bit group for " <<
1084                             I->V.getNode() << " RLAmt = " << I->RLAmt <<
1085                             " [" << I->StartIdx << ", " << I->EndIdx <<
1086                             "] with 32-bit replicated groups with ranges [" <<
1087                             IP->StartIdx << ", " << IP->EndIdx << "] and [" <<
1088                             IN->StartIdx << ", " << IN->EndIdx << "]\n");
1089
1090             if (IP == IN) {
1091               // There is only one other group; change it to cover the whole
1092               // range (backward, so that it can still be Repl32 but cover the
1093               // whole 64-bit range).
1094               IP->StartIdx = 31;
1095               IP->EndIdx = 30;
1096               IP->Repl32CR = IP->Repl32CR || I->RLAmt >= 32;
1097               IP->Repl32Coalesced = true;
1098               I = BitGroups.erase(I);
1099             } else {
1100               // There are two separate groups, one before this group and one
1101               // after us (at the beginning). We're going to remove this group,
1102               // but also the group at the very beginning.
1103               IP->EndIdx = IN->EndIdx;
1104               IP->Repl32CR = IP->Repl32CR || IN->Repl32CR || I->RLAmt >= 32;
1105               IP->Repl32Coalesced = true;
1106               I = BitGroups.erase(I);
1107               BitGroups.erase(BitGroups.begin());
1108             }
1109
1110             // This must be the last group in the vector (and we might have
1111             // just invalidated the iterator above), so break here.
1112             break;
1113           }
1114         }
1115       }
1116
1117       ++I;
1118     }
1119   }
1120
1121   SDValue getI32Imm(unsigned Imm) {
1122     return CurDAG->getTargetConstant(Imm, MVT::i32);
1123   }
1124
1125   uint64_t getZerosMask() {
1126     uint64_t Mask = 0;
1127     for (unsigned i = 0; i < Bits.size(); ++i) {
1128       if (Bits[i].hasValue())
1129         continue;
1130       Mask |= (1ul << i);
1131     }
1132
1133     return ~Mask;
1134   }
1135
1136   // Depending on the number of groups for a particular value, it might be
1137   // better to rotate, mask explicitly (using andi/andis), and then or the
1138   // result. Select this part of the result first.
1139   void SelectAndParts32(SDLoc dl, SDValue &Res, unsigned *InstCnt) {
1140     if (BPermRewriterNoMasking)
1141       return;
1142
1143     for (ValueRotInfo &VRI : ValueRotsVec) {
1144       unsigned Mask = 0;
1145       for (unsigned i = 0; i < Bits.size(); ++i) {
1146         if (!Bits[i].hasValue() || Bits[i].getValue() != VRI.V)
1147           continue;
1148         if (RLAmt[i] != VRI.RLAmt)
1149           continue;
1150         Mask |= (1u << i);
1151       }
1152
1153       // Compute the masks for andi/andis that would be necessary.
1154       unsigned ANDIMask = (Mask & UINT16_MAX), ANDISMask = Mask >> 16;
1155       assert((ANDIMask != 0 || ANDISMask != 0) &&
1156              "No set bits in mask for value bit groups");
1157       bool NeedsRotate = VRI.RLAmt != 0;
1158
1159       // We're trying to minimize the number of instructions. If we have one
1160       // group, using one of andi/andis can break even.  If we have three
1161       // groups, we can use both andi and andis and break even (to use both
1162       // andi and andis we also need to or the results together). We need four
1163       // groups if we also need to rotate. To use andi/andis we need to do more
1164       // than break even because rotate-and-mask instructions tend to be easier
1165       // to schedule.
1166
1167       // FIXME: We've biased here against using andi/andis, which is right for
1168       // POWER cores, but not optimal everywhere. For example, on the A2,
1169       // andi/andis have single-cycle latency whereas the rotate-and-mask
1170       // instructions take two cycles, and it would be better to bias toward
1171       // andi/andis in break-even cases.
1172
1173       unsigned NumAndInsts = (unsigned) NeedsRotate +
1174                              (unsigned) (ANDIMask != 0) +
1175                              (unsigned) (ANDISMask != 0) +
1176                              (unsigned) (ANDIMask != 0 && ANDISMask != 0) +
1177                              (unsigned) (bool) Res;
1178
1179       DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode() <<
1180                       " RL: " << VRI.RLAmt << ":" <<
1181                       "\n\t\t\tisel using masking: " << NumAndInsts <<
1182                       " using rotates: " << VRI.NumGroups << "\n");
1183
1184       if (NumAndInsts >= VRI.NumGroups)
1185         continue;
1186
1187       DEBUG(dbgs() << "\t\t\t\tusing masking\n");
1188
1189       if (InstCnt) *InstCnt += NumAndInsts;
1190
1191       SDValue VRot;
1192       if (VRI.RLAmt) {
1193         SDValue Ops[] =
1194           { VRI.V, getI32Imm(VRI.RLAmt), getI32Imm(0), getI32Imm(31) };
1195         VRot = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
1196                                               Ops), 0);
1197       } else {
1198         VRot = VRI.V;
1199       }
1200
1201       SDValue ANDIVal, ANDISVal;
1202       if (ANDIMask != 0)
1203         ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo, dl, MVT::i32,
1204                             VRot, getI32Imm(ANDIMask)), 0);
1205       if (ANDISMask != 0)
1206         ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo, dl, MVT::i32,
1207                              VRot, getI32Imm(ANDISMask)), 0);
1208
1209       SDValue TotalVal;
1210       if (!ANDIVal)
1211         TotalVal = ANDISVal;
1212       else if (!ANDISVal)
1213         TotalVal = ANDIVal;
1214       else
1215         TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
1216                              ANDIVal, ANDISVal), 0);
1217
1218       if (!Res)
1219         Res = TotalVal;
1220       else
1221         Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
1222                         Res, TotalVal), 0);
1223
1224       // Now, remove all groups with this underlying value and rotation
1225       // factor.
1226       for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1227         if (I->V == VRI.V && I->RLAmt == VRI.RLAmt)
1228           I = BitGroups.erase(I);
1229         else
1230           ++I;
1231       }
1232     }
1233   }
1234
1235   // Instruction selection for the 32-bit case.
1236   SDNode *Select32(SDNode *N, bool LateMask, unsigned *InstCnt) {
1237     SDLoc dl(N);
1238     SDValue Res;
1239
1240     if (InstCnt) *InstCnt = 0;
1241
1242     // Take care of cases that should use andi/andis first.
1243     SelectAndParts32(dl, Res, InstCnt);
1244
1245     // If we've not yet selected a 'starting' instruction, and we have no zeros
1246     // to fill in, select the (Value, RLAmt) with the highest priority (largest
1247     // number of groups), and start with this rotated value.
1248     if ((!HasZeros || LateMask) && !Res) {
1249       ValueRotInfo &VRI = ValueRotsVec[0];
1250       if (VRI.RLAmt) {
1251         if (InstCnt) *InstCnt += 1;
1252         SDValue Ops[] =
1253           { VRI.V, getI32Imm(VRI.RLAmt), getI32Imm(0), getI32Imm(31) };
1254         Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
1255       } else {
1256         Res = VRI.V;
1257       }
1258
1259       // Now, remove all groups with this underlying value and rotation factor.
1260       for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1261         if (I->V == VRI.V && I->RLAmt == VRI.RLAmt)
1262           I = BitGroups.erase(I);
1263         else
1264           ++I;
1265       }
1266     }
1267
1268     if (InstCnt) *InstCnt += BitGroups.size();
1269
1270     // Insert the other groups (one at a time).
1271     for (auto &BG : BitGroups) {
1272       if (!Res) {
1273         SDValue Ops[] =
1274           { BG.V, getI32Imm(BG.RLAmt), getI32Imm(Bits.size() - BG.EndIdx - 1),
1275             getI32Imm(Bits.size() - BG.StartIdx - 1) };
1276         Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
1277       } else {
1278         SDValue Ops[] =
1279           { Res, BG.V, getI32Imm(BG.RLAmt), getI32Imm(Bits.size() - BG.EndIdx - 1),
1280             getI32Imm(Bits.size() - BG.StartIdx - 1) };
1281         Res = SDValue(CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops), 0);
1282       }
1283     }
1284
1285     if (LateMask) {
1286       unsigned Mask = (unsigned) getZerosMask();
1287
1288       unsigned ANDIMask = (Mask & UINT16_MAX), ANDISMask = Mask >> 16;
1289       assert((ANDIMask != 0 || ANDISMask != 0) &&
1290              "No set bits in zeros mask?");
1291
1292       if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
1293                                (unsigned) (ANDISMask != 0) +
1294                                (unsigned) (ANDIMask != 0 && ANDISMask != 0);
1295
1296       SDValue ANDIVal, ANDISVal;
1297       if (ANDIMask != 0)
1298         ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo, dl, MVT::i32,
1299                             Res, getI32Imm(ANDIMask)), 0);
1300       if (ANDISMask != 0)
1301         ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo, dl, MVT::i32,
1302                              Res, getI32Imm(ANDISMask)), 0);
1303
1304       if (!ANDIVal)
1305         Res = ANDISVal;
1306       else if (!ANDISVal)
1307         Res = ANDIVal;
1308       else
1309         Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
1310                         ANDIVal, ANDISVal), 0);
1311     }
1312
1313     return Res.getNode();
1314   }
1315
1316   unsigned SelectRotMask64Count(unsigned RLAmt, bool Repl32,
1317                                 unsigned MaskStart, unsigned MaskEnd,
1318                                 bool IsIns) {
1319     // In the notation used by the instructions, 'start' and 'end' are reversed
1320     // because bits are counted from high to low order.
1321     unsigned InstMaskStart = 64 - MaskEnd - 1,
1322              InstMaskEnd   = 64 - MaskStart - 1;
1323
1324     if (Repl32)
1325       return 1;
1326
1327     if ((!IsIns && (InstMaskEnd == 63 || InstMaskStart == 0)) ||
1328         InstMaskEnd == 63 - RLAmt)
1329       return 1;
1330
1331     return 2;
1332   }
1333
1334   // For 64-bit values, not all combinations of rotates and masks are
1335   // available. Produce one if it is available.
1336   SDValue SelectRotMask64(SDValue V, SDLoc dl, unsigned RLAmt, bool Repl32,
1337                           unsigned MaskStart, unsigned MaskEnd,
1338                           unsigned *InstCnt = nullptr) {
1339     // In the notation used by the instructions, 'start' and 'end' are reversed
1340     // because bits are counted from high to low order.
1341     unsigned InstMaskStart = 64 - MaskEnd - 1,
1342              InstMaskEnd   = 64 - MaskStart - 1;
1343
1344     if (InstCnt) *InstCnt += 1;
1345
1346     if (Repl32) {
1347       // This rotation amount assumes that the lower 32 bits of the quantity
1348       // are replicated in the high 32 bits by the rotation operator (which is
1349       // done by rlwinm and friends).
1350       assert(InstMaskStart >= 32 && "Mask cannot start out of range");
1351       assert(InstMaskEnd   >= 32 && "Mask cannot end out of range");
1352       SDValue Ops[] =
1353         { V, getI32Imm(RLAmt), getI32Imm(InstMaskStart - 32),
1354           getI32Imm(InstMaskEnd - 32) };
1355       return SDValue(CurDAG->getMachineNode(PPC::RLWINM8, dl, MVT::i64,
1356                                             Ops), 0);
1357     }
1358
1359     if (InstMaskEnd == 63) {
1360       SDValue Ops[] =
1361         { V, getI32Imm(RLAmt), getI32Imm(InstMaskStart) };
1362       return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Ops), 0);
1363     }
1364
1365     if (InstMaskStart == 0) {
1366       SDValue Ops[] =
1367         { V, getI32Imm(RLAmt), getI32Imm(InstMaskEnd) };
1368       return SDValue(CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64, Ops), 0);
1369     }
1370
1371     if (InstMaskEnd == 63 - RLAmt) {
1372       SDValue Ops[] =
1373         { V, getI32Imm(RLAmt), getI32Imm(InstMaskStart) };
1374       return SDValue(CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, Ops), 0);
1375     }
1376
1377     // We cannot do this with a single instruction, so we'll use two. The
1378     // problem is that we're not free to choose both a rotation amount and mask
1379     // start and end independently. We can choose an arbitrary mask start and
1380     // end, but then the rotation amount is fixed. Rotation, however, can be
1381     // inverted, and so by applying an "inverse" rotation first, we can get the
1382     // desired result.
1383     if (InstCnt) *InstCnt += 1;
1384
1385     // The rotation mask for the second instruction must be MaskStart.
1386     unsigned RLAmt2 = MaskStart;
1387     // The first instruction must rotate V so that the overall rotation amount
1388     // is RLAmt.
1389     unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
1390     if (RLAmt1)
1391       V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
1392     return SelectRotMask64(V, dl, RLAmt2, false, MaskStart, MaskEnd);
1393   }
1394
1395   // For 64-bit values, not all combinations of rotates and masks are
1396   // available. Produce a rotate-mask-and-insert if one is available.
1397   SDValue SelectRotMaskIns64(SDValue Base, SDValue V, SDLoc dl, unsigned RLAmt,
1398                              bool Repl32, unsigned MaskStart,
1399                              unsigned MaskEnd, unsigned *InstCnt = nullptr) {
1400     // In the notation used by the instructions, 'start' and 'end' are reversed
1401     // because bits are counted from high to low order.
1402     unsigned InstMaskStart = 64 - MaskEnd - 1,
1403              InstMaskEnd   = 64 - MaskStart - 1;
1404
1405     if (InstCnt) *InstCnt += 1;
1406
1407     if (Repl32) {
1408       // This rotation amount assumes that the lower 32 bits of the quantity
1409       // are replicated in the high 32 bits by the rotation operator (which is
1410       // done by rlwinm and friends).
1411       assert(InstMaskStart >= 32 && "Mask cannot start out of range");
1412       assert(InstMaskEnd   >= 32 && "Mask cannot end out of range");
1413       SDValue Ops[] =
1414         { Base, V, getI32Imm(RLAmt), getI32Imm(InstMaskStart - 32),
1415           getI32Imm(InstMaskEnd - 32) };
1416       return SDValue(CurDAG->getMachineNode(PPC::RLWIMI8, dl, MVT::i64,
1417                                             Ops), 0);
1418     }
1419
1420     if (InstMaskEnd == 63 - RLAmt) {
1421       SDValue Ops[] =
1422         { Base, V, getI32Imm(RLAmt), getI32Imm(InstMaskStart) };
1423       return SDValue(CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops), 0);
1424     }
1425
1426     // We cannot do this with a single instruction, so we'll use two. The
1427     // problem is that we're not free to choose both a rotation amount and mask
1428     // start and end independently. We can choose an arbitrary mask start and
1429     // end, but then the rotation amount is fixed. Rotation, however, can be
1430     // inverted, and so by applying an "inverse" rotation first, we can get the
1431     // desired result.
1432     if (InstCnt) *InstCnt += 1;
1433
1434     // The rotation mask for the second instruction must be MaskStart.
1435     unsigned RLAmt2 = MaskStart;
1436     // The first instruction must rotate V so that the overall rotation amount
1437     // is RLAmt.
1438     unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
1439     if (RLAmt1)
1440       V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
1441     return SelectRotMaskIns64(Base, V, dl, RLAmt2, false, MaskStart, MaskEnd);
1442   }
1443
1444   void SelectAndParts64(SDLoc dl, SDValue &Res, unsigned *InstCnt) {
1445     if (BPermRewriterNoMasking)
1446       return;
1447
1448     // The idea here is the same as in the 32-bit version, but with additional
1449     // complications from the fact that Repl32 might be true. Because we
1450     // aggressively convert bit groups to Repl32 form (which, for small
1451     // rotation factors, involves no other change), and then coalesce, it might
1452     // be the case that a single 64-bit masking operation could handle both
1453     // some Repl32 groups and some non-Repl32 groups. If converting to Repl32
1454     // form allowed coalescing, then we must use a 32-bit rotaton in order to
1455     // completely capture the new combined bit group.
1456
1457     for (ValueRotInfo &VRI : ValueRotsVec) {
1458       uint64_t Mask = 0;
1459
1460       // We need to add to the mask all bits from the associated bit groups.
1461       // If Repl32 is false, we need to add bits from bit groups that have
1462       // Repl32 true, but are trivially convertable to Repl32 false. Such a
1463       // group is trivially convertable if it overlaps only with the lower 32
1464       // bits, and the group has not been coalesced.
1465       auto MatchingBG = [VRI](BitGroup &BG) {
1466         if (VRI.V != BG.V)
1467           return false;
1468
1469         unsigned EffRLAmt = BG.RLAmt;
1470         if (!VRI.Repl32 && BG.Repl32) {
1471           if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx <= BG.EndIdx &&
1472               !BG.Repl32Coalesced) {
1473             if (BG.Repl32CR)
1474               EffRLAmt += 32;
1475           } else {
1476             return false;
1477           }
1478         } else if (VRI.Repl32 != BG.Repl32) {
1479           return false;
1480         }
1481
1482         if (VRI.RLAmt != EffRLAmt)
1483           return false;
1484
1485         return true;
1486       };
1487
1488       for (auto &BG : BitGroups) {
1489         if (!MatchingBG(BG))
1490           continue;
1491
1492         if (BG.StartIdx <= BG.EndIdx) {
1493           for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i)
1494             Mask |= (1ul << i);
1495         } else {
1496           for (unsigned i = BG.StartIdx; i < Bits.size(); ++i)
1497             Mask |= (1ul << i);
1498           for (unsigned i = 0; i <= BG.EndIdx; ++i)
1499             Mask |= (1ul << i);
1500         }
1501       }
1502
1503       // We can use the 32-bit andi/andis technique if the mask does not
1504       // require any higher-order bits. This can save an instruction compared
1505       // to always using the general 64-bit technique.
1506       bool Use32BitInsts = isUInt<32>(Mask);
1507       // Compute the masks for andi/andis that would be necessary.
1508       unsigned ANDIMask = (Mask & UINT16_MAX),
1509                ANDISMask = (Mask >> 16) & UINT16_MAX;
1510
1511       bool NeedsRotate = VRI.RLAmt || (VRI.Repl32 && !isUInt<32>(Mask));
1512
1513       unsigned NumAndInsts = (unsigned) NeedsRotate +
1514                              (unsigned) (bool) Res;
1515       if (Use32BitInsts)
1516         NumAndInsts += (unsigned) (ANDIMask != 0) + (unsigned) (ANDISMask != 0) +
1517                        (unsigned) (ANDIMask != 0 && ANDISMask != 0);
1518       else
1519         NumAndInsts += SelectInt64Count(Mask) + /* and */ 1;
1520
1521       unsigned NumRLInsts = 0;
1522       bool FirstBG = true;
1523       for (auto &BG : BitGroups) {
1524         if (!MatchingBG(BG))
1525           continue;
1526         NumRLInsts +=
1527           SelectRotMask64Count(BG.RLAmt, BG.Repl32, BG.StartIdx, BG.EndIdx,
1528                                !FirstBG);
1529         FirstBG = false;
1530       }
1531
1532       DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode() <<
1533                       " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":") <<
1534                       "\n\t\t\tisel using masking: " << NumAndInsts <<
1535                       " using rotates: " << NumRLInsts << "\n");
1536
1537       // When we'd use andi/andis, we bias toward using the rotates (andi only
1538       // has a record form, and is cracked on POWER cores). However, when using
1539       // general 64-bit constant formation, bias toward the constant form,
1540       // because that exposes more opportunities for CSE.
1541       if (NumAndInsts > NumRLInsts)
1542         continue;
1543       if (Use32BitInsts && NumAndInsts == NumRLInsts)
1544         continue;
1545
1546       DEBUG(dbgs() << "\t\t\t\tusing masking\n");
1547
1548       if (InstCnt) *InstCnt += NumAndInsts;
1549
1550       SDValue VRot;
1551       // We actually need to generate a rotation if we have a non-zero rotation
1552       // factor or, in the Repl32 case, if we care about any of the
1553       // higher-order replicated bits. In the latter case, we generate a mask
1554       // backward so that it actually includes the entire 64 bits.
1555       if (VRI.RLAmt || (VRI.Repl32 && !isUInt<32>(Mask)))
1556         VRot = SelectRotMask64(VRI.V, dl, VRI.RLAmt, VRI.Repl32,
1557                                VRI.Repl32 ? 31 : 0, VRI.Repl32 ? 30 : 63);
1558       else
1559         VRot = VRI.V;
1560
1561       SDValue TotalVal;
1562       if (Use32BitInsts) {
1563         assert((ANDIMask != 0 || ANDISMask != 0) &&
1564                "No set bits in mask when using 32-bit ands for 64-bit value");
1565
1566         SDValue ANDIVal, ANDISVal;
1567         if (ANDIMask != 0)
1568           ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo8, dl, MVT::i64,
1569                               VRot, getI32Imm(ANDIMask)), 0);
1570         if (ANDISMask != 0)
1571           ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo8, dl, MVT::i64,
1572                                VRot, getI32Imm(ANDISMask)), 0);
1573
1574         if (!ANDIVal)
1575           TotalVal = ANDISVal;
1576         else if (!ANDISVal)
1577           TotalVal = ANDIVal;
1578         else
1579           TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
1580                                ANDIVal, ANDISVal), 0);
1581       } else {
1582         TotalVal = SDValue(SelectInt64(CurDAG, dl, Mask), 0);
1583         TotalVal =
1584           SDValue(CurDAG->getMachineNode(PPC::AND8, dl, MVT::i64,
1585                                          VRot, TotalVal), 0);
1586      }
1587
1588       if (!Res)
1589         Res = TotalVal;
1590       else
1591         Res = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
1592                                              Res, TotalVal), 0);
1593
1594       // Now, remove all groups with this underlying value and rotation
1595       // factor.
1596       for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1597         if (MatchingBG(*I))
1598           I = BitGroups.erase(I);
1599         else
1600           ++I;
1601       }
1602     }
1603   }
1604
1605   // Instruction selection for the 64-bit case.
1606   SDNode *Select64(SDNode *N, bool LateMask, unsigned *InstCnt) {
1607     SDLoc dl(N);
1608     SDValue Res;
1609
1610     if (InstCnt) *InstCnt = 0;
1611
1612     // Take care of cases that should use andi/andis first.
1613     SelectAndParts64(dl, Res, InstCnt);
1614
1615     // If we've not yet selected a 'starting' instruction, and we have no zeros
1616     // to fill in, select the (Value, RLAmt) with the highest priority (largest
1617     // number of groups), and start with this rotated value.
1618     if ((!HasZeros || LateMask) && !Res) {
1619       // If we have both Repl32 groups and non-Repl32 groups, the non-Repl32
1620       // groups will come first, and so the VRI representing the largest number
1621       // of groups might not be first (it might be the first Repl32 groups).
1622       unsigned MaxGroupsIdx = 0;
1623       if (!ValueRotsVec[0].Repl32) {
1624         for (unsigned i = 0, ie = ValueRotsVec.size(); i < ie; ++i)
1625           if (ValueRotsVec[i].Repl32) {
1626             if (ValueRotsVec[i].NumGroups > ValueRotsVec[0].NumGroups)
1627               MaxGroupsIdx = i;
1628             break;
1629           }
1630       }
1631
1632       ValueRotInfo &VRI = ValueRotsVec[MaxGroupsIdx];
1633       bool NeedsRotate = false;
1634       if (VRI.RLAmt) {
1635         NeedsRotate = true;
1636       } else if (VRI.Repl32) {
1637         for (auto &BG : BitGroups) {
1638           if (BG.V != VRI.V || BG.RLAmt != VRI.RLAmt ||
1639               BG.Repl32 != VRI.Repl32)
1640             continue;
1641
1642           // We don't need a rotate if the bit group is confined to the lower
1643           // 32 bits.
1644           if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx < BG.EndIdx)
1645             continue;
1646
1647           NeedsRotate = true;
1648           break;
1649         }
1650       }
1651
1652       if (NeedsRotate)
1653         Res = SelectRotMask64(VRI.V, dl, VRI.RLAmt, VRI.Repl32,
1654                               VRI.Repl32 ? 31 : 0, VRI.Repl32 ? 30 : 63,
1655                               InstCnt);
1656       else
1657         Res = VRI.V;
1658
1659       // Now, remove all groups with this underlying value and rotation factor.
1660       if (Res)
1661         for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1662           if (I->V == VRI.V && I->RLAmt == VRI.RLAmt && I->Repl32 == VRI.Repl32)
1663             I = BitGroups.erase(I);
1664           else
1665             ++I;
1666         }
1667     }
1668
1669     // Because 64-bit rotates are more flexible than inserts, we might have a
1670     // preference regarding which one we do first (to save one instruction).
1671     if (!Res)
1672       for (auto I = BitGroups.begin(), IE = BitGroups.end(); I != IE; ++I) {
1673         if (SelectRotMask64Count(I->RLAmt, I->Repl32, I->StartIdx, I->EndIdx,
1674                                 false) <
1675             SelectRotMask64Count(I->RLAmt, I->Repl32, I->StartIdx, I->EndIdx,
1676                                 true)) {
1677           if (I != BitGroups.begin()) {
1678             BitGroup BG = *I;
1679             BitGroups.erase(I);
1680             BitGroups.insert(BitGroups.begin(), BG);
1681           }
1682
1683           break;
1684         }
1685       }
1686
1687     // Insert the other groups (one at a time).
1688     for (auto &BG : BitGroups) {
1689       if (!Res)
1690         Res = SelectRotMask64(BG.V, dl, BG.RLAmt, BG.Repl32, BG.StartIdx,
1691                               BG.EndIdx, InstCnt);
1692       else
1693         Res = SelectRotMaskIns64(Res, BG.V, dl, BG.RLAmt, BG.Repl32,
1694                                  BG.StartIdx, BG.EndIdx, InstCnt);
1695     }
1696
1697     if (LateMask) {
1698       uint64_t Mask = getZerosMask();
1699
1700       // We can use the 32-bit andi/andis technique if the mask does not
1701       // require any higher-order bits. This can save an instruction compared
1702       // to always using the general 64-bit technique.
1703       bool Use32BitInsts = isUInt<32>(Mask);
1704       // Compute the masks for andi/andis that would be necessary.
1705       unsigned ANDIMask = (Mask & UINT16_MAX),
1706                ANDISMask = (Mask >> 16) & UINT16_MAX;
1707
1708       if (Use32BitInsts) {
1709         assert((ANDIMask != 0 || ANDISMask != 0) &&
1710                "No set bits in mask when using 32-bit ands for 64-bit value");
1711
1712         if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
1713                                  (unsigned) (ANDISMask != 0) +
1714                                  (unsigned) (ANDIMask != 0 && ANDISMask != 0);
1715
1716         SDValue ANDIVal, ANDISVal;
1717         if (ANDIMask != 0)
1718           ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo8, dl, MVT::i64,
1719                               Res, getI32Imm(ANDIMask)), 0);
1720         if (ANDISMask != 0)
1721           ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo8, dl, MVT::i64,
1722                                Res, getI32Imm(ANDISMask)), 0);
1723
1724         if (!ANDIVal)
1725           Res = ANDISVal;
1726         else if (!ANDISVal)
1727           Res = ANDIVal;
1728         else
1729           Res = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
1730                           ANDIVal, ANDISVal), 0);
1731       } else {
1732         if (InstCnt) *InstCnt += SelectInt64Count(Mask) + /* and */ 1;
1733
1734         SDValue MaskVal = SDValue(SelectInt64(CurDAG, dl, Mask), 0);
1735         Res =
1736           SDValue(CurDAG->getMachineNode(PPC::AND8, dl, MVT::i64,
1737                                          Res, MaskVal), 0);
1738       }
1739     }
1740
1741     return Res.getNode();
1742   }
1743
1744   SDNode *Select(SDNode *N, bool LateMask, unsigned *InstCnt = nullptr) {
1745     // Fill in BitGroups.
1746     collectBitGroups(LateMask);
1747     if (BitGroups.empty())
1748       return nullptr;
1749
1750     // For 64-bit values, figure out when we can use 32-bit instructions.
1751     if (Bits.size() == 64)
1752       assignRepl32BitGroups();
1753
1754     // Fill in ValueRotsVec.
1755     collectValueRotInfo();
1756
1757     if (Bits.size() == 32) {
1758       return Select32(N, LateMask, InstCnt);
1759     } else {
1760       assert(Bits.size() == 64 && "Not 64 bits here?");
1761       return Select64(N, LateMask, InstCnt);
1762     }
1763
1764     return nullptr;
1765   }
1766
1767   SmallVector<ValueBit, 64> Bits;
1768
1769   bool HasZeros;
1770   SmallVector<unsigned, 64> RLAmt;
1771
1772   SmallVector<BitGroup, 16> BitGroups;
1773
1774   DenseMap<std::pair<SDValue, unsigned>, ValueRotInfo> ValueRots;
1775   SmallVector<ValueRotInfo, 16> ValueRotsVec;
1776
1777   SelectionDAG *CurDAG;
1778
1779 public:
1780   BitPermutationSelector(SelectionDAG *DAG)
1781     : CurDAG(DAG) {}
1782
1783   // Here we try to match complex bit permutations into a set of
1784   // rotate-and-shift/shift/and/or instructions, using a set of heuristics
1785   // known to produce optimial code for common cases (like i32 byte swapping).
1786   SDNode *Select(SDNode *N) {
1787     Bits.resize(N->getValueType(0).getSizeInBits());
1788     if (!getValueBits(SDValue(N, 0), Bits))
1789       return nullptr;
1790
1791     DEBUG(dbgs() << "Considering bit-permutation-based instruction"
1792                     " selection for:    ");
1793     DEBUG(N->dump(CurDAG));
1794
1795     // Fill it RLAmt and set HasZeros.
1796     computeRotationAmounts();
1797
1798     if (!HasZeros)
1799       return Select(N, false);
1800
1801     // We currently have two techniques for handling results with zeros: early
1802     // masking (the default) and late masking. Late masking is sometimes more
1803     // efficient, but because the structure of the bit groups is different, it
1804     // is hard to tell without generating both and comparing the results. With
1805     // late masking, we ignore zeros in the resulting value when inserting each
1806     // set of bit groups, and then mask in the zeros at the end. With early
1807     // masking, we only insert the non-zero parts of the result at every step.
1808
1809     unsigned InstCnt, InstCntLateMask;
1810     DEBUG(dbgs() << "\tEarly masking:\n");
1811     SDNode *RN = Select(N, false, &InstCnt);
1812     DEBUG(dbgs() << "\t\tisel would use " << InstCnt << " instructions\n");
1813
1814     DEBUG(dbgs() << "\tLate masking:\n");
1815     SDNode *RNLM = Select(N, true, &InstCntLateMask);
1816     DEBUG(dbgs() << "\t\tisel would use " << InstCntLateMask <<
1817                     " instructions\n");
1818
1819     if (InstCnt <= InstCntLateMask) {
1820       DEBUG(dbgs() << "\tUsing early-masking for isel\n");
1821       return RN;
1822     }
1823
1824     DEBUG(dbgs() << "\tUsing late-masking for isel\n");
1825     return RNLM;
1826   }
1827 };
1828 } // anonymous namespace
1829
1830 SDNode *PPCDAGToDAGISel::SelectBitPermutation(SDNode *N) {
1831   if (N->getValueType(0) != MVT::i32 &&
1832       N->getValueType(0) != MVT::i64)
1833     return nullptr;
1834
1835   if (!UseBitPermRewriter)
1836     return nullptr;
1837
1838   switch (N->getOpcode()) {
1839   default: break;
1840   case ISD::ROTL:
1841   case ISD::SHL:
1842   case ISD::SRL:
1843   case ISD::AND:
1844   case ISD::OR: {
1845     BitPermutationSelector BPS(CurDAG);
1846     return BPS.Select(N);
1847   }
1848   }
1849
1850   return nullptr;
1851 }
1852
1853 /// SelectCC - Select a comparison of the specified values with the specified
1854 /// condition code, returning the CR# of the expression.
1855 SDValue PPCDAGToDAGISel::SelectCC(SDValue LHS, SDValue RHS,
1856                                     ISD::CondCode CC, SDLoc dl) {
1857   // Always select the LHS.
1858   unsigned Opc;
1859
1860   if (LHS.getValueType() == MVT::i32) {
1861     unsigned Imm;
1862     if (CC == ISD::SETEQ || CC == ISD::SETNE) {
1863       if (isInt32Immediate(RHS, Imm)) {
1864         // SETEQ/SETNE comparison with 16-bit immediate, fold it.
1865         if (isUInt<16>(Imm))
1866           return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
1867                                                 getI32Imm(Imm & 0xFFFF)), 0);
1868         // If this is a 16-bit signed immediate, fold it.
1869         if (isInt<16>((int)Imm))
1870           return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
1871                                                 getI32Imm(Imm & 0xFFFF)), 0);
1872
1873         // For non-equality comparisons, the default code would materialize the
1874         // constant, then compare against it, like this:
1875         //   lis r2, 4660
1876         //   ori r2, r2, 22136
1877         //   cmpw cr0, r3, r2
1878         // Since we are just comparing for equality, we can emit this instead:
1879         //   xoris r0,r3,0x1234
1880         //   cmplwi cr0,r0,0x5678
1881         //   beq cr0,L6
1882         SDValue Xor(CurDAG->getMachineNode(PPC::XORIS, dl, MVT::i32, LHS,
1883                                            getI32Imm(Imm >> 16)), 0);
1884         return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, Xor,
1885                                               getI32Imm(Imm & 0xFFFF)), 0);
1886       }
1887       Opc = PPC::CMPLW;
1888     } else if (ISD::isUnsignedIntSetCC(CC)) {
1889       if (isInt32Immediate(RHS, Imm) && isUInt<16>(Imm))
1890         return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
1891                                               getI32Imm(Imm & 0xFFFF)), 0);
1892       Opc = PPC::CMPLW;
1893     } else {
1894       short SImm;
1895       if (isIntS16Immediate(RHS, SImm))
1896         return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
1897                                               getI32Imm((int)SImm & 0xFFFF)),
1898                          0);
1899       Opc = PPC::CMPW;
1900     }
1901   } else if (LHS.getValueType() == MVT::i64) {
1902     uint64_t Imm;
1903     if (CC == ISD::SETEQ || CC == ISD::SETNE) {
1904       if (isInt64Immediate(RHS.getNode(), Imm)) {
1905         // SETEQ/SETNE comparison with 16-bit immediate, fold it.
1906         if (isUInt<16>(Imm))
1907           return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
1908                                                 getI32Imm(Imm & 0xFFFF)), 0);
1909         // If this is a 16-bit signed immediate, fold it.
1910         if (isInt<16>(Imm))
1911           return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
1912                                                 getI32Imm(Imm & 0xFFFF)), 0);
1913
1914         // For non-equality comparisons, the default code would materialize the
1915         // constant, then compare against it, like this:
1916         //   lis r2, 4660
1917         //   ori r2, r2, 22136
1918         //   cmpd cr0, r3, r2
1919         // Since we are just comparing for equality, we can emit this instead:
1920         //   xoris r0,r3,0x1234
1921         //   cmpldi cr0,r0,0x5678
1922         //   beq cr0,L6
1923         if (isUInt<32>(Imm)) {
1924           SDValue Xor(CurDAG->getMachineNode(PPC::XORIS8, dl, MVT::i64, LHS,
1925                                              getI64Imm(Imm >> 16)), 0);
1926           return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, Xor,
1927                                                 getI64Imm(Imm & 0xFFFF)), 0);
1928         }
1929       }
1930       Opc = PPC::CMPLD;
1931     } else if (ISD::isUnsignedIntSetCC(CC)) {
1932       if (isInt64Immediate(RHS.getNode(), Imm) && isUInt<16>(Imm))
1933         return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
1934                                               getI64Imm(Imm & 0xFFFF)), 0);
1935       Opc = PPC::CMPLD;
1936     } else {
1937       short SImm;
1938       if (isIntS16Immediate(RHS, SImm))
1939         return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
1940                                               getI64Imm(SImm & 0xFFFF)),
1941                          0);
1942       Opc = PPC::CMPD;
1943     }
1944   } else if (LHS.getValueType() == MVT::f32) {
1945     Opc = PPC::FCMPUS;
1946   } else {
1947     assert(LHS.getValueType() == MVT::f64 && "Unknown vt!");
1948     Opc = PPCSubTarget->hasVSX() ? PPC::XSCMPUDP : PPC::FCMPUD;
1949   }
1950   return SDValue(CurDAG->getMachineNode(Opc, dl, MVT::i32, LHS, RHS), 0);
1951 }
1952
1953 static PPC::Predicate getPredicateForSetCC(ISD::CondCode CC) {
1954   switch (CC) {
1955   case ISD::SETUEQ:
1956   case ISD::SETONE:
1957   case ISD::SETOLE:
1958   case ISD::SETOGE:
1959     llvm_unreachable("Should be lowered by legalize!");
1960   default: llvm_unreachable("Unknown condition!");
1961   case ISD::SETOEQ:
1962   case ISD::SETEQ:  return PPC::PRED_EQ;
1963   case ISD::SETUNE:
1964   case ISD::SETNE:  return PPC::PRED_NE;
1965   case ISD::SETOLT:
1966   case ISD::SETLT:  return PPC::PRED_LT;
1967   case ISD::SETULE:
1968   case ISD::SETLE:  return PPC::PRED_LE;
1969   case ISD::SETOGT:
1970   case ISD::SETGT:  return PPC::PRED_GT;
1971   case ISD::SETUGE:
1972   case ISD::SETGE:  return PPC::PRED_GE;
1973   case ISD::SETO:   return PPC::PRED_NU;
1974   case ISD::SETUO:  return PPC::PRED_UN;
1975     // These two are invalid for floating point.  Assume we have int.
1976   case ISD::SETULT: return PPC::PRED_LT;
1977   case ISD::SETUGT: return PPC::PRED_GT;
1978   }
1979 }
1980
1981 /// getCRIdxForSetCC - Return the index of the condition register field
1982 /// associated with the SetCC condition, and whether or not the field is
1983 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
1984 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool &Invert) {
1985   Invert = false;
1986   switch (CC) {
1987   default: llvm_unreachable("Unknown condition!");
1988   case ISD::SETOLT:
1989   case ISD::SETLT:  return 0;                  // Bit #0 = SETOLT
1990   case ISD::SETOGT:
1991   case ISD::SETGT:  return 1;                  // Bit #1 = SETOGT
1992   case ISD::SETOEQ:
1993   case ISD::SETEQ:  return 2;                  // Bit #2 = SETOEQ
1994   case ISD::SETUO:  return 3;                  // Bit #3 = SETUO
1995   case ISD::SETUGE:
1996   case ISD::SETGE:  Invert = true; return 0;   // !Bit #0 = SETUGE
1997   case ISD::SETULE:
1998   case ISD::SETLE:  Invert = true; return 1;   // !Bit #1 = SETULE
1999   case ISD::SETUNE:
2000   case ISD::SETNE:  Invert = true; return 2;   // !Bit #2 = SETUNE
2001   case ISD::SETO:   Invert = true; return 3;   // !Bit #3 = SETO
2002   case ISD::SETUEQ:
2003   case ISD::SETOGE:
2004   case ISD::SETOLE:
2005   case ISD::SETONE:
2006     llvm_unreachable("Invalid branch code: should be expanded by legalize");
2007   // These are invalid for floating point.  Assume integer.
2008   case ISD::SETULT: return 0;
2009   case ISD::SETUGT: return 1;
2010   }
2011 }
2012
2013 // getVCmpInst: return the vector compare instruction for the specified
2014 // vector type and condition code. Since this is for altivec specific code,
2015 // only support the altivec types (v16i8, v8i16, v4i32, and v4f32).
2016 static unsigned int getVCmpInst(MVT VecVT, ISD::CondCode CC,
2017                                 bool HasVSX, bool &Swap, bool &Negate) {
2018   Swap = false;
2019   Negate = false;
2020
2021   if (VecVT.isFloatingPoint()) {
2022     /* Handle some cases by swapping input operands.  */
2023     switch (CC) {
2024       case ISD::SETLE: CC = ISD::SETGE; Swap = true; break;
2025       case ISD::SETLT: CC = ISD::SETGT; Swap = true; break;
2026       case ISD::SETOLE: CC = ISD::SETOGE; Swap = true; break;
2027       case ISD::SETOLT: CC = ISD::SETOGT; Swap = true; break;
2028       case ISD::SETUGE: CC = ISD::SETULE; Swap = true; break;
2029       case ISD::SETUGT: CC = ISD::SETULT; Swap = true; break;
2030       default: break;
2031     }
2032     /* Handle some cases by negating the result.  */
2033     switch (CC) {
2034       case ISD::SETNE: CC = ISD::SETEQ; Negate = true; break;
2035       case ISD::SETUNE: CC = ISD::SETOEQ; Negate = true; break;
2036       case ISD::SETULE: CC = ISD::SETOGT; Negate = true; break;
2037       case ISD::SETULT: CC = ISD::SETOGE; Negate = true; break;
2038       default: break;
2039     }
2040     /* We have instructions implementing the remaining cases.  */
2041     switch (CC) {
2042       case ISD::SETEQ:
2043       case ISD::SETOEQ:
2044         if (VecVT == MVT::v4f32)
2045           return HasVSX ? PPC::XVCMPEQSP : PPC::VCMPEQFP;
2046         else if (VecVT == MVT::v2f64)
2047           return PPC::XVCMPEQDP;
2048         break;
2049       case ISD::SETGT:
2050       case ISD::SETOGT:
2051         if (VecVT == MVT::v4f32)
2052           return HasVSX ? PPC::XVCMPGTSP : PPC::VCMPGTFP;
2053         else if (VecVT == MVT::v2f64)
2054           return PPC::XVCMPGTDP;
2055         break;
2056       case ISD::SETGE:
2057       case ISD::SETOGE:
2058         if (VecVT == MVT::v4f32)
2059           return HasVSX ? PPC::XVCMPGESP : PPC::VCMPGEFP;
2060         else if (VecVT == MVT::v2f64)
2061           return PPC::XVCMPGEDP;
2062         break;
2063       default:
2064         break;
2065     }
2066     llvm_unreachable("Invalid floating-point vector compare condition");
2067   } else {
2068     /* Handle some cases by swapping input operands.  */
2069     switch (CC) {
2070       case ISD::SETGE: CC = ISD::SETLE; Swap = true; break;
2071       case ISD::SETLT: CC = ISD::SETGT; Swap = true; break;
2072       case ISD::SETUGE: CC = ISD::SETULE; Swap = true; break;
2073       case ISD::SETULT: CC = ISD::SETUGT; Swap = true; break;
2074       default: break;
2075     }
2076     /* Handle some cases by negating the result.  */
2077     switch (CC) {
2078       case ISD::SETNE: CC = ISD::SETEQ; Negate = true; break;
2079       case ISD::SETUNE: CC = ISD::SETUEQ; Negate = true; break;
2080       case ISD::SETLE: CC = ISD::SETGT; Negate = true; break;
2081       case ISD::SETULE: CC = ISD::SETUGT; Negate = true; break;
2082       default: break;
2083     }
2084     /* We have instructions implementing the remaining cases.  */
2085     switch (CC) {
2086       case ISD::SETEQ:
2087       case ISD::SETUEQ:
2088         if (VecVT == MVT::v16i8)
2089           return PPC::VCMPEQUB;
2090         else if (VecVT == MVT::v8i16)
2091           return PPC::VCMPEQUH;
2092         else if (VecVT == MVT::v4i32)
2093           return PPC::VCMPEQUW;
2094         break;
2095       case ISD::SETGT:
2096         if (VecVT == MVT::v16i8)
2097           return PPC::VCMPGTSB;
2098         else if (VecVT == MVT::v8i16)
2099           return PPC::VCMPGTSH;
2100         else if (VecVT == MVT::v4i32)
2101           return PPC::VCMPGTSW;
2102         break;
2103       case ISD::SETUGT:
2104         if (VecVT == MVT::v16i8)
2105           return PPC::VCMPGTUB;
2106         else if (VecVT == MVT::v8i16)
2107           return PPC::VCMPGTUH;
2108         else if (VecVT == MVT::v4i32)
2109           return PPC::VCMPGTUW;
2110         break;
2111       default:
2112         break;
2113     }
2114     llvm_unreachable("Invalid integer vector compare condition");
2115   }
2116 }
2117
2118 SDNode *PPCDAGToDAGISel::SelectSETCC(SDNode *N) {
2119   SDLoc dl(N);
2120   unsigned Imm;
2121   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
2122   EVT PtrVT = CurDAG->getTargetLoweringInfo().getPointerTy();
2123   bool isPPC64 = (PtrVT == MVT::i64);
2124
2125   if (!PPCSubTarget->useCRBits() &&
2126       isInt32Immediate(N->getOperand(1), Imm)) {
2127     // We can codegen setcc op, imm very efficiently compared to a brcond.
2128     // Check for those cases here.
2129     // setcc op, 0
2130     if (Imm == 0) {
2131       SDValue Op = N->getOperand(0);
2132       switch (CC) {
2133       default: break;
2134       case ISD::SETEQ: {
2135         Op = SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Op), 0);
2136         SDValue Ops[] = { Op, getI32Imm(27), getI32Imm(5), getI32Imm(31) };
2137         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2138       }
2139       case ISD::SETNE: {
2140         if (isPPC64) break;
2141         SDValue AD =
2142           SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2143                                          Op, getI32Imm(~0U)), 0);
2144         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op,
2145                                     AD.getValue(1));
2146       }
2147       case ISD::SETLT: {
2148         SDValue Ops[] = { Op, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
2149         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2150       }
2151       case ISD::SETGT: {
2152         SDValue T =
2153           SDValue(CurDAG->getMachineNode(PPC::NEG, dl, MVT::i32, Op), 0);
2154         T = SDValue(CurDAG->getMachineNode(PPC::ANDC, dl, MVT::i32, T, Op), 0);
2155         SDValue Ops[] = { T, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
2156         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2157       }
2158       }
2159     } else if (Imm == ~0U) {        // setcc op, -1
2160       SDValue Op = N->getOperand(0);
2161       switch (CC) {
2162       default: break;
2163       case ISD::SETEQ:
2164         if (isPPC64) break;
2165         Op = SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2166                                             Op, getI32Imm(1)), 0);
2167         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
2168                               SDValue(CurDAG->getMachineNode(PPC::LI, dl,
2169                                                              MVT::i32,
2170                                                              getI32Imm(0)), 0),
2171                                       Op.getValue(1));
2172       case ISD::SETNE: {
2173         if (isPPC64) break;
2174         Op = SDValue(CurDAG->getMachineNode(PPC::NOR, dl, MVT::i32, Op, Op), 0);
2175         SDNode *AD = CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2176                                             Op, getI32Imm(~0U));
2177         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDValue(AD, 0),
2178                                     Op, SDValue(AD, 1));
2179       }
2180       case ISD::SETLT: {
2181         SDValue AD = SDValue(CurDAG->getMachineNode(PPC::ADDI, dl, MVT::i32, Op,
2182                                                     getI32Imm(1)), 0);
2183         SDValue AN = SDValue(CurDAG->getMachineNode(PPC::AND, dl, MVT::i32, AD,
2184                                                     Op), 0);
2185         SDValue Ops[] = { AN, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
2186         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2187       }
2188       case ISD::SETGT: {
2189         SDValue Ops[] = { Op, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
2190         Op = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops),
2191                      0);
2192         return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op,
2193                                     getI32Imm(1));
2194       }
2195       }
2196     }
2197   }
2198
2199   SDValue LHS = N->getOperand(0);
2200   SDValue RHS = N->getOperand(1);
2201
2202   // Altivec Vector compare instructions do not set any CR register by default and
2203   // vector compare operations return the same type as the operands.
2204   if (LHS.getValueType().isVector()) {
2205     EVT VecVT = LHS.getValueType();
2206     bool Swap, Negate;
2207     unsigned int VCmpInst = getVCmpInst(VecVT.getSimpleVT(), CC,
2208                                         PPCSubTarget->hasVSX(), Swap, Negate);
2209     if (Swap)
2210       std::swap(LHS, RHS);
2211
2212     if (Negate) {
2213       SDValue VCmp(CurDAG->getMachineNode(VCmpInst, dl, VecVT, LHS, RHS), 0);
2214       return CurDAG->SelectNodeTo(N, PPCSubTarget->hasVSX() ? PPC::XXLNOR :
2215                                                               PPC::VNOR,
2216                                   VecVT, VCmp, VCmp);
2217     }
2218
2219     return CurDAG->SelectNodeTo(N, VCmpInst, VecVT, LHS, RHS);
2220   }
2221
2222   if (PPCSubTarget->useCRBits())
2223     return nullptr;
2224
2225   bool Inv;
2226   unsigned Idx = getCRIdxForSetCC(CC, Inv);
2227   SDValue CCReg = SelectCC(LHS, RHS, CC, dl);
2228   SDValue IntCR;
2229
2230   // Force the ccreg into CR7.
2231   SDValue CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
2232
2233   SDValue InFlag(nullptr, 0);  // Null incoming flag value.
2234   CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, CR7Reg, CCReg,
2235                                InFlag).getValue(1);
2236
2237   IntCR = SDValue(CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32, CR7Reg,
2238                                          CCReg), 0);
2239
2240   SDValue Ops[] = { IntCR, getI32Imm((32-(3-Idx)) & 31),
2241                       getI32Imm(31), getI32Imm(31) };
2242   if (!Inv)
2243     return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2244
2245   // Get the specified bit.
2246   SDValue Tmp =
2247     SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
2248   return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1));
2249 }
2250
2251
2252 // Select - Convert the specified operand from a target-independent to a
2253 // target-specific node if it hasn't already been changed.
2254 SDNode *PPCDAGToDAGISel::Select(SDNode *N) {
2255   SDLoc dl(N);
2256   if (N->isMachineOpcode()) {
2257     N->setNodeId(-1);
2258     return nullptr;   // Already selected.
2259   }
2260
2261   // In case any misguided DAG-level optimizations form an ADD with a
2262   // TargetConstant operand, crash here instead of miscompiling (by selecting
2263   // an r+r add instead of some kind of r+i add).
2264   if (N->getOpcode() == ISD::ADD &&
2265       N->getOperand(1).getOpcode() == ISD::TargetConstant)
2266     llvm_unreachable("Invalid ADD with TargetConstant operand");
2267
2268   // Try matching complex bit permutations before doing anything else.
2269   if (SDNode *NN = SelectBitPermutation(N))
2270     return NN;
2271
2272   switch (N->getOpcode()) {
2273   default: break;
2274
2275   case ISD::Constant: {
2276     if (N->getValueType(0) == MVT::i64)
2277       return SelectInt64(CurDAG, N);
2278     break;
2279   }
2280
2281   case ISD::SETCC: {
2282     SDNode *SN = SelectSETCC(N);
2283     if (SN)
2284       return SN;
2285     break;
2286   }
2287   case PPCISD::GlobalBaseReg:
2288     return getGlobalBaseReg();
2289
2290   case ISD::FrameIndex:
2291     return getFrameIndex(N, N);
2292
2293   case PPCISD::MFOCRF: {
2294     SDValue InFlag = N->getOperand(1);
2295     return CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32,
2296                                   N->getOperand(0), InFlag);
2297   }
2298
2299   case PPCISD::READ_TIME_BASE: {
2300     return CurDAG->getMachineNode(PPC::ReadTB, dl, MVT::i32, MVT::i32,
2301                                   MVT::Other, N->getOperand(0));
2302   }
2303
2304   case PPCISD::SRA_ADDZE: {
2305     SDValue N0 = N->getOperand(0);
2306     SDValue ShiftAmt =
2307       CurDAG->getTargetConstant(*cast<ConstantSDNode>(N->getOperand(1))->
2308                                   getConstantIntValue(), N->getValueType(0));
2309     if (N->getValueType(0) == MVT::i64) {
2310       SDNode *Op =
2311         CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, MVT::Glue,
2312                                N0, ShiftAmt);
2313       return CurDAG->SelectNodeTo(N, PPC::ADDZE8, MVT::i64,
2314                                   SDValue(Op, 0), SDValue(Op, 1));
2315     } else {
2316       assert(N->getValueType(0) == MVT::i32 &&
2317              "Expecting i64 or i32 in PPCISD::SRA_ADDZE");
2318       SDNode *Op =
2319         CurDAG->getMachineNode(PPC::SRAWI, dl, MVT::i32, MVT::Glue,
2320                                N0, ShiftAmt);
2321       return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
2322                                   SDValue(Op, 0), SDValue(Op, 1));
2323     }
2324   }
2325
2326   case ISD::LOAD: {
2327     // Handle preincrement loads.
2328     LoadSDNode *LD = cast<LoadSDNode>(N);
2329     EVT LoadedVT = LD->getMemoryVT();
2330
2331     // Normal loads are handled by code generated from the .td file.
2332     if (LD->getAddressingMode() != ISD::PRE_INC)
2333       break;
2334
2335     SDValue Offset = LD->getOffset();
2336     if (Offset.getOpcode() == ISD::TargetConstant ||
2337         Offset.getOpcode() == ISD::TargetGlobalAddress) {
2338
2339       unsigned Opcode;
2340       bool isSExt = LD->getExtensionType() == ISD::SEXTLOAD;
2341       if (LD->getValueType(0) != MVT::i64) {
2342         // Handle PPC32 integer and normal FP loads.
2343         assert((!isSExt || LoadedVT == MVT::i16) && "Invalid sext update load");
2344         switch (LoadedVT.getSimpleVT().SimpleTy) {
2345           default: llvm_unreachable("Invalid PPC load type!");
2346           case MVT::f64: Opcode = PPC::LFDU; break;
2347           case MVT::f32: Opcode = PPC::LFSU; break;
2348           case MVT::i32: Opcode = PPC::LWZU; break;
2349           case MVT::i16: Opcode = isSExt ? PPC::LHAU : PPC::LHZU; break;
2350           case MVT::i1:
2351           case MVT::i8:  Opcode = PPC::LBZU; break;
2352         }
2353       } else {
2354         assert(LD->getValueType(0) == MVT::i64 && "Unknown load result type!");
2355         assert((!isSExt || LoadedVT == MVT::i16) && "Invalid sext update load");
2356         switch (LoadedVT.getSimpleVT().SimpleTy) {
2357           default: llvm_unreachable("Invalid PPC load type!");
2358           case MVT::i64: Opcode = PPC::LDU; break;
2359           case MVT::i32: Opcode = PPC::LWZU8; break;
2360           case MVT::i16: Opcode = isSExt ? PPC::LHAU8 : PPC::LHZU8; break;
2361           case MVT::i1:
2362           case MVT::i8:  Opcode = PPC::LBZU8; break;
2363         }
2364       }
2365
2366       SDValue Chain = LD->getChain();
2367       SDValue Base = LD->getBasePtr();
2368       SDValue Ops[] = { Offset, Base, Chain };
2369       return CurDAG->getMachineNode(Opcode, dl, LD->getValueType(0),
2370                                     PPCLowering->getPointerTy(),
2371                                     MVT::Other, Ops);
2372     } else {
2373       unsigned Opcode;
2374       bool isSExt = LD->getExtensionType() == ISD::SEXTLOAD;
2375       if (LD->getValueType(0) != MVT::i64) {
2376         // Handle PPC32 integer and normal FP loads.
2377         assert((!isSExt || LoadedVT == MVT::i16) && "Invalid sext update load");
2378         switch (LoadedVT.getSimpleVT().SimpleTy) {
2379           default: llvm_unreachable("Invalid PPC load type!");
2380           case MVT::f64: Opcode = PPC::LFDUX; break;
2381           case MVT::f32: Opcode = PPC::LFSUX; break;
2382           case MVT::i32: Opcode = PPC::LWZUX; break;
2383           case MVT::i16: Opcode = isSExt ? PPC::LHAUX : PPC::LHZUX; break;
2384           case MVT::i1:
2385           case MVT::i8:  Opcode = PPC::LBZUX; break;
2386         }
2387       } else {
2388         assert(LD->getValueType(0) == MVT::i64 && "Unknown load result type!");
2389         assert((!isSExt || LoadedVT == MVT::i16 || LoadedVT == MVT::i32) &&
2390                "Invalid sext update load");
2391         switch (LoadedVT.getSimpleVT().SimpleTy) {
2392           default: llvm_unreachable("Invalid PPC load type!");
2393           case MVT::i64: Opcode = PPC::LDUX; break;
2394           case MVT::i32: Opcode = isSExt ? PPC::LWAUX  : PPC::LWZUX8; break;
2395           case MVT::i16: Opcode = isSExt ? PPC::LHAUX8 : PPC::LHZUX8; break;
2396           case MVT::i1:
2397           case MVT::i8:  Opcode = PPC::LBZUX8; break;
2398         }
2399       }
2400
2401       SDValue Chain = LD->getChain();
2402       SDValue Base = LD->getBasePtr();
2403       SDValue Ops[] = { Base, Offset, Chain };
2404       return CurDAG->getMachineNode(Opcode, dl, LD->getValueType(0),
2405                                     PPCLowering->getPointerTy(),
2406                                     MVT::Other, Ops);
2407     }
2408   }
2409
2410   case ISD::AND: {
2411     unsigned Imm, Imm2, SH, MB, ME;
2412     uint64_t Imm64;
2413
2414     // If this is an and of a value rotated between 0 and 31 bits and then and'd
2415     // with a mask, emit rlwinm
2416     if (isInt32Immediate(N->getOperand(1), Imm) &&
2417         isRotateAndMask(N->getOperand(0).getNode(), Imm, false, SH, MB, ME)) {
2418       SDValue Val = N->getOperand(0).getOperand(0);
2419       SDValue Ops[] = { Val, getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
2420       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2421     }
2422     // If this is just a masked value where the input is not handled above, and
2423     // is not a rotate-left (handled by a pattern in the .td file), emit rlwinm
2424     if (isInt32Immediate(N->getOperand(1), Imm) &&
2425         isRunOfOnes(Imm, MB, ME) &&
2426         N->getOperand(0).getOpcode() != ISD::ROTL) {
2427       SDValue Val = N->getOperand(0);
2428       SDValue Ops[] = { Val, getI32Imm(0), getI32Imm(MB), getI32Imm(ME) };
2429       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2430     }
2431     // If this is a 64-bit zero-extension mask, emit rldicl.
2432     if (isInt64Immediate(N->getOperand(1).getNode(), Imm64) &&
2433         isMask_64(Imm64)) {
2434       SDValue Val = N->getOperand(0);
2435       MB = 64 - CountTrailingOnes_64(Imm64);
2436       SH = 0;
2437
2438       // If the operand is a logical right shift, we can fold it into this
2439       // instruction: rldicl(rldicl(x, 64-n, n), 0, mb) -> rldicl(x, 64-n, mb)
2440       // for n <= mb. The right shift is really a left rotate followed by a
2441       // mask, and this mask is a more-restrictive sub-mask of the mask implied
2442       // by the shift.
2443       if (Val.getOpcode() == ISD::SRL &&
2444           isInt32Immediate(Val.getOperand(1).getNode(), Imm) && Imm <= MB) {
2445         assert(Imm < 64 && "Illegal shift amount");
2446         Val = Val.getOperand(0);
2447         SH = 64 - Imm;
2448       }
2449
2450       SDValue Ops[] = { Val, getI32Imm(SH), getI32Imm(MB) };
2451       return CurDAG->SelectNodeTo(N, PPC::RLDICL, MVT::i64, Ops);
2452     }
2453     // AND X, 0 -> 0, not "rlwinm 32".
2454     if (isInt32Immediate(N->getOperand(1), Imm) && (Imm == 0)) {
2455       ReplaceUses(SDValue(N, 0), N->getOperand(1));
2456       return nullptr;
2457     }
2458     // ISD::OR doesn't get all the bitfield insertion fun.
2459     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) is a bitfield insert
2460     if (isInt32Immediate(N->getOperand(1), Imm) &&
2461         N->getOperand(0).getOpcode() == ISD::OR &&
2462         isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
2463       unsigned MB, ME;
2464       Imm = ~(Imm^Imm2);
2465       if (isRunOfOnes(Imm, MB, ME)) {
2466         SDValue Ops[] = { N->getOperand(0).getOperand(0),
2467                             N->getOperand(0).getOperand(1),
2468                             getI32Imm(0), getI32Imm(MB),getI32Imm(ME) };
2469         return CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops);
2470       }
2471     }
2472
2473     // Other cases are autogenerated.
2474     break;
2475   }
2476   case ISD::OR: {
2477     if (N->getValueType(0) == MVT::i32)
2478       if (SDNode *I = SelectBitfieldInsert(N))
2479         return I;
2480
2481     short Imm;
2482     if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
2483         isIntS16Immediate(N->getOperand(1), Imm)) {
2484       APInt LHSKnownZero, LHSKnownOne;
2485       CurDAG->computeKnownBits(N->getOperand(0), LHSKnownZero, LHSKnownOne);
2486
2487       // If this is equivalent to an add, then we can fold it with the
2488       // FrameIndex calculation.
2489       if ((LHSKnownZero.getZExtValue()|~(uint64_t)Imm) == ~0ULL)
2490         return getFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
2491     }
2492
2493     // Other cases are autogenerated.
2494     break;
2495   }
2496   case ISD::ADD: {
2497     short Imm;
2498     if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
2499         isIntS16Immediate(N->getOperand(1), Imm))
2500       return getFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
2501
2502     break;
2503   }
2504   case ISD::SHL: {
2505     unsigned Imm, SH, MB, ME;
2506     if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
2507         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
2508       SDValue Ops[] = { N->getOperand(0).getOperand(0),
2509                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
2510       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2511     }
2512
2513     // Other cases are autogenerated.
2514     break;
2515   }
2516   case ISD::SRL: {
2517     unsigned Imm, SH, MB, ME;
2518     if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
2519         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
2520       SDValue Ops[] = { N->getOperand(0).getOperand(0),
2521                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
2522       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2523     }
2524
2525     // Other cases are autogenerated.
2526     break;
2527   }
2528   // FIXME: Remove this once the ANDI glue bug is fixed:
2529   case PPCISD::ANDIo_1_EQ_BIT:
2530   case PPCISD::ANDIo_1_GT_BIT: {
2531     if (!ANDIGlueBug)
2532       break;
2533
2534     EVT InVT = N->getOperand(0).getValueType();
2535     assert((InVT == MVT::i64 || InVT == MVT::i32) &&
2536            "Invalid input type for ANDIo_1_EQ_BIT");
2537
2538     unsigned Opcode = (InVT == MVT::i64) ? PPC::ANDIo8 : PPC::ANDIo;
2539     SDValue AndI(CurDAG->getMachineNode(Opcode, dl, InVT, MVT::Glue,
2540                                         N->getOperand(0),
2541                                         CurDAG->getTargetConstant(1, InVT)), 0);
2542     SDValue CR0Reg = CurDAG->getRegister(PPC::CR0, MVT::i32);
2543     SDValue SRIdxVal =
2544       CurDAG->getTargetConstant(N->getOpcode() == PPCISD::ANDIo_1_EQ_BIT ?
2545                                 PPC::sub_eq : PPC::sub_gt, MVT::i32);
2546
2547     return CurDAG->SelectNodeTo(N, TargetOpcode::EXTRACT_SUBREG, MVT::i1,
2548                                 CR0Reg, SRIdxVal,
2549                                 SDValue(AndI.getNode(), 1) /* glue */);
2550   }
2551   case ISD::SELECT_CC: {
2552     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
2553     EVT PtrVT = CurDAG->getTargetLoweringInfo().getPointerTy();
2554     bool isPPC64 = (PtrVT == MVT::i64);
2555
2556     // If this is a select of i1 operands, we'll pattern match it.
2557     if (PPCSubTarget->useCRBits() &&
2558         N->getOperand(0).getValueType() == MVT::i1)
2559       break;
2560
2561     // Handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
2562     if (!isPPC64)
2563       if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2564         if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
2565           if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
2566             if (N1C->isNullValue() && N3C->isNullValue() &&
2567                 N2C->getZExtValue() == 1ULL && CC == ISD::SETNE &&
2568                 // FIXME: Implement this optzn for PPC64.
2569                 N->getValueType(0) == MVT::i32) {
2570               SDNode *Tmp =
2571                 CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2572                                        N->getOperand(0), getI32Imm(~0U));
2573               return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
2574                                           SDValue(Tmp, 0), N->getOperand(0),
2575                                           SDValue(Tmp, 1));
2576             }
2577
2578     SDValue CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC, dl);
2579
2580     if (N->getValueType(0) == MVT::i1) {
2581       // An i1 select is: (c & t) | (!c & f).
2582       bool Inv;
2583       unsigned Idx = getCRIdxForSetCC(CC, Inv);
2584
2585       unsigned SRI;
2586       switch (Idx) {
2587       default: llvm_unreachable("Invalid CC index");
2588       case 0: SRI = PPC::sub_lt; break;
2589       case 1: SRI = PPC::sub_gt; break;
2590       case 2: SRI = PPC::sub_eq; break;
2591       case 3: SRI = PPC::sub_un; break;
2592       }
2593
2594       SDValue CCBit = CurDAG->getTargetExtractSubreg(SRI, dl, MVT::i1, CCReg);
2595
2596       SDValue NotCCBit(CurDAG->getMachineNode(PPC::CRNOR, dl, MVT::i1,
2597                                               CCBit, CCBit), 0);
2598       SDValue C =    Inv ? NotCCBit : CCBit,
2599               NotC = Inv ? CCBit    : NotCCBit;
2600
2601       SDValue CAndT(CurDAG->getMachineNode(PPC::CRAND, dl, MVT::i1,
2602                                            C, N->getOperand(2)), 0);
2603       SDValue NotCAndF(CurDAG->getMachineNode(PPC::CRAND, dl, MVT::i1,
2604                                               NotC, N->getOperand(3)), 0);
2605
2606       return CurDAG->SelectNodeTo(N, PPC::CROR, MVT::i1, CAndT, NotCAndF);
2607     }
2608
2609     unsigned BROpc = getPredicateForSetCC(CC);
2610
2611     unsigned SelectCCOp;
2612     if (N->getValueType(0) == MVT::i32)
2613       SelectCCOp = PPC::SELECT_CC_I4;
2614     else if (N->getValueType(0) == MVT::i64)
2615       SelectCCOp = PPC::SELECT_CC_I8;
2616     else if (N->getValueType(0) == MVT::f32)
2617       SelectCCOp = PPC::SELECT_CC_F4;
2618     else if (N->getValueType(0) == MVT::f64)
2619       if (PPCSubTarget->hasVSX())
2620         SelectCCOp = PPC::SELECT_CC_VSFRC;
2621       else
2622         SelectCCOp = PPC::SELECT_CC_F8;
2623     else if (N->getValueType(0) == MVT::v2f64 ||
2624              N->getValueType(0) == MVT::v2i64)
2625       SelectCCOp = PPC::SELECT_CC_VSRC;
2626     else
2627       SelectCCOp = PPC::SELECT_CC_VRRC;
2628
2629     SDValue Ops[] = { CCReg, N->getOperand(2), N->getOperand(3),
2630                         getI32Imm(BROpc) };
2631     return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), Ops);
2632   }
2633   case ISD::VSELECT:
2634     if (PPCSubTarget->hasVSX()) {
2635       SDValue Ops[] = { N->getOperand(2), N->getOperand(1), N->getOperand(0) };
2636       return CurDAG->SelectNodeTo(N, PPC::XXSEL, N->getValueType(0), Ops);
2637     }
2638
2639     break;
2640   case ISD::VECTOR_SHUFFLE:
2641     if (PPCSubTarget->hasVSX() && (N->getValueType(0) == MVT::v2f64 ||
2642                                   N->getValueType(0) == MVT::v2i64)) {
2643       ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
2644
2645       SDValue Op1 = N->getOperand(SVN->getMaskElt(0) < 2 ? 0 : 1),
2646               Op2 = N->getOperand(SVN->getMaskElt(1) < 2 ? 0 : 1);
2647       unsigned DM[2];
2648
2649       for (int i = 0; i < 2; ++i)
2650         if (SVN->getMaskElt(i) <= 0 || SVN->getMaskElt(i) == 2)
2651           DM[i] = 0;
2652         else
2653           DM[i] = 1;
2654
2655       // For little endian, we must swap the input operands and adjust
2656       // the mask elements (reverse and invert them).
2657       if (PPCSubTarget->isLittleEndian()) {
2658         std::swap(Op1, Op2);
2659         unsigned tmp = DM[0];
2660         DM[0] = 1 - DM[1];
2661         DM[1] = 1 - tmp;
2662       }
2663
2664       SDValue DMV = CurDAG->getTargetConstant(DM[1] | (DM[0] << 1), MVT::i32);
2665
2666       if (Op1 == Op2 && DM[0] == 0 && DM[1] == 0 &&
2667           Op1.getOpcode() == ISD::SCALAR_TO_VECTOR &&
2668           isa<LoadSDNode>(Op1.getOperand(0))) {
2669         LoadSDNode *LD = cast<LoadSDNode>(Op1.getOperand(0));
2670         SDValue Base, Offset;
2671
2672         if (LD->isUnindexed() &&
2673             SelectAddrIdxOnly(LD->getBasePtr(), Base, Offset)) {
2674           SDValue Chain = LD->getChain();
2675           SDValue Ops[] = { Base, Offset, Chain };
2676           return CurDAG->SelectNodeTo(N, PPC::LXVDSX,
2677                                       N->getValueType(0), Ops);
2678         }
2679       }
2680
2681       SDValue Ops[] = { Op1, Op2, DMV };
2682       return CurDAG->SelectNodeTo(N, PPC::XXPERMDI, N->getValueType(0), Ops);
2683     }
2684
2685     break;
2686   case PPCISD::BDNZ:
2687   case PPCISD::BDZ: {
2688     bool IsPPC64 = PPCSubTarget->isPPC64();
2689     SDValue Ops[] = { N->getOperand(1), N->getOperand(0) };
2690     return CurDAG->SelectNodeTo(N, N->getOpcode() == PPCISD::BDNZ ?
2691                                    (IsPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
2692                                    (IsPPC64 ? PPC::BDZ8 : PPC::BDZ),
2693                                 MVT::Other, Ops);
2694   }
2695   case PPCISD::COND_BRANCH: {
2696     // Op #0 is the Chain.
2697     // Op #1 is the PPC::PRED_* number.
2698     // Op #2 is the CR#
2699     // Op #3 is the Dest MBB
2700     // Op #4 is the Flag.
2701     // Prevent PPC::PRED_* from being selected into LI.
2702     SDValue Pred =
2703       getI32Imm(cast<ConstantSDNode>(N->getOperand(1))->getZExtValue());
2704     SDValue Ops[] = { Pred, N->getOperand(2), N->getOperand(3),
2705       N->getOperand(0), N->getOperand(4) };
2706     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
2707   }
2708   case ISD::BR_CC: {
2709     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
2710     unsigned PCC = getPredicateForSetCC(CC);
2711
2712     if (N->getOperand(2).getValueType() == MVT::i1) {
2713       unsigned Opc;
2714       bool Swap;
2715       switch (PCC) {
2716       default: llvm_unreachable("Unexpected Boolean-operand predicate");
2717       case PPC::PRED_LT: Opc = PPC::CRANDC; Swap = true;  break;
2718       case PPC::PRED_LE: Opc = PPC::CRORC;  Swap = true;  break;
2719       case PPC::PRED_EQ: Opc = PPC::CREQV;  Swap = false; break;
2720       case PPC::PRED_GE: Opc = PPC::CRORC;  Swap = false; break;
2721       case PPC::PRED_GT: Opc = PPC::CRANDC; Swap = false; break;
2722       case PPC::PRED_NE: Opc = PPC::CRXOR;  Swap = false; break;
2723       }
2724
2725       SDValue BitComp(CurDAG->getMachineNode(Opc, dl, MVT::i1,
2726                                              N->getOperand(Swap ? 3 : 2),
2727                                              N->getOperand(Swap ? 2 : 3)), 0);
2728       return CurDAG->SelectNodeTo(N, PPC::BC, MVT::Other,
2729                                   BitComp, N->getOperand(4), N->getOperand(0));
2730     }
2731
2732     SDValue CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC, dl);
2733     SDValue Ops[] = { getI32Imm(PCC), CondCode,
2734                         N->getOperand(4), N->getOperand(0) };
2735     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
2736   }
2737   case ISD::BRIND: {
2738     // FIXME: Should custom lower this.
2739     SDValue Chain = N->getOperand(0);
2740     SDValue Target = N->getOperand(1);
2741     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
2742     unsigned Reg = Target.getValueType() == MVT::i32 ? PPC::BCTR : PPC::BCTR8;
2743     Chain = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, Target,
2744                                            Chain), 0);
2745     return CurDAG->SelectNodeTo(N, Reg, MVT::Other, Chain);
2746   }
2747   case PPCISD::TOC_ENTRY: {
2748     assert ((PPCSubTarget->isPPC64() || PPCSubTarget->isSVR4ABI()) &&
2749             "Only supported for 64-bit ABI and 32-bit SVR4");
2750     if (PPCSubTarget->isSVR4ABI() && !PPCSubTarget->isPPC64()) {
2751       SDValue GA = N->getOperand(0);
2752       return CurDAG->getMachineNode(PPC::LWZtoc, dl, MVT::i32, GA,
2753                                     N->getOperand(1));
2754     }
2755
2756     // For medium and large code model, we generate two instructions as
2757     // described below.  Otherwise we allow SelectCodeCommon to handle this,
2758     // selecting one of LDtoc, LDtocJTI, LDtocCPT, and LDtocBA.
2759     CodeModel::Model CModel = TM.getCodeModel();
2760     if (CModel != CodeModel::Medium && CModel != CodeModel::Large)
2761       break;
2762
2763     // The first source operand is a TargetGlobalAddress or a TargetJumpTable.
2764     // If it is an externally defined symbol, a symbol with common linkage,
2765     // a non-local function address, or a jump table address, or if we are
2766     // generating code for large code model, we generate:
2767     //   LDtocL(<ga:@sym>, ADDIStocHA(%X2, <ga:@sym>))
2768     // Otherwise we generate:
2769     //   ADDItocL(ADDIStocHA(%X2, <ga:@sym>), <ga:@sym>)
2770     SDValue GA = N->getOperand(0);
2771     SDValue TOCbase = N->getOperand(1);
2772     SDNode *Tmp = CurDAG->getMachineNode(PPC::ADDIStocHA, dl, MVT::i64,
2773                                         TOCbase, GA);
2774
2775     if (isa<JumpTableSDNode>(GA) || isa<BlockAddressSDNode>(GA) ||
2776         CModel == CodeModel::Large)
2777       return CurDAG->getMachineNode(PPC::LDtocL, dl, MVT::i64, GA,
2778                                     SDValue(Tmp, 0));
2779
2780     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(GA)) {
2781       const GlobalValue *GValue = G->getGlobal();
2782       if ((GValue->getType()->getElementType()->isFunctionTy() &&
2783            (GValue->isDeclaration() || GValue->isWeakForLinker())) ||
2784           GValue->isDeclaration() || GValue->hasCommonLinkage() ||
2785           GValue->hasAvailableExternallyLinkage())
2786         return CurDAG->getMachineNode(PPC::LDtocL, dl, MVT::i64, GA,
2787                                       SDValue(Tmp, 0));
2788     }
2789
2790     return CurDAG->getMachineNode(PPC::ADDItocL, dl, MVT::i64,
2791                                   SDValue(Tmp, 0), GA);
2792   }
2793   case PPCISD::PPC32_PICGOT: {
2794     // Generate a PIC-safe GOT reference.
2795     assert(!PPCSubTarget->isPPC64() && PPCSubTarget->isSVR4ABI() &&
2796       "PPCISD::PPC32_PICGOT is only supported for 32-bit SVR4");
2797     return CurDAG->SelectNodeTo(N, PPC::PPC32PICGOT, PPCLowering->getPointerTy(),  MVT::i32);
2798   }
2799   case PPCISD::VADD_SPLAT: {
2800     // This expands into one of three sequences, depending on whether
2801     // the first operand is odd or even, positive or negative.
2802     assert(isa<ConstantSDNode>(N->getOperand(0)) &&
2803            isa<ConstantSDNode>(N->getOperand(1)) &&
2804            "Invalid operand on VADD_SPLAT!");
2805
2806     int Elt     = N->getConstantOperandVal(0);
2807     int EltSize = N->getConstantOperandVal(1);
2808     unsigned Opc1, Opc2, Opc3;
2809     EVT VT;
2810
2811     if (EltSize == 1) {
2812       Opc1 = PPC::VSPLTISB;
2813       Opc2 = PPC::VADDUBM;
2814       Opc3 = PPC::VSUBUBM;
2815       VT = MVT::v16i8;
2816     } else if (EltSize == 2) {
2817       Opc1 = PPC::VSPLTISH;
2818       Opc2 = PPC::VADDUHM;
2819       Opc3 = PPC::VSUBUHM;
2820       VT = MVT::v8i16;
2821     } else {
2822       assert(EltSize == 4 && "Invalid element size on VADD_SPLAT!");
2823       Opc1 = PPC::VSPLTISW;
2824       Opc2 = PPC::VADDUWM;
2825       Opc3 = PPC::VSUBUWM;
2826       VT = MVT::v4i32;
2827     }
2828
2829     if ((Elt & 1) == 0) {
2830       // Elt is even, in the range [-32,-18] + [16,30].
2831       //
2832       // Convert: VADD_SPLAT elt, size
2833       // Into:    tmp = VSPLTIS[BHW] elt
2834       //          VADDU[BHW]M tmp, tmp
2835       // Where:   [BHW] = B for size = 1, H for size = 2, W for size = 4
2836       SDValue EltVal = getI32Imm(Elt >> 1);
2837       SDNode *Tmp = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2838       SDValue TmpVal = SDValue(Tmp, 0);
2839       return CurDAG->getMachineNode(Opc2, dl, VT, TmpVal, TmpVal);
2840
2841     } else if (Elt > 0) {
2842       // Elt is odd and positive, in the range [17,31].
2843       //
2844       // Convert: VADD_SPLAT elt, size
2845       // Into:    tmp1 = VSPLTIS[BHW] elt-16
2846       //          tmp2 = VSPLTIS[BHW] -16
2847       //          VSUBU[BHW]M tmp1, tmp2
2848       SDValue EltVal = getI32Imm(Elt - 16);
2849       SDNode *Tmp1 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2850       EltVal = getI32Imm(-16);
2851       SDNode *Tmp2 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2852       return CurDAG->getMachineNode(Opc3, dl, VT, SDValue(Tmp1, 0),
2853                                     SDValue(Tmp2, 0));
2854
2855     } else {
2856       // Elt is odd and negative, in the range [-31,-17].
2857       //
2858       // Convert: VADD_SPLAT elt, size
2859       // Into:    tmp1 = VSPLTIS[BHW] elt+16
2860       //          tmp2 = VSPLTIS[BHW] -16
2861       //          VADDU[BHW]M tmp1, tmp2
2862       SDValue EltVal = getI32Imm(Elt + 16);
2863       SDNode *Tmp1 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2864       EltVal = getI32Imm(-16);
2865       SDNode *Tmp2 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2866       return CurDAG->getMachineNode(Opc2, dl, VT, SDValue(Tmp1, 0),
2867                                     SDValue(Tmp2, 0));
2868     }
2869   }
2870   }
2871
2872   return SelectCode(N);
2873 }
2874
2875 /// PostprocessISelDAG - Perform some late peephole optimizations
2876 /// on the DAG representation.
2877 void PPCDAGToDAGISel::PostprocessISelDAG() {
2878
2879   // Skip peepholes at -O0.
2880   if (TM.getOptLevel() == CodeGenOpt::None)
2881     return;
2882
2883   PeepholePPC64();
2884   PeepholeCROps();
2885   PeepholePPC64ZExt();
2886 }
2887
2888 // Check if all users of this node will become isel where the second operand
2889 // is the constant zero. If this is so, and if we can negate the condition,
2890 // then we can flip the true and false operands. This will allow the zero to
2891 // be folded with the isel so that we don't need to materialize a register
2892 // containing zero.
2893 bool PPCDAGToDAGISel::AllUsersSelectZero(SDNode *N) {
2894   // If we're not using isel, then this does not matter.
2895   if (!PPCSubTarget->hasISEL())
2896     return false;
2897
2898   for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
2899        UI != UE; ++UI) {
2900     SDNode *User = *UI;
2901     if (!User->isMachineOpcode())
2902       return false;
2903     if (User->getMachineOpcode() != PPC::SELECT_I4 &&
2904         User->getMachineOpcode() != PPC::SELECT_I8)
2905       return false;
2906
2907     SDNode *Op2 = User->getOperand(2).getNode();
2908     if (!Op2->isMachineOpcode())
2909       return false;
2910
2911     if (Op2->getMachineOpcode() != PPC::LI &&
2912         Op2->getMachineOpcode() != PPC::LI8)
2913       return false;
2914
2915     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op2->getOperand(0));
2916     if (!C)
2917       return false;
2918
2919     if (!C->isNullValue())
2920       return false;
2921   }
2922
2923   return true;
2924 }
2925
2926 void PPCDAGToDAGISel::SwapAllSelectUsers(SDNode *N) {
2927   SmallVector<SDNode *, 4> ToReplace;
2928   for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
2929        UI != UE; ++UI) {
2930     SDNode *User = *UI;
2931     assert((User->getMachineOpcode() == PPC::SELECT_I4 ||
2932             User->getMachineOpcode() == PPC::SELECT_I8) &&
2933            "Must have all select users");
2934     ToReplace.push_back(User);
2935   }
2936
2937   for (SmallVector<SDNode *, 4>::iterator UI = ToReplace.begin(),
2938        UE = ToReplace.end(); UI != UE; ++UI) {
2939     SDNode *User = *UI;
2940     SDNode *ResNode =
2941       CurDAG->getMachineNode(User->getMachineOpcode(), SDLoc(User),
2942                              User->getValueType(0), User->getOperand(0),
2943                              User->getOperand(2),
2944                              User->getOperand(1));
2945
2946       DEBUG(dbgs() << "CR Peephole replacing:\nOld:    ");
2947       DEBUG(User->dump(CurDAG));
2948       DEBUG(dbgs() << "\nNew: ");
2949       DEBUG(ResNode->dump(CurDAG));
2950       DEBUG(dbgs() << "\n");
2951
2952       ReplaceUses(User, ResNode);
2953   }
2954 }
2955
2956 void PPCDAGToDAGISel::PeepholeCROps() {
2957   bool IsModified;
2958   do {
2959     IsModified = false;
2960     for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
2961          E = CurDAG->allnodes_end(); I != E; ++I) {
2962       MachineSDNode *MachineNode = dyn_cast<MachineSDNode>(I);
2963       if (!MachineNode || MachineNode->use_empty())
2964         continue;
2965       SDNode *ResNode = MachineNode;
2966
2967       bool Op1Set   = false, Op1Unset = false,
2968            Op1Not   = false,
2969            Op2Set   = false, Op2Unset = false,
2970            Op2Not   = false;
2971
2972       unsigned Opcode = MachineNode->getMachineOpcode();
2973       switch (Opcode) {
2974       default: break;
2975       case PPC::CRAND:
2976       case PPC::CRNAND:
2977       case PPC::CROR:
2978       case PPC::CRXOR:
2979       case PPC::CRNOR:
2980       case PPC::CREQV:
2981       case PPC::CRANDC:
2982       case PPC::CRORC: {
2983         SDValue Op = MachineNode->getOperand(1);
2984         if (Op.isMachineOpcode()) {
2985           if (Op.getMachineOpcode() == PPC::CRSET)
2986             Op2Set = true;
2987           else if (Op.getMachineOpcode() == PPC::CRUNSET)
2988             Op2Unset = true;
2989           else if (Op.getMachineOpcode() == PPC::CRNOR &&
2990                    Op.getOperand(0) == Op.getOperand(1))
2991             Op2Not = true;
2992         }
2993         }  // fallthrough
2994       case PPC::BC:
2995       case PPC::BCn:
2996       case PPC::SELECT_I4:
2997       case PPC::SELECT_I8:
2998       case PPC::SELECT_F4:
2999       case PPC::SELECT_F8:
3000       case PPC::SELECT_VRRC:
3001       case PPC::SELECT_VSFRC:
3002       case PPC::SELECT_VSRC: {
3003         SDValue Op = MachineNode->getOperand(0);
3004         if (Op.isMachineOpcode()) {
3005           if (Op.getMachineOpcode() == PPC::CRSET)
3006             Op1Set = true;
3007           else if (Op.getMachineOpcode() == PPC::CRUNSET)
3008             Op1Unset = true;
3009           else if (Op.getMachineOpcode() == PPC::CRNOR &&
3010                    Op.getOperand(0) == Op.getOperand(1))
3011             Op1Not = true;
3012         }
3013         }
3014         break;
3015       }
3016
3017       bool SelectSwap = false;
3018       switch (Opcode) {
3019       default: break;
3020       case PPC::CRAND:
3021         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3022           // x & x = x
3023           ResNode = MachineNode->getOperand(0).getNode();
3024         else if (Op1Set)
3025           // 1 & y = y
3026           ResNode = MachineNode->getOperand(1).getNode();
3027         else if (Op2Set)
3028           // x & 1 = x
3029           ResNode = MachineNode->getOperand(0).getNode();
3030         else if (Op1Unset || Op2Unset)
3031           // x & 0 = 0 & y = 0
3032           ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3033                                            MVT::i1);
3034         else if (Op1Not)
3035           // ~x & y = andc(y, x)
3036           ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3037                                            MVT::i1, MachineNode->getOperand(1),
3038                                            MachineNode->getOperand(0).
3039                                              getOperand(0));
3040         else if (Op2Not)
3041           // x & ~y = andc(x, y)
3042           ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3043                                            MVT::i1, MachineNode->getOperand(0),
3044                                            MachineNode->getOperand(1).
3045                                              getOperand(0));
3046         else if (AllUsersSelectZero(MachineNode))
3047           ResNode = CurDAG->getMachineNode(PPC::CRNAND, SDLoc(MachineNode),
3048                                            MVT::i1, MachineNode->getOperand(0),
3049                                            MachineNode->getOperand(1)),
3050           SelectSwap = true;
3051         break;
3052       case PPC::CRNAND:
3053         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3054           // nand(x, x) -> nor(x, x)
3055           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3056                                            MVT::i1, MachineNode->getOperand(0),
3057                                            MachineNode->getOperand(0));
3058         else if (Op1Set)
3059           // nand(1, y) -> nor(y, y)
3060           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3061                                            MVT::i1, MachineNode->getOperand(1),
3062                                            MachineNode->getOperand(1));
3063         else if (Op2Set)
3064           // nand(x, 1) -> nor(x, x)
3065           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3066                                            MVT::i1, MachineNode->getOperand(0),
3067                                            MachineNode->getOperand(0));
3068         else if (Op1Unset || Op2Unset)
3069           // nand(x, 0) = nand(0, y) = 1
3070           ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3071                                            MVT::i1);
3072         else if (Op1Not)
3073           // nand(~x, y) = ~(~x & y) = x | ~y = orc(x, y)
3074           ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3075                                            MVT::i1, MachineNode->getOperand(0).
3076                                                       getOperand(0),
3077                                            MachineNode->getOperand(1));
3078         else if (Op2Not)
3079           // nand(x, ~y) = ~x | y = orc(y, x)
3080           ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3081                                            MVT::i1, MachineNode->getOperand(1).
3082                                                       getOperand(0),
3083                                            MachineNode->getOperand(0));
3084         else if (AllUsersSelectZero(MachineNode))
3085           ResNode = CurDAG->getMachineNode(PPC::CRAND, SDLoc(MachineNode),
3086                                            MVT::i1, MachineNode->getOperand(0),
3087                                            MachineNode->getOperand(1)),
3088           SelectSwap = true;
3089         break;
3090       case PPC::CROR:
3091         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3092           // x | x = x
3093           ResNode = MachineNode->getOperand(0).getNode();
3094         else if (Op1Set || Op2Set)
3095           // x | 1 = 1 | y = 1
3096           ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3097                                            MVT::i1);
3098         else if (Op1Unset)
3099           // 0 | y = y
3100           ResNode = MachineNode->getOperand(1).getNode();
3101         else if (Op2Unset)
3102           // x | 0 = x
3103           ResNode = MachineNode->getOperand(0).getNode();
3104         else if (Op1Not)
3105           // ~x | y = orc(y, x)
3106           ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3107                                            MVT::i1, MachineNode->getOperand(1),
3108                                            MachineNode->getOperand(0).
3109                                              getOperand(0));
3110         else if (Op2Not)
3111           // x | ~y = orc(x, y)
3112           ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3113                                            MVT::i1, MachineNode->getOperand(0),
3114                                            MachineNode->getOperand(1).
3115                                              getOperand(0));
3116         else if (AllUsersSelectZero(MachineNode))
3117           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3118                                            MVT::i1, MachineNode->getOperand(0),
3119                                            MachineNode->getOperand(1)),
3120           SelectSwap = true;
3121         break;
3122       case PPC::CRXOR:
3123         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3124           // xor(x, x) = 0
3125           ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3126                                            MVT::i1);
3127         else if (Op1Set)
3128           // xor(1, y) -> nor(y, y)
3129           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3130                                            MVT::i1, MachineNode->getOperand(1),
3131                                            MachineNode->getOperand(1));
3132         else if (Op2Set)
3133           // xor(x, 1) -> nor(x, x)
3134           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3135                                            MVT::i1, MachineNode->getOperand(0),
3136                                            MachineNode->getOperand(0));
3137         else if (Op1Unset)
3138           // xor(0, y) = y
3139           ResNode = MachineNode->getOperand(1).getNode();
3140         else if (Op2Unset)
3141           // xor(x, 0) = x
3142           ResNode = MachineNode->getOperand(0).getNode();
3143         else if (Op1Not)
3144           // xor(~x, y) = eqv(x, y)
3145           ResNode = CurDAG->getMachineNode(PPC::CREQV, SDLoc(MachineNode),
3146                                            MVT::i1, MachineNode->getOperand(0).
3147                                                       getOperand(0),
3148                                            MachineNode->getOperand(1));
3149         else if (Op2Not)
3150           // xor(x, ~y) = eqv(x, y)
3151           ResNode = CurDAG->getMachineNode(PPC::CREQV, SDLoc(MachineNode),
3152                                            MVT::i1, MachineNode->getOperand(0),
3153                                            MachineNode->getOperand(1).
3154                                              getOperand(0));
3155         else if (AllUsersSelectZero(MachineNode))
3156           ResNode = CurDAG->getMachineNode(PPC::CREQV, SDLoc(MachineNode),
3157                                            MVT::i1, MachineNode->getOperand(0),
3158                                            MachineNode->getOperand(1)),
3159           SelectSwap = true;
3160         break;
3161       case PPC::CRNOR:
3162         if (Op1Set || Op2Set)
3163           // nor(1, y) -> 0
3164           ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3165                                            MVT::i1);
3166         else if (Op1Unset)
3167           // nor(0, y) = ~y -> nor(y, y)
3168           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3169                                            MVT::i1, MachineNode->getOperand(1),
3170                                            MachineNode->getOperand(1));
3171         else if (Op2Unset)
3172           // nor(x, 0) = ~x
3173           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3174                                            MVT::i1, MachineNode->getOperand(0),
3175                                            MachineNode->getOperand(0));
3176         else if (Op1Not)
3177           // nor(~x, y) = andc(x, y)
3178           ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3179                                            MVT::i1, MachineNode->getOperand(0).
3180                                                       getOperand(0),
3181                                            MachineNode->getOperand(1));
3182         else if (Op2Not)
3183           // nor(x, ~y) = andc(y, x)
3184           ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3185                                            MVT::i1, MachineNode->getOperand(1).
3186                                                       getOperand(0),
3187                                            MachineNode->getOperand(0));
3188         else if (AllUsersSelectZero(MachineNode))
3189           ResNode = CurDAG->getMachineNode(PPC::CROR, SDLoc(MachineNode),
3190                                            MVT::i1, MachineNode->getOperand(0),
3191                                            MachineNode->getOperand(1)),
3192           SelectSwap = true;
3193         break;
3194       case PPC::CREQV:
3195         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3196           // eqv(x, x) = 1
3197           ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3198                                            MVT::i1);
3199         else if (Op1Set)
3200           // eqv(1, y) = y
3201           ResNode = MachineNode->getOperand(1).getNode();
3202         else if (Op2Set)
3203           // eqv(x, 1) = x
3204           ResNode = MachineNode->getOperand(0).getNode();
3205         else if (Op1Unset)
3206           // eqv(0, y) = ~y -> nor(y, y)
3207           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3208                                            MVT::i1, MachineNode->getOperand(1),
3209                                            MachineNode->getOperand(1));
3210         else if (Op2Unset)
3211           // eqv(x, 0) = ~x
3212           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3213                                            MVT::i1, MachineNode->getOperand(0),
3214                                            MachineNode->getOperand(0));
3215         else if (Op1Not)
3216           // eqv(~x, y) = xor(x, y)
3217           ResNode = CurDAG->getMachineNode(PPC::CRXOR, SDLoc(MachineNode),
3218                                            MVT::i1, MachineNode->getOperand(0).
3219                                                       getOperand(0),
3220                                            MachineNode->getOperand(1));
3221         else if (Op2Not)
3222           // eqv(x, ~y) = xor(x, y)
3223           ResNode = CurDAG->getMachineNode(PPC::CRXOR, SDLoc(MachineNode),
3224                                            MVT::i1, MachineNode->getOperand(0),
3225                                            MachineNode->getOperand(1).
3226                                              getOperand(0));
3227         else if (AllUsersSelectZero(MachineNode))
3228           ResNode = CurDAG->getMachineNode(PPC::CRXOR, SDLoc(MachineNode),
3229                                            MVT::i1, MachineNode->getOperand(0),
3230                                            MachineNode->getOperand(1)),
3231           SelectSwap = true;
3232         break;
3233       case PPC::CRANDC:
3234         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3235           // andc(x, x) = 0
3236           ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3237                                            MVT::i1);
3238         else if (Op1Set)
3239           // andc(1, y) = ~y
3240           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3241                                            MVT::i1, MachineNode->getOperand(1),
3242                                            MachineNode->getOperand(1));
3243         else if (Op1Unset || Op2Set)
3244           // andc(0, y) = andc(x, 1) = 0
3245           ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3246                                            MVT::i1);
3247         else if (Op2Unset)
3248           // andc(x, 0) = x
3249           ResNode = MachineNode->getOperand(0).getNode();
3250         else if (Op1Not)
3251           // andc(~x, y) = ~(x | y) = nor(x, y)
3252           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3253                                            MVT::i1, MachineNode->getOperand(0).
3254                                                       getOperand(0),
3255                                            MachineNode->getOperand(1));
3256         else if (Op2Not)
3257           // andc(x, ~y) = x & y
3258           ResNode = CurDAG->getMachineNode(PPC::CRAND, SDLoc(MachineNode),
3259                                            MVT::i1, MachineNode->getOperand(0),
3260                                            MachineNode->getOperand(1).
3261                                              getOperand(0));
3262         else if (AllUsersSelectZero(MachineNode))
3263           ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3264                                            MVT::i1, MachineNode->getOperand(1),
3265                                            MachineNode->getOperand(0)),
3266           SelectSwap = true;
3267         break;
3268       case PPC::CRORC:
3269         if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3270           // orc(x, x) = 1
3271           ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3272                                            MVT::i1);
3273         else if (Op1Set || Op2Unset)
3274           // orc(1, y) = orc(x, 0) = 1
3275           ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3276                                            MVT::i1);
3277         else if (Op2Set)
3278           // orc(x, 1) = x
3279           ResNode = MachineNode->getOperand(0).getNode();
3280         else if (Op1Unset)
3281           // orc(0, y) = ~y
3282           ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3283                                            MVT::i1, MachineNode->getOperand(1),
3284                                            MachineNode->getOperand(1));
3285         else if (Op1Not)
3286           // orc(~x, y) = ~(x & y) = nand(x, y)
3287           ResNode = CurDAG->getMachineNode(PPC::CRNAND, SDLoc(MachineNode),
3288                                            MVT::i1, MachineNode->getOperand(0).
3289                                                       getOperand(0),
3290                                            MachineNode->getOperand(1));
3291         else if (Op2Not)
3292           // orc(x, ~y) = x | y
3293           ResNode = CurDAG->getMachineNode(PPC::CROR, SDLoc(MachineNode),
3294                                            MVT::i1, MachineNode->getOperand(0),
3295                                            MachineNode->getOperand(1).
3296                                              getOperand(0));
3297         else if (AllUsersSelectZero(MachineNode))
3298           ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3299                                            MVT::i1, MachineNode->getOperand(1),
3300                                            MachineNode->getOperand(0)),
3301           SelectSwap = true;
3302         break;
3303       case PPC::SELECT_I4:
3304       case PPC::SELECT_I8:
3305       case PPC::SELECT_F4:
3306       case PPC::SELECT_F8:
3307       case PPC::SELECT_VRRC:
3308       case PPC::SELECT_VSFRC:
3309       case PPC::SELECT_VSRC:
3310         if (Op1Set)
3311           ResNode = MachineNode->getOperand(1).getNode();
3312         else if (Op1Unset)
3313           ResNode = MachineNode->getOperand(2).getNode();
3314         else if (Op1Not)
3315           ResNode = CurDAG->getMachineNode(MachineNode->getMachineOpcode(),
3316                                            SDLoc(MachineNode),
3317                                            MachineNode->getValueType(0),
3318                                            MachineNode->getOperand(0).
3319                                              getOperand(0),
3320                                            MachineNode->getOperand(2),
3321                                            MachineNode->getOperand(1));
3322         break;
3323       case PPC::BC:
3324       case PPC::BCn:
3325         if (Op1Not)
3326           ResNode = CurDAG->getMachineNode(Opcode == PPC::BC ? PPC::BCn :
3327                                                                PPC::BC,
3328                                            SDLoc(MachineNode),
3329                                            MVT::Other,
3330                                            MachineNode->getOperand(0).
3331                                              getOperand(0),
3332                                            MachineNode->getOperand(1),
3333                                            MachineNode->getOperand(2));
3334         // FIXME: Handle Op1Set, Op1Unset here too.
3335         break;
3336       }
3337
3338       // If we're inverting this node because it is used only by selects that
3339       // we'd like to swap, then swap the selects before the node replacement.
3340       if (SelectSwap)
3341         SwapAllSelectUsers(MachineNode);
3342
3343       if (ResNode != MachineNode) {
3344         DEBUG(dbgs() << "CR Peephole replacing:\nOld:    ");
3345         DEBUG(MachineNode->dump(CurDAG));
3346         DEBUG(dbgs() << "\nNew: ");
3347         DEBUG(ResNode->dump(CurDAG));
3348         DEBUG(dbgs() << "\n");
3349
3350         ReplaceUses(MachineNode, ResNode);
3351         IsModified = true;
3352       }
3353     }
3354     if (IsModified)
3355       CurDAG->RemoveDeadNodes();
3356   } while (IsModified);
3357 }
3358
3359 // Gather the set of 32-bit operations that are known to have their
3360 // higher-order 32 bits zero, where ToPromote contains all such operations.
3361 static bool PeepholePPC64ZExtGather(SDValue Op32,
3362                                     SmallPtrSetImpl<SDNode *> &ToPromote) {
3363   if (!Op32.isMachineOpcode())
3364     return false;
3365
3366   // First, check for the "frontier" instructions (those that will clear the
3367   // higher-order 32 bits.
3368
3369   // For RLWINM and RLWNM, we need to make sure that the mask does not wrap
3370   // around. If it does not, then these instructions will clear the
3371   // higher-order bits.
3372   if ((Op32.getMachineOpcode() == PPC::RLWINM ||
3373        Op32.getMachineOpcode() == PPC::RLWNM) &&
3374       Op32.getConstantOperandVal(2) <= Op32.getConstantOperandVal(3)) {
3375     ToPromote.insert(Op32.getNode());
3376     return true;
3377   }
3378
3379   // SLW and SRW always clear the higher-order bits.
3380   if (Op32.getMachineOpcode() == PPC::SLW ||
3381       Op32.getMachineOpcode() == PPC::SRW) {
3382     ToPromote.insert(Op32.getNode());
3383     return true;
3384   }
3385
3386   // For LI and LIS, we need the immediate to be positive (so that it is not
3387   // sign extended).
3388   if (Op32.getMachineOpcode() == PPC::LI ||
3389       Op32.getMachineOpcode() == PPC::LIS) {
3390     if (!isUInt<15>(Op32.getConstantOperandVal(0)))
3391       return false;
3392
3393     ToPromote.insert(Op32.getNode());
3394     return true;
3395   }
3396
3397   // Next, check for those instructions we can look through.
3398
3399   // Assuming the mask does not wrap around, then the higher-order bits are
3400   // taken directly from the first operand.
3401   if (Op32.getMachineOpcode() == PPC::RLWIMI &&
3402       Op32.getConstantOperandVal(3) <= Op32.getConstantOperandVal(4)) {
3403     SmallPtrSet<SDNode *, 16> ToPromote1;
3404     if (!PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1))
3405       return false;
3406
3407     ToPromote.insert(Op32.getNode());
3408     ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3409     return true;
3410   }
3411
3412   // For OR, the higher-order bits are zero if that is true for both operands.
3413   // For SELECT_I4, the same is true (but the relevant operand numbers are
3414   // shifted by 1).
3415   if (Op32.getMachineOpcode() == PPC::OR ||
3416       Op32.getMachineOpcode() == PPC::SELECT_I4) {
3417     unsigned B = Op32.getMachineOpcode() == PPC::SELECT_I4 ? 1 : 0;
3418     SmallPtrSet<SDNode *, 16> ToPromote1;
3419     if (!PeepholePPC64ZExtGather(Op32.getOperand(B+0), ToPromote1))
3420       return false;
3421     if (!PeepholePPC64ZExtGather(Op32.getOperand(B+1), ToPromote1))
3422       return false;
3423
3424     ToPromote.insert(Op32.getNode());
3425     ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3426     return true;
3427   }
3428
3429   // For ORI and ORIS, we need the higher-order bits of the first operand to be
3430   // zero, and also for the constant to be positive (so that it is not sign
3431   // extended).
3432   if (Op32.getMachineOpcode() == PPC::ORI ||
3433       Op32.getMachineOpcode() == PPC::ORIS) {
3434     SmallPtrSet<SDNode *, 16> ToPromote1;
3435     if (!PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1))
3436       return false;
3437     if (!isUInt<15>(Op32.getConstantOperandVal(1)))
3438       return false;
3439
3440     ToPromote.insert(Op32.getNode());
3441     ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3442     return true;
3443   }
3444
3445   // The higher-order bits of AND are zero if that is true for at least one of
3446   // the operands.
3447   if (Op32.getMachineOpcode() == PPC::AND) {
3448     SmallPtrSet<SDNode *, 16> ToPromote1, ToPromote2;
3449     bool Op0OK =
3450       PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1);
3451     bool Op1OK =
3452       PeepholePPC64ZExtGather(Op32.getOperand(1), ToPromote2);
3453     if (!Op0OK && !Op1OK)
3454       return false;
3455
3456     ToPromote.insert(Op32.getNode());
3457
3458     if (Op0OK)
3459       ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3460
3461     if (Op1OK)
3462       ToPromote.insert(ToPromote2.begin(), ToPromote2.end());
3463
3464     return true;
3465   }
3466
3467   // For ANDI and ANDIS, the higher-order bits are zero if either that is true
3468   // of the first operand, or if the second operand is positive (so that it is
3469   // not sign extended).
3470   if (Op32.getMachineOpcode() == PPC::ANDIo ||
3471       Op32.getMachineOpcode() == PPC::ANDISo) {
3472     SmallPtrSet<SDNode *, 16> ToPromote1;
3473     bool Op0OK =
3474       PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1);
3475     bool Op1OK = isUInt<15>(Op32.getConstantOperandVal(1));
3476     if (!Op0OK && !Op1OK)
3477       return false;
3478
3479     ToPromote.insert(Op32.getNode());
3480
3481     if (Op0OK)
3482       ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3483
3484     return true;
3485   }
3486
3487   return false;
3488 }
3489
3490 void PPCDAGToDAGISel::PeepholePPC64ZExt() {
3491   if (!PPCSubTarget->isPPC64())
3492     return;
3493
3494   // When we zero-extend from i32 to i64, we use a pattern like this:
3495   // def : Pat<(i64 (zext i32:$in)),
3496   //           (RLDICL (INSERT_SUBREG (i64 (IMPLICIT_DEF)), $in, sub_32),
3497   //                   0, 32)>;
3498   // There are several 32-bit shift/rotate instructions, however, that will
3499   // clear the higher-order bits of their output, rendering the RLDICL
3500   // unnecessary. When that happens, we remove it here, and redefine the
3501   // relevant 32-bit operation to be a 64-bit operation.
3502
3503   SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
3504   ++Position;
3505
3506   bool MadeChange = false;
3507   while (Position != CurDAG->allnodes_begin()) {
3508     SDNode *N = --Position;
3509     // Skip dead nodes and any non-machine opcodes.
3510     if (N->use_empty() || !N->isMachineOpcode())
3511       continue;
3512
3513     if (N->getMachineOpcode() != PPC::RLDICL)
3514       continue;
3515
3516     if (N->getConstantOperandVal(1) != 0 ||
3517         N->getConstantOperandVal(2) != 32)
3518       continue;
3519
3520     SDValue ISR = N->getOperand(0);
3521     if (!ISR.isMachineOpcode() ||
3522         ISR.getMachineOpcode() != TargetOpcode::INSERT_SUBREG)
3523       continue;
3524
3525     if (!ISR.hasOneUse())
3526       continue;
3527
3528     if (ISR.getConstantOperandVal(2) != PPC::sub_32)
3529       continue;
3530
3531     SDValue IDef = ISR.getOperand(0);
3532     if (!IDef.isMachineOpcode() ||
3533         IDef.getMachineOpcode() != TargetOpcode::IMPLICIT_DEF)
3534       continue;
3535
3536     // We now know that we're looking at a canonical i32 -> i64 zext. See if we
3537     // can get rid of it.
3538
3539     SDValue Op32 = ISR->getOperand(1);
3540     if (!Op32.isMachineOpcode())
3541       continue;
3542
3543     // There are some 32-bit instructions that always clear the high-order 32
3544     // bits, there are also some instructions (like AND) that we can look
3545     // through.
3546     SmallPtrSet<SDNode *, 16> ToPromote;
3547     if (!PeepholePPC64ZExtGather(Op32, ToPromote))
3548       continue;
3549
3550     // If the ToPromote set contains nodes that have uses outside of the set
3551     // (except for the original INSERT_SUBREG), then abort the transformation.
3552     bool OutsideUse = false;
3553     for (SDNode *PN : ToPromote) {
3554       for (SDNode *UN : PN->uses()) {
3555         if (!ToPromote.count(UN) && UN != ISR.getNode()) {
3556           OutsideUse = true;
3557           break;
3558         }
3559       }
3560
3561       if (OutsideUse)
3562         break;
3563     }
3564     if (OutsideUse)
3565       continue;
3566
3567     MadeChange = true;
3568
3569     // We now know that this zero extension can be removed by promoting to
3570     // nodes in ToPromote to 64-bit operations, where for operations in the
3571     // frontier of the set, we need to insert INSERT_SUBREGs for their
3572     // operands.
3573     for (SDNode *PN : ToPromote) {
3574       unsigned NewOpcode;
3575       switch (PN->getMachineOpcode()) {
3576       default:
3577         llvm_unreachable("Don't know the 64-bit variant of this instruction");
3578       case PPC::RLWINM:    NewOpcode = PPC::RLWINM8; break;
3579       case PPC::RLWNM:     NewOpcode = PPC::RLWNM8; break;
3580       case PPC::SLW:       NewOpcode = PPC::SLW8; break;
3581       case PPC::SRW:       NewOpcode = PPC::SRW8; break;
3582       case PPC::LI:        NewOpcode = PPC::LI8; break;
3583       case PPC::LIS:       NewOpcode = PPC::LIS8; break;
3584       case PPC::RLWIMI:    NewOpcode = PPC::RLWIMI8; break;
3585       case PPC::OR:        NewOpcode = PPC::OR8; break;
3586       case PPC::SELECT_I4: NewOpcode = PPC::SELECT_I8; break;
3587       case PPC::ORI:       NewOpcode = PPC::ORI8; break;
3588       case PPC::ORIS:      NewOpcode = PPC::ORIS8; break;
3589       case PPC::AND:       NewOpcode = PPC::AND8; break;
3590       case PPC::ANDIo:     NewOpcode = PPC::ANDIo8; break;
3591       case PPC::ANDISo:    NewOpcode = PPC::ANDISo8; break;
3592       }
3593
3594       // Note: During the replacement process, the nodes will be in an
3595       // inconsistent state (some instructions will have operands with values
3596       // of the wrong type). Once done, however, everything should be right
3597       // again.
3598
3599       SmallVector<SDValue, 4> Ops;
3600       for (const SDValue &V : PN->ops()) {
3601         if (!ToPromote.count(V.getNode()) && V.getValueType() == MVT::i32 &&
3602             !isa<ConstantSDNode>(V)) {
3603           SDValue ReplOpOps[] = { ISR.getOperand(0), V, ISR.getOperand(2) };
3604           SDNode *ReplOp =
3605             CurDAG->getMachineNode(TargetOpcode::INSERT_SUBREG, SDLoc(V),
3606                                    ISR.getNode()->getVTList(), ReplOpOps);
3607           Ops.push_back(SDValue(ReplOp, 0));
3608         } else {
3609           Ops.push_back(V);
3610         }
3611       }
3612
3613       // Because all to-be-promoted nodes only have users that are other
3614       // promoted nodes (or the original INSERT_SUBREG), we can safely replace
3615       // the i32 result value type with i64.
3616
3617       SmallVector<EVT, 2> NewVTs;
3618       SDVTList VTs = PN->getVTList();
3619       for (unsigned i = 0, ie = VTs.NumVTs; i != ie; ++i)
3620         if (VTs.VTs[i] == MVT::i32)
3621           NewVTs.push_back(MVT::i64);
3622         else
3623           NewVTs.push_back(VTs.VTs[i]);
3624
3625       DEBUG(dbgs() << "PPC64 ZExt Peephole morphing:\nOld:    ");
3626       DEBUG(PN->dump(CurDAG));
3627
3628       CurDAG->SelectNodeTo(PN, NewOpcode, CurDAG->getVTList(NewVTs), Ops);
3629
3630       DEBUG(dbgs() << "\nNew: ");
3631       DEBUG(PN->dump(CurDAG));
3632       DEBUG(dbgs() << "\n");
3633     }
3634
3635     // Now we replace the original zero extend and its associated INSERT_SUBREG
3636     // with the value feeding the INSERT_SUBREG (which has now been promoted to
3637     // return an i64).
3638
3639     DEBUG(dbgs() << "PPC64 ZExt Peephole replacing:\nOld:    ");
3640     DEBUG(N->dump(CurDAG));
3641     DEBUG(dbgs() << "\nNew: ");
3642     DEBUG(Op32.getNode()->dump(CurDAG));
3643     DEBUG(dbgs() << "\n");
3644
3645     ReplaceUses(N, Op32.getNode());
3646   }
3647
3648   if (MadeChange)
3649     CurDAG->RemoveDeadNodes();
3650 }
3651
3652 void PPCDAGToDAGISel::PeepholePPC64() {
3653   // These optimizations are currently supported only for 64-bit SVR4.
3654   if (PPCSubTarget->isDarwin() || !PPCSubTarget->isPPC64())
3655     return;
3656
3657   SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
3658   ++Position;
3659
3660   while (Position != CurDAG->allnodes_begin()) {
3661     SDNode *N = --Position;
3662     // Skip dead nodes and any non-machine opcodes.
3663     if (N->use_empty() || !N->isMachineOpcode())
3664       continue;
3665
3666     unsigned FirstOp;
3667     unsigned StorageOpcode = N->getMachineOpcode();
3668
3669     switch (StorageOpcode) {
3670     default: continue;
3671
3672     case PPC::LBZ:
3673     case PPC::LBZ8:
3674     case PPC::LD:
3675     case PPC::LFD:
3676     case PPC::LFS:
3677     case PPC::LHA:
3678     case PPC::LHA8:
3679     case PPC::LHZ:
3680     case PPC::LHZ8:
3681     case PPC::LWA:
3682     case PPC::LWZ:
3683     case PPC::LWZ8:
3684       FirstOp = 0;
3685       break;
3686
3687     case PPC::STB:
3688     case PPC::STB8:
3689     case PPC::STD:
3690     case PPC::STFD:
3691     case PPC::STFS:
3692     case PPC::STH:
3693     case PPC::STH8:
3694     case PPC::STW:
3695     case PPC::STW8:
3696       FirstOp = 1;
3697       break;
3698     }
3699
3700     // If this is a load or store with a zero offset, we may be able to
3701     // fold an add-immediate into the memory operation.
3702     if (!isa<ConstantSDNode>(N->getOperand(FirstOp)) ||
3703         N->getConstantOperandVal(FirstOp) != 0)
3704       continue;
3705
3706     SDValue Base = N->getOperand(FirstOp + 1);
3707     if (!Base.isMachineOpcode())
3708       continue;
3709
3710     unsigned Flags = 0;
3711     bool ReplaceFlags = true;
3712
3713     // When the feeding operation is an add-immediate of some sort,
3714     // determine whether we need to add relocation information to the
3715     // target flags on the immediate operand when we fold it into the
3716     // load instruction.
3717     //
3718     // For something like ADDItocL, the relocation information is
3719     // inferred from the opcode; when we process it in the AsmPrinter,
3720     // we add the necessary relocation there.  A load, though, can receive
3721     // relocation from various flavors of ADDIxxx, so we need to carry
3722     // the relocation information in the target flags.
3723     switch (Base.getMachineOpcode()) {
3724     default: continue;
3725
3726     case PPC::ADDI8:
3727     case PPC::ADDI:
3728       // In some cases (such as TLS) the relocation information
3729       // is already in place on the operand, so copying the operand
3730       // is sufficient.
3731       ReplaceFlags = false;
3732       // For these cases, the immediate may not be divisible by 4, in
3733       // which case the fold is illegal for DS-form instructions.  (The
3734       // other cases provide aligned addresses and are always safe.)
3735       if ((StorageOpcode == PPC::LWA ||
3736            StorageOpcode == PPC::LD  ||
3737            StorageOpcode == PPC::STD) &&
3738           (!isa<ConstantSDNode>(Base.getOperand(1)) ||
3739            Base.getConstantOperandVal(1) % 4 != 0))
3740         continue;
3741       break;
3742     case PPC::ADDIdtprelL:
3743       Flags = PPCII::MO_DTPREL_LO;
3744       break;
3745     case PPC::ADDItlsldL:
3746       Flags = PPCII::MO_TLSLD_LO;
3747       break;
3748     case PPC::ADDItocL:
3749       Flags = PPCII::MO_TOC_LO;
3750       break;
3751     }
3752
3753     // We found an opportunity.  Reverse the operands from the add
3754     // immediate and substitute them into the load or store.  If
3755     // needed, update the target flags for the immediate operand to
3756     // reflect the necessary relocation information.
3757     DEBUG(dbgs() << "Folding add-immediate into mem-op:\nBase:    ");
3758     DEBUG(Base->dump(CurDAG));
3759     DEBUG(dbgs() << "\nN: ");
3760     DEBUG(N->dump(CurDAG));
3761     DEBUG(dbgs() << "\n");
3762
3763     SDValue ImmOpnd = Base.getOperand(1);
3764
3765     // If the relocation information isn't already present on the
3766     // immediate operand, add it now.
3767     if (ReplaceFlags) {
3768       if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(ImmOpnd)) {
3769         SDLoc dl(GA);
3770         const GlobalValue *GV = GA->getGlobal();
3771         // We can't perform this optimization for data whose alignment
3772         // is insufficient for the instruction encoding.
3773         if (GV->getAlignment() < 4 &&
3774             (StorageOpcode == PPC::LD || StorageOpcode == PPC::STD ||
3775              StorageOpcode == PPC::LWA)) {
3776           DEBUG(dbgs() << "Rejected this candidate for alignment.\n\n");
3777           continue;
3778         }
3779         ImmOpnd = CurDAG->getTargetGlobalAddress(GV, dl, MVT::i64, 0, Flags);
3780       } else if (ConstantPoolSDNode *CP =
3781                  dyn_cast<ConstantPoolSDNode>(ImmOpnd)) {
3782         const Constant *C = CP->getConstVal();
3783         ImmOpnd = CurDAG->getTargetConstantPool(C, MVT::i64,
3784                                                 CP->getAlignment(),
3785                                                 0, Flags);
3786       }
3787     }
3788
3789     if (FirstOp == 1) // Store
3790       (void)CurDAG->UpdateNodeOperands(N, N->getOperand(0), ImmOpnd,
3791                                        Base.getOperand(0), N->getOperand(3));
3792     else // Load
3793       (void)CurDAG->UpdateNodeOperands(N, ImmOpnd, Base.getOperand(0),
3794                                        N->getOperand(2));
3795
3796     // The add-immediate may now be dead, in which case remove it.
3797     if (Base.getNode()->use_empty())
3798       CurDAG->RemoveDeadNode(Base.getNode());
3799   }
3800 }
3801
3802
3803 /// createPPCISelDag - This pass converts a legalized DAG into a
3804 /// PowerPC-specific DAG, ready for instruction scheduling.
3805 ///
3806 FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
3807   return new PPCDAGToDAGISel(TM);
3808 }
3809
3810 static void initializePassOnce(PassRegistry &Registry) {
3811   const char *Name = "PowerPC DAG->DAG Pattern Instruction Selection";
3812   PassInfo *PI = new PassInfo(Name, "ppc-codegen", &SelectionDAGISel::ID,
3813                               nullptr, false, false);
3814   Registry.registerPass(*PI, true);
3815 }
3816
3817 void llvm::initializePPCDAGToDAGISelPass(PassRegistry &Registry) {
3818   CALL_ONCE_INITIALIZATION(initializePassOnce);
3819 }
3820