Lines Matching +full:fetch +full:- +full:depth
1 //===- InstCombineNegator.cpp -----------------------------------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
57 STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
60 "Negator: How many times did the traversal depth limit was reached "
79 DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
83 NegatorEnabled("instcombine-negator-enabled", cl::init(true),
87 NegatorMaxDepth("instcombine-negator-max-depth",
89 cl::desc("What is the maximal lookup depth when trying to "
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)))
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.
128 if (V->getType()->isIntOrIntVectorTy(1))
133 // -(-(X)) -> X.
142 // If we have a non-instruction, then give up.
149 if (!V->hasOneUse() && !IsTrulyNegation)
153 unsigned BitWidth = I->getType()->getScalarSizeInBits();
163 switch (I->getOpcode()) {
168 return Builder.CreateNot(Ops[0], I->getName() + ".neg");
174 return Builder.CreateAdd(X, ConstantInt::get(X->getType(), 1),
175 I->getName() + ".neg");
179 // Right-shift sign bit smear is negatible.
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));
186 NewInstr->copyIRFlags(I);
187 NewInstr->setName(I->getName() + ".neg");
192 // ashr exact %x, C --> sdiv exact i8 %x, -1<<C
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");
212 if (match(Sel->getTrueValue(), m_ImmConstant(TrueC)) &&
213 match(Sel->getFalseValue(), m_ImmConstant(FalseC))) {
216 return Builder.CreateSelect(Sel->getCondition(), NegTrueC, NegFalseC,
217 I->getName() + ".neg", /*MDFrom=*/I);
222 if (auto *CI = dyn_cast<CmpIntrinsic>(I); CI && CI->hasOneUse())
223 return Builder.CreateIntrinsic(CI->getType(), CI->getIntrinsicID(),
224 {CI->getRHS(), CI->getLHS()});
230 if (I->getOpcode() == Instruction::Sub &&
231 (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
235 return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
236 I->getName() + ".neg", /* HasNUW */ false,
237 IsNSW && I->hasNoSignedWrap());
241 // are restricted to the one-use case.
242 if (!V->hasOneUse())
245 switch (I->getOpcode()) {
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);
255 return Builder.CreateSExt(Ashr, I->getType());
261 // sub(y,and(lshr(x,C),1)) --> add(ashr(shl(x,(BW-1)-C),BW-1),y)
265 unsigned BW = X->getType()->getScalarSizeInBits();
266 Constant *BWMinusOne = ConstantInt::get(X->getType(), BW - 1);
269 return Builder.CreateTruncOrBitCast(R, I->getType());
275 // While this is normally not behind a use-check,
277 if (auto *Op1C = dyn_cast<Constant>(I->getOperand(1))) {
278 if (!Op1C->containsUndefOrPoisonElement() &&
279 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
281 Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(Op1C),
282 I->getName() + ".neg");
284 NewInstr->setIsExact(I->isExact());
292 if (Depth > NegatorMaxDepth) {
293 LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
299 switch (I->getOpcode()) {
302 Value *NegOp = negate(I->getOperand(0), IsNSW, Depth + 1);
305 return Builder.CreateFreeze(NegOp, I->getName() + ".neg");
310 SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
311 for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
313 if (DT.dominates(PHI->getParent(), std::get<0>(I)))
316 negate(std::get<0>(I), IsNSW, Depth + 1))) // Early return.
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));
327 if (isKnownNegation(I->getOperand(1), I->getOperand(2), /*NeedNSW=*/false,
331 auto *NewSelect = cast<SelectInst>(I->clone());
333 NewSelect->swapValues();
335 NewSelect->setName(I->getName() + ".neg");
336 // Poison-generating flags should be dropped
337 Value *TV = NewSelect->getTrueValue();
338 Value *FV = NewSelect->getFalseValue();
340 cast<Instruction>(TV)->dropPoisonGeneratingFlags();
342 cast<Instruction>(FV)->dropPoisonGeneratingFlags();
344 cast<Instruction>(TV)->dropPoisonGeneratingFlags();
345 cast<Instruction>(FV)->dropPoisonGeneratingFlags();
351 Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);
354 Value *NegOp2 = negate(I->getOperand(2), IsNSW, Depth + 1);
358 return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
359 I->getName() + ".neg", /*MDFrom=*/I);
364 Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1);
367 Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);
370 return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
371 I->getName() + ".neg");
376 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW, Depth + 1);
379 return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
380 I->getName() + ".neg");
384 // element-to-be-inserted are negatible.
386 Value *NegVector = negate(IEI->getOperand(0), IsNSW, Depth + 1);
389 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW, Depth + 1);
392 return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
393 I->getName() + ".neg");
397 Value *NegOp = negate(I->getOperand(0), /* IsNSW */ false, Depth + 1);
400 return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
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",
410 if (!match(I->getOperand(1), m_ImmConstant(Op1C)) || !IsTrulyNegation)
413 I->getOperand(0),
414 Builder.CreateShl(Constant::getAllOnesValue(Op1C->getType()), Op1C),
415 I->getName() + ".neg", /* HasNUW */ false, IsNSW);
418 if (!cast<PossiblyDisjointInst>(I)->isDisjoint())
424 return Builder.CreateNot(Ops[0], I->getName() + ".neg");
431 for (Value *Op : I->operands()) {
433 if (Value *NegOp = negate(Op, /* IsNSW */ false, Depth + 1)) {
448 I->getName() + ".neg");
449 assert(IsTrulyNegation && "We should have early-exited then.");
453 // 0-(a+b) --> (-a)-b
455 I->getName() + ".neg");
464 return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
465 I->getName() + ".neg");
476 if (Value *NegOp1 = negate(Ops[1], /* IsNSW */ false, Depth + 1)) {
479 } else if (Value *NegOp0 = negate(Ops[0], /* IsNSW */ false, Depth + 1)) {
485 return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg",
486 /* HasNUW */ false, IsNSW && I->hasNoSignedWrap());
495 [[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) {
496 NegatorMaxDepthVisited.updateMax(Depth);
505 Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
512 Value *NegatedV = NegationsCacheIterator->second;
520 // during negation we fetch it from cache, we'll know we're in a cycle.
525 Value *NegatedV = visitImpl(V, IsNSW, Depth);
534 Value *Negated = negate(Root, IsNSW, /*Depth=*/0);
536 // We must cleanup newly-inserted instructions, to avoid any potential
539 I->eraseFromParent();
554 Negator N(Root->getContext(), IC.getDataLayout(), IC.getDominatorTree(),
564 << "\n NEW: " << *Res->second << "\n");
574 // And finally, we must add newly-created instructions into the InstCombine's
576 LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
578 NegatorMaxInstructionsCreated.updateMax(Res->first.size());
579 NegatorNumInstructionsNegatedSuccess += Res->first.size();
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());
586 return Res->second;