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