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