LLVM 17.0.0git
CorrelatedValuePropagation.cpp
Go to the documentation of this file.
1//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
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 the Correlated Value Propagation pass.
10//
11//===----------------------------------------------------------------------===//
12
16#include "llvm/ADT/Statistic.h"
22#include "llvm/IR/Attributes.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/Constant.h"
27#include "llvm/IR/Constants.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/InstrTypes.h"
32#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Operator.h"
36#include "llvm/IR/PassManager.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
40#include "llvm/Pass.h"
45#include <cassert>
46#include <optional>
47#include <utility>
48
49using namespace llvm;
50
51#define DEBUG_TYPE "correlated-value-propagation"
52
54 "canonicalize-icmp-predicates-to-unsigned", cl::init(true), cl::Hidden,
55 cl::desc("Enables canonicalization of signed relational predicates to "
56 "unsigned (e.g. sgt => ugt)"));
57
58STATISTIC(NumPhis, "Number of phis propagated");
59STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
60STATISTIC(NumSelects, "Number of selects propagated");
61STATISTIC(NumMemAccess, "Number of memory access targets propagated");
62STATISTIC(NumCmps, "Number of comparisons propagated");
63STATISTIC(NumReturns, "Number of return values propagated");
64STATISTIC(NumDeadCases, "Number of switch cases removed");
65STATISTIC(NumSDivSRemsNarrowed,
66 "Number of sdivs/srems whose width was decreased");
67STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
68STATISTIC(NumUDivURemsNarrowed,
69 "Number of udivs/urems whose width was decreased");
70STATISTIC(NumAShrsConverted, "Number of ashr converted to lshr");
71STATISTIC(NumAShrsRemoved, "Number of ashr removed");
72STATISTIC(NumSRems, "Number of srem converted to urem");
73STATISTIC(NumSExt, "Number of sext converted to zext");
74STATISTIC(NumSICmps, "Number of signed icmp preds simplified to unsigned");
75STATISTIC(NumAnd, "Number of ands removed");
76STATISTIC(NumNW, "Number of no-wrap deductions");
77STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
78STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
79STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
80STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
81STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
82STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
83STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
84STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
85STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
86STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
87STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
88STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
89STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
90STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
91STATISTIC(NumAbs, "Number of llvm.abs intrinsics removed");
92STATISTIC(NumOverflows, "Number of overflow checks removed");
93STATISTIC(NumSaturating,
94 "Number of saturating arithmetics converted to normal arithmetics");
95STATISTIC(NumNonNull, "Number of function pointer arguments marked non-null");
96STATISTIC(NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed");
97STATISTIC(NumUDivURemsNarrowedExpanded,
98 "Number of bound udiv's/urem's expanded");
99
101 if (S->getType()->isVectorTy()) return false;
102 if (isa<Constant>(S->getCondition())) return false;
103
104 Constant *C = LVI->getConstant(S->getCondition(), S);
105 if (!C) return false;
106
107 ConstantInt *CI = dyn_cast<ConstantInt>(C);
108 if (!CI) return false;
109
110 Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
111 S->replaceAllUsesWith(ReplaceWith);
112 S->eraseFromParent();
113
114 ++NumSelects;
115
116 return true;
117}
118
119/// Try to simplify a phi with constant incoming values that match the edge
120/// values of a non-constant value on all other edges:
121/// bb0:
122/// %isnull = icmp eq i8* %x, null
123/// br i1 %isnull, label %bb2, label %bb1
124/// bb1:
125/// br label %bb2
126/// bb2:
127/// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
128/// -->
129/// %r = %x
131 DominatorTree *DT) {
132 // Collect incoming constants and initialize possible common value.
134 Value *CommonValue = nullptr;
135 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
136 Value *Incoming = P->getIncomingValue(i);
137 if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
138 IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
139 } else if (!CommonValue) {
140 // The potential common value is initialized to the first non-constant.
141 CommonValue = Incoming;
142 } else if (Incoming != CommonValue) {
143 // There can be only one non-constant common value.
144 return false;
145 }
146 }
147
148 if (!CommonValue || IncomingConstants.empty())
149 return false;
150
151 // The common value must be valid in all incoming blocks.
152 BasicBlock *ToBB = P->getParent();
153 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
154 if (!DT->dominates(CommonInst, ToBB))
155 return false;
156
157 // We have a phi with exactly 1 variable incoming value and 1 or more constant
158 // incoming values. See if all constant incoming values can be mapped back to
159 // the same incoming variable value.
160 for (auto &IncomingConstant : IncomingConstants) {
161 Constant *C = IncomingConstant.first;
162 BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
163 if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
164 return false;
165 }
166
167 // LVI only guarantees that the value matches a certain constant if the value
168 // is not poison. Make sure we don't replace a well-defined value with poison.
169 // This is usually satisfied due to a prior branch on the value.
170 if (!isGuaranteedNotToBePoison(CommonValue, nullptr, P, DT))
171 return false;
172
173 // All constant incoming values map to the same variable along the incoming
174 // edges of the phi. The phi is unnecessary.
175 P->replaceAllUsesWith(CommonValue);
176 P->eraseFromParent();
177 ++NumPhiCommon;
178 return true;
179}
180
181static Value *getValueOnEdge(LazyValueInfo *LVI, Value *Incoming,
183 Instruction *CxtI) {
184 if (Constant *C = LVI->getConstantOnEdge(Incoming, From, To, CxtI))
185 return C;
186
187 // Look if the incoming value is a select with a scalar condition for which
188 // LVI can tells us the value. In that case replace the incoming value with
189 // the appropriate value of the select. This often allows us to remove the
190 // select later.
191 auto *SI = dyn_cast<SelectInst>(Incoming);
192 if (!SI)
193 return nullptr;
194
195 // Once LVI learns to handle vector types, we could also add support
196 // for vector type constants that are not all zeroes or all ones.
197 Value *Condition = SI->getCondition();
198 if (!Condition->getType()->isVectorTy()) {
199 if (Constant *C = LVI->getConstantOnEdge(Condition, From, To, CxtI)) {
200 if (C->isOneValue())
201 return SI->getTrueValue();
202 if (C->isZeroValue())
203 return SI->getFalseValue();
204 }
205 }
206
207 // Look if the select has a constant but LVI tells us that the incoming
208 // value can never be that constant. In that case replace the incoming
209 // value with the other value of the select. This often allows us to
210 // remove the select later.
211
212 // The "false" case
213 if (auto *C = dyn_cast<Constant>(SI->getFalseValue()))
214 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
216 return SI->getTrueValue();
217
218 // The "true" case,
219 // similar to the select "false" case, but try the select "true" value
220 if (auto *C = dyn_cast<Constant>(SI->getTrueValue()))
221 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
223 return SI->getFalseValue();
224
225 return nullptr;
226}
227
229 const SimplifyQuery &SQ) {
230 bool Changed = false;
231
232 BasicBlock *BB = P->getParent();
233 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
234 Value *Incoming = P->getIncomingValue(i);
235 if (isa<Constant>(Incoming)) continue;
236
237 Value *V = getValueOnEdge(LVI, Incoming, P->getIncomingBlock(i), BB, P);
238 if (V) {
239 P->setIncomingValue(i, V);
240 Changed = true;
241 }
242 }
243
244 if (Value *V = simplifyInstruction(P, SQ)) {
245 P->replaceAllUsesWith(V);
246 P->eraseFromParent();
247 Changed = true;
248 }
249
250 if (!Changed)
251 Changed = simplifyCommonValuePhi(P, LVI, DT);
252
253 if (Changed)
254 ++NumPhis;
255
256 return Changed;
257}
258
260 Value *Pointer = nullptr;
261 if (LoadInst *L = dyn_cast<LoadInst>(I))
262 Pointer = L->getPointerOperand();
263 else
264 Pointer = cast<StoreInst>(I)->getPointerOperand();
265
266 if (isa<Constant>(Pointer)) return false;
267
268 Constant *C = LVI->getConstant(Pointer, I);
269 if (!C) return false;
270
271 ++NumMemAccess;
272 I->replaceUsesOfWith(Pointer, C);
273 return true;
274}
275
276static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI) {
278 return false;
279
280 // Only for signed relational comparisons of scalar integers.
281 if (Cmp->getType()->isVectorTy() ||
282 !Cmp->getOperand(0)->getType()->isIntegerTy())
283 return false;
284
285 if (!Cmp->isSigned())
286 return false;
287
288 ICmpInst::Predicate UnsignedPred =
290 Cmp->getPredicate(), LVI->getConstantRange(Cmp->getOperand(0), Cmp),
291 LVI->getConstantRange(Cmp->getOperand(1), Cmp));
292
293 if (UnsignedPred == ICmpInst::Predicate::BAD_ICMP_PREDICATE)
294 return false;
295
296 ++NumSICmps;
297 Cmp->setPredicate(UnsignedPred);
298
299 return true;
300}
301
302/// See if LazyValueInfo's ability to exploit edge conditions or range
303/// information is sufficient to prove this comparison. Even for local
304/// conditions, this can sometimes prove conditions instcombine can't by
305/// exploiting range information.
306static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
307 Value *Op0 = Cmp->getOperand(0);
308 Value *Op1 = Cmp->getOperand(1);
310 LVI->getPredicateAt(Cmp->getPredicate(), Op0, Op1, Cmp,
311 /*UseBlockValue=*/true);
312 if (Result == LazyValueInfo::Unknown)
313 return false;
314
315 ++NumCmps;
316 Constant *TorF =
318 Cmp->replaceAllUsesWith(TorF);
319 Cmp->eraseFromParent();
320 return true;
321}
322
323static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
324 if (constantFoldCmp(Cmp, LVI))
325 return true;
326
327 if (auto *ICmp = dyn_cast<ICmpInst>(Cmp))
328 if (processICmp(ICmp, LVI))
329 return true;
330
331 return false;
332}
333
334/// Simplify a switch instruction by removing cases which can never fire. If the
335/// uselessness of a case could be determined locally then constant propagation
336/// would already have figured it out. Instead, walk the predecessors and
337/// statically evaluate cases based on information available on that edge. Cases
338/// that cannot fire no matter what the incoming edge can safely be removed. If
339/// a case fires on every incoming edge then the entire switch can be removed
340/// and replaced with a branch to the case destination.
342 DominatorTree *DT) {
343 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
344 Value *Cond = I->getCondition();
345 BasicBlock *BB = I->getParent();
346
347 // Analyse each switch case in turn.
348 bool Changed = false;
349 DenseMap<BasicBlock*, int> SuccessorsCount;
350 for (auto *Succ : successors(BB))
351 SuccessorsCount[Succ]++;
352
353 { // Scope for SwitchInstProfUpdateWrapper. It must not live during
354 // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
356
357 for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
358 ConstantInt *Case = CI->getCaseValue();
361 /* UseBlockValue */ true);
362
363 if (State == LazyValueInfo::False) {
364 // This case never fires - remove it.
365 BasicBlock *Succ = CI->getCaseSuccessor();
366 Succ->removePredecessor(BB);
367 CI = SI.removeCase(CI);
368 CE = SI->case_end();
369
370 // The condition can be modified by removePredecessor's PHI simplification
371 // logic.
372 Cond = SI->getCondition();
373
374 ++NumDeadCases;
375 Changed = true;
376 if (--SuccessorsCount[Succ] == 0)
377 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
378 continue;
379 }
380 if (State == LazyValueInfo::True) {
381 // This case always fires. Arrange for the switch to be turned into an
382 // unconditional branch by replacing the switch condition with the case
383 // value.
384 SI->setCondition(Case);
385 NumDeadCases += SI->getNumCases();
386 Changed = true;
387 break;
388 }
389
390 // Increment the case iterator since we didn't delete it.
391 ++CI;
392 }
393 }
394
395 if (Changed)
396 // If the switch has been simplified to the point where it can be replaced
397 // by a branch then do so now.
398 ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
399 /*TLI = */ nullptr, &DTU);
400 return Changed;
401}
402
403// See if we can prove that the given binary op intrinsic will not overflow.
408 BO->getBinaryOp(), RRange, BO->getNoWrapKind());
409 return NWRegion.contains(LRange);
410}
411
413 bool NewNSW, bool NewNUW) {
414 Statistic *OpcNW, *OpcNSW, *OpcNUW;
415 switch (Opcode) {
416 case Instruction::Add:
417 OpcNW = &NumAddNW;
418 OpcNSW = &NumAddNSW;
419 OpcNUW = &NumAddNUW;
420 break;
421 case Instruction::Sub:
422 OpcNW = &NumSubNW;
423 OpcNSW = &NumSubNSW;
424 OpcNUW = &NumSubNUW;
425 break;
426 case Instruction::Mul:
427 OpcNW = &NumMulNW;
428 OpcNSW = &NumMulNSW;
429 OpcNUW = &NumMulNUW;
430 break;
431 case Instruction::Shl:
432 OpcNW = &NumShlNW;
433 OpcNSW = &NumShlNSW;
434 OpcNUW = &NumShlNUW;
435 break;
436 default:
437 llvm_unreachable("Will not be called with other binops");
438 }
439
440 auto *Inst = dyn_cast<Instruction>(V);
441 if (NewNSW) {
442 ++NumNW;
443 ++*OpcNW;
444 ++NumNSW;
445 ++*OpcNSW;
446 if (Inst)
447 Inst->setHasNoSignedWrap();
448 }
449 if (NewNUW) {
450 ++NumNW;
451 ++*OpcNW;
452 ++NumNUW;
453 ++*OpcNUW;
454 if (Inst)
455 Inst->setHasNoUnsignedWrap();
456 }
457}
458
459static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
460
461// See if @llvm.abs argument is alays positive/negative, and simplify.
462// Notably, INT_MIN can belong to either range, regardless of the NSW,
463// because it is negation-invariant.
465 Value *X = II->getArgOperand(0);
466 bool IsIntMinPoison = cast<ConstantInt>(II->getArgOperand(1))->isOne();
467
468 Type *Ty = X->getType();
469 Constant *IntMin =
472
473 // Is X in [0, IntMin]? NOTE: INT_MIN is fine!
474 Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_ULE, X, IntMin, II,
475 /*UseBlockValue=*/true);
476 if (Result == LazyValueInfo::True) {
477 ++NumAbs;
479 II->eraseFromParent();
480 return true;
481 }
482
483 // Is X in [IntMin, 0]? NOTE: INT_MIN is fine!
484 Constant *Zero = ConstantInt::getNullValue(Ty);
485 Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_SLE, X, Zero, II,
486 /*UseBlockValue=*/true);
487 assert(Result != LazyValueInfo::False && "Should have been handled already.");
488
489 if (Result == LazyValueInfo::Unknown) {
490 // Argument's range crosses zero.
491 bool Changed = false;
492 if (!IsIntMinPoison) {
493 // Can we at least tell that the argument is never INT_MIN?
494 Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_NE, X, IntMin, II,
495 /*UseBlockValue=*/true);
496 if (Result == LazyValueInfo::True) {
497 ++NumNSW;
498 ++NumSubNSW;
500 Changed = true;
501 }
502 }
503 return Changed;
504 }
505
506 IRBuilder<> B(II);
507 Value *NegX = B.CreateNeg(X, II->getName(), /*HasNUW=*/false,
508 /*HasNSW=*/IsIntMinPoison);
509 ++NumAbs;
510 II->replaceAllUsesWith(NegX);
511 II->eraseFromParent();
512
513 // See if we can infer some no-wrap flags.
514 if (auto *BO = dyn_cast<BinaryOperator>(NegX))
515 processBinOp(BO, LVI);
516
517 return true;
518}
519
520// See if this min/max intrinsic always picks it's one specific operand.
524 Pred, MM->getLHS(), MM->getRHS(), MM, /*UseBlockValue=*/true);
525 if (Result == LazyValueInfo::Unknown)
526 return false;
527
528 ++NumMinMax;
529 MM->replaceAllUsesWith(MM->getOperand(!Result));
530 MM->eraseFromParent();
531 return true;
532}
533
534// Rewrite this with.overflow intrinsic as non-overflowing.
536 IRBuilder<> B(WO);
537 Instruction::BinaryOps Opcode = WO->getBinaryOp();
538 bool NSW = WO->isSigned();
539 bool NUW = !WO->isSigned();
540
541 Value *NewOp =
542 B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
543 setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
544
545 StructType *ST = cast<StructType>(WO->getType());
547 { PoisonValue::get(ST->getElementType(0)),
548 ConstantInt::getFalse(ST->getElementType(1)) });
549 Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
550 WO->replaceAllUsesWith(NewI);
551 WO->eraseFromParent();
552 ++NumOverflows;
553
554 // See if we can infer the other no-wrap too.
555 if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
556 processBinOp(BO, LVI);
557
558 return true;
559}
560
562 Instruction::BinaryOps Opcode = SI->getBinaryOp();
563 bool NSW = SI->isSigned();
564 bool NUW = !SI->isSigned();
566 Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
567 BinOp->setDebugLoc(SI->getDebugLoc());
568 setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
569
570 SI->replaceAllUsesWith(BinOp);
571 SI->eraseFromParent();
572 ++NumSaturating;
573
574 // See if we can infer the other no-wrap too.
575 if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
576 processBinOp(BO, LVI);
577
578 return true;
579}
580
581/// Infer nonnull attributes for the arguments at the specified callsite.
582static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
583
584 if (CB.getIntrinsicID() == Intrinsic::abs) {
585 return processAbsIntrinsic(&cast<IntrinsicInst>(CB), LVI);
586 }
587
588 if (auto *MM = dyn_cast<MinMaxIntrinsic>(&CB)) {
589 return processMinMaxIntrinsic(MM, LVI);
590 }
591
592 if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
593 if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
594 return processOverflowIntrinsic(WO, LVI);
595 }
596 }
597
598 if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
599 if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
600 return processSaturatingInst(SI, LVI);
601 }
602 }
603
604 bool Changed = false;
605
606 // Deopt bundle operands are intended to capture state with minimal
607 // perturbance of the code otherwise. If we can find a constant value for
608 // any such operand and remove a use of the original value, that's
609 // desireable since it may allow further optimization of that value (e.g. via
610 // single use rules in instcombine). Since deopt uses tend to,
611 // idiomatically, appear along rare conditional paths, it's reasonable likely
612 // we may have a conditional fact with which LVI can fold.
613 if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
614 for (const Use &ConstU : DeoptBundle->Inputs) {
615 Use &U = const_cast<Use&>(ConstU);
616 Value *V = U.get();
617 if (V->getType()->isVectorTy()) continue;
618 if (isa<Constant>(V)) continue;
619
620 Constant *C = LVI->getConstant(V, &CB);
621 if (!C) continue;
622 U.set(C);
623 Changed = true;
624 }
625 }
626
628 unsigned ArgNo = 0;
629
630 for (Value *V : CB.args()) {
631 PointerType *Type = dyn_cast<PointerType>(V->getType());
632 // Try to mark pointer typed parameters as non-null. We skip the
633 // relatively expensive analysis for constants which are obviously either
634 // null or non-null to start with.
635 if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
636 !isa<Constant>(V) &&
637 LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
639 /*UseBlockValue=*/false) == LazyValueInfo::False)
640 ArgNos.push_back(ArgNo);
641 ArgNo++;
642 }
643
644 assert(ArgNo == CB.arg_size() && "Call arguments not processed correctly.");
645
646 if (ArgNos.empty())
647 return Changed;
648
649 NumNonNull += ArgNos.size();
651 LLVMContext &Ctx = CB.getContext();
652 AS = AS.addParamAttribute(Ctx, ArgNos,
653 Attribute::get(Ctx, Attribute::NonNull));
654 CB.setAttributes(AS);
655
656 return true;
657}
658
660
661static Domain getDomain(const ConstantRange &CR) {
662 if (CR.isAllNonNegative())
663 return Domain::NonNegative;
664 if (CR.icmp(ICmpInst::ICMP_SLE, APInt::getZero(CR.getBitWidth())))
665 return Domain::NonPositive;
666 return Domain::Unknown;
667}
668
669/// Try to shrink a sdiv/srem's width down to the smallest power of two that's
670/// sufficient to contain its operands.
671static bool narrowSDivOrSRem(BinaryOperator *Instr, const ConstantRange &LCR,
672 const ConstantRange &RCR) {
673 assert(Instr->getOpcode() == Instruction::SDiv ||
674 Instr->getOpcode() == Instruction::SRem);
675 assert(!Instr->getType()->isVectorTy());
676
677 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
678 // operands.
679 unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
680
681 // What is the smallest bit width that can accommodate the entire value ranges
682 // of both of the operands?
683 unsigned MinSignedBits =
684 std::max(LCR.getMinSignedBits(), RCR.getMinSignedBits());
685
686 // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
687 // prove that such a combination is impossible, we need to bump the bitwidth.
688 if (RCR.contains(APInt::getAllOnes(OrigWidth)) &&
689 LCR.contains(APInt::getSignedMinValue(MinSignedBits).sext(OrigWidth)))
690 ++MinSignedBits;
691
692 // Don't shrink below 8 bits wide.
693 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
694
695 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
696 // two.
697 if (NewWidth >= OrigWidth)
698 return false;
699
700 ++NumSDivSRemsNarrowed;
701 IRBuilder<> B{Instr};
702 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
703 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
704 Instr->getName() + ".lhs.trunc");
705 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
706 Instr->getName() + ".rhs.trunc");
707 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
708 auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
709 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
710 if (BinOp->getOpcode() == Instruction::SDiv)
711 BinOp->setIsExact(Instr->isExact());
712
713 Instr->replaceAllUsesWith(Sext);
714 Instr->eraseFromParent();
715 return true;
716}
717
718static bool expandUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
719 const ConstantRange &YCR) {
720 Type *Ty = Instr->getType();
721 assert(Instr->getOpcode() == Instruction::UDiv ||
722 Instr->getOpcode() == Instruction::URem);
723 assert(!Ty->isVectorTy());
724 bool IsRem = Instr->getOpcode() == Instruction::URem;
725
726 Value *X = Instr->getOperand(0);
727 Value *Y = Instr->getOperand(1);
728
729 // X u/ Y -> 0 iff X u< Y
730 // X u% Y -> X iff X u< Y
731 if (XCR.icmp(ICmpInst::ICMP_ULT, YCR)) {
732 Instr->replaceAllUsesWith(IsRem ? X : Constant::getNullValue(Ty));
733 Instr->eraseFromParent();
734 ++NumUDivURemsNarrowedExpanded;
735 return true;
736 }
737
738 // Given
739 // R = X u% Y
740 // We can represent the modulo operation as a loop/self-recursion:
741 // urem_rec(X, Y):
742 // Z = X - Y
743 // if X u< Y
744 // ret X
745 // else
746 // ret urem_rec(Z, Y)
747 // which isn't better, but if we only need a single iteration
748 // to compute the answer, this becomes quite good:
749 // R = X < Y ? X : X - Y iff X u< 2*Y (w/ unsigned saturation)
750 // Now, we do not care about all full multiples of Y in X, they do not change
751 // the answer, thus we could rewrite the expression as:
752 // X* = X - (Y * |_ X / Y _|)
753 // R = X* % Y
754 // so we don't need the *first* iteration to return, we just need to
755 // know *which* iteration will always return, so we could also rewrite it as:
756 // X* = X - (Y * |_ X / Y _|)
757 // R = X* % Y iff X* u< 2*Y (w/ unsigned saturation)
758 // but that does not seem profitable here.
759
760 // Even if we don't know X's range, the divisor may be so large, X can't ever
761 // be 2x larger than that. I.e. if divisor is always negative.
762 if (!XCR.icmp(ICmpInst::ICMP_ULT,
763 YCR.umul_sat(APInt(YCR.getBitWidth(), 2))) &&
764 !YCR.isAllNegative())
765 return false;
766
767 IRBuilder<> B(Instr);
768 Value *ExpandedOp;
769 if (IsRem) {
770 // NOTE: this transformation introduces two uses of X,
771 // but it may be undef so we must freeze it first.
772 Value *FrozenX = B.CreateFreeze(X, X->getName() + ".frozen");
773 auto *AdjX = B.CreateNUWSub(FrozenX, Y, Instr->getName() + ".urem");
774 auto *Cmp =
775 B.CreateICmp(ICmpInst::ICMP_ULT, FrozenX, Y, Instr->getName() + ".cmp");
776 ExpandedOp = B.CreateSelect(Cmp, FrozenX, AdjX);
777 } else {
778 auto *Cmp =
779 B.CreateICmp(ICmpInst::ICMP_UGE, X, Y, Instr->getName() + ".cmp");
780 ExpandedOp = B.CreateZExt(Cmp, Ty, Instr->getName() + ".udiv");
781 }
782 ExpandedOp->takeName(Instr);
783 Instr->replaceAllUsesWith(ExpandedOp);
784 Instr->eraseFromParent();
785 ++NumUDivURemsNarrowedExpanded;
786 return true;
787}
788
789/// Try to shrink a udiv/urem's width down to the smallest power of two that's
790/// sufficient to contain its operands.
791static bool narrowUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
792 const ConstantRange &YCR) {
793 assert(Instr->getOpcode() == Instruction::UDiv ||
794 Instr->getOpcode() == Instruction::URem);
795 assert(!Instr->getType()->isVectorTy());
796
797 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
798 // operands.
799
800 // What is the smallest bit width that can accommodate the entire value ranges
801 // of both of the operands?
802 unsigned MaxActiveBits = std::max(XCR.getActiveBits(), YCR.getActiveBits());
803 // Don't shrink below 8 bits wide.
804 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
805
806 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
807 // two.
808 if (NewWidth >= Instr->getType()->getIntegerBitWidth())
809 return false;
810
811 ++NumUDivURemsNarrowed;
812 IRBuilder<> B{Instr};
813 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
814 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
815 Instr->getName() + ".lhs.trunc");
816 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
817 Instr->getName() + ".rhs.trunc");
818 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
819 auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
820 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
821 if (BinOp->getOpcode() == Instruction::UDiv)
822 BinOp->setIsExact(Instr->isExact());
823
824 Instr->replaceAllUsesWith(Zext);
825 Instr->eraseFromParent();
826 return true;
827}
828
830 assert(Instr->getOpcode() == Instruction::UDiv ||
831 Instr->getOpcode() == Instruction::URem);
832 if (Instr->getType()->isVectorTy())
833 return false;
834
837 if (expandUDivOrURem(Instr, XCR, YCR))
838 return true;
839
840 return narrowUDivOrURem(Instr, XCR, YCR);
841}
842
843static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR,
844 const ConstantRange &RCR, LazyValueInfo *LVI) {
845 assert(SDI->getOpcode() == Instruction::SRem);
846 assert(!SDI->getType()->isVectorTy());
847
848 if (LCR.abs().icmp(CmpInst::ICMP_ULT, RCR.abs())) {
849 SDI->replaceAllUsesWith(SDI->getOperand(0));
850 SDI->eraseFromParent();
851 return true;
852 }
853
854 struct Operand {
855 Value *V;
856 Domain D;
857 };
858 std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
859 {SDI->getOperand(1), getDomain(RCR)}}};
860 if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
861 return false;
862
863 // We know domains of both of the operands!
864 ++NumSRems;
865
866 // We need operands to be non-negative, so negate each one that isn't.
867 for (Operand &Op : Ops) {
868 if (Op.D == Domain::NonNegative)
869 continue;
870 auto *BO =
871 BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
872 BO->setDebugLoc(SDI->getDebugLoc());
873 Op.V = BO;
874 }
875
876 auto *URem =
877 BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
878 URem->setDebugLoc(SDI->getDebugLoc());
879
880 auto *Res = URem;
881
882 // If the divident was non-positive, we need to negate the result.
883 if (Ops[0].D == Domain::NonPositive) {
884 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
885 Res->setDebugLoc(SDI->getDebugLoc());
886 }
887
888 SDI->replaceAllUsesWith(Res);
889 SDI->eraseFromParent();
890
891 // Try to simplify our new urem.
892 processUDivOrURem(URem, LVI);
893
894 return true;
895}
896
897/// See if LazyValueInfo's ability to exploit edge conditions or range
898/// information is sufficient to prove the signs of both operands of this SDiv.
899/// If this is the case, replace the SDiv with a UDiv. Even for local
900/// conditions, this can sometimes prove conditions instcombine can't by
901/// exploiting range information.
902static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR,
903 const ConstantRange &RCR, LazyValueInfo *LVI) {
904 assert(SDI->getOpcode() == Instruction::SDiv);
905 assert(!SDI->getType()->isVectorTy());
906
907 struct Operand {
908 Value *V;
909 Domain D;
910 };
911 std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
912 {SDI->getOperand(1), getDomain(RCR)}}};
913 if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
914 return false;
915
916 // We know domains of both of the operands!
917 ++NumSDivs;
918
919 // We need operands to be non-negative, so negate each one that isn't.
920 for (Operand &Op : Ops) {
921 if (Op.D == Domain::NonNegative)
922 continue;
923 auto *BO =
924 BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
925 BO->setDebugLoc(SDI->getDebugLoc());
926 Op.V = BO;
927 }
928
929 auto *UDiv =
930 BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
931 UDiv->setDebugLoc(SDI->getDebugLoc());
932 UDiv->setIsExact(SDI->isExact());
933
934 Value *Res = UDiv;
935
936 // If the operands had two different domains, we need to negate the result.
937 if (Ops[0].D != Ops[1].D)
938 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
939
940 SDI->replaceAllUsesWith(Res);
941 SDI->eraseFromParent();
942
943 // Try to simplify our new udiv.
944 processUDivOrURem(UDiv, LVI);
945
946 return true;
947}
948
950 assert(Instr->getOpcode() == Instruction::SDiv ||
951 Instr->getOpcode() == Instruction::SRem);
952 if (Instr->getType()->isVectorTy())
953 return false;
954
957 if (Instr->getOpcode() == Instruction::SDiv)
958 if (processSDiv(Instr, LCR, RCR, LVI))
959 return true;
960
961 if (Instr->getOpcode() == Instruction::SRem) {
962 if (processSRem(Instr, LCR, RCR, LVI))
963 return true;
964 }
965
966 return narrowSDivOrSRem(Instr, LCR, RCR);
967}
968
969static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
970 if (SDI->getType()->isVectorTy())
971 return false;
972
974 unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
975 ConstantRange NegOneOrZero =
976 ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
977 if (NegOneOrZero.contains(LRange)) {
978 // ashr of -1 or 0 never changes the value, so drop the whole instruction
979 ++NumAShrsRemoved;
980 SDI->replaceAllUsesWith(SDI->getOperand(0));
981 SDI->eraseFromParent();
982 return true;
983 }
984
985 if (!LRange.isAllNonNegative())
986 return false;
987
988 ++NumAShrsConverted;
989 auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
990 "", SDI);
991 BO->takeName(SDI);
992 BO->setDebugLoc(SDI->getDebugLoc());
993 BO->setIsExact(SDI->isExact());
994 SDI->replaceAllUsesWith(BO);
995 SDI->eraseFromParent();
996
997 return true;
998}
999
1000static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
1001 if (SDI->getType()->isVectorTy())
1002 return false;
1003
1004 const Use &Base = SDI->getOperandUse(0);
1006 return false;
1007
1008 ++NumSExt;
1009 auto *ZExt = CastInst::CreateZExtOrBitCast(Base, SDI->getType(), "", SDI);
1010 ZExt->takeName(SDI);
1011 ZExt->setDebugLoc(SDI->getDebugLoc());
1012 SDI->replaceAllUsesWith(ZExt);
1013 SDI->eraseFromParent();
1014
1015 return true;
1016}
1017
1018static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1019 using OBO = OverflowingBinaryOperator;
1020
1021 if (BinOp->getType()->isVectorTy())
1022 return false;
1023
1024 bool NSW = BinOp->hasNoSignedWrap();
1025 bool NUW = BinOp->hasNoUnsignedWrap();
1026 if (NSW && NUW)
1027 return false;
1028
1029 Instruction::BinaryOps Opcode = BinOp->getOpcode();
1030 Value *LHS = BinOp->getOperand(0);
1031 Value *RHS = BinOp->getOperand(1);
1032
1033 ConstantRange LRange = LVI->getConstantRange(LHS, BinOp);
1034 ConstantRange RRange = LVI->getConstantRange(RHS, BinOp);
1035
1036 bool Changed = false;
1037 bool NewNUW = false, NewNSW = false;
1038 if (!NUW) {
1040 Opcode, RRange, OBO::NoUnsignedWrap);
1041 NewNUW = NUWRange.contains(LRange);
1042 Changed |= NewNUW;
1043 }
1044 if (!NSW) {
1046 Opcode, RRange, OBO::NoSignedWrap);
1047 NewNSW = NSWRange.contains(LRange);
1048 Changed |= NewNSW;
1049 }
1050
1051 setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
1052
1053 return Changed;
1054}
1055
1056static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1057 if (BinOp->getType()->isVectorTy())
1058 return false;
1059
1060 // Pattern match (and lhs, C) where C includes a superset of bits which might
1061 // be set in lhs. This is a common truncation idiom created by instcombine.
1062 const Use &LHS = BinOp->getOperandUse(0);
1063 ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
1064 if (!RHS || !RHS->getValue().isMask())
1065 return false;
1066
1067 // We can only replace the AND with LHS based on range info if the range does
1068 // not include undef.
1069 ConstantRange LRange =
1070 LVI->getConstantRangeAtUse(LHS, /*UndefAllowed=*/false);
1071 if (!LRange.getUnsignedMax().ule(RHS->getValue()))
1072 return false;
1073
1074 BinOp->replaceAllUsesWith(LHS);
1075 BinOp->eraseFromParent();
1076 NumAnd++;
1077 return true;
1078}
1079
1080
1082 if (Constant *C = LVI->getConstant(V, At))
1083 return C;
1084
1085 // TODO: The following really should be sunk inside LVI's core algorithm, or
1086 // at least the outer shims around such.
1087 auto *C = dyn_cast<CmpInst>(V);
1088 if (!C) return nullptr;
1089
1090 Value *Op0 = C->getOperand(0);
1091 Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
1092 if (!Op1) return nullptr;
1093
1095 C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false);
1096 if (Result == LazyValueInfo::Unknown)
1097 return nullptr;
1098
1099 return (Result == LazyValueInfo::True) ?
1100 ConstantInt::getTrue(C->getContext()) :
1101 ConstantInt::getFalse(C->getContext());
1102}
1103
1105 const SimplifyQuery &SQ) {
1106 bool FnChanged = false;
1107 // Visiting in a pre-order depth-first traversal causes us to simplify early
1108 // blocks before querying later blocks (which require us to analyze early
1109 // blocks). Eagerly simplifying shallow blocks means there is strictly less
1110 // work to do for deep blocks. This also means we don't visit unreachable
1111 // blocks.
1112 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1113 bool BBChanged = false;
1114 for (Instruction &II : llvm::make_early_inc_range(*BB)) {
1115 switch (II.getOpcode()) {
1116 case Instruction::Select:
1117 BBChanged |= processSelect(cast<SelectInst>(&II), LVI);
1118 break;
1119 case Instruction::PHI:
1120 BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ);
1121 break;
1122 case Instruction::ICmp:
1123 case Instruction::FCmp:
1124 BBChanged |= processCmp(cast<CmpInst>(&II), LVI);
1125 break;
1126 case Instruction::Load:
1127 case Instruction::Store:
1128 BBChanged |= processMemAccess(&II, LVI);
1129 break;
1130 case Instruction::Call:
1131 case Instruction::Invoke:
1132 BBChanged |= processCallSite(cast<CallBase>(II), LVI);
1133 break;
1134 case Instruction::SRem:
1135 case Instruction::SDiv:
1136 BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI);
1137 break;
1138 case Instruction::UDiv:
1139 case Instruction::URem:
1140 BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
1141 break;
1142 case Instruction::AShr:
1143 BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
1144 break;
1145 case Instruction::SExt:
1146 BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
1147 break;
1148 case Instruction::Add:
1149 case Instruction::Sub:
1150 case Instruction::Mul:
1151 case Instruction::Shl:
1152 BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);
1153 break;
1154 case Instruction::And:
1155 BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI);
1156 break;
1157 }
1158 }
1159
1160 Instruction *Term = BB->getTerminator();
1161 switch (Term->getOpcode()) {
1162 case Instruction::Switch:
1163 BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1164 break;
1165 case Instruction::Ret: {
1166 auto *RI = cast<ReturnInst>(Term);
1167 // Try to determine the return value if we can. This is mainly here to
1168 // simplify the writing of unit tests, but also helps to enable IPO by
1169 // constant folding the return values of callees.
1170 auto *RetVal = RI->getReturnValue();
1171 if (!RetVal) break; // handle "ret void"
1172 if (isa<Constant>(RetVal)) break; // nothing to do
1173 if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1174 ++NumReturns;
1175 RI->replaceUsesOfWith(RetVal, C);
1176 BBChanged = true;
1177 }
1178 }
1179 }
1180
1181 FnChanged |= BBChanged;
1182 }
1183
1184 return FnChanged;
1185}
1186
1191
1192 bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1193
1195 if (!Changed) {
1197 } else {
1200 }
1201
1202 // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1203 // because invalidating values in LVI is expensive. While CVP does preserve
1204 // LVI, we know that passes after JumpThreading+CVP will not need the result
1205 // of this analysis, so we forcefully discard it early.
1207 return PA;
1208}
This file contains the simple types necessary to represent the attributes associated with functions a...
SmallVector< MachineOperand, 4 > Cond
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI)
static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI)
static bool processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI)
static bool processMemAccess(Instruction *I, LazyValueInfo *LVI)
static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI)
static bool expandUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR, const ConstantRange &YCR)
static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI)
See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove...
static bool processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI)
static Value * getValueOnEdge(LazyValueInfo *LVI, Value *Incoming, BasicBlock *From, BasicBlock *To, Instruction *CxtI)
static bool narrowUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR, const ConstantRange &YCR)
Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its ...
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
static bool processSelect(SelectInst *S, LazyValueInfo *LVI)
static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode, bool NewNSW, bool NewNUW)
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI)
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT)
Try to simplify a phi with constant incoming values that match the edge values of a non-constant valu...
static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR, const ConstantRange &RCR, LazyValueInfo *LVI)
static Domain getDomain(const ConstantRange &CR)
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI)
@ NonNegative
@ NonPositive
static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR, const ConstantRange &RCR, LazyValueInfo *LVI)
See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove...
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI)
static cl::opt< bool > CanonicalizeICmpPredicatesToUnsigned("canonicalize-icmp-predicates-to-unsigned", cl::init(true), cl::Hidden, cl::desc("Enables canonicalization of signed relational predicates to " "unsigned (e.g. sgt => ugt)"))
static bool narrowSDivOrSRem(BinaryOperator *Instr, const ConstantRange &LCR, const ConstantRange &RCR)
Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its ...
static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI)
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI)
static bool processAbsIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI)
static bool processCallSite(CallBase &CB, LazyValueInfo *LVI)
Infer nonnull attributes for the arguments at the specified callsite.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool runImpl(Function &F, const TargetLowering &TLI)
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define P(N)
This header defines various interfaces for pass management in LLVM.
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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
@ Struct
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1128
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:946
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:576
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:91
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:341
This class represents an intrinsic that is based on a binary operation.
Value * getRHS() const
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Value * getLHS() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
static BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2046
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1490
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1353
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1358
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1344
unsigned arg_size() const
Definition: InstrTypes.h:1351
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1486
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:708
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1054
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Definition: InstrTypes.h:903
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:199
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1706
This class represents a range of values.
Definition: ConstantRange.h:47
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
ConstantRange umul_sat(const ConstantRange &Other) const
Perform an unsigned saturating multiplication of two constant ranges.
static CmpInst::Predicate getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred, const ConstantRange &CR1, const ConstantRange &CR2)
If the comparison between constant ranges this and Other is insensitive to the signedness of the comp...
bool isAllNegative() const
Return true if all values in this range are negative.
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1315
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2558
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Analysis to compute lazy value information.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:60
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
An instruction for reading from memory.
Definition: Instructions.h:177
This class represents min/max intrinsics.
Value * getLHS() const
Value * getRHS() const
static ICmpInst::Predicate getPredicate(Intrinsic::ID ID)
Returns the comparison predicate underlying the intrinsic.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:75
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1758
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:206
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
This class represents a sign extension of integer types.
Represents a saturating add/sub intrinsic.
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getCondition() const
const Value * getTrueValue() const
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Class to represent struct types.
Definition: DerivedTypes.h:213
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Multiway switch.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:267
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
Represents an op.with.overflow intrinsic.
#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
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:126
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:732
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:469
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)