56#define DEBUG_TYPE "instcombine"
59 "Negator: Number of negations attempted to be sinked");
61 "Negator: Number of negations successfully sinked");
62STATISTIC(NegatorMaxDepthVisited,
"Negator: Maximal traversal depth ever "
63 "reached while attempting to sink negation");
65 "Negator: How many times did the traversal depth limit was reached "
68 NegatorNumValuesVisited,
69 "Negator: Total number of values visited during attempts to sink negation");
71 "Negator: How many negations did we retrieve/reuse from cache");
73 "Negator: Maximal number of values ever visited while attempting to "
76 "Negator: Number of new negated instructions created, total");
78 "Negator: Maximal number of new instructions created during negation "
81 "Negator: Number of new negated instructions created in successful "
82 "negation sinking attempts");
85 "Controls Negator transformations in InstCombine pass");
89 cl::desc(
"Should we attempt to sink negations?"));
94 cl::desc(
"What is the maximal lookup depth when trying to "
95 "check for viability of negation sinking."));
100 ++NegatorNumInstructionsCreatedTotal;
101 NewInstructions.push_back(
I);
103 IsTrulyNegation(IsTrulyNegation_) {}
107 NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
115std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(
Instruction *
I) {
116 assert(
I->getNumOperands() == 2 &&
"Only for binops!");
117 std::array<Value *, 2> Ops{
I->getOperand(0),
I->getOperand(1)};
126[[nodiscard]]
Value *Negator::visitImpl(
Value *V,
bool IsNSW,
unsigned Depth) {
132 if (
V->getType()->isIntOrIntVectorTy(1))
147 if (!isa<Instruction>(V))
153 if (!
V->hasOneUse() && !IsTrulyNegation)
156 auto *
I = cast<Instruction>(V);
157 unsigned BitWidth =
I->getType()->getScalarSizeInBits();
167 switch (
I->getOpcode()) {
168 case Instruction::Add: {
169 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
172 return Builder.
CreateNot(Ops[0],
I->getName() +
".neg");
175 case Instruction::Xor:
178 return Builder.
CreateAdd(
X, ConstantInt::get(
X->getType(), 1),
179 I->getName() +
".neg");
181 case Instruction::AShr:
182 case Instruction::LShr: {
186 Value *BO =
I->getOpcode() == Instruction::AShr
187 ? Builder.
CreateLShr(
I->getOperand(0),
I->getOperand(1))
188 : Builder.
CreateAShr(
I->getOperand(0),
I->getOperand(1));
189 if (
auto *NewInstr = dyn_cast<Instruction>(BO)) {
190 NewInstr->copyIRFlags(
I);
191 NewInstr->
setName(
I->getName() +
".neg");
201 case Instruction::SExt:
202 case Instruction::ZExt:
204 if (
I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
205 return I->getOpcode() == Instruction::SExt
207 I->getName() +
".neg")
209 I->getName() +
".neg");
211 case Instruction::Select: {
214 auto *Sel = cast<SelectInst>(
I);
220 return Builder.
CreateSelect(Sel->getCondition(), NegTrueC, NegFalseC,
221 I->getName() +
".neg",
I);
229 if (
I->getOpcode() == Instruction::Sub &&
234 return Builder.
CreateSub(
I->getOperand(1),
I->getOperand(0),
235 I->getName() +
".neg",
false,
236 IsNSW &&
I->hasNoSignedWrap());
244 switch (
I->getOpcode()) {
245 case Instruction::ZExt: {
249 unsigned SrcWidth =
SrcOp->getType()->getScalarSizeInBits();
250 const APInt &FullShift =
APInt(SrcWidth, SrcWidth - 1);
251 if (IsTrulyNegation &&
258 case Instruction::And: {
264 unsigned BW =
X->getType()->getScalarSizeInBits();
265 Constant *BWMinusOne = ConstantInt::get(
X->getType(), BW - 1);
272 case Instruction::SDiv:
276 if (
auto *Op1C = dyn_cast<Constant>(
I->getOperand(1))) {
277 if (!Op1C->containsUndefOrPoisonElement() &&
278 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
281 I->getName() +
".neg");
282 if (
auto *NewInstr = dyn_cast<Instruction>(BO))
283 NewInstr->setIsExact(
I->isExact());
292 LLVM_DEBUG(
dbgs() <<
"Negator: reached maximal allowed traversal depth in "
293 << *V <<
". Giving up.\n");
294 ++NegatorTimesDepthLimitReached;
298 switch (
I->getOpcode()) {
299 case Instruction::Freeze: {
301 Value *NegOp = negate(
I->getOperand(0), IsNSW,
Depth + 1);
306 case Instruction::PHI: {
308 auto *
PHI = cast<PHINode>(
I);
310 for (
auto I :
zip(
PHI->incoming_values(), NegatedIncomingValues)) {
311 if (!(std::get<1>(
I) =
312 negate(std::get<0>(
I), IsNSW,
Depth + 1)))
317 PHI->getType(),
PHI->getNumOperands(),
PHI->getName() +
".neg");
318 for (
auto I :
zip(NegatedIncomingValues,
PHI->blocks()))
322 case Instruction::Select: {
327 auto *NewSelect = cast<SelectInst>(
I->clone());
329 NewSelect->swapValues();
331 NewSelect->setName(
I->getName() +
".neg");
332 Builder.
Insert(NewSelect);
336 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
339 Value *NegOp2 = negate(
I->getOperand(2), IsNSW,
Depth + 1);
343 return Builder.
CreateSelect(
I->getOperand(0), NegOp1, NegOp2,
344 I->getName() +
".neg",
I);
346 case Instruction::ShuffleVector: {
348 auto *Shuf = cast<ShuffleVectorInst>(
I);
349 Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1);
352 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
356 I->getName() +
".neg");
358 case Instruction::ExtractElement: {
360 auto *EEI = cast<ExtractElementInst>(
I);
361 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW,
Depth + 1);
365 I->getName() +
".neg");
367 case Instruction::InsertElement: {
370 auto *IEI = cast<InsertElementInst>(
I);
371 Value *NegVector = negate(IEI->getOperand(0), IsNSW,
Depth + 1);
374 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW,
Depth + 1);
378 I->getName() +
".neg");
380 case Instruction::Trunc: {
382 Value *NegOp = negate(
I->getOperand(0),
false,
Depth + 1);
385 return Builder.
CreateTrunc(NegOp,
I->getType(),
I->getName() +
".neg");
387 case Instruction::Shl: {
389 IsNSW &=
I->hasNoSignedWrap();
390 if (
Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1))
391 return Builder.
CreateShl(NegOp0,
I->getOperand(1),
I->getName() +
".neg",
394 auto *Op1C = dyn_cast<Constant>(
I->getOperand(1));
395 if (!Op1C || !IsTrulyNegation)
400 I->getName() +
".neg",
false, IsNSW);
402 case Instruction::Or: {
403 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint())
405 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
409 return Builder.
CreateNot(Ops[0],
I->getName() +
".neg");
413 case Instruction::Add: {
424 if (!IsTrulyNegation)
429 "Internal consistency check failed.");
431 if (NegatedOps.
size() == 2)
432 return Builder.
CreateAdd(NegatedOps[0], NegatedOps[1],
433 I->getName() +
".neg");
434 assert(IsTrulyNegation &&
"We should have early-exited then.");
436 if (NonNegatedOps.
size() == 2)
439 return Builder.
CreateSub(NegatedOps[0], NonNegatedOps[0],
440 I->getName() +
".neg");
442 case Instruction::Xor: {
443 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
446 if (
auto *
C = dyn_cast<Constant>(Ops[1])) {
447 if (IsTrulyNegation) {
450 I->getName() +
".neg");
455 case Instruction::Mul: {
456 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
458 Value *NegatedOp, *OtherOp;
461 if (
Value *NegOp1 = negate(Ops[1],
false,
Depth + 1)) {
464 }
else if (
Value *NegOp0 = negate(Ops[0],
false,
Depth + 1)) {
470 return Builder.
CreateMul(NegatedOp, OtherOp,
I->getName() +
".neg",
471 false, IsNSW &&
I->hasNoSignedWrap());
480[[nodiscard]]
Value *Negator::negate(
Value *V,
bool IsNSW,
unsigned Depth) {
481 NegatorMaxDepthVisited.updateMax(
Depth);
482 ++NegatorNumValuesVisited;
485 ++NumValuesVisitedInThisNegator;
490 Value *Placeholder =
reinterpret_cast<Value *
>(
static_cast<uintptr_t
>(-1));
494 auto NegationsCacheIterator = NegationsCache.find(V);
495 if (NegationsCacheIterator != NegationsCache.end()) {
496 ++NegatorNumNegationsFoundInCache;
497 Value *NegatedV = NegationsCacheIterator->second;
498 assert(NegatedV != Placeholder &&
"Encountered a cycle during negation.");
506 NegationsCache[
V] = Placeholder;
512 NegationsCache[
V] = NegatedV;
517[[nodiscard]] std::optional<Negator::Result> Negator::run(
Value *Root,
519 Value *Negated = negate(Root, IsNSW, 0);
524 I->eraseFromParent();
532 ++NegatorTotalNegationsAttempted;
533 LLVM_DEBUG(
dbgs() <<
"Negator: attempting to sink negation into " << *Root
540 std::optional<Result> Res =
N.run(Root, IsNSW);
542 LLVM_DEBUG(
dbgs() <<
"Negator: failed to sink negation into " << *Root
547 LLVM_DEBUG(
dbgs() <<
"Negator: successfully sunk negation into " << *Root
548 <<
"\n NEW: " << *Res->second <<
"\n");
549 ++NegatorNumTreesNegated;
561 <<
" instrs to InstCombine\n");
562 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
563 NegatorNumInstructionsNegatedSuccess += Res->first.size();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
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 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)
This defines the Use class.
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 * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
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="")
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.
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)
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.
match_combine_or< CastOperator_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
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.