LLVM  17.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/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/ADT/Twine.h"
26 #include "llvm/IR/Constant.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DebugLoc.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Use.h"
35 #include "llvm/IR/User.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/Compiler.h"
44 #include <cassert>
45 #include <cstdint>
46 #include <functional>
47 #include <tuple>
48 #include <type_traits>
49 #include <utility>
50 
51 namespace llvm {
52 class AssumptionCache;
53 class DataLayout;
54 class DominatorTree;
55 class LLVMContext;
56 } // namespace llvm
57 
58 using namespace llvm;
59 
60 #define DEBUG_TYPE "instcombine"
61 
62 STATISTIC(NegatorTotalNegationsAttempted,
63  "Negator: Number of negations attempted to be sinked");
64 STATISTIC(NegatorNumTreesNegated,
65  "Negator: Number of negations successfully sinked");
66 STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
67  "reached while attempting to sink negation");
68 STATISTIC(NegatorTimesDepthLimitReached,
69  "Negator: How many times did the traversal depth limit was reached "
70  "during sinking");
71 STATISTIC(
72  NegatorNumValuesVisited,
73  "Negator: Total number of values visited during attempts to sink negation");
74 STATISTIC(NegatorNumNegationsFoundInCache,
75  "Negator: How many negations did we retrieve/reuse from cache");
76 STATISTIC(NegatorMaxTotalValuesVisited,
77  "Negator: Maximal number of values ever visited while attempting to "
78  "sink negation");
79 STATISTIC(NegatorNumInstructionsCreatedTotal,
80  "Negator: Number of new negated instructions created, total");
81 STATISTIC(NegatorMaxInstructionsCreated,
82  "Negator: Maximal number of new instructions created during negation "
83  "attempt");
84 STATISTIC(NegatorNumInstructionsNegatedSuccess,
85  "Negator: Number of new negated instructions created in successful "
86  "negation sinking attempts");
87 
88 DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
89  "Controls Negator transformations in InstCombine pass");
90 
91 static cl::opt<bool>
92  NegatorEnabled("instcombine-negator-enabled", cl::init(true),
93  cl::desc("Should we attempt to sink negations?"));
94 
95 static cl::opt<unsigned>
96  NegatorMaxDepth("instcombine-negator-max-depth",
98  cl::desc("What is the maximal lookup depth when trying to "
99  "check for viability of negation sinking."));
100 
101 Negator::Negator(LLVMContext &C, const DataLayout &DL_, AssumptionCache &AC_,
102  const DominatorTree &DT_, bool IsTrulyNegation_)
103  : Builder(C, TargetFolder(DL_),
105  ++NegatorNumInstructionsCreatedTotal;
106  NewInstructions.push_back(I);
107  })),
108  DL(DL_), AC(AC_), DT(DT_), IsTrulyNegation(IsTrulyNegation_) {}
109 
110 #if LLVM_ENABLE_STATS
111 Negator::~Negator() {
112  NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
113 }
114 #endif
115 
116 // Due to the InstCombine's worklist management, there are no guarantees that
117 // each instruction we'll encounter has been visited by InstCombine already.
118 // In particular, most importantly for us, that means we have to canonicalize
119 // constants to RHS ourselves, since that is helpful sometimes.
120 std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(Instruction *I) {
121  assert(I->getNumOperands() == 2 && "Only for binops!");
122  std::array<Value *, 2> Ops{I->getOperand(0), I->getOperand(1)};
123  if (I->isCommutative() && InstCombiner::getComplexity(I->getOperand(0)) <
124  InstCombiner::getComplexity(I->getOperand(1)))
125  std::swap(Ops[0], Ops[1]);
126  return Ops;
127 }
128 
129 // FIXME: can this be reworked into a worklist-based algorithm while preserving
130 // the depth-first, early bailout traversal?
131 [[nodiscard]] Value *Negator::visitImpl(Value *V, unsigned Depth) {
132  // -(undef) -> undef.
133  if (match(V, m_Undef()))
134  return V;
135 
136  // In i1, negation can simply be ignored.
137  if (V->getType()->isIntOrIntVectorTy(1))
138  return V;
139 
140  Value *X;
141 
142  // -(-(X)) -> X.
143  if (match(V, m_Neg(m_Value(X))))
144  return X;
145 
146  // Integral constants can be freely negated.
147  if (match(V, m_AnyIntegralConstant()))
148  return ConstantExpr::getNeg(cast<Constant>(V), /*HasNUW=*/false,
149  /*HasNSW=*/false);
150 
151  // If we have a non-instruction, then give up.
152  if (!isa<Instruction>(V))
153  return nullptr;
154 
155  // If we have started with a true negation (i.e. `sub 0, %y`), then if we've
156  // got instruction that does not require recursive reasoning, we can still
157  // negate it even if it has other uses, without increasing instruction count.
158  if (!V->hasOneUse() && !IsTrulyNegation)
159  return nullptr;
160 
161  auto *I = cast<Instruction>(V);
162  unsigned BitWidth = I->getType()->getScalarSizeInBits();
163 
164  // We must preserve the insertion point and debug info that is set in the
165  // builder at the time this function is called.
166  InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
167  // And since we are trying to negate instruction I, that tells us about the
168  // insertion point and the debug info that we need to keep.
169  Builder.SetInsertPoint(I);
170 
171  // In some cases we can give the answer without further recursion.
172  switch (I->getOpcode()) {
173  case Instruction::Add: {
174  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
175  // `inc` is always negatible.
176  if (match(Ops[1], m_One()))
177  return Builder.CreateNot(Ops[0], I->getName() + ".neg");
178  break;
179  }
180  case Instruction::Xor:
181  // `not` is always negatible.
182  if (match(I, m_Not(m_Value(X))))
183  return Builder.CreateAdd(X, ConstantInt::get(X->getType(), 1),
184  I->getName() + ".neg");
185  break;
186  case Instruction::AShr:
187  case Instruction::LShr: {
188  // Right-shift sign bit smear is negatible.
189  const APInt *Op1Val;
190  if (match(I->getOperand(1), m_APInt(Op1Val)) && *Op1Val == BitWidth - 1) {
191  Value *BO = I->getOpcode() == Instruction::AShr
192  ? Builder.CreateLShr(I->getOperand(0), I->getOperand(1))
193  : Builder.CreateAShr(I->getOperand(0), I->getOperand(1));
194  if (auto *NewInstr = dyn_cast<Instruction>(BO)) {
195  NewInstr->copyIRFlags(I);
196  NewInstr->setName(I->getName() + ".neg");
197  }
198  return BO;
199  }
200  // While we could negate exact arithmetic shift:
201  // ashr exact %x, C --> sdiv exact i8 %x, -1<<C
202  // iff C != 0 and C u< bitwidth(%x), we don't want to,
203  // because division is *THAT* much worse than a shift.
204  break;
205  }
206  case Instruction::SExt:
207  case Instruction::ZExt:
208  // `*ext` of i1 is always negatible
209  if (I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
210  return I->getOpcode() == Instruction::SExt
211  ? Builder.CreateZExt(I->getOperand(0), I->getType(),
212  I->getName() + ".neg")
213  : Builder.CreateSExt(I->getOperand(0), I->getType(),
214  I->getName() + ".neg");
215  break;
216  case Instruction::Select: {
217  // If both arms of the select are constants, we don't need to recurse.
218  // Therefore, this transform is not limited by uses.
219  auto *Sel = cast<SelectInst>(I);
220  Constant *TrueC, *FalseC;
221  if (match(Sel->getTrueValue(), m_ImmConstant(TrueC)) &&
222  match(Sel->getFalseValue(), m_ImmConstant(FalseC))) {
223  Constant *NegTrueC = ConstantExpr::getNeg(TrueC);
224  Constant *NegFalseC = ConstantExpr::getNeg(FalseC);
225  return Builder.CreateSelect(Sel->getCondition(), NegTrueC, NegFalseC,
226  I->getName() + ".neg", /*MDFrom=*/I);
227  }
228  break;
229  }
230  default:
231  break; // Other instructions require recursive reasoning.
232  }
233 
234  if (I->getOpcode() == Instruction::Sub &&
235  (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
236  // `sub` is always negatible.
237  // However, only do this either if the old `sub` doesn't stick around, or
238  // it was subtracting from a constant. Otherwise, this isn't profitable.
239  return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
240  I->getName() + ".neg");
241  }
242 
243  // Some other cases, while still don't require recursion,
244  // are restricted to the one-use case.
245  if (!V->hasOneUse())
246  return nullptr;
247 
248  switch (I->getOpcode()) {
249  case Instruction::ZExt: {
250  // Negation of zext of signbit is signbit splat:
251  // 0 - (zext (i8 X u>> 7) to iN) --> sext (i8 X s>> 7) to iN
252  Value *SrcOp = I->getOperand(0);
253  unsigned SrcWidth = SrcOp->getType()->getScalarSizeInBits();
254  const APInt &FullShift = APInt(SrcWidth, SrcWidth - 1);
255  if (IsTrulyNegation &&
257  Value *Ashr = Builder.CreateAShr(X, FullShift);
258  return Builder.CreateSExt(Ashr, I->getType());
259  }
260  break;
261  }
262  case Instruction::And: {
263  Constant *ShAmt;
264  // sub(y,and(lshr(x,C),1)) --> add(ashr(shl(x,(BW-1)-C),BW-1),y)
266  m_LShr(m_Value(X), m_ImmConstant(ShAmt)))),
267  m_One()))) {
268  unsigned BW = X->getType()->getScalarSizeInBits();
269  Constant *BWMinusOne = ConstantInt::get(X->getType(), BW - 1);
270  Value *R = Builder.CreateShl(X, Builder.CreateSub(BWMinusOne, ShAmt));
271  R = Builder.CreateAShr(R, BWMinusOne);
272  return Builder.CreateTruncOrBitCast(R, I->getType());
273  }
274  break;
275  }
276  case Instruction::SDiv:
277  // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
278  // While this is normally not behind a use-check,
279  // let's consider division to be special since it's costly.
280  if (auto *Op1C = dyn_cast<Constant>(I->getOperand(1))) {
281  if (!Op1C->containsUndefOrPoisonElement() &&
282  Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
283  Value *BO =
284  Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(Op1C),
285  I->getName() + ".neg");
286  if (auto *NewInstr = dyn_cast<Instruction>(BO))
287  NewInstr->setIsExact(I->isExact());
288  return BO;
289  }
290  }
291  break;
292  }
293 
294  // Rest of the logic is recursive, so if it's time to give up then it's time.
295  if (Depth > NegatorMaxDepth) {
296  LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
297  << *V << ". Giving up.\n");
298  ++NegatorTimesDepthLimitReached;
299  return nullptr;
300  }
301 
302  switch (I->getOpcode()) {
303  case Instruction::Freeze: {
304  // `freeze` is negatible if its operand is negatible.
305  Value *NegOp = negate(I->getOperand(0), Depth + 1);
306  if (!NegOp) // Early return.
307  return nullptr;
308  return Builder.CreateFreeze(NegOp, I->getName() + ".neg");
309  }
310  case Instruction::PHI: {
311  // `phi` is negatible if all the incoming values are negatible.
312  auto *PHI = cast<PHINode>(I);
313  SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
314  for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
315  if (!(std::get<1>(I) =
316  negate(std::get<0>(I), Depth + 1))) // Early return.
317  return nullptr;
318  }
319  // All incoming values are indeed negatible. Create negated PHI node.
320  PHINode *NegatedPHI = Builder.CreatePHI(
321  PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");
322  for (auto I : zip(NegatedIncomingValues, PHI->blocks()))
323  NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));
324  return NegatedPHI;
325  }
326  case Instruction::Select: {
327  if (isKnownNegation(I->getOperand(1), I->getOperand(2))) {
328  // Of one hand of select is known to be negation of another hand,
329  // just swap the hands around.
330  auto *NewSelect = cast<SelectInst>(I->clone());
331  // Just swap the operands of the select.
332  NewSelect->swapValues();
333  // Don't swap prof metadata, we didn't change the branch behavior.
334  NewSelect->setName(I->getName() + ".neg");
335  Builder.Insert(NewSelect);
336  return NewSelect;
337  }
338  // `select` is negatible if both hands of `select` are negatible.
339  Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
340  if (!NegOp1) // Early return.
341  return nullptr;
342  Value *NegOp2 = negate(I->getOperand(2), Depth + 1);
343  if (!NegOp2)
344  return nullptr;
345  // Do preserve the metadata!
346  return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
347  I->getName() + ".neg", /*MDFrom=*/I);
348  }
349  case Instruction::ShuffleVector: {
350  // `shufflevector` is negatible if both operands are negatible.
351  auto *Shuf = cast<ShuffleVectorInst>(I);
352  Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
353  if (!NegOp0) // Early return.
354  return nullptr;
355  Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
356  if (!NegOp1)
357  return nullptr;
358  return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
359  I->getName() + ".neg");
360  }
361  case Instruction::ExtractElement: {
362  // `extractelement` is negatible if source operand is negatible.
363  auto *EEI = cast<ExtractElementInst>(I);
364  Value *NegVector = negate(EEI->getVectorOperand(), Depth + 1);
365  if (!NegVector) // Early return.
366  return nullptr;
367  return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
368  I->getName() + ".neg");
369  }
370  case Instruction::InsertElement: {
371  // `insertelement` is negatible if both the source vector and
372  // element-to-be-inserted are negatible.
373  auto *IEI = cast<InsertElementInst>(I);
374  Value *NegVector = negate(IEI->getOperand(0), Depth + 1);
375  if (!NegVector) // Early return.
376  return nullptr;
377  Value *NegNewElt = negate(IEI->getOperand(1), Depth + 1);
378  if (!NegNewElt) // Early return.
379  return nullptr;
380  return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
381  I->getName() + ".neg");
382  }
383  case Instruction::Trunc: {
384  // `trunc` is negatible if its operand is negatible.
385  Value *NegOp = negate(I->getOperand(0), Depth + 1);
386  if (!NegOp) // Early return.
387  return nullptr;
388  return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
389  }
390  case Instruction::Shl: {
391  // `shl` is negatible if the first operand is negatible.
392  if (Value *NegOp0 = negate(I->getOperand(0), Depth + 1))
393  return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg");
394  // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
395  auto *Op1C = dyn_cast<Constant>(I->getOperand(1));
396  if (!Op1C || !IsTrulyNegation)
397  return nullptr;
398  return Builder.CreateMul(
399  I->getOperand(0),
400  ConstantExpr::getShl(Constant::getAllOnesValue(Op1C->getType()), Op1C),
401  I->getName() + ".neg");
402  }
403  case Instruction::Or: {
404  if (!haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1), DL, &AC, I,
405  &DT))
406  return nullptr; // Don't know how to handle `or` in general.
407  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
408  // `or`/`add` are interchangeable when operands have no common bits set.
409  // `inc` is always negatible.
410  if (match(Ops[1], m_One()))
411  return Builder.CreateNot(Ops[0], I->getName() + ".neg");
412  // Else, just defer to Instruction::Add handling.
413  [[fallthrough]];
414  }
415  case Instruction::Add: {
416  // `add` is negatible if both of its operands are negatible.
417  SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
418  for (Value *Op : I->operands()) {
419  // Can we sink the negation into this operand?
420  if (Value *NegOp = negate(Op, Depth + 1)) {
421  NegatedOps.emplace_back(NegOp); // Successfully negated operand!
422  continue;
423  }
424  // Failed to sink negation into this operand. IFF we started from negation
425  // and we manage to sink negation into one operand, we can still do this.
426  if (!IsTrulyNegation)
427  return nullptr;
428  NonNegatedOps.emplace_back(Op); // Just record which operand that was.
429  }
430  assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
431  "Internal consistency check failed.");
432  // Did we manage to sink negation into both of the operands?
433  if (NegatedOps.size() == 2) // Then we get to keep the `add`!
434  return Builder.CreateAdd(NegatedOps[0], NegatedOps[1],
435  I->getName() + ".neg");
436  assert(IsTrulyNegation && "We should have early-exited then.");
437  // Completely failed to sink negation?
438  if (NonNegatedOps.size() == 2)
439  return nullptr;
440  // 0-(a+b) --> (-a)-b
441  return Builder.CreateSub(NegatedOps[0], NonNegatedOps[0],
442  I->getName() + ".neg");
443  }
444  case Instruction::Xor: {
445  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
446  // `xor` is negatible if one of its operands is invertible.
447  // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
448  if (auto *C = dyn_cast<Constant>(Ops[1])) {
449  Value *Xor = Builder.CreateXor(Ops[0], ConstantExpr::getNot(C));
450  return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
451  I->getName() + ".neg");
452  }
453  return nullptr;
454  }
455  case Instruction::Mul: {
456  std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
457  // `mul` is negatible if one of its operands is negatible.
458  Value *NegatedOp, *OtherOp;
459  // First try the second operand, in case it's a constant it will be best to
460  // just invert it instead of sinking the `neg` deeper.
461  if (Value *NegOp1 = negate(Ops[1], Depth + 1)) {
462  NegatedOp = NegOp1;
463  OtherOp = Ops[0];
464  } else if (Value *NegOp0 = negate(Ops[0], Depth + 1)) {
465  NegatedOp = NegOp0;
466  OtherOp = Ops[1];
467  } else
468  // Can't negate either of them.
469  return nullptr;
470  return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg");
471  }
472  default:
473  return nullptr; // Don't know, likely not negatible for free.
474  }
475 
476  llvm_unreachable("Can't get here. We always return from switch.");
477 }
478 
479 [[nodiscard]] Value *Negator::negate(Value *V, unsigned Depth) {
480  NegatorMaxDepthVisited.updateMax(Depth);
481  ++NegatorNumValuesVisited;
482 
483 #if LLVM_ENABLE_STATS
484  ++NumValuesVisitedInThisNegator;
485 #endif
486 
487 #ifndef NDEBUG
488  // We can't ever have a Value with such an address.
489  Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
490 #endif
491 
492  // Did we already try to negate this value?
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.");
498  return NegatedV;
499  }
500 
501 #ifndef NDEBUG
502  // We did not find a cached result for negation of V. While there,
503  // let's temporairly cache a placeholder value, with the idea that if later
504  // during negation we fetch it from cache, we'll know we're in a cycle.
505  NegationsCache[V] = Placeholder;
506 #endif
507 
508  // No luck. Try negating it for real.
509  Value *NegatedV = visitImpl(V, Depth);
510  // And cache the (real) result for the future.
511  NegationsCache[V] = NegatedV;
512 
513  return NegatedV;
514 }
515 
516 [[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root) {
517  Value *Negated = negate(Root, /*Depth=*/0);
518  if (!Negated) {
519  // We must cleanup newly-inserted instructions, to avoid any potential
520  // endless combine looping.
521  for (Instruction *I : llvm::reverse(NewInstructions))
522  I->eraseFromParent();
523  return std::nullopt;
524  }
525  return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
526 }
527 
528 [[nodiscard]] Value *Negator::Negate(bool LHSIsZero, Value *Root,
529  InstCombinerImpl &IC) {
530  ++NegatorTotalNegationsAttempted;
531  LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
532  << "\n");
533 
534  if (!NegatorEnabled || !DebugCounter::shouldExecute(NegatorCounter))
535  return nullptr;
536 
538  IC.getDominatorTree(), LHSIsZero);
539  std::optional<Result> Res = N.run(Root);
540  if (!Res) { // Negation failed.
541  LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
542  << "\n");
543  return nullptr;
544  }
545 
546  LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
547  << "\n NEW: " << *Res->second << "\n");
548  ++NegatorNumTreesNegated;
549 
550  // We must temporarily unset the 'current' insertion point and DebugLoc of the
551  // InstCombine's IRBuilder so that it won't interfere with the ones we have
552  // already specified when producing negated instructions.
556 
557  // And finally, we must add newly-created instructions into the InstCombine's
558  // worklist (in a proper order!) so it can attempt to combine them.
559  LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
560  << " instrs to InstCombine\n");
561  NegatorMaxInstructionsCreated.updateMax(Res->first.size());
562  NegatorNumInstructionsNegatedSuccess += Res->first.size();
563 
564  // They are in def-use order, so nothing fancy, just insert them in order.
565  for (Instruction *I : Res->first)
566  IC.Builder.Insert(I, I->getName());
567 
568  // And return the new root.
569  return Res->second;
570 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:231
llvm::PatternMatch::m_TruncOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1617
llvm::ConstantExpr::getNot
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2651
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
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:371
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
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:1117
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:169
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
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:275
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:278
CommandLine.h
InstCombineInternal.h
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::PatternMatch::m_SpecificIntAllowUndef
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:862
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:212
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:403
llvm::Instruction
Definition: Instruction.h:41
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
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:887
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
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:517
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::cl::opt< bool >
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::InstCombiner::getAssumptionCache
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:369
llvm::InstCombiner::getDataLayout
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:372
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2854
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
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:2695
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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::isKnownNegation
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
Definition: ValueTracking.cpp:6219
iterator_range.h
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:76
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:660
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
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:994
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:361
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:165
Constant.h
llvm::TargetFolder
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:34
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2644
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:354
llvm::Negator::Negate
static Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:528
llvm::IRBuilderBase::Insert
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Definition: IRBuilder.h:145
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:228
Casting.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
DebugCounter.h
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:186
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:444
SmallVector.h
User.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:882
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:766
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:2708
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
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:774
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:411
raw_ostream.h
Value.h
llvm::MIPatternMatch::m_OneUse
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Definition: MIPatternMatch.h:47
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::SrcOp
Definition: MachineIRBuilder.h:128
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941