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 <utility>
47
48using namespace llvm;
49using namespace llvm::PatternMatch;
50
51#define DEBUG_TYPE "instcombine"
52
53STATISTIC(NegatorTotalNegationsAttempted,
54 "Negator: Number of negations attempted to be sinked");
55STATISTIC(NegatorNumTreesNegated,
56 "Negator: Number of negations successfully sinked");
57STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
58 "reached while attempting to sink negation");
59STATISTIC(NegatorTimesDepthLimitReached,
60 "Negator: How many times did the traversal depth limit was reached "
61 "during sinking");
63 NegatorNumValuesVisited,
64 "Negator: Total number of values visited during attempts to sink negation");
65STATISTIC(NegatorNumNegationsFoundInCache,
66 "Negator: How many negations did we retrieve/reuse from cache");
67STATISTIC(NegatorMaxTotalValuesVisited,
68 "Negator: Maximal number of values ever visited while attempting to "
69 "sink negation");
70STATISTIC(NegatorNumInstructionsCreatedTotal,
71 "Negator: Number of new negated instructions created, total");
72STATISTIC(NegatorMaxInstructionsCreated,
73 "Negator: Maximal number of new instructions created during negation "
74 "attempt");
75STATISTIC(NegatorNumInstructionsNegatedSuccess,
76 "Negator: Number of new negated instructions created in successful "
77 "negation sinking attempts");
78
79DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
80 "Controls Negator transformations in InstCombine pass");
81
82static cl::opt<bool>
83 NegatorEnabled("instcombine-negator-enabled", cl::init(true),
84 cl::desc("Should we attempt to sink negations?"));
85
87 NegatorMaxDepth("instcombine-negator-max-depth",
89 cl::desc("What is the maximal lookup depth when trying to "
90 "check for viability of negation sinking."));
91
92Negator::Negator(LLVMContext &C, const DataLayout &DL, const DominatorTree &DT_,
93 bool IsTrulyNegation_)
94 : Builder(C, TargetFolder(DL),
96 ++NegatorNumInstructionsCreatedTotal;
97 NewInstructions.push_back(I);
98 })),
99 DT(DT_), 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 // Don't negate indvars to avoid infinite loops.
313 if (DT.dominates(PHI->getParent(), std::get<0>(I)))
314 return nullptr;
315 if (!(std::get<1>(I) =
316 negate(std::get<0>(I), IsNSW, 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), /*NeedNSW=*/false,
328 /*AllowPoison=*/false)) {
329 // Of one hand of select is known to be negation of another hand,
330 // just swap the hands around.
331 auto *NewSelect = cast<SelectInst>(I->clone());
332 // Just swap the operands of the select.
333 NewSelect->swapValues();
334 // Don't swap prof metadata, we didn't change the branch behavior.
335 NewSelect->setName(I->getName() + ".neg");
336 // Poison-generating flags should be dropped
337 Value *TV = NewSelect->getTrueValue();
338 Value *FV = NewSelect->getFalseValue();
339 if (match(TV, m_Neg(m_Specific(FV))))
340 cast<Instruction>(TV)->dropPoisonGeneratingFlags();
341 else if (match(FV, m_Neg(m_Specific(TV))))
342 cast<Instruction>(FV)->dropPoisonGeneratingFlags();
343 else {
344 cast<Instruction>(TV)->dropPoisonGeneratingFlags();
345 cast<Instruction>(FV)->dropPoisonGeneratingFlags();
346 }
347 Builder.Insert(NewSelect);
348 return NewSelect;
349 }
350 // `select` is negatible if both hands of `select` are negatible.
351 Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);
352 if (!NegOp1) // Early return.
353 return nullptr;
354 Value *NegOp2 = negate(I->getOperand(2), IsNSW, Depth + 1);
355 if (!NegOp2)
356 return nullptr;
357 // Do preserve the metadata!
358 return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
359 I->getName() + ".neg", /*MDFrom=*/I);
360 }
361 case Instruction::ShuffleVector: {
362 // `shufflevector` is negatible if both operands are negatible.
363 auto *Shuf = cast<ShuffleVectorInst>(I);
364 Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1);
365 if (!NegOp0) // Early return.
366 return nullptr;
367 Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);
368 if (!NegOp1)
369 return nullptr;
370 return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
371 I->getName() + ".neg");
372 }
373 case Instruction::ExtractElement: {
374 // `extractelement` is negatible if source operand is negatible.
375 auto *EEI = cast<ExtractElementInst>(I);
376 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW, Depth + 1);
377 if (!NegVector) // Early return.
378 return nullptr;
379 return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
380 I->getName() + ".neg");
381 }
382 case Instruction::InsertElement: {
383 // `insertelement` is negatible if both the source vector and
384 // element-to-be-inserted are negatible.
385 auto *IEI = cast<InsertElementInst>(I);
386 Value *NegVector = negate(IEI->getOperand(0), IsNSW, Depth + 1);
387 if (!NegVector) // Early return.
388 return nullptr;
389 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW, Depth + 1);
390 if (!NegNewElt) // Early return.
391 return nullptr;
392 return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
393 I->getName() + ".neg");
394 }
395 case Instruction::Trunc: {
396 // `trunc` is negatible if its operand is negatible.
397 Value *NegOp = negate(I->getOperand(0), /* IsNSW */ false, Depth + 1);
398 if (!NegOp) // Early return.
399 return nullptr;
400 return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
401 }
402 case Instruction::Shl: {
403 // `shl` is negatible if the first operand is negatible.
404 IsNSW &= I->hasNoSignedWrap();
405 if (Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1))
406 return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg",
407 /* HasNUW */ false, IsNSW);
408 // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
409 Constant *Op1C;
410 if (!match(I->getOperand(1), m_ImmConstant(Op1C)) || !IsTrulyNegation)
411 return nullptr;
412 return Builder.CreateMul(
413 I->getOperand(0),
414 Builder.CreateShl(Constant::getAllOnesValue(Op1C->getType()), Op1C),
415 I->getName() + ".neg", /* HasNUW */ false, IsNSW);
416 }
417 case Instruction::Or: {
418 if (!cast<PossiblyDisjointInst>(I)->isDisjoint())
419 return nullptr; // Don't know how to handle `or` in general.
420 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
421 // `or`/`add` are interchangeable when operands have no common bits set.
422 // `inc` is always negatible.
423 if (match(Ops[1], m_One()))
424 return Builder.CreateNot(Ops[0], I->getName() + ".neg");
425 // Else, just defer to Instruction::Add handling.
426 [[fallthrough]];
427 }
428 case Instruction::Add: {
429 // `add` is negatible if both of its operands are negatible.
430 SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
431 for (Value *Op : I->operands()) {
432 // Can we sink the negation into this operand?
433 if (Value *NegOp = negate(Op, /* IsNSW */ false, Depth + 1)) {
434 NegatedOps.emplace_back(NegOp); // Successfully negated operand!
435 continue;
436 }
437 // Failed to sink negation into this operand. IFF we started from negation
438 // and we manage to sink negation into one operand, we can still do this.
439 if (!IsTrulyNegation)
440 return nullptr;
441 NonNegatedOps.emplace_back(Op); // Just record which operand that was.
442 }
443 assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
444 "Internal consistency check failed.");
445 // Did we manage to sink negation into both of the operands?
446 if (NegatedOps.size() == 2) // Then we get to keep the `add`!
447 return Builder.CreateAdd(NegatedOps[0], NegatedOps[1],
448 I->getName() + ".neg");
449 assert(IsTrulyNegation && "We should have early-exited then.");
450 // Completely failed to sink negation?
451 if (NonNegatedOps.size() == 2)
452 return nullptr;
453 // 0-(a+b) --> (-a)-b
454 return Builder.CreateSub(NegatedOps[0], NonNegatedOps[0],
455 I->getName() + ".neg");
456 }
457 case Instruction::Xor: {
458 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
459 // `xor` is negatible if one of its operands is invertible.
460 // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
461 if (auto *C = dyn_cast<Constant>(Ops[1])) {
462 if (IsTrulyNegation) {
463 Value *Xor = Builder.CreateXor(Ops[0], ConstantExpr::getNot(C));
464 return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
465 I->getName() + ".neg");
466 }
467 }
468 return nullptr;
469 }
470 case Instruction::Mul: {
471 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
472 // `mul` is negatible if one of its operands is negatible.
473 Value *NegatedOp, *OtherOp;
474 // First try the second operand, in case it's a constant it will be best to
475 // just invert it instead of sinking the `neg` deeper.
476 if (Value *NegOp1 = negate(Ops[1], /* IsNSW */ false, Depth + 1)) {
477 NegatedOp = NegOp1;
478 OtherOp = Ops[0];
479 } else if (Value *NegOp0 = negate(Ops[0], /* IsNSW */ false, Depth + 1)) {
480 NegatedOp = NegOp0;
481 OtherOp = Ops[1];
482 } else
483 // Can't negate either of them.
484 return nullptr;
485 return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg",
486 /* HasNUW */ false, IsNSW && I->hasNoSignedWrap());
487 }
488 default:
489 return nullptr; // Don't know, likely not negatible for free.
490 }
491
492 llvm_unreachable("Can't get here. We always return from switch.");
493}
494
495[[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) {
496 NegatorMaxDepthVisited.updateMax(Depth);
497 ++NegatorNumValuesVisited;
498
499#if LLVM_ENABLE_STATS
500 ++NumValuesVisitedInThisNegator;
501#endif
502
503#ifndef NDEBUG
504 // We can't ever have a Value with such an address.
505 Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
506#endif
507
508 // Did we already try to negate this value?
509 auto NegationsCacheIterator = NegationsCache.find(V);
510 if (NegationsCacheIterator != NegationsCache.end()) {
511 ++NegatorNumNegationsFoundInCache;
512 Value *NegatedV = NegationsCacheIterator->second;
513 assert(NegatedV != Placeholder && "Encountered a cycle during negation.");
514 return NegatedV;
515 }
516
517#ifndef NDEBUG
518 // We did not find a cached result for negation of V. While there,
519 // let's temporairly cache a placeholder value, with the idea that if later
520 // during negation we fetch it from cache, we'll know we're in a cycle.
521 NegationsCache[V] = Placeholder;
522#endif
523
524 // No luck. Try negating it for real.
525 Value *NegatedV = visitImpl(V, IsNSW, Depth);
526 // And cache the (real) result for the future.
527 NegationsCache[V] = NegatedV;
528
529 return NegatedV;
530}
531
532[[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root,
533 bool IsNSW) {
534 Value *Negated = negate(Root, IsNSW, /*Depth=*/0);
535 if (!Negated) {
536 // We must cleanup newly-inserted instructions, to avoid any potential
537 // endless combine looping.
538 for (Instruction *I : llvm::reverse(NewInstructions))
539 I->eraseFromParent();
540 return std::nullopt;
541 }
542 return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
543}
544
545[[nodiscard]] Value *Negator::Negate(bool LHSIsZero, bool IsNSW, Value *Root,
546 InstCombinerImpl &IC) {
547 ++NegatorTotalNegationsAttempted;
548 LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
549 << "\n");
550
551 if (!NegatorEnabled || !DebugCounter::shouldExecute(NegatorCounter))
552 return nullptr;
553
555 LHSIsZero);
556 std::optional<Result> Res = N.run(Root, IsNSW);
557 if (!Res) { // Negation failed.
558 LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
559 << "\n");
560 return nullptr;
561 }
562
563 LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
564 << "\n NEW: " << *Res->second << "\n");
565 ++NegatorNumTreesNegated;
566
567 // We must temporarily unset the 'current' insertion point and DebugLoc of the
568 // InstCombine's IRBuilder so that it won't interfere with the ones we have
569 // already specified when producing negated instructions.
573
574 // And finally, we must add newly-created instructions into the InstCombine's
575 // worklist (in a proper order!) so it can attempt to combine them.
576 LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
577 << " instrs to InstCombine\n");
578 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
579 NegatorNumInstructionsNegatedSuccess += Res->first.size();
580
581 // They are in def-use order, so nothing fancy, just insert them in order.
582 for (Instruction *I : Res->first)
583 IC.Builder.Insert(I, I->getName());
584
585 // And return the new root.
586 return Res->second;
587}
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(...)
Definition: Debug.h:106
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:166
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:2631
static Constant * getNeg(Constant *C, bool HasNSW=false)
Definition: Constants.cpp:2625
This is an important base class in LLVM.
Definition: Constant.h:42
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:420
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:63
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:87
A debug info location.
Definition: DebugLoc.h:33
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2503
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2491
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:890
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1048
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2060
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2566
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1460
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:2429
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1772
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:1367
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1439
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2048
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2525
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1350
Value * CreateSDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1414
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Definition: IRBuilder.h:2034
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:1479
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1542
Value * CreateTruncOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2181
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1384
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:343
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:342
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:143
BuilderTy & Builder
Definition: InstCombiner.h:61
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:78
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
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
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:885
specific_intval< true > m_SpecificIntAllowPoison(const APInt &V)
Definition: PatternMatch.h:990
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:864
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:854
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:420
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:217
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