summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/CaptureTracking.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [CaptureTracking] Support atomicrmw and cmpxchgPhilip Reames2016-02-181-0/+11
| | | | | | | | | | | | These atomic operations are conceptually both a load and store from the same location. As such, we can treat them as the most conservative of those two components which in practice, means we can treat them like stores. An cmpxchg or atomicrmw captures the values, but not the locations accessed. Note: We can probably be more aggressive about the comparison value in an cmpxhg since to have it be in memory, it must already be captured, but I figured it was better to avoid that for the moment. Note 2: It turns out that since we don't actually support cmpxchg of pointer type, writing a negative test is impossible. Differential Revision: http://reviews.llvm.org/D17400 llvm-svn: 261245
* [IR] Reformulate LLVM's EH funclet IRDavid Majnemer2015-12-121-3/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | While we have successfully implemented a funclet-oriented EH scheme on top of LLVM IR, our scheme has some notable deficiencies: - catchendpad and cleanupendpad are necessary in the current design but they are difficult to explain to others, even to seasoned LLVM experts. - catchendpad and cleanupendpad are optimization barriers. They cannot be split and force all potentially throwing call-sites to be invokes. This has a noticable effect on the quality of our code generation. - catchpad, while similar in some aspects to invoke, is fairly awkward. It is unsplittable, starts a funclet, and has control flow to other funclets. - The nesting relationship between funclets is currently a property of control flow edges. Because of this, we are forced to carefully analyze the flow graph to see if there might potentially exist illegal nesting among funclets. While we have logic to clone funclets when they are illegally nested, it would be nicer if we had a representation which forbade them upfront. Let's clean this up a bit by doing the following: - Instead, make catchpad more like cleanuppad and landingpad: no control flow, just a bunch of simple operands; catchpad would be splittable. - Introduce catchswitch, a control flow instruction designed to model the constraints of funclet oriented EH. - Make funclet scoping explicit by having funclet instructions consume the token produced by the funclet which contains them. - Remove catchendpad and cleanupendpad. Their presence can be inferred implicitly using coloring information. N.B. The state numbering code for the CLR has been updated but the veracity of it's output cannot be spoken for. An expert should take a look to make sure the results are reasonable. Reviewers: rnk, JosephTremoulet, andrew.w.kaylor Differential Revision: http://reviews.llvm.org/D15139 llvm-svn: 255422
* Refactor: Simplify boolean conditional return statements in llvm/lib/AnalysisAlexander Kornienko2015-11-051-4/+1
| | | | | | | | Patch by Richard Thomson! Differential revision: http://reviews.llvm.org/D9967 llvm-svn: 252209
* [CaptureTracking] Support operand bundles conservativelySanjoy Das2015-11-041-2/+3
| | | | | | | | | | | | | | | | | | | | | Summary: Earlier CaptureTracking would assume all "interesting" operands to a call or invoke were its arguments. With operand bundles this is no longer true. Note: an earlier change got `doesNotCapture` working correctly with operand bundles. This change uses DSE to test the changes to CaptureTracking. DSE is a vehicle for testing only, and is not directly involved in this change. Reviewers: reames, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14306 llvm-svn: 252095
* [IR] Give catchret an optional 'return value' operandDavid Majnemer2015-08-151-4/+5
| | | | | | | | | | | Some personality routines require funclet exit points to be clearly marked, this is done by producing a token at the funclet pad and consuming it at the corresponding ret instruction. CleanupReturnInst already had a spot for this operand but CatchReturnInst did not. Other personality routines don't need to use this which is why it has been made optional. llvm-svn: 245149
* [CaptureTracker] Provide an ordered basic block to PointerMayBeCapturedBeforeBruno Cardoso Lopes2015-07-311-65/+17
| | | | | | | | | | | | | | | | | | This patch is a follow up from r240560 and is a step further into mitigating the compile time performance issues in CaptureTracker. By providing the CaptureTracker with a "cached ordered basic block" instead of computing it every time, MemDepAnalysis can use this cache throughout its calls to AA->callCapturesBefore, avoiding to recompute it for every scanned instruction. In the same testcase used in r240560, compile time is reduced from 2min to 30s. This also fixes PR22348. rdar://problem/19230319 Differential Revision: http://reviews.llvm.org/D11364 llvm-svn: 243750
* [CaptureTracking] Avoid long compilation time on large basic blocksBruno Cardoso Lopes2015-06-241-16/+111
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CaptureTracking becomes very expensive in large basic blocks while calling PointerMayBeCaptured. PointerMayBeCaptured scans the BB the number of times equal to the number of uses of 'BeforeHere', which is currently capped at 20 and bails out with Tracker->tooManyUses(). The bottleneck here is the number of calls to PointerMayBeCaptured * the basic block scan. In a testcase with a 82k instruction BB, PointerMayBeCaptured is called 130k times, leading to 'shouldExplore' taking 527k runs, this currently takes ~12min. To fix this we locally (within PointerMayBeCaptured) number the instructions in the basic block using a DenseMap to cache instruction positions/numbers. We build the cache incrementally every time we need to scan an unexplored part of the BB, improving compile time to only take ~2min. This triggers in the flow: DeadStoreElimination -> MepDepAnalysis -> CaptureTracking. Side note: after multiple runs in the test-suite I've seen no performance nor compile time regressions, but could note a couple of compile time improvements: Performance Improvements - Compile Time Delta Previous Current StdDev SingleSource/Benchmarks/Misc-C++/bigfib -4.48% 0.8547 0.8164 0.0022 MultiSource/Benchmarks/TSVC/LoopRerolling-dbl/LoopRerolling-dbl -1.47% 1.3912 1.3707 0.0056 Differential Revision: http://reviews.llvm.org/D7010 llvm-svn: 240560
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* [cleanup] Re-sort all the #include lines in LLVM usingChandler Carruth2015-01-141-1/+1
| | | | | | | | | | | utils/sort_includes.py. I clearly haven't done this in a while, so more changed than usual. This even uncovered a missing include from the InstrProf library that I've added. No functionality changed here, just mechanical cleanup of the include order. llvm-svn: 225974
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-1/+1
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* Match semantics of PointerMayBeCapturedBefore to its name by defaultHal Finkel2014-07-211-4/+12
| | | | | | | | | | | | | | | As it turns out, the capture tracker named CaptureBefore used by AA, and now available via the PointerMayBeCapturedBefore function, would have been more-aptly named CapturedBeforeOrAt, because it considers captures at the instruction provided. This is not always what one wants, and it is difficult to get the strictly-before behavior given only the current interface. This adds an additional parameter which controls whether or not you want to include captures at the provided instruction. The default is not to include the instruction provided, so that 'Before' matches its name. No functionality change intended. llvm-svn: 213582
* Move the CapturesBefore tracker from AA into CaptureTrackingHal Finkel2014-07-211-0/+79
| | | | | | | | | | | | | | | | | There were two generally-useful CaptureTracker classes defined in LLVM: the simple tracker defined in CaptureTracking (and made available via the PointerMayBeCaptured utility function), and the CapturesBefore tracker available only inside of AA. This change moves the CapturesBefore tracker into CaptureTracking, generalizes it slightly (by adding a ReturnCaptures parameter), and makes it generally available via a PointerMayBeCapturedBefore utility function. This logic will be needed, for example, to perform noalias function parameter attribute inference. No functionality change intended. llvm-svn: 213519
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-12/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Make this interface accept const Use pointers and use overrideChandler Carruth2014-03-051-5/+5
| | | | | | | | to ensure we don't mess up any of the overrides. Necessary for cleaning up the Value use iterators and enabling range-based traversing of use lists. llvm-svn: 202958
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202945
* [Modules] Move CallSite into the IR library where it belogs. It isChandler Carruth2014-03-041-1/+1
| | | | | | | abstracting between a CallInst and an InvokeInst, both of which are IR concepts. llvm-svn: 202816
* Make nocapture analysis work with addrspacecastMatt Arsenault2014-01-141-0/+1
| | | | llvm-svn: 199246
* 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
* Extend 'readonly' and 'readnone' to work on function arguments as well asNick Lewycky2013-07-061-4/+4
| | | | | | | functions. Make the function attributes pass add it to known library functions and when it can deduce it. llvm-svn: 185735
* Remove unneeded #includes. Use forward declarations instead.Jakub Staszak2013-03-101-0/+5
| | | | llvm-svn: 176783
* 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
* Fix intendation.Chad Rosier2012-05-101-1/+1
| | | | llvm-svn: 156589
* Move includes to the .cpp file.Jakub Staszak2012-01-171-0/+2
| | | | llvm-svn: 148342
* Change CaptureTracking to pass a Use* instead of a Value* when a value isNick Lewycky2011-12-281-6/+6
| | | | | | | | | | | | | | captured. This allows the tracker to look at the specific use, which may be especially interesting for function calls. Use this to fix 'nocapture' deduction in FunctionAttrs. The existing one does not iterate until a fixpoint and does not guarantee that it produces the same result regardless of iteration order. The new implementation builds up a graph of how arguments are passed from function to function, and uses a bottom-up walk on the argument-SCCs to assign nocapture. This gets us nocapture more often, and does so rather efficiently and independent of iteration order. llvm-svn: 147327
* Fix crasher in GVN due to my recent capture tracking changes.Nick Lewycky2011-11-211-0/+3
| | | | llvm-svn: 145047
* Add virtual destructor. Whoops!Nick Lewycky2011-11-211-0/+2
| | | | llvm-svn: 145044
* Less template, more virtual! Refactoring suggested by Chris in code review.Nick Lewycky2011-11-201-2/+107
| | | | llvm-svn: 145014
* Refactor capture tracking (which already had a couple flags for whether returnsNick Lewycky2011-11-141-116/+31
| | | | | | | | | | and stores capture) to permit the caller to see each capture point and decide whether to continue looking. Use this inside memdep to do an analysis that basicaa won't do. This lets us solve another devirtualization case, fixing PR8908! llvm-svn: 144580
* Don't include Operator.h from InstrTypes.h.Jay Foad2011-04-111-0/+1
| | | | llvm-svn: 129271
* VAArg doesn't capture its operand.Dan Gohman2010-11-091-0/+3
| | | | llvm-svn: 118623
* simplifyGabor Greif2010-07-281-1/+1
| | | | llvm-svn: 109578
* rename use_const_iterator to const_use_iterator for consistency's sakeGabor Greif2010-03-251-1/+1
| | | | llvm-svn: 99564
* There are two ways of checking for a given type, for example isa<PointerType>(T)Duncan Sands2010-02-161-1/+1
| | | | | | | and T->isPointerTy(). Convert most instances of the first form to the second form. Requested by Chris. llvm-svn: 96344
* Reuse the Threshold value to size these containers because it'sDan Gohman2009-12-091-2/+2
| | | | | | currently somewhat convenient for them to have the same value. llvm-svn: 90980
* Fix a typo in a comment, and adjust SmallSet and SmallVector sizes,Dan Gohman2009-12-091-7/+7
| | | | | | that Chris noticed. llvm-svn: 90910
* Put a threshold on the number of users PointerMayBeCapturedDan Gohman2009-12-081-0/+16
| | | | | | | | | | | | examines; fall back to a conservative answer if there are more. This works around some several compile time problems resulting from BasicAliasAnalysis calling PointerMayBeCaptured. The value has been chosen arbitrarily. This fixes rdar://7438917 and may partially address PR5708. llvm-svn: 90905
* Use stripPointerCasts(). Thanks Duncan!Dan Gohman2009-11-201-1/+1
| | | | llvm-svn: 89472
* Revert the rule that considers comparisons between two pointers in theDan Gohman2009-11-201-9/+4
| | | | | | | | | | | | same object to be a non-capture; Duncan pointed out a way that such a comparison could be a capture. Make the rule that considers a comparison against null more specific, and only consider noalias return values compared against null. This still supports test/Transforms/GVN/nonescaping-malloc.ll, and is not susceptible to the problem Duncan pointed out with noalias arguments. llvm-svn: 89468
* Simplify this code; it's not necessary to check isIdentifiedObject hereDan Gohman2009-11-201-7/+5
| | | | | | | | because if the results from getUnderlyingObject match, the values must be from the same underlying object, even if we don't know what that object is. llvm-svn: 89434
* Refine the capture tracking rules for comparisons to be moreDan Gohman2009-11-201-6/+19
| | | | | | | | | careful about crazy methods of capturing pointers using comparisons. Comparisons of identified objects with null in the default address space are not captures. And, comparisons of two pointers within the same identified object are not captures. llvm-svn: 89421
* Use isVoidTy().Dan Gohman2009-11-201-2/+1
| | | | llvm-svn: 89419
* Refine this to only apply to null in the default address space.Dan Gohman2009-11-191-2/+4
| | | | llvm-svn: 89411
* Extend CaptureTracking to indicate when a value is never stored, evenDan Gohman2009-11-191-2/+9
| | | | | | | | if it is not ultimately captured. Teach BasicAliasAnalysis that a local object address which does not escape and is never stored does not alias with a value resulting from a load. llvm-svn: 89398
* Comparing a pointer with null is not a capture.Dan Gohman2009-11-191-0/+5
| | | | llvm-svn: 89389
* remove a check of isFreeCall: the argument to free is already nocapture so ↵Chris Lattner2009-11-031-4/+0
| | | | | | the generic call code works fine. llvm-svn: 85865
* Rename MallocFreeHelper as MemoryBuiltinsVictor Hernandez2009-10-271-1/+1
| | | | llvm-svn: 85286
* Rename MallocHelper as MallocFreeHelper, since it now also identifies calls ↵Victor Hernandez2009-10-261-1/+1
| | | | | | to free() llvm-svn: 85181
* Remove FreeInst.Victor Hernandez2009-10-261-3/+4
| | | | | | | Remove LowerAllocations pass. Update some more passes to treate free calls just like they were treating FreeInst. llvm-svn: 85176
* Push LLVMContexts through the IntegerType APIs.Owen Anderson2009-08-131-1/+1
| | | | llvm-svn: 78948
OpenPOWER on IntegriCloud