LLVM  16.0.0git
PPCISelDAGToDAG.cpp
Go to the documentation of this file.
1 //===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a pattern matching instruction selector for PowerPC,
10 // converting from a legalized dag to a PPC dag.
11 //
12 //===----------------------------------------------------------------------===//
13 
16 #include "PPC.h"
17 #include "PPCISelLowering.h"
18 #include "PPCMachineFunctionInfo.h"
19 #include "PPCSubtarget.h"
20 #include "PPCTargetMachine.h"
21 #include "llvm/ADT/APInt.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
41 #include "llvm/IR/BasicBlock.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/GlobalValue.h"
45 #include "llvm/IR/InlineAsm.h"
46 #include "llvm/IR/InstrTypes.h"
47 #include "llvm/IR/IntrinsicsPowerPC.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/Support/Casting.h"
50 #include "llvm/Support/CodeGen.h"
52 #include "llvm/Support/Compiler.h"
53 #include "llvm/Support/Debug.h"
55 #include "llvm/Support/KnownBits.h"
59 #include <algorithm>
60 #include <cassert>
61 #include <cstdint>
62 #include <iterator>
63 #include <limits>
64 #include <memory>
65 #include <new>
66 #include <tuple>
67 #include <utility>
68 
69 using namespace llvm;
70 
71 #define DEBUG_TYPE "ppc-codegen"
72 
73 STATISTIC(NumSextSetcc,
74  "Number of (sext(setcc)) nodes expanded into GPR sequence.");
75 STATISTIC(NumZextSetcc,
76  "Number of (zext(setcc)) nodes expanded into GPR sequence.");
77 STATISTIC(SignExtensionsAdded,
78  "Number of sign extensions for compare inputs added.");
79 STATISTIC(ZeroExtensionsAdded,
80  "Number of zero extensions for compare inputs added.");
81 STATISTIC(NumLogicOpsOnComparison,
82  "Number of logical ops on i1 values calculated in GPR.");
83 STATISTIC(OmittedForNonExtendUses,
84  "Number of compares not eliminated as they have non-extending uses.");
85 STATISTIC(NumP9Setb,
86  "Number of compares lowered to setb.");
87 
88 // FIXME: Remove this once the bug has been fixed!
89 cl::opt<bool> ANDIGlueBug("expose-ppc-andi-glue-bug",
90 cl::desc("expose the ANDI glue bug on PPC"), cl::Hidden);
91 
92 static cl::opt<bool>
93  UseBitPermRewriter("ppc-use-bit-perm-rewriter", cl::init(true),
94  cl::desc("use aggressive ppc isel for bit permutations"),
95  cl::Hidden);
97  "ppc-bit-perm-rewriter-stress-rotates",
98  cl::desc("stress rotate selection in aggressive ppc isel for "
99  "bit permutations"),
100  cl::Hidden);
101 
103  "ppc-use-branch-hint", cl::init(true),
104  cl::desc("Enable static hinting of branches on ppc"),
105  cl::Hidden);
106 
108  "ppc-tls-opt", cl::init(true),
109  cl::desc("Enable tls optimization peephole"),
110  cl::Hidden);
111 
115 
117  "ppc-gpr-icmps", cl::Hidden, cl::init(ICGPR_All),
118  cl::desc("Specify the types of comparisons to emit GPR-only code for."),
119  cl::values(clEnumValN(ICGPR_None, "none", "Do not modify integer comparisons."),
120  clEnumValN(ICGPR_All, "all", "All possible int comparisons in GPRs."),
121  clEnumValN(ICGPR_I32, "i32", "Only i32 comparisons in GPRs."),
122  clEnumValN(ICGPR_I64, "i64", "Only i64 comparisons in GPRs."),
123  clEnumValN(ICGPR_NonExtIn, "nonextin",
124  "Only comparisons where inputs don't need [sz]ext."),
125  clEnumValN(ICGPR_Zext, "zext", "Only comparisons with zext result."),
126  clEnumValN(ICGPR_ZextI32, "zexti32",
127  "Only i32 comparisons with zext result."),
128  clEnumValN(ICGPR_ZextI64, "zexti64",
129  "Only i64 comparisons with zext result."),
130  clEnumValN(ICGPR_Sext, "sext", "Only comparisons with sext result."),
131  clEnumValN(ICGPR_SextI32, "sexti32",
132  "Only i32 comparisons with sext result."),
133  clEnumValN(ICGPR_SextI64, "sexti64",
134  "Only i64 comparisons with sext result.")));
135 namespace {
136 
137  //===--------------------------------------------------------------------===//
138  /// PPCDAGToDAGISel - PPC specific code to select PPC machine
139  /// instructions for SelectionDAG operations.
140  ///
141  class PPCDAGToDAGISel : public SelectionDAGISel {
142  const PPCTargetMachine &TM;
143  const PPCSubtarget *Subtarget = nullptr;
144  const PPCTargetLowering *PPCLowering = nullptr;
145  unsigned GlobalBaseReg = 0;
146 
147  public:
148  explicit PPCDAGToDAGISel(PPCTargetMachine &tm, CodeGenOpt::Level OptLevel)
149  : SelectionDAGISel(tm, OptLevel), TM(tm) {}
150 
151  bool runOnMachineFunction(MachineFunction &MF) override {
152  // Make sure we re-emit a set of the global base reg if necessary
153  GlobalBaseReg = 0;
154  Subtarget = &MF.getSubtarget<PPCSubtarget>();
155  PPCLowering = Subtarget->getTargetLowering();
156  if (Subtarget->hasROPProtect()) {
157  // Create a place on the stack for the ROP Protection Hash.
158  // The ROP Protection Hash will always be 8 bytes and aligned to 8
159  // bytes.
160  MachineFrameInfo &MFI = MF.getFrameInfo();
162  const int Result = MFI.CreateStackObject(8, Align(8), false);
163  FI->setROPProtectionHashSaveIndex(Result);
164  }
166 
167  return true;
168  }
169 
170  void PreprocessISelDAG() override;
171  void PostprocessISelDAG() override;
172 
173  /// getI16Imm - Return a target constant with the specified value, of type
174  /// i16.
175  inline SDValue getI16Imm(unsigned Imm, const SDLoc &dl) {
176  return CurDAG->getTargetConstant(Imm, dl, MVT::i16);
177  }
178 
179  /// getI32Imm - Return a target constant with the specified value, of type
180  /// i32.
181  inline SDValue getI32Imm(unsigned Imm, const SDLoc &dl) {
182  return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
183  }
184 
185  /// getI64Imm - Return a target constant with the specified value, of type
186  /// i64.
187  inline SDValue getI64Imm(uint64_t Imm, const SDLoc &dl) {
188  return CurDAG->getTargetConstant(Imm, dl, MVT::i64);
189  }
190 
191  /// getSmallIPtrImm - Return a target constant of pointer type.
192  inline SDValue getSmallIPtrImm(uint64_t Imm, const SDLoc &dl) {
193  return CurDAG->getTargetConstant(
194  Imm, dl, PPCLowering->getPointerTy(CurDAG->getDataLayout()));
195  }
196 
197  /// isRotateAndMask - Returns true if Mask and Shift can be folded into a
198  /// rotate and mask opcode and mask operation.
199  static bool isRotateAndMask(SDNode *N, unsigned Mask, bool isShiftMask,
200  unsigned &SH, unsigned &MB, unsigned &ME);
201 
202  /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
203  /// base register. Return the virtual register that holds this value.
204  SDNode *getGlobalBaseReg();
205 
206  void selectFrameIndex(SDNode *SN, SDNode *N, uint64_t Offset = 0);
207 
208  // Select - Convert the specified operand from a target-independent to a
209  // target-specific node if it hasn't already been changed.
210  void Select(SDNode *N) override;
211 
212  bool tryBitfieldInsert(SDNode *N);
213  bool tryBitPermutation(SDNode *N);
214  bool tryIntCompareInGPR(SDNode *N);
215 
216  // tryTLSXFormLoad - Convert an ISD::LOAD fed by a PPCISD::ADD_TLS into
217  // an X-Form load instruction with the offset being a relocation coming from
218  // the PPCISD::ADD_TLS.
219  bool tryTLSXFormLoad(LoadSDNode *N);
220  // tryTLSXFormStore - Convert an ISD::STORE fed by a PPCISD::ADD_TLS into
221  // an X-Form store instruction with the offset being a relocation coming from
222  // the PPCISD::ADD_TLS.
223  bool tryTLSXFormStore(StoreSDNode *N);
224  /// SelectCC - Select a comparison of the specified values with the
225  /// specified condition code, returning the CR# of the expression.
227  const SDLoc &dl, SDValue Chain = SDValue());
228 
229  /// SelectAddrImmOffs - Return true if the operand is valid for a preinc
230  /// immediate field. Note that the operand at this point is already the
231  /// result of a prior SelectAddressRegImm call.
232  bool SelectAddrImmOffs(SDValue N, SDValue &Out) const {
233  if (N.getOpcode() == ISD::TargetConstant ||
234  N.getOpcode() == ISD::TargetGlobalAddress) {
235  Out = N;
236  return true;
237  }
238 
239  return false;
240  }
241 
242  /// SelectDSForm - Returns true if address N can be represented by the
243  /// addressing mode of DSForm instructions (a base register, plus a signed
244  /// 16-bit displacement that is a multiple of 4.
245  bool SelectDSForm(SDNode *Parent, SDValue N, SDValue &Disp, SDValue &Base) {
246  return PPCLowering->SelectOptimalAddrMode(Parent, N, Disp, Base, *CurDAG,
247  Align(4)) == PPC::AM_DSForm;
248  }
249 
250  /// SelectDQForm - Returns true if address N can be represented by the
251  /// addressing mode of DQForm instructions (a base register, plus a signed
252  /// 16-bit displacement that is a multiple of 16.
253  bool SelectDQForm(SDNode *Parent, SDValue N, SDValue &Disp, SDValue &Base) {
254  return PPCLowering->SelectOptimalAddrMode(Parent, N, Disp, Base, *CurDAG,
255  Align(16)) == PPC::AM_DQForm;
256  }
257 
258  /// SelectDForm - Returns true if address N can be represented by
259  /// the addressing mode of DForm instructions (a base register, plus a
260  /// signed 16-bit immediate.
261  bool SelectDForm(SDNode *Parent, SDValue N, SDValue &Disp, SDValue &Base) {
262  return PPCLowering->SelectOptimalAddrMode(Parent, N, Disp, Base, *CurDAG,
263  std::nullopt) == PPC::AM_DForm;
264  }
265 
266  /// SelectPCRelForm - Returns true if address N can be represented by
267  /// PC-Relative addressing mode.
268  bool SelectPCRelForm(SDNode *Parent, SDValue N, SDValue &Disp,
269  SDValue &Base) {
270  return PPCLowering->SelectOptimalAddrMode(Parent, N, Disp, Base, *CurDAG,
271  std::nullopt) == PPC::AM_PCRel;
272  }
273 
274  /// SelectPDForm - Returns true if address N can be represented by Prefixed
275  /// DForm addressing mode (a base register, plus a signed 34-bit immediate.
276  bool SelectPDForm(SDNode *Parent, SDValue N, SDValue &Disp, SDValue &Base) {
277  return PPCLowering->SelectOptimalAddrMode(Parent, N, Disp, Base, *CurDAG,
278  std::nullopt) ==
280  }
281 
282  /// SelectXForm - Returns true if address N can be represented by the
283  /// addressing mode of XForm instructions (an indexed [r+r] operation).
284  bool SelectXForm(SDNode *Parent, SDValue N, SDValue &Disp, SDValue &Base) {
285  return PPCLowering->SelectOptimalAddrMode(Parent, N, Disp, Base, *CurDAG,
286  std::nullopt) == PPC::AM_XForm;
287  }
288 
289  /// SelectForceXForm - Given the specified address, force it to be
290  /// represented as an indexed [r+r] operation (an XForm instruction).
291  bool SelectForceXForm(SDNode *Parent, SDValue N, SDValue &Disp,
292  SDValue &Base) {
293  return PPCLowering->SelectForceXFormMode(N, Disp, Base, *CurDAG) ==
295  }
296 
297  /// SelectAddrIdx - Given the specified address, check to see if it can be
298  /// represented as an indexed [r+r] operation.
299  /// This is for xform instructions whose associated displacement form is D.
300  /// The last parameter \p 0 means associated D form has no requirment for 16
301  /// bit signed displacement.
302  /// Returns false if it can be represented by [r+imm], which are preferred.
303  bool SelectAddrIdx(SDValue N, SDValue &Base, SDValue &Index) {
304  return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG,
305  std::nullopt);
306  }
307 
308  /// SelectAddrIdx4 - Given the specified address, check to see if it can be
309  /// represented as an indexed [r+r] operation.
310  /// This is for xform instructions whose associated displacement form is DS.
311  /// The last parameter \p 4 means associated DS form 16 bit signed
312  /// displacement must be a multiple of 4.
313  /// Returns false if it can be represented by [r+imm], which are preferred.
314  bool SelectAddrIdxX4(SDValue N, SDValue &Base, SDValue &Index) {
315  return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG,
316  Align(4));
317  }
318 
319  /// SelectAddrIdx16 - Given the specified address, check to see if it can be
320  /// represented as an indexed [r+r] operation.
321  /// This is for xform instructions whose associated displacement form is DQ.
322  /// The last parameter \p 16 means associated DQ form 16 bit signed
323  /// displacement must be a multiple of 16.
324  /// Returns false if it can be represented by [r+imm], which are preferred.
325  bool SelectAddrIdxX16(SDValue N, SDValue &Base, SDValue &Index) {
326  return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG,
327  Align(16));
328  }
329 
330  /// SelectAddrIdxOnly - Given the specified address, force it to be
331  /// represented as an indexed [r+r] operation.
332  bool SelectAddrIdxOnly(SDValue N, SDValue &Base, SDValue &Index) {
333  return PPCLowering->SelectAddressRegRegOnly(N, Base, Index, *CurDAG);
334  }
335 
336  /// SelectAddrImm - Returns true if the address N can be represented by
337  /// a base register plus a signed 16-bit displacement [r+imm].
338  /// The last parameter \p 0 means D form has no requirment for 16 bit signed
339  /// displacement.
340  bool SelectAddrImm(SDValue N, SDValue &Disp,
341  SDValue &Base) {
342  return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG,
343  std::nullopt);
344  }
345 
346  /// SelectAddrImmX4 - Returns true if the address N can be represented by
347  /// a base register plus a signed 16-bit displacement that is a multiple of
348  /// 4 (last parameter). Suitable for use by STD and friends.
349  bool SelectAddrImmX4(SDValue N, SDValue &Disp, SDValue &Base) {
350  return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, Align(4));
351  }
352 
353  /// SelectAddrImmX16 - Returns true if the address N can be represented by
354  /// a base register plus a signed 16-bit displacement that is a multiple of
355  /// 16(last parameter). Suitable for use by STXV and friends.
356  bool SelectAddrImmX16(SDValue N, SDValue &Disp, SDValue &Base) {
357  return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG,
358  Align(16));
359  }
360 
361  /// SelectAddrImmX34 - Returns true if the address N can be represented by
362  /// a base register plus a signed 34-bit displacement. Suitable for use by
363  /// PSTXVP and friends.
364  bool SelectAddrImmX34(SDValue N, SDValue &Disp, SDValue &Base) {
365  return PPCLowering->SelectAddressRegImm34(N, Disp, Base, *CurDAG);
366  }
367 
368  // Select an address into a single register.
369  bool SelectAddr(SDValue N, SDValue &Base) {
370  Base = N;
371  return true;
372  }
373 
374  bool SelectAddrPCRel(SDValue N, SDValue &Base) {
375  return PPCLowering->SelectAddressPCRel(N, Base);
376  }
377 
378  /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
379  /// inline asm expressions. It is always correct to compute the value into
380  /// a register. The case of adding a (possibly relocatable) constant to a
381  /// register can be improved, but it is wrong to substitute Reg+Reg for
382  /// Reg in an asm, because the load or store opcode would have to change.
383  bool SelectInlineAsmMemoryOperand(const SDValue &Op,
384  unsigned ConstraintID,
385  std::vector<SDValue> &OutOps) override {
386  switch(ConstraintID) {
387  default:
388  errs() << "ConstraintID: " << ConstraintID << "\n";
389  llvm_unreachable("Unexpected asm memory constraint");
396  // We need to make sure that this one operand does not end up in r0
397  // (because we might end up lowering this as 0(%op)).
398  const TargetRegisterInfo *TRI = Subtarget->getRegisterInfo();
399  const TargetRegisterClass *TRC = TRI->getPointerRegClass(*MF, /*Kind=*/1);
400  SDLoc dl(Op);
401  SDValue RC = CurDAG->getTargetConstant(TRC->getID(), dl, MVT::i32);
402  SDValue NewOp =
403  SDValue(CurDAG->getMachineNode(TargetOpcode::COPY_TO_REGCLASS,
404  dl, Op.getValueType(),
405  Op, RC), 0);
406 
407  OutOps.push_back(NewOp);
408  return false;
409  }
410  return true;
411  }
412 
413  StringRef getPassName() const override {
414  return "PowerPC DAG->DAG Pattern Instruction Selection";
415  }
416 
417 // Include the pieces autogenerated from the target description.
418 #include "PPCGenDAGISel.inc"
419 
420 private:
421  bool trySETCC(SDNode *N);
422  bool tryFoldSWTestBRCC(SDNode *N);
423  bool trySelectLoopCountIntrinsic(SDNode *N);
424  bool tryAsSingleRLDICL(SDNode *N);
425  bool tryAsSingleRLDICR(SDNode *N);
426  bool tryAsSingleRLWINM(SDNode *N);
427  bool tryAsSingleRLWINM8(SDNode *N);
428  bool tryAsSingleRLWIMI(SDNode *N);
429  bool tryAsPairOfRLDICL(SDNode *N);
430  bool tryAsSingleRLDIMI(SDNode *N);
431 
432  void PeepholePPC64();
433  void PeepholePPC64ZExt();
434  void PeepholeCROps();
435 
436  SDValue combineToCMPB(SDNode *N);
437  void foldBoolExts(SDValue &Res, SDNode *&N);
438 
439  bool AllUsersSelectZero(SDNode *N);
440  void SwapAllSelectUsers(SDNode *N);
441 
442  bool isOffsetMultipleOf(SDNode *N, unsigned Val) const;
443  void transferMemOperands(SDNode *N, SDNode *Result);
444  };
445 
446 } // end anonymous namespace
447 
448 /// getGlobalBaseReg - Output the instructions required to put the
449 /// base address to use for accessing globals into a register.
450 ///
451 SDNode *PPCDAGToDAGISel::getGlobalBaseReg() {
452  if (!GlobalBaseReg) {
453  const TargetInstrInfo &TII = *Subtarget->getInstrInfo();
454  // Insert the set of GlobalBaseReg into the first MBB of the function
455  MachineBasicBlock &FirstMBB = MF->front();
457  const Module *M = MF->getFunction().getParent();
458  DebugLoc dl;
459 
460  if (PPCLowering->getPointerTy(CurDAG->getDataLayout()) == MVT::i32) {
461  if (Subtarget->isTargetELF()) {
462  GlobalBaseReg = PPC::R30;
463  if (!Subtarget->isSecurePlt() &&
464  M->getPICLevel() == PICLevel::SmallPIC) {
465  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MoveGOTtoLR));
466  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
467  MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
468  } else {
469  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
470  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
471  Register TempReg = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
472  BuildMI(FirstMBB, MBBI, dl,
473  TII.get(PPC::UpdateGBR), GlobalBaseReg)
475  MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
476  }
477  } else {
478  GlobalBaseReg =
479  RegInfo->createVirtualRegister(&PPC::GPRC_and_GPRC_NOR0RegClass);
480  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
481  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
482  }
483  } else {
484  // We must ensure that this sequence is dominated by the prologue.
485  // FIXME: This is a bit of a big hammer since we don't get the benefits
486  // of shrink-wrapping whenever we emit this instruction. Considering
487  // this is used in any function where we emit a jump table, this may be
488  // a significant limitation. We should consider inserting this in the
489  // block where it is used and then commoning this sequence up if it
490  // appears in multiple places.
491  // Note: on ISA 3.0 cores, we can use lnia (addpcis) instead of
492  // MovePCtoLR8.
493  MF->getInfo<PPCFunctionInfo>()->setShrinkWrapDisabled(true);
494  GlobalBaseReg = RegInfo->createVirtualRegister(&PPC::G8RC_and_G8RC_NOX0RegClass);
495  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR8));
496  BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR8), GlobalBaseReg);
497  }
498  }
499  return CurDAG->getRegister(GlobalBaseReg,
500  PPCLowering->getPointerTy(CurDAG->getDataLayout()))
501  .getNode();
502 }
503 
504 // Check if a SDValue has the toc-data attribute.
505 static bool hasTocDataAttr(SDValue Val, unsigned PointerSize) {
506  GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Val);
507  if (!GA)
508  return false;
509 
510  const GlobalVariable *GV = dyn_cast_or_null<GlobalVariable>(GA->getGlobal());
511  if (!GV)
512  return false;
513 
514  if (!GV->hasAttribute("toc-data"))
515  return false;
516 
517  // TODO: These asserts should be updated as more support for the toc data
518  // transformation is added (struct support, etc.).
519 
520  assert(
521  PointerSize >= GV->getAlign().valueOrOne().value() &&
522  "GlobalVariables with an alignment requirement stricter than TOC entry "
523  "size not supported by the toc data transformation.");
524 
525  Type *GVType = GV->getValueType();
526 
527  assert(GVType->isSized() && "A GlobalVariable's size must be known to be "
528  "supported by the toc data transformation.");
529 
530  if (GVType->isVectorTy())
531  report_fatal_error("A GlobalVariable of Vector type is not currently "
532  "supported by the toc data transformation.");
533 
534  if (GVType->isArrayTy())
535  report_fatal_error("A GlobalVariable of Array type is not currently "
536  "supported by the toc data transformation.");
537 
538  if (GVType->isStructTy())
539  report_fatal_error("A GlobalVariable of Struct type is not currently "
540  "supported by the toc data transformation.");
541 
542  assert(GVType->getPrimitiveSizeInBits() <= PointerSize * 8 &&
543  "A GlobalVariable with size larger than a TOC entry is not currently "
544  "supported by the toc data transformation.");
545 
546  if (GV->hasLocalLinkage() || GV->hasPrivateLinkage())
547  report_fatal_error("A GlobalVariable with private or local linkage is not "
548  "currently supported by the toc data transformation.");
549 
550  assert(!GV->hasCommonLinkage() &&
551  "Tentative definitions cannot have the mapping class XMC_TD.");
552 
553  return true;
554 }
555 
556 /// isInt32Immediate - This method tests to see if the node is a 32-bit constant
557 /// operand. If so Imm will receive the 32-bit value.
558 static bool isInt32Immediate(SDNode *N, unsigned &Imm) {
559  if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
560  Imm = cast<ConstantSDNode>(N)->getZExtValue();
561  return true;
562  }
563  return false;
564 }
565 
566 /// isInt64Immediate - This method tests to see if the node is a 64-bit constant
567 /// operand. If so Imm will receive the 64-bit value.
569  if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i64) {
570  Imm = cast<ConstantSDNode>(N)->getZExtValue();
571  return true;
572  }
573  return false;
574 }
575 
576 // isInt32Immediate - This method tests to see if a constant operand.
577 // If so Imm will receive the 32 bit value.
578 static bool isInt32Immediate(SDValue N, unsigned &Imm) {
579  return isInt32Immediate(N.getNode(), Imm);
580 }
581 
582 /// isInt64Immediate - This method tests to see if the value is a 64-bit
583 /// constant operand. If so Imm will receive the 64-bit value.
585  return isInt64Immediate(N.getNode(), Imm);
586 }
587 
588 static unsigned getBranchHint(unsigned PCC,
589  const FunctionLoweringInfo &FuncInfo,
590  const SDValue &DestMBB) {
591  assert(isa<BasicBlockSDNode>(DestMBB));
592 
593  if (!FuncInfo.BPI) return PPC::BR_NO_HINT;
594 
595  const BasicBlock *BB = FuncInfo.MBB->getBasicBlock();
596  const Instruction *BBTerm = BB->getTerminator();
597 
598  if (BBTerm->getNumSuccessors() != 2) return PPC::BR_NO_HINT;
599 
600  const BasicBlock *TBB = BBTerm->getSuccessor(0);
601  const BasicBlock *FBB = BBTerm->getSuccessor(1);
602 
603  auto TProb = FuncInfo.BPI->getEdgeProbability(BB, TBB);
604  auto FProb = FuncInfo.BPI->getEdgeProbability(BB, FBB);
605 
606  // We only want to handle cases which are easy to predict at static time, e.g.
607  // C++ throw statement, that is very likely not taken, or calling never
608  // returned function, e.g. stdlib exit(). So we set Threshold to filter
609  // unwanted cases.
610  //
611  // Below is LLVM branch weight table, we only want to handle case 1, 2
612  //
613  // Case Taken:Nontaken Example
614  // 1. Unreachable 1048575:1 C++ throw, stdlib exit(),
615  // 2. Invoke-terminating 1:1048575
616  // 3. Coldblock 4:64 __builtin_expect
617  // 4. Loop Branch 124:4 For loop
618  // 5. PH/ZH/FPH 20:12
619  const uint32_t Threshold = 10000;
620 
621  if (std::max(TProb, FProb) / Threshold < std::min(TProb, FProb))
622  return PPC::BR_NO_HINT;
623 
624  LLVM_DEBUG(dbgs() << "Use branch hint for '" << FuncInfo.Fn->getName()
625  << "::" << BB->getName() << "'\n"
626  << " -> " << TBB->getName() << ": " << TProb << "\n"
627  << " -> " << FBB->getName() << ": " << FProb << "\n");
628 
629  const BasicBlockSDNode *BBDN = cast<BasicBlockSDNode>(DestMBB);
630 
631  // If Dest BasicBlock is False-BasicBlock (FBB), swap branch probabilities,
632  // because we want 'TProb' stands for 'branch probability' to Dest BasicBlock
633  if (BBDN->getBasicBlock()->getBasicBlock() != TBB)
634  std::swap(TProb, FProb);
635 
636  return (TProb > FProb) ? PPC::BR_TAKEN_HINT : PPC::BR_NONTAKEN_HINT;
637 }
638 
639 // isOpcWithIntImmediate - This method tests to see if the node is a specific
640 // opcode and that it has a immediate integer right operand.
641 // If so Imm will receive the 32 bit value.
642 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
643  return N->getOpcode() == Opc
644  && isInt32Immediate(N->getOperand(1).getNode(), Imm);
645 }
646 
647 void PPCDAGToDAGISel::selectFrameIndex(SDNode *SN, SDNode *N, uint64_t Offset) {
648  SDLoc dl(SN);
649  int FI = cast<FrameIndexSDNode>(N)->getIndex();
650  SDValue TFI = CurDAG->getTargetFrameIndex(FI, N->getValueType(0));
651  unsigned Opc = N->getValueType(0) == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
652  if (SN->hasOneUse())
653  CurDAG->SelectNodeTo(SN, Opc, N->getValueType(0), TFI,
654  getSmallIPtrImm(Offset, dl));
655  else
656  ReplaceNode(SN, CurDAG->getMachineNode(Opc, dl, N->getValueType(0), TFI,
657  getSmallIPtrImm(Offset, dl)));
658 }
659 
660 bool PPCDAGToDAGISel::isRotateAndMask(SDNode *N, unsigned Mask,
661  bool isShiftMask, unsigned &SH,
662  unsigned &MB, unsigned &ME) {
663  // Don't even go down this path for i64, since different logic will be
664  // necessary for rldicl/rldicr/rldimi.
665  if (N->getValueType(0) != MVT::i32)
666  return false;
667 
668  unsigned Shift = 32;
669  unsigned Indeterminant = ~0; // bit mask marking indeterminant results
670  unsigned Opcode = N->getOpcode();
671  if (N->getNumOperands() != 2 ||
672  !isInt32Immediate(N->getOperand(1).getNode(), Shift) || (Shift > 31))
673  return false;
674 
675  if (Opcode == ISD::SHL) {
676  // apply shift left to mask if it comes first
677  if (isShiftMask) Mask = Mask << Shift;
678  // determine which bits are made indeterminant by shift
679  Indeterminant = ~(0xFFFFFFFFu << Shift);
680  } else if (Opcode == ISD::SRL) {
681  // apply shift right to mask if it comes first
682  if (isShiftMask) Mask = Mask >> Shift;
683  // determine which bits are made indeterminant by shift
684  Indeterminant = ~(0xFFFFFFFFu >> Shift);
685  // adjust for the left rotate
686  Shift = 32 - Shift;
687  } else if (Opcode == ISD::ROTL) {
688  Indeterminant = 0;
689  } else {
690  return false;
691  }
692 
693  // if the mask doesn't intersect any Indeterminant bits
694  if (Mask && !(Mask & Indeterminant)) {
695  SH = Shift & 31;
696  // make sure the mask is still a mask (wrap arounds may not be)
697  return isRunOfOnes(Mask, MB, ME);
698  }
699  return false;
700 }
701 
702 bool PPCDAGToDAGISel::tryTLSXFormStore(StoreSDNode *ST) {
703  SDValue Base = ST->getBasePtr();
704  if (Base.getOpcode() != PPCISD::ADD_TLS)
705  return false;
706  SDValue Offset = ST->getOffset();
707  if (!Offset.isUndef())
708  return false;
709  if (Base.getOperand(1).getOpcode() == PPCISD::TLS_LOCAL_EXEC_MAT_ADDR)
710  return false;
711 
712  SDLoc dl(ST);
713  EVT MemVT = ST->getMemoryVT();
714  EVT RegVT = ST->getValue().getValueType();
715 
716  unsigned Opcode;
717  switch (MemVT.getSimpleVT().SimpleTy) {
718  default:
719  return false;
720  case MVT::i8: {
721  Opcode = (RegVT == MVT::i32) ? PPC::STBXTLS_32 : PPC::STBXTLS;
722  break;
723  }
724  case MVT::i16: {
725  Opcode = (RegVT == MVT::i32) ? PPC::STHXTLS_32 : PPC::STHXTLS;
726  break;
727  }
728  case MVT::i32: {
729  Opcode = (RegVT == MVT::i32) ? PPC::STWXTLS_32 : PPC::STWXTLS;
730  break;
731  }
732  case MVT::i64: {
733  Opcode = PPC::STDXTLS;
734  break;
735  }
736  }
737  SDValue Chain = ST->getChain();
738  SDVTList VTs = ST->getVTList();
739  SDValue Ops[] = {ST->getValue(), Base.getOperand(0), Base.getOperand(1),
740  Chain};
741  SDNode *MN = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
742  transferMemOperands(ST, MN);
743  ReplaceNode(ST, MN);
744  return true;
745 }
746 
747 bool PPCDAGToDAGISel::tryTLSXFormLoad(LoadSDNode *LD) {
748  SDValue Base = LD->getBasePtr();
749  if (Base.getOpcode() != PPCISD::ADD_TLS)
750  return false;
751  SDValue Offset = LD->getOffset();
752  if (!Offset.isUndef())
753  return false;
754  if (Base.getOperand(1).getOpcode() == PPCISD::TLS_LOCAL_EXEC_MAT_ADDR)
755  return false;
756 
757  SDLoc dl(LD);
758  EVT MemVT = LD->getMemoryVT();
759  EVT RegVT = LD->getValueType(0);
760  unsigned Opcode;
761  switch (MemVT.getSimpleVT().SimpleTy) {
762  default:
763  return false;
764  case MVT::i8: {
765  Opcode = (RegVT == MVT::i32) ? PPC::LBZXTLS_32 : PPC::LBZXTLS;
766  break;
767  }
768  case MVT::i16: {
769  Opcode = (RegVT == MVT::i32) ? PPC::LHZXTLS_32 : PPC::LHZXTLS;
770  break;
771  }
772  case MVT::i32: {
773  Opcode = (RegVT == MVT::i32) ? PPC::LWZXTLS_32 : PPC::LWZXTLS;
774  break;
775  }
776  case MVT::i64: {
777  Opcode = PPC::LDXTLS;
778  break;
779  }
780  }
781  SDValue Chain = LD->getChain();
782  SDVTList VTs = LD->getVTList();
783  SDValue Ops[] = {Base.getOperand(0), Base.getOperand(1), Chain};
784  SDNode *MN = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
785  transferMemOperands(LD, MN);
786  ReplaceNode(LD, MN);
787  return true;
788 }
789 
790 /// Turn an or of two masked values into the rotate left word immediate then
791 /// mask insert (rlwimi) instruction.
792 bool PPCDAGToDAGISel::tryBitfieldInsert(SDNode *N) {
793  SDValue Op0 = N->getOperand(0);
794  SDValue Op1 = N->getOperand(1);
795  SDLoc dl(N);
796 
797  KnownBits LKnown = CurDAG->computeKnownBits(Op0);
798  KnownBits RKnown = CurDAG->computeKnownBits(Op1);
799 
800  unsigned TargetMask = LKnown.Zero.getZExtValue();
801  unsigned InsertMask = RKnown.Zero.getZExtValue();
802 
803  if ((TargetMask | InsertMask) == 0xFFFFFFFF) {
804  unsigned Op0Opc = Op0.getOpcode();
805  unsigned Op1Opc = Op1.getOpcode();
806  unsigned Value, SH = 0;
807  TargetMask = ~TargetMask;
808  InsertMask = ~InsertMask;
809 
810  // If the LHS has a foldable shift and the RHS does not, then swap it to the
811  // RHS so that we can fold the shift into the insert.
812  if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
813  if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
814  Op0.getOperand(0).getOpcode() == ISD::SRL) {
815  if (Op1.getOperand(0).getOpcode() != ISD::SHL &&
816  Op1.getOperand(0).getOpcode() != ISD::SRL) {
817  std::swap(Op0, Op1);
818  std::swap(Op0Opc, Op1Opc);
819  std::swap(TargetMask, InsertMask);
820  }
821  }
822  } else if (Op0Opc == ISD::SHL || Op0Opc == ISD::SRL) {
823  if (Op1Opc == ISD::AND && Op1.getOperand(0).getOpcode() != ISD::SHL &&
824  Op1.getOperand(0).getOpcode() != ISD::SRL) {
825  std::swap(Op0, Op1);
826  std::swap(Op0Opc, Op1Opc);
827  std::swap(TargetMask, InsertMask);
828  }
829  }
830 
831  unsigned MB, ME;
832  if (isRunOfOnes(InsertMask, MB, ME)) {
833  if ((Op1Opc == ISD::SHL || Op1Opc == ISD::SRL) &&
834  isInt32Immediate(Op1.getOperand(1), Value)) {
835  Op1 = Op1.getOperand(0);
836  SH = (Op1Opc == ISD::SHL) ? Value : 32 - Value;
837  }
838  if (Op1Opc == ISD::AND) {
839  // The AND mask might not be a constant, and we need to make sure that
840  // if we're going to fold the masking with the insert, all bits not
841  // know to be zero in the mask are known to be one.
842  KnownBits MKnown = CurDAG->computeKnownBits(Op1.getOperand(1));
843  bool CanFoldMask = InsertMask == MKnown.One.getZExtValue();
844 
845  unsigned SHOpc = Op1.getOperand(0).getOpcode();
846  if ((SHOpc == ISD::SHL || SHOpc == ISD::SRL) && CanFoldMask &&
848  // Note that Value must be in range here (less than 32) because
849  // otherwise there would not be any bits set in InsertMask.
850  Op1 = Op1.getOperand(0).getOperand(0);
851  SH = (SHOpc == ISD::SHL) ? Value : 32 - Value;
852  }
853  }
854 
855  SH &= 31;
856  SDValue Ops[] = { Op0, Op1, getI32Imm(SH, dl), getI32Imm(MB, dl),
857  getI32Imm(ME, dl) };
858  ReplaceNode(N, CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops));
859  return true;
860  }
861  }
862  return false;
863 }
864 
865 static unsigned allUsesTruncate(SelectionDAG *CurDAG, SDNode *N) {
866  unsigned MaxTruncation = 0;
867  // Cannot use range-based for loop here as we need the actual use (i.e. we
868  // need the operand number corresponding to the use). A range-based for
869  // will unbox the use and provide an SDNode*.
870  for (SDNode::use_iterator Use = N->use_begin(), UseEnd = N->use_end();
871  Use != UseEnd; ++Use) {
872  unsigned Opc =
873  Use->isMachineOpcode() ? Use->getMachineOpcode() : Use->getOpcode();
874  switch (Opc) {
875  default: return 0;
876  case ISD::TRUNCATE:
877  if (Use->isMachineOpcode())
878  return 0;
879  MaxTruncation =
880  std::max(MaxTruncation, (unsigned)Use->getValueType(0).getSizeInBits());
881  continue;
882  case ISD::STORE: {
883  if (Use->isMachineOpcode())
884  return 0;
885  StoreSDNode *STN = cast<StoreSDNode>(*Use);
886  unsigned MemVTSize = STN->getMemoryVT().getSizeInBits();
887  if (MemVTSize == 64 || Use.getOperandNo() != 0)
888  return 0;
889  MaxTruncation = std::max(MaxTruncation, MemVTSize);
890  continue;
891  }
892  case PPC::STW8:
893  case PPC::STWX8:
894  case PPC::STWU8:
895  case PPC::STWUX8:
896  if (Use.getOperandNo() != 0)
897  return 0;
898  MaxTruncation = std::max(MaxTruncation, 32u);
899  continue;
900  case PPC::STH8:
901  case PPC::STHX8:
902  case PPC::STHU8:
903  case PPC::STHUX8:
904  if (Use.getOperandNo() != 0)
905  return 0;
906  MaxTruncation = std::max(MaxTruncation, 16u);
907  continue;
908  case PPC::STB8:
909  case PPC::STBX8:
910  case PPC::STBU8:
911  case PPC::STBUX8:
912  if (Use.getOperandNo() != 0)
913  return 0;
914  MaxTruncation = std::max(MaxTruncation, 8u);
915  continue;
916  }
917  }
918  return MaxTruncation;
919 }
920 
921 // For any 32 < Num < 64, check if the Imm contains at least Num consecutive
922 // zeros and return the number of bits by the left of these consecutive zeros.
923 static int findContiguousZerosAtLeast(uint64_t Imm, unsigned Num) {
924  unsigned HiTZ = countTrailingZeros<uint32_t>(Hi_32(Imm));
925  unsigned LoLZ = countLeadingZeros<uint32_t>(Lo_32(Imm));
926  if ((HiTZ + LoLZ) >= Num)
927  return (32 + HiTZ);
928  return 0;
929 }
930 
931 // Direct materialization of 64-bit constants by enumerated patterns.
932 static SDNode *selectI64ImmDirect(SelectionDAG *CurDAG, const SDLoc &dl,
933  uint64_t Imm, unsigned &InstCnt) {
934  unsigned TZ = countTrailingZeros<uint64_t>(Imm);
935  unsigned LZ = countLeadingZeros<uint64_t>(Imm);
936  unsigned TO = countTrailingOnes<uint64_t>(Imm);
937  unsigned LO = countLeadingOnes<uint64_t>(Imm);
938  unsigned Hi32 = Hi_32(Imm);
939  unsigned Lo32 = Lo_32(Imm);
940  SDNode *Result = nullptr;
941  unsigned Shift = 0;
942 
943  auto getI32Imm = [CurDAG, dl](unsigned Imm) {
944  return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
945  };
946 
947  // Following patterns use 1 instructions to materialize the Imm.
948  InstCnt = 1;
949  // 1-1) Patterns : {zeros}{15-bit valve}
950  // {ones}{15-bit valve}
951  if (isInt<16>(Imm)) {
952  SDValue SDImm = CurDAG->getTargetConstant(Imm, dl, MVT::i64);
953  return CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
954  }
955  // 1-2) Patterns : {zeros}{15-bit valve}{16 zeros}
956  // {ones}{15-bit valve}{16 zeros}
957  if (TZ > 15 && (LZ > 32 || LO > 32))
958  return CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64,
959  getI32Imm((Imm >> 16) & 0xffff));
960 
961  // Following patterns use 2 instructions to materialize the Imm.
962  InstCnt = 2;
963  assert(LZ < 64 && "Unexpected leading zeros here.");
964  // Count of ones follwing the leading zeros.
965  unsigned FO = countLeadingOnes<uint64_t>(Imm << LZ);
966  // 2-1) Patterns : {zeros}{31-bit value}
967  // {ones}{31-bit value}
968  if (isInt<32>(Imm)) {
969  uint64_t ImmHi16 = (Imm >> 16) & 0xffff;
970  unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
971  Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
972  return CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
973  getI32Imm(Imm & 0xffff));
974  }
975  // 2-2) Patterns : {zeros}{ones}{15-bit value}{zeros}
976  // {zeros}{15-bit value}{zeros}
977  // {zeros}{ones}{15-bit value}
978  // {ones}{15-bit value}{zeros}
979  // We can take advantage of LI's sign-extension semantics to generate leading
980  // ones, and then use RLDIC to mask off the ones in both sides after rotation.
981  if ((LZ + FO + TZ) > 48) {
982  Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
983  getI32Imm((Imm >> TZ) & 0xffff));
984  return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
985  getI32Imm(TZ), getI32Imm(LZ));
986  }
987  // 2-3) Pattern : {zeros}{15-bit value}{ones}
988  // Shift right the Imm by (48 - LZ) bits to construct a negtive 16 bits value,
989  // therefore we can take advantage of LI's sign-extension semantics, and then
990  // mask them off after rotation.
991  //
992  // +--LZ--||-15-bit-||--TO--+ +-------------|--16-bit--+
993  // |00000001bbbbbbbbb1111111| -> |00000000000001bbbbbbbbb1|
994  // +------------------------+ +------------------------+
995  // 63 0 63 0
996  // Imm (Imm >> (48 - LZ) & 0xffff)
997  // +----sext-----|--16-bit--+ +clear-|-----------------+
998  // |11111111111111bbbbbbbbb1| -> |00000001bbbbbbbbb1111111|
999  // +------------------------+ +------------------------+
1000  // 63 0 63 0
1001  // LI8: sext many leading zeros RLDICL: rotate left (48 - LZ), clear left LZ
1002  if ((LZ + TO) > 48) {
1003  // Since the immediates with (LZ > 32) have been handled by previous
1004  // patterns, here we have (LZ <= 32) to make sure we will not shift right
1005  // the Imm by a negative value.
1006  assert(LZ <= 32 && "Unexpected shift value.");
1007  Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
1008  getI32Imm((Imm >> (48 - LZ) & 0xffff)));
1009  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1010  getI32Imm(48 - LZ), getI32Imm(LZ));
1011  }
1012  // 2-4) Patterns : {zeros}{ones}{15-bit value}{ones}
1013  // {ones}{15-bit value}{ones}
1014  // We can take advantage of LI's sign-extension semantics to generate leading
1015  // ones, and then use RLDICL to mask off the ones in left sides (if required)
1016  // after rotation.
1017  //
1018  // +-LZ-FO||-15-bit-||--TO--+ +-------------|--16-bit--+
1019  // |00011110bbbbbbbbb1111111| -> |000000000011110bbbbbbbbb|
1020  // +------------------------+ +------------------------+
1021  // 63 0 63 0
1022  // Imm (Imm >> TO) & 0xffff
1023  // +----sext-----|--16-bit--+ +LZ|---------------------+
1024  // |111111111111110bbbbbbbbb| -> |00011110bbbbbbbbb1111111|
1025  // +------------------------+ +------------------------+
1026  // 63 0 63 0
1027  // LI8: sext many leading zeros RLDICL: rotate left TO, clear left LZ
1028  if ((LZ + FO + TO) > 48) {
1029  Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
1030  getI32Imm((Imm >> TO) & 0xffff));
1031  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1032  getI32Imm(TO), getI32Imm(LZ));
1033  }
1034  // 2-5) Pattern : {32 zeros}{****}{0}{15-bit value}
1035  // If Hi32 is zero and the Lo16(in Lo32) can be presented as a positive 16 bit
1036  // value, we can use LI for Lo16 without generating leading ones then add the
1037  // Hi16(in Lo32).
1038  if (LZ == 32 && ((Lo32 & 0x8000) == 0)) {
1039  Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
1040  getI32Imm(Lo32 & 0xffff));
1041  return CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64, SDValue(Result, 0),
1042  getI32Imm(Lo32 >> 16));
1043  }
1044  // 2-6) Patterns : {******}{49 zeros}{******}
1045  // {******}{49 ones}{******}
1046  // If the Imm contains 49 consecutive zeros/ones, it means that a total of 15
1047  // bits remain on both sides. Rotate right the Imm to construct an int<16>
1048  // value, use LI for int<16> value and then use RLDICL without mask to rotate
1049  // it back.
1050  //
1051  // 1) findContiguousZerosAtLeast(Imm, 49)
1052  // +------|--zeros-|------+ +---ones--||---15 bit--+
1053  // |bbbbbb0000000000aaaaaa| -> |0000000000aaaaaabbbbbb|
1054  // +----------------------+ +----------------------+
1055  // 63 0 63 0
1056  //
1057  // 2) findContiguousZerosAtLeast(~Imm, 49)
1058  // +------|--ones--|------+ +---ones--||---15 bit--+
1059  // |bbbbbb1111111111aaaaaa| -> |1111111111aaaaaabbbbbb|
1060  // +----------------------+ +----------------------+
1061  // 63 0 63 0
1062  if ((Shift = findContiguousZerosAtLeast(Imm, 49)) ||
1063  (Shift = findContiguousZerosAtLeast(~Imm, 49))) {
1064  uint64_t RotImm = APInt(64, Imm).rotr(Shift).getZExtValue();
1065  Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
1066  getI32Imm(RotImm & 0xffff));
1067  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1068  getI32Imm(Shift), getI32Imm(0));
1069  }
1070 
1071  // Following patterns use 3 instructions to materialize the Imm.
1072  InstCnt = 3;
1073  // 3-1) Patterns : {zeros}{ones}{31-bit value}{zeros}
1074  // {zeros}{31-bit value}{zeros}
1075  // {zeros}{ones}{31-bit value}
1076  // {ones}{31-bit value}{zeros}
1077  // We can take advantage of LIS's sign-extension semantics to generate leading
1078  // ones, add the remaining bits with ORI, and then use RLDIC to mask off the
1079  // ones in both sides after rotation.
1080  if ((LZ + FO + TZ) > 32) {
1081  uint64_t ImmHi16 = (Imm >> (TZ + 16)) & 0xffff;
1082  unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
1083  Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
1084  Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
1085  getI32Imm((Imm >> TZ) & 0xffff));
1086  return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
1087  getI32Imm(TZ), getI32Imm(LZ));
1088  }
1089  // 3-2) Pattern : {zeros}{31-bit value}{ones}
1090  // Shift right the Imm by (32 - LZ) bits to construct a negtive 32 bits value,
1091  // therefore we can take advantage of LIS's sign-extension semantics, add
1092  // the remaining bits with ORI, and then mask them off after rotation.
1093  // This is similar to Pattern 2-3, please refer to the diagram there.
1094  if ((LZ + TO) > 32) {
1095  // Since the immediates with (LZ > 32) have been handled by previous
1096  // patterns, here we have (LZ <= 32) to make sure we will not shift right
1097  // the Imm by a negative value.
1098  assert(LZ <= 32 && "Unexpected shift value.");
1099  Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64,
1100  getI32Imm((Imm >> (48 - LZ)) & 0xffff));
1101  Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
1102  getI32Imm((Imm >> (32 - LZ)) & 0xffff));
1103  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1104  getI32Imm(32 - LZ), getI32Imm(LZ));
1105  }
1106  // 3-3) Patterns : {zeros}{ones}{31-bit value}{ones}
1107  // {ones}{31-bit value}{ones}
1108  // We can take advantage of LIS's sign-extension semantics to generate leading
1109  // ones, add the remaining bits with ORI, and then use RLDICL to mask off the
1110  // ones in left sides (if required) after rotation.
1111  // This is similar to Pattern 2-4, please refer to the diagram there.
1112  if ((LZ + FO + TO) > 32) {
1113  Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64,
1114  getI32Imm((Imm >> (TO + 16)) & 0xffff));
1115  Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
1116  getI32Imm((Imm >> TO) & 0xffff));
1117  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1118  getI32Imm(TO), getI32Imm(LZ));
1119  }
1120  // 3-4) Patterns : High word == Low word
1121  if (Hi32 == Lo32) {
1122  // Handle the first 32 bits.
1123  uint64_t ImmHi16 = (Lo32 >> 16) & 0xffff;
1124  unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
1125  Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
1126  Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
1127  getI32Imm(Lo32 & 0xffff));
1128  // Use rldimi to insert the Low word into High word.
1129  SDValue Ops[] = {SDValue(Result, 0), SDValue(Result, 0), getI32Imm(32),
1130  getI32Imm(0)};
1131  return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
1132  }
1133  // 3-5) Patterns : {******}{33 zeros}{******}
1134  // {******}{33 ones}{******}
1135  // If the Imm contains 33 consecutive zeros/ones, it means that a total of 31
1136  // bits remain on both sides. Rotate right the Imm to construct an int<32>
1137  // value, use LIS + ORI for int<32> value and then use RLDICL without mask to
1138  // rotate it back.
1139  // This is similar to Pattern 2-6, please refer to the diagram there.
1140  if ((Shift = findContiguousZerosAtLeast(Imm, 33)) ||
1141  (Shift = findContiguousZerosAtLeast(~Imm, 33))) {
1142  uint64_t RotImm = APInt(64, Imm).rotr(Shift).getZExtValue();
1143  uint64_t ImmHi16 = (RotImm >> 16) & 0xffff;
1144  unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
1145  Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
1146  Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
1147  getI32Imm(RotImm & 0xffff));
1148  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1149  getI32Imm(Shift), getI32Imm(0));
1150  }
1151 
1152  InstCnt = 0;
1153  return nullptr;
1154 }
1155 
1156 // Try to select instructions to generate a 64 bit immediate using prefix as
1157 // well as non prefix instructions. The function will return the SDNode
1158 // to materialize that constant or it will return nullptr if it does not
1159 // find one. The variable InstCnt is set to the number of instructions that
1160 // were selected.
1162  uint64_t Imm, unsigned &InstCnt) {
1163  unsigned TZ = countTrailingZeros<uint64_t>(Imm);
1164  unsigned LZ = countLeadingZeros<uint64_t>(Imm);
1165  unsigned TO = countTrailingOnes<uint64_t>(Imm);
1166  unsigned FO = countLeadingOnes<uint64_t>(LZ == 64 ? 0 : (Imm << LZ));
1167  unsigned Hi32 = Hi_32(Imm);
1168  unsigned Lo32 = Lo_32(Imm);
1169 
1170  auto getI32Imm = [CurDAG, dl](unsigned Imm) {
1171  return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
1172  };
1173 
1174  auto getI64Imm = [CurDAG, dl](uint64_t Imm) {
1175  return CurDAG->getTargetConstant(Imm, dl, MVT::i64);
1176  };
1177 
1178  // Following patterns use 1 instruction to materialize Imm.
1179  InstCnt = 1;
1180 
1181  // The pli instruction can materialize up to 34 bits directly.
1182  // If a constant fits within 34-bits, emit the pli instruction here directly.
1183  if (isInt<34>(Imm))
1184  return CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
1185  CurDAG->getTargetConstant(Imm, dl, MVT::i64));
1186 
1187  // Require at least two instructions.
1188  InstCnt = 2;
1189  SDNode *Result = nullptr;
1190  // Patterns : {zeros}{ones}{33-bit value}{zeros}
1191  // {zeros}{33-bit value}{zeros}
1192  // {zeros}{ones}{33-bit value}
1193  // {ones}{33-bit value}{zeros}
1194  // We can take advantage of PLI's sign-extension semantics to generate leading
1195  // ones, and then use RLDIC to mask off the ones on both sides after rotation.
1196  if ((LZ + FO + TZ) > 30) {
1197  APInt SignedInt34 = APInt(34, (Imm >> TZ) & 0x3ffffffff);
1198  APInt Extended = SignedInt34.sext(64);
1199  Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
1200  getI64Imm(*Extended.getRawData()));
1201  return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
1202  getI32Imm(TZ), getI32Imm(LZ));
1203  }
1204  // Pattern : {zeros}{33-bit value}{ones}
1205  // Shift right the Imm by (30 - LZ) bits to construct a negative 34 bit value,
1206  // therefore we can take advantage of PLI's sign-extension semantics, and then
1207  // mask them off after rotation.
1208  //
1209  // +--LZ--||-33-bit-||--TO--+ +-------------|--34-bit--+
1210  // |00000001bbbbbbbbb1111111| -> |00000000000001bbbbbbbbb1|
1211  // +------------------------+ +------------------------+
1212  // 63 0 63 0
1213  //
1214  // +----sext-----|--34-bit--+ +clear-|-----------------+
1215  // |11111111111111bbbbbbbbb1| -> |00000001bbbbbbbbb1111111|
1216  // +------------------------+ +------------------------+
1217  // 63 0 63 0
1218  if ((LZ + TO) > 30) {
1219  APInt SignedInt34 = APInt(34, (Imm >> (30 - LZ)) & 0x3ffffffff);
1220  APInt Extended = SignedInt34.sext(64);
1221  Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
1222  getI64Imm(*Extended.getRawData()));
1223  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1224  getI32Imm(30 - LZ), getI32Imm(LZ));
1225  }
1226  // Patterns : {zeros}{ones}{33-bit value}{ones}
1227  // {ones}{33-bit value}{ones}
1228  // Similar to LI we can take advantage of PLI's sign-extension semantics to
1229  // generate leading ones, and then use RLDICL to mask off the ones in left
1230  // sides (if required) after rotation.
1231  if ((LZ + FO + TO) > 30) {
1232  APInt SignedInt34 = APInt(34, (Imm >> TO) & 0x3ffffffff);
1233  APInt Extended = SignedInt34.sext(64);
1234  Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
1235  getI64Imm(*Extended.getRawData()));
1236  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
1237  getI32Imm(TO), getI32Imm(LZ));
1238  }
1239  // Patterns : {******}{31 zeros}{******}
1240  // : {******}{31 ones}{******}
1241  // If Imm contains 31 consecutive zeros/ones then the remaining bit count
1242  // is 33. Rotate right the Imm to construct a int<33> value, we can use PLI
1243  // for the int<33> value and then use RLDICL without a mask to rotate it back.
1244  //
1245  // +------|--ones--|------+ +---ones--||---33 bit--+
1246  // |bbbbbb1111111111aaaaaa| -> |1111111111aaaaaabbbbbb|
1247  // +----------------------+ +----------------------+
1248  // 63 0 63 0
1249  for (unsigned Shift = 0; Shift < 63; ++Shift) {
1250  uint64_t RotImm = APInt(64, Imm).rotr(Shift).getZExtValue();
1251  if (isInt<34>(RotImm)) {
1252  Result =
1253  CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(RotImm));
1254  return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
1255  SDValue(Result, 0), getI32Imm(Shift),
1256  getI32Imm(0));
1257  }
1258  }
1259 
1260  // Patterns : High word == Low word
1261  // This is basically a splat of a 32 bit immediate.
1262  if (Hi32 == Lo32) {
1263  Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Hi32));
1264  SDValue Ops[] = {SDValue(Result, 0), SDValue(Result, 0), getI32Imm(32),
1265  getI32Imm(0)};
1266  return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
1267  }
1268 
1269  InstCnt = 3;
1270  // Catch-all
1271  // This pattern can form any 64 bit immediate in 3 instructions.
1272  SDNode *ResultHi =
1273  CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Hi32));
1274  SDNode *ResultLo =
1275  CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Lo32));
1276  SDValue Ops[] = {SDValue(ResultLo, 0), SDValue(ResultHi, 0), getI32Imm(32),
1277  getI32Imm(0)};
1278  return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
1279 }
1280 
1281 static SDNode *selectI64Imm(SelectionDAG *CurDAG, const SDLoc &dl, uint64_t Imm,
1282  unsigned *InstCnt = nullptr) {
1283  unsigned InstCntDirect = 0;
1284  // No more than 3 instructions is used if we can select the i64 immediate
1285  // directly.
1286  SDNode *Result = selectI64ImmDirect(CurDAG, dl, Imm, InstCntDirect);
1287 
1288  const PPCSubtarget &Subtarget =
1290 
1291  // If we have prefixed instructions and there is a chance we can
1292  // materialize the constant with fewer prefixed instructions than
1293  // non-prefixed, try that.
1294  if (Subtarget.hasPrefixInstrs() && InstCntDirect != 1) {
1295  unsigned InstCntDirectP = 0;
1296  SDNode *ResultP = selectI64ImmDirectPrefix(CurDAG, dl, Imm, InstCntDirectP);
1297  // Use the prefix case in either of two cases:
1298  // 1) We have no result from the non-prefix case to use.
1299  // 2) The non-prefix case uses more instructions than the prefix case.
1300  // If the prefix and non-prefix cases use the same number of instructions
1301  // we will prefer the non-prefix case.
1302  if (ResultP && (!Result || InstCntDirectP < InstCntDirect)) {
1303  if (InstCnt)
1304  *InstCnt = InstCntDirectP;
1305  return ResultP;
1306  }
1307  }
1308 
1309  if (Result) {
1310  if (InstCnt)
1311  *InstCnt = InstCntDirect;
1312  return Result;
1313  }
1314  auto getI32Imm = [CurDAG, dl](unsigned Imm) {
1315  return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
1316  };
1317  // Handle the upper 32 bit value.
1318  Result =
1319  selectI64ImmDirect(CurDAG, dl, Imm & 0xffffffff00000000, InstCntDirect);
1320  // Add in the last bits as required.
1321  if (uint32_t Hi16 = (Lo_32(Imm) >> 16) & 0xffff) {
1322  Result = CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64,
1323  SDValue(Result, 0), getI32Imm(Hi16));
1324  ++InstCntDirect;
1325  }
1326  if (uint32_t Lo16 = Lo_32(Imm) & 0xffff) {
1327  Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
1328  getI32Imm(Lo16));
1329  ++InstCntDirect;
1330  }
1331  if (InstCnt)
1332  *InstCnt = InstCntDirect;
1333  return Result;
1334 }
1335 
1336 // Select a 64-bit constant.
1338  SDLoc dl(N);
1339 
1340  // Get 64 bit value.
1341  int64_t Imm = cast<ConstantSDNode>(N)->getZExtValue();
1342  if (unsigned MinSize = allUsesTruncate(CurDAG, N)) {
1343  uint64_t SextImm = SignExtend64(Imm, MinSize);
1344  SDValue SDImm = CurDAG->getTargetConstant(SextImm, dl, MVT::i64);
1345  if (isInt<16>(SextImm))
1346  return CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
1347  }
1348  return selectI64Imm(CurDAG, dl, Imm);
1349 }
1350 
1351 namespace {
1352 
1353 class BitPermutationSelector {
1354  struct ValueBit {
1355  SDValue V;
1356 
1357  // The bit number in the value, using a convention where bit 0 is the
1358  // lowest-order bit.
1359  unsigned Idx;
1360 
1361  // ConstZero means a bit we need to mask off.
1362  // Variable is a bit comes from an input variable.
1363  // VariableKnownToBeZero is also a bit comes from an input variable,
1364  // but it is known to be already zero. So we do not need to mask them.
1365  enum Kind {
1366  ConstZero,
1367  Variable,
1368  VariableKnownToBeZero
1369  } K;
1370 
1371  ValueBit(SDValue V, unsigned I, Kind K = Variable)
1372  : V(V), Idx(I), K(K) {}
1373  ValueBit(Kind K = Variable) : Idx(UINT32_MAX), K(K) {}
1374 
1375  bool isZero() const {
1376  return K == ConstZero || K == VariableKnownToBeZero;
1377  }
1378 
1379  bool hasValue() const {
1380  return K == Variable || K == VariableKnownToBeZero;
1381  }
1382 
1383  SDValue getValue() const {
1384  assert(hasValue() && "Cannot get the value of a constant bit");
1385  return V;
1386  }
1387 
1388  unsigned getValueBitIndex() const {
1389  assert(hasValue() && "Cannot get the value bit index of a constant bit");
1390  return Idx;
1391  }
1392  };
1393 
1394  // A bit group has the same underlying value and the same rotate factor.
1395  struct BitGroup {
1396  SDValue V;
1397  unsigned RLAmt;
1398  unsigned StartIdx, EndIdx;
1399 
1400  // This rotation amount assumes that the lower 32 bits of the quantity are
1401  // replicated in the high 32 bits by the rotation operator (which is done
1402  // by rlwinm and friends in 64-bit mode).
1403  bool Repl32;
1404  // Did converting to Repl32 == true change the rotation factor? If it did,
1405  // it decreased it by 32.
1406  bool Repl32CR;
1407  // Was this group coalesced after setting Repl32 to true?
1408  bool Repl32Coalesced;
1409 
1410  BitGroup(SDValue V, unsigned R, unsigned S, unsigned E)
1411  : V(V), RLAmt(R), StartIdx(S), EndIdx(E), Repl32(false), Repl32CR(false),
1412  Repl32Coalesced(false) {
1413  LLVM_DEBUG(dbgs() << "\tbit group for " << V.getNode() << " RLAmt = " << R
1414  << " [" << S << ", " << E << "]\n");
1415  }
1416  };
1417 
1418  // Information on each (Value, RLAmt) pair (like the number of groups
1419  // associated with each) used to choose the lowering method.
1420  struct ValueRotInfo {
1421  SDValue V;
1422  unsigned RLAmt = std::numeric_limits<unsigned>::max();
1423  unsigned NumGroups = 0;
1424  unsigned FirstGroupStartIdx = std::numeric_limits<unsigned>::max();
1425  bool Repl32 = false;
1426 
1427  ValueRotInfo() = default;
1428 
1429  // For sorting (in reverse order) by NumGroups, and then by
1430  // FirstGroupStartIdx.
1431  bool operator < (const ValueRotInfo &Other) const {
1432  // We need to sort so that the non-Repl32 come first because, when we're
1433  // doing masking, the Repl32 bit groups might be subsumed into the 64-bit
1434  // masking operation.
1435  if (Repl32 < Other.Repl32)
1436  return true;
1437  else if (Repl32 > Other.Repl32)
1438  return false;
1439  else if (NumGroups > Other.NumGroups)
1440  return true;
1441  else if (NumGroups < Other.NumGroups)
1442  return false;
1443  else if (RLAmt == 0 && Other.RLAmt != 0)
1444  return true;
1445  else if (RLAmt != 0 && Other.RLAmt == 0)
1446  return false;
1447  else if (FirstGroupStartIdx < Other.FirstGroupStartIdx)
1448  return true;
1449  return false;
1450  }
1451  };
1452 
1453  using ValueBitsMemoizedValue = std::pair<bool, SmallVector<ValueBit, 64>>;
1454  using ValueBitsMemoizer =
1456  ValueBitsMemoizer Memoizer;
1457 
1458  // Return a pair of bool and a SmallVector pointer to a memoization entry.
1459  // The bool is true if something interesting was deduced, otherwise if we're
1460  // providing only a generic representation of V (or something else likewise
1461  // uninteresting for instruction selection) through the SmallVector.
1462  std::pair<bool, SmallVector<ValueBit, 64> *> getValueBits(SDValue V,
1463  unsigned NumBits) {
1464  auto &ValueEntry = Memoizer[V];
1465  if (ValueEntry)
1466  return std::make_pair(ValueEntry->first, &ValueEntry->second);
1467  ValueEntry.reset(new ValueBitsMemoizedValue());
1468  bool &Interesting = ValueEntry->first;
1469  SmallVector<ValueBit, 64> &Bits = ValueEntry->second;
1470  Bits.resize(NumBits);
1471 
1472  switch (V.getOpcode()) {
1473  default: break;
1474  case ISD::ROTL:
1475  if (isa<ConstantSDNode>(V.getOperand(1))) {
1476  unsigned RotAmt = V.getConstantOperandVal(1);
1477 
1478  const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
1479 
1480  for (unsigned i = 0; i < NumBits; ++i)
1481  Bits[i] = LHSBits[i < RotAmt ? i + (NumBits - RotAmt) : i - RotAmt];
1482 
1483  return std::make_pair(Interesting = true, &Bits);
1484  }
1485  break;
1486  case ISD::SHL:
1487  case PPCISD::SHL:
1488  if (isa<ConstantSDNode>(V.getOperand(1))) {
1489  unsigned ShiftAmt = V.getConstantOperandVal(1);
1490 
1491  const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
1492 
1493  for (unsigned i = ShiftAmt; i < NumBits; ++i)
1494  Bits[i] = LHSBits[i - ShiftAmt];
1495 
1496  for (unsigned i = 0; i < ShiftAmt; ++i)
1497  Bits[i] = ValueBit(ValueBit::ConstZero);
1498 
1499  return std::make_pair(Interesting = true, &Bits);
1500  }
1501  break;
1502  case ISD::SRL:
1503  case PPCISD::SRL:
1504  if (isa<ConstantSDNode>(V.getOperand(1))) {
1505  unsigned ShiftAmt = V.getConstantOperandVal(1);
1506 
1507  const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
1508 
1509  for (unsigned i = 0; i < NumBits - ShiftAmt; ++i)
1510  Bits[i] = LHSBits[i + ShiftAmt];
1511 
1512  for (unsigned i = NumBits - ShiftAmt; i < NumBits; ++i)
1513  Bits[i] = ValueBit(ValueBit::ConstZero);
1514 
1515  return std::make_pair(Interesting = true, &Bits);
1516  }
1517  break;
1518  case ISD::AND:
1519  if (isa<ConstantSDNode>(V.getOperand(1))) {
1521 
1522  const SmallVector<ValueBit, 64> *LHSBits;
1523  // Mark this as interesting, only if the LHS was also interesting. This
1524  // prevents the overall procedure from matching a single immediate 'and'
1525  // (which is non-optimal because such an and might be folded with other
1526  // things if we don't select it here).
1527  std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0), NumBits);
1528 
1529  for (unsigned i = 0; i < NumBits; ++i)
1530  if (((Mask >> i) & 1) == 1)
1531  Bits[i] = (*LHSBits)[i];
1532  else {
1533  // AND instruction masks this bit. If the input is already zero,
1534  // we have nothing to do here. Otherwise, make the bit ConstZero.
1535  if ((*LHSBits)[i].isZero())
1536  Bits[i] = (*LHSBits)[i];
1537  else
1538  Bits[i] = ValueBit(ValueBit::ConstZero);
1539  }
1540 
1541  return std::make_pair(Interesting, &Bits);
1542  }
1543  break;
1544  case ISD::OR: {
1545  const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
1546  const auto &RHSBits = *getValueBits(V.getOperand(1), NumBits).second;
1547 
1548  bool AllDisjoint = true;
1549  SDValue LastVal = SDValue();
1550  unsigned LastIdx = 0;
1551  for (unsigned i = 0; i < NumBits; ++i) {
1552  if (LHSBits[i].isZero() && RHSBits[i].isZero()) {
1553  // If both inputs are known to be zero and one is ConstZero and
1554  // another is VariableKnownToBeZero, we can select whichever
1555  // we like. To minimize the number of bit groups, we select
1556  // VariableKnownToBeZero if this bit is the next bit of the same
1557  // input variable from the previous bit. Otherwise, we select
1558  // ConstZero.
1559  if (LHSBits[i].hasValue() && LHSBits[i].getValue() == LastVal &&
1560  LHSBits[i].getValueBitIndex() == LastIdx + 1)
1561  Bits[i] = LHSBits[i];
1562  else if (RHSBits[i].hasValue() && RHSBits[i].getValue() == LastVal &&
1563  RHSBits[i].getValueBitIndex() == LastIdx + 1)
1564  Bits[i] = RHSBits[i];
1565  else
1566  Bits[i] = ValueBit(ValueBit::ConstZero);
1567  }
1568  else if (LHSBits[i].isZero())
1569  Bits[i] = RHSBits[i];
1570  else if (RHSBits[i].isZero())
1571  Bits[i] = LHSBits[i];
1572  else {
1573  AllDisjoint = false;
1574  break;
1575  }
1576  // We remember the value and bit index of this bit.
1577  if (Bits[i].hasValue()) {
1578  LastVal = Bits[i].getValue();
1579  LastIdx = Bits[i].getValueBitIndex();
1580  }
1581  else {
1582  if (LastVal) LastVal = SDValue();
1583  LastIdx = 0;
1584  }
1585  }
1586 
1587  if (!AllDisjoint)
1588  break;
1589 
1590  return std::make_pair(Interesting = true, &Bits);
1591  }
1592  case ISD::ZERO_EXTEND: {
1593  // We support only the case with zero extension from i32 to i64 so far.
1594  if (V.getValueType() != MVT::i64 ||
1595  V.getOperand(0).getValueType() != MVT::i32)
1596  break;
1597 
1598  const SmallVector<ValueBit, 64> *LHSBits;
1599  const unsigned NumOperandBits = 32;
1600  std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0),
1601  NumOperandBits);
1602 
1603  for (unsigned i = 0; i < NumOperandBits; ++i)
1604  Bits[i] = (*LHSBits)[i];
1605 
1606  for (unsigned i = NumOperandBits; i < NumBits; ++i)
1607  Bits[i] = ValueBit(ValueBit::ConstZero);
1608 
1609  return std::make_pair(Interesting, &Bits);
1610  }
1611  case ISD::TRUNCATE: {
1613  EVT ToType = V.getValueType();
1614  // We support only the case with truncate from i64 to i32.
1615  if (FromType != MVT::i64 || ToType != MVT::i32)
1616  break;
1617  const unsigned NumAllBits = FromType.getSizeInBits();
1618  SmallVector<ValueBit, 64> *InBits;
1619  std::tie(Interesting, InBits) = getValueBits(V.getOperand(0),
1620  NumAllBits);
1621  const unsigned NumValidBits = ToType.getSizeInBits();
1622 
1623  // A 32-bit instruction cannot touch upper 32-bit part of 64-bit value.
1624  // So, we cannot include this truncate.
1625  bool UseUpper32bit = false;
1626  for (unsigned i = 0; i < NumValidBits; ++i)
1627  if ((*InBits)[i].hasValue() && (*InBits)[i].getValueBitIndex() >= 32) {
1628  UseUpper32bit = true;
1629  break;
1630  }
1631  if (UseUpper32bit)
1632  break;
1633 
1634  for (unsigned i = 0; i < NumValidBits; ++i)
1635  Bits[i] = (*InBits)[i];
1636 
1637  return std::make_pair(Interesting, &Bits);
1638  }
1639  case ISD::AssertZext: {
1640  // For AssertZext, we look through the operand and
1641  // mark the bits known to be zero.
1642  const SmallVector<ValueBit, 64> *LHSBits;
1643  std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0),
1644  NumBits);
1645 
1646  EVT FromType = cast<VTSDNode>(V.getOperand(1))->getVT();
1647  const unsigned NumValidBits = FromType.getSizeInBits();
1648  for (unsigned i = 0; i < NumValidBits; ++i)
1649  Bits[i] = (*LHSBits)[i];
1650 
1651  // These bits are known to be zero but the AssertZext may be from a value
1652  // that already has some constant zero bits (i.e. from a masking and).
1653  for (unsigned i = NumValidBits; i < NumBits; ++i)
1654  Bits[i] = (*LHSBits)[i].hasValue()
1655  ? ValueBit((*LHSBits)[i].getValue(),
1656  (*LHSBits)[i].getValueBitIndex(),
1657  ValueBit::VariableKnownToBeZero)
1658  : ValueBit(ValueBit::ConstZero);
1659 
1660  return std::make_pair(Interesting, &Bits);
1661  }
1662  case ISD::LOAD:
1663  LoadSDNode *LD = cast<LoadSDNode>(V);
1664  if (ISD::isZEXTLoad(V.getNode()) && V.getResNo() == 0) {
1665  EVT VT = LD->getMemoryVT();
1666  const unsigned NumValidBits = VT.getSizeInBits();
1667 
1668  for (unsigned i = 0; i < NumValidBits; ++i)
1669  Bits[i] = ValueBit(V, i);
1670 
1671  // These bits are known to be zero.
1672  for (unsigned i = NumValidBits; i < NumBits; ++i)
1673  Bits[i] = ValueBit(V, i, ValueBit::VariableKnownToBeZero);
1674 
1675  // Zero-extending load itself cannot be optimized. So, it is not
1676  // interesting by itself though it gives useful information.
1677  return std::make_pair(Interesting = false, &Bits);
1678  }
1679  break;
1680  }
1681 
1682  for (unsigned i = 0; i < NumBits; ++i)
1683  Bits[i] = ValueBit(V, i);
1684 
1685  return std::make_pair(Interesting = false, &Bits);
1686  }
1687 
1688  // For each value (except the constant ones), compute the left-rotate amount
1689  // to get it from its original to final position.
1690  void computeRotationAmounts() {
1691  NeedMask = false;
1692  RLAmt.resize(Bits.size());
1693  for (unsigned i = 0; i < Bits.size(); ++i)
1694  if (Bits[i].hasValue()) {
1695  unsigned VBI = Bits[i].getValueBitIndex();
1696  if (i >= VBI)
1697  RLAmt[i] = i - VBI;
1698  else
1699  RLAmt[i] = Bits.size() - (VBI - i);
1700  } else if (Bits[i].isZero()) {
1701  NeedMask = true;
1702  RLAmt[i] = UINT32_MAX;
1703  } else {
1704  llvm_unreachable("Unknown value bit type");
1705  }
1706  }
1707 
1708  // Collect groups of consecutive bits with the same underlying value and
1709  // rotation factor. If we're doing late masking, we ignore zeros, otherwise
1710  // they break up groups.
1711  void collectBitGroups(bool LateMask) {
1712  BitGroups.clear();
1713 
1714  unsigned LastRLAmt = RLAmt[0];
1715  SDValue LastValue = Bits[0].hasValue() ? Bits[0].getValue() : SDValue();
1716  unsigned LastGroupStartIdx = 0;
1717  bool IsGroupOfZeros = !Bits[LastGroupStartIdx].hasValue();
1718  for (unsigned i = 1; i < Bits.size(); ++i) {
1719  unsigned ThisRLAmt = RLAmt[i];
1720  SDValue ThisValue = Bits[i].hasValue() ? Bits[i].getValue() : SDValue();
1721  if (LateMask && !ThisValue) {
1722  ThisValue = LastValue;
1723  ThisRLAmt = LastRLAmt;
1724  // If we're doing late masking, then the first bit group always starts
1725  // at zero (even if the first bits were zero).
1726  if (BitGroups.empty())
1727  LastGroupStartIdx = 0;
1728  }
1729 
1730  // If this bit is known to be zero and the current group is a bit group
1731  // of zeros, we do not need to terminate the current bit group even the
1732  // Value or RLAmt does not match here. Instead, we terminate this group
1733  // when the first non-zero bit appears later.
1734  if (IsGroupOfZeros && Bits[i].isZero())
1735  continue;
1736 
1737  // If this bit has the same underlying value and the same rotate factor as
1738  // the last one, then they're part of the same group.
1739  if (ThisRLAmt == LastRLAmt && ThisValue == LastValue)
1740  // We cannot continue the current group if this bits is not known to
1741  // be zero in a bit group of zeros.
1742  if (!(IsGroupOfZeros && ThisValue && !Bits[i].isZero()))
1743  continue;
1744 
1745  if (LastValue.getNode())
1746  BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
1747  i-1));
1748  LastRLAmt = ThisRLAmt;
1749  LastValue = ThisValue;
1750  LastGroupStartIdx = i;
1751  IsGroupOfZeros = !Bits[LastGroupStartIdx].hasValue();
1752  }
1753  if (LastValue.getNode())
1754  BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
1755  Bits.size()-1));
1756 
1757  if (BitGroups.empty())
1758  return;
1759 
1760  // We might be able to combine the first and last groups.
1761  if (BitGroups.size() > 1) {
1762  // If the first and last groups are the same, then remove the first group
1763  // in favor of the last group, making the ending index of the last group
1764  // equal to the ending index of the to-be-removed first group.
1765  if (BitGroups[0].StartIdx == 0 &&
1766  BitGroups[BitGroups.size()-1].EndIdx == Bits.size()-1 &&
1767  BitGroups[0].V == BitGroups[BitGroups.size()-1].V &&
1768  BitGroups[0].RLAmt == BitGroups[BitGroups.size()-1].RLAmt) {
1769  LLVM_DEBUG(dbgs() << "\tcombining final bit group with initial one\n");
1770  BitGroups[BitGroups.size()-1].EndIdx = BitGroups[0].EndIdx;
1771  BitGroups.erase(BitGroups.begin());
1772  }
1773  }
1774  }
1775 
1776  // Take all (SDValue, RLAmt) pairs and sort them by the number of groups
1777  // associated with each. If the number of groups are same, we prefer a group
1778  // which does not require rotate, i.e. RLAmt is 0, to avoid the first rotate
1779  // instruction. If there is a degeneracy, pick the one that occurs
1780  // first (in the final value).
1781  void collectValueRotInfo() {
1782  ValueRots.clear();
1783 
1784  for (auto &BG : BitGroups) {
1785  unsigned RLAmtKey = BG.RLAmt + (BG.Repl32 ? 64 : 0);
1786  ValueRotInfo &VRI = ValueRots[std::make_pair(BG.V, RLAmtKey)];
1787  VRI.V = BG.V;
1788  VRI.RLAmt = BG.RLAmt;
1789  VRI.Repl32 = BG.Repl32;
1790  VRI.NumGroups += 1;
1791  VRI.FirstGroupStartIdx = std::min(VRI.FirstGroupStartIdx, BG.StartIdx);
1792  }
1793 
1794  // Now that we've collected the various ValueRotInfo instances, we need to
1795  // sort them.
1796  ValueRotsVec.clear();
1797  for (auto &I : ValueRots) {
1798  ValueRotsVec.push_back(I.second);
1799  }
1800  llvm::sort(ValueRotsVec);
1801  }
1802 
1803  // In 64-bit mode, rlwinm and friends have a rotation operator that
1804  // replicates the low-order 32 bits into the high-order 32-bits. The mask
1805  // indices of these instructions can only be in the lower 32 bits, so they
1806  // can only represent some 64-bit bit groups. However, when they can be used,
1807  // the 32-bit replication can be used to represent, as a single bit group,
1808  // otherwise separate bit groups. We'll convert to replicated-32-bit bit
1809  // groups when possible. Returns true if any of the bit groups were
1810  // converted.
1811  void assignRepl32BitGroups() {
1812  // If we have bits like this:
1813  //
1814  // Indices: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1815  // V bits: ... 7 6 5 4 3 2 1 0 31 30 29 28 27 26 25 24
1816  // Groups: | RLAmt = 8 | RLAmt = 40 |
1817  //
1818  // But, making use of a 32-bit operation that replicates the low-order 32
1819  // bits into the high-order 32 bits, this can be one bit group with a RLAmt
1820  // of 8.
1821 
1822  auto IsAllLow32 = [this](BitGroup & BG) {
1823  if (BG.StartIdx <= BG.EndIdx) {
1824  for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i) {
1825  if (!Bits[i].hasValue())
1826  continue;
1827  if (Bits[i].getValueBitIndex() >= 32)
1828  return false;
1829  }
1830  } else {
1831  for (unsigned i = BG.StartIdx; i < Bits.size(); ++i) {
1832  if (!Bits[i].hasValue())
1833  continue;
1834  if (Bits[i].getValueBitIndex() >= 32)
1835  return false;
1836  }
1837  for (unsigned i = 0; i <= BG.EndIdx; ++i) {
1838  if (!Bits[i].hasValue())
1839  continue;
1840  if (Bits[i].getValueBitIndex() >= 32)
1841  return false;
1842  }
1843  }
1844 
1845  return true;
1846  };
1847 
1848  for (auto &BG : BitGroups) {
1849  // If this bit group has RLAmt of 0 and will not be merged with
1850  // another bit group, we don't benefit from Repl32. We don't mark
1851  // such group to give more freedom for later instruction selection.
1852  if (BG.RLAmt == 0) {
1853  auto PotentiallyMerged = [this](BitGroup & BG) {
1854  for (auto &BG2 : BitGroups)
1855  if (&BG != &BG2 && BG.V == BG2.V &&
1856  (BG2.RLAmt == 0 || BG2.RLAmt == 32))
1857  return true;
1858  return false;
1859  };
1860  if (!PotentiallyMerged(BG))
1861  continue;
1862  }
1863  if (BG.StartIdx < 32 && BG.EndIdx < 32) {
1864  if (IsAllLow32(BG)) {
1865  if (BG.RLAmt >= 32) {
1866  BG.RLAmt -= 32;
1867  BG.Repl32CR = true;
1868  }
1869 
1870  BG.Repl32 = true;
1871 
1872  LLVM_DEBUG(dbgs() << "\t32-bit replicated bit group for "
1873  << BG.V.getNode() << " RLAmt = " << BG.RLAmt << " ["
1874  << BG.StartIdx << ", " << BG.EndIdx << "]\n");
1875  }
1876  }
1877  }
1878 
1879  // Now walk through the bit groups, consolidating where possible.
1880  for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1881  // We might want to remove this bit group by merging it with the previous
1882  // group (which might be the ending group).
1883  auto IP = (I == BitGroups.begin()) ?
1884  std::prev(BitGroups.end()) : std::prev(I);
1885  if (I->Repl32 && IP->Repl32 && I->V == IP->V && I->RLAmt == IP->RLAmt &&
1886  I->StartIdx == (IP->EndIdx + 1) % 64 && I != IP) {
1887 
1888  LLVM_DEBUG(dbgs() << "\tcombining 32-bit replicated bit group for "
1889  << I->V.getNode() << " RLAmt = " << I->RLAmt << " ["
1890  << I->StartIdx << ", " << I->EndIdx
1891  << "] with group with range [" << IP->StartIdx << ", "
1892  << IP->EndIdx << "]\n");
1893 
1894  IP->EndIdx = I->EndIdx;
1895  IP->Repl32CR = IP->Repl32CR || I->Repl32CR;
1896  IP->Repl32Coalesced = true;
1897  I = BitGroups.erase(I);
1898  continue;
1899  } else {
1900  // There is a special case worth handling: If there is a single group
1901  // covering the entire upper 32 bits, and it can be merged with both
1902  // the next and previous groups (which might be the same group), then
1903  // do so. If it is the same group (so there will be only one group in
1904  // total), then we need to reverse the order of the range so that it
1905  // covers the entire 64 bits.
1906  if (I->StartIdx == 32 && I->EndIdx == 63) {
1907  assert(std::next(I) == BitGroups.end() &&
1908  "bit group ends at index 63 but there is another?");
1909  auto IN = BitGroups.begin();
1910 
1911  if (IP->Repl32 && IN->Repl32 && I->V == IP->V && I->V == IN->V &&
1912  (I->RLAmt % 32) == IP->RLAmt && (I->RLAmt % 32) == IN->RLAmt &&
1913  IP->EndIdx == 31 && IN->StartIdx == 0 && I != IP &&
1914  IsAllLow32(*I)) {
1915 
1916  LLVM_DEBUG(dbgs() << "\tcombining bit group for " << I->V.getNode()
1917  << " RLAmt = " << I->RLAmt << " [" << I->StartIdx
1918  << ", " << I->EndIdx
1919  << "] with 32-bit replicated groups with ranges ["
1920  << IP->StartIdx << ", " << IP->EndIdx << "] and ["
1921  << IN->StartIdx << ", " << IN->EndIdx << "]\n");
1922 
1923  if (IP == IN) {
1924  // There is only one other group; change it to cover the whole
1925  // range (backward, so that it can still be Repl32 but cover the
1926  // whole 64-bit range).
1927  IP->StartIdx = 31;
1928  IP->EndIdx = 30;
1929  IP->Repl32CR = IP->Repl32CR || I->RLAmt >= 32;
1930  IP->Repl32Coalesced = true;
1931  I = BitGroups.erase(I);
1932  } else {
1933  // There are two separate groups, one before this group and one
1934  // after us (at the beginning). We're going to remove this group,
1935  // but also the group at the very beginning.
1936  IP->EndIdx = IN->EndIdx;
1937  IP->Repl32CR = IP->Repl32CR || IN->Repl32CR || I->RLAmt >= 32;
1938  IP->Repl32Coalesced = true;
1939  I = BitGroups.erase(I);
1940  BitGroups.erase(BitGroups.begin());
1941  }
1942 
1943  // This must be the last group in the vector (and we might have
1944  // just invalidated the iterator above), so break here.
1945  break;
1946  }
1947  }
1948  }
1949 
1950  ++I;
1951  }
1952  }
1953 
1954  SDValue getI32Imm(unsigned Imm, const SDLoc &dl) {
1955  return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
1956  }
1957 
1958  uint64_t getZerosMask() {
1959  uint64_t Mask = 0;
1960  for (unsigned i = 0; i < Bits.size(); ++i) {
1961  if (Bits[i].hasValue())
1962  continue;
1963  Mask |= (UINT64_C(1) << i);
1964  }
1965 
1966  return ~Mask;
1967  }
1968 
1969  // This method extends an input value to 64 bit if input is 32-bit integer.
1970  // While selecting instructions in BitPermutationSelector in 64-bit mode,
1971  // an input value can be a 32-bit integer if a ZERO_EXTEND node is included.
1972  // In such case, we extend it to 64 bit to be consistent with other values.
1973  SDValue ExtendToInt64(SDValue V, const SDLoc &dl) {
1974  if (V.getValueSizeInBits() == 64)
1975  return V;
1976 
1977  assert(V.getValueSizeInBits() == 32);
1978  SDValue SubRegIdx = CurDAG->getTargetConstant(PPC::sub_32, dl, MVT::i32);
1979  SDValue ImDef = SDValue(CurDAG->getMachineNode(PPC::IMPLICIT_DEF, dl,
1980  MVT::i64), 0);
1981  SDValue ExtVal = SDValue(CurDAG->getMachineNode(PPC::INSERT_SUBREG, dl,
1982  MVT::i64, ImDef, V,
1983  SubRegIdx), 0);
1984  return ExtVal;
1985  }
1986 
1987  SDValue TruncateToInt32(SDValue V, const SDLoc &dl) {
1988  if (V.getValueSizeInBits() == 32)
1989  return V;
1990 
1991  assert(V.getValueSizeInBits() == 64);
1992  SDValue SubRegIdx = CurDAG->getTargetConstant(PPC::sub_32, dl, MVT::i32);
1993  SDValue SubVal = SDValue(CurDAG->getMachineNode(PPC::EXTRACT_SUBREG, dl,
1994  MVT::i32, V, SubRegIdx), 0);
1995  return SubVal;
1996  }
1997 
1998  // Depending on the number of groups for a particular value, it might be
1999  // better to rotate, mask explicitly (using andi/andis), and then or the
2000  // result. Select this part of the result first.
2001  void SelectAndParts32(const SDLoc &dl, SDValue &Res, unsigned *InstCnt) {
2003  return;
2004 
2005  for (ValueRotInfo &VRI : ValueRotsVec) {
2006  unsigned Mask = 0;
2007  for (unsigned i = 0; i < Bits.size(); ++i) {
2008  if (!Bits[i].hasValue() || Bits[i].getValue() != VRI.V)
2009  continue;
2010  if (RLAmt[i] != VRI.RLAmt)
2011  continue;
2012  Mask |= (1u << i);
2013  }
2014 
2015  // Compute the masks for andi/andis that would be necessary.
2016  unsigned ANDIMask = (Mask & UINT16_MAX), ANDISMask = Mask >> 16;
2017  assert((ANDIMask != 0 || ANDISMask != 0) &&
2018  "No set bits in mask for value bit groups");
2019  bool NeedsRotate = VRI.RLAmt != 0;
2020 
2021  // We're trying to minimize the number of instructions. If we have one
2022  // group, using one of andi/andis can break even. If we have three
2023  // groups, we can use both andi and andis and break even (to use both
2024  // andi and andis we also need to or the results together). We need four
2025  // groups if we also need to rotate. To use andi/andis we need to do more
2026  // than break even because rotate-and-mask instructions tend to be easier
2027  // to schedule.
2028 
2029  // FIXME: We've biased here against using andi/andis, which is right for
2030  // POWER cores, but not optimal everywhere. For example, on the A2,
2031  // andi/andis have single-cycle latency whereas the rotate-and-mask
2032  // instructions take two cycles, and it would be better to bias toward
2033  // andi/andis in break-even cases.
2034 
2035  unsigned NumAndInsts = (unsigned) NeedsRotate +
2036  (unsigned) (ANDIMask != 0) +
2037  (unsigned) (ANDISMask != 0) +
2038  (unsigned) (ANDIMask != 0 && ANDISMask != 0) +
2039  (unsigned) (bool) Res;
2040 
2041  LLVM_DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode()
2042  << " RL: " << VRI.RLAmt << ":"
2043  << "\n\t\t\tisel using masking: " << NumAndInsts
2044  << " using rotates: " << VRI.NumGroups << "\n");
2045 
2046  if (NumAndInsts >= VRI.NumGroups)
2047  continue;
2048 
2049  LLVM_DEBUG(dbgs() << "\t\t\t\tusing masking\n");
2050 
2051  if (InstCnt) *InstCnt += NumAndInsts;
2052 
2053  SDValue VRot;
2054  if (VRI.RLAmt) {
2055  SDValue Ops[] =
2056  { TruncateToInt32(VRI.V, dl), getI32Imm(VRI.RLAmt, dl),
2057  getI32Imm(0, dl), getI32Imm(31, dl) };
2058  VRot = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
2059  Ops), 0);
2060  } else {
2061  VRot = TruncateToInt32(VRI.V, dl);
2062  }
2063 
2064  SDValue ANDIVal, ANDISVal;
2065  if (ANDIMask != 0)
2066  ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDI_rec, dl, MVT::i32,
2067  VRot, getI32Imm(ANDIMask, dl)),
2068  0);
2069  if (ANDISMask != 0)
2070  ANDISVal =
2071  SDValue(CurDAG->getMachineNode(PPC::ANDIS_rec, dl, MVT::i32, VRot,
2072  getI32Imm(ANDISMask, dl)),
2073  0);
2074 
2075  SDValue TotalVal;
2076  if (!ANDIVal)
2077  TotalVal = ANDISVal;
2078  else if (!ANDISVal)
2079  TotalVal = ANDIVal;
2080  else
2081  TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
2082  ANDIVal, ANDISVal), 0);
2083 
2084  if (!Res)
2085  Res = TotalVal;
2086  else
2087  Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
2088  Res, TotalVal), 0);
2089 
2090  // Now, remove all groups with this underlying value and rotation
2091  // factor.
2092  eraseMatchingBitGroups([VRI](const BitGroup &BG) {
2093  return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt;
2094  });
2095  }
2096  }
2097 
2098  // Instruction selection for the 32-bit case.
2099  SDNode *Select32(SDNode *N, bool LateMask, unsigned *InstCnt) {
2100  SDLoc dl(N);
2101  SDValue Res;
2102 
2103  if (InstCnt) *InstCnt = 0;
2104 
2105  // Take care of cases that should use andi/andis first.
2106  SelectAndParts32(dl, Res, InstCnt);
2107 
2108  // If we've not yet selected a 'starting' instruction, and we have no zeros
2109  // to fill in, select the (Value, RLAmt) with the highest priority (largest
2110  // number of groups), and start with this rotated value.
2111  if ((!NeedMask || LateMask) && !Res) {
2112  ValueRotInfo &VRI = ValueRotsVec[0];
2113  if (VRI.RLAmt) {
2114  if (InstCnt) *InstCnt += 1;
2115  SDValue Ops[] =
2116  { TruncateToInt32(VRI.V, dl), getI32Imm(VRI.RLAmt, dl),
2117  getI32Imm(0, dl), getI32Imm(31, dl) };
2118  Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops),
2119  0);
2120  } else {
2121  Res = TruncateToInt32(VRI.V, dl);
2122  }
2123 
2124  // Now, remove all groups with this underlying value and rotation factor.
2125  eraseMatchingBitGroups([VRI](const BitGroup &BG) {
2126  return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt;
2127  });
2128  }
2129 
2130  if (InstCnt) *InstCnt += BitGroups.size();
2131 
2132  // Insert the other groups (one at a time).
2133  for (auto &BG : BitGroups) {
2134  if (!Res) {
2135  SDValue Ops[] =
2136  { TruncateToInt32(BG.V, dl), getI32Imm(BG.RLAmt, dl),
2137  getI32Imm(Bits.size() - BG.EndIdx - 1, dl),
2138  getI32Imm(Bits.size() - BG.StartIdx - 1, dl) };
2139  Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
2140  } else {
2141  SDValue Ops[] =
2142  { Res, TruncateToInt32(BG.V, dl), getI32Imm(BG.RLAmt, dl),
2143  getI32Imm(Bits.size() - BG.EndIdx - 1, dl),
2144  getI32Imm(Bits.size() - BG.StartIdx - 1, dl) };
2145  Res = SDValue(CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops), 0);
2146  }
2147  }
2148 
2149  if (LateMask) {
2150  unsigned Mask = (unsigned) getZerosMask();
2151 
2152  unsigned ANDIMask = (Mask & UINT16_MAX), ANDISMask = Mask >> 16;
2153  assert((ANDIMask != 0 || ANDISMask != 0) &&
2154  "No set bits in zeros mask?");
2155 
2156  if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
2157  (unsigned) (ANDISMask != 0) +
2158  (unsigned) (ANDIMask != 0 && ANDISMask != 0);
2159 
2160  SDValue ANDIVal, ANDISVal;
2161  if (ANDIMask != 0)
2162  ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDI_rec, dl, MVT::i32,
2163  Res, getI32Imm(ANDIMask, dl)),
2164  0);
2165  if (ANDISMask != 0)
2166  ANDISVal =
2167  SDValue(CurDAG->getMachineNode(PPC::ANDIS_rec, dl, MVT::i32, Res,
2168  getI32Imm(ANDISMask, dl)),
2169  0);
2170 
2171  if (!ANDIVal)
2172  Res = ANDISVal;
2173  else if (!ANDISVal)
2174  Res = ANDIVal;
2175  else
2176  Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
2177  ANDIVal, ANDISVal), 0);
2178  }
2179 
2180  return Res.getNode();
2181  }
2182 
2183  unsigned SelectRotMask64Count(unsigned RLAmt, bool Repl32,
2184  unsigned MaskStart, unsigned MaskEnd,
2185  bool IsIns) {
2186  // In the notation used by the instructions, 'start' and 'end' are reversed
2187  // because bits are counted from high to low order.
2188  unsigned InstMaskStart = 64 - MaskEnd - 1,
2189  InstMaskEnd = 64 - MaskStart - 1;
2190 
2191  if (Repl32)
2192  return 1;
2193 
2194  if ((!IsIns && (InstMaskEnd == 63 || InstMaskStart == 0)) ||
2195  InstMaskEnd == 63 - RLAmt)
2196  return 1;
2197 
2198  return 2;
2199  }
2200 
2201  // For 64-bit values, not all combinations of rotates and masks are
2202  // available. Produce one if it is available.
2203  SDValue SelectRotMask64(SDValue V, const SDLoc &dl, unsigned RLAmt,
2204  bool Repl32, unsigned MaskStart, unsigned MaskEnd,
2205  unsigned *InstCnt = nullptr) {
2206  // In the notation used by the instructions, 'start' and 'end' are reversed
2207  // because bits are counted from high to low order.
2208  unsigned InstMaskStart = 64 - MaskEnd - 1,
2209  InstMaskEnd = 64 - MaskStart - 1;
2210 
2211  if (InstCnt) *InstCnt += 1;
2212 
2213  if (Repl32) {
2214  // This rotation amount assumes that the lower 32 bits of the quantity
2215  // are replicated in the high 32 bits by the rotation operator (which is
2216  // done by rlwinm and friends).
2217  assert(InstMaskStart >= 32 && "Mask cannot start out of range");
2218  assert(InstMaskEnd >= 32 && "Mask cannot end out of range");
2219  SDValue Ops[] =
2220  { ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
2221  getI32Imm(InstMaskStart - 32, dl), getI32Imm(InstMaskEnd - 32, dl) };
2222  return SDValue(CurDAG->getMachineNode(PPC::RLWINM8, dl, MVT::i64,
2223  Ops), 0);
2224  }
2225 
2226  if (InstMaskEnd == 63) {
2227  SDValue Ops[] =
2228  { ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
2229  getI32Imm(InstMaskStart, dl) };
2230  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Ops), 0);
2231  }
2232 
2233  if (InstMaskStart == 0) {
2234  SDValue Ops[] =
2235  { ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
2236  getI32Imm(InstMaskEnd, dl) };
2237  return SDValue(CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64, Ops), 0);
2238  }
2239 
2240  if (InstMaskEnd == 63 - RLAmt) {
2241  SDValue Ops[] =
2242  { ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
2243  getI32Imm(InstMaskStart, dl) };
2244  return SDValue(CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, Ops), 0);
2245  }
2246 
2247  // We cannot do this with a single instruction, so we'll use two. The
2248  // problem is that we're not free to choose both a rotation amount and mask
2249  // start and end independently. We can choose an arbitrary mask start and
2250  // end, but then the rotation amount is fixed. Rotation, however, can be
2251  // inverted, and so by applying an "inverse" rotation first, we can get the
2252  // desired result.
2253  if (InstCnt) *InstCnt += 1;
2254 
2255  // The rotation mask for the second instruction must be MaskStart.
2256  unsigned RLAmt2 = MaskStart;
2257  // The first instruction must rotate V so that the overall rotation amount
2258  // is RLAmt.
2259  unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
2260  if (RLAmt1)
2261  V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
2262  return SelectRotMask64(V, dl, RLAmt2, false, MaskStart, MaskEnd);
2263  }
2264 
2265  // For 64-bit values, not all combinations of rotates and masks are
2266  // available. Produce a rotate-mask-and-insert if one is available.
2267  SDValue SelectRotMaskIns64(SDValue Base, SDValue V, const SDLoc &dl,
2268  unsigned RLAmt, bool Repl32, unsigned MaskStart,
2269  unsigned MaskEnd, unsigned *InstCnt = nullptr) {
2270  // In the notation used by the instructions, 'start' and 'end' are reversed
2271  // because bits are counted from high to low order.
2272  unsigned InstMaskStart = 64 - MaskEnd - 1,
2273  InstMaskEnd = 64 - MaskStart - 1;
2274 
2275  if (InstCnt) *InstCnt += 1;
2276 
2277  if (Repl32) {
2278  // This rotation amount assumes that the lower 32 bits of the quantity
2279  // are replicated in the high 32 bits by the rotation operator (which is
2280  // done by rlwinm and friends).
2281  assert(InstMaskStart >= 32 && "Mask cannot start out of range");
2282  assert(InstMaskEnd >= 32 && "Mask cannot end out of range");
2283  SDValue Ops[] =
2284  { ExtendToInt64(Base, dl), ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
2285  getI32Imm(InstMaskStart - 32, dl), getI32Imm(InstMaskEnd - 32, dl) };
2286  return SDValue(CurDAG->getMachineNode(PPC::RLWIMI8, dl, MVT::i64,
2287  Ops), 0);
2288  }
2289 
2290  if (InstMaskEnd == 63 - RLAmt) {
2291  SDValue Ops[] =
2292  { ExtendToInt64(Base, dl), ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
2293  getI32Imm(InstMaskStart, dl) };
2294  return SDValue(CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops), 0);
2295  }
2296 
2297  // We cannot do this with a single instruction, so we'll use two. The
2298  // problem is that we're not free to choose both a rotation amount and mask
2299  // start and end independently. We can choose an arbitrary mask start and
2300  // end, but then the rotation amount is fixed. Rotation, however, can be
2301  // inverted, and so by applying an "inverse" rotation first, we can get the
2302  // desired result.
2303  if (InstCnt) *InstCnt += 1;
2304 
2305  // The rotation mask for the second instruction must be MaskStart.
2306  unsigned RLAmt2 = MaskStart;
2307  // The first instruction must rotate V so that the overall rotation amount
2308  // is RLAmt.
2309  unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
2310  if (RLAmt1)
2311  V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
2312  return SelectRotMaskIns64(Base, V, dl, RLAmt2, false, MaskStart, MaskEnd);
2313  }
2314 
2315  void SelectAndParts64(const SDLoc &dl, SDValue &Res, unsigned *InstCnt) {
2317  return;
2318 
2319  // The idea here is the same as in the 32-bit version, but with additional
2320  // complications from the fact that Repl32 might be true. Because we
2321  // aggressively convert bit groups to Repl32 form (which, for small
2322  // rotation factors, involves no other change), and then coalesce, it might
2323  // be the case that a single 64-bit masking operation could handle both
2324  // some Repl32 groups and some non-Repl32 groups. If converting to Repl32
2325  // form allowed coalescing, then we must use a 32-bit rotaton in order to
2326  // completely capture the new combined bit group.
2327 
2328  for (ValueRotInfo &VRI : ValueRotsVec) {
2329  uint64_t Mask = 0;
2330 
2331  // We need to add to the mask all bits from the associated bit groups.
2332  // If Repl32 is false, we need to add bits from bit groups that have
2333  // Repl32 true, but are trivially convertable to Repl32 false. Such a
2334  // group is trivially convertable if it overlaps only with the lower 32
2335  // bits, and the group has not been coalesced.
2336  auto MatchingBG = [VRI](const BitGroup &BG) {
2337  if (VRI.V != BG.V)
2338  return false;
2339 
2340  unsigned EffRLAmt = BG.RLAmt;
2341  if (!VRI.Repl32 && BG.Repl32) {
2342  if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx <= BG.EndIdx &&
2343  !BG.Repl32Coalesced) {
2344  if (BG.Repl32CR)
2345  EffRLAmt += 32;
2346  } else {
2347  return false;
2348  }
2349  } else if (VRI.Repl32 != BG.Repl32) {
2350  return false;
2351  }
2352 
2353  return VRI.RLAmt == EffRLAmt;
2354  };
2355 
2356  for (auto &BG : BitGroups) {
2357  if (!MatchingBG(BG))
2358  continue;
2359 
2360  if (BG.StartIdx <= BG.EndIdx) {
2361  for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i)
2362  Mask |= (UINT64_C(1) << i);
2363  } else {
2364  for (unsigned i = BG.StartIdx; i < Bits.size(); ++i)
2365  Mask |= (UINT64_C(1) << i);
2366  for (unsigned i = 0; i <= BG.EndIdx; ++i)
2367  Mask |= (UINT64_C(1) << i);
2368  }
2369  }
2370 
2371  // We can use the 32-bit andi/andis technique if the mask does not
2372  // require any higher-order bits. This can save an instruction compared
2373  // to always using the general 64-bit technique.
2374  bool Use32BitInsts = isUInt<32>(Mask);
2375  // Compute the masks for andi/andis that would be necessary.
2376  unsigned ANDIMask = (Mask & UINT16_MAX),
2377  ANDISMask = (Mask >> 16) & UINT16_MAX;
2378 
2379  bool NeedsRotate = VRI.RLAmt || (VRI.Repl32 && !isUInt<32>(Mask));
2380 
2381  unsigned NumAndInsts = (unsigned) NeedsRotate +
2382  (unsigned) (bool) Res;
2383  unsigned NumOfSelectInsts = 0;
2384  selectI64Imm(CurDAG, dl, Mask, &NumOfSelectInsts);
2385  assert(NumOfSelectInsts > 0 && "Failed to select an i64 constant.");
2386  if (Use32BitInsts)
2387  NumAndInsts += (unsigned) (ANDIMask != 0) + (unsigned) (ANDISMask != 0) +
2388  (unsigned) (ANDIMask != 0 && ANDISMask != 0);
2389  else
2390  NumAndInsts += NumOfSelectInsts + /* and */ 1;
2391 
2392  unsigned NumRLInsts = 0;
2393  bool FirstBG = true;
2394  bool MoreBG = false;
2395  for (auto &BG : BitGroups) {
2396  if (!MatchingBG(BG)) {
2397  MoreBG = true;
2398  continue;
2399  }
2400  NumRLInsts +=
2401  SelectRotMask64Count(BG.RLAmt, BG.Repl32, BG.StartIdx, BG.EndIdx,
2402  !FirstBG);
2403  FirstBG = false;
2404  }
2405 
2406  LLVM_DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode()
2407  << " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":")
2408  << "\n\t\t\tisel using masking: " << NumAndInsts
2409  << " using rotates: " << NumRLInsts << "\n");
2410 
2411  // When we'd use andi/andis, we bias toward using the rotates (andi only
2412  // has a record form, and is cracked on POWER cores). However, when using
2413  // general 64-bit constant formation, bias toward the constant form,
2414  // because that exposes more opportunities for CSE.
2415  if (NumAndInsts > NumRLInsts)
2416  continue;
2417  // When merging multiple bit groups, instruction or is used.
2418  // But when rotate is used, rldimi can inert the rotated value into any
2419  // register, so instruction or can be avoided.
2420  if ((Use32BitInsts || MoreBG) && NumAndInsts == NumRLInsts)
2421  continue;
2422 
2423  LLVM_DEBUG(dbgs() << "\t\t\t\tusing masking\n");
2424 
2425  if (InstCnt) *InstCnt += NumAndInsts;
2426 
2427  SDValue VRot;
2428  // We actually need to generate a rotation if we have a non-zero rotation
2429  // factor or, in the Repl32 case, if we care about any of the
2430  // higher-order replicated bits. In the latter case, we generate a mask
2431  // backward so that it actually includes the entire 64 bits.
2432  if (VRI.RLAmt || (VRI.Repl32 && !isUInt<32>(Mask)))
2433  VRot = SelectRotMask64(VRI.V, dl, VRI.RLAmt, VRI.Repl32,
2434  VRI.Repl32 ? 31 : 0, VRI.Repl32 ? 30 : 63);
2435  else
2436  VRot = VRI.V;
2437 
2438  SDValue TotalVal;
2439  if (Use32BitInsts) {
2440  assert((ANDIMask != 0 || ANDISMask != 0) &&
2441  "No set bits in mask when using 32-bit ands for 64-bit value");
2442 
2443  SDValue ANDIVal, ANDISVal;
2444  if (ANDIMask != 0)
2445  ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDI8_rec, dl, MVT::i64,
2446  ExtendToInt64(VRot, dl),
2447  getI32Imm(ANDIMask, dl)),
2448  0);
2449  if (ANDISMask != 0)
2450  ANDISVal =
2451  SDValue(CurDAG->getMachineNode(PPC::ANDIS8_rec, dl, MVT::i64,
2452  ExtendToInt64(VRot, dl),
2453  getI32Imm(ANDISMask, dl)),
2454  0);
2455 
2456  if (!ANDIVal)
2457  TotalVal = ANDISVal;
2458  else if (!ANDISVal)
2459  TotalVal = ANDIVal;
2460  else
2461  TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
2462  ExtendToInt64(ANDIVal, dl), ANDISVal), 0);
2463  } else {
2464  TotalVal = SDValue(selectI64Imm(CurDAG, dl, Mask), 0);
2465  TotalVal =
2466  SDValue(CurDAG->getMachineNode(PPC::AND8, dl, MVT::i64,
2467  ExtendToInt64(VRot, dl), TotalVal),
2468  0);
2469  }
2470 
2471  if (!Res)
2472  Res = TotalVal;
2473  else
2474  Res = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
2475  ExtendToInt64(Res, dl), TotalVal),
2476  0);
2477 
2478  // Now, remove all groups with this underlying value and rotation
2479  // factor.
2480  eraseMatchingBitGroups(MatchingBG);
2481  }
2482  }
2483 
2484  // Instruction selection for the 64-bit case.
2485  SDNode *Select64(SDNode *N, bool LateMask, unsigned *InstCnt) {
2486  SDLoc dl(N);
2487  SDValue Res;
2488 
2489  if (InstCnt) *InstCnt = 0;
2490 
2491  // Take care of cases that should use andi/andis first.
2492  SelectAndParts64(dl, Res, InstCnt);
2493 
2494  // If we've not yet selected a 'starting' instruction, and we have no zeros
2495  // to fill in, select the (Value, RLAmt) with the highest priority (largest
2496  // number of groups), and start with this rotated value.
2497  if ((!NeedMask || LateMask) && !Res) {
2498  // If we have both Repl32 groups and non-Repl32 groups, the non-Repl32
2499  // groups will come first, and so the VRI representing the largest number
2500  // of groups might not be first (it might be the first Repl32 groups).
2501  unsigned MaxGroupsIdx = 0;
2502  if (!ValueRotsVec[0].Repl32) {
2503  for (unsigned i = 0, ie = ValueRotsVec.size(); i < ie; ++i)
2504  if (ValueRotsVec[i].Repl32) {
2505  if (ValueRotsVec[i].NumGroups > ValueRotsVec[0].NumGroups)
2506  MaxGroupsIdx = i;
2507  break;
2508  }
2509  }
2510 
2511  ValueRotInfo &VRI = ValueRotsVec[MaxGroupsIdx];
2512  bool NeedsRotate = false;
2513  if (VRI.RLAmt) {
2514  NeedsRotate = true;
2515  } else if (VRI.Repl32) {
2516  for (auto &BG : BitGroups) {
2517  if (BG.V != VRI.V || BG.RLAmt != VRI.RLAmt ||
2518  BG.Repl32 != VRI.Repl32)
2519  continue;
2520 
2521  // We don't need a rotate if the bit group is confined to the lower
2522  // 32 bits.
2523  if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx < BG.EndIdx)
2524  continue;
2525 
2526  NeedsRotate = true;
2527  break;
2528  }
2529  }
2530 
2531  if (NeedsRotate)
2532  Res = SelectRotMask64(VRI.V, dl, VRI.RLAmt, VRI.Repl32,
2533  VRI.Repl32 ? 31 : 0, VRI.Repl32 ? 30 : 63,
2534  InstCnt);
2535  else
2536  Res = VRI.V;
2537 
2538  // Now, remove all groups with this underlying value and rotation factor.
2539  if (Res)
2540  eraseMatchingBitGroups([VRI](const BitGroup &BG) {
2541  return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt &&
2542  BG.Repl32 == VRI.Repl32;
2543  });
2544  }
2545 
2546  // Because 64-bit rotates are more flexible than inserts, we might have a
2547  // preference regarding which one we do first (to save one instruction).
2548  if (!Res)
2549  for (auto I = BitGroups.begin(), IE = BitGroups.end(); I != IE; ++I) {
2550  if (SelectRotMask64Count(I->RLAmt, I->Repl32, I->StartIdx, I->EndIdx,
2551  false) <
2552  SelectRotMask64Count(I->RLAmt, I->Repl32, I->StartIdx, I->EndIdx,
2553  true)) {
2554  if (I != BitGroups.begin()) {
2555  BitGroup BG = *I;
2556  BitGroups.erase(I);
2557  BitGroups.insert(BitGroups.begin(), BG);
2558  }
2559 
2560  break;
2561  }
2562  }
2563 
2564  // Insert the other groups (one at a time).
2565  for (auto &BG : BitGroups) {
2566  if (!Res)
2567  Res = SelectRotMask64(BG.V, dl, BG.RLAmt, BG.Repl32, BG.StartIdx,
2568  BG.EndIdx, InstCnt);
2569  else
2570  Res = SelectRotMaskIns64(Res, BG.V, dl, BG.RLAmt, BG.Repl32,
2571  BG.StartIdx, BG.EndIdx, InstCnt);
2572  }
2573 
2574  if (LateMask) {
2575  uint64_t Mask = getZerosMask();
2576 
2577  // We can use the 32-bit andi/andis technique if the mask does not
2578  // require any higher-order bits. This can save an instruction compared
2579  // to always using the general 64-bit technique.
2580  bool Use32BitInsts = isUInt<32>(Mask);
2581  // Compute the masks for andi/andis that would be necessary.
2582  unsigned ANDIMask = (Mask & UINT16_MAX),
2583  ANDISMask = (Mask >> 16) & UINT16_MAX;
2584 
2585  if (Use32BitInsts) {
2586  assert((ANDIMask != 0 || ANDISMask != 0) &&
2587  "No set bits in mask when using 32-bit ands for 64-bit value");
2588 
2589  if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
2590  (unsigned) (ANDISMask != 0) +
2591  (unsigned) (ANDIMask != 0 && ANDISMask != 0);
2592 
2593  SDValue ANDIVal, ANDISVal;
2594  if (ANDIMask != 0)
2595  ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDI8_rec, dl, MVT::i64,
2596  ExtendToInt64(Res, dl),
2597  getI32Imm(ANDIMask, dl)),
2598  0);
2599  if (ANDISMask != 0)
2600  ANDISVal =
2601  SDValue(CurDAG->getMachineNode(PPC::ANDIS8_rec, dl, MVT::i64,
2602  ExtendToInt64(Res, dl),
2603  getI32Imm(ANDISMask, dl)),
2604  0);
2605 
2606  if (!ANDIVal)
2607  Res = ANDISVal;
2608  else if (!ANDISVal)
2609  Res = ANDIVal;
2610  else
2611  Res = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
2612  ExtendToInt64(ANDIVal, dl), ANDISVal), 0);
2613  } else {
2614  unsigned NumOfSelectInsts = 0;
2615  SDValue MaskVal =
2616  SDValue(selectI64Imm(CurDAG, dl, Mask, &NumOfSelectInsts), 0);
2617  Res = SDValue(CurDAG->getMachineNode(PPC::AND8, dl, MVT::i64,
2618  ExtendToInt64(Res, dl), MaskVal),
2619  0);
2620  if (InstCnt)
2621  *InstCnt += NumOfSelectInsts + /* and */ 1;
2622  }
2623  }
2624 
2625  return Res.getNode();
2626  }
2627 
2628  SDNode *Select(SDNode *N, bool LateMask, unsigned *InstCnt = nullptr) {
2629  // Fill in BitGroups.
2630  collectBitGroups(LateMask);
2631  if (BitGroups.empty())
2632  return nullptr;
2633 
2634  // For 64-bit values, figure out when we can use 32-bit instructions.
2635  if (Bits.size() == 64)
2636  assignRepl32BitGroups();
2637 
2638  // Fill in ValueRotsVec.
2639  collectValueRotInfo();
2640 
2641  if (Bits.size() == 32) {
2642  return Select32(N, LateMask, InstCnt);
2643  } else {
2644  assert(Bits.size() == 64 && "Not 64 bits here?");
2645  return Select64(N, LateMask, InstCnt);
2646  }
2647 
2648  return nullptr;
2649  }
2650 
2651  void eraseMatchingBitGroups(function_ref<bool(const BitGroup &)> F) {
2652  erase_if(BitGroups, F);
2653  }
2654 
2656 
2657  bool NeedMask = false;
2659 
2660  SmallVector<BitGroup, 16> BitGroups;
2661 
2662  DenseMap<std::pair<SDValue, unsigned>, ValueRotInfo> ValueRots;
2663  SmallVector<ValueRotInfo, 16> ValueRotsVec;
2664 
2665  SelectionDAG *CurDAG = nullptr;
2666 
2667 public:
2668  BitPermutationSelector(SelectionDAG *DAG)
2669  : CurDAG(DAG) {}
2670 
2671  // Here we try to match complex bit permutations into a set of
2672  // rotate-and-shift/shift/and/or instructions, using a set of heuristics
2673  // known to produce optimal code for common cases (like i32 byte swapping).
2674  SDNode *Select(SDNode *N) {
2675  Memoizer.clear();
2676  auto Result =
2677  getValueBits(SDValue(N, 0), N->getValueType(0).getSizeInBits());
2678  if (!Result.first)
2679  return nullptr;
2680  Bits = std::move(*Result.second);
2681 
2682  LLVM_DEBUG(dbgs() << "Considering bit-permutation-based instruction"
2683  " selection for: ");
2684  LLVM_DEBUG(N->dump(CurDAG));
2685 
2686  // Fill it RLAmt and set NeedMask.
2687  computeRotationAmounts();
2688 
2689  if (!NeedMask)
2690  return Select(N, false);
2691 
2692  // We currently have two techniques for handling results with zeros: early
2693  // masking (the default) and late masking. Late masking is sometimes more
2694  // efficient, but because the structure of the bit groups is different, it
2695  // is hard to tell without generating both and comparing the results. With
2696  // late masking, we ignore zeros in the resulting value when inserting each
2697  // set of bit groups, and then mask in the zeros at the end. With early
2698  // masking, we only insert the non-zero parts of the result at every step.
2699 
2700  unsigned InstCnt = 0, InstCntLateMask = 0;
2701  LLVM_DEBUG(dbgs() << "\tEarly masking:\n");
2702  SDNode *RN = Select(N, false, &InstCnt);
2703  LLVM_DEBUG(dbgs() << "\t\tisel would use " << InstCnt << " instructions\n");
2704 
2705  LLVM_DEBUG(dbgs() << "\tLate masking:\n");
2706  SDNode *RNLM = Select(N, true, &InstCntLateMask);
2707  LLVM_DEBUG(dbgs() << "\t\tisel would use " << InstCntLateMask
2708  << " instructions\n");
2709 
2710  if (InstCnt <= InstCntLateMask) {
2711  LLVM_DEBUG(dbgs() << "\tUsing early-masking for isel\n");
2712  return RN;
2713  }
2714 
2715  LLVM_DEBUG(dbgs() << "\tUsing late-masking for isel\n");
2716  return RNLM;
2717  }
2718 };
2719 
2720 class IntegerCompareEliminator {
2721  SelectionDAG *CurDAG;
2722  PPCDAGToDAGISel *S;
2723  // Conversion type for interpreting results of a 32-bit instruction as
2724  // a 64-bit value or vice versa.
2725  enum ExtOrTruncConversion { Ext, Trunc };
2726 
2727  // Modifiers to guide how an ISD::SETCC node's result is to be computed
2728  // in a GPR.
2729  // ZExtOrig - use the original condition code, zero-extend value
2730  // ZExtInvert - invert the condition code, zero-extend value
2731  // SExtOrig - use the original condition code, sign-extend value
2732  // SExtInvert - invert the condition code, sign-extend value
2733  enum SetccInGPROpts { ZExtOrig, ZExtInvert, SExtOrig, SExtInvert };
2734 
2735  // Comparisons against zero to emit GPR code sequences for. Each of these
2736  // sequences may need to be emitted for two or more equivalent patterns.
2737  // For example (a >= 0) == (a > -1). The direction of the comparison (</>)
2738  // matters as well as the extension type: sext (-1/0), zext (1/0).
2739  // GEZExt - (zext (LHS >= 0))
2740  // GESExt - (sext (LHS >= 0))
2741  // LEZExt - (zext (LHS <= 0))
2742  // LESExt - (sext (LHS <= 0))
2743  enum ZeroCompare { GEZExt, GESExt, LEZExt, LESExt };
2744 
2745  SDNode *tryEXTEND(SDNode *N);
2746  SDNode *tryLogicOpOfCompares(SDNode *N);
2747  SDValue computeLogicOpInGPR(SDValue LogicOp);
2748  SDValue signExtendInputIfNeeded(SDValue Input);
2749  SDValue zeroExtendInputIfNeeded(SDValue Input);
2750  SDValue addExtOrTrunc(SDValue NatWidthRes, ExtOrTruncConversion Conv);
2751  SDValue getCompoundZeroComparisonInGPR(SDValue LHS, SDLoc dl,
2752  ZeroCompare CmpTy);
2753  SDValue get32BitZExtCompare(SDValue LHS, SDValue RHS, ISD::CondCode CC,
2754  int64_t RHSValue, SDLoc dl);
2755  SDValue get32BitSExtCompare(SDValue LHS, SDValue RHS, ISD::CondCode CC,
2756  int64_t RHSValue, SDLoc dl);
2757  SDValue get64BitZExtCompare(SDValue LHS, SDValue RHS, ISD::CondCode CC,
2758  int64_t RHSValue, SDLoc dl);
2759  SDValue get64BitSExtCompare(SDValue LHS, SDValue RHS, ISD::CondCode CC,
2760  int64_t RHSValue, SDLoc dl);
2761  SDValue getSETCCInGPR(SDValue Compare, SetccInGPROpts ConvOpts);
2762 
2763 public:
2764  IntegerCompareEliminator(SelectionDAG *DAG,
2765  PPCDAGToDAGISel *Sel) : CurDAG(DAG), S(Sel) {
2766  assert(CurDAG->getTargetLoweringInfo()
2767  .getPointerTy(CurDAG->getDataLayout()).getSizeInBits() == 64 &&
2768  "Only expecting to use this on 64 bit targets.");
2769  }
2770  SDNode *Select(SDNode *N) {
2771  if (CmpInGPR == ICGPR_None)
2772  return nullptr;
2773  switch (N->getOpcode()) {
2774  default: break;
2775  case ISD::ZERO_EXTEND:
2776  if (CmpInGPR == ICGPR_Sext || CmpInGPR == ICGPR_SextI32 ||
2778  return nullptr;
2779  [[fallthrough]];
2780  case ISD::SIGN_EXTEND:
2781  if (CmpInGPR == ICGPR_Zext || CmpInGPR == ICGPR_ZextI32 ||
2783  return nullptr;
2784  return tryEXTEND(N);
2785  case ISD::AND:
2786  case ISD::OR:
2787  case ISD::XOR:
2788  return tryLogicOpOfCompares(N);
2789  }
2790  return nullptr;
2791  }
2792 };
2793 
2794 static bool isLogicOp(unsigned Opc) {
2795  return Opc == ISD::AND || Opc == ISD::OR || Opc == ISD::XOR;
2796 }
2797 // The obvious case for wanting to keep the value in a GPR. Namely, the
2798 // result of the comparison is actually needed in a GPR.
2799 SDNode *IntegerCompareEliminator::tryEXTEND(SDNode *N) {
2800  assert((N->getOpcode() == ISD::ZERO_EXTEND ||
2801  N->getOpcode() == ISD::SIGN_EXTEND) &&
2802  "Expecting a zero/sign extend node!");
2803  SDValue WideRes;
2804  // If we are zero-extending the result of a logical operation on i1
2805  // values, we can keep the values in GPRs.
2806  if (isLogicOp(N->getOperand(0).getOpcode()) &&
2807  N->getOperand(0).getValueType() == MVT::i1 &&
2808  N->getOpcode() == ISD::ZERO_EXTEND)
2809  WideRes = computeLogicOpInGPR(N->getOperand(0));
2810  else if (N->getOperand(0).getOpcode() != ISD::SETCC)
2811  return nullptr;
2812  else
2813  WideRes =
2814  getSETCCInGPR(N->getOperand(0),
2815  N->getOpcode() == ISD::SIGN_EXTEND ?
2816  SetccInGPROpts::SExtOrig : SetccInGPROpts::ZExtOrig);
2817 
2818  if (!WideRes)
2819  return nullptr;
2820 
2821  SDLoc dl(N);
2822  bool Input32Bit = WideRes.getValueType() == MVT::i32;
2823  bool Output32Bit = N->getValueType(0) == MVT::i32;
2824 
2825  NumSextSetcc += N->getOpcode() == ISD::SIGN_EXTEND ? 1 : 0;
2826  NumZextSetcc += N->getOpcode() == ISD::SIGN_EXTEND ? 0 : 1;
2827 
2828  SDValue ConvOp = WideRes;
2829  if (Input32Bit != Output32Bit)
2830  ConvOp = addExtOrTrunc(WideRes, Input32Bit ? ExtOrTruncConversion::Ext :
2831  ExtOrTruncConversion::Trunc);
2832  return ConvOp.getNode();
2833 }
2834 
2835 // Attempt to perform logical operations on the results of comparisons while
2836 // keeping the values in GPRs. Without doing so, these would end up being
2837 // lowered to CR-logical operations which suffer from significant latency and
2838 // low ILP.
2839 SDNode *IntegerCompareEliminator::tryLogicOpOfCompares(SDNode *N) {
2840  if (N->getValueType(0) != MVT::i1)
2841  return nullptr;
2842  assert(isLogicOp(N->getOpcode()) &&
2843  "Expected a logic operation on setcc results.");
2844  SDValue LoweredLogical = computeLogicOpInGPR(SDValue(N, 0));
2845  if (!LoweredLogical)
2846  return nullptr;
2847 
2848  SDLoc dl(N);
2849  bool IsBitwiseNegate = LoweredLogical.getMachineOpcode() == PPC::XORI8;
2850  unsigned SubRegToExtract = IsBitwiseNegate ? PPC::sub_eq : PPC::sub_gt;
2851  SDValue CR0Reg = CurDAG->getRegister(PPC::CR0, MVT::i32);
2852  SDValue LHS = LoweredLogical.getOperand(0);
2853  SDValue RHS = LoweredLogical.getOperand(1);
2854  SDValue WideOp;
2855  SDValue OpToConvToRecForm;
2856 
2857  // Look through any 32-bit to 64-bit implicit extend nodes to find the
2858  // opcode that is input to the XORI.
2859  if (IsBitwiseNegate &&
2860  LoweredLogical.getOperand(0).getMachineOpcode() == PPC::INSERT_SUBREG)
2861  OpToConvToRecForm = LoweredLogical.getOperand(0).getOperand(1);
2862  else if (IsBitwiseNegate)
2863  // If the input to the XORI isn't an extension, that's what we're after.
2864  OpToConvToRecForm = LoweredLogical.getOperand(0);
2865  else
2866  // If this is not an XORI, it is a reg-reg logical op and we can convert
2867  // it to record-form.
2868  OpToConvToRecForm = LoweredLogical;
2869 
2870  // Get the record-form version of the node we're looking to use to get the
2871  // CR result from.
2872  uint16_t NonRecOpc = OpToConvToRecForm.getMachineOpcode();
2873  int NewOpc = PPCInstrInfo::getRecordFormOpcode(NonRecOpc);
2874 
2875  // Convert the right node to record-form. This is either the logical we're
2876  // looking at or it is the input node to the negation (if we're looking at
2877  // a bitwise negation).
2878  if (NewOpc != -1 && IsBitwiseNegate) {
2879  // The input to the XORI has a record-form. Use it.
2880  assert(LoweredLogical.getConstantOperandVal(1) == 1 &&
2881  "Expected a PPC::XORI8 only for bitwise negation.");
2882  // Emit the record-form instruction.
2883  std::vector<SDValue> Ops;
2884  for (int i = 0, e = OpToConvToRecForm.getNumOperands(); i < e; i++)
2885  Ops.push_back(OpToConvToRecForm.getOperand(i));
2886 
2887  WideOp =
2888  SDValue(CurDAG->getMachineNode(NewOpc, dl,
2889  OpToConvToRecForm.getValueType(),
2890  MVT::Glue, Ops), 0);
2891  } else {
2892  assert((NewOpc != -1 || !IsBitwiseNegate) &&
2893  "No record form available for AND8/OR8/XOR8?");
2894  WideOp =
2895  SDValue(CurDAG->getMachineNode(NewOpc == -1 ? PPC::ANDI8_rec : NewOpc,
2896  dl, MVT::i64, MVT::Glue, LHS, RHS),
2897  0);
2898  }
2899 
2900  // Select this node to a single bit from CR0 set by the record-form node
2901  // just created. For bitwise negation, use the EQ bit which is the equivalent
2902  // of negating the result (i.e. it is a bit set when the result of the
2903  // operation is zero).
2904  SDValue SRIdxVal =
2905  CurDAG->getTargetConstant(SubRegToExtract, dl, MVT::i32);
2906  SDValue CRBit =
2907  SDValue(CurDAG->getMachineNode(TargetOpcode::EXTRACT_SUBREG, dl,
2908  MVT::i1, CR0Reg, SRIdxVal,
2909  WideOp.getValue(1)), 0);
2910  return CRBit.getNode();
2911 }
2912 
2913 // Lower a logical operation on i1 values into a GPR sequence if possible.
2914 // The result can be kept in a GPR if requested.
2915 // Three types of inputs can be handled:
2916 // - SETCC
2917 // - TRUNCATE
2918 // - Logical operation (AND/OR/XOR)
2919 // There is also a special case that is handled (namely a complement operation
2920 // achieved with xor %a, -1).
2921 SDValue IntegerCompareEliminator::computeLogicOpInGPR(SDValue LogicOp) {
2922  assert(isLogicOp(LogicOp.getOpcode()) &&
2923  "Can only handle logic operations here.");
2924  assert(LogicOp.getValueType() == MVT::i1 &&
2925  "Can only handle logic operations on i1 values here.");
2926  SDLoc dl(LogicOp);
2927  SDValue LHS, RHS;
2928 
2929  // Special case: xor %a, -1
2930  bool IsBitwiseNegation = isBitwiseNot(LogicOp);
2931 
2932  // Produces a GPR sequence for each operand of the binary logic operation.
2933  // For SETCC, it produces the respective comparison, for TRUNCATE it truncates
2934  // the value in a GPR and for logic operations, it will recursively produce
2935  // a GPR sequence for the operation.
2936  auto getLogicOperand = [&] (SDValue Operand) -> SDValue {
2937  unsigned OperandOpcode = Operand.getOpcode();
2938  if (OperandOpcode == ISD::SETCC)
2939  return getSETCCInGPR(Operand, SetccInGPROpts::ZExtOrig);
2940  else if (OperandOpcode == ISD::TRUNCATE) {
2941  SDValue InputOp = Operand.getOperand(0);
2942  EVT InVT = InputOp.getValueType();
2943  return SDValue(CurDAG->getMachineNode(InVT == MVT::i32 ? PPC::RLDICL_32 :
2944  PPC::RLDICL, dl, InVT, InputOp,
2945  S->getI64Imm(0, dl),
2946  S->getI64Imm(63, dl)), 0);
2947  } else if (isLogicOp(OperandOpcode))
2948  return computeLogicOpInGPR(Operand);
2949  return SDValue();
2950  };
2951  LHS = getLogicOperand(LogicOp.getOperand(0));
2952  RHS = getLogicOperand(LogicOp.getOperand(1));
2953 
2954  // If a GPR sequence can't be produced for the LHS we can't proceed.
2955  // Not producing a GPR sequence for the RHS is only a problem if this isn't
2956  // a bitwise negation operation.
2957  if (!LHS || (!RHS && !IsBitwiseNegation))
2958  return SDValue();
2959 
2960  NumLogicOpsOnComparison++;
2961 
2962  // We will use the inputs as 64-bit values.
2963  if (LHS.getValueType() == MVT::i32)
2964  LHS = addExtOrTrunc(LHS, ExtOrTruncConversion::Ext);
2965  if (!IsBitwiseNegation && RHS.getValueType() == MVT::i32)
2966  RHS = addExtOrTrunc(RHS, ExtOrTruncConversion::Ext);
2967 
2968  unsigned NewOpc;
2969  switch (LogicOp.getOpcode()) {
2970  default: llvm_unreachable("Unknown logic operation.");
2971  case ISD::AND: NewOpc = PPC::AND8; break;
2972  case ISD::OR: NewOpc = PPC::OR8; break;
2973  case ISD::XOR: NewOpc = PPC::XOR8; break;
2974  }
2975 
2976  if (IsBitwiseNegation) {
2977  RHS = S->getI64Imm(1, dl);
2978  NewOpc = PPC::XORI8;
2979  }
2980 
2981  return SDValue(CurDAG->getMachineNode(NewOpc, dl, MVT::i64, LHS, RHS), 0);
2982 
2983 }
2984 
2985 /// If the value isn't guaranteed to be sign-extended to 64-bits, extend it.
2986 /// Otherwise just reinterpret it as a 64-bit value.
2987 /// Useful when emitting comparison code for 32-bit values without using
2988 /// the compare instruction (which only considers the lower 32-bits).
2989 SDValue IntegerCompareEliminator::signExtendInputIfNeeded(SDValue Input) {
2990  assert(Input.getValueType() == MVT::i32 &&
2991  "Can only sign-extend 32-bit values here.");
2992  unsigned Opc = Input.getOpcode();
2993 
2994  // The value was sign extended and then truncated to 32-bits. No need to
2995  // sign extend it again.
2996  if (Opc == ISD::TRUNCATE &&
2997  (Input.getOperand(0).getOpcode() == ISD::AssertSext ||
2998  Input.getOperand(0).getOpcode() == ISD::SIGN_EXTEND))
2999  return addExtOrTrunc(Input, ExtOrTruncConversion::Ext);
3000 
3001  LoadSDNode *InputLoad = dyn_cast<LoadSDNode>(Input);
3002  // The input is a sign-extending load. All ppc sign-extending loads
3003  // sign-extend to the full 64-bits.
3004  if (InputLoad && InputLoad->getExtensionType() == ISD::SEXTLOAD)
3005  return addExtOrTrunc(Input, ExtOrTruncConversion::Ext);
3006 
3007  ConstantSDNode *InputConst = dyn_cast<ConstantSDNode>(Input);
3008  // We don't sign-extend constants.
3009  if (InputConst)
3010  return addExtOrTrunc(Input, ExtOrTruncConversion::Ext);
3011 
3012  SDLoc dl(Input);
3013  SignExtensionsAdded++;
3014  return SDValue(CurDAG->getMachineNode(PPC::EXTSW_32_64, dl,
3015  MVT::i64, Input), 0);
3016 }
3017 
3018 /// If the value isn't guaranteed to be zero-extended to 64-bits, extend it.
3019 /// Otherwise just reinterpret it as a 64-bit value.
3020 /// Useful when emitting comparison code for 32-bit values without using
3021 /// the compare instruction (which only considers the lower 32-bits).
3022 SDValue IntegerCompareEliminator::zeroExtendInputIfNeeded(SDValue Input) {
3023  assert(Input.getValueType() == MVT::i32 &&
3024  "Can only zero-extend 32-bit values here.");
3025  unsigned Opc = Input.getOpcode();
3026 
3027  // The only condition under which we can omit the actual extend instruction:
3028  // - The value is a positive constant
3029  // - The value comes from a load that isn't a sign-extending load
3030  // An ISD::TRUNCATE needs to be zero-extended unless it is fed by a zext.
3031  bool IsTruncateOfZExt = Opc == ISD::TRUNCATE &&
3032  (Input.getOperand(0).getOpcode() == ISD::AssertZext ||
3033  Input.getOperand(0).getOpcode() == ISD::ZERO_EXTEND);
3034  if (IsTruncateOfZExt)
3035  return addExtOrTrunc(Input, ExtOrTruncConversion::Ext);
3036 
3037  ConstantSDNode *InputConst = dyn_cast<ConstantSDNode>(Input);
3038  if (InputConst && InputConst->getSExtValue() >= 0)
3039  return addExtOrTrunc(Input, ExtOrTruncConversion::Ext);
3040 
3041  LoadSDNode *InputLoad = dyn_cast<LoadSDNode>(Input);
3042  // The input is a load that doesn't sign-extend (it will be zero-extended).
3043  if (InputLoad && InputLoad->getExtensionType() != ISD::SEXTLOAD)
3044  return addExtOrTrunc(Input, ExtOrTruncConversion::Ext);
3045 
3046  // None of the above, need to zero-extend.
3047  SDLoc dl(Input);
3048  ZeroExtensionsAdded++;
3049  return SDValue(CurDAG->getMachineNode(PPC::RLDICL_32_64, dl, MVT::i64, Input,
3050  S->getI64Imm(0, dl),
3051  S->getI64Imm(32, dl)), 0);
3052 }
3053 
3054 // Handle a 32-bit value in a 64-bit register and vice-versa. These are of
3055 // course not actual zero/sign extensions that will generate machine code,
3056 // they're just a way to reinterpret a 32 bit value in a register as a
3057 // 64 bit value and vice-versa.
3058 SDValue IntegerCompareEliminator::addExtOrTrunc(SDValue NatWidthRes,
3059  ExtOrTruncConversion Conv) {
3060  SDLoc dl(NatWidthRes);
3061 
3062  // For reinterpreting 32-bit values as 64 bit values, we generate
3063  // INSERT_SUBREG IMPLICIT_DEF:i64, <input>, TargetConstant:i32<1>
3064  if (Conv == ExtOrTruncConversion::Ext) {
3065  SDValue ImDef(CurDAG->getMachineNode(PPC::IMPLICIT_DEF, dl, MVT::i64), 0);
3066  SDValue SubRegIdx =
3067  CurDAG->getTargetConstant(PPC::sub_32, dl, MVT::i32);
3068  return SDValue(CurDAG->getMachineNode(PPC::INSERT_SUBREG, dl, MVT::i64,
3069  ImDef, NatWidthRes, SubRegIdx), 0);
3070  }
3071 
3072  assert(Conv == ExtOrTruncConversion::Trunc &&
3073  "Unknown convertion between 32 and 64 bit values.");
3074  // For reinterpreting 64-bit values as 32-bit values, we just need to
3075  // EXTRACT_SUBREG (i.e. extract the low word).
3076  SDValue SubRegIdx =
3077  CurDAG->getTargetConstant(PPC::sub_32, dl, MVT::i32);
3078  return SDValue(CurDAG->getMachineNode(PPC::EXTRACT_SUBREG, dl, MVT::i32,
3079  NatWidthRes, SubRegIdx), 0);
3080 }
3081 
3082 // Produce a GPR sequence for compound comparisons (<=, >=) against zero.
3083 // Handle both zero-extensions and sign-extensions.
3084 SDValue
3085 IntegerCompareEliminator::getCompoundZeroComparisonInGPR(SDValue LHS, SDLoc dl,
3086  ZeroCompare CmpTy) {
3087  EVT InVT = LHS.getValueType();
3088  bool Is32Bit = InVT == MVT::i32;
3089  SDValue ToExtend;
3090 
3091  // Produce the value that needs to be either zero or sign extended.
3092  switch (CmpTy) {
3093  case ZeroCompare::GEZExt:
3094  case ZeroCompare::GESExt:
3095  ToExtend = SDValue(CurDAG->getMachineNode(Is32Bit ? PPC::NOR : PPC::NOR8,
3096  dl, InVT, LHS, LHS), 0);
3097  break;
3098  case ZeroCompare::LEZExt:
3099  case ZeroCompare::LESExt: {
3100  if (Is32Bit) {
3101  // Upper 32 bits cannot be undefined for this sequence.
3102  LHS = signExtendInputIfNeeded(LHS);
3103  SDValue Neg =
3104  SDValue(CurDAG->getMachineNode(PPC::NEG8, dl, MVT::i64, LHS), 0);
3105  ToExtend =
3106  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3107  Neg, S->getI64Imm(1, dl),
3108  S->getI64Imm(63, dl)), 0);
3109  } else {
3110  SDValue Addi =
3111  SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64, LHS,
3112  S->getI64Imm(~0ULL, dl)), 0);
3113  ToExtend = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
3114  Addi, LHS), 0);
3115  }
3116  break;
3117  }
3118  }
3119 
3120  // For 64-bit sequences, the extensions are the same for the GE/LE cases.
3121  if (!Is32Bit &&
3122  (CmpTy == ZeroCompare::GEZExt || CmpTy == ZeroCompare::LEZExt))
3123  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3124  ToExtend, S->getI64Imm(1, dl),
3125  S->getI64Imm(63, dl)), 0);
3126  if (!Is32Bit &&
3127  (CmpTy == ZeroCompare::GESExt || CmpTy == ZeroCompare::LESExt))
3128  return SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, ToExtend,
3129  S->getI64Imm(63, dl)), 0);
3130 
3131  assert(Is32Bit && "Should have handled the 32-bit sequences above.");
3132  // For 32-bit sequences, the extensions differ between GE/LE cases.
3133  switch (CmpTy) {
3134  case ZeroCompare::GEZExt: {
3135  SDValue ShiftOps[] = { ToExtend, S->getI32Imm(1, dl), S->getI32Imm(31, dl),
3136  S->getI32Imm(31, dl) };
3137  return SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
3138  ShiftOps), 0);
3139  }
3140  case ZeroCompare::GESExt:
3141  return SDValue(CurDAG->getMachineNode(PPC::SRAWI, dl, MVT::i32, ToExtend,
3142  S->getI32Imm(31, dl)), 0);
3143  case ZeroCompare::LEZExt:
3144  return SDValue(CurDAG->getMachineNode(PPC::XORI8, dl, MVT::i64, ToExtend,
3145  S->getI32Imm(1, dl)), 0);
3146  case ZeroCompare::LESExt:
3147  return SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64, ToExtend,
3148  S->getI32Imm(-1, dl)), 0);
3149  }
3150 
3151  // The above case covers all the enumerators so it can't have a default clause
3152  // to avoid compiler warnings.
3153  llvm_unreachable("Unknown zero-comparison type.");
3154 }
3155 
3156 /// Produces a zero-extended result of comparing two 32-bit values according to
3157 /// the passed condition code.
3158 SDValue
3159 IntegerCompareEliminator::get32BitZExtCompare(SDValue LHS, SDValue RHS,
3160  ISD::CondCode CC,
3161  int64_t RHSValue, SDLoc dl) {
3162  if (CmpInGPR == ICGPR_I64 || CmpInGPR == ICGPR_SextI64 ||
3164  return SDValue();
3165  bool IsRHSZero = RHSValue == 0;
3166  bool IsRHSOne = RHSValue == 1;
3167  bool IsRHSNegOne = RHSValue == -1LL;
3168  switch (CC) {
3169  default: return SDValue();
3170  case ISD::SETEQ: {
3171  // (zext (setcc %a, %b, seteq)) -> (lshr (cntlzw (xor %a, %b)), 5)
3172  // (zext (setcc %a, 0, seteq)) -> (lshr (cntlzw %a), 5)
3173  SDValue Xor = IsRHSZero ? LHS :
3174  SDValue(CurDAG->getMachineNode(PPC::XOR, dl, MVT::i32, LHS, RHS), 0);
3175  SDValue Clz =
3176  SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Xor), 0);
3177  SDValue ShiftOps[] = { Clz, S->getI32Imm(27, dl), S->getI32Imm(5, dl),
3178  S->getI32Imm(31, dl) };
3179  return SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
3180  ShiftOps), 0);
3181  }
3182  case ISD::SETNE: {
3183  // (zext (setcc %a, %b, setne)) -> (xor (lshr (cntlzw (xor %a, %b)), 5), 1)
3184  // (zext (setcc %a, 0, setne)) -> (xor (lshr (cntlzw %a), 5), 1)
3185  SDValue Xor = IsRHSZero ? LHS :
3186  SDValue(CurDAG->getMachineNode(PPC::XOR, dl, MVT::i32, LHS, RHS), 0);
3187  SDValue Clz =
3188  SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Xor), 0);
3189  SDValue ShiftOps[] = { Clz, S->getI32Imm(27, dl), S->getI32Imm(5, dl),
3190  S->getI32Imm(31, dl) };
3191  SDValue Shift =
3192  SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, ShiftOps), 0);
3193  return SDValue(CurDAG->getMachineNode(PPC::XORI, dl, MVT::i32, Shift,
3194  S->getI32Imm(1, dl)), 0);
3195  }
3196  case ISD::SETGE: {
3197  // (zext (setcc %a, %b, setge)) -> (xor (lshr (sub %a, %b), 63), 1)
3198  // (zext (setcc %a, 0, setge)) -> (lshr (~ %a), 31)
3199  if(IsRHSZero)
3200  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GEZExt);
3201 
3202  // Not a special case (i.e. RHS == 0). Handle (%a >= %b) as (%b <= %a)
3203  // by swapping inputs and falling through.
3204  std::swap(LHS, RHS);
3205  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3206  IsRHSZero = RHSConst && RHSConst->isZero();
3207  [[fallthrough]];
3208  }
3209  case ISD::SETLE: {
3210  if (CmpInGPR == ICGPR_NonExtIn)
3211  return SDValue();
3212  // (zext (setcc %a, %b, setle)) -> (xor (lshr (sub %b, %a), 63), 1)
3213  // (zext (setcc %a, 0, setle)) -> (xor (lshr (- %a), 63), 1)
3214  if(IsRHSZero) {
3215  if (CmpInGPR == ICGPR_NonExtIn)
3216  return SDValue();
3217  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LEZExt);
3218  }
3219 
3220  // The upper 32-bits of the register can't be undefined for this sequence.
3221  LHS = signExtendInputIfNeeded(LHS);
3222  RHS = signExtendInputIfNeeded(RHS);
3223  SDValue Sub =
3224  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, LHS, RHS), 0);
3225  SDValue Shift =
3226  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Sub,
3227  S->getI64Imm(1, dl), S->getI64Imm(63, dl)),
3228  0);
3229  return
3230  SDValue(CurDAG->getMachineNode(PPC::XORI8, dl,
3231  MVT::i64, Shift, S->getI32Imm(1, dl)), 0);
3232  }
3233  case ISD::SETGT: {
3234  // (zext (setcc %a, %b, setgt)) -> (lshr (sub %b, %a), 63)
3235  // (zext (setcc %a, -1, setgt)) -> (lshr (~ %a), 31)
3236  // (zext (setcc %a, 0, setgt)) -> (lshr (- %a), 63)
3237  // Handle SETLT -1 (which is equivalent to SETGE 0).
3238  if (IsRHSNegOne)
3239  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GEZExt);
3240 
3241  if (IsRHSZero) {
3242  if (CmpInGPR == ICGPR_NonExtIn)
3243  return SDValue();
3244  // The upper 32-bits of the register can't be undefined for this sequence.
3245  LHS = signExtendInputIfNeeded(LHS);
3246  RHS = signExtendInputIfNeeded(RHS);
3247  SDValue Neg =
3248  SDValue(CurDAG->getMachineNode(PPC::NEG8, dl, MVT::i64, LHS), 0);
3249  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3250  Neg, S->getI32Imm(1, dl), S->getI32Imm(63, dl)), 0);
3251  }
3252  // Not a special case (i.e. RHS == 0 or RHS == -1). Handle (%a > %b) as
3253  // (%b < %a) by swapping inputs and falling through.
3254  std::swap(LHS, RHS);
3255  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3256  IsRHSZero = RHSConst && RHSConst->isZero();
3257  IsRHSOne = RHSConst && RHSConst->getSExtValue() == 1;
3258  [[fallthrough]];
3259  }
3260  case ISD::SETLT: {
3261  // (zext (setcc %a, %b, setlt)) -> (lshr (sub %a, %b), 63)
3262  // (zext (setcc %a, 1, setlt)) -> (xor (lshr (- %a), 63), 1)
3263  // (zext (setcc %a, 0, setlt)) -> (lshr %a, 31)
3264  // Handle SETLT 1 (which is equivalent to SETLE 0).
3265  if (IsRHSOne) {
3266  if (CmpInGPR == ICGPR_NonExtIn)
3267  return SDValue();
3268  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LEZExt);
3269  }
3270 
3271  if (IsRHSZero) {
3272  SDValue ShiftOps[] = { LHS, S->getI32Imm(1, dl), S->getI32Imm(31, dl),
3273  S->getI32Imm(31, dl) };
3274  return SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
3275  ShiftOps), 0);
3276  }
3277 
3278  if (CmpInGPR == ICGPR_NonExtIn)
3279  return SDValue();
3280  // The upper 32-bits of the register can't be undefined for this sequence.
3281  LHS = signExtendInputIfNeeded(LHS);
3282  RHS = signExtendInputIfNeeded(RHS);
3283  SDValue SUBFNode =
3284  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, RHS, LHS), 0);
3285  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3286  SUBFNode, S->getI64Imm(1, dl),
3287  S->getI64Imm(63, dl)), 0);
3288  }
3289  case ISD::SETUGE:
3290  // (zext (setcc %a, %b, setuge)) -> (xor (lshr (sub %b, %a), 63), 1)
3291  // (zext (setcc %a, %b, setule)) -> (xor (lshr (sub %a, %b), 63), 1)
3292  std::swap(LHS, RHS);
3293  [[fallthrough]];
3294  case ISD::SETULE: {
3295  if (CmpInGPR == ICGPR_NonExtIn)
3296  return SDValue();
3297  // The upper 32-bits of the register can't be undefined for this sequence.
3298  LHS = zeroExtendInputIfNeeded(LHS);
3299  RHS = zeroExtendInputIfNeeded(RHS);
3300  SDValue Subtract =
3301  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, LHS, RHS), 0);
3302  SDValue SrdiNode =
3303  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3304  Subtract, S->getI64Imm(1, dl),
3305  S->getI64Imm(63, dl)), 0);
3306  return SDValue(CurDAG->getMachineNode(PPC::XORI8, dl, MVT::i64, SrdiNode,
3307  S->getI32Imm(1, dl)), 0);
3308  }
3309  case ISD::SETUGT:
3310  // (zext (setcc %a, %b, setugt)) -> (lshr (sub %b, %a), 63)
3311  // (zext (setcc %a, %b, setult)) -> (lshr (sub %a, %b), 63)
3312  std::swap(LHS, RHS);
3313  [[fallthrough]];
3314  case ISD::SETULT: {
3315  if (CmpInGPR == ICGPR_NonExtIn)
3316  return SDValue();
3317  // The upper 32-bits of the register can't be undefined for this sequence.
3318  LHS = zeroExtendInputIfNeeded(LHS);
3319  RHS = zeroExtendInputIfNeeded(RHS);
3320  SDValue Subtract =
3321  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, RHS, LHS), 0);
3322  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3323  Subtract, S->getI64Imm(1, dl),
3324  S->getI64Imm(63, dl)), 0);
3325  }
3326  }
3327 }
3328 
3329 /// Produces a sign-extended result of comparing two 32-bit values according to
3330 /// the passed condition code.
3331 SDValue
3332 IntegerCompareEliminator::get32BitSExtCompare(SDValue LHS, SDValue RHS,
3333  ISD::CondCode CC,
3334  int64_t RHSValue, SDLoc dl) {
3335  if (CmpInGPR == ICGPR_I64 || CmpInGPR == ICGPR_SextI64 ||
3337  return SDValue();
3338  bool IsRHSZero = RHSValue == 0;
3339  bool IsRHSOne = RHSValue == 1;
3340  bool IsRHSNegOne = RHSValue == -1LL;
3341 
3342  switch (CC) {
3343  default: return SDValue();
3344  case ISD::SETEQ: {
3345  // (sext (setcc %a, %b, seteq)) ->
3346  // (ashr (shl (ctlz (xor %a, %b)), 58), 63)
3347  // (sext (setcc %a, 0, seteq)) ->
3348  // (ashr (shl (ctlz %a), 58), 63)
3349  SDValue CountInput = IsRHSZero ? LHS :
3350  SDValue(CurDAG->getMachineNode(PPC::XOR, dl, MVT::i32, LHS, RHS), 0);
3351  SDValue Cntlzw =
3352  SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, CountInput), 0);
3353  SDValue SHLOps[] = { Cntlzw, S->getI32Imm(27, dl),
3354  S->getI32Imm(5, dl), S->getI32Imm(31, dl) };
3355  SDValue Slwi =
3356  SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, SHLOps), 0);
3357  return SDValue(CurDAG->getMachineNode(PPC::NEG, dl, MVT::i32, Slwi), 0);
3358  }
3359  case ISD::SETNE: {
3360  // Bitwise xor the operands, count leading zeros, shift right by 5 bits and
3361  // flip the bit, finally take 2's complement.
3362  // (sext (setcc %a, %b, setne)) ->
3363  // (neg (xor (lshr (ctlz (xor %a, %b)), 5), 1))
3364  // Same as above, but the first xor is not needed.
3365  // (sext (setcc %a, 0, setne)) ->
3366  // (neg (xor (lshr (ctlz %a), 5), 1))
3367  SDValue Xor = IsRHSZero ? LHS :
3368  SDValue(CurDAG->getMachineNode(PPC::XOR, dl, MVT::i32, LHS, RHS), 0);
3369  SDValue Clz =
3370  SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Xor), 0);
3371  SDValue ShiftOps[] =
3372  { Clz, S->getI32Imm(27, dl), S->getI32Imm(5, dl), S->getI32Imm(31, dl) };
3373  SDValue Shift =
3374  SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, ShiftOps), 0);
3375  SDValue Xori =
3376  SDValue(CurDAG->getMachineNode(PPC::XORI, dl, MVT::i32, Shift,
3377  S->getI32Imm(1, dl)), 0);
3378  return SDValue(CurDAG->getMachineNode(PPC::NEG, dl, MVT::i32, Xori), 0);
3379  }
3380  case ISD::SETGE: {
3381  // (sext (setcc %a, %b, setge)) -> (add (lshr (sub %a, %b), 63), -1)
3382  // (sext (setcc %a, 0, setge)) -> (ashr (~ %a), 31)
3383  if (IsRHSZero)
3384  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GESExt);
3385 
3386  // Not a special case (i.e. RHS == 0). Handle (%a >= %b) as (%b <= %a)
3387  // by swapping inputs and falling through.
3388  std::swap(LHS, RHS);
3389  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3390  IsRHSZero = RHSConst && RHSConst->isZero();
3391  [[fallthrough]];
3392  }
3393  case ISD::SETLE: {
3394  if (CmpInGPR == ICGPR_NonExtIn)
3395  return SDValue();
3396  // (sext (setcc %a, %b, setge)) -> (add (lshr (sub %b, %a), 63), -1)
3397  // (sext (setcc %a, 0, setle)) -> (add (lshr (- %a), 63), -1)
3398  if (IsRHSZero)
3399  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LESExt);
3400 
3401  // The upper 32-bits of the register can't be undefined for this sequence.
3402  LHS = signExtendInputIfNeeded(LHS);
3403  RHS = signExtendInputIfNeeded(RHS);
3404  SDValue SUBFNode =
3405  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, MVT::Glue,
3406  LHS, RHS), 0);
3407  SDValue Srdi =
3408  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3409  SUBFNode, S->getI64Imm(1, dl),
3410  S->getI64Imm(63, dl)), 0);
3411  return SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64, Srdi,
3412  S->getI32Imm(-1, dl)), 0);
3413  }
3414  case ISD::SETGT: {
3415  // (sext (setcc %a, %b, setgt)) -> (ashr (sub %b, %a), 63)
3416  // (sext (setcc %a, -1, setgt)) -> (ashr (~ %a), 31)
3417  // (sext (setcc %a, 0, setgt)) -> (ashr (- %a), 63)
3418  if (IsRHSNegOne)
3419  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GESExt);
3420  if (IsRHSZero) {
3421  if (CmpInGPR == ICGPR_NonExtIn)
3422  return SDValue();
3423  // The upper 32-bits of the register can't be undefined for this sequence.
3424  LHS = signExtendInputIfNeeded(LHS);
3425  RHS = signExtendInputIfNeeded(RHS);
3426  SDValue Neg =
3427  SDValue(CurDAG->getMachineNode(PPC::NEG8, dl, MVT::i64, LHS), 0);
3428  return SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, Neg,
3429  S->getI64Imm(63, dl)), 0);
3430  }
3431  // Not a special case (i.e. RHS == 0 or RHS == -1). Handle (%a > %b) as
3432  // (%b < %a) by swapping inputs and falling through.
3433  std::swap(LHS, RHS);
3434  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3435  IsRHSZero = RHSConst && RHSConst->isZero();
3436  IsRHSOne = RHSConst && RHSConst->getSExtValue() == 1;
3437  [[fallthrough]];
3438  }
3439  case ISD::SETLT: {
3440  // (sext (setcc %a, %b, setgt)) -> (ashr (sub %a, %b), 63)
3441  // (sext (setcc %a, 1, setgt)) -> (add (lshr (- %a), 63), -1)
3442  // (sext (setcc %a, 0, setgt)) -> (ashr %a, 31)
3443  if (IsRHSOne) {
3444  if (CmpInGPR == ICGPR_NonExtIn)
3445  return SDValue();
3446  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LESExt);
3447  }
3448  if (IsRHSZero)
3449  return SDValue(CurDAG->getMachineNode(PPC::SRAWI, dl, MVT::i32, LHS,
3450  S->getI32Imm(31, dl)), 0);
3451 
3452  if (CmpInGPR == ICGPR_NonExtIn)
3453  return SDValue();
3454  // The upper 32-bits of the register can't be undefined for this sequence.
3455  LHS = signExtendInputIfNeeded(LHS);
3456  RHS = signExtendInputIfNeeded(RHS);
3457  SDValue SUBFNode =
3458  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, RHS, LHS), 0);
3459  return SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64,
3460  SUBFNode, S->getI64Imm(63, dl)), 0);
3461  }
3462  case ISD::SETUGE:
3463  // (sext (setcc %a, %b, setuge)) -> (add (lshr (sub %a, %b), 63), -1)
3464  // (sext (setcc %a, %b, setule)) -> (add (lshr (sub %b, %a), 63), -1)
3465  std::swap(LHS, RHS);
3466  [[fallthrough]];
3467  case ISD::SETULE: {
3468  if (CmpInGPR == ICGPR_NonExtIn)
3469  return SDValue();
3470  // The upper 32-bits of the register can't be undefined for this sequence.
3471  LHS = zeroExtendInputIfNeeded(LHS);
3472  RHS = zeroExtendInputIfNeeded(RHS);
3473  SDValue Subtract =
3474  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, LHS, RHS), 0);
3475  SDValue Shift =
3476  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Subtract,
3477  S->getI32Imm(1, dl), S->getI32Imm(63,dl)),
3478  0);
3479  return SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64, Shift,
3480  S->getI32Imm(-1, dl)), 0);
3481  }
3482  case ISD::SETUGT:
3483  // (sext (setcc %a, %b, setugt)) -> (ashr (sub %b, %a), 63)
3484  // (sext (setcc %a, %b, setugt)) -> (ashr (sub %a, %b), 63)
3485  std::swap(LHS, RHS);
3486  [[fallthrough]];
3487  case ISD::SETULT: {
3488  if (CmpInGPR == ICGPR_NonExtIn)
3489  return SDValue();
3490  // The upper 32-bits of the register can't be undefined for this sequence.
3491  LHS = zeroExtendInputIfNeeded(LHS);
3492  RHS = zeroExtendInputIfNeeded(RHS);
3493  SDValue Subtract =
3494  SDValue(CurDAG->getMachineNode(PPC::SUBF8, dl, MVT::i64, RHS, LHS), 0);
3495  return SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64,
3496  Subtract, S->getI64Imm(63, dl)), 0);
3497  }
3498  }
3499 }
3500 
3501 /// Produces a zero-extended result of comparing two 64-bit values according to
3502 /// the passed condition code.
3503 SDValue
3504 IntegerCompareEliminator::get64BitZExtCompare(SDValue LHS, SDValue RHS,
3505  ISD::CondCode CC,
3506  int64_t RHSValue, SDLoc dl) {
3507  if (CmpInGPR == ICGPR_I32 || CmpInGPR == ICGPR_SextI32 ||
3509  return SDValue();
3510  bool IsRHSZero = RHSValue == 0;
3511  bool IsRHSOne = RHSValue == 1;
3512  bool IsRHSNegOne = RHSValue == -1LL;
3513  switch (CC) {
3514  default: return SDValue();
3515  case ISD::SETEQ: {
3516  // (zext (setcc %a, %b, seteq)) -> (lshr (ctlz (xor %a, %b)), 6)
3517  // (zext (setcc %a, 0, seteq)) -> (lshr (ctlz %a), 6)
3518  SDValue Xor = IsRHSZero ? LHS :
3519  SDValue(CurDAG->getMachineNode(PPC::XOR8, dl, MVT::i64, LHS, RHS), 0);
3520  SDValue Clz =
3521  SDValue(CurDAG->getMachineNode(PPC::CNTLZD, dl, MVT::i64, Xor), 0);
3522  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Clz,
3523  S->getI64Imm(58, dl),
3524  S->getI64Imm(63, dl)), 0);
3525  }
3526  case ISD::SETNE: {
3527  // {addc.reg, addc.CA} = (addcarry (xor %a, %b), -1)
3528  // (zext (setcc %a, %b, setne)) -> (sube addc.reg, addc.reg, addc.CA)
3529  // {addcz.reg, addcz.CA} = (addcarry %a, -1)
3530  // (zext (setcc %a, 0, setne)) -> (sube addcz.reg, addcz.reg, addcz.CA)
3531  SDValue Xor = IsRHSZero ? LHS :
3532  SDValue(CurDAG->getMachineNode(PPC::XOR8, dl, MVT::i64, LHS, RHS), 0);
3533  SDValue AC =
3534  SDValue(CurDAG->getMachineNode(PPC::ADDIC8, dl, MVT::i64, MVT::Glue,
3535  Xor, S->getI32Imm(~0U, dl)), 0);
3536  return SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64, AC,
3537  Xor, AC.getValue(1)), 0);
3538  }
3539  case ISD::SETGE: {
3540  // {subc.reg, subc.CA} = (subcarry %a, %b)
3541  // (zext (setcc %a, %b, setge)) ->
3542  // (adde (lshr %b, 63), (ashr %a, 63), subc.CA)
3543  // (zext (setcc %a, 0, setge)) -> (lshr (~ %a), 63)
3544  if (IsRHSZero)
3545  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GEZExt);
3546  std::swap(LHS, RHS);
3547  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3548  IsRHSZero = RHSConst && RHSConst->isZero();
3549  [[fallthrough]];
3550  }
3551  case ISD::SETLE: {
3552  // {subc.reg, subc.CA} = (subcarry %b, %a)
3553  // (zext (setcc %a, %b, setge)) ->
3554  // (adde (lshr %a, 63), (ashr %b, 63), subc.CA)
3555  // (zext (setcc %a, 0, setge)) -> (lshr (or %a, (add %a, -1)), 63)
3556  if (IsRHSZero)
3557  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LEZExt);
3558  SDValue ShiftL =
3559  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, LHS,
3560  S->getI64Imm(1, dl),
3561  S->getI64Imm(63, dl)), 0);
3562  SDValue ShiftR =
3563  SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, RHS,
3564  S->getI64Imm(63, dl)), 0);
3565  SDValue SubtractCarry =
3566  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3567  LHS, RHS), 1);
3568  return SDValue(CurDAG->getMachineNode(PPC::ADDE8, dl, MVT::i64, MVT::Glue,
3569  ShiftR, ShiftL, SubtractCarry), 0);
3570  }
3571  case ISD::SETGT: {
3572  // {subc.reg, subc.CA} = (subcarry %b, %a)
3573  // (zext (setcc %a, %b, setgt)) ->
3574  // (xor (adde (lshr %a, 63), (ashr %b, 63), subc.CA), 1)
3575  // (zext (setcc %a, 0, setgt)) -> (lshr (nor (add %a, -1), %a), 63)
3576  if (IsRHSNegOne)
3577  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GEZExt);
3578  if (IsRHSZero) {
3579  SDValue Addi =
3580  SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64, LHS,
3581  S->getI64Imm(~0ULL, dl)), 0);
3582  SDValue Nor =
3583  SDValue(CurDAG->getMachineNode(PPC::NOR8, dl, MVT::i64, Addi, LHS), 0);
3584  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Nor,
3585  S->getI64Imm(1, dl),
3586  S->getI64Imm(63, dl)), 0);
3587  }
3588  std::swap(LHS, RHS);
3589  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3590  IsRHSZero = RHSConst && RHSConst->isZero();
3591  IsRHSOne = RHSConst && RHSConst->getSExtValue() == 1;
3592  [[fallthrough]];
3593  }
3594  case ISD::SETLT: {
3595  // {subc.reg, subc.CA} = (subcarry %a, %b)
3596  // (zext (setcc %a, %b, setlt)) ->
3597  // (xor (adde (lshr %b, 63), (ashr %a, 63), subc.CA), 1)
3598  // (zext (setcc %a, 0, setlt)) -> (lshr %a, 63)
3599  if (IsRHSOne)
3600  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LEZExt);
3601  if (IsRHSZero)
3602  return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, LHS,
3603  S->getI64Imm(1, dl),
3604  S->getI64Imm(63, dl)), 0);
3605  SDValue SRADINode =
3606  SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64,
3607  LHS, S->getI64Imm(63, dl)), 0);
3608  SDValue SRDINode =
3609  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3610  RHS, S->getI64Imm(1, dl),
3611  S->getI64Imm(63, dl)), 0);
3612  SDValue SUBFC8Carry =
3613  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3614  RHS, LHS), 1);
3615  SDValue ADDE8Node =
3616  SDValue(CurDAG->getMachineNode(PPC::ADDE8, dl, MVT::i64, MVT::Glue,
3617  SRDINode, SRADINode, SUBFC8Carry), 0);
3618  return SDValue(CurDAG->getMachineNode(PPC::XORI8, dl, MVT::i64,
3619  ADDE8Node, S->getI64Imm(1, dl)), 0);
3620  }
3621  case ISD::SETUGE:
3622  // {subc.reg, subc.CA} = (subcarry %a, %b)
3623  // (zext (setcc %a, %b, setuge)) -> (add (sube %b, %b, subc.CA), 1)
3624  std::swap(LHS, RHS);
3625  [[fallthrough]];
3626  case ISD::SETULE: {
3627  // {subc.reg, subc.CA} = (subcarry %b, %a)
3628  // (zext (setcc %a, %b, setule)) -> (add (sube %a, %a, subc.CA), 1)
3629  SDValue SUBFC8Carry =
3630  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3631  LHS, RHS), 1);
3632  SDValue SUBFE8Node =
3633  SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64, MVT::Glue,
3634  LHS, LHS, SUBFC8Carry), 0);
3635  return SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64,
3636  SUBFE8Node, S->getI64Imm(1, dl)), 0);
3637  }
3638  case ISD::SETUGT:
3639  // {subc.reg, subc.CA} = (subcarry %b, %a)
3640  // (zext (setcc %a, %b, setugt)) -> -(sube %b, %b, subc.CA)
3641  std::swap(LHS, RHS);
3642  [[fallthrough]];
3643  case ISD::SETULT: {
3644  // {subc.reg, subc.CA} = (subcarry %a, %b)
3645  // (zext (setcc %a, %b, setult)) -> -(sube %a, %a, subc.CA)
3646  SDValue SubtractCarry =
3647  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3648  RHS, LHS), 1);
3649  SDValue ExtSub =
3650  SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64,
3651  LHS, LHS, SubtractCarry), 0);
3652  return SDValue(CurDAG->getMachineNode(PPC::NEG8, dl, MVT::i64,
3653  ExtSub), 0);
3654  }
3655  }
3656 }
3657 
3658 /// Produces a sign-extended result of comparing two 64-bit values according to
3659 /// the passed condition code.
3660 SDValue
3661 IntegerCompareEliminator::get64BitSExtCompare(SDValue LHS, SDValue RHS,
3662  ISD::CondCode CC,
3663  int64_t RHSValue, SDLoc dl) {
3664  if (CmpInGPR == ICGPR_I32 || CmpInGPR == ICGPR_SextI32 ||
3666  return SDValue();
3667  bool IsRHSZero = RHSValue == 0;
3668  bool IsRHSOne = RHSValue == 1;
3669  bool IsRHSNegOne = RHSValue == -1LL;
3670  switch (CC) {
3671  default: return SDValue();
3672  case ISD::SETEQ: {
3673  // {addc.reg, addc.CA} = (addcarry (xor %a, %b), -1)
3674  // (sext (setcc %a, %b, seteq)) -> (sube addc.reg, addc.reg, addc.CA)
3675  // {addcz.reg, addcz.CA} = (addcarry %a, -1)
3676  // (sext (setcc %a, 0, seteq)) -> (sube addcz.reg, addcz.reg, addcz.CA)
3677  SDValue AddInput = IsRHSZero ? LHS :
3678  SDValue(CurDAG->getMachineNode(PPC::XOR8, dl, MVT::i64, LHS, RHS), 0);
3679  SDValue Addic =
3680  SDValue(CurDAG->getMachineNode(PPC::ADDIC8, dl, MVT::i64, MVT::Glue,
3681  AddInput, S->getI32Imm(~0U, dl)), 0);
3682  return SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64, Addic,
3683  Addic, Addic.getValue(1)), 0);
3684  }
3685  case ISD::SETNE: {
3686  // {subfc.reg, subfc.CA} = (subcarry 0, (xor %a, %b))
3687  // (sext (setcc %a, %b, setne)) -> (sube subfc.reg, subfc.reg, subfc.CA)
3688  // {subfcz.reg, subfcz.CA} = (subcarry 0, %a)
3689  // (sext (setcc %a, 0, setne)) -> (sube subfcz.reg, subfcz.reg, subfcz.CA)
3690  SDValue Xor = IsRHSZero ? LHS :
3691  SDValue(CurDAG->getMachineNode(PPC::XOR8, dl, MVT::i64, LHS, RHS), 0);
3692  SDValue SC =
3693  SDValue(CurDAG->getMachineNode(PPC::SUBFIC8, dl, MVT::i64, MVT::Glue,
3694  Xor, S->getI32Imm(0, dl)), 0);
3695  return SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64, SC,
3696  SC, SC.getValue(1)), 0);
3697  }
3698  case ISD::SETGE: {
3699  // {subc.reg, subc.CA} = (subcarry %a, %b)
3700  // (zext (setcc %a, %b, setge)) ->
3701  // (- (adde (lshr %b, 63), (ashr %a, 63), subc.CA))
3702  // (zext (setcc %a, 0, setge)) -> (~ (ashr %a, 63))
3703  if (IsRHSZero)
3704  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GESExt);
3705  std::swap(LHS, RHS);
3706  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3707  IsRHSZero = RHSConst && RHSConst->isZero();
3708  [[fallthrough]];
3709  }
3710  case ISD::SETLE: {
3711  // {subc.reg, subc.CA} = (subcarry %b, %a)
3712  // (zext (setcc %a, %b, setge)) ->
3713  // (- (adde (lshr %a, 63), (ashr %b, 63), subc.CA))
3714  // (zext (setcc %a, 0, setge)) -> (ashr (or %a, (add %a, -1)), 63)
3715  if (IsRHSZero)
3716  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LESExt);
3717  SDValue ShiftR =
3718  SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, RHS,
3719  S->getI64Imm(63, dl)), 0);
3720  SDValue ShiftL =
3721  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, LHS,
3722  S->getI64Imm(1, dl),
3723  S->getI64Imm(63, dl)), 0);
3724  SDValue SubtractCarry =
3725  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3726  LHS, RHS), 1);
3727  SDValue Adde =
3728  SDValue(CurDAG->getMachineNode(PPC::ADDE8, dl, MVT::i64, MVT::Glue,
3729  ShiftR, ShiftL, SubtractCarry), 0);
3730  return SDValue(CurDAG->getMachineNode(PPC::NEG8, dl, MVT::i64, Adde), 0);
3731  }
3732  case ISD::SETGT: {
3733  // {subc.reg, subc.CA} = (subcarry %b, %a)
3734  // (zext (setcc %a, %b, setgt)) ->
3735  // -(xor (adde (lshr %a, 63), (ashr %b, 63), subc.CA), 1)
3736  // (zext (setcc %a, 0, setgt)) -> (ashr (nor (add %a, -1), %a), 63)
3737  if (IsRHSNegOne)
3738  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::GESExt);
3739  if (IsRHSZero) {
3740  SDValue Add =
3741  SDValue(CurDAG->getMachineNode(PPC::ADDI8, dl, MVT::i64, LHS,
3742  S->getI64Imm(-1, dl)), 0);
3743  SDValue Nor =
3744  SDValue(CurDAG->getMachineNode(PPC::NOR8, dl, MVT::i64, Add, LHS), 0);
3745  return SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, Nor,
3746  S->getI64Imm(63, dl)), 0);
3747  }
3748  std::swap(LHS, RHS);
3749  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3750  IsRHSZero = RHSConst && RHSConst->isZero();
3751  IsRHSOne = RHSConst && RHSConst->getSExtValue() == 1;
3752  [[fallthrough]];
3753  }
3754  case ISD::SETLT: {
3755  // {subc.reg, subc.CA} = (subcarry %a, %b)
3756  // (zext (setcc %a, %b, setlt)) ->
3757  // -(xor (adde (lshr %b, 63), (ashr %a, 63), subc.CA), 1)
3758  // (zext (setcc %a, 0, setlt)) -> (ashr %a, 63)
3759  if (IsRHSOne)
3760  return getCompoundZeroComparisonInGPR(LHS, dl, ZeroCompare::LESExt);
3761  if (IsRHSZero) {
3762  return SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, LHS,
3763  S->getI64Imm(63, dl)), 0);
3764  }
3765  SDValue SRADINode =
3766  SDValue(CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64,
3767  LHS, S->getI64Imm(63, dl)), 0);
3768  SDValue SRDINode =
3769  SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
3770  RHS, S->getI64Imm(1, dl),
3771  S->getI64Imm(63, dl)), 0);
3772  SDValue SUBFC8Carry =
3773  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3774  RHS, LHS), 1);
3775  SDValue ADDE8Node =
3776  SDValue(CurDAG->getMachineNode(PPC::ADDE8, dl, MVT::i64,
3777  SRDINode, SRADINode, SUBFC8Carry), 0);
3778  SDValue XORI8Node =
3779  SDValue(CurDAG->getMachineNode(PPC::XORI8, dl, MVT::i64,
3780  ADDE8Node, S->getI64Imm(1, dl)), 0);
3781  return SDValue(CurDAG->getMachineNode(PPC::NEG8, dl, MVT::i64,
3782  XORI8Node), 0);
3783  }
3784  case ISD::SETUGE:
3785  // {subc.reg, subc.CA} = (subcarry %a, %b)
3786  // (sext (setcc %a, %b, setuge)) -> ~(sube %b, %b, subc.CA)
3787  std::swap(LHS, RHS);
3788  [[fallthrough]];
3789  case ISD::SETULE: {
3790  // {subc.reg, subc.CA} = (subcarry %b, %a)
3791  // (sext (setcc %a, %b, setule)) -> ~(sube %a, %a, subc.CA)
3792  SDValue SubtractCarry =
3793  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3794  LHS, RHS), 1);
3795  SDValue ExtSub =
3796  SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64, MVT::Glue, LHS,
3797  LHS, SubtractCarry), 0);
3798  return SDValue(CurDAG->getMachineNode(PPC::NOR8, dl, MVT::i64,
3799  ExtSub, ExtSub), 0);
3800  }
3801  case ISD::SETUGT:
3802  // {subc.reg, subc.CA} = (subcarry %b, %a)
3803  // (sext (setcc %a, %b, setugt)) -> (sube %b, %b, subc.CA)
3804  std::swap(LHS, RHS);
3805  [[fallthrough]];
3806  case ISD::SETULT: {
3807  // {subc.reg, subc.CA} = (subcarry %a, %b)
3808  // (sext (setcc %a, %b, setult)) -> (sube %a, %a, subc.CA)
3809  SDValue SubCarry =
3810  SDValue(CurDAG->getMachineNode(PPC::SUBFC8, dl, MVT::i64, MVT::Glue,
3811  RHS, LHS), 1);
3812  return SDValue(CurDAG->getMachineNode(PPC::SUBFE8, dl, MVT::i64,
3813  LHS, LHS, SubCarry), 0);
3814  }
3815  }
3816 }
3817 
3818 /// Do all uses of this SDValue need the result in a GPR?
3819 /// This is meant to be used on values that have type i1 since
3820 /// it is somewhat meaningless to ask if values of other types
3821 /// should be kept in GPR's.
3822 static bool allUsesExtend(SDValue Compare, SelectionDAG *CurDAG) {
3823  assert(Compare.getOpcode() == ISD::SETCC &&
3824  "An ISD::SETCC node required here.");
3825 
3826  // For values that have a single use, the caller should obviously already have
3827  // checked if that use is an extending use. We check the other uses here.
3828  if (Compare.hasOneUse())
3829  return true;
3830  // We want the value in a GPR if it is being extended, used for a select, or
3831  // used in logical operations.
3832  for (auto *CompareUse : Compare.getNode()->uses())
3833  if (CompareUse->getOpcode() != ISD::SIGN_EXTEND &&
3834  CompareUse->getOpcode() != ISD::ZERO_EXTEND &&
3835  CompareUse->getOpcode() != ISD::SELECT &&
3836  !isLogicOp(CompareUse->getOpcode())) {
3837  OmittedForNonExtendUses++;
3838  return false;
3839  }
3840  return true;
3841 }
3842 
3843 /// Returns an equivalent of a SETCC node but with the result the same width as
3844 /// the inputs. This can also be used for SELECT_CC if either the true or false
3845 /// values is a power of two while the other is zero.
3846 SDValue IntegerCompareEliminator::getSETCCInGPR(SDValue Compare,
3847  SetccInGPROpts ConvOpts) {
3848  assert((Compare.getOpcode() == ISD::SETCC ||
3849  Compare.getOpcode() == ISD::SELECT_CC) &&
3850  "An ISD::SETCC node required here.");
3851 
3852  // Don't convert this comparison to a GPR sequence because there are uses
3853  // of the i1 result (i.e. uses that require the result in the CR).
3854  if ((Compare.getOpcode() == ISD::SETCC) && !allUsesExtend(Compare, CurDAG))
3855  return SDValue();
3856 
3857  SDValue LHS = Compare.getOperand(0);
3858  SDValue RHS = Compare.getOperand(1);
3859 
3860  // The condition code is operand 2 for SETCC and operand 4 for SELECT_CC.
3861  int CCOpNum = Compare.getOpcode() == ISD::SELECT_CC ? 4 : 2;
3862  ISD::CondCode CC =
3863  cast<CondCodeSDNode>(Compare.getOperand(CCOpNum))->get();
3864  EVT InputVT = LHS.getValueType();
3865  if (InputVT != MVT::i32 && InputVT != MVT::i64)
3866  return SDValue();
3867 
3868  if (ConvOpts == SetccInGPROpts::ZExtInvert ||
3869  ConvOpts == SetccInGPROpts::SExtInvert)
3870  CC = ISD::getSetCCInverse(CC, InputVT);
3871 
3872  bool Inputs32Bit = InputVT == MVT::i32;
3873 
3874  SDLoc dl(Compare);
3875  ConstantSDNode *RHSConst = dyn_cast<ConstantSDNode>(RHS);
3876  int64_t RHSValue = RHSConst ? RHSConst->getSExtValue() : INT64_MAX;
3877  bool IsSext = ConvOpts == SetccInGPROpts::SExtOrig ||
3878  ConvOpts == SetccInGPROpts::SExtInvert;
3879 
3880  if (IsSext && Inputs32Bit)
3881  return get32BitSExtCompare(LHS, RHS, CC, RHSValue, dl);
3882  else if (Inputs32Bit)
3883  return get32BitZExtCompare(LHS, RHS, CC, RHSValue, dl);
3884  else if (IsSext)
3885  return get64BitSExtCompare(LHS, RHS, CC, RHSValue, dl);
3886  return get64BitZExtCompare(LHS, RHS, CC, RHSValue, dl);
3887 }
3888 
3889 } // end anonymous namespace
3890 
3891 bool PPCDAGToDAGISel::tryIntCompareInGPR(SDNode *N) {
3892  if (N->getValueType(0) != MVT::i32 &&
3893  N->getValueType(0) != MVT::i64)
3894  return false;
3895 
3896  // This optimization will emit code that assumes 64-bit registers
3897  // so we don't want to run it in 32-bit mode. Also don't run it
3898  // on functions that are not to be optimized.
3899  if (TM.getOptLevel() == CodeGenOpt::None || !TM.isPPC64())
3900  return false;
3901 
3902  // For POWER10, it is more profitable to use the set boolean extension
3903  // instructions rather than the integer compare elimination codegen.
3904  // Users can override this via the command line option, `--ppc-gpr-icmps`.
3905  if (!(CmpInGPR.getNumOccurrences() > 0) && Subtarget->isISA3_1())
3906  return false;
3907 
3908  switch (N->getOpcode()) {
3909  default: break;
3910  case ISD::ZERO_EXTEND:
3911  case ISD::SIGN_EXTEND:
3912  case ISD::AND:
3913  case ISD::OR:
3914  case ISD::XOR: {
3915  IntegerCompareEliminator ICmpElim(CurDAG, this);
3916  if (SDNode *New = ICmpElim.Select(N)) {
3917  ReplaceNode(N, New);
3918  return true;
3919  }
3920  }
3921  }
3922  return false;
3923 }
3924 
3925 bool PPCDAGToDAGISel::tryBitPermutation(SDNode *N) {
3926  if (N->getValueType(0) != MVT::i32 &&
3927  N->getValueType(0) != MVT::i64)
3928  return false;
3929 
3930  if (!UseBitPermRewriter)
3931  return false;
3932 
3933  switch (N->getOpcode()) {
3934  default: break;
3935  case ISD::ROTL:
3936  case ISD::SHL:
3937  case ISD::SRL:
3938  case ISD::AND:
3939  case ISD::OR: {
3940  BitPermutationSelector BPS(CurDAG);
3941  if (SDNode *New = BPS.Select(N)) {
3942  ReplaceNode(N, New);
3943  return true;
3944  }
3945  return false;
3946  }
3947  }
3948 
3949  return false;
3950 }
3951 
3952 /// SelectCC - Select a comparison of the specified values with the specified
3953 /// condition code, returning the CR# of the expression.
3954 SDValue PPCDAGToDAGISel::SelectCC(SDValue LHS, SDValue RHS, ISD::CondCode CC,
3955  const SDLoc &dl, SDValue Chain) {
3956  // Always select the LHS.
3957  unsigned Opc;
3958 
3959  if (LHS.getValueType() == MVT::i32) {
3960  unsigned Imm;
3961  if (CC == ISD::SETEQ || CC == ISD::SETNE) {
3962  if (isInt32Immediate(RHS, Imm)) {
3963  // SETEQ/SETNE comparison with 16-bit immediate, fold it.
3964  if (isUInt<16>(Imm))
3965  return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
3966  getI32Imm(Imm & 0xFFFF, dl)),
3967  0);
3968  // If this is a 16-bit signed immediate, fold it.
3969  if (isInt<16>((int)Imm))
3970  return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
3971  getI32Imm(Imm & 0xFFFF, dl)),
3972  0);
3973 
3974  // For non-equality comparisons, the default code would materialize the
3975  // constant, then compare against it, like this:
3976  // lis r2, 4660
3977  // ori r2, r2, 22136
3978  // cmpw cr0, r3, r2
3979  // Since we are just comparing for equality, we can emit this instead:
3980  // xoris r0,r3,0x1234
3981  // cmplwi cr0,r0,0x5678
3982  // beq cr0,L6
3983  SDValue Xor(CurDAG->getMachineNode(PPC::XORIS, dl, MVT::i32, LHS,
3984  getI32Imm(Imm >> 16, dl)), 0);
3985  return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, Xor,
3986  getI32Imm(Imm & 0xFFFF, dl)), 0);
3987  }
3988  Opc = PPC::CMPLW;
3989  } else if (ISD::isUnsignedIntSetCC(CC)) {
3990  if (isInt32Immediate(RHS, Imm) && isUInt<16>(Imm))
3991  return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
3992  getI32Imm(Imm & 0xFFFF, dl)), 0);
3993  Opc = PPC::CMPLW;
3994  } else {
3995  int16_t SImm;
3996  if (isIntS16Immediate(RHS, SImm))
3997  return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
3998  getI32Imm((int)SImm & 0xFFFF,
3999  dl)),
4000  0);
4001  Opc = PPC::CMPW;
4002  }
4003  } else if (LHS.getValueType() == MVT::i64) {
4004  uint64_t Imm;
4005  if (CC == ISD::SETEQ || CC == ISD::SETNE) {
4006  if (isInt64Immediate(RHS.getNode(), Imm)) {
4007  // SETEQ/SETNE comparison with 16-bit immediate, fold it.
4008  if (isUInt<16>(Imm))
4009  return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
4010  getI32Imm(Imm & 0xFFFF, dl)),
4011  0);
4012  // If this is a 16-bit signed immediate, fold it.
4013  if (isInt<16>(Imm))
4014  return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
4015  getI32Imm(Imm & 0xFFFF, dl)),
4016  0);
4017 
4018  // For non-equality comparisons, the default code would materialize the
4019  // constant, then compare against it, like this:
4020  // lis r2, 4660
4021  // ori r2, r2, 22136
4022  // cmpd cr0, r3, r2
4023  // Since we are just comparing for equality, we can emit this instead:
4024  // xoris r0,r3,0x1234
4025  // cmpldi cr0,r0,0x5678
4026  // beq cr0,L6
4027  if (isUInt<32>(Imm)) {
4028  SDValue Xor(CurDAG->getMachineNode(PPC::XORIS8, dl, MVT::i64, LHS,
4029  getI64Imm(Imm >> 16, dl)), 0);
4030  return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, Xor,
4031  getI64Imm(Imm & 0xFFFF, dl)),
4032  0);
4033  }
4034  }
4035  Opc = PPC::CMPLD;
4036  } else if (ISD::isUnsignedIntSetCC(CC)) {
4037  if (isInt64Immediate(RHS.getNode(), Imm) && isUInt<16>(Imm))
4038  return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
4039  getI64Imm(Imm & 0xFFFF, dl)), 0);
4040  Opc = PPC::CMPLD;
4041  } else {
4042  int16_t SImm;
4043  if (isIntS16Immediate(RHS, SImm))
4044  return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
4045  getI64Imm(SImm & 0xFFFF, dl)),
4046  0);
4047  Opc = PPC::CMPD;
4048  }
4049  } else if (LHS.getValueType() == MVT::f32) {
4050  if (Subtarget->hasSPE()) {
4051  switch (CC) {
4052  default:
4053  case ISD::SETEQ:
4054  case ISD::SETNE:
4055  Opc = PPC::EFSCMPEQ;
4056  break;
4057  case ISD::SETLT:
4058  case ISD::SETGE:
4059  case ISD::SETOLT:
4060  case ISD::SETOGE:
4061  case ISD::SETULT:
4062  case ISD::SETUGE:
4063  Opc = PPC::EFSCMPLT;
4064  break;
4065  case ISD::SETGT:
4066  case ISD::SETLE:
4067  case ISD::SETOGT:
4068  case ISD::SETOLE:
4069  case ISD::SETUGT:
4070  case ISD::SETULE:
4071  Opc = PPC::EFSCMPGT;
4072  break;
4073  }
4074  } else
4075  Opc = PPC::FCMPUS;
4076  } else if (LHS.getValueType() == MVT::f64) {
4077  if (Subtarget->hasSPE()) {
4078  switch (CC) {
4079  default:
4080  case ISD::SETEQ:
4081  case ISD::SETNE:
4082  Opc = PPC::EFDCMPEQ;
4083  break;
4084  case ISD::SETLT:
4085  case ISD::SETGE:
4086  case ISD::SETOLT:
4087  case ISD::SETOGE:
4088  case ISD::SETULT:
4089  case ISD::SETUGE:
4090  Opc = PPC::EFDCMPLT;
4091  break;
4092  case ISD::SETGT:
4093  case ISD::SETLE:
4094  case ISD::SETOGT:
4095  case ISD::SETOLE:
4096  case ISD::SETUGT:
4097  case ISD::SETULE:
4098  Opc = PPC::EFDCMPGT;
4099  break;
4100  }
4101  } else
4102  Opc = Subtarget->hasVSX() ? PPC::XSCMPUDP : PPC::FCMPUD;
4103  } else {
4104  assert(LHS.getValueType() == MVT::f128 && "Unknown vt!");
4105  assert(Subtarget->hasP9Vector() && "XSCMPUQP requires Power9 Vector");
4106  Opc = PPC::XSCMPUQP;
4107  }
4108  if (Chain)
4109  return SDValue(
4110  CurDAG->getMachineNode(Opc, dl, MVT::i32, MVT::Other, LHS, RHS, Chain),
4111  0);
4112  else
4113  return SDValue(CurDAG->getMachineNode(Opc, dl, MVT::i32, LHS, RHS), 0);
4114 }
4115 
4117  const PPCSubtarget *Subtarget) {
4118  // For SPE instructions, the result is in GT bit of the CR
4119  bool UseSPE = Subtarget->hasSPE() && VT.isFloatingPoint();
4120 
4121  switch (CC) {
4122  case ISD::SETUEQ:
4123  case ISD::SETONE:
4124  case ISD::SETOLE:
4125  case ISD::SETOGE:
4126  llvm_unreachable("Should be lowered by legalize!");
4127  default: llvm_unreachable("Unknown condition!");
4128  case ISD::SETOEQ:
4129  case ISD::SETEQ:
4130  return UseSPE ? PPC::PRED_GT : PPC::PRED_EQ;
4131  case ISD::SETUNE:
4132  case ISD::SETNE:
4133  return UseSPE ? PPC::PRED_LE : PPC::PRED_NE;
4134  case ISD::SETOLT:
4135  case ISD::SETLT:
4136  return UseSPE ? PPC::PRED_GT : PPC::PRED_LT;
4137  case ISD::SETULE:
4138  case ISD::SETLE:
4139  return PPC::PRED_LE;
4140  case ISD::SETOGT:
4141  case ISD::SETGT:
4142  return PPC::PRED_GT;
4143  case ISD::SETUGE:
4144  case ISD::SETGE:
4145  return UseSPE ? PPC::PRED_LE : PPC::PRED_GE;
4146  case ISD::SETO: return PPC::PRED_NU;
4147  case ISD::SETUO: return PPC::PRED_UN;
4148  // These two are invalid for floating point. Assume we have int.
4149  case ISD::SETULT: return PPC::PRED_LT;
4150  case ISD::SETUGT: return PPC::PRED_GT;
4151  }
4152 }
4153 
4154 /// getCRIdxForSetCC - Return the index of the condition register field
4155 /// associated with the SetCC condition, and whether or not the field is
4156 /// treated as inverted. That is, lt = 0; ge = 0 inverted.
4157 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool &Invert) {
4158  Invert = false;
4159  switch (CC) {
4160  default: llvm_unreachable("Unknown condition!");
4161  case ISD::SETOLT:
4162  case ISD::SETLT: return 0; // Bit #0 = SETOLT
4163  case ISD::SETOGT:
4164  case ISD::SETGT: return 1; // Bit #1 = SETOGT
4165  case ISD::SETOEQ:
4166  case ISD::SETEQ: return 2; // Bit #2 = SETOEQ
4167  case ISD::SETUO: return 3; // Bit #3 = SETUO
4168  case ISD::SETUGE:
4169  case ISD::SETGE: Invert = true; return 0; // !Bit #0 = SETUGE
4170  case ISD::SETULE:
4171  case ISD::SETLE: Invert = true; return 1; // !Bit #1 = SETULE
4172  case ISD::SETUNE:
4173  case ISD::SETNE: Invert = true; return 2; // !Bit #2 = SETUNE
4174  case ISD::SETO: Invert = true; return 3; // !Bit #3 = SETO
4175  case ISD::SETUEQ:
4176  case ISD::SETOGE:
4177  case ISD::SETOLE:
4178  case ISD::SETONE:
4179  llvm_unreachable("Invalid branch code: should be expanded by legalize");
4180  // These are invalid for floating point. Assume integer.
4181  case ISD::SETULT: return 0;
4182  case ISD::SETUGT: return 1;
4183  }
4184 }
4185 
4186 // getVCmpInst: return the vector compare instruction for the specified
4187 // vector type and condition code. Since this is for altivec specific code,
4188 // only support the altivec types (v16i8, v8i16, v4i32, v2i64, v1i128,
4189 // and v4f32).
4190 static unsigned int getVCmpInst(MVT VecVT, ISD::CondCode CC,
4191  bool HasVSX, bool &Swap, bool &Negate) {
4192  Swap = false;
4193  Negate = false;
4194 
4195  if (VecVT.isFloatingPoint()) {
4196  /* Handle some cases by swapping input operands. */
4197  switch (CC) {
4198  case ISD::SETLE: CC = ISD::SETGE; Swap = true; break;
4199  case ISD::SETLT: CC = ISD::SETGT; Swap = true; break;
4200  case ISD::SETOLE: CC = ISD::SETOGE; Swap = true; break;
4201  case ISD::SETOLT: CC = ISD::SETOGT; Swap = true; break;
4202  case ISD::SETUGE: CC = ISD::SETULE; Swap = true; break;
4203  case ISD::SETUGT: CC = ISD::SETULT; Swap = true; break;
4204  default: break;
4205  }
4206  /* Handle some cases by negating the result. */
4207  switch (CC) {
4208  case ISD::SETNE: CC = ISD::SETEQ; Negate = true; break;
4209  case ISD::SETUNE: CC = ISD::SETOEQ; Negate = true; break;
4210  case ISD::SETULE: CC = ISD::SETOGT; Negate = true; break;
4211  case ISD::SETULT: CC = ISD::SETOGE; Negate = true; break;
4212  default: break;
4213  }
4214  /* We have instructions implementing the remaining cases. */
4215  switch (CC) {
4216  case ISD::SETEQ:
4217  case ISD::SETOEQ:
4218  if (VecVT == MVT::v4f32)
4219  return HasVSX ? PPC::XVCMPEQSP : PPC::VCMPEQFP;
4220  else if (VecVT == MVT::v2f64)
4221  return PPC::XVCMPEQDP;
4222  break;
4223  case ISD::SETGT:
4224  case ISD::SETOGT:
4225  if (VecVT == MVT::v4f32)
4226  return HasVSX ? PPC::XVCMPGTSP : PPC::VCMPGTFP;
4227  else if (VecVT == MVT::v2f64)
4228  return PPC::XVCMPGTDP;
4229  break;
4230  case ISD::SETGE:
4231  case ISD::SETOGE:
4232  if (VecVT == MVT::v4f32)
4233  return HasVSX ? PPC::XVCMPGESP : PPC::VCMPGEFP;
4234  else if (VecVT == MVT::v2f64)
4235  return PPC::XVCMPGEDP;
4236  break;
4237  default:
4238  break;
4239  }
4240  llvm_unreachable("Invalid floating-point vector compare condition");
4241  } else {
4242  /* Handle some cases by swapping input operands. */
4243  switch (CC) {
4244  case ISD::SETGE: CC = ISD::SETLE; Swap = true; break;
4245  case ISD::SETLT: CC = ISD::SETGT; Swap = true; break;
4246  case ISD::SETUGE: CC = ISD::SETULE; Swap = true; break;
4247  case ISD::SETULT: CC = ISD::SETUGT; Swap = true; break;
4248  default: break;
4249  }
4250  /* Handle some cases by negating the result. */
4251  switch (CC) {
4252  case ISD::SETNE: CC = ISD::SETEQ; Negate = true; break;
4253  case ISD::SETUNE: CC = ISD::SETUEQ; Negate = true; break;
4254  case ISD::SETLE: CC = ISD::SETGT; Negate = true; break;
4255  case ISD::SETULE: CC = ISD::SETUGT; Negate = true; break;
4256  default: break;
4257  }
4258  /* We have instructions implementing the remaining cases. */
4259  switch (CC) {
4260  case ISD::SETEQ:
4261  case ISD::SETUEQ:
4262  if (VecVT == MVT::v16i8)
4263  return PPC::VCMPEQUB;
4264  else if (VecVT == MVT::v8i16)
4265  return PPC::VCMPEQUH;
4266  else if (VecVT == MVT::v4i32)
4267  return PPC::VCMPEQUW;
4268  else if (VecVT == MVT::v2i64)
4269  return PPC::VCMPEQUD;
4270  else if (VecVT == MVT::v1i128)
4271  return PPC::VCMPEQUQ;
4272  break;
4273  case ISD::SETGT:
4274  if (VecVT == MVT::v16i8)
4275  return PPC::VCMPGTSB;
4276  else if (VecVT == MVT::v8i16)
4277  return PPC::VCMPGTSH;
4278  else if (VecVT == MVT::v4i32)
4279  return PPC::VCMPGTSW;
4280  else if (VecVT == MVT::v2i64)
4281  return PPC::VCMPGTSD;
4282  else if (VecVT == MVT::v1i128)
4283  return PPC::VCMPGTSQ;
4284  break;
4285  case ISD::SETUGT:
4286  if (VecVT == MVT::v16i8)
4287  return PPC::VCMPGTUB;
4288  else if (VecVT == MVT::v8i16)
4289  return PPC::VCMPGTUH;
4290  else if (VecVT == MVT::v4i32)
4291  return PPC::VCMPGTUW;
4292  else if (VecVT == MVT::v2i64)
4293  return PPC::VCMPGTUD;
4294  else if (VecVT == MVT::v1i128)
4295  return PPC::VCMPGTUQ;
4296  break;
4297  default:
4298  break;
4299  }
4300  llvm_unreachable("Invalid integer vector compare condition");
4301  }
4302 }
4303 
4304 bool PPCDAGToDAGISel::trySETCC(SDNode *N) {
4305  SDLoc dl(N);
4306  unsigned Imm;
4307  bool IsStrict = N->isStrictFPOpcode();
4308  ISD::CondCode CC =
4309  cast<CondCodeSDNode>(N->getOperand(IsStrict ? 3 : 2))->get();
4310  EVT PtrVT =
4311  CurDAG->getTargetLoweringInfo().getPointerTy(CurDAG->getDataLayout());
4312  bool isPPC64 = (PtrVT == MVT::i64);
4313  SDValue Chain = IsStrict ? N->getOperand(0) : SDValue();
4314 
4315  SDValue LHS = N->getOperand(IsStrict ? 1 : 0);
4316  SDValue RHS = N->getOperand(IsStrict ? 2 : 1);
4317 
4318  if (!IsStrict && !Subtarget->useCRBits() && isInt32Immediate(RHS, Imm)) {
4319  // We can codegen setcc op, imm very efficiently compared to a brcond.
4320  // Check for those cases here.
4321  // setcc op, 0
4322  if (Imm == 0) {
4323  SDValue Op = LHS;
4324  switch (CC) {
4325  default: break;
4326  case ISD::SETEQ: {
4327  Op = SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Op), 0);
4328  SDValue Ops[] = { Op, getI32Imm(27, dl), getI32Imm(5, dl),
4329  getI32Imm(31, dl) };
4330  CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
4331  return true;
4332  }
4333  case ISD::SETNE: {
4334  if (isPPC64) break;
4335  SDValue AD =
4336  SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
4337  Op, getI32Imm(~0U, dl)), 0);
4338  CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op, AD.getValue(1));
4339  return true;
4340  }
4341  case ISD::SETLT: {
4342  SDValue Ops[] = { Op, getI32Imm(1, dl), getI32Imm(31, dl),
4343  getI32Imm(31, dl) };
4344  CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
4345  return true;
4346  }
4347  case ISD::SETGT: {
4348  SDValue T =
4349  SDValue(CurDAG->getMachineNode(PPC::NEG, dl, MVT::i32, Op), 0);
4350  T = SDValue(CurDAG->getMachineNode(PPC::ANDC, dl, MVT::i32, T, Op), 0);
4351  SDValue Ops[] = { T, getI32Imm(1, dl), getI32Imm(31, dl),
4352  getI32Imm(31, dl) };
4353  CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
4354  return true;
4355  }
4356  }
4357  } else if (Imm == ~0U) { // setcc op, -1
4358  SDValue Op = LHS;
4359  switch (CC) {
4360  default: break;
4361  case ISD::SETEQ:
4362  if (isPPC64) break;
4363  Op = SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
4364  Op, getI32Imm(1, dl)), 0);
4365  CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
4366  SDValue(CurDAG->getMachineNode(PPC::LI, dl,
4367  MVT::i32,
4368  getI32Imm(0, dl)),
4369  0), Op.getValue(1));
4370  return true;
4371  case ISD::SETNE: {
4372  if (isPPC64) break;
4373  Op = SDValue(CurDAG->getMachineNode(PPC::NOR, dl, MVT::i32, Op, Op), 0);
4374  SDNode *AD = CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
4375  Op, getI32Imm(~0U, dl));
4376  CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDValue(AD, 0), Op,
4377  SDValue(AD, 1));
4378  return true;
4379  }
4380  case ISD::SETLT: {
4381  SDValue AD = SDValue(CurDAG->getMachineNode(PPC::ADDI, dl, MVT::i32, Op,
4382  getI32Imm(1, dl)), 0);
4383  SDValue AN = SDValue(CurDAG->getMachineNode(PPC::AND, dl, MVT::i32, AD,
4384  Op), 0);
4385  SDValue Ops[] = { AN, getI32Imm(1, dl), getI32Imm(31, dl),
4386  getI32Imm(31, dl) };
4387  CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
4388  return true;
4389  }
4390  case ISD::SETGT: {
4391  SDValue Ops[] = { Op, getI32Imm(1, dl), getI32Imm(31, dl),
4392  getI32Imm(31, dl) };
4393  Op = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
4394  CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op, getI32Imm(1, dl));
4395  return true;
4396  }
4397  }
4398  }
4399  }
4400 
4401  // Altivec Vector compare instructions do not set any CR register by default and
4402  // vector compare operations return the same type as the operands.
4403  if (!IsStrict && LHS.getValueType().isVector()) {
4404  if (Subtarget->hasSPE())
4405  return false;
4406 
4407  EVT VecVT = LHS.getValueType();
4408  bool Swap, Negate;
4409  unsigned int VCmpInst =
4410  getVCmpInst(VecVT.getSimpleVT(), CC, Subtarget->hasVSX(), Swap, Negate);
4411  if (Swap)
4412  std::swap(LHS, RHS);
4413 
4414  EVT ResVT = VecVT.changeVectorElementTypeToInteger();
4415  if (Negate) {
4416  SDValue VCmp(CurDAG->getMachineNode(VCmpInst, dl, ResVT, LHS, RHS), 0);
4417  CurDAG->SelectNodeTo(N, Subtarget->hasVSX() ? PPC::XXLNOR : PPC::VNOR,
4418  ResVT, VCmp, VCmp);
4419  return true;
4420  }
4421 
4422  CurDAG->SelectNodeTo(N, VCmpInst, ResVT, LHS, RHS);
4423  return true;
4424  }
4425 
4426  if (Subtarget->useCRBits())
4427  return false;
4428 
4429  bool Inv;
4430  unsigned Idx = getCRIdxForSetCC(CC, Inv);
4431  SDValue CCReg = SelectCC(LHS, RHS, CC, dl, Chain);
4432  if (IsStrict)
4433  CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 1), CCReg.getValue(1));
4434  SDValue IntCR;
4435 
4436  // SPE e*cmp* instructions only set the 'gt' bit, so hard-code that
4437  // The correct compare instruction is already set by SelectCC()
4438  if (Subtarget->hasSPE() && LHS.getValueType().isFloatingPoint()) {
4439  Idx = 1;
4440  }
4441 
4442  // Force the ccreg into CR7.
4443  SDValue CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
4444 
4445  SDValue InFlag; // Null incoming flag value.
4446  CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, CR7Reg, CCReg,
4447  InFlag).getValue(1);
4448 
4449  IntCR = SDValue(CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32, CR7Reg,
4450  CCReg), 0);
4451 
4452  SDValue Ops[] = { IntCR, getI32Imm((32 - (3 - Idx)) & 31, dl),
4453  getI32Imm(31, dl), getI32Imm(31, dl) };
4454  if (!Inv) {
4455  CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
4456  return true;
4457  }
4458 
4459  // Get the specified bit.
4460  SDValue Tmp =
4461  SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
4462  CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1, dl));
4463  return true;
4464 }
4465 
4466 /// Does this node represent a load/store node whose address can be represented
4467 /// with a register plus an immediate that's a multiple of \p Val:
4468 bool PPCDAGToDAGISel::isOffsetMultipleOf(SDNode *N, unsigned Val) const {
4469  LoadSDNode *LDN = dyn_cast<LoadSDNode>(N);
4470  StoreSDNode *STN = dyn_cast<StoreSDNode>(N);
4471  MemIntrinsicSDNode *MIN = dyn_cast<MemIntrinsicSDNode>(N);
4472  SDValue AddrOp;
4473  if (LDN || (MIN && MIN->getOpcode() == PPCISD::LD_SPLAT))
4474  AddrOp = N->getOperand(1);
4475  else if (STN)
4476  AddrOp = STN->getOperand(2);
4477 
4478  // If the address points a frame object or a frame object with an offset,
4479  // we need to check the object alignment.
4480  short Imm = 0;
4481  if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(
4482  AddrOp.getOpcode() == ISD::ADD ? AddrOp.getOperand(0) :
4483  AddrOp)) {
4484  // If op0 is a frame index that is under aligned, we can't do it either,
4485  // because it is translated to r31 or r1 + slot + offset. We won't know the
4486  // slot number until the stack frame is finalized.
4487  const MachineFrameInfo &MFI = CurDAG->getMachineFunction().getFrameInfo();
4488  unsigned SlotAlign = MFI.getObjectAlign(FI->getIndex()).value();
4489  if ((SlotAlign % Val) != 0)
4490  return false;
4491 
4492  // If we have an offset, we need further check on the offset.
4493  if (AddrOp.getOpcode() != ISD::ADD)
4494  return true;
4495  }
4496 
4497  if (AddrOp.getOpcode() == ISD::ADD)
4498  return isIntS16Immediate(AddrOp.getOperand(1), Imm) && !(Imm % Val);
4499 
4500  // If the address comes from the outside, the offset will be zero.
4501  return AddrOp.getOpcode() == ISD::CopyFromReg;
4502 }
4503 
4504 void PPCDAGToDAGISel::transferMemOperands(SDNode *N, SDNode *Result) {
4505  // Transfer memoperands.
4506  MachineMemOperand *MemOp = cast<MemSDNode>(N)->getMemOperand();
4507  CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
4508 }
4509 
4510 static bool mayUseP9Setb(SDNode *N, const ISD::CondCode &CC, SelectionDAG *DAG,
4511  bool &NeedSwapOps, bool &IsUnCmp) {
4512 
4513  assert(N->getOpcode() == ISD::SELECT_CC && "Expecting a SELECT_CC here.");
4514 
4515  SDValue LHS = N->getOperand(0);
4516  SDValue RHS = N->getOperand(1);
4517  SDValue TrueRes = N->getOperand(2);
4518  SDValue FalseRes = N->getOperand(3);
4519  ConstantSDNode *TrueConst = dyn_cast<ConstantSDNode>(TrueRes);
4520  if (!TrueConst || (N->getSimpleValueType(0) != MVT::i64 &&
4521  N->getSimpleValueType(0) != MVT::i32))
4522  return false;
4523 
4524  // We are looking for any of:
4525  // (select_cc lhs, rhs, 1, (sext (setcc [lr]hs, [lr]hs, cc2)), cc1)
4526  // (select_cc lhs, rhs, -1, (zext (setcc [lr]hs, [lr]hs, cc2)), cc1)
4527  // (select_cc lhs, rhs, 0, (select_cc [lr]hs, [lr]hs, 1, -1, cc2), seteq)
4528  // (select_cc lhs, rhs, 0, (select_cc [lr]hs, [lr]hs, -1, 1, cc2), seteq)
4529  int64_t TrueResVal = TrueConst->getSExtValue();
4530  if ((TrueResVal < -1 || TrueResVal > 1) ||
4531  (TrueResVal == -1 && FalseRes.getOpcode() != ISD::ZERO_EXTEND) ||
4532  (TrueResVal == 1 && FalseRes.getOpcode() != ISD::SIGN_EXTEND) ||
4533  (TrueResVal == 0 &&
4534  (FalseRes.getOpcode() != ISD::SELECT_CC || CC != ISD::SETEQ)))
4535  return false;
4536 
4537  SDValue SetOrSelCC = FalseRes.getOpcode() == ISD::SELECT_CC
4538  ? FalseRes
4539  : FalseRes.getOperand(0);
4540  bool InnerIsSel = SetOrSelCC.getOpcode() == ISD::SELECT_CC;
4541  if (SetOrSelCC.getOpcode() != ISD::SETCC &&
4542  SetOrSelCC.getOpcode() != ISD::SELECT_CC)
4543  return false;
4544 
4545  // Without this setb optimization, the outer SELECT_CC will be manually
4546  // selected to SELECT_CC_I4/SELECT_CC_I8 Pseudo, then expand-isel-pseudos pass
4547  // transforms pseudo instruction to isel instruction. When there are more than
4548  // one use for result like zext/sext, with current optimization we only see
4549  // isel is replaced by setb but can't see any significant gain. Since
4550  // setb has longer latency than original isel, we should avoid this. Another
4551  // point is that setb requires comparison always kept, it can break the
4552  // opportunity to get the comparison away if we have in future.
4553  if (!SetOrSelCC.hasOneUse() || (!InnerIsSel && !FalseRes.hasOneUse()))
4554  return false;
4555 
4556  SDValue InnerLHS = SetOrSelCC.getOperand(0);
4557  SDValue InnerRHS = SetOrSelCC.getOperand(1);
4558  ISD::CondCode InnerCC =
4559  cast<CondCodeSDNode>(SetOrSelCC.getOperand(InnerIsSel ? 4 : 2))->get();
4560  // If the inner comparison is a select_cc, make sure the true/false values are
4561  // 1/-1 and canonicalize it if needed.
4562  if (InnerIsSel) {
4563  ConstantSDNode *SelCCTrueConst =
4564  dyn_cast<ConstantSDNode>(SetOrSelCC.getOperand(2));
4565  ConstantSDNode *SelCCFalseConst =
4566  dyn_cast<ConstantSDNode>(SetOrSelCC.getOperand(3));
4567  if (!SelCCTrueConst || !SelCCFalseConst)
4568  return false;
4569  int64_t SelCCTVal = SelCCTrueConst->getSExtValue();
4570  int64_t SelCCFVal = SelCCFalseConst->getSExtValue();
4571  // The values must be -1/1 (requiring a swap) or 1/-1.
4572  if (SelCCTVal == -1 && SelCCFVal == 1) {
4573  std::swap(InnerLHS, InnerRHS);
4574  } else if (SelCCTVal != 1 || SelCCFVal != -1)
4575  return false;
4576  }
4577 
4578  // Canonicalize unsigned case
4579  if (InnerCC == ISD::SETULT || InnerCC == ISD::SETUGT) {
4580  IsUnCmp = true;
4581  InnerCC = (InnerCC == ISD::SETULT) ? ISD::SETLT : ISD::SETGT;
4582  }
4583 
4584  bool InnerSwapped = false;
4585  if (LHS == InnerRHS && RHS == InnerLHS)
4586  InnerSwapped = true;
4587  else if (LHS != InnerLHS || RHS != InnerRHS)
4588  return false;
4589 
4590  switch (CC) {
4591  // (select_cc lhs, rhs, 0, \
4592  // (select_cc [lr]hs, [lr]hs, 1, -1, setlt/setgt), seteq)
4593  case ISD::SETEQ:
4594  if (!InnerIsSel)
4595  return false;
4596  if (InnerCC != ISD::SETLT && InnerCC != ISD::SETGT)
4597  return false;
4598  NeedSwapOps = (InnerCC == ISD::SETGT) ? InnerSwapped : !InnerSwapped;
4599  break;
4600 
4601  // (select_cc lhs, rhs, -1, (zext (setcc [lr]hs, [lr]hs, setne)), setu?lt)
4602  // (select_cc lhs, rhs, -1, (zext (setcc lhs, rhs, setgt)), setu?lt)
4603  // (select_cc lhs, rhs, -1, (zext (setcc rhs, lhs, setlt)), setu?lt)
4604  // (select_cc lhs, rhs, 1, (sext (setcc [lr]hs, [lr]hs, setne)), setu?lt)
4605  // (select_cc lhs, rhs, 1, (sext (setcc lhs, rhs, setgt)), setu?lt)
4606  // (select_cc lhs, rhs, 1, (sext (setcc rhs, lhs, setlt)), setu?lt)
4607  case ISD::SETULT:
4608  if (!IsUnCmp && InnerCC != ISD::SETNE)
4609  return false;
4610  IsUnCmp = true;
4611  [[fallthrough]];
4612  case ISD::SETLT:
4613  if (InnerCC == ISD::SETNE || (InnerCC == ISD::SETGT && !InnerSwapped) ||
4614  (InnerCC == ISD::SETLT && InnerSwapped))
4615  NeedSwapOps = (TrueResVal == 1);
4616  else
4617  return false;
4618  break;
4619 
4620  // (select_cc lhs, rhs, 1, (sext (setcc [lr]hs, [lr]hs, setne)), setu?gt)
4621  // (select_cc lhs, rhs, 1, (sext (setcc lhs, rhs, setlt)), setu?gt)
4622  // (select_cc lhs, rhs, 1, (sext (setcc rhs, lhs, setgt)), setu?gt)
4623  // (select_cc lhs, rhs, -1, (zext (setcc [lr]hs, [lr]hs, setne)), setu?gt)
4624  // (select_cc lhs, rhs, -1, (zext (setcc lhs, rhs, setlt)), setu?gt)
4625  // (select_cc lhs, rhs, -1, (zext (setcc rhs, lhs, setgt)), setu?gt)
4626  case ISD::SETUGT:
4627  if (!IsUnCmp && InnerCC != ISD::SETNE)
4628  return false;
4629  IsUnCmp = true;
4630  [[fallthrough]];
4631  case ISD::SETGT:
4632  if (InnerCC == ISD::SETNE || (InnerCC == ISD::SETLT && !InnerSwapped) ||
4633  (InnerCC == ISD::SETGT && InnerSwapped))
4634  NeedSwapOps = (TrueResVal == -1);
4635  else
4636  return false;
4637  break;
4638 
4639  default:
4640  return false;
4641  }
4642 
4643  LLVM_DEBUG(dbgs() << "Found a node that can be lowered to a SETB: ");
4644  LLVM_DEBUG(N->dump());
4645 
4646  return true;
4647 }
4648 
4649 // Return true if it's a software square-root/divide operand.
4650 static bool isSWTestOp(SDValue N) {
4651  if (N.getOpcode() == PPCISD::FTSQRT)
4652  return true;
4653  if (N.getNumOperands() < 1 || !isa<ConstantSDNode>(N.getOperand(0)) ||
4654  N.getOpcode() != ISD::INTRINSIC_WO_CHAIN)
4655  return false;
4656  switch (N.getConstantOperandVal(0)) {
4657  case Intrinsic::ppc_vsx_xvtdivdp:
4658  case Intrinsic::ppc_vsx_xvtdivsp:
4659  case Intrinsic::ppc_vsx_xvtsqrtdp:
4660  case Intrinsic::ppc_vsx_xvtsqrtsp:
4661  return true;
4662  }
4663  return false;
4664 }
4665 
4666 bool PPCDAGToDAGISel::tryFoldSWTestBRCC(SDNode *N) {
4667  assert(N->getOpcode() == ISD::BR_CC && "ISD::BR_CC is expected.");
4668  // We are looking for following patterns, where `truncate to i1` actually has
4669  // the same semantic with `and 1`.
4670  // (br_cc seteq, (truncateToi1 SWTestOp), 0) -> (BCC PRED_NU, SWTestOp)
4671  // (br_cc seteq, (and SWTestOp, 2), 0) -> (BCC PRED_NE, SWTestOp)
4672  // (br_cc seteq, (and SWTestOp, 4), 0) -> (BCC PRED_LE, SWTestOp)
4673  // (br_cc seteq, (and SWTestOp, 8), 0) -> (BCC PRED_GE, SWTestOp)
4674  // (br_cc setne, (truncateToi1 SWTestOp), 0) -> (BCC PRED_UN, SWTestOp)
4675  // (br_cc setne, (and SWTestOp, 2), 0) -> (BCC PRED_EQ, SWTestOp)
4676  // (br_cc setne, (and SWTestOp, 4), 0) -> (BCC PRED_GT, SWTestOp)
4677  // (br_cc setne, (and SWTestOp, 8), 0) -> (BCC PRED_LT, SWTestOp)
4678  ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
4679  if (CC != ISD::SETEQ && CC != ISD::SETNE)
4680  return false;
4681 
4682  SDValue CmpRHS = N->getOperand(3);
4683  if (!isa<ConstantSDNode>(CmpRHS) ||
4684  cast<ConstantSDNode>(CmpRHS)->getSExtValue() != 0)
4685  return false;
4686 
4687  SDValue CmpLHS = N->getOperand(2);
4688  if (CmpLHS.getNumOperands() < 1 || !isSWTestOp(CmpLHS.getOperand(0)))
4689  return false;
4690 
4691  unsigned PCC = 0;
4692  bool IsCCNE = CC == ISD::SETNE;
4693  if (CmpLHS.getOpcode() == ISD::AND &&
4694  isa<ConstantSDNode>(CmpLHS.getOperand(1)))
4695  switch (CmpLHS.getConstantOperandVal(1)) {
4696  case 1:
4697  PCC = IsCCNE ? PPC::PRED_UN : PPC::PRED_NU;
4698  break;
4699  case 2:
4700  PCC = IsCCNE ? PPC::PRED_EQ : PPC::PRED_NE;
4701  break;
4702  case 4:
4703  PCC = IsCCNE ? PPC::PRED_GT : PPC::PRED_LE;
4704  break;
4705  case 8:
4706  PCC = IsCCNE ? PPC::PRED_LT : PPC::PRED_GE;
4707  break;
4708  default:
4709  return false;
4710  }
4711  else if (CmpLHS.getOpcode() == ISD::TRUNCATE &&
4712  CmpLHS.getValueType() == MVT::i1)
4713  PCC = IsCCNE ? PPC::PRED_UN : PPC::PRED_NU;
4714 
4715  if (PCC) {
4716  SDLoc dl(N);
4717  SDValue Ops[] = {getI32Imm(PCC, dl), CmpLHS.getOperand(0), N->getOperand(4),
4718  N->getOperand(0)};
4719  CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
4720  return true;
4721  }
4722  return false;
4723 }
4724 
4725 bool PPCDAGToDAGISel::trySelectLoopCountIntrinsic(SDNode *N) {
4726  // Sometimes the promoted value of the intrinsic is ANDed by some non-zero
4727  // value, for example when crbits is disabled. If so, select the
4728  // loop_decrement intrinsics now.
4729  ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
4730  SDValue LHS = N->getOperand(2), RHS = N->getOperand(3);
4731 
4732  if (LHS.getOpcode() != ISD::AND || !isa<ConstantSDNode>(LHS.getOperand(1)) ||
4733  isNullConstant(LHS.getOperand(1)))
4734  return false;
4735 
4736  if (LHS.getOperand(0).getOpcode() != ISD::INTRINSIC_W_CHAIN ||
4737  cast<ConstantSDNode>(LHS.getOperand(0).getOperand(1))->getZExtValue() !=
4738  Intrinsic::loop_decrement)
4739  return false;
4740 
4741  if (!isa<ConstantSDNode>(RHS))
4742  return false;
4743 
4744  assert((CC == ISD::SETEQ || CC == ISD::SETNE) &&
4745  "Counter decrement comparison is not EQ or NE");
4746 
4747  SDValue OldDecrement = LHS.getOperand(0);
4748  assert(OldDecrement.hasOneUse() && "loop decrement has more than one use!");
4749 
4750