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