| Commit message (Collapse) | Author | Age | Files | Lines |
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
> 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
|
|
|
|
|
|
|
|
| |
Currently there is no generic way to derive phy
type information from the instruction flow.
Signed-off-by: David Given <dg@cowlark.com>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
| |
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
| |
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
|
|
| |
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
|
|
|
|
| |
You can mark a function as requiring a lock, or requiring being called
without a lock.
|
|
|
|
|
|
|
|
| |
Rather than tying everything to the beginning basic block
position.
This should be able to pinpoint instruction issues much more
exactly and readably.
|
| |
|
|
|
|
|
| |
Otherwise we lose the information what the target
type is (we only have the bit-size of the target).
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
| |
(symbol addresses).
They are pretty different. Symbol addresses have special meaning during
various phases, from symbol simplification to CSE.
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
| |
This also makes the OP_ASM data structures a bit more structured
in order to contain all the required information.
|
|
|
|
|
| |
Not only does it make sense, but the back-end needs to
know what pseudos got allocated ;)
|
|
|
|
| |
the list or not.
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
| |
We already did this, we just didn't have a visible prototype.
|
|
|
|
| |
white-space.
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
| |
We want to use it in almost any debugging schenario, so why not
just admit that.
|
|
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
|
|
|
|
|
| |
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).
|
|
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
| |
Very useful for debugging, since otherwise it's often
impossible to find all the other basic blocks.
|
|
|
|
|
|
| |
It will assrt if it can't find that many entries.
Zero means "all the ones you can find", aka old behaviour.
|
|
|
|
| |
Besides, the code is cleaner now - we can use our helper functions.
|
|
|
|
| |
We don't have usage counters, we have usage lists these days.
|
|
|
|
|
|
|
| |
track of which instructions use which pseudos.
It also verifies the usage, which shows a few bugs in
structure handling.
|
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
|
|
|
|
| |
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.
|
|
|
|
| |
has to agree on it or bad things happen.
|
|
|
|
|
|
|
| |
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.
|