summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LazyValueInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Backport 4878aa36d4a [ValueLattice] Add new state for undef constants.Florian Hahn2020-05-181-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: NOTE: I mostly put it on Phabricator to make it easy for other people to fetch & check if that fixes a bug. This patch backports 4878aa36d4a and required earlier patches onto the release/10.x branch. It includes the following patches: aa5ebfdf205de6d599c1fed3161da3b63b6f0bef [ValueLattice] Make mark* functions public, return if value changed. c1943b42c5b7feff5d0e0c1358d02889e2be165f [ValueLattice] Update markConstantRange to return false equal ranges. e30c257811f62fea21704caa961c61e4559de202 [CVP,SCCP] Precommit test for D75055. 4878aa36d4aa27df644430139fab2734fde4a000 [ValueLattice] Add new state for undef constants. All patches except the last one apply cleanly. For the last one, the changes to SCCP.cpp were stripped, because SCCP does not yet use ValueLattice on release/10.x. Otherwise we would have to pull in more additional changes. Subscribers: tstellar, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D76596
* Temporarily revert "Reapply [LVI] Normalize pointer behavior" and "[LVI] ↵Jordan Rupprecht2019-12-201-134/+174
| | | | | | Restructure caching" This reverts commits 7e18aeba5062cd4324a9efb7bc25c9dbc4a34c2c (D70376) 21fbd5587cdfa11dabb3aeb0ead2d3d5fd0b490d (D69914) due to increased memory usage.
* Reapply [LVI] Normalize pointer behaviorNikita Popov2019-12-131-79/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a rebase of the change over D70376, which fixes an LVI cache invalidation issue that also affected this patch. ----- Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses. The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block. This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change). Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value. I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior. Differential Revision: https://reviews.llvm.org/D69914
* [LVI] Restructure cachingNikita Popov2019-12-041-96/+47
| | | | | | | | | | | | | | | Variant on D70103. The caching is switched to always use a BB to cache entry map, which then contains per-value caches. A separate set contains value handles with a deletion callback. This allows us to properly invalidate overdefined values. A possible alternative would be to always cache by value first and have per-BB maps/sets in the each cache entry. In that case we could use a ValueMap and would avoid the separate value handle set. I went with the BB indexing at the top level to make it easier to integrate D69914, but possibly that's not the right choice. Differential Revision: https://reviews.llvm.org/D70376
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* Temporarily Revert "Reapply [LVI] Normalize pointer behavior" as it's broken ↵Eric Christopher2019-11-121-97/+89
| | | | | | | | python 3.6. Reverting to figure out if it's a problem in python or the compiler for now. This reverts commit 885a05f48a5d320946c89590b73a764e5884fe4f.
* Reapply [LVI] Normalize pointer behaviorNikita Popov2019-11-081-89/+97
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fix cache invalidation by not guarding the dereferenced pointer cache erasure by SeenBlocks. SeenBlocks is only populated when actually caching a value in the block, which doesn't necessarily have to happen just because dereferenced pointers were calculated. ----- Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses. The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block. This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change). Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value. I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior. Differential Revision: https://reviews.llvm.org/D69914
* Revert "[LVI] Normalize pointer behavior"Nikita Popov2019-11-081-94/+89
| | | | | | | This reverts commit 15bc4dc9a8949f9cffd46ec647baf0818d28fb28. clang-cmake-x86_64-sde-avx512-linux buildbot reported quite a few compile-time regressions in test-suite, will investigate.
* [LVI] Normalize pointer behaviorNikita Popov2019-11-081-89/+94
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Related to D69686. As noted there, LVI currently behaves differently for integer and pointer values: For integers, the block value is always valid inside the basic block, while for pointers it is only valid at the end of the basic block. I believe the integer behavior is the correct one, and CVP relies on it via its getConstantRange() uses. The reason for the special pointer behavior is that LVI checks whether a pointer is dereferenced in a given basic block and marks it as non-null in that case. Of course, this information is valid only after the dereferencing instruction, or in conservative approximation, at the end of the block. This patch changes the treatment of dereferencability: Instead of including it inside the block value, we instead treat it as something similar to an assume (it essentially is a non-nullness assume) and incorporate this information in intersectAssumeOrGuardBlockValueConstantRange() if the context instruction is the terminator of the basic block. This happens either when determining an edge-value internally in LVI, or when a terminator was explicitly passed to getValueAt(). The latter case makes this change not fully NFC, because we can now fold terminator icmps based on the dereferencability information in the same block. This is the reason why I changed one JumpThreading test (it would optimize the condition away without the change). Of course, we do not want to recompute dereferencability on each intersectAssume call, so we need a new cache for this. The dereferencability analysis requires walking the entire basic block and computing underlying objects of all memory operands. This was previously done separately for each queried pointer value. In the new implementation (both because this makes the caching simpler, and because it is faster), I instead only walk the full BB once and cache all the dereferenced pointers. So the traversal is now performed only once per BB, instead of once per queried pointer value. I think the overall model now makes more sense than before, and there will be no more pitfalls due to differing integer/pointer behavior. Differential Revision: https://reviews.llvm.org/D69914
* Fix MSVC "switch statement contains 'default' but no 'case' labels" warning. ↵Simon Pilgrim2019-10-241-7/+4
| | | | NFCI.
* [LVI][NFC] Factor solveBlockValueSaturatingIntrinsic() out of ↵Roman Lebedev2019-10-231-11/+25
| | | | | | solveBlockValueIntrinsic() Now that there's SaturatingInst class, this is cleaner.
* [LVI][CVP] LazyValueInfoImpl::solveBlockValueBinaryOp(): use no-wrap flags ↵Roman Lebedev2019-10-231-2/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | from `add` op Summary: This was suggested in https://reviews.llvm.org/D69277#1717210 In this form (this is what was suggested, right?), the results aren't staggering (especially since given LVI cross-block focus) this does catch some things (as per test-suite), but not too much: | statistic | old | new | delta | % change | | correlated-value-propagation.NumAddNSW | 4981 | 4982 | 1 | 0.0201% | | correlated-value-propagation.NumAddNW | 12125 | 12126 | 1 | 0.0082% | | correlated-value-propagation.NumCmps | 1199 | 1202 | 3 | 0.2502% | | correlated-value-propagation.NumDeadCases | 112 | 111 | -1 | -0.8929% | | correlated-value-propagation.NumMulNSW | 275 | 278 | 3 | 1.0909% | | correlated-value-propagation.NumMulNUW | 1323 | 1326 | 3 | 0.2268% | | correlated-value-propagation.NumMulNW | 1598 | 1604 | 6 | 0.3755% | | correlated-value-propagation.NumNSW | 7158 | 7167 | 9 | 0.1257% | | correlated-value-propagation.NumNUW | 13304 | 13310 | 6 | 0.0451% | | correlated-value-propagation.NumNW | 20462 | 20477 | 15 | 0.0733% | | correlated-value-propagation.NumOverflows | 4 | 7 | 3 | 75.0000% | | correlated-value-propagation.NumPhis | 15366 | 15381 | 15 | 0.0976% | | correlated-value-propagation.NumSExt | 6273 | 6277 | 4 | 0.0638% | | correlated-value-propagation.NumShlNSW | 1172 | 1171 | -1 | -0.0853% | | correlated-value-propagation.NumShlNUW | 2793 | 2794 | 1 | 0.0358% | | correlated-value-propagation.NumSubNSW | 730 | 736 | 6 | 0.8219% | | correlated-value-propagation.NumSubNUW | 2044 | 2046 | 2 | 0.0978% | | correlated-value-propagation.NumSubNW | 2774 | 2782 | 8 | 0.2884% | | instcount.NumAddInst | 277586 | 277569 | -17 | -0.0061% | | instcount.NumAndInst | 66056 | 66054 | -2 | -0.0030% | | instcount.NumBrInst | 709147 | 709146 | -1 | -0.0001% | | instcount.NumCallInst | 528579 | 528576 | -3 | -0.0006% | | instcount.NumExtractValueInst | 18307 | 18301 | -6 | -0.0328% | | instcount.NumOrInst | 102660 | 102665 | 5 | 0.0049% | | instcount.NumPHIInst | 318008 | 318007 | -1 | -0.0003% | | instcount.NumSelectInst | 46373 | 46370 | -3 | -0.0065% | | instcount.NumSExtInst | 79496 | 79488 | -8 | -0.0101% | | instcount.NumShlInst | 40654 | 40657 | 3 | 0.0074% | | instcount.NumTruncInst | 62251 | 62249 | -2 | -0.0032% | | instcount.NumZExtInst | 68211 | 68221 | 10 | 0.0147% | | instcount.TotalBlocks | 843910 | 843909 | -1 | -0.0001% | | instcount.TotalInsts | 7387448 | 7387423 | -25 | -0.0003% | Reviewers: nikic, reames Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69321
* [LVI] Look through extractvalue of insertvalueNikita Popov2019-09-071-0/+15
| | | | | | | | | | | | | | | | | | | | | | | | | This addresses the issue mentioned on D19867. When we simplify with.overflow instructions in CVP, we leave behind extractvalue of insertvalue sequences that LVI no longer understands. This means that we can not simplify any instructions based on the with.overflow anymore (until some over pass like InstCombine cleans them up). This patch extends LVI extractvalue handling by calling SimplifyExtractValueInst (which doesn't do anything more than constant folding + looking through insertvalue) and using the block value of the simplification. A possible alternative would be to do something similar to SimplifyIndVars, where we instead directly try to replace extractvalue users of the with.overflow. This would need some additional structural changes to CVP, as it's currently not legal to remove anything but the current instruction -- we'd have to introduce a worklist with instructions scheduled for deletion or similar. Differential Revision: https://reviews.llvm.org/D67035 llvm-svn: 371306
* Change TargetLibraryInfo analysis passes to always require FunctionTeresa Johnson2019-09-071-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first change to enable the TLI to be built per-function so that -fno-builtin* handling can be migrated to use function attributes. See discussion on D61634 for background. This is an enabler for fixing handling of these options for LTO, for example. This change should not affect behavior, as the provided function is not yet used to build a specifically per-function TLI, but rather enables that migration. Most of the changes were very mechanical, e.g. passing a Function to the legacy analysis pass's getTLI interface, or in Module level cases, adding a callback. This is similar to the way the per-function TTI analysis works. There was one place where we were looking for builtins but not in the context of a specific function. See FindCXAAtExit in lib/Transforms/IPO/GlobalOpt.cpp. I'm somewhat concerned my workaround could provide the wrong behavior in some corner cases. Suggestions welcome. Reviewers: chandlerc, hfinkel Subscribers: arsenm, dschuff, jvesely, nhaehnle, mehdi_amini, javed.absar, sbc100, jgravelle-google, eraman, aheejin, steven_wu, george.burgess.iv, dexonsmith, jfb, asbirlea, gchatelet, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66428 llvm-svn: 371284
* [LVI] Extract solveBlockValueExtractValue(); NFCNikita Popov2019-08-311-3/+15
| | | | | | | Extract this method in preparation for additional extractvalue support. llvm-svn: 370575
* [llvm] Migrate llvm::make_unique to std::make_uniqueJonas Devlieghere2019-08-151-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
* Introduce Value::stripPointerCastsSameRepresentationJohannes Doerfert2019-06-041-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
* [LVI][CVP] Add support for urem, srem and sdivNikita Popov2019-06-041-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
* [LVI][CVP] Add support for saturating add/subNikita Popov2019-05-251-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
* [LVI][CVP] Calculate with.overflow result rangeNikita Popov2019-05-251-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
* [LVI] Extract helper for binary range calculations; NFCNikita Popov2019-05-251-23/+28
| | | | llvm-svn: 361692
* [LVI][CVP] Add support for abs/nabs select pattern flavorNikita Popov2019-05-141-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
* [ConstantRange] Add makeExactNoWrapRegion()Nikita Popov2019-04-281-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
* Revert "[ConstantRange] Rename make{Guaranteed -> Exact}NoWrapRegion() NFC"Nikita Popov2019-04-221-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
* [ConstantRange] Rename make{Guaranteed -> Exact}NoWrapRegion() NFCNikita Popov2019-04-221-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
* [LVI][CVP] Constrain values in with.overflow branchesNikita Popov2019-04-171-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
* [ConstantRange] Add getFull() + getEmpty() named constructors; NFCNikita Popov2019-03-241-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
* [NFC] fix trivial typos in commentsHiroshi Inoue2019-02-051-1/+1
| | | | llvm-svn: 353147
* [CVP] Use LVI to constant fold deopt operandsPhilip Reames2019-01-221-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
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-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
* [LVI] run transfer function for binary operator even when the RHS isn't a ↵John Regehr2018-11-211-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
* Remove trailing spaceFangrui Song2018-07-301-1/+1
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* llvm: Add support for "-fno-delete-null-pointer-checks"Manoj Gupta2018-07-091-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
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-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
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-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
* [LVI] Fix typo. NFCXin Tong2018-04-241-1/+1
| | | | llvm-svn: 330688
* [LazyValueInfo] PR33357 prevent infinite recursion on BinaryOperatorBrian M. Rzycki2018-03-131-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
* [JumpThreading] PR36133 enable/disable DominatorTree for LVI analysisBrian M. Rzycki2018-02-161-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
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-01-171-1/+1
| | | | | | "the the" -> "the" llvm-svn: 322636
* [LVI] Support for ashr in LVIMax Kazantsev2017-12-181-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
* Remove redundant includes from lib/Analysis.Michael Zolotukhin2017-12-131-1/+0
| | | | llvm-svn: 320617
* [LVI] Move LVILatticeVal class to separate header file (NFC).Florian Hahn2017-09-281-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
* Merge isKnownNonNull into isKnownNonZeroNuno Lopes2017-09-091-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
* [LVI] Fix LVI compile time regression around constantFoldUser()Hiroshi Yamauchi2017-08-101-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
* [ConstantInt] Use ConstantInt::getValue instead of ↵Craig Topper2017-08-041-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
* [LVI] Constant-propagate a zero extension of the switch condition value ↵Hiroshi Yamauchi2017-08-031-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
* Revert r309415: "[LVI] Constant-propagate a zero extension of the switch ↵Daniel Jasper2017-08-011-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
* [LVI] Constant-propagate a zero extension of the switch condition value ↵Hiroshi Yamauchi2017-07-281-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
* [JumpThreading] Teach jump threading how to analyze (and (cmp A, C1), (cmp ↵Craig Topper2017-06-231-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
* [LVI] Teach LVI to reason about ORs of icmps similar to how it reasons about ↵Craig Topper2017-06-231-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
OpenPOWER on IntegriCloud