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: {
326 auto *NewSelect = cast<SelectInst>(
I->clone());
328 NewSelect->swapValues();
330 NewSelect->setName(
I->getName() +
".neg");
331 Builder.
Insert(NewSelect);
335 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
338 Value *NegOp2 = negate(
I->getOperand(2), IsNSW,
Depth + 1);
342 return Builder.
CreateSelect(
I->getOperand(0), NegOp1, NegOp2,
343 I->getName() +
".neg",
I);
345 case Instruction::ShuffleVector: {
347 auto *Shuf = cast<ShuffleVectorInst>(
I);
348 Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1);
351 Value *NegOp1 = negate(
I->getOperand(1), IsNSW,
Depth + 1);
355 I->getName() +
".neg");
357 case Instruction::ExtractElement: {
359 auto *EEI = cast<ExtractElementInst>(
I);
360 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW,
Depth + 1);
364 I->getName() +
".neg");
366 case Instruction::InsertElement: {
369 auto *IEI = cast<InsertElementInst>(
I);
370 Value *NegVector = negate(IEI->getOperand(0), IsNSW,
Depth + 1);
373 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW,
Depth + 1);
377 I->getName() +
".neg");
379 case Instruction::Trunc: {
381 Value *NegOp = negate(
I->getOperand(0),
false,
Depth + 1);
384 return Builder.
CreateTrunc(NegOp,
I->getType(),
I->getName() +
".neg");
386 case Instruction::Shl: {
388 IsNSW &=
I->hasNoSignedWrap();
389 if (
Value *NegOp0 = negate(
I->getOperand(0), IsNSW,
Depth + 1))
390 return Builder.
CreateShl(NegOp0,
I->getOperand(1),
I->getName() +
".neg",
393 auto *Op1C = dyn_cast<Constant>(
I->getOperand(1));
394 if (!Op1C || !IsTrulyNegation)
399 I->getName() +
".neg",
false, IsNSW);
401 case Instruction::Or: {
402 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint())
404 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
408 return Builder.
CreateNot(Ops[0],
I->getName() +
".neg");
412 case Instruction::Add: {
423 if (!IsTrulyNegation)
428 "Internal consistency check failed.");
430 if (NegatedOps.
size() == 2)
431 return Builder.
CreateAdd(NegatedOps[0], NegatedOps[1],
432 I->getName() +
".neg");
433 assert(IsTrulyNegation &&
"We should have early-exited then.");
435 if (NonNegatedOps.
size() == 2)
438 return Builder.
CreateSub(NegatedOps[0], NonNegatedOps[0],
439 I->getName() +
".neg");
441 case Instruction::Xor: {
442 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
445 if (
auto *
C = dyn_cast<Constant>(Ops[1])) {
446 if (IsTrulyNegation) {
449 I->getName() +
".neg");
454 case Instruction::Mul: {
455 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
457 Value *NegatedOp, *OtherOp;
460 if (
Value *NegOp1 = negate(Ops[1],
false,
Depth + 1)) {
463 }
else if (
Value *NegOp0 = negate(Ops[0],
false,
Depth + 1)) {
469 return Builder.
CreateMul(NegatedOp, OtherOp,
I->getName() +
".neg",
470 false, IsNSW &&
I->hasNoSignedWrap());
479[[nodiscard]]
Value *Negator::negate(
Value *V,
bool IsNSW,
unsigned Depth) {
480 NegatorMaxDepthVisited.updateMax(
Depth);
481 ++NegatorNumValuesVisited;
484 ++NumValuesVisitedInThisNegator;
489 Value *Placeholder =
reinterpret_cast<Value *
>(
static_cast<uintptr_t
>(-1));
493 auto NegationsCacheIterator = NegationsCache.find(V);
494 if (NegationsCacheIterator != NegationsCache.end()) {
495 ++NegatorNumNegationsFoundInCache;
496 Value *NegatedV = NegationsCacheIterator->second;
497 assert(NegatedV != Placeholder &&
"Encountered a cycle during negation.");
505 NegationsCache[
V] = Placeholder;
511 NegationsCache[
V] = NegatedV;
516[[nodiscard]] std::optional<Negator::Result> Negator::run(
Value *Root,
518 Value *Negated = negate(Root, IsNSW, 0);
523 I->eraseFromParent();
531 ++NegatorTotalNegationsAttempted;
532 LLVM_DEBUG(
dbgs() <<
"Negator: attempting to sink negation into " << *Root
539 std::optional<Result> Res =
N.run(Root, IsNSW);
541 LLVM_DEBUG(
dbgs() <<
"Negator: failed to sink negation into " << *Root
546 LLVM_DEBUG(
dbgs() <<
"Negator: successfully sunk negation into " << *Root
547 <<
"\n NEW: " << *Res->second <<
"\n");
548 ++NegatorNumTreesNegated;
560 <<
" instrs to InstCombine\n");
561 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
562 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 HasNUW=false, 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 * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
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)
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)
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)
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
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.
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
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
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.