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