LLVM  14.0.0git
InstCombineNegator.cpp
Go to the documentation of this file.
1 //===- InstCombineNegator.cpp -----------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements sinking of negation into expression trees,
10 // as long as that can be done without increasing instruction count.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/ADT/StringRef.h"
24 #include "llvm/ADT/Twine.h"
28 #include "llvm/IR/Constant.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DebugLoc.h"
31 #include "llvm/IR/IRBuilder.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/PatternMatch.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/Use.h"
37 #include "llvm/IR/User.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/Compiler.h"
46 #include <cassert>
47 #include <cstdint>
48 #include <functional>
49 #include <tuple>
50 #include <type_traits>
51 #include <utility>
52 
53 namespace llvm {
54 class AssumptionCache;
55 class DataLayout;
56 class DominatorTree;
57 class LLVMContext;
58 } // namespace llvm
59 
60 using namespace llvm;
61 
62 #define DEBUG_TYPE "instcombine"
63 
64 STATISTIC(NegatorTotalNegationsAttempted,
65  "Negator: Number of negations attempted to be sinked");
66 STATISTIC(NegatorNumTreesNegated,
67  "Negator: Number of negations successfully sinked");
68 STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
69  "reached while attempting to sink negation");
70 STATISTIC(NegatorTimesDepthLimitReached,
71  "Negator: How many times did the traversal depth limit was reached "
72  "during sinking");
73 STATISTIC(
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");
78 STATISTIC(NegatorMaxTotalValuesVisited,
79  "Negator: Maximal number of values ever visited while attempting to "
80  "sink negation");
81 STATISTIC(NegatorNumInstructionsCreatedTotal,
82  "Negator: Number of new negated instructions created, total");
83 STATISTIC(NegatorMaxInstructionsCreated,
84  "Negator: Maximal number of new instructions created during negation "
85  "attempt");
86 STATISTIC(NegatorNumInstructionsNegatedSuccess,
87  "Negator: Number of new negated instructions created in successful "
88  "negation sinking attempts");
89 
90 DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
91  "Controls Negator transformations in InstCombine pass");
92 
93 static cl::opt<bool>
94  NegatorEnabled("instcombine-negator-enabled", cl::init(true),
95  cl::desc("Should we attempt to sink negations?"));
96 
97 static cl::opt<unsigned>
98  NegatorMaxDepth("instcombine-negator-max-depth",
100  cl::desc("What is the maximal lookup depth when trying to "
101  "check for viability of negation sinking."));
102 
103 Negator::Negator(LLVMContext &C, const DataLayout &DL_, AssumptionCache &AC_,
104  const DominatorTree &DT_, bool IsTrulyNegation_)
105  : Builder(C, TargetFolder(DL_),
107  ++NegatorNumInstructionsCreatedTotal;
108  NewInstructions.push_back(I);
109  })),
110  DL(DL_), AC(AC_), DT(DT_), IsTrulyNegation(IsTrulyNegation_) {}
111 
112 #if LLVM_ENABLE_STATS
113 Negator::~Negator() {
114  NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
115 }
116 #endif
117 
118 // Due to the InstCombine's worklist management, there are no guarantees that
119 // each instruction we'll encounter has been visited by InstCombine already.
120 // In particular, most importantly for us, that means we have to canonicalize
121 // constants to RHS ourselves, since that is helpful sometimes.
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)};
125  if (I->isCommutative() && InstCombiner::getComplexity(I->getOperand(0)) <
126  InstCombiner::getComplexity(I->getOperand(1)))
127  std::swap(Ops[0], Ops[1]);
128  return Ops;
129 }
130 
131 // FIXME: can this be reworked into a worklist-based algorithm while preserving
132 // the depth-first, early bailout traversal?
133 LLVM_NODISCARD Value *Negator::visitImpl(Value *V, unsigned Depth) {
134  // -(undef) -> undef.
135  if (match(V, m_Undef()))
136  return V;
137 
138  // In i1, negation can simply be ignored.
139  if (V->getType()->isIntOrIntVectorTy(1))
140  return V;
141 
142  Value *X;
143 
144  // -(-(X)) -> X.
145  if (match(V, m_Neg(m_Value(X))))
146  return X;
147 
148  // Integral constants can be freely negated.
149  if (match(V, m_AnyIntegralConstant()))
150  return ConstantExpr::getNeg(cast<Constant>(V), /*HasNUW=*/false,
151  /*HasNSW=*/false);
152 
153  // If we have a non-instruction, then give up.
154  if (!isa<Instruction>(V))
155  return nullptr;
156 
157  // If we have started with a true negation (i.e. `sub 0, %y`), then if we've
158  // got instruction that does not require recursive reasoning, we can still
159  // negate it even if it has other uses, without increasing instruction count.
160  if (!V->hasOneUse() && !IsTrulyNegation)
161  return nullptr;
162 
163  auto *I = cast<Instruction>(V);
164  unsigned BitWidth = I->getType()->getScalarSizeInBits();
165 
166  // We must preserve the insertion point and debug info that is set in the
167  // builder at the time this function is called.
168  InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
169  // And since we are trying to negate instruction I, that tells us about the
170  // insertion point and the debug info that we need to keep.
171  Builder.SetInsertPoint(I);
172 
173  // In some cases we can give the answer without further recursion.
174  switch (I->getOpcode()) {
175  case Instruction::Add: {
176  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
177  // `inc` is always negatible.
178  if (match(Ops[1], m_One()))
179  return Builder.CreateNot(Ops[0], I->getName() + ".neg");
180  break;
181  }
182  case Instruction::Xor:
183  // `not` is always negatible.
184  if (match(I, m_Not(m_Value(X))))
185  return Builder.CreateAdd(X, ConstantInt::get(X->getType(), 1),
186  I->getName() + ".neg");
187  break;
188  case Instruction::AShr:
189  case Instruction::LShr: {
190  // Right-shift sign bit smear is negatible.
191  const APInt *Op1Val;
192  if (match(I->getOperand(1), m_APInt(Op1Val)) && *Op1Val == BitWidth - 1) {
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");
199  }
200  return BO;
201  }
202  // While we could negate exact arithmetic shift:
203  // ashr exact %x, C --> sdiv exact i8 %x, -1<<C
204  // iff C != 0 and C u< bitwidth(%x), we don't want to,
205  // because division is *THAT* much worse than a shift.
206  break;
207  }
208  case Instruction::SExt:
209  case Instruction::ZExt:
210  // `*ext` of i1 is always negatible
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");
217  break;
218  default:
219  break; // Other instructions require recursive reasoning.
220  }
221 
222  if (I->getOpcode() == Instruction::Sub &&
223  (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
224  // `sub` is always negatible.
225  // However, only do this either if the old `sub` doesn't stick around, or
226  // it was subtracting from a constant. Otherwise, this isn't profitable.
227  return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
228  I->getName() + ".neg");
229  }
230 
231  // Some other cases, while still don't require recursion,
232  // are restricted to the one-use case.
233  if (!V->hasOneUse())
234  return nullptr;
235 
236  switch (I->getOpcode()) {
237  case Instruction::SDiv:
238  // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
239  // While this is normally not behind a use-check,
240  // let's consider division to be special since it's costly.
241  if (auto *Op1C = dyn_cast<Constant>(I->getOperand(1))) {
242  if (!Op1C->containsUndefOrPoisonElement() &&
243  Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
244  Value *BO =
245  Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(Op1C),
246  I->getName() + ".neg");
247  if (auto *NewInstr = dyn_cast<Instruction>(BO))
248  NewInstr->setIsExact(I->isExact());
249  return BO;
250  }
251  }
252  break;
253  }
254 
255  // Rest of the logic is recursive, so if it's time to give up then it's time.
256  if (Depth > NegatorMaxDepth) {
257  LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
258  << *V << ". Giving up.\n");
259  ++NegatorTimesDepthLimitReached;
260  return nullptr;
261  }
262 
263  switch (I->getOpcode()) {
264  case Instruction::Freeze: {
265  // `freeze` is negatible if its operand is negatible.
266  Value *NegOp = negate(I->getOperand(0), Depth + 1);
267  if (!NegOp) // Early return.
268  return nullptr;
269  return Builder.CreateFreeze(NegOp, I->getName() + ".neg");
270  }
271  case Instruction::PHI: {
272  // `phi` is negatible if all the incoming values are negatible.
273  auto *PHI = cast<PHINode>(I);
274  SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
275  for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
276  if (!(std::get<1>(I) =
277  negate(std::get<0>(I), Depth + 1))) // Early return.
278  return nullptr;
279  }
280  // All incoming values are indeed negatible. Create negated PHI node.
281  PHINode *NegatedPHI = Builder.CreatePHI(
282  PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");
283  for (auto I : zip(NegatedIncomingValues, PHI->blocks()))
284  NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));
285  return NegatedPHI;
286  }
287  case Instruction::Select: {
288  if (isKnownNegation(I->getOperand(1), I->getOperand(2))) {
289  // Of one hand of select is known to be negation of another hand,
290  // just swap the hands around.
291  auto *NewSelect = cast<SelectInst>(I->clone());
292  // Just swap the operands of the select.
293  NewSelect->swapValues();
294  // Don't swap prof metadata, we didn't change the branch behavior.
295  NewSelect->setName(I->getName() + ".neg");
296  Builder.Insert(NewSelect);
297  return NewSelect;
298  }
299  // `select` is negatible if both hands of `select` are negatible.
300  Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
301  if (!NegOp1) // Early return.
302  return nullptr;
303  Value *NegOp2 = negate(I->getOperand(2), Depth + 1);
304  if (!NegOp2)
305  return nullptr;
306  // Do preserve the metadata!
307  return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
308  I->getName() + ".neg", /*MDFrom=*/I);
309  }
310  case Instruction::ShuffleVector: {
311  // `shufflevector` is negatible if both operands are negatible.
312  auto *Shuf = cast<ShuffleVectorInst>(I);
313  Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
314  if (!NegOp0) // Early return.
315  return nullptr;
316  Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
317  if (!NegOp1)
318  return nullptr;
319  return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
320  I->getName() + ".neg");
321  }
322  case Instruction::ExtractElement: {
323  // `extractelement` is negatible if source operand is negatible.
324  auto *EEI = cast<ExtractElementInst>(I);
325  Value *NegVector = negate(EEI->getVectorOperand(), Depth + 1);
326  if (!NegVector) // Early return.
327  return nullptr;
328  return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
329  I->getName() + ".neg");
330  }
331  case Instruction::InsertElement: {
332  // `insertelement` is negatible if both the source vector and
333  // element-to-be-inserted are negatible.
334  auto *IEI = cast<InsertElementInst>(I);
335  Value *NegVector = negate(IEI->getOperand(0), Depth + 1);
336  if (!NegVector) // Early return.
337  return nullptr;
338  Value *NegNewElt = negate(IEI->getOperand(1), Depth + 1);
339  if (!NegNewElt) // Early return.
340  return nullptr;
341  return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
342  I->getName() + ".neg");
343  }
344  case Instruction::Trunc: {
345  // `trunc` is negatible if its operand is negatible.
346  Value *NegOp = negate(I->getOperand(0), Depth + 1);
347  if (!NegOp) // Early return.
348  return nullptr;
349  return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
350  }
351  case Instruction::Shl: {
352  // `shl` is negatible if the first operand is negatible.
353  if (Value *NegOp0 = negate(I->getOperand(0), Depth + 1))
354  return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg");
355  // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
356  auto *Op1C = dyn_cast<Constant>(I->getOperand(1));
357  if (!Op1C) // Early return.
358  return nullptr;
359  return Builder.CreateMul(
360  I->getOperand(0),
361  ConstantExpr::getShl(Constant::getAllOnesValue(Op1C->getType()), Op1C),
362  I->getName() + ".neg");
363  }
364  case Instruction::Or: {
365  if (!haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1), DL, &AC, I,
366  &DT))
367  return nullptr; // Don't know how to handle `or` in general.
368  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
369  // `or`/`add` are interchangeable when operands have no common bits set.
370  // `inc` is always negatible.
371  if (match(Ops[1], m_One()))
372  return Builder.CreateNot(Ops[0], I->getName() + ".neg");
373  // Else, just defer to Instruction::Add handling.
375  }
376  case Instruction::Add: {
377  // `add` is negatible if both of its operands are negatible.
378  SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
379  for (Value *Op : I->operands()) {
380  // Can we sink the negation into this operand?
381  if (Value *NegOp = negate(Op, Depth + 1)) {
382  NegatedOps.emplace_back(NegOp); // Successfully negated operand!
383  continue;
384  }
385  // Failed to sink negation into this operand. IFF we started from negation
386  // and we manage to sink negation into one operand, we can still do this.
387  if (!IsTrulyNegation)
388  return nullptr;
389  NonNegatedOps.emplace_back(Op); // Just record which operand that was.
390  }
391  assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
392  "Internal consistency sanity check.");
393  // Did we manage to sink negation into both of the operands?
394  if (NegatedOps.size() == 2) // Then we get to keep the `add`!
395  return Builder.CreateAdd(NegatedOps[0], NegatedOps[1],
396  I->getName() + ".neg");
397  assert(IsTrulyNegation && "We should have early-exited then.");
398  // Completely failed to sink negation?
399  if (NonNegatedOps.size() == 2)
400  return nullptr;
401  // 0-(a+b) --> (-a)-b
402  return Builder.CreateSub(NegatedOps[0], NonNegatedOps[0],
403  I->getName() + ".neg");
404  }
405  case Instruction::Xor: {
406  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
407  // `xor` is negatible if one of its operands is invertible.
408  // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
409  if (auto *C = dyn_cast<Constant>(Ops[1])) {
410  Value *Xor = Builder.CreateXor(Ops[0], ConstantExpr::getNot(C));
411  return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
412  I->getName() + ".neg");
413  }
414  return nullptr;
415  }
416  case Instruction::Mul: {
417  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
418  // `mul` is negatible if one of its operands is negatible.
419  Value *NegatedOp, *OtherOp;
420  // First try the second operand, in case it's a constant it will be best to
421  // just invert it instead of sinking the `neg` deeper.
422  if (Value *NegOp1 = negate(Ops[1], Depth + 1)) {
423  NegatedOp = NegOp1;
424  OtherOp = Ops[0];
425  } else if (Value *NegOp0 = negate(Ops[0], Depth + 1)) {
426  NegatedOp = NegOp0;
427  OtherOp = Ops[1];
428  } else
429  // Can't negate either of them.
430  return nullptr;
431  return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg");
432  }
433  default:
434  return nullptr; // Don't know, likely not negatible for free.
435  }
436 
437  llvm_unreachable("Can't get here. We always return from switch.");
438 }
439 
440 LLVM_NODISCARD Value *Negator::negate(Value *V, unsigned Depth) {
441  NegatorMaxDepthVisited.updateMax(Depth);
442  ++NegatorNumValuesVisited;
443 
444 #if LLVM_ENABLE_STATS
445  ++NumValuesVisitedInThisNegator;
446 #endif
447 
448 #ifndef NDEBUG
449  // We can't ever have a Value with such an address.
450  Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
451 #endif
452 
453  // Did we already try to negate this value?
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.");
459  return NegatedV;
460  }
461 
462 #ifndef NDEBUG
463  // We did not find a cached result for negation of V. While there,
464  // let's temporairly cache a placeholder value, with the idea that if later
465  // during negation we fetch it from cache, we'll know we're in a cycle.
466  NegationsCache[V] = Placeholder;
467 #endif
468 
469  // No luck. Try negating it for real.
470  Value *NegatedV = visitImpl(V, Depth);
471  // And cache the (real) result for the future.
472  NegationsCache[V] = NegatedV;
473 
474  return NegatedV;
475 }
476 
477 LLVM_NODISCARD Optional<Negator::Result> Negator::run(Value *Root) {
478  Value *Negated = negate(Root, /*Depth=*/0);
479  if (!Negated) {
480  // We must cleanup newly-inserted instructions, to avoid any potential
481  // endless combine looping.
482  for (Instruction *I : llvm::reverse(NewInstructions))
483  I->eraseFromParent();
484  return llvm::None;
485  }
486  return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
487 }
488 
489 LLVM_NODISCARD Value *Negator::Negate(bool LHSIsZero, Value *Root,
490  InstCombinerImpl &IC) {
491  ++NegatorTotalNegationsAttempted;
492  LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
493  << "\n");
494 
495  if (!NegatorEnabled || !DebugCounter::shouldExecute(NegatorCounter))
496  return nullptr;
497 
499  IC.getDominatorTree(), LHSIsZero);
500  Optional<Result> Res = N.run(Root);
501  if (!Res) { // Negation failed.
502  LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
503  << "\n");
504  return nullptr;
505  }
506 
507  LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
508  << "\n NEW: " << *Res->second << "\n");
509  ++NegatorNumTreesNegated;
510 
511  // We must temporarily unset the 'current' insertion point and DebugLoc of the
512  // InstCombine's IRBuilder so that it won't interfere with the ones we have
513  // already specified when producing negated instructions.
517 
518  // And finally, we must add newly-created instructions into the InstCombine's
519  // worklist (in a proper order!) so it can attempt to combine them.
520  LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
521  << " instrs to InstCombine\n");
522  NegatorMaxInstructionsCreated.updateMax(Res->first.size());
523  NegatorNumInstructionsNegatedSuccess += Res->first.size();
524 
525  // They are in def-use order, so nothing fancy, just insert them in order.
526  for (Instruction *I : Res->first)
527  IC.Builder.Insert(I, I->getName());
528 
529  // And return the new root.
530  return Res->second;
531 }
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::haveNoCommonBitsSet
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.
Definition: ValueTracking.cpp:258
llvm::ConstantExpr::getNot
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2659
Optional.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
InstCombiner.h
llvm::InstCombiner::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:368
DEBUG_COUNTER
DEBUG_COUNTER(NegatorCounter, "instcombine-negator", "Controls Negator transformations in InstCombine pass")
StringRef.h
TargetFolder.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:56
Statistic.h
ErrorHandling.h
llvm::IRBuilderBase::ClearInsertionPoint
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:173
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
APInt.h
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
llvm::Optional
Definition: APInt.h:33
STLExtras.h
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:270
CommandLine.h
InstCombineInternal.h
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
Twine.h
llvm::IRBuilderBase::SetCurrentDebugLocation
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:208
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:405
llvm::Instruction
Definition: Instruction.h:45
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
llvm::ConstantInt::get
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.
Definition: Constants.cpp:900
DebugLoc.h
llvm::InstCombiner::getComplexity
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:125
PatternMatch.h
llvm::None
const NoneType None
Definition: None.h:23
NegatorDefaultMaxDepth
static constexpr unsigned NegatorDefaultMaxDepth
Definition: InstCombineInternal.h:39
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
NegatorMaxDepth
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."))
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:513
llvm::cl::opt< bool >
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:781
llvm::InstCombiner::getAssumptionCache
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:366
llvm::InstCombiner::getDataLayout
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:369
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ConstantExpr::getShl
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2741
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
ArrayRef.h
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::Negator::Negate
static LLVM_NODISCARD Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:489
llvm::isKnownNegation
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
Definition: ValueTracking.cpp:5859
iterator_range.h
llvm::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:732
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:77
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::Negator
Definition: InstCombineInternal.h:738
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
None.h
llvm::PatternMatch::m_Undef
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
Compiler.h
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:978
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:367
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:273
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
Constant.h
llvm::TargetFolder
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:32
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2646
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::IRBuilderBase::Insert
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Definition: IRBuilder.h:149
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:207
Casting.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
DebugCounter.h
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
Instructions.h
llvm::PatternMatch::m_AnyIntegralConstant
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:436
SmallVector.h
User.h
N
#define N
llvm::MIPatternMatch::m_Neg
BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)
Matches a register negated by a G_SUB.
Definition: MIPatternMatch.h:568
NegatorEnabled
static cl::opt< bool > NegatorEnabled("instcombine-negator-enabled", cl::init(true), cl::desc("Should we attempt to sink negations?"))
llvm::PHINode
Definition: Instructions.h:2625
llvm::MIPatternMatch::m_Not
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
Definition: MIPatternMatch.h:576
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:414
raw_ostream.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908