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
100namespace {
101
102 class CorrelatedValuePropagation : public FunctionPass {
103 public:
104 static char ID;
105
106 CorrelatedValuePropagation(): FunctionPass(ID) {
108 }
109
110 bool runOnFunction(Function &F) override;
111
112 void getAnalysisUsage(AnalysisUsage &AU) const override {
118 }
119 };
120
121} // end anonymous namespace
122
123char CorrelatedValuePropagation::ID = 0;
124
125INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
126 "Value Propagation", false, false)
129INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
131
132// Public interface to the Value Propagation pass
134 return new CorrelatedValuePropagation();
135}
136
138 if (S->getType()->isVectorTy()) return false;
139 if (isa<Constant>(S->getCondition())) return false;
140
141 Constant *C = LVI->getConstant(S->getCondition(), S);
142 if (!C) return false;
143
144 ConstantInt *CI = dyn_cast<ConstantInt>(C);
145 if (!CI) return false;
146
147 Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
148 S->replaceAllUsesWith(ReplaceWith);
149 S->eraseFromParent();
150
151 ++NumSelects;
152
153 return true;
154}
155
156/// Try to simplify a phi with constant incoming values that match the edge
157/// values of a non-constant value on all other edges:
158/// bb0:
159/// %isnull = icmp eq i8* %x, null
160/// br i1 %isnull, label %bb2, label %bb1
161/// bb1:
162/// br label %bb2
163/// bb2:
164/// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
165/// -->
166/// %r = %x
168 DominatorTree *DT) {
169 // Collect incoming constants and initialize possible common value.
171 Value *CommonValue = nullptr;
172 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
173 Value *Incoming = P->getIncomingValue(i);
174 if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
175 IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
176 } else if (!CommonValue) {
177 // The potential common value is initialized to the first non-constant.
178 CommonValue = Incoming;
179 } else if (Incoming != CommonValue) {
180 // There can be only one non-constant common value.
181 return false;
182 }
183 }
184
185 if (!CommonValue || IncomingConstants.empty())
186 return false;
187
188 // The common value must be valid in all incoming blocks.
189 BasicBlock *ToBB = P->getParent();
190 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
191 if (!DT->dominates(CommonInst, ToBB))
192 return false;
193
194 // We have a phi with exactly 1 variable incoming value and 1 or more constant
195 // incoming values. See if all constant incoming values can be mapped back to
196 // the same incoming variable value.
197 for (auto &IncomingConstant : IncomingConstants) {
198 Constant *C = IncomingConstant.first;
199 BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
200 if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
201 return false;
202 }
203
204 // LVI only guarantees that the value matches a certain constant if the value
205 // is not poison. Make sure we don't replace a well-defined value with poison.
206 // This is usually satisfied due to a prior branch on the value.
207 if (!isGuaranteedNotToBePoison(CommonValue, nullptr, P, DT))
208 return false;
209
210 // All constant incoming values map to the same variable along the incoming
211 // edges of the phi. The phi is unnecessary.
212 P->replaceAllUsesWith(CommonValue);
213 P->eraseFromParent();
214 ++NumPhiCommon;
215 return true;
216}
217
218static Value *getValueOnEdge(LazyValueInfo *LVI, Value *Incoming,
220 Instruction *CxtI) {
221 if (Constant *C = LVI->getConstantOnEdge(Incoming, From, To, CxtI))
222 return C;
223
224 // Look if the incoming value is a select with a scalar condition for which
225 // LVI can tells us the value. In that case replace the incoming value with
226 // the appropriate value of the select. This often allows us to remove the
227 // select later.
228 auto *SI = dyn_cast<SelectInst>(Incoming);
229 if (!SI)
230 return nullptr;
231
232 // Once LVI learns to handle vector types, we could also add support
233 // for vector type constants that are not all zeroes or all ones.
234 Value *Condition = SI->getCondition();
235 if (!Condition->getType()->isVectorTy()) {
236 if (Constant *C = LVI->getConstantOnEdge(Condition, From, To, CxtI)) {
237 if (C->isOneValue())
238 return SI->getTrueValue();
239 if (C->isZeroValue())
240 return SI->getFalseValue();
241 }
242 }
243
244 // Look if the select has a constant but LVI tells us that the incoming
245 // value can never be that constant. In that case replace the incoming
246 // value with the other value of the select. This often allows us to
247 // remove the select later.
248
249 // The "false" case
250 if (auto *C = dyn_cast<Constant>(SI->getFalseValue()))
251 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
253 return SI->getTrueValue();
254
255 // The "true" case,
256 // similar to the select "false" case, but try the select "true" value
257 if (auto *C = dyn_cast<Constant>(SI->getTrueValue()))
258 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
260 return SI->getFalseValue();
261
262 return nullptr;
263}
264
266 const SimplifyQuery &SQ) {
267 bool Changed = false;
268
269 BasicBlock *BB = P->getParent();
270 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
271 Value *Incoming = P->getIncomingValue(i);
272 if (isa<Constant>(Incoming)) continue;
273
274 Value *V = getValueOnEdge(LVI, Incoming, P->getIncomingBlock(i), BB, P);
275 if (V) {
276 P->setIncomingValue(i, V);
277 Changed = true;
278 }
279 }
280
281 if (Value *V = simplifyInstruction(P, SQ)) {
282 P->replaceAllUsesWith(V);
283 P->eraseFromParent();
284 Changed = true;
285 }
286
287 if (!Changed)
288 Changed = simplifyCommonValuePhi(P, LVI, DT);
289
290 if (Changed)
291 ++NumPhis;
292
293 return Changed;
294}
295
297 Value *Pointer = nullptr;
298 if (LoadInst *L = dyn_cast<LoadInst>(I))
299 Pointer = L->getPointerOperand();
300 else
301 Pointer = cast<StoreInst>(I)->getPointerOperand();
302
303 if (isa<Constant>(Pointer)) return false;
304
305 Constant *C = LVI->getConstant(Pointer, I);
306 if (!C) return false;
307
308 ++NumMemAccess;
309 I->replaceUsesOfWith(Pointer, C);
310 return true;
311}
312
313static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI) {
315 return false;
316
317 // Only for signed relational comparisons of scalar integers.
318 if (Cmp->getType()->isVectorTy() ||
319 !Cmp->getOperand(0)->getType()->isIntegerTy())
320 return false;
321
322 if (!Cmp->isSigned())
323 return false;
324
325 ICmpInst::Predicate UnsignedPred =
327 Cmp->getPredicate(), LVI->getConstantRange(Cmp->getOperand(0), Cmp),
328 LVI->getConstantRange(Cmp->getOperand(1), Cmp));
329
330 if (UnsignedPred == ICmpInst::Predicate::BAD_ICMP_PREDICATE)
331 return false;
332
333 ++NumSICmps;
334 Cmp->setPredicate(UnsignedPred);
335
336 return true;
337}
338
339/// See if LazyValueInfo's ability to exploit edge conditions or range
340/// information is sufficient to prove this comparison. Even for local
341/// conditions, this can sometimes prove conditions instcombine can't by
342/// exploiting range information.
343static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
344 Value *Op0 = Cmp->getOperand(0);
345 Value *Op1 = Cmp->getOperand(1);
347 LVI->getPredicateAt(Cmp->getPredicate(), Op0, Op1, Cmp,
348 /*UseBlockValue=*/true);
349 if (Result == LazyValueInfo::Unknown)
350 return false;
351
352 ++NumCmps;
353 Constant *TorF =
355 Cmp->replaceAllUsesWith(TorF);
356 Cmp->eraseFromParent();
357 return true;
358}
359
360static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
361 if (constantFoldCmp(Cmp, LVI))
362 return true;
363
364 if (auto *ICmp = dyn_cast<ICmpInst>(Cmp))
365 if (processICmp(ICmp, LVI))
366 return true;
367
368 return false;
369}
370
371/// Simplify a switch instruction by removing cases which can never fire. If the
372/// uselessness of a case could be determined locally then constant propagation
373/// would already have figured it out. Instead, walk the predecessors and
374/// statically evaluate cases based on information available on that edge. Cases
375/// that cannot fire no matter what the incoming edge can safely be removed. If
376/// a case fires on every incoming edge then the entire switch can be removed
377/// and replaced with a branch to the case destination.
379 DominatorTree *DT) {
380 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
381 Value *Cond = I->getCondition();
382 BasicBlock *BB = I->getParent();
383
384 // Analyse each switch case in turn.
385 bool Changed = false;
386 DenseMap<BasicBlock*, int> SuccessorsCount;
387 for (auto *Succ : successors(BB))
388 SuccessorsCount[Succ]++;
389
390 { // Scope for SwitchInstProfUpdateWrapper. It must not live during
391 // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
393
394 for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
395 ConstantInt *Case = CI->getCaseValue();
398 /* UseBlockValue */ true);
399
400 if (State == LazyValueInfo::False) {
401 // This case never fires - remove it.
402 BasicBlock *Succ = CI->getCaseSuccessor();
403 Succ->removePredecessor(BB);
404 CI = SI.removeCase(CI);
405 CE = SI->case_end();
406
407 // The condition can be modified by removePredecessor's PHI simplification
408 // logic.
409 Cond = SI->getCondition();
410
411 ++NumDeadCases;
412 Changed = true;
413 if (--SuccessorsCount[Succ] == 0)
414 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
415 continue;
416 }
417 if (State == LazyValueInfo::True) {
418 // This case always fires. Arrange for the switch to be turned into an
419 // unconditional branch by replacing the switch condition with the case
420 // value.
421 SI->setCondition(Case);
422 NumDeadCases += SI->getNumCases();
423 Changed = true;
424 break;
425 }
426
427 // Increment the case iterator since we didn't delete it.
428 ++CI;
429 }
430 }
431
432 if (Changed)
433 // If the switch has been simplified to the point where it can be replaced
434 // by a branch then do so now.
435 ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
436 /*TLI = */ nullptr, &DTU);
437 return Changed;
438}
439
440// See if we can prove that the given binary op intrinsic will not overflow.
445 BO->getBinaryOp(), RRange, BO->getNoWrapKind());
446 return NWRegion.contains(LRange);
447}
448
450 bool NewNSW, bool NewNUW) {
451 Statistic *OpcNW, *OpcNSW, *OpcNUW;
452 switch (Opcode) {
453 case Instruction::Add:
454 OpcNW = &NumAddNW;
455 OpcNSW = &NumAddNSW;
456 OpcNUW = &NumAddNUW;
457 break;
458 case Instruction::Sub:
459 OpcNW = &NumSubNW;
460 OpcNSW = &NumSubNSW;
461 OpcNUW = &NumSubNUW;
462 break;
463 case Instruction::Mul:
464 OpcNW = &NumMulNW;
465 OpcNSW = &NumMulNSW;
466 OpcNUW = &NumMulNUW;
467 break;
468 case Instruction::Shl:
469 OpcNW = &NumShlNW;
470 OpcNSW = &NumShlNSW;
471 OpcNUW = &NumShlNUW;
472 break;
473 default:
474 llvm_unreachable("Will not be called with other binops");
475 }
476
477 auto *Inst = dyn_cast<Instruction>(V);
478 if (NewNSW) {
479 ++NumNW;
480 ++*OpcNW;
481 ++NumNSW;
482 ++*OpcNSW;
483 if (Inst)
484 Inst->setHasNoSignedWrap();
485 }
486 if (NewNUW) {
487 ++NumNW;
488 ++*OpcNW;
489 ++NumNUW;
490 ++*OpcNUW;
491 if (Inst)
492 Inst->setHasNoUnsignedWrap();
493 }
494}
495
496static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
497
498// See if @llvm.abs argument is alays positive/negative, and simplify.
499// Notably, INT_MIN can belong to either range, regardless of the NSW,
500// because it is negation-invariant.
502 Value *X = II->getArgOperand(0);
503 bool IsIntMinPoison = cast<ConstantInt>(II->getArgOperand(1))->isOne();
504
505 Type *Ty = X->getType();
506 Constant *IntMin =
509
510 // Is X in [0, IntMin]? NOTE: INT_MIN is fine!
511 Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_ULE, X, IntMin, II,
512 /*UseBlockValue=*/true);
513 if (Result == LazyValueInfo::True) {
514 ++NumAbs;
516 II->eraseFromParent();
517 return true;
518 }
519
520 // Is X in [IntMin, 0]? NOTE: INT_MIN is fine!
521 Constant *Zero = ConstantInt::getNullValue(Ty);
522 Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_SLE, X, Zero, II,
523 /*UseBlockValue=*/true);
524 assert(Result != LazyValueInfo::False && "Should have been handled already.");
525
526 if (Result == LazyValueInfo::Unknown) {
527 // Argument's range crosses zero.
528 bool Changed = false;
529 if (!IsIntMinPoison) {
530 // Can we at least tell that the argument is never INT_MIN?
531 Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_NE, X, IntMin, II,
532 /*UseBlockValue=*/true);
533 if (Result == LazyValueInfo::True) {
534 ++NumNSW;
535 ++NumSubNSW;
537 Changed = true;
538 }
539 }
540 return Changed;
541 }
542
543 IRBuilder<> B(II);
544 Value *NegX = B.CreateNeg(X, II->getName(), /*HasNUW=*/false,
545 /*HasNSW=*/IsIntMinPoison);
546 ++NumAbs;
547 II->replaceAllUsesWith(NegX);
548 II->eraseFromParent();
549
550 // See if we can infer some no-wrap flags.
551 if (auto *BO = dyn_cast<BinaryOperator>(NegX))
552 processBinOp(BO, LVI);
553
554 return true;
555}
556
557// See if this min/max intrinsic always picks it's one specific operand.
561 Pred, MM->getLHS(), MM->getRHS(), MM, /*UseBlockValue=*/true);
562 if (Result == LazyValueInfo::Unknown)
563 return false;
564
565 ++NumMinMax;
566 MM->replaceAllUsesWith(MM->getOperand(!Result));
567 MM->eraseFromParent();
568 return true;
569}
570
571// Rewrite this with.overflow intrinsic as non-overflowing.
573 IRBuilder<> B(WO);
574 Instruction::BinaryOps Opcode = WO->getBinaryOp();
575 bool NSW = WO->isSigned();
576 bool NUW = !WO->isSigned();
577
578 Value *NewOp =
579 B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
580 setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
581
582 StructType *ST = cast<StructType>(WO->getType());
584 { PoisonValue::get(ST->getElementType(0)),
585 ConstantInt::getFalse(ST->getElementType(1)) });
586 Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
587 WO->replaceAllUsesWith(NewI);
588 WO->eraseFromParent();
589 ++NumOverflows;
590
591 // See if we can infer the other no-wrap too.
592 if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
593 processBinOp(BO, LVI);
594
595 return true;
596}
597
599 Instruction::BinaryOps Opcode = SI->getBinaryOp();
600 bool NSW = SI->isSigned();
601 bool NUW = !SI->isSigned();
603 Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
604 BinOp->setDebugLoc(SI->getDebugLoc());
605 setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
606
607 SI->replaceAllUsesWith(BinOp);
608 SI->eraseFromParent();
609 ++NumSaturating;
610
611 // See if we can infer the other no-wrap too.
612 if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
613 processBinOp(BO, LVI);
614
615 return true;
616}
617
618/// Infer nonnull attributes for the arguments at the specified callsite.
619static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
620
621 if (CB.getIntrinsicID() == Intrinsic::abs) {
622 return processAbsIntrinsic(&cast<IntrinsicInst>(CB), LVI);
623 }
624
625 if (auto *MM = dyn_cast<MinMaxIntrinsic>(&CB)) {
626 return processMinMaxIntrinsic(MM, LVI);
627 }
628
629 if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
630 if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
631 return processOverflowIntrinsic(WO, LVI);
632 }
633 }
634
635 if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
636 if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
637 return processSaturatingInst(SI, LVI);
638 }
639 }
640
641 bool Changed = false;
642
643 // Deopt bundle operands are intended to capture state with minimal
644 // perturbance of the code otherwise. If we can find a constant value for
645 // any such operand and remove a use of the original value, that's
646 // desireable since it may allow further optimization of that value (e.g. via
647 // single use rules in instcombine). Since deopt uses tend to,
648 // idiomatically, appear along rare conditional paths, it's reasonable likely
649 // we may have a conditional fact with which LVI can fold.
650 if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
651 for (const Use &ConstU : DeoptBundle->Inputs) {
652 Use &U = const_cast<Use&>(ConstU);
653 Value *V = U.get();
654 if (V->getType()->isVectorTy()) continue;
655 if (isa<Constant>(V)) continue;
656
657 Constant *C = LVI->getConstant(V, &CB);
658 if (!C) continue;
659 U.set(C);
660 Changed = true;
661 }
662 }
663
665 unsigned ArgNo = 0;
666
667 for (Value *V : CB.args()) {
668 PointerType *Type = dyn_cast<PointerType>(V->getType());
669 // Try to mark pointer typed parameters as non-null. We skip the
670 // relatively expensive analysis for constants which are obviously either
671 // null or non-null to start with.
672 if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
673 !isa<Constant>(V) &&
674 LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
676 /*UseBlockValue=*/false) == LazyValueInfo::False)
677 ArgNos.push_back(ArgNo);
678 ArgNo++;
679 }
680
681 assert(ArgNo == CB.arg_size() && "Call arguments not processed correctly.");
682
683 if (ArgNos.empty())
684 return Changed;
685
686 NumNonNull += ArgNos.size();
688 LLVMContext &Ctx = CB.getContext();
689 AS = AS.addParamAttribute(Ctx, ArgNos,
690 Attribute::get(Ctx, Attribute::NonNull));
691 CB.setAttributes(AS);
692
693 return true;
694}
695
697
698static Domain getDomain(const ConstantRange &CR) {
699 if (CR.isAllNonNegative())
700 return Domain::NonNegative;
701 if (CR.icmp(ICmpInst::ICMP_SLE, APInt::getNullValue(CR.getBitWidth())))
702 return Domain::NonPositive;
703 return Domain::Unknown;
704}
705
706/// Try to shrink a sdiv/srem's width down to the smallest power of two that's
707/// sufficient to contain its operands.
708static bool narrowSDivOrSRem(BinaryOperator *Instr, const ConstantRange &LCR,
709 const ConstantRange &RCR) {
710 assert(Instr->getOpcode() == Instruction::SDiv ||
711 Instr->getOpcode() == Instruction::SRem);
712 assert(!Instr->getType()->isVectorTy());
713
714 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
715 // operands.
716 unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
717
718 // What is the smallest bit width that can accommodate the entire value ranges
719 // of both of the operands?
720 unsigned MinSignedBits =
721 std::max(LCR.getMinSignedBits(), RCR.getMinSignedBits());
722
723 // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
724 // prove that such a combination is impossible, we need to bump the bitwidth.
725 if (RCR.contains(APInt::getAllOnes(OrigWidth)) &&
726 LCR.contains(APInt::getSignedMinValue(MinSignedBits).sext(OrigWidth)))
727 ++MinSignedBits;
728
729 // Don't shrink below 8 bits wide.
730 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
731
732 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
733 // two.
734 if (NewWidth >= OrigWidth)
735 return false;
736
737 ++NumSDivSRemsNarrowed;
738 IRBuilder<> B{Instr};
739 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
740 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
741 Instr->getName() + ".lhs.trunc");
742 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
743 Instr->getName() + ".rhs.trunc");
744 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
745 auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
746 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
747 if (BinOp->getOpcode() == Instruction::SDiv)
748 BinOp->setIsExact(Instr->isExact());
749
750 Instr->replaceAllUsesWith(Sext);
751 Instr->eraseFromParent();
752 return true;
753}
754
755static bool expandUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
756 const ConstantRange &YCR) {
757 Type *Ty = Instr->getType();
758 assert(Instr->getOpcode() == Instruction::UDiv ||
759 Instr->getOpcode() == Instruction::URem);
760 assert(!Ty->isVectorTy());
761 bool IsRem = Instr->getOpcode() == Instruction::URem;
762
763 Value *X = Instr->getOperand(0);
764 Value *Y = Instr->getOperand(1);
765
766 // X u/ Y -> 0 iff X u< Y
767 // X u% Y -> X iff X u< Y
768 if (XCR.icmp(ICmpInst::ICMP_ULT, YCR)) {
769 Instr->replaceAllUsesWith(IsRem ? X : Constant::getNullValue(Ty));
770 Instr->eraseFromParent();
771 ++NumUDivURemsNarrowedExpanded;
772 return true;
773 }
774
775 // Given
776 // R = X u% Y
777 // We can represent the modulo operation as a loop/self-recursion:
778 // urem_rec(X, Y):
779 // Z = X - Y
780 // if X u< Y
781 // ret X
782 // else
783 // ret urem_rec(Z, Y)
784 // which isn't better, but if we only need a single iteration
785 // to compute the answer, this becomes quite good:
786 // R = X < Y ? X : X - Y iff X u< 2*Y (w/ unsigned saturation)
787 // Now, we do not care about all full multiples of Y in X, they do not change
788 // the answer, thus we could rewrite the expression as:
789 // X* = X - (Y * |_ X / Y _|)
790 // R = X* % Y
791 // so we don't need the *first* iteration to return, we just need to
792 // know *which* iteration will always return, so we could also rewrite it as:
793 // X* = X - (Y * |_ X / Y _|)
794 // R = X* % Y iff X* u< 2*Y (w/ unsigned saturation)
795 // but that does not seem profitable here.
796
797 // Even if we don't know X's range, the divisor may be so large, X can't ever
798 // be 2x larger than that. I.e. if divisor is always negative.
799 if (!XCR.icmp(ICmpInst::ICMP_ULT,
800 YCR.umul_sat(APInt(YCR.getBitWidth(), 2))) &&
801 !YCR.isAllNegative())
802 return false;
803
804 IRBuilder<> B(Instr);
805 Value *ExpandedOp;
806 if (IsRem) {
807 // NOTE: this transformation introduces two uses of X,
808 // but it may be undef so we must freeze it first.
809 Value *FrozenX = B.CreateFreeze(X, X->getName() + ".frozen");
810 auto *AdjX = B.CreateNUWSub(FrozenX, Y, Instr->getName() + ".urem");
811 auto *Cmp =
812 B.CreateICmp(ICmpInst::ICMP_ULT, FrozenX, Y, Instr->getName() + ".cmp");
813 ExpandedOp = B.CreateSelect(Cmp, FrozenX, AdjX);
814 } else {
815 auto *Cmp =
816 B.CreateICmp(ICmpInst::ICMP_UGE, X, Y, Instr->getName() + ".cmp");
817 ExpandedOp = B.CreateZExt(Cmp, Ty, Instr->getName() + ".udiv");
818 }
819 ExpandedOp->takeName(Instr);
820 Instr->replaceAllUsesWith(ExpandedOp);
821 Instr->eraseFromParent();
822 ++NumUDivURemsNarrowedExpanded;
823 return true;
824}
825
826/// Try to shrink a udiv/urem's width down to the smallest power of two that's
827/// sufficient to contain its operands.
828static bool narrowUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
829 const ConstantRange &YCR) {
830 assert(Instr->getOpcode() == Instruction::UDiv ||
831 Instr->getOpcode() == Instruction::URem);
832 assert(!Instr->getType()->isVectorTy());
833
834 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
835 // operands.
836
837 // What is the smallest bit width that can accommodate the entire value ranges
838 // of both of the operands?
839 unsigned MaxActiveBits = std::max(XCR.getActiveBits(), YCR.getActiveBits());
840 // Don't shrink below 8 bits wide.
841 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
842
843 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
844 // two.
845 if (NewWidth >= Instr->getType()->getIntegerBitWidth())
846 return false;
847
848 ++NumUDivURemsNarrowed;
849 IRBuilder<> B{Instr};
850 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
851 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
852 Instr->getName() + ".lhs.trunc");
853 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
854 Instr->getName() + ".rhs.trunc");
855 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
856 auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
857 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
858 if (BinOp->getOpcode() == Instruction::UDiv)
859 BinOp->setIsExact(Instr->isExact());
860
861 Instr->replaceAllUsesWith(Zext);
862 Instr->eraseFromParent();
863 return true;
864}
865
867 assert(Instr->getOpcode() == Instruction::UDiv ||
868 Instr->getOpcode() == Instruction::URem);
869 if (Instr->getType()->isVectorTy())
870 return false;
871
874 if (expandUDivOrURem(Instr, XCR, YCR))
875 return true;
876
877 return narrowUDivOrURem(Instr, XCR, YCR);
878}
879
880static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR,
881 const ConstantRange &RCR, LazyValueInfo *LVI) {
882 assert(SDI->getOpcode() == Instruction::SRem);
883 assert(!SDI->getType()->isVectorTy());
884
885 if (LCR.abs().icmp(CmpInst::ICMP_ULT, RCR.abs())) {
886 SDI->replaceAllUsesWith(SDI->getOperand(0));
887 SDI->eraseFromParent();
888 return true;
889 }
890
891 struct Operand {
892 Value *V;
893 Domain D;
894 };
895 std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
896 {SDI->getOperand(1), getDomain(RCR)}}};
897 if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
898 return false;
899
900 // We know domains of both of the operands!
901 ++NumSRems;
902
903 // We need operands to be non-negative, so negate each one that isn't.
904 for (Operand &Op : Ops) {
905 if (Op.D == Domain::NonNegative)
906 continue;
907 auto *BO =
908 BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
909 BO->setDebugLoc(SDI->getDebugLoc());
910 Op.V = BO;
911 }
912
913 auto *URem =
914 BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
915 URem->setDebugLoc(SDI->getDebugLoc());
916
917 auto *Res = URem;
918
919 // If the divident was non-positive, we need to negate the result.
920 if (Ops[0].D == Domain::NonPositive) {
921 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
922 Res->setDebugLoc(SDI->getDebugLoc());
923 }
924
925 SDI->replaceAllUsesWith(Res);
926 SDI->eraseFromParent();
927
928 // Try to simplify our new urem.
929 processUDivOrURem(URem, LVI);
930
931 return true;
932}
933
934/// See if LazyValueInfo's ability to exploit edge conditions or range
935/// information is sufficient to prove the signs of both operands of this SDiv.
936/// If this is the case, replace the SDiv with a UDiv. Even for local
937/// conditions, this can sometimes prove conditions instcombine can't by
938/// exploiting range information.
939static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR,
940 const ConstantRange &RCR, LazyValueInfo *LVI) {
941 assert(SDI->getOpcode() == Instruction::SDiv);
942 assert(!SDI->getType()->isVectorTy());
943
944 struct Operand {
945 Value *V;
946 Domain D;
947 };
948 std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
949 {SDI->getOperand(1), getDomain(RCR)}}};
950 if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
951 return false;
952
953 // We know domains of both of the operands!
954 ++NumSDivs;
955
956 // We need operands to be non-negative, so negate each one that isn't.
957 for (Operand &Op : Ops) {
958 if (Op.D == Domain::NonNegative)
959 continue;
960 auto *BO =
961 BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
962 BO->setDebugLoc(SDI->getDebugLoc());
963 Op.V = BO;
964 }
965
966 auto *UDiv =
967 BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
968 UDiv->setDebugLoc(SDI->getDebugLoc());
969 UDiv->setIsExact(SDI->isExact());
970
971 Value *Res = UDiv;
972
973 // If the operands had two different domains, we need to negate the result.
974 if (Ops[0].D != Ops[1].D)
975 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
976
977 SDI->replaceAllUsesWith(Res);
978 SDI->eraseFromParent();
979
980 // Try to simplify our new udiv.
981 processUDivOrURem(UDiv, LVI);
982
983 return true;
984}
985
987 assert(Instr->getOpcode() == Instruction::SDiv ||
988 Instr->getOpcode() == Instruction::SRem);
989 if (Instr->getType()->isVectorTy())
990 return false;
991
994 if (Instr->getOpcode() == Instruction::SDiv)
995 if (processSDiv(Instr, LCR, RCR, LVI))
996 return true;
997
998 if (Instr->getOpcode() == Instruction::SRem) {
999 if (processSRem(Instr, LCR, RCR, LVI))
1000 return true;
1001 }
1002
1003 return narrowSDivOrSRem(Instr, LCR, RCR);
1004}
1005
1007 if (SDI->getType()->isVectorTy())
1008 return false;
1009
1010 ConstantRange LRange = LVI->getConstantRangeAtUse(SDI->getOperandUse(0));
1011 unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
1012 ConstantRange NegOneOrZero =
1013 ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
1014 if (NegOneOrZero.contains(LRange)) {
1015 // ashr of -1 or 0 never changes the value, so drop the whole instruction
1016 ++NumAShrsRemoved;
1017 SDI->replaceAllUsesWith(SDI->getOperand(0));
1018 SDI->eraseFromParent();
1019 return true;
1020 }
1021
1022 if (!LRange.isAllNonNegative())
1023 return false;
1024
1025 ++NumAShrsConverted;
1026 auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
1027 "", SDI);
1028 BO->takeName(SDI);
1029 BO->setDebugLoc(SDI->getDebugLoc());
1030 BO->setIsExact(SDI->isExact());
1031 SDI->replaceAllUsesWith(BO);
1032 SDI->eraseFromParent();
1033
1034 return true;
1035}
1036
1037static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
1038 if (SDI->getType()->isVectorTy())
1039 return false;
1040
1041 const Use &Base = SDI->getOperandUse(0);
1043 return false;
1044
1045 ++NumSExt;
1046 auto *ZExt = CastInst::CreateZExtOrBitCast(Base, SDI->getType(), "", SDI);
1047 ZExt->takeName(SDI);
1048 ZExt->setDebugLoc(SDI->getDebugLoc());
1049 SDI->replaceAllUsesWith(ZExt);
1050 SDI->eraseFromParent();
1051
1052 return true;
1053}
1054
1055static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1056 using OBO = OverflowingBinaryOperator;
1057
1058 if (BinOp->getType()->isVectorTy())
1059 return false;
1060
1061 bool NSW = BinOp->hasNoSignedWrap();
1062 bool NUW = BinOp->hasNoUnsignedWrap();
1063 if (NSW && NUW)
1064 return false;
1065
1066 Instruction::BinaryOps Opcode = BinOp->getOpcode();
1067 Value *LHS = BinOp->getOperand(0);
1068 Value *RHS = BinOp->getOperand(1);
1069
1070 ConstantRange LRange = LVI->getConstantRange(LHS, BinOp);
1071 ConstantRange RRange = LVI->getConstantRange(RHS, BinOp);
1072
1073 bool Changed = false;
1074 bool NewNUW = false, NewNSW = false;
1075 if (!NUW) {
1077 Opcode, RRange, OBO::NoUnsignedWrap);
1078 NewNUW = NUWRange.contains(LRange);
1079 Changed |= NewNUW;
1080 }
1081 if (!NSW) {
1083 Opcode, RRange, OBO::NoSignedWrap);
1084 NewNSW = NSWRange.contains(LRange);
1085 Changed |= NewNSW;
1086 }
1087
1088 setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
1089
1090 return Changed;
1091}
1092
1093static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1094 if (BinOp->getType()->isVectorTy())
1095 return false;
1096
1097 // Pattern match (and lhs, C) where C includes a superset of bits which might
1098 // be set in lhs. This is a common truncation idiom created by instcombine.
1099 const Use &LHS = BinOp->getOperandUse(0);
1100 ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
1101 if (!RHS || !RHS->getValue().isMask())
1102 return false;
1103
1104 // We can only replace the AND with LHS based on range info if the range does
1105 // not include undef.
1106 ConstantRange LRange =
1107 LVI->getConstantRangeAtUse(LHS, /*UndefAllowed=*/false);
1108 if (!LRange.getUnsignedMax().ule(RHS->getValue()))
1109 return false;
1110
1111 BinOp->replaceAllUsesWith(LHS);
1112 BinOp->eraseFromParent();
1113 NumAnd++;
1114 return true;
1115}
1116
1117
1119 if (Constant *C = LVI->getConstant(V, At))
1120 return C;
1121
1122 // TODO: The following really should be sunk inside LVI's core algorithm, or
1123 // at least the outer shims around such.
1124 auto *C = dyn_cast<CmpInst>(V);
1125 if (!C) return nullptr;
1126
1127 Value *Op0 = C->getOperand(0);
1128 Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
1129 if (!Op1) return nullptr;
1130
1132 C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false);
1133 if (Result == LazyValueInfo::Unknown)
1134 return nullptr;
1135
1136 return (Result == LazyValueInfo::True) ?
1137 ConstantInt::getTrue(C->getContext()) :
1138 ConstantInt::getFalse(C->getContext());
1139}
1140
1142 const SimplifyQuery &SQ) {
1143 bool FnChanged = false;
1144 // Visiting in a pre-order depth-first traversal causes us to simplify early
1145 // blocks before querying later blocks (which require us to analyze early
1146 // blocks). Eagerly simplifying shallow blocks means there is strictly less
1147 // work to do for deep blocks. This also means we don't visit unreachable
1148 // blocks.
1149 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1150 bool BBChanged = false;
1151 for (Instruction &II : llvm::make_early_inc_range(*BB)) {
1152 switch (II.getOpcode()) {
1153 case Instruction::Select:
1154 BBChanged |= processSelect(cast<SelectInst>(&II), LVI);
1155 break;
1156 case Instruction::PHI:
1157 BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ);
1158 break;
1159 case Instruction::ICmp:
1160 case Instruction::FCmp:
1161 BBChanged |= processCmp(cast<CmpInst>(&II), LVI);
1162 break;
1163 case Instruction::Load:
1164 case Instruction::Store:
1165 BBChanged |= processMemAccess(&II, LVI);
1166 break;
1167 case Instruction::Call:
1168 case Instruction::Invoke:
1169 BBChanged |= processCallSite(cast<CallBase>(II), LVI);
1170 break;
1171 case Instruction::SRem:
1172 case Instruction::SDiv:
1173 BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI);
1174 break;
1175 case Instruction::UDiv:
1176 case Instruction::URem:
1177 BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
1178 break;
1179 case Instruction::AShr:
1180 BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
1181 break;
1182 case Instruction::SExt:
1183 BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
1184 break;
1185 case Instruction::Add:
1186 case Instruction::Sub:
1187 case Instruction::Mul:
1188 case Instruction::Shl:
1189 BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);
1190 break;
1191 case Instruction::And:
1192 BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI);
1193 break;
1194 }
1195 }
1196
1197 Instruction *Term = BB->getTerminator();
1198 switch (Term->getOpcode()) {
1199 case Instruction::Switch:
1200 BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1201 break;
1202 case Instruction::Ret: {
1203 auto *RI = cast<ReturnInst>(Term);
1204 // Try to determine the return value if we can. This is mainly here to
1205 // simplify the writing of unit tests, but also helps to enable IPO by
1206 // constant folding the return values of callees.
1207 auto *RetVal = RI->getReturnValue();
1208 if (!RetVal) break; // handle "ret void"
1209 if (isa<Constant>(RetVal)) break; // nothing to do
1210 if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1211 ++NumReturns;
1212 RI->replaceUsesOfWith(RetVal, C);
1213 BBChanged = true;
1214 }
1215 }
1216 }
1217
1218 FnChanged |= BBChanged;
1219 }
1220
1221 return FnChanged;
1222}
1223
1224bool CorrelatedValuePropagation::runOnFunction(Function &F) {
1225 if (skipFunction(F))
1226 return false;
1227
1228 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1229 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1230
1231 return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
1232}
1233
1238
1239 bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1240
1242 if (!Changed) {
1244 } else {
1247 }
1248
1249 // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1250 // because invalidating values in LVI is expensive. While CVP does preserve
1251 // LVI, we know that passes after JumpThreading+CVP will not need the result
1252 // of this analysis, so we forcefully discard it early.
1254 return PA;
1255}
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)
correlated Value Propagation
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)
correlated propagation
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.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
@ 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 getNullValue(unsigned numBits)
NOTE: This is soft-deprecated. Please use getZero() instead.
Definition: APInt.h:180
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
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
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:570
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:1184
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2036
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:1488
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1351
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1356
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:1342
unsigned arg_size() const
Definition: InstrTypes.h:1349
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1484
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:835
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:887
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:842
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1707
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:1314
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
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
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
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Legacy wrapper pass to provide the GlobalsAAResult object.
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:2550
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.
Wrapper around LazyValueInfo.
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 PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1759
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:258
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
void set(Value *Val)
Definition: Value.h:865
Value * get() const
Definition: Use.h:66
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ 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:721
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:455
Pass * createCorrelatedValuePropagationPass()
void initializeCorrelatedValuePropagationPass(PassRegistry &)
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)