summaryrefslogtreecommitdiff
path: root/contrib/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Move all sources from the llvm project into contrib/llvm-project.Dimitry Andric2019-12-2098-81110/+0
| | | | | | | | | | | | | This uses the new layout of the upstream repository, which was recently migrated to GitHub, and converted into a "monorepo". That is, most of the earlier separate sub-projects with their own branches and tags were consolidated into one top-level directory, and are now branched and tagged together. Updating the vendor area to match this layout is next. Notes: svn path=/head/; revision=355940
* Merge llvm, clang, compiler-rt, libc++, libunwind, lld, lldb, and openmpDimitry Andric2019-09-021-12/+18
| | | | | | | release_90 branch r370514, and update version numbers. Notes: svn path=/projects/clang900-import/; revision=351722
* Merge llvm trunk r366426, resolve conflicts, and update FREEBSD-Xlist.Dimitry Andric2019-08-2199-3505/+5765
| | | | Notes: svn path=/projects/clang900-import/; revision=351344
* Pull in r360968 from upstream llvm trunk (by Philip Reames):Dimitry Andric2019-07-011-2/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Clarify comments on helpers used by LFTR [NFC] I'm slowly wrapping my head around this code, and am making comment improvements where I can. Pull in r360972 from upstream llvm trunk (by Philip Reames): [LFTR] Factor out a helper function for readability purpose [NFC] Pull in r360976 from upstream llvm trunk (by Philip Reames): [IndVars] Don't reimplement Loop::isLoopInvariant [NFC] Using dominance vs a set membership check is indistinguishable from a compile time perspective, and the two queries return equivelent results. Simplify code by using the existing function. Pull in r360978 from upstream llvm trunk (by Philip Reames): [LFTR] Strengthen assertions in genLoopLimit [NFCI] Pull in r362292 from upstream llvm trunk (by Nikita Popov): [IndVarSimplify] Fixup nowrap flags during LFTR (PR31181) Fix for https://bugs.llvm.org/show_bug.cgi?id=31181 and partial fix for LFTR poison handling issues in general. When LFTR moves a condition from pre-inc to post-inc, it may now depend on value that is poison due to nowrap flags. To avoid this, we clear any nowrap flag that SCEV cannot prove for the post-inc addrec. Additionally, LFTR may switch to a different IV that is dynamically dead and as such may be arbitrarily poison. This patch will correct nowrap flags in some but not all cases where this happens. This is related to the adoption of IR nowrap flags for the pre-inc addrec. (See some of the switch_to_different_iv tests, where flags are not dropped or insufficiently dropped.) Finally, there are likely similar issues with the handling of GEP inbounds, but we don't have a test case for this yet. Differential Revision: https://reviews.llvm.org/D60935 Pull in r362971 from upstream llvm trunk (by Philip Reames): Prepare for multi-exit LFTR [NFC] This change does the plumbing to wire an ExitingBB parameter through the LFTR implementation, and reorganizes the code to work in terms of a set of individual loop exits. Most of it is fairly obvious, but there's one key complexity which makes it worthy of consideration. The actual multi-exit LFTR patch is in D62625 for context. Specifically, it turns out the existing code uses the backedge taken count from before a IV is widened. Oddly, we can end up with a different (more expensive, but semantically equivelent) BE count for the loop when requerying after widening. For the nestedIV example from elim-extend, we end up with the following BE counts: BEFORE: (-2 + (-1 * %innercount) + %limit) AFTER: (-1 + (sext i32 (-1 + %limit) to i64) + (-1 * (sext i32 %innercount to i64))<nsw>) This is the only test in tree which seems sensitive to this difference. The actual result of using the wider BETC on this example is that we actually produce slightly better code. :) In review, we decided to accept that test change. This patch is structured to preserve the old behavior, but a separate change will immediate follow with the behavior change. (I wanted it separate for problem attribution purposes.) Differential Revision: https://reviews.llvm.org/D62880 Pull in r362975 from upstream llvm trunk (by Philip Reames): [LFTR] Use recomputed BE count This was discussed as part of D62880. The basic thought is that computing BE taken count after widening should produce (on average) an equally good backedge taken count as the one before widening. Since there's only one test in the suite which is impacted by this change, and it's essentially equivelent codegen, that seems to be a reasonable assertion. This change was separated from r362971 so that if this turns out to be problematic, the triggering piece is obvious and easily revertable. For the nestedIV example from elim-extend.ll, we end up with the following BE counts: BEFORE: (-2 + (-1 * %innercount) + %limit) AFTER: (-1 + (sext i32 (-1 + %limit) to i64) + (-1 * (sext i32 %innercount to i64))<nsw>) Note that before is an i32 type, and the after is an i64. Truncating the i64 produces the i32. Pull in r362980 from upstream llvm trunk (by Philip Reames): Factor out a helper function for readability and reuse in a future patch [NFC] Pull in r363613 from upstream llvm trunk (by Philip Reames): Fix a bug w/inbounds invalidation in LFTR (recommit) Recommit r363289 with a bug fix for crash identified in pr42279. Issue was that a loop exit test does not have to be an icmp, leading to a null dereference crash when new logic was exercised for that case. Test case previously committed in r363601. Original commit comment follows: This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV. The basic scheme used is to prove that using the given IV (pre or post increment forms) would have to already trigger UB on the path to the test we're modifying. As such, our potential UB triggering use does not change the semantics of the original program. As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well. (Note: I'm going to address Nikita's last style comment in a separate commit just to minimize chance of subtle bugs being introduced due to typos.) Differential Revision: https://reviews.llvm.org/D62939 Pull in r363875 from upstream llvm trunk (by Philip Reames): [LFTR] Rename variable to minimize confusion [NFC] (Recommit of r363293 which was reverted when a dependent patch was.) As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to refer to the backedge taken count of the loop. A conditional backedge taken count - one which only applies if a particular exit is taken - is called a ExitCount in SCEV code, so be consistent here. Pull in r363877 from upstream llvm trunk (by Philip Reames): [LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC] (Resumbit of r363292 which was reverted along w/an earlier patch) Pull in r364346 from upstream llvm trunk (by Philip Reames): [LFTR] Adjust debug output to include extensions (if any) Pull in r364693 from upstream llvm trunk (by Philip Reames): [IndVars] Remove a bit of manual constant folding [NFC] SCEV is more than capable of folding (add x, trunc(0)) to x. Pull in r364709 from upstream llvm trunk (by Nikita Popov): [LFTR] Fix post-inc pointer IV with truncated exit count (PR41998) Fixes https://bugs.llvm.org/show_bug.cgi?id=41998. Usually when we have a truncated exit count we'll truncate the IV when comparing against the limit, in which case exit count overflow in post-inc form doesn't matter. However, for pointer IVs we don't do that, so we have to be careful about incrementing the IV in the wide type. I'm fixing this by removing the IVCount variable (which was ExitCount or ExitCount+1) and replacing it with a UsePostInc flag, and then moving the actual limit adjustment to the individual cases (which are: pointer IV where we add to the wide type, integer IV where we add to the narrow type, and constant integer IV where we add to the wide type). Differential Revision: https://reviews.llvm.org/D63686 Together, these should fix a hang when building the textproc/htmldoc port, due to an incorrect loop optimization. PR: 237515 MFC after: 1 week Notes: svn path=/head/; revision=349583
* Merge llvm, clang, compiler-rt, libc++, lld, and lldb release_80 branchDimitry Andric2019-02-151-74/+94
| | | | | | | r354130, resolve conflicts, and bump version numbers. Notes: svn path=/projects/clang800-import/; revision=344177
* Merge llvm trunk r351319, resolve conflicts, and update FREEBSD-Xlist.Dimitry Andric2019-01-2066-1984/+7635
| | | | Notes: svn path=/projects/clang800-import/; revision=343210
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ release_70 branchDimitry Andric2018-12-091-1/+0
| | | | | | | | | | r348686 (effectively 7.0.1 rc3), resolve conflicts, and bump version numbers. PR: 230240, 230355 Notes: svn path=/projects/clang700-import/; revision=341763
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ release_70 branchDimitry Andric2018-11-041-3/+16
| | | | | | | | | | r346007 (effectively 7.0.1 rc2), resolve conflicts, and bump version numbers. PR: 230240, 230355 Notes: svn path=/projects/clang700-import/; revision=340125
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ release_70 branchDimitry Andric2018-08-183-11/+17
| | | | | | | | | r339999, resolve conflicts, and bump version numbers. PR: 230240,230355 Notes: svn path=/projects/clang700-import/; revision=338014
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ release_70 branchDimitry Andric2018-08-112-4/+41
| | | | | | | r339355, resolve conflicts, and bump version numbers. Notes: svn path=/projects/clang700-import/; revision=337645
* Merge llvm trunk r338150 (just before the 7.0.0 branch point), andDimitry Andric2018-08-0216-280/+390
| | | | | | | resolve conflicts. Notes: svn path=/projects/clang700-import/; revision=337149
* Merge llvm trunk r338150, and resolve conflicts.Dimitry Andric2018-07-3067-2440/+4914
| | | | Notes: svn path=/projects/clang700-import/; revision=336916
* Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ toDimitry Andric2018-06-292-9/+22
| | | | | | | | | | 6.0.1 release (upstream r335540). Relnotes: yes MFC after: 2 weeks Notes: svn path=/head/; revision=335799
* Pull in r327638 from upstream llvm trunk (by Matthew Simpson):Dimitry Andric2018-03-161-2/+2
| | | | | | | | | | | | | | | | | | | | [ConstantFolding, InstSimplify] Handle more vector GEPs This patch addresses some additional cases where the compiler crashes upon encountering vector GEPs. This should fix PR36116. Differential Revision: https://reviews.llvm.org/D44219 Reference: https://bugs.llvm.org/show_bug.cgi?id=36116 This fixes an assertion when building the emulators/snes9x port. Reported by: jbeich PR: 225471 MFC after: 3 months X-MFC-With: r327952 Notes: svn path=/head/; revision=331065
* Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ toDimitry Andric2018-02-251-0/+7
| | | | | | | | | | | 6.0.0 (branches/release_60 r325932). This corresponds to 6.0.0 rc3. MFC after: 3 months X-MFC-With: r327952 PR: 224669 Notes: svn path=/head/; revision=329983
* Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ toDimitry Andric2018-02-011-11/+18
| | | | | | | | | | | 6.0.0 (branches/release_60 r323948). MFC after: 3 months X-MFC-With: r327952 PR: 224669 Notes: svn path=/head/; revision=328753
* Pull in r322016 from upstream llvm trunk (by Sanjay Patel):Dimitry Andric2018-01-181-1/+1
| | | | | | | | | | | | | | | | | | [ValueTracking] remove overzealous assert The test is derived from a failing fuzz test: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=5008 Credit to @rksimon for pointing out the problem. This should fix "Bad flavor while matching min/max" errors when building the graphics/libsixel and science/kst2 ports. Reported by: jbeich PR: 225268, 225269 Notes: svn path=/head/; revision=328145
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ release_60 r321788,Dimitry Andric2018-01-064-53/+146
| | | | | | | update build glue and version numbers. Notes: svn path=/projects/clang600-import/; revision=327657
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ trunk r321545,Dimitry Andric2017-12-299-35/+102
| | | | | | | | update build glue and version numbers, add new intrinsics headers, and update OptionalObsoleteFiles.inc. Notes: svn path=/projects/clang600-import/; revision=327330
* Merge llvm trunk r321414 to contrib/llvm.Dimitry Andric2017-12-2414-219/+297
| | | | Notes: svn path=/projects/clang600-import/; revision=327134
* Merge llvm trunk r321017 to contrib/llvm.Dimitry Andric2017-12-2062-3644/+5226
| | | | Notes: svn path=/projects/clang600-import/; revision=327023
* Upgrade our copies of clang, llvm, lldb and compiler-rt to r312293 fromDimitry Andric2017-09-011-2/+0
| | | | | | | | | | | | | | the upstream release_50 branch. This corresponds to 5.0.0 rc4. As of this version, the cad/stepcode port should now compile in a more reasonable time on i386 (see bug 221836 for more information). PR: 221836 MFC after: 2 months X-MFC-with: r321369 Notes: svn path=/head/; revision=323112
* Upgrade our copies of clang, llvm, lld and libc++ to r311219 from theDimitry Andric2017-08-212-0/+34
| | | | | | | | | | upstream release_50 branch. MFC after: 2 months X-MFC-with: r321369 Notes: svn path=/head/; revision=322740
* Upgrade our copies of clang, llvm and libc++ to r310316 from theDimitry Andric2017-08-091-0/+63
| | | | | | | | | | upstream release_50 branch. MFC after: 2 months X-MFC-with: r321369 Notes: svn path=/head/; revision=322320
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r308421, and updateDimitry Andric2017-07-1911-52/+441
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=321238
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r307894, and updateDimitry Andric2017-07-1316-115/+307
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=320970
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r306956, and updateDimitry Andric2017-07-0210-212/+206
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=320572
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r306325, and updateDimitry Andric2017-06-2714-121/+176
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=320397
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r305575, and updateDimitry Andric2017-06-177-65/+107
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=320041
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r305145, and updateDimitry Andric2017-06-1029-204/+287
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=319799
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r304659, and updateDimitry Andric2017-06-037-119/+121
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=319547
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r304460, and updateDimitry Andric2017-06-018-6/+33
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=319479
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r304222, and updateDimitry Andric2017-05-301-4/+3
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=319250
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r304149, and updateDimitry Andric2017-05-298-117/+177
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=319164
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r303571, and updateDimitry Andric2017-05-228-124/+222
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=318681
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r303291, and updateDimitry Andric2017-05-185-54/+84
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=318477
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r303197, and updateDimitry Andric2017-05-1615-323/+569
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=318384
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r302418, and updateDimitry Andric2017-05-088-282/+360
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=317969
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r302069, and updateDimitry Andric2017-05-0314-556/+352
| | | | | | | build glue (preliminary, not all option combinations work yet). Notes: svn path=/projects/clang500-import/; revision=317778
* Merge llvm, clang, lld, lldb, compiler-rt and libc++ r301441, and updateDimitry Andric2017-04-2612-828/+1008
| | | | | | | build glue. Notes: svn path=/projects/clang500-import/; revision=317472
* Merge llvm, clang, lld and lldb trunk r300890, and update build glue.Dimitry Andric2017-04-208-210/+389
| | | | Notes: svn path=/projects/clang500-import/; revision=317230
* Merge llvm trunk r300422 and resolve conflicts.Dimitry Andric2017-04-1648-2677/+6212
| | | | Notes: svn path=/projects/clang500-import/; revision=317029
* Reapply r287232 from upstream llvm trunk (by Daniil Fukalov):Dimitry Andric2017-03-061-17/+49
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | [SCEV] limit recursion depth of CompareSCEVComplexity Summary: CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time. Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter. Reviewers: sanjoy Subscribers: mzolotukhin, tstellarAMD, llvm-commits Differential Revision: https://reviews.llvm.org/D26389 Pull in r296992 from upstream llvm trunk (by Sanjoy Das): [SCEV] Decrease the recursion threshold for CompareValueComplexity Fixes PR32142. r287232 accidentally increased the recursion threshold for CompareValueComplexity from 2 to 32. This change reverses that change by introducing a separate flag for CompareValueComplexity's threshold. The latter revision fixes the excessive compile times for skein_block.c. Notes: svn path=/head/; revision=314795
* For now, revert r287232 from upstream llvm trunk (by Daniil Fukalov):Dimitry Andric2017-03-051-44/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | [SCEV] limit recursion depth of CompareSCEVComplexity Summary: CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time. Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter. Reviewers: sanjoy Subscribers: mzolotukhin, tstellarAMD, llvm-commits Differential Revision: https://reviews.llvm.org/D26389 This commit is the cause of excessive compile times on skein_block.c (and possibly other files) during kernel builds on amd64. We never saw the problematic behavior described in this upstream commit, so for now it is better to revert it. An upstream bug has been filed here: https://bugs.llvm.org/show_bug.cgi?id=32142 Reported by: mjg Notes: svn path=/head/; revision=314708
* Pull in r293773 from upstream llvm trunk (by Sanjay Patel):Dimitry Andric2017-02-021-0/+17
| | | | | | | | | | | | | | | | | | | | | | [ValueTracking] avoid crashing from bad assumptions (PR31809) A program may contain llvm.assume info that disagrees with other analysis. This may be caused by UB in the program, so we must not crash because of that. As noted in the code comments: https://llvm.org/bugs/show_bug.cgi?id=31809 ...we can do better, but this at least avoids the assert/crash in the bug report. Differential Revision: https://reviews.llvm.org/D29395 This fixes an assertion when building editors/emacs-devel. PR: 216614 Notes: svn path=/projects/clang400-import/; revision=313110
* Merge llvm, clang, compiler-rt, libc++, lld and lldb release_40 branchDimitry Andric2017-01-291-5/+5
| | | | | | | r293443, and update build glue. Notes: svn path=/projects/clang400-import/; revision=312967
* Merge llvm, clang, lld and lldb release_40 branch 292732, and updateDimitry Andric2017-01-221-0/+1
| | | | | | | build glue. Notes: svn path=/projects/clang400-import/; revision=312639
* Pull in r292133 from upstream llvm trunk (by Hal Finkel):Dimitry Andric2017-01-161-10/+17
| | | | | | | | | | | | | | | | | | | | | | Fix use-after-free bug in AffectedValueCallbackVH::allUsesReplacedWith When transferring affected values in the cache from an old value, identified by the value of the current callback, to the specified new value we might need to insert a new entry into the DenseMap which constitutes the cache. Doing so might delete the current callback object. Move the copying logic into a new function, a member of the assumption cache itself, so that we don't run into UB should the callback handle itself be removed mid-copy. Differential Revision: https://reviews.llvm.org/D28749 This should fix crashes when building lld (as part of the llvmXY ports). Reported by: jbeich PR: 216117 Notes: svn path=/projects/clang400-import/; revision=312308
* Merge llvm, clang, lld and lldb release_40 branch r292009. Also updateDimitry Andric2017-01-1415-223/+506
| | | | | | | build glue. Notes: svn path=/projects/clang400-import/; revision=312197
* Merge llvm, clang, lld and lldb trunk r291476.Dimitry Andric2017-01-095-29/+52
| | | | Notes: svn path=/projects/clang400-import/; revision=311833
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-27 06:53:15 +0000