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/Compiler.h"
38#include "llvm/Support/DebugCounter.h"
39#include "llvm/Support/ErrorHandling.h"
40#include "llvm/Support/raw_ostream.h"
41#include "llvm/Transforms/InstCombine/InstCombiner.h"
42#include <cassert>
43#include <cstdint>
44#include <functional>
45#include <utility>
46
47using namespace llvm;
48using namespace llvm::PatternMatch;
49
50#define DEBUG_TYPE "instcombine"
51
52STATISTIC(NegatorTotalNegationsAttempted,
53 "Negator: Number of negations attempted to be sinked");
54STATISTIC(NegatorNumTreesNegated,
55 "Negator: Number of negations successfully sinked");
56STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
57 "reached while attempting to sink negation");
58STATISTIC(NegatorTimesDepthLimitReached,
59 "Negator: How many times did the traversal depth limit was reached "
60 "during sinking");
61STATISTIC(
62 NegatorNumValuesVisited,
63 "Negator: Total number of values visited during attempts to sink negation");
64STATISTIC(NegatorNumNegationsFoundInCache,
65 "Negator: How many negations did we retrieve/reuse from cache");
66STATISTIC(NegatorMaxTotalValuesVisited,
67 "Negator: Maximal number of values ever visited while attempting to "
68 "sink negation");
69STATISTIC(NegatorNumInstructionsCreatedTotal,
70 "Negator: Number of new negated instructions created, total");
71STATISTIC(NegatorMaxInstructionsCreated,
72 "Negator: Maximal number of new instructions created during negation "
73 "attempt");
74STATISTIC(NegatorNumInstructionsNegatedSuccess,
75 "Negator: Number of new negated instructions created in successful "
76 "negation sinking attempts");
77
78DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
79 "Controls Negator transformations in InstCombine pass");
80
81Negator::Negator(Module &M, const DominatorTree &DT_, bool IsTrulyNegation_,
82 unsigned MaxDepth)
83 : Builder(M, TargetFolder(M.getDataLayout()),
84 IRBuilderCallbackInserter([&](Instruction *I) {
85 ++NegatorNumInstructionsCreatedTotal;
86 NewInstructions.push_back(Elt: I);
87 })),
88 DT(DT_), IsTrulyNegation(IsTrulyNegation_), MaxDepth(MaxDepth) {}
89
90#if LLVM_ENABLE_STATS
91Negator::~Negator() {
92 NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
93}
94#endif
95
96// Due to the InstCombine's worklist management, there are no guarantees that
97// each instruction we'll encounter has been visited by InstCombine already.
98// In particular, most importantly for us, that means we have to canonicalize
99// constants to RHS ourselves, since that is helpful sometimes.
100std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(Instruction *I) {
101 assert(I->getNumOperands() == 2 && "Only for binops!");
102 std::array<Value *, 2> Ops{I->getOperand(i: 0), I->getOperand(i: 1)};
103 if (I->isCommutative() && InstCombiner::getComplexity(V: I->getOperand(i: 0)) <
104 InstCombiner::getComplexity(V: I->getOperand(i: 1)))
105 std::swap(a&: Ops[0], b&: Ops[1]);
106 return Ops;
107}
108
109// FIXME: can this be reworked into a worklist-based algorithm while preserving
110// the depth-first, early bailout traversal?
111[[nodiscard]] Value *Negator::visitImpl(Value *V, bool IsNSW, unsigned Depth) {
112 // -(undef) -> undef.
113 if (match(V, P: m_Undef()))
114 return V;
115
116 // In i1, negation can simply be ignored.
117 if (V->getType()->isIntOrIntVectorTy(BitWidth: 1))
118 return V;
119
120 Value *X;
121
122 // -(-(X)) -> X.
123 if (match(V, P: m_Neg(V: m_Value(V&: X))))
124 return X;
125
126 // Integral constants can be freely negated.
127 if (match(V, P: m_AnyIntegralConstant()))
128 return ConstantExpr::getNeg(C: cast<Constant>(Val: V),
129 /*HasNSW=*/false);
130
131 // If we have a non-instruction, then give up.
132 if (!isa<Instruction>(Val: V))
133 return nullptr;
134
135 // If we have started with a true negation (i.e. `sub 0, %y`), then if we've
136 // got instruction that does not require recursive reasoning, we can still
137 // negate it even if it has other uses, without increasing instruction count.
138 if (!V->hasOneUse() && !IsTrulyNegation)
139 return nullptr;
140
141 auto *I = cast<Instruction>(Val: V);
142 unsigned BitWidth = I->getType()->getScalarSizeInBits();
143
144 // We must preserve the insertion point and debug info that is set in the
145 // builder at the time this function is called.
146 InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
147 // And since we are trying to negate instruction I, that tells us about the
148 // insertion point and the debug info that we need to keep.
149 Builder.SetInsertPoint(I);
150
151 // In some cases we can give the answer without further recursion.
152 switch (I->getOpcode()) {
153 case Instruction::Add: {
154 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
155 // `inc` is always negatible.
156 if (match(V: Ops[1], P: m_One()))
157 return Builder.CreateNot(V: Ops[0], Name: I->getName() + ".neg");
158 break;
159 }
160 case Instruction::Xor:
161 // `not` is always negatible.
162 if (match(V: I, P: m_Not(V: m_Value(V&: X))))
163 return Builder.CreateAdd(LHS: X, RHS: ConstantInt::get(Ty: X->getType(), V: 1),
164 Name: I->getName() + ".neg");
165 break;
166 case Instruction::AShr:
167 case Instruction::LShr: {
168 // Right-shift sign bit smear is negatible.
169 const APInt *Op1Val;
170 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: Op1Val)) && *Op1Val == BitWidth - 1) {
171 Value *BO = I->getOpcode() == Instruction::AShr
172 ? Builder.CreateLShr(LHS: I->getOperand(i: 0), RHS: I->getOperand(i: 1))
173 : Builder.CreateAShr(LHS: I->getOperand(i: 0), RHS: I->getOperand(i: 1));
174 if (auto *NewInstr = dyn_cast<Instruction>(Val: BO)) {
175 NewInstr->copyIRFlags(V: I);
176 NewInstr->setName(I->getName() + ".neg");
177 }
178 return BO;
179 }
180 // While we could negate exact arithmetic shift:
181 // ashr exact %x, C --> sdiv exact i8 %x, -1<<C
182 // iff C != 0 and C u< bitwidth(%x), we don't want to,
183 // because division is *THAT* much worse than a shift.
184 break;
185 }
186 case Instruction::SExt:
187 case Instruction::ZExt:
188 // `*ext` of i1 is always negatible
189 if (I->getOperand(i: 0)->getType()->isIntOrIntVectorTy(BitWidth: 1))
190 return I->getOpcode() == Instruction::SExt
191 ? Builder.CreateZExt(V: I->getOperand(i: 0), DestTy: I->getType(),
192 Name: I->getName() + ".neg")
193 : Builder.CreateSExt(V: I->getOperand(i: 0), DestTy: I->getType(),
194 Name: I->getName() + ".neg");
195 break;
196 case Instruction::Select: {
197 // If both arms of the select are constants, we don't need to recurse.
198 // Therefore, this transform is not limited by uses.
199 auto *Sel = cast<SelectInst>(Val: I);
200 Constant *TrueC, *FalseC;
201 if (match(V: Sel->getTrueValue(), P: m_ImmConstant(C&: TrueC)) &&
202 match(V: Sel->getFalseValue(), P: m_ImmConstant(C&: FalseC))) {
203 Constant *NegTrueC = ConstantExpr::getNeg(C: TrueC);
204 Constant *NegFalseC = ConstantExpr::getNeg(C: FalseC);
205 return Builder.CreateSelect(C: Sel->getCondition(), True: NegTrueC, False: NegFalseC,
206 Name: I->getName() + ".neg", /*MDFrom=*/I);
207 }
208 break;
209 }
210 case Instruction::Call:
211 if (auto *CI = dyn_cast<CmpIntrinsic>(Val: I); CI && CI->hasOneUse())
212 return Builder.CreateIntrinsic(RetTy: CI->getType(), ID: CI->getIntrinsicID(),
213 Args: {CI->getRHS(), CI->getLHS()});
214 break;
215 default:
216 break; // Other instructions require recursive reasoning.
217 }
218
219 if (I->getOpcode() == Instruction::Sub &&
220 (I->hasOneUse() || match(V: I->getOperand(i: 0), P: m_ImmConstant()))) {
221 // `sub` is always negatible.
222 // However, only do this either if the old `sub` doesn't stick around, or
223 // it was subtracting from a constant. Otherwise, this isn't profitable.
224 return Builder.CreateSub(LHS: I->getOperand(i: 1), RHS: I->getOperand(i: 0),
225 Name: I->getName() + ".neg", /*HasNUW=*/false,
226 HasNSW: IsNSW && I->hasNoSignedWrap());
227 }
228
229 // Some other cases, while still don't require recursion,
230 // are restricted to the one-use case.
231 if (!V->hasOneUse())
232 return nullptr;
233
234 switch (I->getOpcode()) {
235 case Instruction::ZExt: {
236 // Negation of zext of signbit is signbit splat:
237 // 0 - (zext (i8 X u>> 7) to iN) --> sext (i8 X s>> 7) to iN
238 Value *SrcOp = I->getOperand(i: 0);
239 unsigned SrcWidth = SrcOp->getType()->getScalarSizeInBits();
240 const APInt &FullShift = APInt(SrcWidth, SrcWidth - 1);
241 if (IsTrulyNegation &&
242 match(V: SrcOp, P: m_LShr(L: m_Value(V&: X), R: m_SpecificIntAllowPoison(V: FullShift)))) {
243 Value *Ashr = Builder.CreateAShr(LHS: X, RHS: FullShift);
244 return Builder.CreateSExt(V: Ashr, DestTy: I->getType());
245 }
246 break;
247 }
248 case Instruction::And: {
249 Constant *ShAmt;
250 // sub(0,and(lshr(x,C),1)) --> add(ashr(shl(x,(BW-1)-C),BW-1),0)
251 // Only applies when this is a true negation (LHS is zero). For the
252 // general sub(y,and(lshr(x,C),1)) case the rewrite replaces one 2-insn
253 // sequence with another without reducing instruction count, and the
254 // resulting shl/ashr form prevents later target-specific combines (e.g.
255 // on PowerPC the original lshr+and maps to a single rldicl, while the
256 // shl+ashr form requires sldi+sradi).
257 if (IsTrulyNegation &&
258 match(V: I, P: m_And(L: m_OneUse(SubPattern: m_TruncOrSelf(
259 Op: m_LShr(L: m_Value(V&: X), R: m_ImmConstant(C&: ShAmt)))),
260 R: m_One()))) {
261 unsigned BW = X->getType()->getScalarSizeInBits();
262 Constant *BWMinusOne = ConstantInt::get(Ty: X->getType(), V: BW - 1);
263 Value *R = Builder.CreateShl(LHS: X, RHS: Builder.CreateSub(LHS: BWMinusOne, RHS: ShAmt));
264 R = Builder.CreateAShr(LHS: R, RHS: BWMinusOne);
265 return Builder.CreateTruncOrBitCast(V: R, DestTy: I->getType());
266 }
267 break;
268 }
269 case Instruction::SDiv:
270 // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
271 // While this is normally not behind a use-check,
272 // let's consider division to be special since it's costly.
273 if (auto *Op1C = dyn_cast<Constant>(Val: I->getOperand(i: 1))) {
274 if (!Op1C->containsUndefOrPoisonElement() &&
275 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
276 Value *BO =
277 Builder.CreateSDiv(LHS: I->getOperand(i: 0), RHS: ConstantExpr::getNeg(C: Op1C),
278 Name: I->getName() + ".neg");
279 if (auto *NewInstr = dyn_cast<Instruction>(Val: BO))
280 NewInstr->setIsExact(I->isExact());
281 return BO;
282 }
283 }
284 break;
285 }
286
287 // Rest of the logic is recursive, so if it's time to give up then it's time.
288 if (Depth > MaxDepth) {
289 LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
290 << *V << ". Giving up.\n");
291 ++NegatorTimesDepthLimitReached;
292 return nullptr;
293 }
294
295 switch (I->getOpcode()) {
296 case Instruction::Freeze: {
297 // `freeze` is negatible if its operand is negatible.
298 Value *NegOp = negate(V: I->getOperand(i: 0), IsNSW, Depth: Depth + 1);
299 if (!NegOp) // Early return.
300 return nullptr;
301 return Builder.CreateFreeze(V: NegOp, Name: I->getName() + ".neg");
302 }
303 case Instruction::PHI: {
304 // `phi` is negatible if all the incoming values are negatible.
305 auto *PHI = cast<PHINode>(Val: I);
306 SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
307 for (auto I : zip(t: PHI->incoming_values(), u&: NegatedIncomingValues)) {
308 // Don't negate indvars to avoid infinite loops.
309 if (DT.dominates(BB: PHI->getParent(), U: std::get<0>(t&: I)))
310 return nullptr;
311 if (!(std::get<1>(t&: I) =
312 negate(V: std::get<0>(t&: I), IsNSW, Depth: Depth + 1))) // Early return.
313 return nullptr;
314 }
315 // All incoming values are indeed negatible. Create negated PHI node.
316 PHINode *NegatedPHI = Builder.CreatePHI(
317 Ty: PHI->getType(), NumReservedValues: PHI->getNumOperands(), Name: PHI->getName() + ".neg");
318 for (auto I : zip(t&: NegatedIncomingValues, u: PHI->blocks()))
319 NegatedPHI->addIncoming(V: std::get<0>(t&: I), BB: std::get<1>(t&: I));
320 return NegatedPHI;
321 }
322 case Instruction::Select: {
323 if (isKnownNegation(X: I->getOperand(i: 1), Y: I->getOperand(i: 2), /*NeedNSW=*/false,
324 /*AllowPoison=*/false)) {
325 // Of one hand of select is known to be negation of another hand,
326 // just swap the hands around.
327 auto *NewSelect = cast<SelectInst>(Val: I->clone());
328 // Just swap the operands of the select.
329 NewSelect->swapValues();
330 // Don't swap prof metadata, we didn't change the branch behavior.
331 NewSelect->setName(I->getName() + ".neg");
332 // Poison-generating flags should be dropped
333 Value *TV = NewSelect->getTrueValue();
334 Value *FV = NewSelect->getFalseValue();
335 if (match(V: TV, P: m_Neg(V: m_Specific(V: FV))))
336 cast<Instruction>(Val: TV)->dropPoisonGeneratingFlags();
337 else if (match(V: FV, P: m_Neg(V: m_Specific(V: TV))))
338 cast<Instruction>(Val: FV)->dropPoisonGeneratingFlags();
339 else {
340 cast<Instruction>(Val: TV)->dropPoisonGeneratingFlags();
341 cast<Instruction>(Val: FV)->dropPoisonGeneratingFlags();
342 }
343 Builder.Insert(I: NewSelect);
344 return NewSelect;
345 }
346 // `select` is negatible if both hands of `select` are negatible.
347 Value *NegOp1 = negate(V: I->getOperand(i: 1), IsNSW, Depth: Depth + 1);
348 if (!NegOp1) // Early return.
349 return nullptr;
350 Value *NegOp2 = negate(V: I->getOperand(i: 2), IsNSW, Depth: Depth + 1);
351 if (!NegOp2)
352 return nullptr;
353 // Do preserve the metadata!
354 return Builder.CreateSelect(C: I->getOperand(i: 0), True: NegOp1, False: NegOp2,
355 Name: I->getName() + ".neg", /*MDFrom=*/I);
356 }
357 case Instruction::ShuffleVector: {
358 // `shufflevector` is negatible if both operands are negatible.
359 auto *Shuf = cast<ShuffleVectorInst>(Val: I);
360 Value *NegOp0 = negate(V: I->getOperand(i: 0), IsNSW, Depth: Depth + 1);
361 if (!NegOp0) // Early return.
362 return nullptr;
363 Value *NegOp1 = negate(V: I->getOperand(i: 1), IsNSW, Depth: Depth + 1);
364 if (!NegOp1)
365 return nullptr;
366 return Builder.CreateShuffleVector(V1: NegOp0, V2: NegOp1, Mask: Shuf->getShuffleMask(),
367 Name: I->getName() + ".neg");
368 }
369 case Instruction::ExtractElement: {
370 // `extractelement` is negatible if source operand is negatible.
371 auto *EEI = cast<ExtractElementInst>(Val: I);
372 Value *NegVector = negate(V: EEI->getVectorOperand(), IsNSW, Depth: Depth + 1);
373 if (!NegVector) // Early return.
374 return nullptr;
375 return Builder.CreateExtractElement(Vec: NegVector, Idx: EEI->getIndexOperand(),
376 Name: I->getName() + ".neg");
377 }
378 case Instruction::InsertElement: {
379 // `insertelement` is negatible if both the source vector and
380 // element-to-be-inserted are negatible.
381 auto *IEI = cast<InsertElementInst>(Val: I);
382 Value *NegVector = negate(V: IEI->getOperand(i_nocapture: 0), IsNSW, Depth: Depth + 1);
383 if (!NegVector) // Early return.
384 return nullptr;
385 Value *NegNewElt = negate(V: IEI->getOperand(i_nocapture: 1), IsNSW, Depth: Depth + 1);
386 if (!NegNewElt) // Early return.
387 return nullptr;
388 return Builder.CreateInsertElement(Vec: NegVector, NewElt: NegNewElt, Idx: IEI->getOperand(i_nocapture: 2),
389 Name: I->getName() + ".neg");
390 }
391 case Instruction::Trunc: {
392 // `trunc` is negatible if its operand is negatible.
393 Value *NegOp = negate(V: I->getOperand(i: 0), /* IsNSW */ false, Depth: Depth + 1);
394 if (!NegOp) // Early return.
395 return nullptr;
396 return Builder.CreateTrunc(V: NegOp, DestTy: I->getType(), Name: I->getName() + ".neg");
397 }
398 case Instruction::Shl: {
399 // `shl` is negatible if the first operand is negatible.
400 IsNSW &= I->hasNoSignedWrap();
401 if (Value *NegOp0 = negate(V: I->getOperand(i: 0), IsNSW, Depth: Depth + 1))
402 return Builder.CreateShl(LHS: NegOp0, RHS: I->getOperand(i: 1), Name: I->getName() + ".neg",
403 /*HasNUW=*/false, HasNSW: IsNSW);
404 // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
405 Constant *Op1C;
406 if (!match(V: I->getOperand(i: 1), P: m_ImmConstant(C&: Op1C)) || !IsTrulyNegation)
407 return nullptr;
408 return Builder.CreateMul(
409 LHS: I->getOperand(i: 0),
410 RHS: Builder.CreateShl(LHS: Constant::getAllOnesValue(Ty: Op1C->getType()), RHS: Op1C),
411 Name: I->getName() + ".neg", /*HasNUW=*/false, HasNSW: IsNSW);
412 }
413 case Instruction::Or: {
414 if (!cast<PossiblyDisjointInst>(Val: I)->isDisjoint())
415 return nullptr; // Don't know how to handle `or` in general.
416 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
417 // `or`/`add` are interchangeable when operands have no common bits set.
418 // `inc` is always negatible.
419 if (match(V: Ops[1], P: m_One()))
420 return Builder.CreateNot(V: Ops[0], Name: I->getName() + ".neg");
421 // Else, just defer to Instruction::Add handling.
422 [[fallthrough]];
423 }
424 case Instruction::Add: {
425 // `add` is negatible if both of its operands are negatible.
426 SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
427 for (Value *Op : I->operands()) {
428 // Can we sink the negation into this operand?
429 if (Value *NegOp = negate(V: Op, /* IsNSW */ false, Depth: Depth + 1)) {
430 NegatedOps.emplace_back(Args&: NegOp); // Successfully negated operand!
431 continue;
432 }
433 // Failed to sink negation into this operand. IFF we started from negation
434 // and we manage to sink negation into one operand, we can still do this.
435 if (!IsTrulyNegation)
436 return nullptr;
437 NonNegatedOps.emplace_back(Args&: Op); // Just record which operand that was.
438 }
439 assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&
440 "Internal consistency check failed.");
441 // Did we manage to sink negation into both of the operands?
442 if (NegatedOps.size() == 2) // Then we get to keep the `add`!
443 return Builder.CreateAdd(LHS: NegatedOps[0], RHS: NegatedOps[1],
444 Name: I->getName() + ".neg");
445 assert(IsTrulyNegation && "We should have early-exited then.");
446 // Completely failed to sink negation?
447 if (NonNegatedOps.size() == 2)
448 return nullptr;
449 // 0-(a+b) --> (-a)-b
450 return Builder.CreateSub(LHS: NegatedOps[0], RHS: NonNegatedOps[0],
451 Name: I->getName() + ".neg");
452 }
453 case Instruction::Xor: {
454 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
455 // `xor` is negatible if one of its operands is invertible.
456 // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
457 if (auto *C = dyn_cast<Constant>(Val: Ops[1])) {
458 if (IsTrulyNegation) {
459 Value *Xor = Builder.CreateXor(LHS: Ops[0], RHS: ConstantExpr::getNot(C));
460 return Builder.CreateAdd(LHS: Xor, RHS: ConstantInt::get(Ty: Xor->getType(), V: 1),
461 Name: I->getName() + ".neg");
462 }
463 }
464 return nullptr;
465 }
466 case Instruction::Mul: {
467 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
468 // `mul` is negatible if one of its operands is negatible.
469 Value *NegatedOp, *OtherOp;
470 // First try the second operand, in case it's a constant it will be best to
471 // just invert it instead of sinking the `neg` deeper.
472 if (Value *NegOp1 = negate(V: Ops[1], /* IsNSW */ false, Depth: Depth + 1)) {
473 NegatedOp = NegOp1;
474 OtherOp = Ops[0];
475 } else if (Value *NegOp0 = negate(V: Ops[0], /* IsNSW */ false, Depth: Depth + 1)) {
476 NegatedOp = NegOp0;
477 OtherOp = Ops[1];
478 } else
479 // Can't negate either of them.
480 return nullptr;
481 return Builder.CreateMul(LHS: NegatedOp, RHS: OtherOp, Name: I->getName() + ".neg",
482 /*HasNUW=*/false, HasNSW: IsNSW && I->hasNoSignedWrap());
483 }
484 default:
485 return nullptr; // Don't know, likely not negatible for free.
486 }
487
488 llvm_unreachable("Can't get here. We always return from switch.");
489}
490
491[[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) {
492 NegatorMaxDepthVisited.updateMax(V: Depth);
493 ++NegatorNumValuesVisited;
494
495#if LLVM_ENABLE_STATS
496 ++NumValuesVisitedInThisNegator;
497#endif
498
499#ifndef NDEBUG
500 // We can't ever have a Value with such an address.
501 Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
502#endif
503
504 // Did we already try to negate this value?
505 auto NegationsCacheIterator = NegationsCache.find(Val: V);
506 if (NegationsCacheIterator != NegationsCache.end()) {
507 ++NegatorNumNegationsFoundInCache;
508 Value *NegatedV = NegationsCacheIterator->second;
509 assert(NegatedV != Placeholder && "Encountered a cycle during negation.");
510 return NegatedV;
511 }
512
513#ifndef NDEBUG
514 // We did not find a cached result for negation of V. While there,
515 // let's temporairly cache a placeholder value, with the idea that if later
516 // during negation we fetch it from cache, we'll know we're in a cycle.
517 NegationsCache[V] = Placeholder;
518#endif
519
520 // No luck. Try negating it for real.
521 Value *NegatedV = visitImpl(V, IsNSW, Depth);
522 // And cache the (real) result for the future.
523 NegationsCache[V] = NegatedV;
524
525 return NegatedV;
526}
527
528[[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root,
529 bool IsNSW) {
530 Value *Negated = negate(V: Root, IsNSW, /*Depth=*/0);
531 if (!Negated) {
532 // We must cleanup newly-inserted instructions, to avoid any potential
533 // endless combine looping.
534 for (Instruction *I : llvm::reverse(C&: NewInstructions))
535 I->eraseFromParent();
536 return std::nullopt;
537 }
538 return std::make_pair(x: ArrayRef<Instruction *>(NewInstructions), y&: Negated);
539}
540
541[[nodiscard]] Value *Negator::Negate(bool LHSIsZero, bool IsNSW, Value *Root,
542 InstCombinerImpl &IC) {
543 ++NegatorTotalNegationsAttempted;
544 LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
545 << "\n");
546
547 if (!IC.CLOpts.negator_enabled ||
548 !DebugCounter::shouldExecute(Counter&: NegatorCounter))
549 return nullptr;
550
551 Negator N(IC.getModule(), IC.getDominatorTree(), LHSIsZero,
552 IC.CLOpts.negator_max_depth);
553 std::optional<Result> Res = N.run(Root, IsNSW);
554 if (!Res) { // Negation failed.
555 LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
556 << "\n");
557 return nullptr;
558 }
559
560 LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
561 << "\n NEW: " << *Res->second << "\n");
562 ++NegatorNumTreesNegated;
563
564 // And finally, we must add newly-created instructions into the InstCombine's
565 // worklist (in a proper order!) so it can attempt to combine them.
566 LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
567 << " instrs to InstCombine\n");
568 NegatorMaxInstructionsCreated.updateMax(V: Res->first.size());
569 NegatorNumInstructionsNegatedSuccess += Res->first.size();
570
571 for (Instruction *I : Res->first)
572 IC.addToWorklist(I);
573
574 // And return the new root.
575 return Res->second;
576}
577