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"
23#include "llvm/Analysis/TargetFolder.h"
24#include "llvm/Analysis/ValueTracking.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"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/PatternMatch.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"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Compiler.h"
39#include "llvm/Support/DebugCounter.h"
40#include "llvm/Support/ErrorHandling.h"
41#include "llvm/Support/raw_ostream.h"
42#include "llvm/Transforms/InstCombine/InstCombiner.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");
62STATISTIC(
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(Val: true),
84 cl::desc("Should we attempt to sink negations?"));
85
86static cl::opt<unsigned>
87 NegatorMaxDepth("instcombine-negator-max-depth",
88 cl::init(Val: NegatorDefaultMaxDepth),
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),
95 IRBuilderCallbackInserter([&](Instruction *I) {
96 ++NegatorNumInstructionsCreatedTotal;
97 NewInstructions.push_back(Elt: 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(i: 0), I->getOperand(i: 1)};
114 if (I->isCommutative() && InstCombiner::getComplexity(V: I->getOperand(i: 0)) <
115 InstCombiner::getComplexity(V: I->getOperand(i: 1)))
116 std::swap(a&: Ops[0], b&: 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, P: m_Undef()))
125 return V;
126
127 // In i1, negation can simply be ignored.
128 if (V->getType()->isIntOrIntVectorTy(BitWidth: 1))
129 return V;
130
131 Value *X;
132
133 // -(-(X)) -> X.
134 if (match(V, P: m_Neg(V: m_Value(V&: X))))
135 return X;
136
137 // Integral constants can be freely negated.
138 if (match(V, P: m_AnyIntegralConstant()))
139 return ConstantExpr::getNeg(C: cast<Constant>(Val: V),
140 /*HasNSW=*/false);
141
142 // If we have a non-instruction, then give up.
143 if (!isa<Instruction>(Val: 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>(Val: 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.
157 InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
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(V: Ops[1], P: m_One()))
168 return Builder.CreateNot(V: Ops[0], Name: I->getName() + ".neg");
169 break;
170 }
171 case Instruction::Xor:
172 // `not` is always negatible.
173 if (match(V: I, P: m_Not(V: m_Value(V&: X))))
174 return Builder.CreateAdd(LHS: X, RHS: ConstantInt::get(Ty: X->getType(), V: 1),
175 Name: 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(V: I->getOperand(i: 1), P: m_APInt(Res&: Op1Val)) && *Op1Val == BitWidth - 1) {
182 Value *BO = I->getOpcode() == Instruction::AShr
183 ? Builder.CreateLShr(LHS: I->getOperand(i: 0), RHS: I->getOperand(i: 1))
184 : Builder.CreateAShr(LHS: I->getOperand(i: 0), RHS: I->getOperand(i: 1));
185 if (auto *NewInstr = dyn_cast<Instruction>(Val: BO)) {
186 NewInstr->copyIRFlags(V: 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(i: 0)->getType()->isIntOrIntVectorTy(BitWidth: 1))
201 return I->getOpcode() == Instruction::SExt
202 ? Builder.CreateZExt(V: I->getOperand(i: 0), DestTy: I->getType(),
203 Name: I->getName() + ".neg")
204 : Builder.CreateSExt(V: I->getOperand(i: 0), DestTy: I->getType(),
205 Name: 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>(Val: I);
211 Constant *TrueC, *FalseC;
212 if (match(V: Sel->getTrueValue(), P: m_ImmConstant(C&: TrueC)) &&
213 match(V: Sel->getFalseValue(), P: m_ImmConstant(C&: FalseC))) {
214 Constant *NegTrueC = ConstantExpr::getNeg(C: TrueC);
215 Constant *NegFalseC = ConstantExpr::getNeg(C: FalseC);
216 return Builder.CreateSelect(C: Sel->getCondition(), True: NegTrueC, False: NegFalseC,
217 Name: I->getName() + ".neg", /*MDFrom=*/I);
218 }
219 break;
220 }
221 case Instruction::Call:
222 if (auto *CI = dyn_cast<CmpIntrinsic>(Val: I); CI && CI->hasOneUse())
223 return Builder.CreateIntrinsic(RetTy: CI->getType(), ID: CI->getIntrinsicID(),
224 Args: {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(V: I->getOperand(i: 0), P: 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(LHS: I->getOperand(i: 1), RHS: I->getOperand(i: 0),
236 Name: I->getName() + ".neg", /*HasNUW=*/false,
237 HasNSW: 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(i: 0);
250 unsigned SrcWidth = SrcOp->getType()->getScalarSizeInBits();
251 const APInt &FullShift = APInt(SrcWidth, SrcWidth - 1);
252 if (IsTrulyNegation &&
253 match(V: SrcOp, P: m_LShr(L: m_Value(V&: X), R: m_SpecificIntAllowPoison(V: FullShift)))) {
254 Value *Ashr = Builder.CreateAShr(LHS: X, RHS: FullShift);
255 return Builder.CreateSExt(V: Ashr, DestTy: I->getType());
256 }
257 break;
258 }
259 case Instruction::And: {
260 Constant *ShAmt;
261 // sub(0,and(lshr(x,C),1)) --> add(ashr(shl(x,(BW-1)-C),BW-1),0)
262 // Only applies when this is a true negation (LHS is zero). For the
263 // general sub(y,and(lshr(x,C),1)) case the rewrite replaces one 2-insn
264 // sequence with another without reducing instruction count, and the
265 // resulting shl/ashr form prevents later target-specific combines (e.g.
266 // on PowerPC the original lshr+and maps to a single rldicl, while the
267 // shl+ashr form requires sldi+sradi).
268 if (IsTrulyNegation &&
269 match(V: I, P: m_And(L: m_OneUse(SubPattern: m_TruncOrSelf(
270 Op: m_LShr(L: m_Value(V&: X), R: m_ImmConstant(C&: ShAmt)))),
271 R: m_One()))) {
272 unsigned BW = X->getType()->getScalarSizeInBits();
273 Constant *BWMinusOne = ConstantInt::get(Ty: X->getType(), V: BW - 1);
274 Value *R = Builder.CreateShl(LHS: X, RHS: Builder.CreateSub(LHS: BWMinusOne, RHS: ShAmt));
275 R = Builder.CreateAShr(LHS: R, RHS: BWMinusOne);
276 return Builder.CreateTruncOrBitCast(V: R, DestTy: I->getType());
277 }
278 break;
279 }
280 case Instruction::SDiv:
281 // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
282 // While this is normally not behind a use-check,
283 // let's consider division to be special since it's costly.
284 if (auto *Op1C = dyn_cast<Constant>(Val: I->getOperand(i: 1))) {
285 if (!Op1C->containsUndefOrPoisonElement() &&
286 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
287 Value *BO =
288 Builder.CreateSDiv(LHS: I->getOperand(i: 0), RHS: ConstantExpr::getNeg(C: Op1C),
289 Name: I->getName() + ".neg");
290 if (auto *NewInstr = dyn_cast<Instruction>(Val: BO))
291 NewInstr->setIsExact(I->isExact());
292 return BO;
293 }
294 }
295 break;
296 }
297
298 // Rest of the logic is recursive, so if it's time to give up then it's time.
299 if (Depth > NegatorMaxDepth) {
300 LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
301 << *V << ". Giving up.\n");
302 ++NegatorTimesDepthLimitReached;
303 return nullptr;
304 }
305
306 switch (I->getOpcode()) {
307 case Instruction::Freeze: {
308 // `freeze` is negatible if its operand is negatible.
309 Value *NegOp = negate(V: I->getOperand(i: 0), IsNSW, Depth: Depth + 1);
310 if (!NegOp) // Early return.
311 return nullptr;
312 return Builder.CreateFreeze(V: NegOp, Name: I->getName() + ".neg");
313 }
314 case Instruction::PHI: {
315 // `phi` is negatible if all the incoming values are negatible.
316 auto *PHI = cast<PHINode>(Val: I);
317 SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
318 for (auto I : zip(t: PHI->incoming_values(), u&: NegatedIncomingValues)) {
319 // Don't negate indvars to avoid infinite loops.
320 if (DT.dominates(BB: PHI->getParent(), U: std::get<0>(t&: I)))
321 return nullptr;
322 if (!(std::get<1>(t&: I) =
323 negate(V: std::get<0>(t&: I), IsNSW, Depth: Depth + 1))) // Early return.
324 return nullptr;
325 }
326 // All incoming values are indeed negatible. Create negated PHI node.
327 PHINode *NegatedPHI = Builder.CreatePHI(
328 Ty: PHI->getType(), NumReservedValues: PHI->getNumOperands(), Name: PHI->getName() + ".neg");
329 for (auto I : zip(t&: NegatedIncomingValues, u: PHI->blocks()))
330 NegatedPHI->addIncoming(V: std::get<0>(t&: I), BB: std::get<1>(t&: I));
331 return NegatedPHI;
332 }
333 case Instruction::Select: {
334 if (isKnownNegation(X: I->getOperand(i: 1), Y: I->getOperand(i: 2), /*NeedNSW=*/false,
335 /*AllowPoison=*/false)) {
336 // Of one hand of select is known to be negation of another hand,
337 // just swap the hands around.
338 auto *NewSelect = cast<SelectInst>(Val: I->clone());
339 // Just swap the operands of the select.
340 NewSelect->swapValues();
341 // Don't swap prof metadata, we didn't change the branch behavior.
342 NewSelect->setName(I->getName() + ".neg");
343 // Poison-generating flags should be dropped
344 Value *TV = NewSelect->getTrueValue();
345 Value *FV = NewSelect->getFalseValue();
346 if (match(V: TV, P: m_Neg(V: m_Specific(V: FV))))
347 cast<Instruction>(Val: TV)->dropPoisonGeneratingFlags();
348 else if (match(V: FV, P: m_Neg(V: m_Specific(V: TV))))
349 cast<Instruction>(Val: FV)->dropPoisonGeneratingFlags();
350 else {
351 cast<Instruction>(Val: TV)->dropPoisonGeneratingFlags();
352 cast<Instruction>(Val: FV)->dropPoisonGeneratingFlags();
353 }
354 Builder.Insert(I: NewSelect);
355 return NewSelect;
356 }
357 // `select` is negatible if both hands of `select` are negatible.
358 Value *NegOp1 = negate(V: I->getOperand(i: 1), IsNSW, Depth: Depth + 1);
359 if (!NegOp1) // Early return.
360 return nullptr;
361 Value *NegOp2 = negate(V: I->getOperand(i: 2), IsNSW, Depth: Depth + 1);
362 if (!NegOp2)
363 return nullptr;
364 // Do preserve the metadata!
365 return Builder.CreateSelect(C: I->getOperand(i: 0), True: NegOp1, False: NegOp2,
366 Name: I->getName() + ".neg", /*MDFrom=*/I);
367 }
368 case Instruction::ShuffleVector: {
369 // `shufflevector` is negatible if both operands are negatible.
370 auto *Shuf = cast<ShuffleVectorInst>(Val: I);
371 Value *NegOp0 = negate(V: I->getOperand(i: 0), IsNSW, Depth: Depth + 1);
372 if (!NegOp0) // Early return.
373 return nullptr;
374 Value *NegOp1 = negate(V: I->getOperand(i: 1), IsNSW, Depth: Depth + 1);
375 if (!NegOp1)
376 return nullptr;
377 return Builder.CreateShuffleVector(V1: NegOp0, V2: NegOp1, Mask: Shuf->getShuffleMask(),
378 Name: I->getName() + ".neg");
379 }
380 case Instruction::ExtractElement: {
381 // `extractelement` is negatible if source operand is negatible.
382 auto *EEI = cast<ExtractElementInst>(Val: I);
383 Value *NegVector = negate(V: EEI->getVectorOperand(), IsNSW, Depth: Depth + 1);
384 if (!NegVector) // Early return.
385 return nullptr;
386 return Builder.CreateExtractElement(Vec: NegVector, Idx: EEI->getIndexOperand(),
387 Name: I->getName() + ".neg");
388 }
389 case Instruction::InsertElement: {
390 // `insertelement` is negatible if both the source vector and
391 // element-to-be-inserted are negatible.
392 auto *IEI = cast<InsertElementInst>(Val: I);
393 Value *NegVector = negate(V: IEI->getOperand(i_nocapture: 0), IsNSW, Depth: Depth + 1);
394 if (!NegVector) // Early return.
395 return nullptr;
396 Value *NegNewElt = negate(V: IEI->getOperand(i_nocapture: 1), IsNSW, Depth: Depth + 1);
397 if (!NegNewElt) // Early return.
398 return nullptr;
399 return Builder.CreateInsertElement(Vec: NegVector, NewElt: NegNewElt, Idx: IEI->getOperand(i_nocapture: 2),
400 Name: I->getName() + ".neg");
401 }
402 case Instruction::Trunc: {
403 // `trunc` is negatible if its operand is negatible.
404 Value *NegOp = negate(V: I->getOperand(i: 0), /* IsNSW */ false, Depth: Depth + 1);
405 if (!NegOp) // Early return.
406 return nullptr;
407 return Builder.CreateTrunc(V: NegOp, DestTy: I->getType(), Name: I->getName() + ".neg");
408 }
409 case Instruction::Shl: {
410 // `shl` is negatible if the first operand is negatible.
411 IsNSW &= I->hasNoSignedWrap();
412 if (Value *NegOp0 = negate(V: I->getOperand(i: 0), IsNSW, Depth: Depth + 1))
413 return Builder.CreateShl(LHS: NegOp0, RHS: I->getOperand(i: 1), Name: I->getName() + ".neg",
414 /*HasNUW=*/false, HasNSW: IsNSW);
415 // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
416 Constant *Op1C;
417 if (!match(V: I->getOperand(i: 1), P: m_ImmConstant(C&: Op1C)) || !IsTrulyNegation)
418 return nullptr;
419 return Builder.CreateMul(
420 LHS: I->getOperand(i: 0),
421 RHS: Builder.CreateShl(LHS: Constant::getAllOnesValue(Ty: Op1C->getType()), RHS: Op1C),
422 Name: I->getName() + ".neg", /*HasNUW=*/false, HasNSW: IsNSW);
423 }
424 case Instruction::Or: {
425 if (!cast<PossiblyDisjointInst>(Val: I)->isDisjoint())
426 return nullptr; // Don't know how to handle `or` in general.
427 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
428 // `or`/`add` are interchangeable when operands have no common bits set.
429 // `inc` is always negatible.
430 if (match(V: Ops[1], P: m_One()))
431 return Builder.CreateNot(V: Ops[0], Name: I->getName() + ".neg");
432 // Else, just defer to Instruction::Add handling.
433 [[fallthrough]];
434 }
435 case Instruction::Add: {
436 // `add` is negatible if both of its operands are negatible.
437 SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
438 for (Value *Op : I->operands()) {
439 // Can we sink the negation into this operand?
440 if (Value *NegOp = negate(V: Op, /* IsNSW */ false, Depth: Depth + 1)) {
441 NegatedOps.emplace_back(Args&: NegOp); // Successfully negated operand!
442 continue;
443 }
444 // Failed to sink negation into this operand. IFF we started from negation
445 // and we manage to sink negation into one operand, we can still do this.
446 if (!IsTrulyNegation)
447 return nullptr;
448 NonNegatedOps.emplace_back(Args&: Op); // Just record which operand that was.
449 }
450 assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
451 "Internal consistency check failed.");
452 // Did we manage to sink negation into both of the operands?
453 if (NegatedOps.size() == 2) // Then we get to keep the `add`!
454 return Builder.CreateAdd(LHS: NegatedOps[0], RHS: NegatedOps[1],
455 Name: I->getName() + ".neg");
456 assert(IsTrulyNegation && "We should have early-exited then.");
457 // Completely failed to sink negation?
458 if (NonNegatedOps.size() == 2)
459 return nullptr;
460 // 0-(a+b) --> (-a)-b
461 return Builder.CreateSub(LHS: NegatedOps[0], RHS: NonNegatedOps[0],
462 Name: I->getName() + ".neg");
463 }
464 case Instruction::Xor: {
465 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
466 // `xor` is negatible if one of its operands is invertible.
467 // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
468 if (auto *C = dyn_cast<Constant>(Val: Ops[1])) {
469 if (IsTrulyNegation) {
470 Value *Xor = Builder.CreateXor(LHS: Ops[0], RHS: ConstantExpr::getNot(C));
471 return Builder.CreateAdd(LHS: Xor, RHS: ConstantInt::get(Ty: Xor->getType(), V: 1),
472 Name: I->getName() + ".neg");
473 }
474 }
475 return nullptr;
476 }
477 case Instruction::Mul: {
478 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
479 // `mul` is negatible if one of its operands is negatible.
480 Value *NegatedOp, *OtherOp;
481 // First try the second operand, in case it's a constant it will be best to
482 // just invert it instead of sinking the `neg` deeper.
483 if (Value *NegOp1 = negate(V: Ops[1], /* IsNSW */ false, Depth: Depth + 1)) {
484 NegatedOp = NegOp1;
485 OtherOp = Ops[0];
486 } else if (Value *NegOp0 = negate(V: Ops[0], /* IsNSW */ false, Depth: Depth + 1)) {
487 NegatedOp = NegOp0;
488 OtherOp = Ops[1];
489 } else
490 // Can't negate either of them.
491 return nullptr;
492 return Builder.CreateMul(LHS: NegatedOp, RHS: OtherOp, Name: I->getName() + ".neg",
493 /*HasNUW=*/false, HasNSW: IsNSW && I->hasNoSignedWrap());
494 }
495 default:
496 return nullptr; // Don't know, likely not negatible for free.
497 }
498
499 llvm_unreachable("Can't get here. We always return from switch.");
500}
501
502[[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) {
503 NegatorMaxDepthVisited.updateMax(V: Depth);
504 ++NegatorNumValuesVisited;
505
506#if LLVM_ENABLE_STATS
507 ++NumValuesVisitedInThisNegator;
508#endif
509
510#ifndef NDEBUG
511 // We can't ever have a Value with such an address.
512 Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
513#endif
514
515 // Did we already try to negate this value?
516 auto NegationsCacheIterator = NegationsCache.find(Val: V);
517 if (NegationsCacheIterator != NegationsCache.end()) {
518 ++NegatorNumNegationsFoundInCache;
519 Value *NegatedV = NegationsCacheIterator->second;
520 assert(NegatedV != Placeholder && "Encountered a cycle during negation.");
521 return NegatedV;
522 }
523
524#ifndef NDEBUG
525 // We did not find a cached result for negation of V. While there,
526 // let's temporairly cache a placeholder value, with the idea that if later
527 // during negation we fetch it from cache, we'll know we're in a cycle.
528 NegationsCache[V] = Placeholder;
529#endif
530
531 // No luck. Try negating it for real.
532 Value *NegatedV = visitImpl(V, IsNSW, Depth);
533 // And cache the (real) result for the future.
534 NegationsCache[V] = NegatedV;
535
536 return NegatedV;
537}
538
539[[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root,
540 bool IsNSW) {
541 Value *Negated = negate(V: Root, IsNSW, /*Depth=*/0);
542 if (!Negated) {
543 // We must cleanup newly-inserted instructions, to avoid any potential
544 // endless combine looping.
545 for (Instruction *I : llvm::reverse(C&: NewInstructions))
546 I->eraseFromParent();
547 return std::nullopt;
548 }
549 return std::make_pair(x: ArrayRef<Instruction *>(NewInstructions), y&: Negated);
550}
551
552[[nodiscard]] Value *Negator::Negate(bool LHSIsZero, bool IsNSW, Value *Root,
553 InstCombinerImpl &IC) {
554 ++NegatorTotalNegationsAttempted;
555 LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
556 << "\n");
557
558 if (!NegatorEnabled || !DebugCounter::shouldExecute(Counter&: NegatorCounter))
559 return nullptr;
560
561 Negator N(Root->getContext(), IC.getDataLayout(), IC.getDominatorTree(),
562 LHSIsZero);
563 std::optional<Result> Res = N.run(Root, IsNSW);
564 if (!Res) { // Negation failed.
565 LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
566 << "\n");
567 return nullptr;
568 }
569
570 LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
571 << "\n NEW: " << *Res->second << "\n");
572 ++NegatorNumTreesNegated;
573
574 // We must temporarily unset the 'current' insertion point and DebugLoc of the
575 // InstCombine's IRBuilder so that it won't interfere with the ones we have
576 // already specified when producing negated instructions.
577 InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
578 IC.Builder.ClearInsertionPoint();
579 IC.Builder.SetCurrentDebugLocation(DebugLoc());
580
581 // And finally, we must add newly-created instructions into the InstCombine's
582 // worklist (in a proper order!) so it can attempt to combine them.
583 LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
584 << " instrs to InstCombine\n");
585 NegatorMaxInstructionsCreated.updateMax(V: Res->first.size());
586 NegatorNumInstructionsNegatedSuccess += Res->first.size();
587
588 // They are in def-use order, so nothing fancy, just insert them in order.
589 for (Instruction *I : Res->first)
590 IC.Builder.Insert(I, Name: I->getName());
591
592 // And return the new root.
593 return Res->second;
594}
595