Go to the documentation of this file.
50 #include <type_traits>
62 #define DEBUG_TYPE "instcombine"
65 "Negator: Number of negations attempted to be sinked");
67 "Negator: Number of negations successfully sinked");
68 STATISTIC(NegatorMaxDepthVisited,
"Negator: Maximal traversal depth ever "
69 "reached while attempting to sink negation");
71 "Negator: How many times did the traversal depth limit was reached "
74 NegatorNumValuesVisited,
75 "Negator: Total number of values visited during attempts to sink negation");
76 STATISTIC(NegatorNumNegationsFoundInCache,
77 "Negator: How many negations did we retrieve/reuse from cache");
79 "Negator: Maximal number of values ever visited while attempting to "
81 STATISTIC(NegatorNumInstructionsCreatedTotal,
82 "Negator: Number of new negated instructions created, total");
84 "Negator: Maximal number of new instructions created during negation "
86 STATISTIC(NegatorNumInstructionsNegatedSuccess,
87 "Negator: Number of new negated instructions created in successful "
88 "negation sinking attempts");
91 "Controls Negator transformations in InstCombine pass");
95 cl::desc(
"Should we attempt to sink negations?"));
100 cl::desc(
"What is the maximal lookup depth when trying to "
101 "check for viability of negation sinking."));
107 ++NegatorNumInstructionsCreatedTotal;
108 NewInstructions.push_back(
I);
110 DL(DL_), AC(AC_), DT(DT_), IsTrulyNegation(IsTrulyNegation_) {}
112 #if LLVM_ENABLE_STATS
113 Negator::~Negator() {
114 NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
122 std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(
Instruction *
I) {
123 assert(
I->getNumOperands() == 2 &&
"Only for binops!");
124 std::array<Value *, 2> Ops{
I->getOperand(0),
I->getOperand(1)};
154 if (!isa<Instruction>(V))
163 auto *
I = cast<Instruction>(V);
164 unsigned BitWidth =
I->getType()->getScalarSizeInBits();
168 InstCombiner::BuilderTy::InsertPointGuard Guard(
Builder);
174 switch (
I->getOpcode()) {
176 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
179 return Builder.CreateNot(Ops[0],
I->getName() +
".neg");
182 case Instruction::Xor:
186 I->getName() +
".neg");
188 case Instruction::AShr:
189 case Instruction::LShr: {
193 Value *BO =
I->getOpcode() == Instruction::AShr
194 ?
Builder.CreateLShr(
I->getOperand(0),
I->getOperand(1))
195 :
Builder.CreateAShr(
I->getOperand(0),
I->getOperand(1));
196 if (
auto *NewInstr = dyn_cast<Instruction>(BO)) {
197 NewInstr->copyIRFlags(
I);
198 NewInstr->setName(
I->getName() +
".neg");
208 case Instruction::SExt:
209 case Instruction::ZExt:
211 if (
I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
212 return I->getOpcode() == Instruction::SExt
213 ?
Builder.CreateZExt(
I->getOperand(0),
I->getType(),
214 I->getName() +
".neg")
215 :
Builder.CreateSExt(
I->getOperand(0),
I->getType(),
216 I->getName() +
".neg");
222 if (
I->getOpcode() == Instruction::Sub &&
227 return Builder.CreateSub(
I->getOperand(1),
I->getOperand(0),
228 I->getName() +
".neg");
236 switch (
I->getOpcode()) {
237 case Instruction::SDiv:
241 if (
auto *Op1C = dyn_cast<Constant>(
I->getOperand(1))) {
242 if (!Op1C->containsUndefOrPoisonElement() &&
243 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
246 I->getName() +
".neg");
247 if (
auto *NewInstr = dyn_cast<Instruction>(BO))
248 NewInstr->setIsExact(
I->isExact());
257 LLVM_DEBUG(
dbgs() <<
"Negator: reached maximal allowed traversal depth in "
258 << *V <<
". Giving up.\n");
259 ++NegatorTimesDepthLimitReached;
263 switch (
I->getOpcode()) {
264 case Instruction::Freeze: {
266 Value *NegOp = negate(
I->getOperand(0),
Depth + 1);
269 return Builder.CreateFreeze(NegOp,
I->getName() +
".neg");
271 case Instruction::PHI: {
273 auto *PHI = cast<PHINode>(
I);
275 for (
auto I :
zip(PHI->incoming_values(), NegatedIncomingValues)) {
276 if (!(std::get<1>(
I) =
277 negate(std::get<0>(
I),
Depth + 1)))
282 PHI->getType(), PHI->getNumOperands(), PHI->getName() +
".neg");
283 for (
auto I :
zip(NegatedIncomingValues, PHI->blocks()))
291 auto *NewSelect = cast<SelectInst>(
I->clone());
293 NewSelect->swapValues();
295 NewSelect->setName(
I->getName() +
".neg");
300 Value *NegOp1 = negate(
I->getOperand(1),
Depth + 1);
303 Value *NegOp2 = negate(
I->getOperand(2),
Depth + 1);
307 return Builder.CreateSelect(
I->getOperand(0), NegOp1, NegOp2,
308 I->getName() +
".neg",
I);
310 case Instruction::ShuffleVector: {
312 auto *Shuf = cast<ShuffleVectorInst>(
I);
313 Value *NegOp0 = negate(
I->getOperand(0),
Depth + 1);
316 Value *NegOp1 = negate(
I->getOperand(1),
Depth + 1);
319 return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
320 I->getName() +
".neg");
322 case Instruction::ExtractElement: {
324 auto *EEI = cast<ExtractElementInst>(
I);
325 Value *NegVector = negate(EEI->getVectorOperand(),
Depth + 1);
328 return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
329 I->getName() +
".neg");
331 case Instruction::InsertElement: {
334 auto *IEI = cast<InsertElementInst>(
I);
335 Value *NegVector = negate(IEI->getOperand(0),
Depth + 1);
338 Value *NegNewElt = negate(IEI->getOperand(1),
Depth + 1);
341 return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
342 I->getName() +
".neg");
344 case Instruction::Trunc: {
346 Value *NegOp = negate(
I->getOperand(0),
Depth + 1);
349 return Builder.CreateTrunc(NegOp,
I->getType(),
I->getName() +
".neg");
351 case Instruction::Shl: {
353 if (
Value *NegOp0 = negate(
I->getOperand(0),
Depth + 1))
354 return Builder.CreateShl(NegOp0,
I->getOperand(1),
I->getName() +
".neg");
356 auto *Op1C = dyn_cast<Constant>(
I->getOperand(1));
362 I->getName() +
".neg");
364 case Instruction::Or: {
368 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
372 return Builder.CreateNot(Ops[0],
I->getName() +
".neg");
387 if (!IsTrulyNegation)
391 assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
392 "Internal consistency sanity check.");
394 if (NegatedOps.size() == 2)
395 return Builder.CreateAdd(NegatedOps[0], NegatedOps[1],
396 I->getName() +
".neg");
397 assert(IsTrulyNegation &&
"We should have early-exited then.");
399 if (NonNegatedOps.size() == 2)
402 return Builder.CreateSub(NegatedOps[0], NonNegatedOps[0],
403 I->getName() +
".neg");
405 case Instruction::Xor: {
406 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
409 if (
auto *
C = dyn_cast<Constant>(Ops[1])) {
412 I->getName() +
".neg");
416 case Instruction::Mul: {
417 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(
I);
419 Value *NegatedOp, *OtherOp;
422 if (
Value *NegOp1 = negate(Ops[1],
Depth + 1)) {
425 }
else if (
Value *NegOp0 = negate(Ops[0],
Depth + 1)) {
431 return Builder.CreateMul(NegatedOp, OtherOp,
I->getName() +
".neg");
441 NegatorMaxDepthVisited.updateMax(
Depth);
442 ++NegatorNumValuesVisited;
444 #if LLVM_ENABLE_STATS
445 ++NumValuesVisitedInThisNegator;
450 Value *Placeholder =
reinterpret_cast<Value *
>(
static_cast<uintptr_t
>(-1));
454 auto NegationsCacheIterator = NegationsCache.find(V);
455 if (NegationsCacheIterator != NegationsCache.end()) {
456 ++NegatorNumNegationsFoundInCache;
457 Value *NegatedV = NegationsCacheIterator->second;
458 assert(NegatedV != Placeholder &&
"Encountered a cycle during negation.");
466 NegationsCache[V] = Placeholder;
472 NegationsCache[V] = NegatedV;
478 Value *Negated = negate(Root, 0);
483 I->eraseFromParent();
491 ++NegatorTotalNegationsAttempted;
492 LLVM_DEBUG(
dbgs() <<
"Negator: attempting to sink negation into " << *Root
502 LLVM_DEBUG(
dbgs() <<
"Negator: failed to sink negation into " << *Root
507 LLVM_DEBUG(
dbgs() <<
"Negator: successfully sunk negation into " << *Root
508 <<
"\n NEW: " << *Res->second <<
"\n");
509 ++NegatorNumTreesNegated;
521 <<
" instrs to InstCombine\n");
522 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
523 NegatorNumInstructionsNegatedSuccess += Res->first.size();
This class represents lattice values for constants.
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
static Constant * getNot(Constant *C)
A parsed version of the target data layout string in and methods for querying it.
bool hasOneUse() const
Return true if there is exactly one use of this value.
DominatorTree & getDominatorTree() const
DEBUG_COUNTER(NegatorCounter, "instcombine-negator", "Controls Negator transformations in InstCombine pass")
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
bool match(Val *V, const Pattern &P)
(vector float) vec_cmpeq(*A, *B) C
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
static Constant * getAllOnesValue(Type *Ty)
static bool shouldExecute(unsigned CounterName)
STATISTIC(NumFunctions, "Total number of functions")
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
static constexpr unsigned NegatorDefaultMaxDepth
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
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."))
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
AssumptionCache & getAssumptionCache() const
const DataLayout & getDataLayout() const
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
This is an important class for using LLVM in a threaded context.
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
initializer< Ty > init(const Ty &Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static LLVM_NODISCARD Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
TargetFolder - Create constants with target dependent folding.
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
constexpr unsigned BitWidth
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)
Matches a register negated by a G_SUB.
static cl::opt< bool > NegatorEnabled("instcombine-negator-enabled", cl::init(true), cl::desc("Should we attempt to sink negations?"))
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
LLVM Value Representation.
@ Xor
Bitwise or logical XOR of integers.
reference emplace_back(ArgTypes &&... Args)