blob: dd7b7a345d66db3fc3746f8b2b472ed006ac4ab8 [file] [log] [blame]
//===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines a pattern matching instruction selector for PowerPC,
// converting from a legalized dag to a PPC dag.
//
//===----------------------------------------------------------------------===//
#include "MCTargetDesc/PPCMCTargetDesc.h"
#include "MCTargetDesc/PPCPredicates.h"
#include "PPC.h"
#include "PPCISelLowering.h"
#include "PPCMachineFunctionInfo.h"
#include "PPCSubtarget.h"
#include "PPCTargetMachine.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/IntrinsicsPowerPC.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MachineValueType.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <tuple>
#include <utility>
using namespace llvm;
#define DEBUG_TYPE "ppc-codegen"
STATISTIC(NumSextSetcc,
"Number of (sext(setcc)) nodes expanded into GPR sequence.");
STATISTIC(NumZextSetcc,
"Number of (zext(setcc)) nodes expanded into GPR sequence.");
STATISTIC(SignExtensionsAdded,
"Number of sign extensions for compare inputs added.");
STATISTIC(ZeroExtensionsAdded,
"Number of zero extensions for compare inputs added.");
STATISTIC(NumLogicOpsOnComparison,
"Number of logical ops on i1 values calculated in GPR.");
STATISTIC(OmittedForNonExtendUses,
"Number of compares not eliminated as they have non-extending uses.");
STATISTIC(NumP9Setb,
"Number of compares lowered to setb.");
// FIXME: Remove this once the bug has been fixed!
cl::opt<bool> ANDIGlueBug("expose-ppc-andi-glue-bug",
cl::desc("expose the ANDI glue bug on PPC"), cl::Hidden);
static cl::opt<bool>
UseBitPermRewriter("ppc-use-bit-perm-rewriter", cl::init(true),
cl::desc("use aggressive ppc isel for bit permutations"),
cl::Hidden);
static cl::opt<bool> BPermRewriterNoMasking(
"ppc-bit-perm-rewriter-stress-rotates",
cl::desc("stress rotate selection in aggressive ppc isel for "
"bit permutations"),
cl::Hidden);
static cl::opt<bool> EnableBranchHint(
"ppc-use-branch-hint", cl::init(true),
cl::desc("Enable static hinting of branches on ppc"),
cl::Hidden);
static cl::opt<bool> EnableTLSOpt(
"ppc-tls-opt", cl::init(true),
cl::desc("Enable tls optimization peephole"),
cl::Hidden);
enum ICmpInGPRType { ICGPR_All, ICGPR_None, ICGPR_I32, ICGPR_I64,
ICGPR_NonExtIn, ICGPR_Zext, ICGPR_Sext, ICGPR_ZextI32,
ICGPR_SextI32, ICGPR_ZextI64, ICGPR_SextI64 };
static cl::opt<ICmpInGPRType> CmpInGPR(
"ppc-gpr-icmps", cl::Hidden, cl::init(ICGPR_All),
cl::desc("Specify the types of comparisons to emit GPR-only code for."),
cl::values(clEnumValN(ICGPR_None, "none", "Do not modify integer comparisons."),
clEnumValN(ICGPR_All, "all", "All possible int comparisons in GPRs."),
clEnumValN(ICGPR_I32, "i32", "Only i32 comparisons in GPRs."),
clEnumValN(ICGPR_I64, "i64", "Only i64 comparisons in GPRs."),
clEnumValN(ICGPR_NonExtIn, "nonextin",
"Only comparisons where inputs don't need [sz]ext."),
clEnumValN(ICGPR_Zext, "zext", "Only comparisons with zext result."),
clEnumValN(ICGPR_ZextI32, "zexti32",
"Only i32 comparisons with zext result."),
clEnumValN(ICGPR_ZextI64, "zexti64",
"Only i64 comparisons with zext result."),
clEnumValN(ICGPR_Sext, "sext", "Only comparisons with sext result."),
clEnumValN(ICGPR_SextI32, "sexti32",
"Only i32 comparisons with sext result."),
clEnumValN(ICGPR_SextI64, "sexti64",
"Only i64 comparisons with sext result.")));
namespace {
//===--------------------------------------------------------------------===//
/// PPCDAGToDAGISel - PPC specific code to select PPC machine
/// instructions for SelectionDAG operations.
///
class PPCDAGToDAGISel : public SelectionDAGISel {
const PPCTargetMachine &TM;
const PPCSubtarget *Subtarget = nullptr;
const PPCTargetLowering *PPCLowering = nullptr;
unsigned GlobalBaseReg = 0;
public:
explicit PPCDAGToDAGISel(PPCTargetMachine &tm, CodeGenOpt::Level OptLevel)
: SelectionDAGISel(tm, OptLevel), TM(tm) {}
bool runOnMachineFunction(MachineFunction &MF) override {
// Make sure we re-emit a set of the global base reg if necessary
GlobalBaseReg = 0;
Subtarget = &MF.getSubtarget<PPCSubtarget>();
PPCLowering = Subtarget->getTargetLowering();
SelectionDAGISel::runOnMachineFunction(MF);
return true;
}
void PreprocessISelDAG() override;
void PostprocessISelDAG() override;
/// getI16Imm - Return a target constant with the specified value, of type
/// i16.
inline SDValue getI16Imm(unsigned Imm, const SDLoc &dl) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i16);
}
/// getI32Imm - Return a target constant with the specified value, of type
/// i32.
inline SDValue getI32Imm(unsigned Imm, const SDLoc &dl) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
}
/// getI64Imm - Return a target constant with the specified value, of type
/// i64.
inline SDValue getI64Imm(uint64_t Imm, const SDLoc &dl) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i64);
}
/// getSmallIPtrImm - Return a target constant of pointer type.
inline SDValue getSmallIPtrImm(unsigned Imm, const SDLoc &dl) {
return CurDAG->getTargetConstant(
Imm, dl, PPCLowering->getPointerTy(CurDAG->getDataLayout()));
}
/// isRotateAndMask - Returns true if Mask and Shift can be folded into a
/// rotate and mask opcode and mask operation.
static bool isRotateAndMask(SDNode *N, unsigned Mask, bool isShiftMask,
unsigned &SH, unsigned &MB, unsigned &ME);
/// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
/// base register. Return the virtual register that holds this value.
SDNode *getGlobalBaseReg();
void selectFrameIndex(SDNode *SN, SDNode *N, unsigned Offset = 0);
// Select - Convert the specified operand from a target-independent to a
// target-specific node if it hasn't already been changed.
void Select(SDNode *N) override;
bool tryBitfieldInsert(SDNode *N);
bool tryBitPermutation(SDNode *N);
bool tryIntCompareInGPR(SDNode *N);
// tryTLSXFormLoad - Convert an ISD::LOAD fed by a PPCISD::ADD_TLS into
// an X-Form load instruction with the offset being a relocation coming from
// the PPCISD::ADD_TLS.
bool tryTLSXFormLoad(LoadSDNode *N);
// tryTLSXFormStore - Convert an ISD::STORE fed by a PPCISD::ADD_TLS into
// an X-Form store instruction with the offset being a relocation coming from
// the PPCISD::ADD_TLS.
bool tryTLSXFormStore(StoreSDNode *N);
/// SelectCC - Select a comparison of the specified values with the
/// specified condition code, returning the CR# of the expression.
SDValue SelectCC(SDValue LHS, SDValue RHS, ISD::CondCode CC,
const SDLoc &dl, SDValue Chain = SDValue());
/// SelectAddrImmOffs - Return true if the operand is valid for a preinc
/// immediate field. Note that the operand at this point is already the
/// result of a prior SelectAddressRegImm call.
bool SelectAddrImmOffs(SDValue N, SDValue &Out) const {
if (N.getOpcode() == ISD::TargetConstant ||
N.getOpcode() == ISD::TargetGlobalAddress) {
Out = N;
return true;
}
return false;
}
/// SelectAddrIdx - Given the specified address, check to see if it can be
/// represented as an indexed [r+r] operation.
/// This is for xform instructions whose associated displacement form is D.
/// The last parameter \p 0 means associated D form has no requirment for 16
/// bit signed displacement.
/// Returns false if it can be represented by [r+imm], which are preferred.
bool SelectAddrIdx(SDValue N, SDValue &Base, SDValue &Index) {
return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG, None);
}
/// SelectAddrIdx4 - Given the specified address, check to see if it can be
/// represented as an indexed [r+r] operation.
/// This is for xform instructions whose associated displacement form is DS.
/// The last parameter \p 4 means associated DS form 16 bit signed
/// displacement must be a multiple of 4.
/// Returns false if it can be represented by [r+imm], which are preferred.
bool SelectAddrIdxX4(SDValue N, SDValue &Base, SDValue &Index) {
return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG,
Align(4));
}
/// SelectAddrIdx16 - Given the specified address, check to see if it can be
/// represented as an indexed [r+r] operation.
/// This is for xform instructions whose associated displacement form is DQ.
/// The last parameter \p 16 means associated DQ form 16 bit signed
/// displacement must be a multiple of 16.
/// Returns false if it can be represented by [r+imm], which are preferred.
bool SelectAddrIdxX16(SDValue N, SDValue &Base, SDValue &Index) {
return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG,
Align(16));
}
/// SelectAddrIdxOnly - Given the specified address, force it to be
/// represented as an indexed [r+r] operation.
bool SelectAddrIdxOnly(SDValue N, SDValue &Base, SDValue &Index) {
return PPCLowering->SelectAddressRegRegOnly(N, Base, Index, *CurDAG);
}
/// SelectAddrImm - Returns true if the address N can be represented by
/// a base register plus a signed 16-bit displacement [r+imm].
/// The last parameter \p 0 means D form has no requirment for 16 bit signed
/// displacement.
bool SelectAddrImm(SDValue N, SDValue &Disp,
SDValue &Base) {
return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, None);
}
/// SelectAddrImmX4 - Returns true if the address N can be represented by
/// a base register plus a signed 16-bit displacement that is a multiple of
/// 4 (last parameter). Suitable for use by STD and friends.
bool SelectAddrImmX4(SDValue N, SDValue &Disp, SDValue &Base) {
return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, Align(4));
}
/// SelectAddrImmX16 - Returns true if the address N can be represented by
/// a base register plus a signed 16-bit displacement that is a multiple of
/// 16(last parameter). Suitable for use by STXV and friends.
bool SelectAddrImmX16(SDValue N, SDValue &Disp, SDValue &Base) {
return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG,
Align(16));
}
/// SelectAddrImmX34 - Returns true if the address N can be represented by
/// a base register plus a signed 34-bit displacement. Suitable for use by
/// PSTXVP and friends.
bool SelectAddrImmX34(SDValue N, SDValue &Disp, SDValue &Base) {
return PPCLowering->SelectAddressRegImm34(N, Disp, Base, *CurDAG);
}
// Select an address into a single register.
bool SelectAddr(SDValue N, SDValue &Base) {
Base = N;
return true;
}
bool SelectAddrPCRel(SDValue N, SDValue &Base) {
return PPCLowering->SelectAddressPCRel(N, Base);
}
/// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
/// inline asm expressions. It is always correct to compute the value into
/// a register. The case of adding a (possibly relocatable) constant to a
/// register can be improved, but it is wrong to substitute Reg+Reg for
/// Reg in an asm, because the load or store opcode would have to change.
bool SelectInlineAsmMemoryOperand(const SDValue &Op,
unsigned ConstraintID,
std::vector<SDValue> &OutOps) override {
switch(ConstraintID) {
default:
errs() << "ConstraintID: " << ConstraintID << "\n";
llvm_unreachable("Unexpected asm memory constraint");
case InlineAsm::Constraint_es:
case InlineAsm::Constraint_m:
case InlineAsm::Constraint_o:
case InlineAsm::Constraint_Q:
case InlineAsm::Constraint_Z:
case InlineAsm::Constraint_Zy:
// We need to make sure that this one operand does not end up in r0
// (because we might end up lowering this as 0(%op)).
const TargetRegisterInfo *TRI = Subtarget->getRegisterInfo();
const TargetRegisterClass *TRC = TRI->getPointerRegClass(*MF, /*Kind=*/1);
SDLoc dl(Op);
SDValue RC = CurDAG->getTargetConstant(TRC->getID(), dl, MVT::i32);
SDValue NewOp =
SDValue(CurDAG->getMachineNode(TargetOpcode::COPY_TO_REGCLASS,
dl, Op.getValueType(),
Op, RC), 0);
OutOps.push_back(NewOp);
return false;
}
return true;
}
StringRef getPassName() const override {
return "PowerPC DAG->DAG Pattern Instruction Selection";
}
// Include the pieces autogenerated from the target description.
#include "PPCGenDAGISel.inc"
private:
bool trySETCC(SDNode *N);
bool tryFoldSWTestBRCC(SDNode *N);
bool tryAsSingleRLDICL(SDNode *N);
bool tryAsSingleRLDICR(SDNode *N);
bool tryAsSingleRLWINM(SDNode *N);
bool tryAsSingleRLWINM8(SDNode *N);
bool tryAsSingleRLWIMI(SDNode *N);
bool tryAsPairOfRLDICL(SDNode *N);
bool tryAsSingleRLDIMI(SDNode *N);
void PeepholePPC64();
void PeepholePPC64ZExt();
void PeepholeCROps();
SDValue combineToCMPB(SDNode *N);
void foldBoolExts(SDValue &Res, SDNode *&N);
bool AllUsersSelectZero(SDNode *N);
void SwapAllSelectUsers(SDNode *N);
bool isOffsetMultipleOf(SDNode *N, unsigned Val) const;
void transferMemOperands(SDNode *N, SDNode *Result);
};
} // end anonymous namespace
/// getGlobalBaseReg - Output the instructions required to put the
/// base address to use for accessing globals into a register.
///
SDNode *PPCDAGToDAGISel::getGlobalBaseReg() {
if (!GlobalBaseReg) {
const TargetInstrInfo &TII = *Subtarget->getInstrInfo();
// Insert the set of GlobalBaseReg into the first MBB of the function
MachineBasicBlock &FirstMBB = MF->front();
MachineBasicBlock::iterator MBBI = FirstMBB.begin();
const Module *M = MF->getFunction().getParent();
DebugLoc dl;
if (PPCLowering->getPointerTy(CurDAG->getDataLayout()) == MVT::i32) {
if (Subtarget->isTargetELF()) {
GlobalBaseReg = PPC::R30;
if (!Subtarget->isSecurePlt() &&
M->getPICLevel() == PICLevel::SmallPIC) {
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MoveGOTtoLR));
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
} else {
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
Register TempReg = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
BuildMI(FirstMBB, MBBI, dl,
TII.get(PPC::UpdateGBR), GlobalBaseReg)
.addReg(TempReg, RegState::Define).addReg(GlobalBaseReg);
MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
}
} else {
GlobalBaseReg =
RegInfo->createVirtualRegister(&PPC::GPRC_and_GPRC_NOR0RegClass);
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
}
} else {
// We must ensure that this sequence is dominated by the prologue.
// FIXME: This is a bit of a big hammer since we don't get the benefits
// of shrink-wrapping whenever we emit this instruction. Considering
// this is used in any function where we emit a jump table, this may be
// a significant limitation. We should consider inserting this in the
// block where it is used and then commoning this sequence up if it
// appears in multiple places.
// Note: on ISA 3.0 cores, we can use lnia (addpcis) instead of
// MovePCtoLR8.
MF->getInfo<PPCFunctionInfo>()->setShrinkWrapDisabled(true);
GlobalBaseReg = RegInfo->createVirtualRegister(&PPC::G8RC_and_G8RC_NOX0RegClass);
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR8));
BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR8), GlobalBaseReg);
}
}
return CurDAG->getRegister(GlobalBaseReg,
PPCLowering->getPointerTy(CurDAG->getDataLayout()))
.getNode();
}
/// isInt32Immediate - This method tests to see if the node is a 32-bit constant
/// operand. If so Imm will receive the 32-bit value.
static bool isInt32Immediate(SDNode *N, unsigned &Imm) {
if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
Imm = cast<ConstantSDNode>(N)->getZExtValue();
return true;
}
return false;
}
/// isInt64Immediate - This method tests to see if the node is a 64-bit constant
/// operand. If so Imm will receive the 64-bit value.
static bool isInt64Immediate(SDNode *N, uint64_t &Imm) {
if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i64) {
Imm = cast<ConstantSDNode>(N)->getZExtValue();
return true;
}
return false;
}
// isInt32Immediate - This method tests to see if a constant operand.
// If so Imm will receive the 32 bit value.
static bool isInt32Immediate(SDValue N, unsigned &Imm) {
return isInt32Immediate(N.getNode(), Imm);
}
/// isInt64Immediate - This method tests to see if the value is a 64-bit
/// constant operand. If so Imm will receive the 64-bit value.
static bool isInt64Immediate(SDValue N, uint64_t &Imm) {
return isInt64Immediate(N.getNode(), Imm);
}
static unsigned getBranchHint(unsigned PCC,
const FunctionLoweringInfo &FuncInfo,
const SDValue &DestMBB) {
assert(isa<BasicBlockSDNode>(DestMBB));
if (!FuncInfo.BPI) return PPC::BR_NO_HINT;
const BasicBlock *BB = FuncInfo.MBB->getBasicBlock();
const Instruction *BBTerm = BB->getTerminator();
if (BBTerm->getNumSuccessors() != 2) return PPC::BR_NO_HINT;
const BasicBlock *TBB = BBTerm->getSuccessor(0);
const BasicBlock *FBB = BBTerm->getSuccessor(1);
auto TProb = FuncInfo.BPI->getEdgeProbability(BB, TBB);
auto FProb = FuncInfo.BPI->getEdgeProbability(BB, FBB);
// We only want to handle cases which are easy to predict at static time, e.g.
// C++ throw statement, that is very likely not taken, or calling never
// returned function, e.g. stdlib exit(). So we set Threshold to filter
// unwanted cases.
//
// Below is LLVM branch weight table, we only want to handle case 1, 2
//
// Case Taken:Nontaken Example
// 1. Unreachable 1048575:1 C++ throw, stdlib exit(),
// 2. Invoke-terminating 1:1048575
// 3. Coldblock 4:64 __builtin_expect
// 4. Loop Branch 124:4 For loop
// 5. PH/ZH/FPH 20:12
const uint32_t Threshold = 10000;
if (std::max(TProb, FProb) / Threshold < std::min(TProb, FProb))
return PPC::BR_NO_HINT;
LLVM_DEBUG(dbgs() << "Use branch hint for '" << FuncInfo.Fn->getName()
<< "::" << BB->getName() << "'\n"
<< " -> " << TBB->getName() << ": " << TProb << "\n"
<< " -> " << FBB->getName() << ": " << FProb << "\n");
const BasicBlockSDNode *BBDN = cast<BasicBlockSDNode>(DestMBB);
// If Dest BasicBlock is False-BasicBlock (FBB), swap branch probabilities,
// because we want 'TProb' stands for 'branch probability' to Dest BasicBlock
if (BBDN->getBasicBlock()->getBasicBlock() != TBB)
std::swap(TProb, FProb);
return (TProb > FProb) ? PPC::BR_TAKEN_HINT : PPC::BR_NONTAKEN_HINT;
}
// isOpcWithIntImmediate - This method tests to see if the node is a specific
// opcode and that it has a immediate integer right operand.
// If so Imm will receive the 32 bit value.
static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
return N->getOpcode() == Opc
&& isInt32Immediate(N->getOperand(1).getNode(), Imm);
}
void PPCDAGToDAGISel::selectFrameIndex(SDNode *SN, SDNode *N, unsigned Offset) {
SDLoc dl(SN);
int FI = cast<FrameIndexSDNode>(N)->getIndex();
SDValue TFI = CurDAG->getTargetFrameIndex(FI, N->getValueType(0));
unsigned Opc = N->getValueType(0) == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
if (SN->hasOneUse())
CurDAG->SelectNodeTo(SN, Opc, N->getValueType(0), TFI,
getSmallIPtrImm(Offset, dl));
else
ReplaceNode(SN, CurDAG->getMachineNode(Opc, dl, N->getValueType(0), TFI,
getSmallIPtrImm(Offset, dl)));
}
bool PPCDAGToDAGISel::isRotateAndMask(SDNode *N, unsigned Mask,
bool isShiftMask, unsigned &SH,
unsigned &MB, unsigned &ME) {
// Don't even go down this path for i64, since different logic will be
// necessary for rldicl/rldicr/rldimi.
if (N->getValueType(0) != MVT::i32)
return false;
unsigned Shift = 32;
unsigned Indeterminant = ~0; // bit mask marking indeterminant results
unsigned Opcode = N->getOpcode();
if (N->getNumOperands() != 2 ||
!isInt32Immediate(N->getOperand(1).getNode(), Shift) || (Shift > 31))
return false;
if (Opcode == ISD::SHL) {
// apply shift left to mask if it comes first
if (isShiftMask) Mask = Mask << Shift;
// determine which bits are made indeterminant by shift
Indeterminant = ~(0xFFFFFFFFu << Shift);
} else if (Opcode == ISD::SRL) {
// apply shift right to mask if it comes first
if (isShiftMask) Mask = Mask >> Shift;
// determine which bits are made indeterminant by shift
Indeterminant = ~(0xFFFFFFFFu >> Shift);
// adjust for the left rotate
Shift = 32 - Shift;
} else if (Opcode == ISD::ROTL) {
Indeterminant = 0;
} else {
return false;
}
// if the mask doesn't intersect any Indeterminant bits
if (Mask && !(Mask & Indeterminant)) {
SH = Shift & 31;
// make sure the mask is still a mask (wrap arounds may not be)
return isRunOfOnes(Mask, MB, ME);
}
return false;
}
bool PPCDAGToDAGISel::tryTLSXFormStore(StoreSDNode *ST) {
SDValue Base = ST->getBasePtr();
if (Base.getOpcode() != PPCISD::ADD_TLS)
return false;
SDValue Offset = ST->getOffset();
if (!Offset.isUndef())
return false;
if (Base.getOperand(1).getOpcode() == PPCISD::TLS_LOCAL_EXEC_MAT_ADDR)
return false;
SDLoc dl(ST);
EVT MemVT = ST->getMemoryVT();
EVT RegVT = ST->getValue().getValueType();
unsigned Opcode;
switch (MemVT.getSimpleVT().SimpleTy) {
default:
return false;
case MVT::i8: {
Opcode = (RegVT == MVT::i32) ? PPC::STBXTLS_32 : PPC::STBXTLS;
break;
}
case MVT::i16: {
Opcode = (RegVT == MVT::i32) ? PPC::STHXTLS_32 : PPC::STHXTLS;
break;
}
case MVT::i32: {
Opcode = (RegVT == MVT::i32) ? PPC::STWXTLS_32 : PPC::STWXTLS;
break;
}
case MVT::i64: {
Opcode = PPC::STDXTLS;
break;
}
}
SDValue Chain = ST->getChain();
SDVTList VTs = ST->getVTList();
SDValue Ops[] = {ST->getValue(), Base.getOperand(0), Base.getOperand(1),
Chain};
SDNode *MN = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
transferMemOperands(ST, MN);
ReplaceNode(ST, MN);
return true;
}
bool PPCDAGToDAGISel::tryTLSXFormLoad(LoadSDNode *LD) {
SDValue Base = LD->getBasePtr();
if (Base.getOpcode() != PPCISD::ADD_TLS)
return false;
SDValue Offset = LD->getOffset();
if (!Offset.isUndef())
return false;
if (Base.getOperand(1).getOpcode() == PPCISD::TLS_LOCAL_EXEC_MAT_ADDR)
return false;
SDLoc dl(LD);
EVT MemVT = LD->getMemoryVT();
EVT RegVT = LD->getValueType(0);
unsigned Opcode;
switch (MemVT.getSimpleVT().SimpleTy) {
default:
return false;
case MVT::i8: {
Opcode = (RegVT == MVT::i32) ? PPC::LBZXTLS_32 : PPC::LBZXTLS;
break;
}
case MVT::i16: {
Opcode = (RegVT == MVT::i32) ? PPC::LHZXTLS_32 : PPC::LHZXTLS;
break;
}
case MVT::i32: {
Opcode = (RegVT == MVT::i32) ? PPC::LWZXTLS_32 : PPC::LWZXTLS;
break;
}
case MVT::i64: {
Opcode = PPC::LDXTLS;
break;
}
}
SDValue Chain = LD->getChain();
SDVTList VTs = LD->getVTList();
SDValue Ops[] = {Base.getOperand(0), Base.getOperand(1), Chain};
SDNode *MN = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
transferMemOperands(LD, MN);
ReplaceNode(LD, MN);
return true;
}
/// Turn an or of two masked values into the rotate left word immediate then
/// mask insert (rlwimi) instruction.
bool PPCDAGToDAGISel::tryBitfieldInsert(SDNode *N) {
SDValue Op0 = N->getOperand(0);
SDValue Op1 = N->getOperand(1);
SDLoc dl(N);
KnownBits LKnown = CurDAG->computeKnownBits(Op0);
KnownBits RKnown = CurDAG->computeKnownBits(Op1);
unsigned TargetMask = LKnown.Zero.getZExtValue();
unsigned InsertMask = RKnown.Zero.getZExtValue();
if ((TargetMask | InsertMask) == 0xFFFFFFFF) {
unsigned Op0Opc = Op0.getOpcode();
unsigned Op1Opc = Op1.getOpcode();
unsigned Value, SH = 0;
TargetMask = ~TargetMask;
InsertMask = ~InsertMask;
// If the LHS has a foldable shift and the RHS does not, then swap it to the
// RHS so that we can fold the shift into the insert.
if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
Op0.getOperand(0).getOpcode() == ISD::SRL) {
if (Op1.getOperand(0).getOpcode() != ISD::SHL &&
Op1.getOperand(0).getOpcode() != ISD::SRL) {
std::swap(Op0, Op1);
std::swap(Op0Opc, Op1Opc);
std::swap(TargetMask, InsertMask);
}
}
} else if (Op0Opc == ISD::SHL || Op0Opc == ISD::SRL) {
if (Op1Opc == ISD::AND && Op1.getOperand(0).getOpcode() != ISD::SHL &&
Op1.getOperand(0).getOpcode() != ISD::SRL) {
std::swap(Op0, Op1);
std::swap(Op0Opc, Op1Opc);
std::swap(TargetMask, InsertMask);
}
}
unsigned MB, ME;
if (isRunOfOnes(InsertMask, MB, ME)) {
if ((Op1Opc == ISD::SHL || Op1Opc == ISD::SRL) &&
isInt32Immediate(Op1.getOperand(1), Value)) {
Op1 = Op1.getOperand(0);
SH = (Op1Opc == ISD::SHL) ? Value : 32 - Value;
}
if (Op1Opc == ISD::AND) {
// The AND mask might not be a constant, and we need to make sure that
// if we're going to fold the masking with the insert, all bits not
// know to be zero in the mask are known to be one.
KnownBits MKnown = CurDAG->computeKnownBits(Op1.getOperand(1));
bool CanFoldMask = InsertMask == MKnown.One.getZExtValue();
unsigned SHOpc = Op1.getOperand(0).getOpcode();
if ((SHOpc == ISD::SHL || SHOpc == ISD::SRL) && CanFoldMask &&
isInt32Immediate(Op1.getOperand(0).getOperand(1), Value)) {
// Note that Value must be in range here (less than 32) because
// otherwise there would not be any bits set in InsertMask.
Op1 = Op1.getOperand(0).getOperand(0);
SH = (SHOpc == ISD::SHL) ? Value : 32 - Value;
}
}
SH &= 31;
SDValue Ops[] = { Op0, Op1, getI32Imm(SH, dl), getI32Imm(MB, dl),
getI32Imm(ME, dl) };
ReplaceNode(N, CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops));
return true;
}
}
return false;
}
static unsigned allUsesTruncate(SelectionDAG *CurDAG, SDNode *N) {
unsigned MaxTruncation = 0;
// Cannot use range-based for loop here as we need the actual use (i.e. we
// need the operand number corresponding to the use). A range-based for
// will unbox the use and provide an SDNode*.
for (SDNode::use_iterator Use = N->use_begin(), UseEnd = N->use_end();
Use != UseEnd; ++Use) {
unsigned Opc =
Use->isMachineOpcode() ? Use->getMachineOpcode() : Use->getOpcode();
switch (Opc) {
default: return 0;
case ISD::TRUNCATE:
if (Use->isMachineOpcode())
return 0;
MaxTruncation =
std::max(MaxTruncation, (unsigned)Use->getValueType(0).getSizeInBits());
continue;
case ISD::STORE: {
if (Use->isMachineOpcode())
return 0;
StoreSDNode *STN = cast<StoreSDNode>(*Use);
unsigned MemVTSize = STN->getMemoryVT().getSizeInBits();
if (MemVTSize == 64 || Use.getOperandNo() != 0)
return 0;
MaxTruncation = std::max(MaxTruncation, MemVTSize);
continue;
}
case PPC::STW8:
case PPC::STWX8:
case PPC::STWU8:
case PPC::STWUX8:
if (Use.getOperandNo() != 0)
return 0;
MaxTruncation = std::max(MaxTruncation, 32u);
continue;
case PPC::STH8:
case PPC::STHX8:
case PPC::STHU8:
case PPC::STHUX8:
if (Use.getOperandNo() != 0)
return 0;
MaxTruncation = std::max(MaxTruncation, 16u);
continue;
case PPC::STB8:
case PPC::STBX8:
case PPC::STBU8:
case PPC::STBUX8:
if (Use.getOperandNo() != 0)
return 0;
MaxTruncation = std::max(MaxTruncation, 8u);
continue;
}
}
return MaxTruncation;
}
// For any 32 < Num < 64, check if the Imm contains at least Num consecutive
// zeros and return the number of bits by the left of these consecutive zeros.
static int findContiguousZerosAtLeast(uint64_t Imm, unsigned Num) {
unsigned HiTZ = countTrailingZeros<uint32_t>(Hi_32(Imm));
unsigned LoLZ = countLeadingZeros<uint32_t>(Lo_32(Imm));
if ((HiTZ + LoLZ) >= Num)
return (32 + HiTZ);
return 0;
}
// Direct materialization of 64-bit constants by enumerated patterns.
static SDNode *selectI64ImmDirect(SelectionDAG *CurDAG, const SDLoc &dl,
uint64_t Imm, unsigned &InstCnt) {
unsigned TZ = countTrailingZeros<uint64_t>(Imm);
unsigned LZ = countLeadingZeros<uint64_t>(Imm);
unsigned TO = countTrailingOnes<uint64_t>(Imm);
unsigned LO = countLeadingOnes<uint64_t>(Imm);
unsigned Hi32 = Hi_32(Imm);
unsigned Lo32 = Lo_32(Imm);
SDNode *Result = nullptr;
unsigned Shift = 0;
auto getI32Imm = [CurDAG, dl](unsigned Imm) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
};
// Following patterns use 1 instructions to materialize the Imm.
InstCnt = 1;
// 1-1) Patterns : {zeros}{15-bit valve}
// {ones}{15-bit valve}
if (isInt<16>(Imm)) {
SDValue SDImm = CurDAG->getTargetConstant(Imm, dl, MVT::i64);
return CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
}
// 1-2) Patterns : {zeros}{15-bit valve}{16 zeros}
// {ones}{15-bit valve}{16 zeros}
if (TZ > 15 && (LZ > 32 || LO > 32))
return CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64,
getI32Imm((Imm >> 16) & 0xffff));
// Following patterns use 2 instructions to materialize the Imm.
InstCnt = 2;
assert(LZ < 64 && "Unexpected leading zeros here.");
// Count of ones follwing the leading zeros.
unsigned FO = countLeadingOnes<uint64_t>(Imm << LZ);
// 2-1) Patterns : {zeros}{31-bit value}
// {ones}{31-bit value}
if (isInt<32>(Imm)) {
uint64_t ImmHi16 = (Imm >> 16) & 0xffff;
unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
return CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(Imm & 0xffff));
}
// 2-2) Patterns : {zeros}{ones}{15-bit value}{zeros}
// {zeros}{15-bit value}{zeros}
// {zeros}{ones}{15-bit value}
// {ones}{15-bit value}{zeros}
// We can take advantage of LI's sign-extension semantics to generate leading
// ones, and then use RLDIC to mask off the ones in both sides after rotation.
if ((LZ + FO + TZ) > 48) {
Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
getI32Imm((Imm >> TZ) & 0xffff));
return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(TZ), getI32Imm(LZ));
}
// 2-3) Pattern : {zeros}{15-bit value}{ones}
// Shift right the Imm by (48 - LZ) bits to construct a negtive 16 bits value,
// therefore we can take advantage of LI's sign-extension semantics, and then
// mask them off after rotation.
//
// +--LZ--||-15-bit-||--TO--+ +-------------|--16-bit--+
// |00000001bbbbbbbbb1111111| -> |00000000000001bbbbbbbbb1|
// +------------------------+ +------------------------+
// 63 0 63 0
// Imm (Imm >> (48 - LZ) & 0xffff)
// +----sext-----|--16-bit--+ +clear-|-----------------+
// |11111111111111bbbbbbbbb1| -> |00000001bbbbbbbbb1111111|
// +------------------------+ +------------------------+
// 63 0 63 0
// LI8: sext many leading zeros RLDICL: rotate left (48 - LZ), clear left LZ
if ((LZ + TO) > 48) {
// Since the immediates with (LZ > 32) have been handled by previous
// patterns, here we have (LZ <= 32) to make sure we will not shift right
// the Imm by a negative value.
assert(LZ <= 32 && "Unexpected shift value.");
Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
getI32Imm((Imm >> (48 - LZ) & 0xffff)));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(48 - LZ), getI32Imm(LZ));
}
// 2-4) Patterns : {zeros}{ones}{15-bit value}{ones}
// {ones}{15-bit value}{ones}
// We can take advantage of LI's sign-extension semantics to generate leading
// ones, and then use RLDICL to mask off the ones in left sides (if required)
// after rotation.
//
// +-LZ-FO||-15-bit-||--TO--+ +-------------|--16-bit--+
// |00011110bbbbbbbbb1111111| -> |000000000011110bbbbbbbbb|
// +------------------------+ +------------------------+
// 63 0 63 0
// Imm (Imm >> TO) & 0xffff
// +----sext-----|--16-bit--+ +LZ|---------------------+
// |111111111111110bbbbbbbbb| -> |00011110bbbbbbbbb1111111|
// +------------------------+ +------------------------+
// 63 0 63 0
// LI8: sext many leading zeros RLDICL: rotate left TO, clear left LZ
if ((LZ + FO + TO) > 48) {
Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
getI32Imm((Imm >> TO) & 0xffff));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(TO), getI32Imm(LZ));
}
// 2-5) Pattern : {32 zeros}{****}{0}{15-bit value}
// If Hi32 is zero and the Lo16(in Lo32) can be presented as a positive 16 bit
// value, we can use LI for Lo16 without generating leading ones then add the
// Hi16(in Lo32).
if (LZ == 32 && ((Lo32 & 0x8000) == 0)) {
Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
getI32Imm(Lo32 & 0xffff));
return CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(Lo32 >> 16));
}
// 2-6) Patterns : {******}{49 zeros}{******}
// {******}{49 ones}{******}
// If the Imm contains 49 consecutive zeros/ones, it means that a total of 15
// bits remain on both sides. Rotate right the Imm to construct an int<16>
// value, use LI for int<16> value and then use RLDICL without mask to rotate
// it back.
//
// 1) findContiguousZerosAtLeast(Imm, 49)
// +------|--zeros-|------+ +---ones--||---15 bit--+
// |bbbbbb0000000000aaaaaa| -> |0000000000aaaaaabbbbbb|
// +----------------------+ +----------------------+
// 63 0 63 0
//
// 2) findContiguousZerosAtLeast(~Imm, 49)
// +------|--ones--|------+ +---ones--||---15 bit--+
// |bbbbbb1111111111aaaaaa| -> |1111111111aaaaaabbbbbb|
// +----------------------+ +----------------------+
// 63 0 63 0
if ((Shift = findContiguousZerosAtLeast(Imm, 49)) ||
(Shift = findContiguousZerosAtLeast(~Imm, 49))) {
uint64_t RotImm = APInt(64, Imm).rotr(Shift).getZExtValue();
Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64,
getI32Imm(RotImm & 0xffff));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(Shift), getI32Imm(0));
}
// Following patterns use 3 instructions to materialize the Imm.
InstCnt = 3;
// 3-1) Patterns : {zeros}{ones}{31-bit value}{zeros}
// {zeros}{31-bit value}{zeros}
// {zeros}{ones}{31-bit value}
// {ones}{31-bit value}{zeros}
// We can take advantage of LIS's sign-extension semantics to generate leading
// ones, add the remaining bits with ORI, and then use RLDIC to mask off the
// ones in both sides after rotation.
if ((LZ + FO + TZ) > 32) {
uint64_t ImmHi16 = (Imm >> (TZ + 16)) & 0xffff;
unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm((Imm >> TZ) & 0xffff));
return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(TZ), getI32Imm(LZ));
}
// 3-2) Pattern : {zeros}{31-bit value}{ones}
// Shift right the Imm by (32 - LZ) bits to construct a negtive 32 bits value,
// therefore we can take advantage of LIS's sign-extension semantics, add
// the remaining bits with ORI, and then mask them off after rotation.
// This is similar to Pattern 2-3, please refer to the diagram there.
if ((LZ + TO) > 32) {
// Since the immediates with (LZ > 32) have been handled by previous
// patterns, here we have (LZ <= 32) to make sure we will not shift right
// the Imm by a negative value.
assert(LZ <= 32 && "Unexpected shift value.");
Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64,
getI32Imm((Imm >> (48 - LZ)) & 0xffff));
Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm((Imm >> (32 - LZ)) & 0xffff));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(32 - LZ), getI32Imm(LZ));
}
// 3-3) Patterns : {zeros}{ones}{31-bit value}{ones}
// {ones}{31-bit value}{ones}
// We can take advantage of LIS's sign-extension semantics to generate leading
// ones, add the remaining bits with ORI, and then use RLDICL to mask off the
// ones in left sides (if required) after rotation.
// This is similar to Pattern 2-4, please refer to the diagram there.
if ((LZ + FO + TO) > 32) {
Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64,
getI32Imm((Imm >> (TO + 16)) & 0xffff));
Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm((Imm >> TO) & 0xffff));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(TO), getI32Imm(LZ));
}
// 3-4) Patterns : High word == Low word
if (Hi32 == Lo32) {
// Handle the first 32 bits.
uint64_t ImmHi16 = (Lo32 >> 16) & 0xffff;
unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(Lo32 & 0xffff));
// Use rldimi to insert the Low word into High word.
SDValue Ops[] = {SDValue(Result, 0), SDValue(Result, 0), getI32Imm(32),
getI32Imm(0)};
return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
}
// 3-5) Patterns : {******}{33 zeros}{******}
// {******}{33 ones}{******}
// If the Imm contains 33 consecutive zeros/ones, it means that a total of 31
// bits remain on both sides. Rotate right the Imm to construct an int<32>
// value, use LIS + ORI for int<32> value and then use RLDICL without mask to
// rotate it back.
// This is similar to Pattern 2-6, please refer to the diagram there.
if ((Shift = findContiguousZerosAtLeast(Imm, 33)) ||
(Shift = findContiguousZerosAtLeast(~Imm, 33))) {
uint64_t RotImm = APInt(64, Imm).rotr(Shift).getZExtValue();
uint64_t ImmHi16 = (RotImm >> 16) & 0xffff;
unsigned Opcode = ImmHi16 ? PPC::LIS8 : PPC::LI8;
Result = CurDAG->getMachineNode(Opcode, dl, MVT::i64, getI32Imm(ImmHi16));
Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(RotImm & 0xffff));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(Shift), getI32Imm(0));
}
InstCnt = 0;
return nullptr;
}
// Try to select instructions to generate a 64 bit immediate using prefix as
// well as non prefix instructions. The function will return the SDNode
// to materialize that constant or it will return nullptr if it does not
// find one. The variable InstCnt is set to the number of instructions that
// were selected.
static SDNode *selectI64ImmDirectPrefix(SelectionDAG *CurDAG, const SDLoc &dl,
uint64_t Imm, unsigned &InstCnt) {
unsigned TZ = countTrailingZeros<uint64_t>(Imm);
unsigned LZ = countLeadingZeros<uint64_t>(Imm);
unsigned TO = countTrailingOnes<uint64_t>(Imm);
unsigned FO = countLeadingOnes<uint64_t>(LZ == 64 ? 0 : (Imm << LZ));
unsigned Hi32 = Hi_32(Imm);
unsigned Lo32 = Lo_32(Imm);
auto getI32Imm = [CurDAG, dl](unsigned Imm) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
};
auto getI64Imm = [CurDAG, dl](uint64_t Imm) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i64);
};
// Following patterns use 1 instruction to materialize Imm.
InstCnt = 1;
// The pli instruction can materialize up to 34 bits directly.
// It is defined in the TD file and so we just return the constant.
if (isInt<34>(Imm))
return cast<ConstantSDNode>(CurDAG->getConstant(Imm, dl, MVT::i64));
// Require at least two instructions.
InstCnt = 2;
SDNode *Result = nullptr;
// Patterns : {zeros}{ones}{33-bit value}{zeros}
// {zeros}{33-bit value}{zeros}
// {zeros}{ones}{33-bit value}
// {ones}{33-bit value}{zeros}
// We can take advantage of PLI's sign-extension semantics to generate leading
// ones, and then use RLDIC to mask off the ones on both sides after rotation.
if ((LZ + FO + TZ) > 30) {
APInt SignedInt34 = APInt(34, (Imm >> TZ) & 0x3ffffffff);
APInt Extended = SignedInt34.sext(64);
Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
getI64Imm(*Extended.getRawData()));
return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(TZ), getI32Imm(LZ));
}
// Pattern : {zeros}{33-bit value}{ones}
// Shift right the Imm by (30 - LZ) bits to construct a negative 34 bit value,
// therefore we can take advantage of PLI's sign-extension semantics, and then
// mask them off after rotation.
//
// +--LZ--||-33-bit-||--TO--+ +-------------|--34-bit--+
// |00000001bbbbbbbbb1111111| -> |00000000000001bbbbbbbbb1|
// +------------------------+ +------------------------+
// 63 0 63 0
//
// +----sext-----|--34-bit--+ +clear-|-----------------+
// |11111111111111bbbbbbbbb1| -> |00000001bbbbbbbbb1111111|
// +------------------------+ +------------------------+
// 63 0 63 0
if ((LZ + TO) > 30) {
APInt SignedInt34 = APInt(34, (Imm >> (30 - LZ)) & 0x3ffffffff);
APInt Extended = SignedInt34.sext(64);
Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
getI64Imm(*Extended.getRawData()));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(30 - LZ), getI32Imm(LZ));
}
// Patterns : {zeros}{ones}{33-bit value}{ones}
// {ones}{33-bit value}{ones}
// Similar to LI we can take advantage of PLI's sign-extension semantics to
// generate leading ones, and then use RLDICL to mask off the ones in left
// sides (if required) after rotation.
if ((LZ + FO + TO) > 30) {
APInt SignedInt34 = APInt(34, (Imm >> TO) & 0x3ffffffff);
APInt Extended = SignedInt34.sext(64);
Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
getI64Imm(*Extended.getRawData()));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(TO), getI32Imm(LZ));
}
// Patterns : {******}{31 zeros}{******}
// : {******}{31 ones}{******}
// If Imm contains 31 consecutive zeros/ones then the remaining bit count
// is 33. Rotate right the Imm to construct a int<33> value, we can use PLI
// for the int<33> value and then use RLDICL without a mask to rotate it back.
//
// +------|--ones--|------+ +---ones--||---33 bit--+
// |bbbbbb1111111111aaaaaa| -> |1111111111aaaaaabbbbbb|
// +----------------------+ +----------------------+
// 63 0 63 0
for (unsigned Shift = 0; Shift < 63; ++Shift) {
uint64_t RotImm = APInt(64, Imm).rotr(Shift).getZExtValue();
if (isInt<34>(RotImm)) {
Result =
CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(RotImm));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
SDValue(Result, 0), getI32Imm(Shift),
getI32Imm(0));
}
}
// Patterns : High word == Low word
// This is basically a splat of a 32 bit immediate.
if (Hi32 == Lo32) {
Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Hi32));
SDValue Ops[] = {SDValue(Result, 0), SDValue(Result, 0), getI32Imm(32),
getI32Imm(0)};
return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
}
InstCnt = 3;
// Catch-all
// This pattern can form any 64 bit immediate in 3 instructions.
SDNode *ResultHi =
CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Hi32));
SDNode *ResultLo =
CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Lo32));
SDValue Ops[] = {SDValue(ResultLo, 0), SDValue(ResultHi, 0), getI32Imm(32),
getI32Imm(0)};
return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
}
static SDNode *selectI64Imm(SelectionDAG *CurDAG, const SDLoc &dl, uint64_t Imm,
unsigned *InstCnt = nullptr) {
unsigned InstCntDirect = 0;
// No more than 3 instructions is used if we can select the i64 immediate
// directly.
SDNode *Result = selectI64ImmDirect(CurDAG, dl, Imm, InstCntDirect);
const PPCSubtarget &Subtarget =
CurDAG->getMachineFunction().getSubtarget<PPCSubtarget>();
// If we have prefixed instructions and there is a chance we can
// materialize the constant with fewer prefixed instructions than
// non-prefixed, try that.
if (Subtarget.hasPrefixInstrs() && InstCntDirect != 1) {
unsigned InstCntDirectP = 0;
SDNode *ResultP = selectI64ImmDirectPrefix(CurDAG, dl, Imm, InstCntDirectP);
// Use the prefix case in either of two cases:
// 1) We have no result from the non-prefix case to use.
// 2) The non-prefix case uses more instructions than the prefix case.
// If the prefix and non-prefix cases use the same number of instructions
// we will prefer the non-prefix case.
if (ResultP && (!Result || InstCntDirectP < InstCntDirect)) {
if (InstCnt)
*InstCnt = InstCntDirectP;
return ResultP;
}
}
if (Result) {
if (InstCnt)
*InstCnt = InstCntDirect;
return Result;
}
auto getI32Imm = [CurDAG, dl](unsigned Imm) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
};
// Handle the upper 32 bit value.
Result =
selectI64ImmDirect(CurDAG, dl, Imm & 0xffffffff00000000, InstCntDirect);
// Add in the last bits as required.
if (uint32_t Hi16 = (Lo_32(Imm) >> 16) & 0xffff) {
Result = CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64,
SDValue(Result, 0), getI32Imm(Hi16));
++InstCntDirect;
}
if (uint32_t Lo16 = Lo_32(Imm) & 0xffff) {
Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64, SDValue(Result, 0),
getI32Imm(Lo16));
++InstCntDirect;
}
if (InstCnt)
*InstCnt = InstCntDirect;
return Result;
}
// Select a 64-bit constant.
static SDNode *selectI64Imm(SelectionDAG *CurDAG, SDNode *N) {
SDLoc dl(N);
// Get 64 bit value.
int64_t Imm = cast<ConstantSDNode>(N)->getZExtValue();
if (unsigned MinSize = allUsesTruncate(CurDAG, N)) {
uint64_t SextImm = SignExtend64(Imm, MinSize);
SDValue SDImm = CurDAG->getTargetConstant(SextImm, dl, MVT::i64);
if (isInt<16>(SextImm))
return CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
}
return selectI64Imm(CurDAG, dl, Imm);
}
namespace {
class BitPermutationSelector {
struct ValueBit {
SDValue V;
// The bit number in the value, using a convention where bit 0 is the
// lowest-order bit.
unsigned Idx;
// ConstZero means a bit we need to mask off.
// Variable is a bit comes from an input variable.
// VariableKnownToBeZero is also a bit comes from an input variable,
// but it is known to be already zero. So we do not need to mask them.
enum Kind {
ConstZero,
Variable,
VariableKnownToBeZero
} K;
ValueBit(SDValue V, unsigned I, Kind K = Variable)
: V(V), Idx(I), K(K) {}
ValueBit(Kind K = Variable)
: V(SDValue(nullptr, 0)), Idx(UINT32_MAX), K(K) {}
bool isZero() const {
return K == ConstZero || K == VariableKnownToBeZero;
}
bool hasValue() const {
return K == Variable || K == VariableKnownToBeZero;
}
SDValue getValue() const {
assert(hasValue() && "Cannot get the value of a constant bit");
return V;
}
unsigned getValueBitIndex() const {
assert(hasValue() && "Cannot get the value bit index of a constant bit");
return Idx;
}
};
// A bit group has the same underlying value and the same rotate factor.
struct BitGroup {
SDValue V;
unsigned RLAmt;
unsigned StartIdx, EndIdx;
// This rotation amount assumes that the lower 32 bits of the quantity are
// replicated in the high 32 bits by the rotation operator (which is done
// by rlwinm and friends in 64-bit mode).
bool Repl32;
// Did converting to Repl32 == true change the rotation factor? If it did,
// it decreased it by 32.
bool Repl32CR;
// Was this group coalesced after setting Repl32 to true?
bool Repl32Coalesced;
BitGroup(SDValue V, unsigned R, unsigned S, unsigned E)
: V(V), RLAmt(R), StartIdx(S), EndIdx(E), Repl32(false), Repl32CR(false),
Repl32Coalesced(false) {
LLVM_DEBUG(dbgs() << "\tbit group for " << V.getNode() << " RLAmt = " << R
<< " [" << S << ", " << E << "]\n");
}
};
// Information on each (Value, RLAmt) pair (like the number of groups
// associated with each) used to choose the lowering method.
struct ValueRotInfo {
SDValue V;
unsigned RLAmt = std::numeric_limits<unsigned>::max();
unsigned NumGroups = 0;
unsigned FirstGroupStartIdx = std::numeric_limits<unsigned>::max();
bool Repl32 = false;
ValueRotInfo() = default;
// For sorting (in reverse order) by NumGroups, and then by
// FirstGroupStartIdx.
bool operator < (const ValueRotInfo &Other) const {
// We need to sort so that the non-Repl32 come first because, when we're
// doing masking, the Repl32 bit groups might be subsumed into the 64-bit
// masking operation.
if (Repl32 < Other.Repl32)
return true;
else if (Repl32 > Other.Repl32)
return false;
else if (NumGroups > Other.NumGroups)
return true;
else if (NumGroups < Other.NumGroups)
return false;
else if (RLAmt == 0 && Other.RLAmt != 0)
return true;
else if (RLAmt != 0 && Other.RLAmt == 0)
return false;
else if (FirstGroupStartIdx < Other.FirstGroupStartIdx)
return true;
return false;
}
};
using ValueBitsMemoizedValue = std::pair<bool, SmallVector<ValueBit, 64>>;
using ValueBitsMemoizer =
DenseMap<SDValue, std::unique_ptr<ValueBitsMemoizedValue>>;
ValueBitsMemoizer Memoizer;
// Return a pair of bool and a SmallVector pointer to a memoization entry.
// The bool is true if something interesting was deduced, otherwise if we're
// providing only a generic representation of V (or something else likewise
// uninteresting for instruction selection) through the SmallVector.
std::pair<bool, SmallVector<ValueBit, 64> *> getValueBits(SDValue V,
unsigned NumBits) {
auto &ValueEntry = Memoizer[V];
if (ValueEntry)
return std::make_pair(ValueEntry->first, &ValueEntry->second);
ValueEntry.reset(new ValueBitsMemoizedValue());
bool &Interesting = ValueEntry->first;
SmallVector<ValueBit, 64> &Bits = ValueEntry->second;
Bits.resize(NumBits);
switch (V.getOpcode()) {
default: break;
case ISD::ROTL:
if (isa<ConstantSDNode>(V.getOperand(1))) {
unsigned RotAmt = V.getConstantOperandVal(1);
const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
for (unsigned i = 0; i < NumBits; ++i)
Bits[i] = LHSBits[i < RotAmt ? i + (NumBits - RotAmt) : i - RotAmt];
return std::make_pair(Interesting = true, &Bits);
}
break;
case ISD::SHL:
case PPCISD::SHL:
if (isa<ConstantSDNode>(V.getOperand(1))) {
unsigned ShiftAmt = V.getConstantOperandVal(1);
const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
for (unsigned i = ShiftAmt; i < NumBits; ++i)
Bits[i] = LHSBits[i - ShiftAmt];
for (unsigned i = 0; i < ShiftAmt; ++i)
Bits[i] = ValueBit(ValueBit::ConstZero);
return std::make_pair(Interesting = true, &Bits);
}
break;
case ISD::SRL:
case PPCISD::SRL:
if (isa<ConstantSDNode>(V.getOperand(1))) {
unsigned ShiftAmt = V.getConstantOperandVal(1);
const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
for (unsigned i = 0; i < NumBits - ShiftAmt; ++i)
Bits[i] = LHSBits[i + ShiftAmt];
for (unsigned i = NumBits - ShiftAmt; i < NumBits; ++i)
Bits[i] = ValueBit(ValueBit::ConstZero);
return std::make_pair(Interesting = true, &Bits);
}
break;
case ISD::AND:
if (isa<ConstantSDNode>(V.getOperand(1))) {
uint64_t Mask = V.getConstantOperandVal(1);
const SmallVector<ValueBit, 64> *LHSBits;
// Mark this as interesting, only if the LHS was also interesting. This
// prevents the overall procedure from matching a single immediate 'and'
// (which is non-optimal because such an and might be folded with other
// things if we don't select it here).
std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0), NumBits);
for (unsigned i = 0; i < NumBits; ++i)
if (((Mask >> i) & 1) == 1)
Bits[i] = (*LHSBits)[i];
else {
// AND instruction masks this bit. If the input is already zero,
// we have nothing to do here. Otherwise, make the bit ConstZero.
if ((*LHSBits)[i].isZero())
Bits[i] = (*LHSBits)[i];
else
Bits[i] = ValueBit(ValueBit::ConstZero);
}
return std::make_pair(Interesting, &Bits);
}
break;
case ISD::OR: {
const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
const auto &RHSBits = *getValueBits(V.getOperand(1), NumBits).second;
bool AllDisjoint = true;
SDValue LastVal = SDValue();
unsigned LastIdx = 0;
for (unsigned i = 0; i < NumBits; ++i) {
if (LHSBits[i].isZero() && RHSBits[i].isZero()) {
// If both inputs are known to be zero and one is ConstZero and
// another is VariableKnownToBeZero, we can select whichever
// we like. To minimize the number of bit groups, we select
// VariableKnownToBeZero if this bit is the next bit of the same
// input variable from the previous bit. Otherwise, we select
// ConstZero.
if (LHSBits[i].hasValue() && LHSBits[i].getValue() == LastVal &&
LHSBits[i].getValueBitIndex() == LastIdx + 1)
Bits[i] = LHSBits[i];
else if (RHSBits[i].hasValue() && RHSBits[i].getValue() == LastVal &&
RHSBits[i].getValueBitIndex() == LastIdx + 1)
Bits[i] = RHSBits[i];
else
Bits[i] = ValueBit(ValueBit::ConstZero);
}
else if (LHSBits[i].isZero())
Bits[i] = RHSBits[i];
else if (RHSBits[i].isZero())
Bits[i] = LHSBits[i];
else {
AllDisjoint = false;
break;
}
// We remember the value and bit index of this bit.
if (Bits[i].hasValue()) {
LastVal = Bits[i].getValue();
LastIdx = Bits[i].getValueBitIndex();
}
else {
if (LastVal) LastVal = SDValue();
LastIdx = 0;
}
}
if (!AllDisjoint)
break;
return std::make_pair(Interesting = true, &Bits);
}
case ISD::ZERO_EXTEND: {
// We support only the case with zero extension from i32 to i64 so far.
if (V.getValueType() != MVT::i64 ||
V.getOperand(0).getValueType() != MVT::i32)
break;
const SmallVector<ValueBit, 64> *LHSBits;
const unsigned NumOperandBits = 32;
std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0),
NumOperandBits);
for (unsigned i = 0; i < NumOperandBits; ++i)
Bits[i] = (*LHSBits)[i];
for (unsigned i = NumOperandBits; i < NumBits; ++i)
Bits[i] = ValueBit(ValueBit::ConstZero);
return std::make_pair(Interesting, &Bits);
}
case ISD::TRUNCATE: {
EVT FromType = V.getOperand(0).getValueType();
EVT ToType = V.getValueType();
// We support only the case with truncate from i64 to i32.
if (FromType != MVT::i64 || ToType != MVT::i32)
break;
const unsigned NumAllBits = FromType.getSizeInBits();
SmallVector<ValueBit, 64> *InBits;
std::tie(Interesting, InBits) = getValueBits(V.getOperand(0),
NumAllBits);
const unsigned NumValidBits = ToType.getSizeInBits();
// A 32-bit instruction cannot touch upper 32-bit part of 64-bit value.
// So, we cannot include this truncate.
bool UseUpper32bit = false;
for (unsigned i = 0; i < NumValidBits; ++i)
if ((*InBits)[i].hasValue() && (*InBits)[i].getValueBitIndex() >= 32) {
UseUpper32bit = true;
break;
}
if (UseUpper32bit)
break;
for (unsigned i = 0; i < NumValidBits; ++i)
Bits[i] = (*InBits)[i];
return std::make_pair(Interesting, &Bits);
}
case ISD::AssertZext: {
// For AssertZext, we look through the operand and
// mark the bits known to be zero.
const SmallVector<ValueBit, 64> *LHSBits;
std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0),
NumBits);
EVT FromType = cast<VTSDNode>(V.getOperand(1))->getVT();
const unsigned NumValidBits = FromType.getSizeInBits();
for (unsigned i = 0; i < NumValidBits; ++i)
Bits[i] = (*LHSBits)[i];
// These bits are known to be zero but the AssertZext may be from a value
// that already has some constant zero bits (i.e. from a masking and).
for (unsigned i = NumValidBits; i < NumBits; ++i)
Bits[i] = (*LHSBits)[i].hasValue()
? ValueBit((*LHSBits)[i].getValue(),
(*LHSBits)[i].getValueBitIndex(),
ValueBit::VariableKnownToBeZero)
: ValueBit(ValueBit::ConstZero);
return std::make_pair(Interesting, &Bits);
}
case ISD::LOAD:
LoadSDNode *LD = cast<LoadSDNode>(V);
if (ISD::isZEXTLoad(V.getNode()) && V.getResNo() == 0) {
EVT VT = LD->getMemoryVT();
const unsigned NumValidBits = VT.getSizeInBits();
for (unsigned i = 0; i < NumValidBits; ++i)
Bits[i] = ValueBit(V, i);
// These bits are known to be zero.
for (unsigned i = NumValidBits; i < NumBits; ++i)
Bits[i] = ValueBit(V, i, ValueBit::VariableKnownToBeZero);
// Zero-extending load itself cannot be optimized. So, it is not
// interesting by itself though it gives useful information.
return std::make_pair(Interesting = false, &Bits);
}
break;
}
for (unsigned i = 0; i < NumBits; ++i)
Bits[i] = ValueBit(V, i);
return std::make_pair(Interesting = false, &Bits);
}
// For each value (except the constant ones), compute the left-rotate amount
// to get it from its original to final position.
void computeRotationAmounts() {
NeedMask = false;
RLAmt.resize(Bits.size());
for (unsigned i = 0; i < Bits.size(); ++i)
if (Bits[i].hasValue()) {
unsigned VBI = Bits[i].getValueBitIndex();
if (i >= VBI)
RLAmt[i] = i - VBI;
else
RLAmt[i] = Bits.size() - (VBI - i);
} else if (Bits[i].isZero()) {
NeedMask = true;
RLAmt[i] = UINT32_MAX;
} else {
llvm_unreachable("Unknown value bit type");
}
}
// Collect groups of consecutive bits with the same underlying value and
// rotation factor. If we're doing late masking, we ignore zeros, otherwise
// they break up groups.
void collectBitGroups(bool LateMask) {
BitGroups.clear();
unsigned LastRLAmt = RLAmt[0];
SDValue LastValue = Bits[0].hasValue() ? Bits[0].getValue() : SDValue();
unsigned LastGroupStartIdx = 0;
bool IsGroupOfZeros = !Bits[LastGroupStartIdx].hasValue();
for (unsigned i = 1; i < Bits.size(); ++i) {
unsigned ThisRLAmt = RLAmt[i];
SDValue ThisValue = Bits[i].hasValue() ? Bits[i].getValue() : SDValue();
if (LateMask && !ThisValue) {
ThisValue = LastValue;
ThisRLAmt = LastRLAmt;
// If we're doing late masking, then the first bit group always starts
// at zero (even if the first bits were zero).
if (BitGroups.empty())
LastGroupStartIdx = 0;
}
// If this bit is known to be zero and the current group is a bit group
// of zeros, we do not need to terminate the current bit group even the
// Value or RLAmt does not match here. Instead, we terminate this group
// when the first non-zero bit appears later.
if (IsGroupOfZeros && Bits[i].isZero())
continue;
// If this bit has the same underlying value and the same rotate factor as
// the last one, then they're part of the same group.
if (ThisRLAmt == LastRLAmt && ThisValue == LastValue)
// We cannot continue the current group if this bits is not known to
// be zero in a bit group of zeros.
if (!(IsGroupOfZeros && ThisValue && !Bits[i].isZero()))
continue;
if (LastValue.getNode())
BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
i-1));
LastRLAmt = ThisRLAmt;
LastValue = ThisValue;
LastGroupStartIdx = i;
IsGroupOfZeros = !Bits[LastGroupStartIdx].hasValue();
}
if (LastValue.getNode())
BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
Bits.size()-1));
if (BitGroups.empty())
return;
// We might be able to combine the first and last groups.
if (BitGroups.size() > 1) {
// If the first and last groups are the same, then remove the first group
// in favor of the last group, making the ending index of the last group
// equal to the ending index of the to-be-removed first group.
if (BitGroups[0].StartIdx == 0 &&
BitGroups[BitGroups.size()-1].EndIdx == Bits.size()-1 &&
BitGroups[0].V == BitGroups[BitGroups.size()-1].V &&
BitGroups[0].RLAmt == BitGroups[BitGroups.size()-1].RLAmt) {
LLVM_DEBUG(dbgs() << "\tcombining final bit group with initial one\n");
BitGroups[BitGroups.size()-1].EndIdx = BitGroups[0].EndIdx;
BitGroups.erase(BitGroups.begin());
}
}
}
// Take all (SDValue, RLAmt) pairs and sort them by the number of groups
// associated with each. If the number of groups are same, we prefer a group
// which does not require rotate, i.e. RLAmt is 0, to avoid the first rotate
// instruction. If there is a degeneracy, pick the one that occurs
// first (in the final value).
void collectValueRotInfo() {
ValueRots.clear();
for (auto &BG : BitGroups) {
unsigned RLAmtKey = BG.RLAmt + (BG.Repl32 ? 64 : 0);
ValueRotInfo &VRI = ValueRots[std::make_pair(BG.V, RLAmtKey)];
VRI.V = BG.V;
VRI.RLAmt = BG.RLAmt;
VRI.Repl32 = BG.Repl32;
VRI.NumGroups += 1;
VRI.FirstGroupStartIdx = std::min(VRI.FirstGroupStartIdx, BG.StartIdx);
}
// Now that we've collected the various ValueRotInfo instances, we need to
// sort them.
ValueRotsVec.clear();
for (auto &I : ValueRots) {
ValueRotsVec.push_back(I.second);
}
llvm::sort(ValueRotsVec);
}
// In 64-bit mode, rlwinm and friends have a rotation operator that
// replicates the low-order 32 bits into the high-order 32-bits. The mask
// indices of these instructions can only be in the lower 32 bits, so they
// can only represent some 64-bit bit groups. However, when they can be used,
// the 32-bit replication can be used to represent, as a single bit group,
// otherwise separate bit groups. We'll convert to replicated-32-bit bit
// groups when possible. Returns true if any of the bit groups were
// converted.
void assignRepl32BitGroups() {
// If we have bits like this:
//
// Indices: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
// V bits: ... 7 6 5 4 3 2 1 0 31 30 29 28 27 26 25 24
// Groups: | RLAmt = 8 | RLAmt = 40 |
//
// But, making use of a 32-bit operation that replicates the low-order 32
// bits into the high-order 32 bits, this can be one bit group with a RLAmt
// of 8.
auto IsAllLow32 = [this](BitGroup & BG) {
if (BG.StartIdx <= BG.EndIdx) {
for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i) {
if (!Bits[i].hasValue())
continue;
if (Bits[i].getValueBitIndex() >= 32)
return false;
}
} else {
for (unsigned i = BG.StartIdx; i < Bits.size(); ++i) {
if (!Bits[i].hasValue())
continue;
if (Bits[i].getValueBitIndex() >= 32)
return false;
}
for (unsigned i = 0; i <= BG.EndIdx; ++i) {
if (!Bits[i].hasValue())
continue;
if (Bits[i].getValueBitIndex() >= 32)
return false;
}
}
return true;
};
for (auto &BG : BitGroups) {
// If this bit group has RLAmt of 0 and will not be merged with
// another bit group, we don't benefit from Repl32. We don't mark
// such group to give more freedom for later instruction selection.
if (BG.RLAmt == 0) {
auto PotentiallyMerged = [this](BitGroup & BG) {
for (auto &BG2 : BitGroups)
if (&BG != &BG2 && BG.V == BG2.V &&
(BG2.RLAmt == 0 || BG2.RLAmt == 32))
return true;
return false;
};
if (!PotentiallyMerged(BG))
continue;
}
if (BG.StartIdx < 32 && BG.EndIdx < 32) {
if (IsAllLow32(BG)) {
if (BG.RLAmt >= 32) {
BG.RLAmt -= 32;
BG.Repl32CR = true;
}
BG.Repl32 = true;
LLVM_DEBUG(dbgs() << "\t32-bit replicated bit group for "
<< BG.V.getNode() << " RLAmt = " << BG.RLAmt << " ["
<< BG.StartIdx << ", " << BG.EndIdx << "]\n");
}
}
}
// Now walk through the bit groups, consolidating where possible.
for (auto I = BitGroups.begin(); I != BitGroups.end();) {
// We might want to remove this bit group by merging it with the previous
// group (which might be the ending group).
auto IP = (I == BitGroups.begin()) ?
std::prev(BitGroups.end()) : std::prev(I);
if (I->Repl32 && IP->Repl32 && I->V == IP->V && I->RLAmt == IP->RLAmt &&
I->StartIdx == (IP->EndIdx + 1) % 64 && I != IP) {
LLVM_DEBUG(dbgs() << "\tcombining 32-bit replicated bit group for "
<< I->V.getNode() << " RLAmt = " << I->RLAmt << " ["
<< I->StartIdx << ", " << I->EndIdx
<< "] with group with range [" << IP->StartIdx << ", "
<< IP->EndIdx << "]\n");
IP->EndIdx = I->EndIdx;
IP->Repl32CR = IP->Repl32CR || I->Repl32CR;
IP->Repl32Coalesced = true;
I = BitGroups.erase(I);
continue;
} else {
// There is a special case worth handling: If there is a single group
// covering the entire upper 32 bits, and it can be merged with both
// the next and previous groups (which might be the same group), then
// do so. If it is the same group (so there will be only one group in
// total), then we need to reverse the order of the range so that it
// covers the entire 64 bits.
if (I->StartIdx == 32 && I->EndIdx == 63) {
assert(std::next(I) == BitGroups.end() &&
"bit group ends at index 63 but there is another?");
auto IN = BitGroups.begin();
if (IP->Repl32 && IN->Repl32 && I->V == IP->V && I->V == IN->V &&
(I->RLAmt % 32) == IP->RLAmt && (I->RLAmt % 32) == IN->RLAmt &&
IP->EndIdx == 31 && IN->StartIdx == 0 && I != IP &&
IsAllLow32(*I)) {
LLVM_DEBUG(dbgs() << "\tcombining bit group for " << I->V.getNode()
<< " RLAmt = " << I->RLAmt << " [" << I->StartIdx
<< ", " << I->EndIdx
<< "] with 32-bit replicated groups with ranges ["
<< IP->StartIdx << ", " << IP->EndIdx << "] and ["
<< IN->StartIdx << ", " << IN->EndIdx << "]\n");
if (IP == IN) {
// There is only one other group; change it to cover the whole
// range (backward, so that it can still be Repl32 but cover the
// whole 64-bit range).
IP->StartIdx = 31;
IP->EndIdx = 30;
IP->Repl32CR = IP->Repl32CR || I->RLAmt >= 32;
IP->Repl32Coalesced = true;
I = BitGroups.erase(I);
} else {
// There are two separate groups, one before this group and one
// after us (at the beginning). We're going to remove this group,
// but also the group at the very beginning.
IP->EndIdx = IN->EndIdx;
IP->Repl32CR = IP->Repl32CR || IN->Repl32CR || I->RLAmt >= 32;
IP->Repl32Coalesced = true;
I = BitGroups.erase(I);
BitGroups.erase(BitGroups.begin());
}
// This must be the last group in the vector (and we might have
// just invalidated the iterator above), so break here.
break;
}
}
}
++I;
}
}
SDValue getI32Imm(unsigned Imm, const SDLoc &dl) {
return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
}
uint64_t getZerosMask() {
uint64_t Mask = 0;
for (unsigned i = 0; i < Bits.size(); ++i) {
if (Bits[i].hasValue())
continue;
Mask |= (UINT64_C(1) << i);
}
return ~Mask;
}
// This method extends an input value to 64 bit if input is 32-bit integer.
// While selecting instructions in BitPermutationSelector in 64-bit mode,
// an input value can be a 32-bit integer if a ZERO_EXTEND node is included.
// In such case, we extend it to 64 bit to be consistent with other values.
SDValue ExtendToInt64(SDValue V, const SDLoc &dl) {
if (V.getValueSizeInBits() == 64)
return V;
assert(V.getValueSizeInBits() == 32);
SDValue SubRegIdx = CurDAG->getTargetConstant(PPC::sub_32, dl, MVT::i32);
SDValue ImDef = SDValue(CurDAG->getMachineNode(PPC::IMPLICIT_DEF, dl,
MVT::i64), 0);
SDValue ExtVal = SDValue(CurDAG->getMachineNode(PPC::INSERT_SUBREG, dl,
MVT::i64, ImDef, V,
SubRegIdx), 0);
return ExtVal;
}
SDValue TruncateToInt32(SDValue V, const SDLoc &dl) {
if (V.getValueSizeInBits() == 32)
return V;
assert(V.getValueSizeInBits() == 64);
SDValue SubRegIdx = CurDAG->getTargetConstant(PPC::sub_32, dl, MVT::i32);
SDValue SubVal = SDValue(CurDAG->getMachineNode(PPC::EXTRACT_SUBREG, dl,
MVT::i32, V, SubRegIdx), 0);
return SubVal;
}
// Depending on the number of groups for a particular value, it might be
// better to rotate, mask explicitly (using andi/andis), and then or the
// result. Select this part of the result first.
void SelectAndParts32(const SDLoc &dl, SDValue &Res, unsigned *InstCnt) {
if (BPermRewriterNoMasking)
return;
for (ValueRotInfo &VRI : ValueRotsVec) {
unsigned Mask = 0;
for (unsigned i = 0; i < Bits.size(); ++i) {
if (!Bits[i].hasValue() || Bits[i].getValue() != VRI.V)
continue;
if (RLAmt[i] != VRI.RLAmt)
continue;
Mask |= (1u << i);
}
// Compute the masks for andi/andis that would be necessary.
unsigned ANDIMask = (Mask & UINT16_MAX), ANDISMask = Mask >> 16;
assert((ANDIMask != 0 || ANDISMask != 0) &&
"No set bits in mask for value bit groups");
bool NeedsRotate = VRI.RLAmt != 0;
// We're trying to minimize the number of instructions. If we have one
// group, using one of andi/andis can break even. If we have three
// groups, we can use both andi and andis and break even (to use both
// andi and andis we also need to or the results together). We need four
// groups if we also need to rotate. To use andi/andis we need to do more
// than break even because rotate-and-mask instructions tend to be easier
// to schedule.
// FIXME: We've biased here against using andi/andis, which is right for
// POWER cores, but not optimal everywhere. For example, on the A2,
// andi/andis have single-cycle latency whereas the rotate-and-mask
// instructions take two cycles, and it would be better to bias toward
// andi/andis in break-even cases.
unsigned NumAndInsts = (unsigned) NeedsRotate +
(unsigned) (ANDIMask != 0) +
(unsigned) (ANDISMask != 0) +
(unsigned) (ANDIMask != 0 && ANDISMask != 0) +
(unsigned) (bool) Res;
LLVM_DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode()
<< " RL: " << VRI.RLAmt << ":"
<< "\n\t\t\tisel using masking: " << NumAndInsts
<< " using rotates: " << VRI.NumGroups << "\n");
if (NumAndInsts >= VRI.NumGroups)
continue;
LLVM_DEBUG(dbgs() << "\t\t\t\tusing masking\n");
if (InstCnt) *InstCnt += NumAndInsts;
SDValue VRot;
if (VRI.RLAmt) {
SDValue Ops[] =
{ TruncateToInt32(VRI.V, dl), getI32Imm(VRI.RLAmt, dl),
getI32Imm(0, dl), getI32Imm(31, dl) };
VRot = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
Ops), 0);
} else {
VRot = TruncateToInt32(VRI.V, dl);
}
SDValue ANDIVal, ANDISVal;
if (ANDIMask != 0)
ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDI_rec, dl, MVT::i32,
VRot, getI32Imm(ANDIMask, dl)),
0);
if (ANDISMask != 0)
ANDISVal =
SDValue(CurDAG->getMachineNode(PPC::ANDIS_rec, dl, MVT::i32, VRot,
getI32Imm(ANDISMask, dl)),
0);
SDValue TotalVal;
if (!ANDIVal)
TotalVal = ANDISVal;
else if (!ANDISVal)
TotalVal = ANDIVal;
else
TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
ANDIVal, ANDISVal), 0);
if (!Res)
Res = TotalVal;
else
Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
Res, TotalVal), 0);
// Now, remove all groups with this underlying value and rotation
// factor.
eraseMatchingBitGroups([VRI](const BitGroup &BG) {
return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt;
});
}
}
// Instruction selection for the 32-bit case.
SDNode *Select32(SDNode *N, bool LateMask, unsigned *InstCnt) {
SDLoc dl(N);
SDValue Res;
if (InstCnt) *InstCnt = 0;
// Take care of cases that should use andi/andis first.
SelectAndParts32(dl, Res, InstCnt);
// If we've not yet selected a 'starting' instruction, and we have no zeros
// to fill in, select the (Value, RLAmt) with the highest priority (largest
// number of groups), and start with this rotated value.
if ((!NeedMask || LateMask) && !Res) {
ValueRotInfo &VRI = ValueRotsVec[0];
if (VRI.RLAmt) {
if (InstCnt) *InstCnt += 1;
SDValue Ops[] =
{ TruncateToInt32(VRI.V, dl), getI32Imm(VRI.RLAmt, dl),
getI32Imm(0, dl), getI32Imm(31, dl) };
Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops),
0);
} else {
Res = TruncateToInt32(VRI.V, dl);
}
// Now, remove all groups with this underlying value and rotation factor.
eraseMatchingBitGroups([VRI](const BitGroup &BG) {
return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt;
});
}
if (InstCnt) *InstCnt += BitGroups.size();
// Insert the other groups (one at a time).
for (auto &BG : BitGroups) {
if (!Res) {
SDValue Ops[] =
{ TruncateToInt32(BG.V, dl), getI32Imm(BG.RLAmt, dl),
getI32Imm(Bits.size() - BG.EndIdx - 1, dl),
getI32Imm(Bits.size() - BG.StartIdx - 1, dl) };
Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
} else {
SDValue Ops[] =
{ Res, TruncateToInt32(BG.V, dl), getI32Imm(BG.RLAmt, dl),
getI32Imm(Bits.size() - BG.EndIdx - 1, dl),
getI32Imm(Bits.size() - BG.StartIdx - 1, dl) };
Res = SDValue(CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops), 0);
}
}
if (LateMask) {
unsigned Mask = (unsigned) getZerosMask();
unsigned ANDIMask = (Mask & UINT16_MAX), ANDISMask = Mask >> 16;
assert((ANDIMask != 0 || ANDISMask != 0) &&
"No set bits in zeros mask?");
if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
(unsigned) (ANDISMask != 0) +
(unsigned) (ANDIMask != 0 && ANDISMask != 0);
SDValue ANDIVal, ANDISVal;
if (ANDIMask != 0)
ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDI_rec, dl, MVT::i32,
Res, getI32Imm(ANDIMask, dl)),
0);
if (ANDISMask != 0)
ANDISVal =
SDValue(CurDAG->getMachineNode(PPC::ANDIS_rec, dl, MVT::i32, Res,
getI32Imm(ANDISMask, dl)),
0);
if (!ANDIVal)
Res = ANDISVal;
else if (!ANDISVal)
Res = ANDIVal;
else
Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
ANDIVal, ANDISVal), 0);
}
return Res.getNode();
}
unsigned SelectRotMask64Count(unsigned RLAmt, bool Repl32,
unsigned MaskStart, unsigned MaskEnd,
bool IsIns) {
// In the notation used by the instructions, 'start' and 'end' are reversed
// because bits are counted from high to low order.
unsigned InstMaskStart = 64 - MaskEnd - 1,
InstMaskEnd = 64 - MaskStart - 1;
if (Repl32)
return 1;
if ((!IsIns && (InstMaskEnd == 63 || InstMaskStart == 0)) ||
InstMaskEnd == 63 - RLAmt)
return 1;
return 2;
}
// For 64-bit values, not all combinations of rotates and masks are
// available. Produce one if it is available.
SDValue SelectRotMask64(SDValue V, const SDLoc &dl, unsigned RLAmt,
bool Repl32, unsigned MaskStart, unsigned MaskEnd,
unsigned *InstCnt = nullptr) {
// In the notation used by the instructions, 'start' and 'end' are reversed
// because bits are counted from high to low order.
unsigned InstMaskStart = 64 - MaskEnd - 1,
InstMaskEnd = 64 - MaskStart - 1;
if (InstCnt) *InstCnt += 1;
if (Repl32) {
// This rotation amount assumes that the lower 32 bits of the quantity
// are replicated in the high 32 bits by the rotation operator (which is
// done by rlwinm and friends).
assert(InstMaskStart >= 32 && "Mask cannot start out of range");
assert(InstMaskEnd >= 32 && "Mask cannot end out of range");
SDValue Ops[] =
{ ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
getI32Imm(InstMaskStart - 32, dl), getI32Imm(InstMaskEnd - 32, dl) };
return SDValue(CurDAG->getMachineNode(PPC::RLWINM8, dl, MVT::i64,
Ops), 0);
}
if (InstMaskEnd == 63) {
SDValue Ops[] =
{ ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
getI32Imm(InstMaskStart, dl) };
return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Ops), 0);
}
if (InstMaskStart == 0) {
SDValue Ops[] =
{ ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
getI32Imm(InstMaskEnd, dl) };
return SDValue(CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64, Ops), 0);
}
if (InstMaskEnd == 63 - RLAmt) {
SDValue Ops[] =
{ ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
getI32Imm(InstMaskStart, dl) };
return SDValue(CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, Ops), 0);
}
// We cannot do this with a single instruction, so we'll use two. The
// problem is that we're not free to choose both a rotation amount and mask
// start and end independently. We can choose an arbitrary mask start and
// end, but then the rotation amount is fixed. Rotation, however, can be
// inverted, and so by applying an "inverse" rotation first, we can get the
// desired result.
if (InstCnt) *InstCnt += 1;
// The rotation mask for the second instruction must be MaskStart.
unsigned RLAmt2 = MaskStart;
// The first instruction must rotate V so that the overall rotation amount
// is RLAmt.
unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
if (RLAmt1)
V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
return SelectRotMask64(V, dl, RLAmt2, false, MaskStart, MaskEnd);
}
// For 64-bit values, not all combinations of rotates and masks are
// available. Produce a rotate-mask-and-insert if one is available.
SDValue SelectRotMaskIns64(SDValue Base, SDValue V, const SDLoc &dl,
unsigned RLAmt, bool Repl32, unsigned MaskStart,
unsigned MaskEnd, unsigned *InstCnt = nullptr) {
// In the notation used by the instructions, 'start' and 'end' are reversed
// because bits are counted from high to low order.
unsigned InstMaskStart = 64 - MaskEnd - 1,
InstMaskEnd = 64 - MaskStart - 1;
if (InstCnt) *InstCnt += 1;
if (Repl32) {
// This rotation amount assumes that the lower 32 bits of the quantity
// are replicated in the high 32 bits by the rotation operator (which is
// done by rlwinm and friends).
assert(InstMaskStart >= 32 && "Mask cannot start out of range");
assert(InstMaskEnd >= 32 && "Mask cannot end out of range");
SDValue Ops[] =
{ ExtendToInt64(Base, dl), ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
getI32Imm(InstMaskStart - 32, dl), getI32Imm(InstMaskEnd - 32, dl) };
return SDValue(CurDAG->getMachineNode(PPC::RLWIMI8, dl, MVT::i64,
Ops), 0);
}
if (InstMaskEnd == 63 - RLAmt) {
SDValue Ops[] =
{ ExtendToInt64(Base, dl), ExtendToInt64(V, dl), getI32Imm(RLAmt, dl),
getI32Imm(InstMaskStart, dl) };
return SDValue(CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops), 0);
}
// We cannot do this with a single instruction, so we'll use two. The
// problem is that we're not free to choose both a rotation amount and mask
// start and end independently. We can choose an arbitrary mask start and
// end, but then the rotation amount is fixed. Rotation, however, can be
// inverted, and so by applying an "inverse" rotation first, we can get the
// desired result.
if (InstCnt) *InstCnt += 1;
// The rotation mask for the second instruction must be MaskStart.
unsigned RLAmt2 = MaskStart;
// The first instruction must rotate V so that the overall rotation amount
// is RLAmt.
unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
if (RLAmt1)
V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
return SelectRotMaskIns64(Base, V, dl, RLAmt2, false, MaskStart, MaskEnd);
}
void SelectAndParts64(const SDLoc &dl, SDValue &Res, unsigned *InstCnt) {
if (BPermRewriterNoMasking)
return;
// The idea here is the same as in the 32-bit version, but with additional
// complications from the fact that Repl32 might be true. Because we
// aggressively convert bit groups to Repl32 form (which, for small
// rotation factors, involves no other change), and then coalesce, it might
// be the case that a single 64-bit masking operation could handle both
// some Repl32 groups and some non-Repl32 groups. If converting to Repl32
// form allowed coalescing, then we must use a 32-bit rotaton in order to
// completely capture the new combined bit group.
for (ValueRotInfo &VRI : ValueRotsVec) {
uint64_t Mask = 0;
// We need to add to the mask all bits from the associated bit groups.
// If Repl32 is false, we need to add bits from bit groups that have
// Repl32 true, but are trivially convertable to Repl32 false. Such a
// group is trivially convertable if it overlaps only with the lower 32
// bits, and the group has not been coalesced.
auto MatchingBG = [VRI](const BitGroup &BG) {
if (VRI.V != BG.V)
return false;
unsigned EffRLAmt = BG.RLAmt;
if (!VRI.Repl32 && BG.Repl32) {
if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx <= BG.EndIdx &&
!BG.Repl32Coalesced) {
if (BG.Repl32CR)
EffRLAmt += 32;
} else {
return false;
}
} else if (VRI.Repl32 != BG.Repl32) {
return false;
}
return VRI.RLAmt == EffRLAmt;
};
for (auto &BG : BitGroups) {
if (!MatchingBG(BG))
continue;
if (BG.StartIdx <= BG.EndIdx) {
for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i)
Mask |= (UINT64_C(1) << i);
} else {
for (unsigned i = BG.StartIdx; i < Bits.size(); ++i)
Mask |= (UINT64_C(1) << i);
for (unsigned i = 0; i <= BG.EndIdx; ++i)
Mask |= (UINT64_C(1) << i);
}
}
// We can use the 32-bit andi/andis technique if the mask does not
// require any higher-order bits. This can save an instruction compared
// to always using the general 64-bit technique.
bool Use32BitInsts = isUInt<32>(Mask);
// Compute the masks for andi/andis that would be necessary.
unsigned ANDIMask = (Mask & UINT16_MAX),
ANDISMask = (Mask >> 16) & UINT16_MAX;
bool NeedsRotate = VRI.RLAmt || (VRI.Repl32 && !isUInt<32>(Mask));
unsigned NumAndInsts = (unsigned) NeedsRotate +
(unsigned) (bool) Res;
unsigned NumOfSelectInsts = 0;
selectI64Imm(CurDAG, dl, Mask, &NumOfSelectInsts);
assert(NumOfSelectInsts > 0 && "Failed to select an i64 constant.");
if (Use32BitInsts)
NumAndInsts += (unsigned) (ANDIMask != 0) + (unsigned) (ANDISMask != 0) +
(unsigned) (ANDIMask != 0 && ANDISMask != 0);
else
NumAndInsts += NumOfSelectInsts + /* and */ 1;
unsigned NumRLInsts = 0;
bool FirstBG = true;
bool MoreBG = false;
for (auto &BG : BitGroups) {
if (!MatchingBG(BG)) {
MoreBG = true;
continue;
}
NumRLInsts +=
SelectRotMask64Count(BG.RLAmt, BG.Repl32, BG.StartIdx, BG.EndIdx,
!FirstBG);
FirstBG = false;
}
LLVM_DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode()
<< " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":")
<< "\n\t\t\tisel using masking: " << NumAndInsts