52#define DEBUG_TYPE "instcombine"
55 "Negator: Number of negations attempted to be sinked");
57 "Negator: Number of negations successfully sinked");
58STATISTIC(NegatorMaxDepthVisited,
"Negator: Maximal traversal depth ever "
59 "reached while attempting to sink negation");
61 "Negator: How many times did the traversal depth limit was reached "
64 NegatorNumValuesVisited,
65 "Negator: Total number of values visited during attempts to sink negation");
67 "Negator: How many negations did we retrieve/reuse from cache");
69 "Negator: Maximal number of values ever visited while attempting to "
72 "Negator: Number of new negated instructions created, total");
74 "Negator: Maximal number of new instructions created during negation "
77 "Negator: Number of new negated instructions created in successful "
78 "negation sinking attempts");
81 "Controls Negator transformations in InstCombine pass");
85 cl::desc(
"Should we attempt to sink negations?"));
90 cl::desc(
"What is the maximal lookup depth when trying to "
91 "check for viability of negation sinking."));
96 ++NegatorNumInstructionsCreatedTotal;
97 NewInstructions.push_back(
I);
99 IsTrulyNegation(IsTrulyNegation_) {}
103 NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
111std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(
Instruction *
I) {
112 assert(
I->getNumOperands() == 2 &&
"Only for binops!");
113 std::array<Value *, 2> Ops{
I->getOperand(0),
I->getOperand(1)};
122[[nodiscard]]
Value *Negator::visitImpl(
Value *V,
bool IsNSW,
unsigned Depth) {
128 if (
V->getType()->isIntOrIntVectorTy(1))
143 if (!isa<Instruction>(V))
149 if (!
V->hasOneUse() && !IsTrulyNegation)
152 auto *
I = cast<Instruction>(V);
153 unsigned BitWidth =
I->getType()->getScalarSizeInBits();
163 switch (
I->getOpcode()) {
164 case Instruction::Add: {
165 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
168 return Builder.
CreateNot(Ops[0],
I->getName() +
".neg");
171 case Instruction::Xor:
174 return Builder.
CreateAdd(
X, ConstantInt::get(
X->getType(), 1),
175 I->getName() +
".neg");
177 case Instruction::AShr:
178 case Instruction::LShr: {
182 Value *BO =
I->getOpcode() == Instruction::AShr
183 ? Builder.
CreateLShr(
I->getOperand(0),
I->getOperand(1))
184 : Builder.
CreateAShr(
I->getOperand(0),
I->getOperand(1));
185 if (
auto *NewInstr = dyn_cast<Instruction>(BO)) {
186 NewInstr->copyIRFlags(
I);
187 NewInstr->
setName(
I->getName() +
".neg");
197 case Instruction::SExt:
198 case Instruction::ZExt:
200 if (
I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
201 return I->getOpcode() == Instruction::SExt
203 I->getName() +
".neg")
205 I->getName() +
".neg");
207 case Instruction::Select: {
210 auto *Sel = cast<SelectInst>(
I);
216 return Builder.
CreateSelect(Sel->getCondition(), NegTrueC, NegFalseC,
217 I->getName() +
".neg",
I);
221 case Instruction::Call:
222 if (
auto *CI = dyn_cast<CmpIntrinsic>(
I); CI && CI->hasOneUse())
224 {CI->getRHS(), CI->getLHS()});
230 if (
I->getOpcode() == Instruction::Sub &&
235 return Builder.
CreateSub(
I->getOperand(1),
I->getOperand(0),
236 I->getName() +
".neg",
false,
237 IsNSW &&
I->hasNoSignedWrap());
245 switch (
I->getOpcode()) {
246 case Instruction::ZExt: {
250 unsigned SrcWidth =
SrcOp->getType()->getScalarSizeInBits();
251 const APInt &FullShift =
APInt(SrcWidth, SrcWidth - 1);
252 if (IsTrulyNegation &&
259 case Instruction::And: {
265 unsigned BW =
X->getType()->getScalarSizeInBits();
266 Constant *BWMinusOne = ConstantInt::get(
X->getType(), BW - 1);
273 case Instruction::SDiv:
277 if (
auto *Op1C = dyn_cast<Constant>(
I->getOperand(1))) {
278 if (!Op1C->containsUndefOrPoisonElement() &&
279 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
282 I->getName() +
".neg");
283 if (
auto *NewInstr = dyn_cast<Instruction>(BO))
284 NewInstr->setIsExact(
I->isExact());
293 LLVM_DEBUG(
dbgs() <<
"Negator: reached maximal allowed traversal depth in "
294 << *V <<
". Giving up.\n");
295 ++NegatorTimesDepthLimitReached;
299 switch (
I->getOpcode()) {
300 case Instruction::Freeze: {
302 Value *NegOp = negate(
I->getOperand(0), IsNSW,
Depth + 1);
307 case Instruction::PHI: {
309 auto *
PHI = cast<PHINode>(
I);
311 for (
auto I :
zip(
PHI->incoming_values(), NegatedIncomingValues)) {
312 if (!(std::get<1>(
I) =
313 negate(std::get<0>(
I), IsNSW,
Depth + 1)))
318 PHI->getType(),
PHI->getNumOperands(),
PHI->getName() +
".neg");
319 for (
auto I :
zip(NegatedIncomingValues,
PHI->blocks()))
323 case Instruction::Select: {
328 auto *NewSelect = cast<SelectInst>(
I->clone());
330 NewSelect->swapValues();
332 NewSelect->setName(
I->getName() +
".neg");
333 Builder.
Insert(NewSelect);
337 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
340 Value *NegOp2 = negate(
I->getOperand(2), IsNSW,
Depth + 1);
344 return Builder.
CreateSelect(
I->getOperand(0), NegOp1, NegOp2,
345 I->getName() +
".neg",
I);
347 case Instruction::ShuffleVector: {
349 auto *Shuf = cast<ShuffleVectorInst>(
I);
350 Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1);
353 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
357 I->getName() +
".neg");
359 case Instruction::ExtractElement: {
361 auto *EEI = cast<ExtractElementInst>(
I);
362 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW,
Depth + 1);
366 I->getName() +
".neg");
368 case Instruction::InsertElement: {
371 auto *IEI = cast<InsertElementInst>(
I);
372 Value *NegVector = negate(IEI->getOperand(0), IsNSW,
Depth + 1);
375 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW,
Depth + 1);
379 I->getName() +
".neg");
381 case Instruction::Trunc: {
383 Value *NegOp = negate(
I->getOperand(0),
false,
Depth + 1);
386 return Builder.
CreateTrunc(NegOp,
I->getType(),
I->getName() +
".neg");
388 case Instruction::Shl: {
390 IsNSW &=
I->hasNoSignedWrap();
391 if (
Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1))
392 return Builder.
CreateShl(NegOp0,
I->getOperand(1),
I->getName() +
".neg",
401 I->getName() +
".neg",
false, IsNSW);
403 case Instruction::Or: {
404 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint())
406 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
410 return Builder.
CreateNot(Ops[0],
I->getName() +
".neg");
414 case Instruction::Add: {
425 if (!IsTrulyNegation)
430 "Internal consistency check failed.");
432 if (NegatedOps.
size() == 2)
433 return Builder.
CreateAdd(NegatedOps[0], NegatedOps[1],
434 I->getName() +
".neg");
435 assert(IsTrulyNegation &&
"We should have early-exited then.");
437 if (NonNegatedOps.
size() == 2)
440 return Builder.
CreateSub(NegatedOps[0], NonNegatedOps[0],
441 I->getName() +
".neg");
443 case Instruction::Xor: {
444 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
447 if (
auto *
C = dyn_cast<Constant>(Ops[1])) {
448 if (IsTrulyNegation) {
451 I->getName() +
".neg");
456 case Instruction::Mul: {
457 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
459 Value *NegatedOp, *OtherOp;
462 if (
Value *NegOp1 = negate(Ops[1],
false,
Depth + 1)) {
465 }
else if (
Value *NegOp0 = negate(Ops[0],
false,
Depth + 1)) {
471 return Builder.
CreateMul(NegatedOp, OtherOp,
I->getName() +
".neg",
472 false, IsNSW &&
I->hasNoSignedWrap());
481[[nodiscard]]
Value *Negator::negate(
Value *V,
bool IsNSW,
unsigned Depth) {
482 NegatorMaxDepthVisited.updateMax(
Depth);
483 ++NegatorNumValuesVisited;
486 ++NumValuesVisitedInThisNegator;
491 Value *Placeholder =
reinterpret_cast<Value *
>(
static_cast<uintptr_t
>(-1));
495 auto NegationsCacheIterator = NegationsCache.find(V);
496 if (NegationsCacheIterator != NegationsCache.end()) {
497 ++NegatorNumNegationsFoundInCache;
498 Value *NegatedV = NegationsCacheIterator->second;
499 assert(NegatedV != Placeholder &&
"Encountered a cycle during negation.");
507 NegationsCache[
V] = Placeholder;
513 NegationsCache[
V] = NegatedV;
518[[nodiscard]] std::optional<Negator::Result> Negator::run(
Value *Root,
520 Value *Negated = negate(Root, IsNSW, 0);
525 I->eraseFromParent();
533 ++NegatorTotalNegationsAttempted;
534 LLVM_DEBUG(
dbgs() <<
"Negator: attempting to sink negation into " << *Root
541 std::optional<Result> Res =
N.run(Root, IsNSW);
543 LLVM_DEBUG(
dbgs() <<
"Negator: failed to sink negation into " << *Root
548 LLVM_DEBUG(
dbgs() <<
"Negator: successfully sunk negation into " << *Root
549 <<
"\n NEW: " << *Res->second <<
"\n");
550 ++NegatorNumTreesNegated;
562 <<
" instrs to InstCombine\n");
563 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
564 NegatorNumInstructionsNegatedSuccess += Res->first.size();
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This defines the Use class.
This file provides internal interfaces used to implement the InstCombine.
static constexpr unsigned NegatorDefaultMaxDepth
static cl::opt< bool > NegatorEnabled("instcombine-negator-enabled", cl::init(true), cl::desc("Should we attempt to sink negations?"))
static cl::opt< unsigned > NegatorMaxDepth("instcombine-negator-max-depth", cl::init(NegatorDefaultMaxDepth), cl::desc("What is the maximal lookup depth when trying to " "check for viability of negation sinking."))
This file provides the interface for the instcombine pass implementation.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
static Constant * getNot(Constant *C)
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is an important base class in LLVM.
static Constant * getAllOnesValue(Type *Ty)
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
static bool shouldExecute(unsigned CounterName)
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateSDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateTruncOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
const DataLayout & getDataLayout() const
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
This is an important class for using LLVM in a threaded context.
static Value * Negate(bool LHSIsZero, bool IsNSW, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
reference emplace_back(ArgTypes &&... Args)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetFolder - Create constants with target dependent folding.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
LLVMContext & getContext() const
All values hold a context through their type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, TruncInst >, OpTy > m_TruncOrSelf(const OpTy &Op)
bool match(Val *V, const Pattern &P)
specific_intval< true > m_SpecificIntAllowPoison(const APInt &V)
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
OneUse_match< T > m_OneUse(const T &SubPattern)
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
@ Xor
Bitwise or logical XOR of integers.
constexpr unsigned BitWidth
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false, bool AllowPoison=true)
Return true if the two given values are negation.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.