summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert the majority of the next patch in the address space series:Chandler Carruth2012-11-016-37/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | r165941: Resubmit the changes to llvm core to update the functions to support different pointer sizes on a per address space basis. Despite this commit log, this change primarily changed stuff outside of VMCore, and those changes do not carry any tests for correctness (or even plausibility), and we have consistently found questionable or flat out incorrect cases in these changes. Most of them are probably correct, but we need to devise a system that makes it more clear when we have handled the address space concerns correctly, and ideally each pass that gets updated would receive an accompanying test case that exercises that pass specificaly w.r.t. alternate address spaces. However, from this commit, I have retained the new C API entry points. Those were an orthogonal change that probably should have been split apart, but they seem entirely good. In several places the changes were very obvious cleanups with no actual multiple address space code added; these I have not reverted when I spotted them. In a few other places there were merge conflicts due to a cleaner solution being implemented later, often not using address spaces at all. In those cases, I've preserved the new code which isn't address space dependent. This is part of my ongoing effort to clean out the partial address space code which carries high risk and low test coverage, and not likely to be finished before the 3.2 release looms closer. Duncan and I would both like to see the above issues addressed before we return to these changes. llvm-svn: 167222
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-017-146/+140
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. llvm-svn: 167221
* Fix a couple of comment typos.Benjamin Kramer2012-10-311-2/+2
| | | | llvm-svn: 167113
* DependenceAnalysis: Don't crash if there is no constant operand.Benjamin Kramer2012-10-311-3/+4
| | | | | | This makes the code match the comments. Resolves a crash in loop idiom (PR14219). llvm-svn: 167110
* Remove code to saturate profile counts.Bob Wilson2012-10-291-8/+1
| | | | | | | | | We may need to change the way profile counter values are stored, but saturation is the wrong thing to do. Just remove it for now. Patch by Alastair Murray! llvm-svn: 166938
* SCEV validator: Ignore CouldNotCompute/undef on both sides. This is mostly ↵Benjamin Kramer2012-10-271-3/+6
| | | | | | noise and blocks finding more severe bugs. llvm-svn: 166873
* SCEV validator: Add workarounds for some common false positives due to the ↵Benjamin Kramer2012-10-271-0/+18
| | | | | | way it handles strings. llvm-svn: 166872
* Remove LoopDependenceAnalysis.Benjamin Kramer2012-10-263-364/+0
| | | | | | | It was unmaintained and not much more than a stub. The new DependenceAnalysis pass is both more general and complete. llvm-svn: 166810
* Add a basic verifier for SCEV's backedge taken counts.Benjamin Kramer2012-10-261-0/+68
| | | | | | | | | | | Enabled with -verify-scev. This could be extended significantly but hopefully catches the common cases now. Note that it's not enabled by default in any configuration because the way it tries to distinguish SCEVs is still fragile and may produce false positives. Also the test-suite isn't clean yet, one example is that it fails if a pass drops an NSW bit but it's still present in SCEV's cached. Cleaning up all those cases will take some time. llvm-svn: 166786
* Fix a crash in SimpliftDemandedBits of vectors of pointers.Nadav Rotem2012-10-261-6/+4
| | | | | | PR14183. llvm-svn: 166785
* Hoist out some work done inside a loop doing a linear scan over allNick Lewycky2012-10-261-12/+17
| | | | | | | | | | | | instructions in a block. GetUnderlyingObject is more expensive than it looks as it can, for instance, call SimplifyInstruction. This might have some behavioural changes in odd corner cases, but only because of some strange artefacts of the original implementation. If you were relying on those, we can fix that by replacing this with a smarter algorithm. Change passes the existing tests. llvm-svn: 166754
* Revert 166726 because it may have broken a number of SPEC tests. PR14183.Nadav Rotem2012-10-251-3/+2
| | | | llvm-svn: 166739
* Fix a crash in ValueTracking. Add support for vectors of pointers.Nadav Rotem2012-10-251-2/+3
| | | | llvm-svn: 166726
* DependenceAnalysis: Push #includes down into the implementation.Benjamin Kramer2012-10-251-1/+5
| | | | llvm-svn: 166688
* getSmallConstantTripMultiple should never return zero.Hal Finkel2012-10-241-2/+5
| | | | | | | | | When the trip count is -1, getSmallConstantTripMultiple could return zero, and this would cause runtime loop unrolling to assert. Instead of returning zero, one is now returned (consistent with the existing overflow cases). Fixes PR14167. llvm-svn: 166612
* Add some cleanup to the DataLayout changes requested by Chandler.Micah Villmow2012-10-243-7/+3
| | | | llvm-svn: 166607
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-247-133/+143
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Ignore unreachable blocks when doing memory dependence analysis on non-localBill Wendling2012-10-231-2/+2
| | | | | | | | | | | loads. It's not really profitable and may result in GVN going into an infinite loop when it hits constructs like this: %x = gep %some.type %x, ... Found via an LTO build of LLVM. llvm-svn: 166490
* revert r166264 because the LTO build is still failingNadav Rotem2012-10-191-6/+6
| | | | llvm-svn: 166340
* SCEVExpander: Don't crash when trying to merge two constant phis.Benjamin Kramer2012-10-191-0/+11
| | | | | | Just constant fold them so they can't cause any trouble. Fixes PR12627. llvm-svn: 166286
* recommit the patch that makes LSR and LowerInvoke use the TargetTransform ↵Nadav Rotem2012-10-191-6/+6
| | | | | | interface. llvm-svn: 166264
* Temporarily revert the TargetTransform changes.Bob Wilson2012-10-181-6/+6
| | | | | | | | | | | The TargetTransform changes are breaking LTO bootstraps of clang. I am working with Nadav to figure out the problem, but I am reverting it for now to get our buildbots working. This reverts svn commits: 165665 165669 165670 165786 165787 165997 and I have also reverted clang svn 165741 llvm-svn: 166168
* Resubmit the changes to llvm core to update the functions to support ↵Micah Villmow2012-10-156-20/+37
| | | | | | different pointer sizes on a per address space basis. llvm-svn: 165941
* fix warningSebastian Pop2012-10-121-6/+6
| | | | | | | | | | | DependenceAnalysis.cpp:1164:32: warning: implicit truncation from 'int' to bitfield changes value from -5 to 3 [-Wconstant-conversion] Result.DV[Level].Direction &= ~Dependence::DVEntry::GT; ^ ~~~~~~~~~~~~~~~~~~~~~~~~ Patch from Preston Briggs <preston.briggs@gmail.com>. llvm-svn: 165784
* Revert 165732 for further review.Micah Villmow2012-10-116-37/+20
| | | | llvm-svn: 165747
* Add in the first iteration of support for llvm/clang/lldb to allow variable ↵Micah Villmow2012-10-116-20/+37
| | | | | | per address space pointer sizes to be optimized correctly. llvm-svn: 165726
* dependence analysisSebastian Pop2012-10-113-0/+3783
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Patch from Preston Briggs <preston.briggs@gmail.com>. This is an updated version of the dependence-analysis patch, including an MIV test based on Banerjee's inequalities. It's a fairly complete implementation of the paper Practical Dependence Testing Gina Goff, Ken Kennedy, and Chau-Wen Tseng PLDI 1991 It cannot yet propagate constraints between coupled RDIV subscripts (discussed in Section 5.3.2 of the paper). It's organized as a FunctionPass with a single entry point that supports testing for dependence between two instructions in a function. If there's no dependence, it returns null. If there's a dependence, it returns a pointer to a Dependence which can be queried about details (what kind of dependence, is it loop independent, direction and distance vector entries, etc). I haven't included every imaginable feature, but there's a good selection that should be adequate for supporting many loop transformations. Of course, it can be extended as necessary. Included in the patch file are many test cases, commented with C code showing the loops and array references. llvm-svn: 165708
* Add a new interface to allow IR-level passes to access codegen-specific ↵Nadav Rotem2012-10-101-6/+6
| | | | | | information. llvm-svn: 165665
* Use the attribute enums to query if a function has an attribute.Bill Wendling2012-10-091-1/+1
| | | | llvm-svn: 165551
* Use the attribute enums to query if a parameter has an attribute.Bill Wendling2012-10-091-1/+1
| | | | llvm-svn: 165550
* Create enums for the different attributes.Bill Wendling2012-10-093-6/+7
| | | | | | | We use the enums to query whether an Attributes object has that attribute. The opaque layer is responsible for knowing where that specific attribute is stored. llvm-svn: 165488
* Remove more uses of the attribute enums by supplying appropriate query ↵Bill Wendling2012-10-091-1/+1
| | | | | | | | methods for them. No functionality change intended. llvm-svn: 165466
* Give CaptureTracker::shouldExplore a base implementation. Most users want to doNick Lewycky2012-10-081-2/+2
| | | | | | the same thing. No functionality change. llvm-svn: 165435
* Move TargetData to DataLayout.Micah Villmow2012-10-0818-132/+132
| | | | llvm-svn: 165402
* Make sure always-inline functions get inlined. <rdar://problem/12423986>Bob Wilson2012-10-071-1/+3
| | | | | | | | | | | | | | | | Without this change, when the estimated cost for inlining a function with an "alwaysinline" attribute was lower than the inlining threshold, the getInlineCost function was returning that estimated cost rather than the special InlineCost::AlwaysInlineCost value. That is fine in the normal inlining case, but it can fail when the inliner considers the opportunity cost of inlining into an internal or linkonce-odr function. It may decide not to inline the always-inline function in that case. The fix here is just to make getInlineCost always return the special value for always-inline functions. I ran into this building clang with libc++. Tablegen failed to link because of an always-inline function that was not inlined. I have been unable to reduce the testcase down to a reasonable size. llvm-svn: 165367
* The alignment of an sret parameter is known: it must be at least theDuncan Sands2012-10-041-5/+14
| | | | | | alignment of the return type. Teach the optimizers this. llvm-svn: 165226
* Use method to query for NoAlias attribute.Bill Wendling2012-10-041-1/+1
| | | | llvm-svn: 165211
* Ignore apparent buffer overruns on external or weak globals. This is a majorDuncan Sands2012-09-301-7/+11
| | | | | | | source of false positives due to globals being declared in a header with some kind of incomplete (small) type, but the actual definition being bigger. llvm-svn: 164912
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-275-19/+19
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-275-19/+19
| | | | llvm-svn: 164767
* Remove the `hasFnAttr' method from Function.Bill Wendling2012-09-263-5/+5
| | | | | | | The hasFnAttr method has been replaced by querying the Attributes explicitly. No intended functionality change. llvm-svn: 164725
* Now that invoke of an intrinsic is possible (for the llvm.do.nothing intrinsic)Duncan Sands2012-09-261-4/+5
| | | | | | | teach the callgraph logic to not create callgraph edges to intrinsics for invoke instructions; it already skips this for call instructions. Fixes PR13903. llvm-svn: 164707
* Teach the 'lint' sanity checking pass to detect simple buffer overflows.Duncan Sands2012-09-261-19/+39
| | | | llvm-svn: 164671
* Change the way the lint sanity checking pass detects misaligned memory accesses.Duncan Sands2012-09-251-6/+18
| | | | | | | | | | | | | | | Previously it was only be able to detect problems if the pointer was a numerical value (eg inttoptr i32 1 to i32*), but not if it was an alloca or globa. The reason was the use of ComputeMaskedBits: imagine you have "alloca i8, align 2", and ask ComputeMaskedBits what it knows about the bits of the alloca pointer. It can tell you that the bottom bit is known zero (due to align 2) but it can't tell you that bit 1 is known one. That's because the address could be an even multiple of 2 rather than an odd multiple, eg it might be a multiple of 4. Thus trying to use KnownOne is ineffective in the case of an alloca as it will never have any bits set. Instead look explicitly for constant offsets from allocas and globals. llvm-svn: 164595
* GCC doesn't understand that OrigAliasResult having a value is correlated withDuncan Sands2012-09-191-1/+1
| | | | | | | ArePhisAssumedNoAlias, and warns that OrigAliasResult may be used uninitialized. Pacify GCC. llvm-svn: 164229
* Prevent inlining of callees which allocate lots of memory into a recursive ↵Nadav Rotem2012-09-191-14/+58
| | | | | | | | | | | | | | | | | | caller. Example: void foo() { ... foo(); // I'm recursive! bar(); } bar() { int a[1000]; // large stack size } rdar://10853263 llvm-svn: 164207
* Release build: guard dump functions withManman Ren2012-09-1210-11/+11
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. llvm-svn: 163679
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-0610-0/+22
| | | | | | No functional change. llvm-svn: 163344
* Dont cast away const needlessly. Found by gcc48 -Wcast-qual.Roman Divacky2012-09-061-1/+2
| | | | llvm-svn: 163324
* BasicAA: Recognize cyclic NoAlias phisArnold Schwaighofer2012-09-061-0/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Enhances basic alias analysis to recognize phis whose first incoming values are NoAlias and whose other incoming values are just the phi node itself through some amount of recursion. Example: With this change basicaa reports that ptr_phi and ptr_phi2 do not alias each other. bb: ptr = ptr2 + 1 loop: ptr_phi = phi [bb, ptr], [loop, ptr_plus_one] ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one] ... ptr_plus_one = gep ptr_phi, 1 ptr2_plus_one = gep ptr2_phi, 1 This enables the elimination of one load in code like the following: extern int foo; int test_noalias(int *ptr, int num, int* coeff) { int *ptr2 = ptr; int result = (*ptr++) * (*coeff--); while (num--) { *ptr2++ = *ptr; result += (*coeff--) * (*ptr++); } *ptr = foo; return result; } Part 2/2 of fix for PR13564. llvm-svn: 163319
OpenPOWER on IntegriCloud