LLVM 19.0.0git
InstCombineNegator.cpp
Go to the documentation of this file.
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"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/ADT/Twine.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"
32#include "llvm/IR/Type.h"
33#include "llvm/IR/Use.h"
34#include "llvm/IR/User.h"
35#include "llvm/IR/Value.h"
43#include <cassert>
44#include <cstdint>
45#include <functional>
46#include <type_traits>
47#include <utility>
48
49namespace llvm {
50class DataLayout;
51class LLVMContext;
52} // namespace llvm
53
54using namespace llvm;
55
56#define DEBUG_TYPE "instcombine"
57
58STATISTIC(NegatorTotalNegationsAttempted,
59 "Negator: Number of negations attempted to be sinked");
60STATISTIC(NegatorNumTreesNegated,
61 "Negator: Number of negations successfully sinked");
62STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
63 "reached while attempting to sink negation");
64STATISTIC(NegatorTimesDepthLimitReached,
65 "Negator: How many times did the traversal depth limit was reached "
66 "during sinking");
68 NegatorNumValuesVisited,
69 "Negator: Total number of values visited during attempts to sink negation");
70STATISTIC(NegatorNumNegationsFoundInCache,
71 "Negator: How many negations did we retrieve/reuse from cache");
72STATISTIC(NegatorMaxTotalValuesVisited,
73 "Negator: Maximal number of values ever visited while attempting to "
74 "sink negation");
75STATISTIC(NegatorNumInstructionsCreatedTotal,
76 "Negator: Number of new negated instructions created, total");
77STATISTIC(NegatorMaxInstructionsCreated,
78 "Negator: Maximal number of new instructions created during negation "
79 "attempt");
80STATISTIC(NegatorNumInstructionsNegatedSuccess,
81 "Negator: Number of new negated instructions created in successful "
82 "negation sinking attempts");
83
84DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
85 "Controls Negator transformations in InstCombine pass");
86
87static cl::opt<bool>
88 NegatorEnabled("instcombine-negator-enabled", cl::init(true),
89 cl::desc("Should we attempt to sink negations?"));
90
92 NegatorMaxDepth("instcombine-negator-max-depth",
94 cl::desc("What is the maximal lookup depth when trying to "
95 "check for viability of negation sinking."));
96
97Negator::Negator(LLVMContext &C, const DataLayout &DL, bool IsTrulyNegation_)
98 : Builder(C, TargetFolder(DL),
100 ++NegatorNumInstructionsCreatedTotal;
101 NewInstructions.push_back(I);
102 })),
103 IsTrulyNegation(IsTrulyNegation_) {}
104
105#if LLVM_ENABLE_STATS
106Negator::~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.
115std::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.
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.
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 &&
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)
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.
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}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file provides internal interfaces used to implement the InstCombine.
static constexpr unsigned NegatorDefaultMaxDepth
static cl::opt< bool > NegatorEnabled("instcombine-negator-enabled", cl::init(true), cl::desc("Should we attempt to sink negations?"))
static cl::opt< unsigned > NegatorMaxDepth("instcombine-negator-max-depth", cl::init(NegatorDefaultMaxDepth), cl::desc("What is the maximal lookup depth when trying to " "check for viability of negation sinking."))
This file provides the interface for the instcombine pass implementation.
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This defines the Use class.
Class for arbitrary precision integers.
Definition: APInt.h:76
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2531
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2562
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2525
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:417
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
A debug info location.
Definition: DebugLoc.h:33
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2006
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2455
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2443
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1110
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2022
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2518
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1431
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:220
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2380
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1748
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Definition: IRBuilder.h:145
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1338
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1410
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2010
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2477
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1321
Value * CreateSDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1385
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:169
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1450
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1513
Value * CreateTruncOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2136
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1355
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:76
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:340
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:138
BuilderTy & Builder
Definition: InstCombiner.h:60
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
static Value * Negate(bool LHSIsZero, bool IsNSW, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
size_t size() const
Definition: SmallVector.h:91
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:34
LLVM Value Representation.
Definition: Value.h:74
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:541
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:460
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:800
match_combine_or< CastOperator_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:911
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:294
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:152
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:862
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ Xor
Bitwise or logical XOR of integers.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N