llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

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