Get Gentoo!
gentoo.org sites
gentoo.org Wiki Bugs Forums Packages
Planet Archives Sources
Infra Status
aboutsummaryrefslogtreecommitdiff
path: root/linearize.h
Commit message (Collapse)AuthorAgeFilesLines
* linearize.h: sanitize headerKamil Dudka2009-07-291-1/+1
| | | | | | | | | | It's unfortunate to use 'true' and 'false' as identifiers in a system header. It clashes with corresponding macros from <stdbool.h> when included before <sparse/linearize.h>. Signed-off-by: Kamil Dudka <kdudka@redhat.com> Acked-by: Hannes Eder <hannes@hanneseder.net> Signed-off-by: Christopher Li <sparse@chrisli.org>
* Revert the context tracking codeJohannes Berg2008-12-241-4/+3
| | | | | | | | | | | | | | | | | | > Do you want to resend your change which revert the context changes? > Make it base on Josh's git's tree and I will merge your changes in my > branch. Below. Or I can give it to you in git if you prefer. I still think we should redo this in some form so that annotations with different contexts can work properly, but I don't have time to take care of it right now. johannes >From ca95b62edf1600a2b55ed9ca0515d049807a84fc Mon Sep 17 00:00:00 2001 From: Johannes Berg <johannes@sipsolutions.net> Date: Tue, 23 Dec 2008 10:53:19 +0100 Subject: [PATCH] Revert context tracking code
* Add type information to struct instruction.David Given2008-12-181-0/+1
| | | | | | | | Currently there is no generic way to derive phy type information from the instruction flow. Signed-off-by: David Given <dg@cowlark.com>
* fix bug in context tracking codeJohannes Berg2008-04-241-1/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | My optimisation to avoid recursion into BBs when checking contexts lead to a failure in a case like this: static int warn_conditional(void) { if (condition) return 0; a(); if (condition == 0) return 1; r(); return 0; } because some blocks are called with different contexts and thus need to be checked multiple times. The obvious fix would be to decrease the recursion depth at the end of the BB check function, but that, while correct, leads to extremely long sparse runtimes on somewhat complex functions. Thus, this patch also makes sparse cache which contexts it has checked a block in and avoid the re-checking in that case. Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
* sparse: simple conditional context trackingJohannes Berg2008-04-211-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch enables a very simple form of conditional context tracking, namely something like if (spin_trylock(...)) { [...] spin_unlock(...); } Note that __ret = spin_trylock(...); if (__ret) { [...] spin_unlock(...); } does /not/ work since that would require tracking the variable and doing extra checks to ensure the variable isn't globally accessible or similar which could lead to race conditions. To declare a trylock, one uses: int spin_trylock(...) __attribute__((conditional_context(spinlock,0,1,0))) {...} Note that doing this currently excludes that function itself from context checking completely. Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
* make sparse keep its promise about context trackingJohannes Berg2008-04-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The sparse man page promises that it will check this: Functions with the extended attribute __attribute__((context(expression,in_context,out_context)) require the context expression (for instance, a lock) to have the value in_context (a constant nonnegative integer) when called, and return with the value out_context (a constant nonnegative integer). It doesn't keep that promise though, nor can it, especially with contexts that can be acquired recursively (like RCU in the kernel.) This patch makes sparse track different contexts, and also follows up on that promise, but with slightly different semantics: * the "require the context to have the value" is changed to require it to have /at least/ the value if 'in_context', * an exact_context(...) attribute is introduced with the previously described semantics (to be used for non-recursive contexts), * the __context__ statement is extended to also include a required context argument (same at least semantics), Unfortunately, I wasn't able to keep the same output, so now you'll see different messages from sparse, especially when trying to unlock a lock that isn't locked you'll see a message pointing to the unlock function rather than complaining about the basic block, you can see that in the test suite changes. This patch also contains test updates and a lot of new tests for the new functionality. Except for the changed messages, old functionality should not be affected. However, the kernel use of __attribute__((context(...)) is actually wrong, the kernel often does things like: static void *dev_mc_seq_start(struct seq_file *seq, loff_t * pos) __acquires(dev_base_lock) { [...] read_lock(&dev_base_lock); [...] } rather than static void *dev_mc_seq_start(struct seq_file *seq, loff_t * pos) __acquires(dev_base_lock) { [...] __acquire__(dev_base_lock); read_lock(&dev_base_lock); [...] } (and possibly more when read_lock() is annotated appropriately, such as dropping whatever context read_lock() returns to convert the context to the dev_base_lock one.) Currently, sparse doesn't care, but if it's going to check the context of functions contained within another function then we need to put the actual __acquire__ together with acquiring the context. The great benefit of this patch is that you can now document at least some locking assumptions in a machine-readable way: before: /* requires mylock held */ static void myfunc(void) {...} after: static void myfunc(void) __requires(mylock) {...} where, for sparse, #define __requires(x) __attribute__((context(x,1,1))) Doing so may result in lots of other functions that need to be annoated along with it because they also have the same locking requirements, but ultimately sparse can check a lot of locking assumptions that way. I have already used this patch and identify a number of kernel bugs by marking things to require certain locks or RCU-protection and checking sparse output. To do that, you need a few kernel patches which I'll send separately. Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
* linearize: DECLARE_ALLOCATOR for asm_constraint and asm_rulesJosh Triplett2007-04-201-0/+3
| | | | Signed-off-by: Josh Triplett <josh@freedesktop.org>
* Add annotation for inline function call.Christopher Li2007-03-021-0/+1
| | | | | | | | For inline functions, Sparse inlines the function body at evaluation. It is very hard to find out the original function call. This change preserves the original call as an annotation. Signed-Off-By: Christopher Li <sparse@chrisli.org>
* Add missing #include "allocate.h" in linearize.h for DECLARE_ALLOCATOR.Josh Triplett2007-01-271-0/+1
| | | | Signed-off-by: Josh Triplett <josh@freedesktop.org>
* Coding style fix: in a pointer type, * goes with the name, not the type.Josh Triplett2007-01-271-1/+1
| | | | Signed-off-by: Josh Triplett <josh@freedesktop.org>
* Add instruction to pseudo user tracking.Christopher Li2007-01-161-3/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The current way of tracking pseudo register user is by keeping a list of the address of the pseudo_t member. This address can be in part of the instruction member, the worse case is in the argument list of the call instruction. As the comment for address_taken() said, using the container to get instruction pointer is wrong. It use to work with instruction that relate to symbol address. But that is not true any more. Even worse, it is very hard to track the pseudo usage other than symbol address. The only reason symbol address used to works for call instruction is because call instruction did not directly use the symbol address. I bit the bullet and just add the instruction pointer to pair with the pseudo user pointer. So it will work with the case that the user instruction is call as well. Testing: I compare the linearize result with/without the patch on a few sparse source file it self. The linearize generate exactly the same result except the symbol address changes. Which is predictable different because the pseudo user structure allocate memory. Singed-Off-By: Christopher Li <sparse@chrisli.org>
* Change the symbol access list to a pseudo listChristopher Li2007-01-161-1/+1
| | | | | | | | | A pseudo list contains more information. It can get to the symbol as well as the usage information. Now it is much easier to answer questions like "What functions does this function call?". Signed-Off-By: Christopher Li <sparse@chrisli.org>
* bb_terminated: Use boundary values rather than specific opcodesJosh Triplett2006-09-141-1/+2
| | | | | | | | The opcode enum defines the boundary values OP_TERMINATOR and OP_TERMINATOR_END for terminator instructions; use those in bb_terminated rather than the specific values they currently equal. Signed-off-by: Josh Triplett <josh@freedesktop.org>
* [PATCH] Parse and track multiple contexts by expressionJosh Triplett2006-08-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | sparse currently only tracks one global context for __context__ and __attribute__((context)). This adds support for parsing an additional argument to each of these which gives a context expression. For __attribute__((context)), store each context attribute as a separate context structure containing the expression, the entry context, and the exit context, and keep a list of these structures in the ctype. For __context__, store the context expression in the context instruction. Modify the various frontends to adapt to this change, without changing functionality. This change should not affect parsing of programs which worked with previous versions of sparse, unless those programs use comma expressions as arguments to __context__ or __attribute__((context)), which seems highly dubious and unlikely. sparse with -Wcontext generates identical output with or without this change on Linux 2.6.18-rc4. Signed-off-by: Josh Triplett <josh@freedesktop.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* Fix dropped type information in "add_pseudo()".Linus Torvalds2006-07-081-1/+1
| | | | | | | | | We return a well-defined type (a pointer to the pseudo_t we added), so don't cast it to "void *" unnecessarily. Type safety is good. Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] Add a function to translate the SSA form back to normal form.Luc Van Oostenryck2005-11-211-0/+1
| | | | | | | | For now, it use a simple method but which introduces a lot more copies than necessary. Can be fixed later. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@looxix.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] Add a new opcode: OP_COPY.Luc Van Oostenryck2005-11-211-0/+3
| | | | | | | | | | | | | This is needed to translate SSA back to normal form. Maybe we should split this in two distinct ops: The first ones correspond to the old OP_PHISOURCE (but if the same phisrc feed several phi-nodes, we need sevarel distinct copy instruction); at this stage they are the only instruction that can define a pseudo in multiple places. The other ones being the "normal" copies. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@looxix.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* Add support for context checking functions.Linus Torvalds2005-04-071-0/+1
| | | | | You can mark a function as requiring a lock, or requiring being called without a lock.
* Make each instruction have a position of its own.Linus Torvalds2005-04-071-0/+1
| | | | | | | | Rather than tying everything to the beginning basic block position. This should be able to pinpoint instruction issues much more exactly and readably.
* Add compile-time "range-check" infrastructure to sparseLinus Torvalds2005-04-071-0/+1
|
* Split OP_CAST into signed, unsigned and FP casts.Linus Torvalds2005-04-071-0/+2
| | | | | Otherwise we lose the information what the target type is (we only have the bit-size of the target).
* Split the binops where signedness matters into unsigned and signed.Linus Torvalds2005-04-071-4/+4
| | | | | | | This is OP_MUL/OP_DIV/OP_MOD/OP_SHR. We actually do the constant simplifications still wrong, but now the information is all there.
* Split OP_SETVAL into OP_SETVAL (fp expressions and labels) and OP_SYMADDRLinus Torvalds2005-04-071-0/+1
| | | | | | | (symbol addresses). They are pretty different. Symbol addresses have special meaning during various phases, from symbol simplification to CSE.
* Save off the asm parameter name too.Linus Torvalds2005-04-071-0/+1
| | | | | | | The asm_inputs/outputs "expression list" is not really an expression list any more: it is a list of "triples", where the first entry is the identifier name, the second one is the constraint string, and the third one is the expression.
* Make asm linearization not drop the constraints.Linus Torvalds2005-04-071-2/+14
| | | | | This also makes the OP_ASM data structures a bit more structured in order to contain all the required information.
* Add the argument pseudos to the "enter" instructionLinus Torvalds2005-04-071-0/+3
| | | | | Not only does it make sense, but the back-end needs to know what pseudos got allocated ;)
* Make "remove_pseudo()" return whether it removed a pseudo fromLinus Torvalds2005-04-071-2/+2
| | | | the list or not.
* Make pretty helper functions for showing individual instructionsLinus Torvalds2005-04-071-1/+1
| | | | | | | | | | | | and labels. And comments, for that matter. This eventually allows us to buffer them up, rather than print them out directly. Which we'll need to do if we want to fix up frame offsets etc (for register save areas). And other post- processing. Also, for comments, make "show_instruction()" return the string rather than print it out.
* Move remove_pseudo() to linearize.hLinus Torvalds2005-04-071-0/+4
|
* Expose "show_instruction()" for debugging.Linus Torvalds2005-04-071-0/+1
| | | | We already did this, we just didn't have a visible prototype.
* Expose "show_bb()" for debugging, and make it do more appropriateLinus Torvalds2005-04-071-0/+1
| | | | white-space.
* Make OP_PHISOURCE track the OP_PHI instructions that it defines.Linus Torvalds2005-04-071-0/+4
| | | | | | | | This allows us to always see which pseudos are nonlocally affected by the phi source. We can only do this after the instruction flow is fixed, together with the OP_DEATHNOTE phase.
* Linearize inline asm statementsLinus Torvalds2005-04-071-0/+6
| | | | | | | | This doesn't actually save the register class information, so you can't do proper register allocation, but it does all the input reading and store to outputs. Still need to teach the liveness analysis about the _usage_ rules.
* Make the "entrypoint" be a special OP_ENTRY instruction instead ofLinus Torvalds2005-04-071-1/+5
| | | | | | | | | a special basic block. This removes a lot of special cases, since now flow doesn't have any special BB to worry about. It also gives a clear definition point for argument pseudos, and thus makes liveness tracking lose a special case.
* Expose "show_pseudo()" to the world.Linus Torvalds2005-04-071-0/+1
| | | | | We want to use it in almost any debugging schenario, so why not just admit that.
* Add pseudo death-note tracking.Linus Torvalds2005-04-071-0/+1
| | | | | | | | | | Now that we have full pseudo usage lists, we can also add deathnotes to pseudos in the instruction stream. NOTE! We add the deathnote to _before_ the last instruction that uses that pseudo. That looks a bit strange, but it's actually what you want: when we traverse the instuctions, we want to know that the inputs are dead.
* Remove OP_SETCC, make OP_SEL bigger instead.Linus Torvalds2005-04-071-4/+3
| | | | | | | This was originally done so that "struct instruction" would be smaller, but it has since grown anyway (for the memops), so splitting OP_SEL into two instructions no longer makes sense, and makes it harder on CSE.
* Simplify trivial casts (and handle pointers specially).Linus Torvalds2005-04-071-0/+1
| | | | | | | | | | | | This does trivial simplification of casting to the same typesize. HOWEVER. We split casts up into whether they cast to a dereferencable pointer type or not, and we don't simplify pointer casts. This should mean that if we ever want to do type-based alias analysis, we can still avoid casted accesses. (If we do type-based alias analysis, we'll also need to make a union access do a cast. Which we probably should do anyway).
* Associate pseudos with the symbol name whose value they got.Linus Torvalds2005-04-071-0/+1
| | | | | | | | | | This is purely for debugging. It's only used to show what symbol a pseudo might be (and I stress "might", since CSE can and does screw it up) associated with. Also print out the def list for a basic block when verbose. It all makes it a bit easier to guess what's up.
* Start tracking cross-basic-block pseudo usage.Linus Torvalds2005-04-071-2/+1
| | | | | | This should basically allow us to do register allocation. Or maybe it's too broken. But the results look reasonable from a quick manual peek.
* Start using instruction sizes properly.Linus Torvalds2005-04-071-3/+3
| | | | | | | | | | We should drop symbol types by now, and base things on just raw sizes. Anything else just doesn't work from a CSE standpoint. Some things may care about actual types later, notably the type- based alias analysis. Those types still exist in the cast nodes. Also, make the printout be more readable.
* Add entrypoint pointer to each bb.Linus Torvalds2005-04-071-0/+1
| | | | | Very useful for debugging, since otherwise it's often impossible to find all the other basic blocks.
* Make list-ptr remove/replace take a count.Linus Torvalds2005-04-071-5/+5
| | | | | | It will assrt if it can't find that many entries. Zero means "all the ones you can find", aka old behaviour.
* Be a lot more careful when re-writing branches.Linus Torvalds2005-04-071-0/+6
| | | | Besides, the code is cleaner now - we can use our helper functions.
* Kill long-dead pseudo-reuse code.Linus Torvalds2005-04-071-2/+1
| | | | We don't have usage counters, we have usage lists these days.
* Add a final pseudo usage tracking phase, which keepsLinus Torvalds2005-04-071-0/+2
| | | | | | | track of which instructions use which pseudos. It also verifies the usage, which shows a few bugs in structure handling.
* Who says you can't do type-safe function-overloading in C?Linus Torvalds2005-04-071-5/+5
| | | | | | | | | You just have to be a bit crazy (*), and use "__typeof__" in creative ways. (*) Ok, a _lot_ crazy. But dammit, I want type-safety _and_ convenience, and I'm willing to do a few crazy macros to get it.
* Add some type-safety features to the list pointer operations.Linus Torvalds2005-04-071-1/+1
| | | | | | | | The list pointer traversal macros are very easy to use, but you can also mis-use them by passing in the wrong pointer type without the macros having any chance to warn you about it. Until now.
* Clean up the tests for "pseudo has use list", since add/removeLinus Torvalds2005-04-071-1/+6
| | | | has to agree on it or bad things happen.
* Do early CSE before even doing the symbol simplification.Linus Torvalds2005-04-071-2/+2
| | | | | | | This allows us to notice when a symbol address usage is trivially dead, and optimize such a symbol better since we don't have to worry about the address being used to access it.