51#define DEBUG_TYPE "instcombine"
54 "Negator: Number of negations attempted to be sinked");
56 "Negator: Number of negations successfully sinked");
57STATISTIC(NegatorMaxDepthVisited,
"Negator: Maximal traversal depth ever "
58 "reached while attempting to sink negation");
60 "Negator: How many times did the traversal depth limit was reached "
63 NegatorNumValuesVisited,
64 "Negator: Total number of values visited during attempts to sink negation");
66 "Negator: How many negations did we retrieve/reuse from cache");
68 "Negator: Maximal number of values ever visited while attempting to "
71 "Negator: Number of new negated instructions created, total");
73 "Negator: Maximal number of new instructions created during negation "
76 "Negator: Number of new negated instructions created in successful "
77 "negation sinking attempts");
80 "Controls Negator transformations in InstCombine pass");
84 cl::desc(
"Should we attempt to sink negations?"));
89 cl::desc(
"What is the maximal lookup depth when trying to "
90 "check for viability of negation sinking."));
93 bool IsTrulyNegation_)
96 ++NegatorNumInstructionsCreatedTotal;
97 NewInstructions.push_back(
I);
99 DT(DT_), 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)) {
315 if (!(std::get<1>(
I) =
316 negate(std::get<0>(
I), IsNSW,
Depth + 1)))
321 PHI->getType(),
PHI->getNumOperands(),
PHI->getName() +
".neg");
322 for (
auto I :
zip(NegatedIncomingValues,
PHI->blocks()))
326 case Instruction::Select: {
331 auto *NewSelect = cast<SelectInst>(
I->clone());
333 NewSelect->swapValues();
335 NewSelect->setName(
I->getName() +
".neg");
337 Value *TV = NewSelect->getTrueValue();
338 Value *FV = NewSelect->getFalseValue();
340 cast<Instruction>(TV)->dropPoisonGeneratingFlags();
342 cast<Instruction>(FV)->dropPoisonGeneratingFlags();
344 cast<Instruction>(TV)->dropPoisonGeneratingFlags();
345 cast<Instruction>(FV)->dropPoisonGeneratingFlags();
347 Builder.
Insert(NewSelect);
351 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
354 Value *NegOp2 = negate(
I->getOperand(2), IsNSW,
Depth + 1);
358 return Builder.
CreateSelect(
I->getOperand(0), NegOp1, NegOp2,
359 I->getName() +
".neg",
I);
361 case Instruction::ShuffleVector: {
363 auto *Shuf = cast<ShuffleVectorInst>(
I);
364 Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1);
367 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
371 I->getName() +
".neg");
373 case Instruction::ExtractElement: {
375 auto *EEI = cast<ExtractElementInst>(
I);
376 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW,
Depth + 1);
380 I->getName() +
".neg");
382 case Instruction::InsertElement: {
385 auto *IEI = cast<InsertElementInst>(
I);
386 Value *NegVector = negate(IEI->getOperand(0), IsNSW,
Depth + 1);
389 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW,
Depth + 1);
393 I->getName() +
".neg");
395 case Instruction::Trunc: {
397 Value *NegOp = negate(
I->getOperand(0),
false,
Depth + 1);
400 return Builder.
CreateTrunc(NegOp,
I->getType(),
I->getName() +
".neg");
402 case Instruction::Shl: {
404 IsNSW &=
I->hasNoSignedWrap();
405 if (
Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1))
406 return Builder.
CreateShl(NegOp0,
I->getOperand(1),
I->getName() +
".neg",
415 I->getName() +
".neg",
false, IsNSW);
417 case Instruction::Or: {
418 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint())
420 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
424 return Builder.
CreateNot(Ops[0],
I->getName() +
".neg");
428 case Instruction::Add: {
439 if (!IsTrulyNegation)
444 "Internal consistency check failed.");
446 if (NegatedOps.
size() == 2)
447 return Builder.
CreateAdd(NegatedOps[0], NegatedOps[1],
448 I->getName() +
".neg");
449 assert(IsTrulyNegation &&
"We should have early-exited then.");
451 if (NonNegatedOps.
size() == 2)
454 return Builder.
CreateSub(NegatedOps[0], NonNegatedOps[0],
455 I->getName() +
".neg");
457 case Instruction::Xor: {
458 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
461 if (
auto *
C = dyn_cast<Constant>(Ops[1])) {
462 if (IsTrulyNegation) {
465 I->getName() +
".neg");
470 case Instruction::Mul: {
471 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
473 Value *NegatedOp, *OtherOp;
476 if (
Value *NegOp1 = negate(Ops[1],
false,
Depth + 1)) {
479 }
else if (
Value *NegOp0 = negate(Ops[0],
false,
Depth + 1)) {
485 return Builder.
CreateMul(NegatedOp, OtherOp,
I->getName() +
".neg",
486 false, IsNSW &&
I->hasNoSignedWrap());
495[[nodiscard]]
Value *Negator::negate(
Value *V,
bool IsNSW,
unsigned Depth) {
496 NegatorMaxDepthVisited.updateMax(
Depth);
497 ++NegatorNumValuesVisited;
500 ++NumValuesVisitedInThisNegator;
505 Value *Placeholder =
reinterpret_cast<Value *
>(
static_cast<uintptr_t
>(-1));
509 auto NegationsCacheIterator = NegationsCache.find(V);
510 if (NegationsCacheIterator != NegationsCache.end()) {
511 ++NegatorNumNegationsFoundInCache;
512 Value *NegatedV = NegationsCacheIterator->second;
513 assert(NegatedV != Placeholder &&
"Encountered a cycle during negation.");
521 NegationsCache[
V] = Placeholder;
527 NegationsCache[
V] = NegatedV;
532[[nodiscard]] std::optional<Negator::Result> Negator::run(
Value *Root,
534 Value *Negated = negate(Root, IsNSW, 0);
539 I->eraseFromParent();
547 ++NegatorTotalNegationsAttempted;
548 LLVM_DEBUG(
dbgs() <<
"Negator: attempting to sink negation into " << *Root
556 std::optional<Result> Res =
N.run(Root, IsNSW);
558 LLVM_DEBUG(
dbgs() <<
"Negator: failed to sink negation into " << *Root
563 LLVM_DEBUG(
dbgs() <<
"Negator: successfully sunk negation into " << *Root
564 <<
"\n NEW: " << *Res->second <<
"\n");
565 ++NegatorNumTreesNegated;
577 <<
" instrs to InstCombine\n");
578 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
579 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)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
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
DominatorTree & getDominatorTree() 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)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
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.