LLVM  15.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  case Instruction::Select: {
219  // If both arms of the select are constants, we don't need to recurse.
220  // Therefore, this transform is not limited by uses.
221  auto *Sel = cast<SelectInst>(I);
222  Constant *TrueC, *FalseC;
223  if (match(Sel->getTrueValue(), m_ImmConstant(TrueC)) &&
224  match(Sel->getFalseValue(), m_ImmConstant(FalseC))) {
225  Constant *NegTrueC = ConstantExpr::getNeg(TrueC);
226  Constant *NegFalseC = ConstantExpr::getNeg(FalseC);
227  return Builder.CreateSelect(Sel->getCondition(), NegTrueC, NegFalseC,
228  I->getName() + ".neg", /*MDFrom=*/I);
229  }
230  break;
231  }
232  default:
233  break; // Other instructions require recursive reasoning.
234  }
235 
236  if (I->getOpcode() == Instruction::Sub &&
237  (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
238  // `sub` is always negatible.
239  // However, only do this either if the old `sub` doesn't stick around, or
240  // it was subtracting from a constant. Otherwise, this isn't profitable.
241  return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
242  I->getName() + ".neg");
243  }
244 
245  // Some other cases, while still don't require recursion,
246  // are restricted to the one-use case.
247  if (!V->hasOneUse())
248  return nullptr;
249 
250  switch (I->getOpcode()) {
251  case Instruction::And: {
252  Constant *ShAmt;
253  // sub(y,and(lshr(x,C),1)) --> add(ashr(shl(x,(BW-1)-C),BW-1),y)
255  m_LShr(m_Value(X), m_ImmConstant(ShAmt)))),
256  m_One()))) {
257  unsigned BW = X->getType()->getScalarSizeInBits();
258  Constant *BWMinusOne = ConstantInt::get(X->getType(), BW - 1);
259  Value *R = Builder.CreateShl(X, Builder.CreateSub(BWMinusOne, ShAmt));
260  R = Builder.CreateAShr(R, BWMinusOne);
261  return Builder.CreateTruncOrBitCast(R, I->getType());
262  }
263  break;
264  }
265  case Instruction::SDiv:
266  // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
267  // While this is normally not behind a use-check,
268  // let's consider division to be special since it's costly.
269  if (auto *Op1C = dyn_cast<Constant>(I->getOperand(1))) {
270  if (!Op1C->containsUndefOrPoisonElement() &&
271  Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
272  Value *BO =
273  Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(Op1C),
274  I->getName() + ".neg");
275  if (auto *NewInstr = dyn_cast<Instruction>(BO))
276  NewInstr->setIsExact(I->isExact());
277  return BO;
278  }
279  }
280  break;
281  }
282 
283  // Rest of the logic is recursive, so if it's time to give up then it's time.
284  if (Depth > NegatorMaxDepth) {
285  LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
286  << *V << ". Giving up.\n");
287  ++NegatorTimesDepthLimitReached;
288  return nullptr;
289  }
290 
291  switch (I->getOpcode()) {
292  case Instruction::Freeze: {
293  // `freeze` is negatible if its operand is negatible.
294  Value *NegOp = negate(I->getOperand(0), Depth + 1);
295  if (!NegOp) // Early return.
296  return nullptr;
297  return Builder.CreateFreeze(NegOp, I->getName() + ".neg");
298  }
299  case Instruction::PHI: {
300  // `phi` is negatible if all the incoming values are negatible.
301  auto *PHI = cast<PHINode>(I);
302  SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
303  for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
304  if (!(std::get<1>(I) =
305  negate(std::get<0>(I), Depth + 1))) // Early return.
306  return nullptr;
307  }
308  // All incoming values are indeed negatible. Create negated PHI node.
309  PHINode *NegatedPHI = Builder.CreatePHI(
310  PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");
311  for (auto I : zip(NegatedIncomingValues, PHI->blocks()))
312  NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));
313  return NegatedPHI;
314  }
315  case Instruction::Select: {
316  if (isKnownNegation(I->getOperand(1), I->getOperand(2))) {
317  // Of one hand of select is known to be negation of another hand,
318  // just swap the hands around.
319  auto *NewSelect = cast<SelectInst>(I->clone());
320  // Just swap the operands of the select.
321  NewSelect->swapValues();
322  // Don't swap prof metadata, we didn't change the branch behavior.
323  NewSelect->setName(I->getName() + ".neg");
324  Builder.Insert(NewSelect);
325  return NewSelect;
326  }
327  // `select` is negatible if both hands of `select` are negatible.
328  Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
329  if (!NegOp1) // Early return.
330  return nullptr;
331  Value *NegOp2 = negate(I->getOperand(2), Depth + 1);
332  if (!NegOp2)
333  return nullptr;
334  // Do preserve the metadata!
335  return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
336  I->getName() + ".neg", /*MDFrom=*/I);
337  }
338  case Instruction::ShuffleVector: {
339  // `shufflevector` is negatible if both operands are negatible.
340  auto *Shuf = cast<ShuffleVectorInst>(I);
341  Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
342  if (!NegOp0) // Early return.
343  return nullptr;
344  Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
345  if (!NegOp1)
346  return nullptr;
347  return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
348  I->getName() + ".neg");
349  }
350  case Instruction::ExtractElement: {
351  // `extractelement` is negatible if source operand is negatible.
352  auto *EEI = cast<ExtractElementInst>(I);
353  Value *NegVector = negate(EEI->getVectorOperand(), Depth + 1);
354  if (!NegVector) // Early return.
355  return nullptr;
356  return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
357  I->getName() + ".neg");
358  }
359  case Instruction::InsertElement: {
360  // `insertelement` is negatible if both the source vector and
361  // element-to-be-inserted are negatible.
362  auto *IEI = cast<InsertElementInst>(I);
363  Value *NegVector = negate(IEI->getOperand(0), Depth + 1);
364  if (!NegVector) // Early return.
365  return nullptr;
366  Value *NegNewElt = negate(IEI->getOperand(1), Depth + 1);
367  if (!NegNewElt) // Early return.
368  return nullptr;
369  return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
370  I->getName() + ".neg");
371  }
372  case Instruction::Trunc: {
373  // `trunc` is negatible if its operand is negatible.
374  Value *NegOp = negate(I->getOperand(0), Depth + 1);
375  if (!NegOp) // Early return.
376  return nullptr;
377  return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
378  }
379  case Instruction::Shl: {
380  // `shl` is negatible if the first operand is negatible.
381  if (Value *NegOp0 = negate(I->getOperand(0), Depth + 1))
382  return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg");
383  // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
384  auto *Op1C = dyn_cast<Constant>(I->getOperand(1));
385  if (!Op1C) // Early return.
386  return nullptr;
387  return Builder.CreateMul(
388  I->getOperand(0),
389  ConstantExpr::getShl(Constant::getAllOnesValue(Op1C->getType()), Op1C),
390  I->getName() + ".neg");
391  }
392  case Instruction::Or: {
393  if (!haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1), DL, &AC, I,
394  &DT))
395  return nullptr; // Don't know how to handle `or` in general.
396  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
397  // `or`/`add` are interchangeable when operands have no common bits set.
398  // `inc` is always negatible.
399  if (match(Ops[1], m_One()))
400  return Builder.CreateNot(Ops[0], I->getName() + ".neg");
401  // Else, just defer to Instruction::Add handling.
403  }
404  case Instruction::Add: {
405  // `add` is negatible if both of its operands are negatible.
406  SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
407  for (Value *Op : I->operands()) {
408  // Can we sink the negation into this operand?
409  if (Value *NegOp = negate(Op, Depth + 1)) {
410  NegatedOps.emplace_back(NegOp); // Successfully negated operand!
411  continue;
412  }
413  // Failed to sink negation into this operand. IFF we started from negation
414  // and we manage to sink negation into one operand, we can still do this.
415  if (!IsTrulyNegation)
416  return nullptr;
417  NonNegatedOps.emplace_back(Op); // Just record which operand that was.
418  }
419  assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
420  "Internal consistency check failed.");
421  // Did we manage to sink negation into both of the operands?
422  if (NegatedOps.size() == 2) // Then we get to keep the `add`!
423  return Builder.CreateAdd(NegatedOps[0], NegatedOps[1],
424  I->getName() + ".neg");
425  assert(IsTrulyNegation && "We should have early-exited then.");
426  // Completely failed to sink negation?
427  if (NonNegatedOps.size() == 2)
428  return nullptr;
429  // 0-(a+b) --> (-a)-b
430  return Builder.CreateSub(NegatedOps[0], NonNegatedOps[0],
431  I->getName() + ".neg");
432  }
433  case Instruction::Xor: {
434  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
435  // `xor` is negatible if one of its operands is invertible.
436  // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
437  if (auto *C = dyn_cast<Constant>(Ops[1])) {
438  Value *Xor = Builder.CreateXor(Ops[0], ConstantExpr::getNot(C));
439  return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
440  I->getName() + ".neg");
441  }
442  return nullptr;
443  }
444  case Instruction::Mul: {
445  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
446  // `mul` is negatible if one of its operands is negatible.
447  Value *NegatedOp, *OtherOp;
448  // First try the second operand, in case it's a constant it will be best to
449  // just invert it instead of sinking the `neg` deeper.
450  if (Value *NegOp1 = negate(Ops[1], Depth + 1)) {
451  NegatedOp = NegOp1;
452  OtherOp = Ops[0];
453  } else if (Value *NegOp0 = negate(Ops[0], Depth + 1)) {
454  NegatedOp = NegOp0;
455  OtherOp = Ops[1];
456  } else
457  // Can't negate either of them.
458  return nullptr;
459  return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg");
460  }
461  default:
462  return nullptr; // Don't know, likely not negatible for free.
463  }
464 
465  llvm_unreachable("Can't get here. We always return from switch.");
466 }
467 
468 LLVM_NODISCARD Value *Negator::negate(Value *V, unsigned Depth) {
469  NegatorMaxDepthVisited.updateMax(Depth);
470  ++NegatorNumValuesVisited;
471 
472 #if LLVM_ENABLE_STATS
473  ++NumValuesVisitedInThisNegator;
474 #endif
475 
476 #ifndef NDEBUG
477  // We can't ever have a Value with such an address.
478  Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
479 #endif
480 
481  // Did we already try to negate this value?
482  auto NegationsCacheIterator = NegationsCache.find(V);
483  if (NegationsCacheIterator != NegationsCache.end()) {
484  ++NegatorNumNegationsFoundInCache;
485  Value *NegatedV = NegationsCacheIterator->second;
486  assert(NegatedV != Placeholder && "Encountered a cycle during negation.");
487  return NegatedV;
488  }
489 
490 #ifndef NDEBUG
491  // We did not find a cached result for negation of V. While there,
492  // let's temporairly cache a placeholder value, with the idea that if later
493  // during negation we fetch it from cache, we'll know we're in a cycle.
494  NegationsCache[V] = Placeholder;
495 #endif
496 
497  // No luck. Try negating it for real.
498  Value *NegatedV = visitImpl(V, Depth);
499  // And cache the (real) result for the future.
500  NegationsCache[V] = NegatedV;
501 
502  return NegatedV;
503 }
504 
506  Value *Negated = negate(Root, /*Depth=*/0);
507  if (!Negated) {
508  // We must cleanup newly-inserted instructions, to avoid any potential
509  // endless combine looping.
510  for (Instruction *I : llvm::reverse(NewInstructions))
511  I->eraseFromParent();
512  return llvm::None;
513  }
514  return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
515 }
516 
517 LLVM_NODISCARD Value *Negator::Negate(bool LHSIsZero, Value *Root,
518  InstCombinerImpl &IC) {
519  ++NegatorTotalNegationsAttempted;
520  LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
521  << "\n");
522 
523  if (!NegatorEnabled || !DebugCounter::shouldExecute(NegatorCounter))
524  return nullptr;
525 
527  IC.getDominatorTree(), LHSIsZero);
528  Optional<Result> Res = N.run(Root);
529  if (!Res) { // Negation failed.
530  LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
531  << "\n");
532  return nullptr;
533  }
534 
535  LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
536  << "\n NEW: " << *Res->second << "\n");
537  ++NegatorNumTreesNegated;
538 
539  // We must temporarily unset the 'current' insertion point and DebugLoc of the
540  // InstCombine's IRBuilder so that it won't interfere with the ones we have
541  // already specified when producing negated instructions.
545 
546  // And finally, we must add newly-created instructions into the InstCombine's
547  // worklist (in a proper order!) so it can attempt to combine them.
548  LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
549  << " instrs to InstCombine\n");
550  NegatorMaxInstructionsCreated.updateMax(Res->first.size());
551  NegatorNumInstructionsNegatedSuccess += Res->first.size();
552 
553  // They are in def-use order, so nothing fancy, just insert them in order.
554  for (Instruction *I : Res->first)
555  IC.Builder.Insert(I, I->getName());
556 
557  // And return the new root.
558  return Res->second;
559 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:267
llvm::PatternMatch::m_TruncOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1627
llvm::ConstantExpr::getNot
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2709
Optional.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
InstCombiner.h
llvm::InstCombiner::getDominatorTree
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:370
DEBUG_COUNTER
DEBUG_COUNTER(NegatorCounter, "instcombine-negator", "Controls Negator transformations in InstCombine pass")
StringRef.h
TargetFolder.h
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1127
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:58
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:168
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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:380
llvm::Optional
Definition: APInt.h:33
STLExtras.h
llvm::PatternMatch::m_c_And
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
Definition: PatternMatch.h:2262
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
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:203
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:395
llvm::Instruction
Definition: Instruction.h:42
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:919
DebugLoc.h
llvm::InstCombiner::getComplexity
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:127
PatternMatch.h
llvm::None
const NoneType None
Definition: None.h:24
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::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::cl::opt< bool >
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
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:759
llvm::InstCombiner::getAssumptionCache
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:368
llvm::InstCombiner::getDataLayout
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:371
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2814
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:58
llvm::ConstantExpr::getShl
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2791
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:853
llvm::Negator::Negate
static LLVM_NODISCARD Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:517
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:5881
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:766
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:75
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
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:765
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
None.h
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
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:42
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
Compiler.h
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:350
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:280
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
Constant.h
llvm::TargetFolder
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:33
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2696
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::IRBuilderBase::Insert
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Definition: IRBuilder.h:144
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:197
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:155
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
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:688
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:2664
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:696
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:405
raw_ostream.h
Value.h
llvm::MIPatternMatch::m_OneUse
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Definition: MIPatternMatch.h:45
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927