aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
AgeCommit message (Collapse)AuthorFilesLines
2019-08-15[llvm] Migrate llvm::make_unique to std::make_uniqueJonas Devlieghere1-1/+1
Now that we've moved to C++14, we no longer need the llvm::make_unique implementation from STLExtras.h. This patch is a mechanical replacement of (hopefully) all the llvm::make_unique instances across the monorepo. llvm-svn: 369013
2019-06-04Introduce Value::stripPointerCastsSameRepresentationJohannes Doerfert1-1/+1
This patch allows current users of Value::stripPointerCasts() to force the result of the function to have the same representation as the value it was called on. This is useful in various cases, e.g., (non-)null checks. In this patch only a single call site was adjusted to fix an existing misuse that would cause nonnull where they may be wrong. Uses in attribute deduction and other areas, e.g., D60047, are to be expected. For a discussion on this topic, please see [0]. [0] http://lists.llvm.org/pipermail/llvm-dev/2018-December/128423.html Reviewers: hfinkel, arsenm, reames Subscribers: wdng, hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61607 llvm-svn: 362545
2019-06-04[LVI][CVP] Add support for urem, srem and sdivNikita Popov1-21/+8
The underlying ConstantRange functionality has been added in D60952, D61207 and D61238, this just exposes it for LVI. I'm switching the code from using a whitelist to a blacklist, as we're down to one unsupported operation here (xor) and writing it this way seems more obvious :) Differential Revision: https://reviews.llvm.org/D62822 llvm-svn: 362519
2019-05-25[LVI][CVP] Add support for saturating add/subNikita Popov1-0/+36
Adds support for the uadd.sat family of intrinsics in LVI, based on ConstantRange methods from D60946. Differential Revision: https://reviews.llvm.org/D62447 llvm-svn: 361703
2019-05-25[LVI][CVP] Calculate with.overflow result rangeNikita Popov1-0/+15
In LVI, calculate the range of extractvalue(op.with.overflow(%x, %y), 0) as the range of op(%x, %y). This is mainly useful in conjunction with D60650: If the result of the operation is extracted in a branch guarded against overflow, then the value of %x will be appropriately constrained and the result range of the operation will be calculated taking that into account. Differential Revision: https://reviews.llvm.org/D60656 llvm-svn: 361693
2019-05-25[LVI] Extract helper for binary range calculations; NFCNikita Popov1-23/+28
llvm-svn: 361692
2019-05-14[LVI][CVP] Add support for abs/nabs select pattern flavorNikita Popov1-1/+22
Based on ConstantRange support added in D61084, we can now handle abs and nabs select pattern flavors in LVI. Differential Revision: https://reviews.llvm.org/D61794 llvm-svn: 360700
2019-04-28[ConstantRange] Add makeExactNoWrapRegion()Nikita Popov1-2/+2
I got confused on the terminology, and the change in D60598 was not correct. I was thinking of "exact" in terms of the result being non-approximate. However, the relevant distinction here is whether the result is * Largest range such that: Forall Y in Other: Forall X in Result: X BinOp Y does not wrap. (makeGuaranteedNoWrapRegion) * Smallest range such that: Forall Y in Other: Forall X not in Result: X BinOp Y wraps. (A hypothetical makeAllowedNoWrapRegion) * Both. (makeExactNoWrapRegion) I'm adding a separate makeExactNoWrapRegion method accepting a single APInt (same as makeExactICmpRegion) and using it in the places where the guarantee is relevant. Differential Revision: https://reviews.llvm.org/D60960 llvm-svn: 359402
2019-04-22Revert "[ConstantRange] Rename make{Guaranteed -> Exact}NoWrapRegion() NFC"Nikita Popov1-1/+1
This reverts commit 7bf4d7c07f2fac862ef34c82ad0fef6513452445. After thinking about this more, this isn't right, the range is not exact in the same sense as makeExactICmpRegion(). This needs a separate function. llvm-svn: 358876
2019-04-22[ConstantRange] Rename make{Guaranteed -> Exact}NoWrapRegion() NFCNikita Popov1-1/+1
Following D60632 makeGuaranteedNoWrapRegion() always returns an exact nowrap region. Rename the function accordingly. This is in line with the naming of makeExactICmpRegion(). llvm-svn: 358875
2019-04-17[LVI][CVP] Constrain values in with.overflow branchesNikita Popov1-0/+27
If a branch is conditional on extractvalue(op.with.overflow(%x, C), 1) then we can constrain the value of %x inside the branch based on makeGuaranteedNoWrapRegion(). We do this by extending the edge-value handling in LVI. This allows CVP to then fold comparisons against %x, as illustrated in the tests. Differential Revision: https://reviews.llvm.org/D60650 llvm-svn: 358597
2019-03-24[ConstantRange] Add getFull() + getEmpty() named constructors; NFCNikita Popov1-5/+5
This adds ConstantRange::getFull(BitWidth) and ConstantRange::getEmpty(BitWidth) named constructors as more readable alternatives to the current ConstantRange(BitWidth, /* full */ false) and similar. Additionally private getFull() and getEmpty() member functions are added which return a full/empty range with the same bit width -- these are commonly needed inside ConstantRange.cpp. The IsFullSet argument in the ConstantRange(BitWidth, IsFullSet) constructor is now mandatory for the few usages that still make use of it. Differential Revision: https://reviews.llvm.org/D59716 llvm-svn: 356852
2019-02-05[NFC] fix trivial typos in commentsHiroshi Inoue1-1/+1
llvm-svn: 353147
2019-01-22[CVP] Use LVI to constant fold deopt operandsPhilip Reames1-1/+3
Deopt operands are generally intended to record information about a site in code with minimal perturbation of the surrounding code. Idiomatically, they also tend to appear down rare paths. Putting these together, we have an obvious case for extending CVP w/deopt operand constant folding. Arguably, we should be doing this for all operands on all instructions, but that's definitely a much larger and risky change. Differential Revision: https://reviews.llvm.org/D55678 llvm-svn: 351774
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2018-11-21[LVI] run transfer function for binary operator even when the RHS isn't a ↵John Regehr1-36/+39
constant LVI was symbolically executing binary operators only when the RHS was constant, missing the case where we have a ConstantRange for the RHS, but not an actual constant. Tested using check-all and by bootstrapping. Compile time is not impacted measurably. Differential Revision: https://reviews.llvm.org/D19859 llvm-svn: 347379
2018-07-30Remove trailing spaceFangrui Song1-1/+1
sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
2018-07-09llvm: Add support for "-fno-delete-null-pointer-checks"Manoj Gupta1-6/+8
Summary: Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers. More details : https://lkml.org/lkml/2018/4/4/601 GCC option description for -fdelete-null-pointer-checks: This Assume that programs cannot safely dereference null pointers, and that no code or data element resides at address zero. -fno-delete-null-pointer-checks is the inverse of this implying that null pointer dereferencing is not undefined. This feature is implemented in LLVM IR in this CL as the function attribute "null-pointer-is-valid"="true" in IR (Under review at D47894). The CL updates several passes that assumed null pointer dereferencing is undefined to not optimize when the "null-pointer-is-valid"="true" attribute is present. Reviewers: t.p.northover, efriedma, jyknight, chandlerc, rnk, srhines, void, george.burgess.iv Reviewed By: efriedma, george.burgess.iv Subscribers: eraman, haicheng, george.burgess.iv, drinkcat, theraven, reames, sanjoy, xbolva00, llvm-commits Differential Revision: https://reviews.llvm.org/D47895 llvm-svn: 336613
2018-05-14Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen1-26/+29
The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
2018-05-01Remove \brief commands from doxygen comments.Adrian Prantl1-2/+2
We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
2018-04-24[LVI] Fix typo. NFCXin Tong1-1/+1
llvm-svn: 330688
2018-03-13[LazyValueInfo] PR33357 prevent infinite recursion on BinaryOperatorBrian M. Rzycki1-3/+11
Summary: It is possible for LVI to encounter instructions that are not in valid SSA form and reference themselves. One example is the following: %tmp4 = and i1 %tmp4, undef Before this patch LVI would recurse until running out of stack memory and crashed. This patch marks these self-referential instructions as Overdefined and aborts analysis on the instruction. Fixes https://bugs.llvm.org/show_bug.cgi?id=33357 Reviewers: craig.topper, anna, efriedma, dberlin, sebpop, kuhar Reviewed by: dberlin Subscribers: uabelho, spatel, a.elovikov, fhahn, eli.friedman, mzolotukhin, spop, evandro, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34135 llvm-svn: 327432
2018-02-16[JumpThreading] PR36133 enable/disable DominatorTree for LVI analysisBrian M. Rzycki1-1/+29
Summary: The LazyValueInfo pass caches a copy of the DominatorTree when available. Whenever there are pending DominatorTree updates within JumpThreading's DeferredDominance object we cannot use the cached DT for LVI analysis. This commit adds the new methods enableDT() and disableDT() to LVI. JumpThreading also sets the appropriate usage model before calling LVI analysis methods. Fixes https://bugs.llvm.org/show_bug.cgi?id=36133 Reviewers: sebpop, dberlin, kuhar Reviewed by: sebpop, kuhar Subscribers: uabelho, llvm-commits, aprantl, hiraditya, a.elovikov Differential Revision: https://reviews.llvm.org/D42717 llvm-svn: 325356
2018-01-17[NFC] fix trivial typos in commentsHiroshi Inoue1-1/+1
"the the" -> "the" llvm-svn: 322636
2017-12-18[LVI] Support for ashr in LVIMax Kazantsev1-0/+1
Enhance LVI to analyze the ‘ashr’ binary operation. This leverages the infrastructure in ConstantRange for the ashr operation. Patch by Surya Kumari Jangala! Differential Revision: https://reviews.llvm.org/D40886 llvm-svn: 320983
2017-12-13Remove redundant includes from lib/Analysis.Michael Zolotukhin1-1/+0
llvm-svn: 320617
2017-09-28[LVI] Move LVILatticeVal class to separate header file (NFC).Florian Hahn1-347/+133
Summary: This allows sharing the lattice value code between LVI and SCCP (D36656). It also adds a `satisfiesPredicate` function, used by D36656. Reviewers: davide, sanjoy, efriedma Reviewed By: sanjoy Subscribers: mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D37591 llvm-svn: 314411
2017-09-09Merge isKnownNonNull into isKnownNonZeroNuno Lopes1-6/+6
It now knows the tricks of both functions. Also, fix a bug that considered allocas of non-zero address space to be always non null Differential Revision: https://reviews.llvm.org/D37628 llvm-svn: 312869
2017-08-10[LVI] Fix LVI compile time regression around constantFoldUser()Hiroshi Yamauchi1-14/+28
Summary: Avoid checking each operand and calling getValueFromCondition() before calling constantFoldUser() when the instruction type isn't supported by constantFoldUser(). This fixes a large compile time regression in an internal build. Reviewers: sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D36552 llvm-svn: 310545
2017-08-04[ConstantInt] Use ConstantInt::getValue instead of ↵Craig Topper1-3/+3
Constant::getUniqueInteger in a few places where we obviously have a ConstantInt. NFC getUniqueInteger will ultimately call ConstantInt::getValue, but calling ConstantInt::getValue should be inlined. llvm-svn: 310069
2017-08-03[LVI] Constant-propagate a zero extension of the switch condition value ↵Hiroshi Yamauchi1-6/+114
through case edges Summary: (This is a second attempt as https://reviews.llvm.org/D34822 was reverted.) LazyValueInfo currently computes the constant value of the switch condition through case edges, which allows the constant value to be propagated through the case edges. But we have seen a case where a zero-extended value of the switch condition is used past case edges for which the constant propagation doesn't occur. This patch adds a small logic to handle such a case in getEdgeValueLocal(). This is motivated by the Python 2.7 eval loop in PyEval_EvalFrameEx() where the lack of the constant propagation causes longer live ranges and more spill code than necessary. With this patch, we see that the code size of PyEval_EvalFrameEx() decreases by ~5.4% and a performance test improves by ~4.6%. Reviewers: sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D36247 llvm-svn: 309986
2017-08-01Revert r309415: "[LVI] Constant-propagate a zero extension of the switch ↵Daniel Jasper1-108/+4
condition value through case edges" This causes assertion failures in (a somewhat old version of) SpiderMonkey. I have already forwarded reproduction instructions to the patch author. llvm-svn: 309659
2017-07-28[LVI] Constant-propagate a zero extension of the switch condition value ↵Hiroshi Yamauchi1-4/+108
through case edges Summary: LazyValueInfo currently computes the constant value of the switch condition through case edges, which allows the constant value to be propagated through the case edges. But we have seen a case where a zero-extended value of the switch condition is used past case edges for which the constant propagation doesn't occur. This patch adds a small logic to handle such a case in getEdgeValueLocal(). This is motivated by the Python 2.7 eval loop in PyEval_EvalFrameEx() where the lack of the constant propagation causes longer live ranges and more spill code than necessary. With this patch, we see that the code size of PyEval_EvalFrameEx() decreases by ~5.4% and a performance test improves by ~4.6%. Reviewers: wmi, dberlin, sanjoy Reviewed By: sanjoy Subscribers: davide, davidxl, llvm-commits Differential Revision: https://reviews.llvm.org/D34822 llvm-svn: 309415
2017-06-23[JumpThreading] Teach jump threading how to analyze (and (cmp A, C1), (cmp ↵Craig Topper1-0/+20
A, C2)) after InstCombine has turned it into (cmp (add A, C3), C4) Currently JumpThreading can use LazyValueInfo to analyze an 'and' or 'or' of compare if the compare is fed by a livein of a basic block. This can be used to to prove the condition can't be met for some predecessor and the jump from that predecessor can be moved to the false path of the condition. But if the compare is something that InstCombine turns into an add and a single compare, it can't be analyzed because the livein is now an input to the add and not the compare. This patch adds a new method to LVI to get a ConstantRange on an edge. Then we teach jump threading to detect the add livein feeding a compare and to get the ConstantRange and propagate it. Differential Revision: https://reviews.llvm.org/D33262 llvm-svn: 306085
2017-06-23[LVI] Teach LVI to reason about ORs of icmps similar to how it reasons about ↵Craig Topper1-5/+5
ANDs of icmps Summary: LVI can reason about an AND of icmps on the true dest of a branch. I believe we can do similar for the false dest of ORs. This allows us to get the same answer for the demorganed versions of some of the AND test cases as you can see. Reviewers: anna, reames Reviewed By: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34431 llvm-svn: 306076
2017-06-09[LVI] Fix spelling error in comment. NFCCraig Topper1-1/+1
llvm-svn: 305115
2017-06-09[LVI] Const correct and rename the LVILatticeVal parameter to ↵Craig Topper1-9/+8
getPredicateResult. NFC Previously it was non-const reference named Result which would tend to make someone think that it was an outparam when really its an input. llvm-svn: 305114
2017-06-09[LazyValueInfo] Don't run the more complex predicate handling code for EQ ↵Craig Topper1-8/+8
and NE in getPredicateResult Summary: Unless I'm mistaken, the special handling for EQ/NE should cover everything and there is no reason to fallthrough to the more complex code. For that matter I'm not sure there's any reason to special case EQ/NE other than avoiding creating temporary ConstantRanges. This patch moves the complex code into an else so we only do it when we are handling a predicate other than EQ/NE. Reviewers: anna, reames, resistor, Farhana Reviewed By: anna Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34000 llvm-svn: 305086
2017-06-08[LazyValueInfo] Make LVILatticeVal intersect method take arguments by ↵Craig Topper1-1/+1
reference so we don't copy ConstantRanges unless we need to. llvm-svn: 304990
2017-06-07[LazyValueInfo] Remove redundant calls to ConstantRange::contains. The same ↵Craig Topper1-2/+2
exact call was made in the if above and we already know it returned true. NFC llvm-svn: 304857
2017-06-06[LVI Printer] Rely on the LVI analysis functions rather than the LVI cacheAnna Thomas1-64/+89
Summary: LVIPrinter pass was previously relying on the LVICache. We now directly call the the LVI functions which solves the value if the LVI information is not already available in the cache. This has 2 benefits over the printing of LVI cache: 1. higher coverage (i.e. catches errors) in LVI code when cache value is invalidated. 2. relies on the core functions, and not dependent on the LVI cache (which may be scrapped at some point). It would still catch any cache invalidation errors, since we first go through the cache. Reviewers: reames, dberlin, sanjoy Reviewed by: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32135 llvm-svn: 304819
2017-06-03[LazyValueInfo] Use Type::getIntegerBitWidth instead of casting to ↵Craig Topper1-2/+1
IntegerType to call getBitWidth. NFC llvm-svn: 304656
2017-06-03[LazyValueInfo] Make solveBlockValueCast take a CastInst* instead of ↵Craig Topper1-18/+18
Instruction*. Makes getOpcode return the appropriate enum without a cast. NFC llvm-svn: 304655
2017-06-02[LazyValueInfo] Fix formatting NFC.Craig Topper1-1/+1
llvm-svn: 304567
2017-06-02[LazyValueInfo] Make solveBlockValueBinaryOp take a BinaryOperator* instead ↵Craig Topper1-14/+14
of Instruction*. This removes a cast of getOpcode to BinaryOps. llvm-svn: 304563
2017-06-02[LazyValueInfo] Fix typo in comment. NFCCraig Topper1-1/+1
llvm-svn: 304560
2017-05-06[LazyValueInfo] Avoid unnecessary copies of ConstantRangesCraig Topper1-7/+7
Summary: ConstantRange contains two APInts which can allocate memory if their width is larger than 64-bits. So we shouldn't copy it when we can avoid it. This changes LVILatticeVal::getConstantRange() to return its internal ConstantRange by reference. This allows many places that just need a ConstantRange reference to avoid making a copy. Several places now capture the return value of getConstantRange() by reference so they can call methods on it that don't need a new object. Lastly it adds std::move in one place to capture to move a local ConstantRange into an LVILatticeVal. Reviewers: reames, dberlin, sanjoy, anna Reviewed By: reames Subscribers: grandinj, llvm-commits Differential Revision: https://reviews.llvm.org/D32884 llvm-svn: 302331
2017-04-28[LazyValueInfo] Fix typo in comment. NFCCraig Topper1-1/+1
llvm-svn: 301655
2017-04-12[IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth1-4/+4
and to expose a handle to represent the actual case rather than having the iterator return a reference to itself. All of this allows the iterator to be used with common STL facilities, standard algorithms, etc. Doing this exposed some missing facilities in the iterator facade that I've fixed and required some work to the actual iterator to fully support the necessary API. Differential Revision: https://reviews.llvm.org/D31548 llvm-svn: 300032
2017-03-23[LVIPrinterPass] Print LVI info for function argumentsAnna Thomas1-0/+12
Using AssemblyAnnotationWriter for LVI printer prints for instructions and basic blocks. So, we explicitly need to print LVI info for the arguments of the function (these are values and not instructions). llvm-svn: 298640
generated by cgit v1.1 at 2025-10-09 06:06:52 +0000