aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/CaptureTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2016-05-26[CaptureTracking] Volatile operations capture their memory locationDavid Majnemer1-11/+36
The memory location that corresponds to a volatile operation is very special. They are observed by the machine in ways which we cannot reason about. Differential Revision: http://reviews.llvm.org/D20555 llvm-svn: 270879
2016-05-03Fold compares irrespective of whether allocation can be elidedAnna Thomas1-1/+9
Summary When a non-escaping pointer is compared to a global value, the comparison can be folded even if the corresponding malloc/allocation call cannot be elided. We need to make sure the global value is not null, since comparisons to null cannot be folded. In future, we should also handle cases when the the comparison instruction dominates the pointer escape. Reviewers: sanjoy Subscribers s.egerton, llvm-commits Differential Revision: http://reviews.llvm.org/D19549 llvm-svn: 268390
2016-02-18[CaptureTracking] Support atomicrmw and cmpxchgPhilip Reames1-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
2015-12-12[IR] Reformulate LLVM's EH funclet IRDavid Majnemer1-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
2015-11-05Refactor: Simplify boolean conditional return statements in llvm/lib/AnalysisAlexander Kornienko1-4/+1
Patch by Richard Thomson! Differential revision: http://reviews.llvm.org/D9967 llvm-svn: 252209
2015-11-04[CaptureTracking] Support operand bundles conservativelySanjoy Das1-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
2015-08-15[IR] Give catchret an optional 'return value' operandDavid Majnemer1-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
2015-07-31[CaptureTracker] Provide an ordered basic block to PointerMayBeCapturedBeforeBruno Cardoso Lopes1-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
2015-06-24[CaptureTracking] Avoid long compilation time on large basic blocksBruno Cardoso Lopes1-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
2015-06-23Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko1-1/+1
Apparently, the style needs to be agreed upon first. llvm-svn: 240390
2015-06-19Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko1-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
2015-01-14[cleanup] Re-sort all the #include lines in LLVM usingChandler Carruth1-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
2014-11-19Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie1-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
2014-07-21Match semantics of PointerMayBeCapturedBefore to its name by defaultHal Finkel1-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
2014-07-21Move the CapturesBefore tracker from AA into CaptureTrackingHal Finkel1-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
2014-03-09[C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth1-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
2014-03-05[C++11] Make this interface accept const Use pointers and use overrideChandler Carruth1-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
2014-03-05[C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper1-2/+2
class. llvm-svn: 202945
2014-03-04[Modules] Move CallSite into the IR library where it belogs. It isChandler Carruth1-1/+1
abstracting between a CallInst and an InvokeInst, both of which are IR concepts. llvm-svn: 202816
2014-01-14Make nocapture analysis work with addrspacecastMatt Arsenault1-0/+1
llvm-svn: 199246
2013-10-03CaptureTracking: Plug a loophole in the "too many uses" heuristic.Benjamin Kramer1-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
2013-07-06Extend 'readonly' and 'readnone' to work on function arguments as well asNick Lewycky1-4/+4
functions. Make the function attributes pass add it to known library functions and when it can deduce it. llvm-svn: 185735
2013-03-10Remove unneeded #includes. Use forward declarations instead.Jakub Staszak1-0/+5
llvm-svn: 176783
2012-10-08Give CaptureTracker::shouldExplore a base implementation. Most users want to doNick Lewycky1-2/+2
the same thing. No functionality change. llvm-svn: 165435
2012-05-10Fix intendation.Chad Rosier1-1/+1
llvm-svn: 156589
2012-01-17Move includes to the .cpp file.Jakub Staszak1-0/+2
llvm-svn: 148342
2011-12-28Change CaptureTracking to pass a Use* instead of a Value* when a value isNick Lewycky1-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
2011-11-21Fix crasher in GVN due to my recent capture tracking changes.Nick Lewycky1-0/+3
llvm-svn: 145047
2011-11-21Add virtual destructor. Whoops!Nick Lewycky1-0/+2
llvm-svn: 145044
2011-11-20Less template, more virtual! Refactoring suggested by Chris in code review.Nick Lewycky1-2/+107
llvm-svn: 145014
2011-11-14Refactor capture tracking (which already had a couple flags for whether returnsNick Lewycky1-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
2011-04-11Don't include Operator.h from InstrTypes.h.Jay Foad1-0/+1
llvm-svn: 129271
2010-11-09VAArg doesn't capture its operand.Dan Gohman1-0/+3
llvm-svn: 118623
2010-07-28simplifyGabor Greif1-1/+1
llvm-svn: 109578
2010-03-25rename use_const_iterator to const_use_iterator for consistency's sakeGabor Greif1-1/+1
llvm-svn: 99564
2010-02-16There are two ways of checking for a given type, for example isa<PointerType>(T)Duncan Sands1-1/+1
and T->isPointerTy(). Convert most instances of the first form to the second form. Requested by Chris. llvm-svn: 96344
2009-12-09Reuse the Threshold value to size these containers because it'sDan Gohman1-2/+2
currently somewhat convenient for them to have the same value. llvm-svn: 90980
2009-12-09Fix a typo in a comment, and adjust SmallSet and SmallVector sizes,Dan Gohman1-7/+7
that Chris noticed. llvm-svn: 90910
2009-12-08Put a threshold on the number of users PointerMayBeCapturedDan Gohman1-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
2009-11-20Use stripPointerCasts(). Thanks Duncan!Dan Gohman1-1/+1
llvm-svn: 89472
2009-11-20Revert the rule that considers comparisons between two pointers in theDan Gohman1-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
2009-11-20Simplify this code; it's not necessary to check isIdentifiedObject hereDan Gohman1-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
2009-11-20Refine the capture tracking rules for comparisons to be moreDan Gohman1-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
2009-11-20Use isVoidTy().Dan Gohman1-2/+1
llvm-svn: 89419
2009-11-19Refine this to only apply to null in the default address space.Dan Gohman1-2/+4
llvm-svn: 89411
2009-11-19Extend CaptureTracking to indicate when a value is never stored, evenDan Gohman1-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
2009-11-19Comparing a pointer with null is not a capture.Dan Gohman1-0/+5
llvm-svn: 89389
2009-11-03remove a check of isFreeCall: the argument to free is already nocapture so ↵Chris Lattner1-4/+0
the generic call code works fine. llvm-svn: 85865
2009-10-27Rename MallocFreeHelper as MemoryBuiltinsVictor Hernandez1-1/+1
llvm-svn: 85286
2009-10-26Rename MallocHelper as MallocFreeHelper, since it now also identifies calls ↵Victor Hernandez1-1/+1
to free() llvm-svn: 85181
generated by cgit v1.1 at 2025-10-15 13:11:25 +0000