summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [cleanup] Remove trailing whitespace before I start changing this file.Chandler Carruth2013-12-121-1/+1
| | | | llvm-svn: 197149
* Don't #include heavy Dominators.h file in LoopInfo.h. This change reducesJakub Staszak2013-12-071-0/+1
| | | | | | overall time of LLVM compilation by ~1%. llvm-svn: 196667
* Correct word hyphenationsAlp Toker2013-12-052-2/+2
| | | | | | | This patch tries to avoid unrelated changes other than fixing a few hyphen-related ambiguities and contractions in nearby lines. llvm-svn: 196471
* Fix typo.Eric Christopher2013-12-041-1/+1
| | | | llvm-svn: 196434
* [PM] Split the CallGraph out from the ModulePass which creates theChandler Carruth2013-11-265-81/+116
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CallGraph. This makes the CallGraph a totally generic analysis object that is the container for the graph data structure and the primary interface for querying and manipulating it. The pass logic is separated into its own class. For compatibility reasons, the pass provides wrapper methods for most of the methods on CallGraph -- they all just forward. This will allow the new pass manager infrastructure to provide its own analysis pass that constructs the same CallGraph object and makes it available. The idea is that in the new pass manager, the analysis pass's 'run' method returns a concrete analysis 'result'. Here, that result is a 'CallGraph'. The 'run' method will typically do only minimal work, deferring much of the work into the implementation of the result object in order to be lazy about computing things, but when (like DomTree) there is *some* up-front computation, the analysis does it prior to handing the result back to the querying pass. I know some of this is fairly ugly. I'm happy to change it around if folks can suggest a cleaner interim state, but there is going to be some amount of unavoidable ugliness during the transition period. The good thing is that this is very limited and will naturally go away when the old pass infrastructure goes away. It won't hang around to bother us later. Next up is the initial new-PM-style call graph analysis. =] llvm-svn: 195722
* [PM] Reformat some code with clang-format as I'm going to be editting asChandler Carruth2013-11-261-21/+12
| | | | | | | part of generalizing the call graph infrastructure for the new pass manager. llvm-svn: 195718
* [PM] Rename the 'Mod' member to the more idiomatic 'M'. No functionalityChandler Carruth2013-11-261-3/+3
| | | | | | changed. llvm-svn: 195701
* Don't speculate loads under ThreadSanitizerKostya Serebryany2013-11-211-1/+3
| | | | | | | | | | | | | | | | | Summary: Don't speculate loads under ThreadSanitizer. This fixes https://code.google.com/p/thread-sanitizer/issues/detail?id=40 Also discussed here: http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-November/067929.html Reviewers: chandlerc Reviewed By: chandlerc CC: llvm-commits, dvyukov Differential Revision: http://llvm-reviews.chandlerc.com/D2227 llvm-svn: 195324
* The 'optnone' attribute means don't inline anything into this functionPaul Robinson2013-11-181-0/+4
| | | | | | | | | | (except functions marked always_inline). Functions with 'optnone' must also have 'noinline' so they don't get inlined into any other function. Based on work by Andrea Di Biagio. llvm-svn: 195046
* Annotate APInt methods where it's not clear whether they are in place with ↵Benjamin Kramer2013-11-161-6/+6
| | | | | | | | warn_unused_result. Fix ScalarEvolution bugs uncovered by this. llvm-svn: 194928
* Use correct size for address space in BasicAA.Matt Arsenault2013-11-161-2/+3
| | | | | | | | | | | | The tests just hit this with a different sized address space since I haven't figured out how to use this to break it. I thought I committed this a long time ago, and I'm not sure why missing this hasn't caused any problems. llvm-svn: 194903
* Add addrspacecast instruction.Matt Arsenault2013-11-151-5/+7
| | | | | | Patch by Michele Scandale! llvm-svn: 194760
* Added BlockFrequencyInfo::view for displaying the block frequency ↵Michael Gottesman2013-11-141-0/+103
| | | | | | | | | | propagation graph via graphviz. This is useful for debugging issues in the BlockFrequency implementation since one can easily visualize where probability mass and other errors occur in the propagation. llvm-svn: 194654
* Fixing a heisenbug where the memory dependence analysis behaves differentlyYunzhong Gao2013-11-141-5/+6
| | | | | | | | | | | | with and without -g. Adding a test case to make sure that the threshold used in the memory dependence analysis is respected. The test case also checks that debug intrinsics are not counted towards this threshold. Differential Revision: http://llvm-reviews.chandlerc.com/D2141 llvm-svn: 194646
* Fixed 80+ violations.Michael Gottesman2013-11-141-5/+5
| | | | llvm-svn: 194634
* add more comments around the delinearization of arraysSebastian Pop2013-11-133-17/+88
| | | | llvm-svn: 194612
* Simplify code. No functionality change.Jakub Staszak2013-11-131-8/+8
| | | | llvm-svn: 194602
* Move Delinearization pass into an anonymous namespace.Benjamin Kramer2013-11-131-0/+4
| | | | llvm-svn: 194582
* delinearization of arraysSebastian Pop2013-11-125-0/+653
| | | | llvm-svn: 194527
* Change data structure to memorize computed result in ScalarEvolutionWan Xiaofei2013-11-121-22/+42
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Replace std::map with SmallVector to memorize the cached result since SCEV usually belongs to little Loop/BB Linear scan on SmallVector is faster than std::map. Code reviewer : Andrew Trick. Test result : Pass Unit Test & LLVM Test Suite 401.bzip2 0.425721 0.419981 101.37% 403.gcc 24.53855 24.2667 101.12% 429.mcf 0.060847 0.059944 101.51% 433.milc 0.646009 0.636119 101.55% 444.namd 1.383928 1.370614 100.97% 445.gobmk 5.836575 5.800225 100.63% 450.soplex 1.911257 1.895963 100.81% 456.hmmer 1.039565 1.032534 100.68% 458.sjeng 0.897401 0.885567 101.34% 464.h264ref 3.645908 3.577991 101.90% 470.lbm 0.049456 0.048398 102.19% 471.omnetpp 5.638575 5.60435 100.61% bitmnp01 0.045738 0.045291 100.99% cjpegv2data 0.304359 0.302833 100.50% idctrn01 0.046433 0.045763 101.46% quake2 4.534416 4.4952 100.87% quake 2.688566 2.659208 101.10% xcsoar 12.42545 12.30385 100.99% linpack 0.038739 0.03803 101.86% matrix01 0.053564 0.0528 101.45% nbench 0.402867 0.395803 101.78% tblook01 0.021265 0.021015 101.19% ttsprk01 0.066384 0.065566 101.25% llvm-svn: 194459
* Use size function instead of manually calculating it.Matt Arsenault2013-11-101-1/+1
| | | | llvm-svn: 194345
* Move the old pass manager infrastructure into a legacy namespace andChandler Carruth2013-11-091-1/+1
| | | | | | | | | | | | | | | | | | | give the files a legacy prefix in the right directory. Use forwarding headers in the old locations to paper over the name change for most clients during the transitional period. No functionality changed here! This is just clearing some space to reduce renaming churn later on with a new system. Even when the new stuff starts to go in, it is going to be hidden behind a flag and off-by-default as it is still WIP and under development. This patch is specifically designed so that very little out-of-tree code has to change. I'm going to work as hard as I can to keep that the case. Only direct forward declarations of the PassManager class are impacted by this change. llvm-svn: 194324
* Rewrite SCEV's backedge taken count computation.Andrew Trick2013-11-061-163/+207
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Patch by Michele Scandale! Rewrite of the functions used to compute the backedge taken count of a loop on LT and GT comparisons. I decided to split the handling of LT and GT cases becasue the trick "a > b == -a < -b" in some cases prevents the trip count computation due to the multiplication by -1 on the two operands of the comparison. This issue comes from the conservative computation of value range of SCEVs: taking the negative SCEV of an expression that have a small positive range (e.g. [0,31]), we would have a SCEV with a fullset as value range. Indeed, in the new rewritten function I tried to better handle the maximum backedge taken count computation when MAX/MIN expression are used to handle the cases where no entry guard is found. Some test have been modified in order to check the new value correctly (I manually check them and reasoning on possible overflow the new values seem correct). I finally added a new test case related to the multiplication by -1 issue on GT comparisons. llvm-svn: 194116
* Fix another constant folding address space place I missed.Matt Arsenault2013-11-041-12/+19
| | | | | | This fixes an assertion failure with a different sized address space. llvm-svn: 194014
* Consider (x == -1) unlikely in BranchProbabilityInfoHal Finkel2013-11-011-4/+18
| | | | | | | | | | | | This adds another heuristic to BPI, similar to the existing heuristic that considers (x == 0) unlikely to be true. As suggested in the PACT'98 paper by Deitrich, Cheng, and Hwu, -1 is often used to indicate an invalid index, and equality comparisons with -1 are also unlikely to succeed. Local experimentation supports this hypothesis: This yields a 1-2% speedup in the test-suite sqlite benchmark on the PPC A2 core, with no significant regressions. llvm-svn: 193855
* Merge CallGraph and BasicCallGraph.Rafael Espindola2013-10-313-159/+80
| | | | llvm-svn: 193734
* SCEV: Make the final add of an inbounds GEP nuw if we know that the index is ↵Benjamin Kramer2013-10-281-4/+9
| | | | | | | | | | | | | | | | | | | | | | | positive. We can't do this for the general case as saying a GEP with a negative index doesn't have unsigned wrap isn't valid for negative indices. %gep = getelementptr inbounds i32* %p, i64 -1 But an inbounds GEP cannot run past the end of address space. So we check for the very common case of a positive index and make GEPs derived from that NUW. Together with Andy's recent non-unit stride work this lets us analyze loops like void foo3(int *a, int *b) { for (; a < b; a++) {} } PR12375, PR12376. Differential Revision: http://llvm-reviews.chandlerc.com/D2033 llvm-svn: 193514
* Revert r193251 : Use address-taken to disambiguate global variable and ↵Shuxin Yang2013-10-271-11/+0
| | | | | | indirect memops. llvm-svn: 193489
* Quick look-up for block in loop.Wan Xiaofei2013-10-261-15/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements quick look-up for block in loop by maintaining a hash set for blocks. It improves the efficiency of loop analysis a lot, the biggest improvement could be 5-6%(458.sjeng). Below are the compilation time for our benchmark in llc before & after the patch. Benchmark llc - trunk llc - patched 401.bzip2 0.339081 100.00% 0.329657 102.86% 403.gcc 19.853966 100.00% 19.605466 101.27% 429.mcf 0.049823 100.00% 0.048451 102.83% 433.milc 0.514898 100.00% 0.510217 100.92% 444.namd 1.109328 100.00% 1.103481 100.53% 445.gobmk 4.988028 100.00% 4.929114 101.20% 456.hmmer 0.843871 100.00% 0.825865 102.18% 458.sjeng 0.754238 100.00% 0.714095 105.62% 464.h264ref 2.9668 100.00% 2.90612 102.09% 471.omnetpp 4.556533 100.00% 4.511886 100.99% bitmnp01 0.038168 100.00% 0.0357 106.91% idctrn01 0.037745 100.00% 0.037332 101.11% libquake2 3.78689 100.00% 3.76209 100.66% libquake_ 2.251525 100.00% 2.234104 100.78% linpack 0.033159 100.00% 0.032788 101.13% matrix01 0.045319 100.00% 0.043497 104.19% nbench 0.333161 100.00% 0.329799 101.02% tblook01 0.017863 100.00% 0.017666 101.12% ttsprk01 0.054337 100.00% 0.053057 102.41% Reviewer : Andrew Trick <atrick@apple.com>, Hal Finkel <hfinkel@anl.gov> Approver : Andrew Trick <atrick@apple.com> Test : Pass make check-all & llvm test-suite llvm-svn: 193460
* Fix SCEVExpander: don't try to expand quadratic recurrences outside a loop.Andrew Trick2013-10-251-11/+27
| | | | | | | | | | | | Partial fix for PR17459: wrong code at -O3 on x86_64-linux-gnu (affecting trunk and 3.3) When SCEV expands a recurrence outside of a loop it attempts to scale by the stride of the recurrence. Chained recurrences don't work that way. We could compute binomial coefficients, but would hve to guarantee that the chained AddRec's are in a perfectly reduced form. llvm-svn: 193438
* Fix LSR: don't normalize quadratic recurrences.Andrew Trick2013-10-251-5/+13
| | | | | | | | | | Partial fix for PR17459: wrong code at -O3 on x86_64-linux-gnu (affecting trunk and 3.3) ScalarEvolutionNormalization was attempting to normalize by adding and subtracting strides. Chained recurrences don't work that way. llvm-svn: 193437
* Call destroy from ~BasicCallGraph.Rafael Espindola2013-10-251-0/+4
| | | | | | | | | | | | This fix a memory leak found by valgrind. Calling it from the base class destructor would not destroy the BasicCallGraph bits. FIXME: BasicCallGraph is the only thing that inherits from CallGraph. Can we merge the two? llvm-svn: 193412
* fix PR17635: false positive with packed structuresNuno Lopes2013-10-241-3/+5
| | | | | | LLVM optimizers may widen accesses to packed structures that overflow the structure itself, but should be in bounds up to the alignment of the object llvm-svn: 193317
* Use address-taken to disambiguate global variable and indirect memops.Shuxin Yang2013-10-231-0/+11
| | | | | | | | | | Major steps include: 1). introduces a not-addr-taken bit-field in GlobalVariable 2). GlobalOpt pass sets "not-address-taken" if it proves a global varirable dosen't have its address taken. 3). AA use this info for disambiguation. llvm-svn: 193251
* Clarify SCEV comments.Andrew Trick2013-10-221-8/+11
| | | | | | We handle for(i=n; i>0; i -= s) by canonicalizing within SCEV to for(i=-n; i<0; i += s). llvm-svn: 193147
* TBAA: fix PR17620.Manman Ren2013-10-221-1/+5
| | | | | | | We can have a struct type with a single field and the field does not start with 0. In that case, we should correctly update the offset. llvm-svn: 193137
* Use more type helper functionsMatt Arsenault2013-10-211-1/+1
| | | | llvm-svn: 193109
* Fix creating bitcasts between address spaces in SCEV.Matt Arsenault2013-10-211-5/+10
| | | | | | | | The test before wasn't successfully testing this since it was missing the datalayout piece to change the size of the second address space. llvm-svn: 193102
* Remove unused SCEV functionsMatt Arsenault2013-10-211-20/+1
| | | | llvm-svn: 193097
* SCEV should use NSW to get trip count for positive nonunit stride loops.Andrew Trick2013-10-181-18/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | SCEV currently fails to compute loop counts for nonunit stride loops. This comes up frequently. It prevents loop optimization and forces vectorization to insert extra loop checks. For example: void foo(int n, int *x) { for (int i = 0; i < n; i += 3) { x[i] = i; x[i+1] = i+1; x[i+2] = i+2; } } We need to properly handle the case in which limit > INT_MAX-stride. In the above case: n > INT_MAX-3. In this case the loop counter will step beyond the limit and overflow at the same time. However, knowing that signed integer overlow in undefined, we can assume the loop test behavior is arbitrary after overflow. This obeys both C undefined behavior rules, and the more strict LLVM poison value rules. I'm finally fixing this in response to Hal Finkel's persistence. The most probable reason that we never optimized this before is that we were being careful to handle case where the developer expected a side-effect free infinite loop relying on overflow: for (int i = 0; i < n; i += s) { ++j; } return j; If INT_MAX+1 is a multiple of s and n > INT_MAX-s, then we might expect an infinite loop. However there are plenty of ways to achieve this effect without relying on undefined behavior of signed overflow. llvm-svn: 193015
* Remove x86_sse42_crc32_64_8 intrinsic. It has no functional difference from ↵Craig Topper2013-10-151-1/+0
| | | | | | x86_sse42_crc32_32_8 and was not mapped to a clang builtin. I'm not even sure why this form of the instruction is even called out explicitly in the docs. Also add AutoUpgrade support to convert it into the other intrinsic with appropriate trunc and zext. llvm-svn: 192672
* Rename DataLayout variables TD -> DLMatt Arsenault2013-10-031-26/+25
| | | | llvm-svn: 191927
* CaptureTracking: Plug a loophole in the "too many uses" heuristic.Benjamin Kramer2013-10-031-0/+6
| | | | | | | | | | The heuristic was added to avoid spending too much compile time A specially crafted test case (PR17461, PR16474) with many uses on a select or bitcast instruction can still trigger the slow case. Add a check for that case. This only affects compile time, don't have a good way to test it. llvm-svn: 191896
* Remove the very substantial, largely unmaintained legacy PGOChandler Carruth2013-10-0212-3832/+0
| | | | | | | | | | | | | | | | | | | | infrastructure. This was essentially work toward PGO based on a design that had several flaws, partially dating from a time when LLVM had a different architecture, and with an effort to modernize it abandoned without being completed. Since then, it has bitrotted for several years further. The result is nearly unusable, and isn't helping any of the modern PGO efforts. Instead, it is getting in the way, adding confusion about PGO in LLVM and distracting everyone with maintenance on essentially dead code. Removing it paves the way for modern efforts around PGO. Among other effects, this removes the last of the runtime libraries from LLVM. Those are being developed in the separate 'compiler-rt' project now, with somewhat different licensing specifically more approriate for runtimes. llvm-svn: 191835
* Remove several unused variables.Rafael Espindola2013-10-011-1/+0
| | | | | | Patch by Alp Toker. llvm-svn: 191757
* SCEVExpander: Fix a regression I introduced by to eagerly adding RAII objects.Benjamin Kramer2013-10-011-1/+4
| | | | | | PR17425. llvm-svn: 191741
* Convert manual insert point restores to the new RAII object.Benjamin Kramer2013-09-301-47/+15
| | | | llvm-svn: 191675
* ObjectSizeOffsetEvaluator: Don't run into infinite recursion if we have a ↵Benjamin Kramer2013-09-291-5/+7
| | | | | | | | cyclic GEP. Those can occur in dead code. PR17402. llvm-svn: 191644
* TBAA: try to fix the dragonegg bots.Manman Ren2013-09-271-1/+3
| | | | llvm-svn: 191585
* Minor code simplificationMatt Arsenault2013-09-271-11/+8
| | | | llvm-svn: 191579
OpenPOWER on IntegriCloud