Re: Normalizing the bitmap APIs.
On Thu, Oct 11, 2012 at 3:08 AM, Lawrence Crowl wrote: > As part of our effort to make programming in GCC easier, we would like > to improve the interface to bitmaps. > > There are three bitmap types, each with disparate operations and > function names. This disparity causes problems > * when changing a variable from one type to another, > * when moving one's attention from one type to another. > We would like to change the existing function names to be more uniform. > > The most complicated operations > are those that produce a bitwise result > for one or more binary bitwise operations. > These do work as if written with one of the following forms: > > d = a OP b > d = a OP b with reporting of a change to d > a OP= b > a OP= b with reporting of a change to a > > d = a OP (b OP c) > d = a OP (b OP c) with reporting of a change to d > a OP= (b OP c) > a OP= (b OP c) with reporting of a change to a > > where OP is one of > > OP TAG operation description >& and intersection >| ior union >^ xor inequivalence >- dif set difference (reverse relative complement) (a&~b) >/ rdf reverse set difference (relative complement) (~a&b) > > One approach is to add operators for the bitmap operations. > Unfortunately, the straightforward way to do that would introduce > temporary variables where none exist now, which would result in a net > loss of performance. For example, > bitmap_a_and_b (dest, a, b); > written as > dest = a & b; > would result in code that is effectively > tmp = a & b; > dest = tmp; > and would require allocation and copying of tmp. > > We can avoid this run-time expense by using expression templates > http://en.wikipedia.org/wiki/Expression_templates. However, that > change would require substantial implementation work and substantial > compile-time effort to untangle the templates. > > Also, unfortunately, with C++2003 as the implementation language and > the existing use of unions in critical data structures like trees, > the overloading of assignment operators would either be prohibited or > require a significantly clumsier syntax than one would like. > > Instead, I propose a more modest change, preserving the existing call > syntax, but normalizing it so that function names are predictable and > general. By overloading these operations on the type of the bitmap, > we can use a single name for a single action, regardless of type. > Doing so eases the task of changing types, as may be desiriable to > obtain a different performance profile. > > For the operations above, I suggest names as follows: > > assign_TAG (d = a OP b) > assign_TAG_changed > TAG_assign (a OP= b) > TAG_assign_changed > > assign_TAG_TAG (d = a OP (b OP c)) > assign_TAG_TAG_changed > TAG_assign_TAG (a OP= (b OP c)) > TAG_assign_TAG_changed > > For example, sbitmap_a_or_b_cg (d, a, b) > becomes assign_ior_changed (d, a, b); > and bitmap_ior_and_compl_into (a, b, c) > becomes ior_assign_dif (a, b, c). > > It is not surprising that some expressions using change-returning > functions do not use the function result. However, it appears that > some such functions never have their result used. I would propose > using void versions everwhere that the result is not used. These can > be implemented with the non-void versions easily enough. > > Testing for a change also applies to the single bit clear and set > routines for bitmap, but not ebitmap or sbitmap. It would probably > be prudent to make names for both variants, and implement the testing > version only when needed. The non-testing version can be implemented > via the testing version in the short term. > > Other operations are simpler in structure, but still need common > names. I propose the following: > > clear (bitmap) -> void > clear_range (bitmap, unsigned, unsigned) -> void > assign_not (bitmap, const_bitmap) -> void > has_intersection (const_bitmap, const_bitmap) -> bool > is_subset_of (const_bitmap, const_bitmap) -> bool > cardinality (const_bitmap) -> unsigned > cardinality_of_range (const_bitmap, unsigned, unsigned) -> unsigned > is_empty (const_bitmap) -> bool > is_singleton (const_bitmap) -> bool > first_set_bit (const_bitmap) -> unsigned > last_set_bit (const_bitmap) -> unsigned > test_bit (const_bitmap, unsigned) -> bool > > I propose to leave the allocation, iteration, vector, debug/dump/print > and functions alone for the time being. > > Comments? In general unifying the interface to the various bitmap implementations occured to me as well. I also quickly settled on function overloads for this. Rather than inventing new names I'd pick the most suitable existing set of names - which is those from bitmap.h. I'd rather not mix this with any kind of further C++-ification (that is introduction of member functions or operator overloads). Just my 2 cents, Richard. > -- > Lawrence Crowl
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
On Thu, Oct 11, 2012 at 5:04 AM, Uday P. Khedker wrote: > Hi David, > >> This is great progress. > > > Thanks. > > >> >> If I understand the experiments, your implementtion has very small >> cost to perform the analysis, at least for the SPEC benchmarks you are >> testing. Have you connected the analysis to any optimizations? Is >> there any improvement in performance on SPEC CPU or other >> applications? > > > Unfortunately we could not do this as it requires changing the way the > pointer information > is made available to other passes. Right now, it is encoded in the TREE > nodes of > variables which make is same at all program points. In other words, GCC, by > definition > assumes flow insensitive information. Supporting flow sensitivity implies > being able > to provide different information for the same pointer at different program > points. That's actually not true. In fact existing GCC pointer analysis is flow-sensitive for all SSA pointers. Points-to information is associated with each (and only with!) SSA pointer variable via SSA_NAME_PTR_INFO. > We are investigating how this can be done and this is one of the most > important future > works on which we seek collaboration. Unless we are able to do this, we will > not be able > to take advantage of the analysis. I suggest to look at the above and the disambiguators that use points-to information in tree-ssa-alias.c (and their helpers in tree-ssa-struct-alias.c). >> >> You ask for collaboration, but it's not clear what state the >> infrastructure is in, how complete it is, and what more needs to be >> done. > > > The infrastructure is in a reasonably complete state except that > (a) It is not directly useful to other analyses and optimizations for the > reasons described above. > (b) It uses rather naive and inefficient data structures in which sets are > stored as linked lists and set operations are implemented using linear > searches. > (c) Some corner cases related identifying pointers need to be fixed. > (d) It handles heap locations rather conservatively. > > We seek collaborations on (a) and (b). We have designed APIs to hide the > data structures > and now these are good student projects. Some details can be found at > http://www.cse.iitb.ac.in/grc/gcc-workshop-12/index.php?page=projects#Projects_with_Concrete_and_Detailed. > > We are carrying out research on (d) and have some ideas on what needs to be > done but it will > be some time before the infrastructure is enhanced to include it. We are > committed to doing it. I'd be interested to know how you analysis (is it interprocedural at all?) scales on programs the existing IPA PTA blows up (in both compile-time and memory-usage, usually first memory-usage ;)). Did you investigate on how to handle whole-program PTA at link-time with our distributed WHOPR mode (thus at no point a single compiler process sees all function bodies of the program but WPA phase sees the whole program callgraph). Thanks, Richard. > Thanks and regards, > > Uday. > >
Re: Normalizing the bitmap APIs.
On Thu, Oct 11, 2012 at 9:01 AM, Richard Biener wrote: > I'd rather not mix this with any kind of further C++-ification (that is > introduction of member functions or operator overloads). Agreed. At first I was surprised that Lawrence had not done the obvious operator overloads, but the introduction of temporaries convinced me. Also, doing it via template expressions seemed overkill for what amounts to syntactic sugar. Diego.
Re: Functions that are CSEable but not pure
On Oct 3, 2012, Jason Merrill wrote:
> int& lazy_i()
> {
> static int i = init;
> return i;
> }
> If the initialization is expensive or order-sensitive, this is a
> useful alternative to initialization on load
> An interesting property of such functions is that they only have
> side-effects the first time they are called, so subsequent calls can
> be optimized away to just use the return value of the first call.
> Currently there is no way to express this in GCC so that the
> optimizers know that multiple calls are redundant.
On Oct 4, 2012, Jakub Jelinek wrote:
> The singleton function really is
> void singleton (void)
> {
> static __thread bool initialized;
> if (!initialized) {
> initialized = true;
> call_some_function_that_may_modify_memory ();
> }
> }
> and has side effects just first time in a thread.
How about marking the singleton containing the call to the initializer
as always_inline, but not the initializer itself?
The compiler can then infer that initialized is set on the first inlined
call and optimize away subsequent tests and initializer calls
(call_some_function_that_may_modify_memory).
--
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/ FSF Latin America board member
Free Software Evangelist Red Hat Brazil Compiler Engineer
Re: Functions that are CSEable but not pure
On 10/11/2012 11:14 AM, Alexandre Oliva wrote:
How about marking the singleton containing the call to the initializer
as always_inline, but not the initializer itself?
The compiler can then infer that initialized is set on the first inlined
call and optimize away subsequent tests and initializer calls
(call_some_function_that_may_modify_memory).
That would require exporting the initialized flag in addition to the
initializer function; currently it is private to the translation unit
with the initializer function. That is, the wrapper currently looks like
int& i_wrap()
{
if (i_init) i_init();
return i;
}
and your suggestion would change it to
int& i_wrap()
{
if (i_init && !i_initialized) { i_initialized = true; i_init(); }
return i;
}
In previous discussions, people thought this would be less efficient.
Jason
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
That's actually not true. In fact existing GCC pointer analysis is
flow-sensitive for all SSA pointers.
SSA provides partial flow sensitivity to the top level pointers. For deeper
pointers, one needs to interleave SSA and points-to analysis. Besides, it cannot
handle global pointers which are important at the interprocedural level.
Points-to information is associated
with each (and only with!) SSA pointer variable via SSA_NAME_PTR_INFO.
I have enclosed a program fragment and dump fragment that shows
(a) flow insensitivity of GCC's points-to analysis
(b) points-to information for non-SSA variables.
At the same time, yes I reckon that the points-to information is encoded
in SSA_NAME_PTR_INFO and I wondered why the prefix SSA. Could you help
me by explaining the dump?
I suggest to look at the above and the disambiguators that use points-to
information in tree-ssa-alias.c (and their helpers in tree-ssa-struct-alias.c).
Since we are interested in interprocedural analysis, we would like to include
global variables and pointers at all levels of indirection. Hence we do not
depend
on SSA variables. However, our analysis can become more efficient by separating
SSA
names and other names.
I'd be interested to know how you analysis (is it interprocedural at all?)
Yes it is interprocedural and does not introduce approximations even in
the presence of recursion. Without interprocedural analysis, pointer analysis
is not much useful.
We use full call strings method (Sharir-Pnueli, 1981) for full flow and
context sensitivity but use value based termination (Khedker-Karkare, CC 2008)
that reduces the time and space by orders of magnitude (actually by a factor of
a
million for recursive programs).
scales on programs the existing IPA PTA blows up (in both compile-time
and memory-usage, usually first memory-usage ;)).
You are right. As our paper shows, even with our value based termination,
the blow up is significant. Hence we factor in strong liveness. This reduces
the size of information dramatically without missing out on any useful
information.
And there are more avenues of speeding up our analysis at the algorithmic level
(and I am not counting the use of better data structures which is the most
obvious thing to do.)
Did you investigate
on how to handle whole-program PTA at link-time with our distributed
WHOPR mode (thus at no point a single compiler process sees all
function bodies of the program but WPA phase sees the whole program
callgraph).
We have use LTO framework but did not use WHOPR mode because context sensitive
analysis is not possible for recursive programs by creating context independent
summaries by looking at one procedure at a time. Well, one can always compromise
on precision but we did not want to do that. So we use -flto-partition=none to
load all procedure bodies.
Thanks.
Uday.
-
Program fragment
-
#include
int a, b, c, *e;
int main()
{
if (a == b)
e = &c; /* statement n1 */
else
e = &b; /* statement n2 */
e = &a; /* statement n3 */
p();
}
p()
{
printf ("%d", e);
}
Dump fragment. Note that flow sensitive analysis should say that
- e points only to c after n1,
- e points only to b after n2,
- e points only to c and b before n3,
- e points only a after n3.
However the analysis simply says that e points to a, b, c (ap0art from ESCAPED
and NONLOCAL).
Points-to sets
NULL = { }
ANYTHING = { ANYTHING }
READONLY = { READONLY }
ESCAPED = { READONLY ESCAPED NONLOCAL a b c }
NONLOCAL = { ESCAPED NONLOCAL }
CALLUSED = { }
STOREDANYTHING = { }
INTEGER = { ANYTHING }
e.0_1 = same as e
e = { ESCAPED NONLOCAL a b c }
a.1_1 = { ESCAPED NONLOCAL }
a = same as a.1_1
b.2_2 = { ESCAPED NONLOCAL }
b = same as b.2_2
c = { ESCAPED NONLOCAL }
Re: Normalizing the bitmap APIs.
On 10/11/12, Richard Biener wrote: > On Oct 11, 2012, Lawrence Crowl wrote: >> As part of our effort to make programming in GCC easier, we would like >> to improve the interface to bitmaps. >> >> There are three bitmap types, each with disparate operations and >> function names. This disparity causes problems >> * when changing a variable from one type to another, >> * when moving one's attention from one type to another. >> We would like to change the existing function names to be more uniform. >> >> The most complicated operations >> are those that produce a bitwise result >> for one or more binary bitwise operations. >> These do work as if written with one of the following forms: >> >> d = a OP b >> d = a OP b with reporting of a change to d >> a OP= b >> a OP= b with reporting of a change to a >> >> d = a OP (b OP c) >> d = a OP (b OP c) with reporting of a change to d >> a OP= (b OP c) >> a OP= (b OP c) with reporting of a change to a >> >> where OP is one of >> >> OP TAG operation description >>& and intersection >>| ior union >>^ xor inequivalence >>- dif set difference (reverse relative complement) (a&~b) >>/ rdf reverse set difference (relative complement) (~a&b) >> >> One approach is to add operators for the bitmap operations. >> Unfortunately, the straightforward way to do that would introduce >> temporary variables where none exist now, which would result in a net >> loss of performance. For example, >> bitmap_a_and_b (dest, a, b); >> written as >> dest = a & b; >> would result in code that is effectively >> tmp = a & b; >> dest = tmp; >> and would require allocation and copying of tmp. >> >> We can avoid this run-time expense by using expression templates >> http://en.wikipedia.org/wiki/Expression_templates. However, that >> change would require substantial implementation work and substantial >> compile-time effort to untangle the templates. >> >> Also, unfortunately, with C++2003 as the implementation language and >> the existing use of unions in critical data structures like trees, >> the overloading of assignment operators would either be prohibited or >> require a significantly clumsier syntax than one would like. >> >> Instead, I propose a more modest change, preserving the existing call >> syntax, but normalizing it so that function names are predictable and >> general. By overloading these operations on the type of the bitmap, >> we can use a single name for a single action, regardless of type. >> Doing so eases the task of changing types, as may be desiriable to >> obtain a different performance profile. >> >> For the operations above, I suggest names as follows: >> >> assign_TAG (d = a OP b) >> assign_TAG_changed >> TAG_assign (a OP= b) >> TAG_assign_changed >> >> assign_TAG_TAG (d = a OP (b OP c)) >> assign_TAG_TAG_changed >> TAG_assign_TAG (a OP= (b OP c)) >> TAG_assign_TAG_changed >> >> For example, sbitmap_a_or_b_cg (d, a, b) >> becomes assign_ior_changed (d, a, b); >> and bitmap_ior_and_compl_into (a, b, c) >> becomes ior_assign_dif (a, b, c). >> >> It is not surprising that some expressions using change-returning >> functions do not use the function result. However, it appears that >> some such functions never have their result used. I would propose >> using void versions everwhere that the result is not used. These can >> be implemented with the non-void versions easily enough. >> >> Testing for a change also applies to the single bit clear and set >> routines for bitmap, but not ebitmap or sbitmap. It would probably >> be prudent to make names for both variants, and implement the testing >> version only when needed. The non-testing version can be implemented >> via the testing version in the short term. >> >> Other operations are simpler in structure, but still need common >> names. I propose the following: >> >> clear (bitmap) -> void >> clear_range (bitmap, unsigned, unsigned) -> void >> assign_not (bitmap, const_bitmap) -> void >> has_intersection (const_bitmap, const_bitmap) -> bool >> is_subset_of (const_bitmap, const_bitmap) -> bool >> cardinality (const_bitmap) -> unsigned >> cardinality_of_range (const_bitmap, unsigned, unsigned) -> unsigned >> is_empty (const_bitmap) -> bool >> is_singleton (const_bitmap) -> bool >> first_set_bit (const_bitmap) -> unsigned >> last_set_bit (const_bitmap) -> unsigned >> test_bit (const_bitmap, unsigned) -> bool >> >> I propose to leave the allocation, iteration, vector, debug/dump/print >> and functions alone for the time being. >> >> Comments? > > In general unifying the interface to the various bitmap implementations > occured to me as well. I also quickly settled on function overloads > for this. > > Rather than inventing new names I'd pick the most suitable existing > set of names - which is those from bitmap.h. The existing bitmap.h names do not distinguish between functions that report changes and those that do not, but
Re: Normalizing the bitmap APIs.
On 2012-10-11 13:26 , Lawrence Crowl wrote: My only other concern was that the mapping between those function names and the tasks to be done sometimes seemed less than obvious. So, I proposed the name change. However, I think the current names are workable, assuming an acceptable solution to the above problem. I would say, add both variants and make the empty ones drop the return value. So, for instance, bitmap_ior returns a value, so make bitmap_ior_cg drop it. Diego.
Re: Functions that are CSEable but not pure
On Oct 11, 2012, Jason Merrill wrote:
> On 10/11/2012 11:14 AM, Alexandre Oliva wrote:
>> How about marking the singleton containing the call to the initializer
>> as always_inline, but not the initializer itself?
>>
>> The compiler can then infer that initialized is set on the first inlined
>> call and optimize away subsequent tests and initializer calls
>> (call_some_function_that_may_modify_memory).
> That would require exporting the initialized flag in addition to the
> initializer function; currently it is private to the translation unit
> with the initializer function. That is, the wrapper currently looks
> like
> int& i_wrap() { if (i_init) i_init(); return i; }
This is not entirely clear to me; where is i defined in the first place?
Is it i_init that defines and tests i_initialized?
I.e., do we translate:
[EXTERN] thread_local T i;
int f()
{
T& j = i;
...
}
to:
[EXTERN] __thread T i;
#if !EXTERN
void
i_init()
{
static __thread bool initialized;
if (!initialized)
{
initialized = true;
i.T();
}
}
#endif
static T&
i_wrap ()
{
if (i_init)
i_init ();
return i;
}
int
f()
{
T& j = i_wrap();
...
}
?
Consider instead the following expansion:
[EXTERN] __thread T i;
#if !EXTERN
static void i_init (void);
__thread void (*i_initialize)(void) = i_init;
static void
i_init ()
{
i_initialize = NULL;
i.T();
}
#else
EXTERN __thread void (*i_initialize)(void);
#endif
static T& __attribute__((__always_inline__))
i_wrap ()
{
if (i_initialize)
{
i_initialize ();
// this is redundant, but it should enable removal of subsequent calls
i_initialize = NULL;
}
return i;
}
or this:
[EXTERN] __thread T *i;
#if !EXTERN
static __thread T i_data;
void
i_init ()
{
i = &i_data; // or maybe allocate it dynamically?
i->T();
}
#else
extern void i_init ();
#endif
static T& __attribute__((__always_inline__))
i_wrap ()
{
if (!i)
i_init ();
return *i; // dereference should enable cse
}
--
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/ FSF Latin America board member
Free Software Evangelist Red Hat Brazil Compiler Engineer
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
On Thu, Oct 11, 2012 at 11:53 AM, Uday P. Khedker wrote: > >> >> That's actually not true. In fact existing GCC pointer analysis is >> flow-sensitive for all SSA pointers. > > > SSA provides partial flow sensitivity to the top level pointers. For deeper > pointers, one needs to interleave SSA and points-to analysis. Besides, it > cannot > handle global pointers which are important at the interprocedural level. Yes, for global pointers, but in GIMPLE we do not have 'deeper' pointers. Unless I'm misunderstanding you. By 'deep pointers' you mean 'foo->ptr1->ptr2'? There are no memory expressions of that kind in GIMPLE. Diego.
Re: Normalizing the bitmap APIs.
On 10/11/12, Diego Novillo wrote: > On 2012-10-11 13:26 , Lawrence Crowl wrote: >> My only other concern was that the mapping between those function >> names and the tasks to be done sometimes seemed less than obvious. >> So, I proposed the name change. However, I think the current names >> are workable, assuming an acceptable solution to the above problem. > > I would say, add both variants and make the empty ones drop the return > value. So, for instance, bitmap_ior returns a value, so make > bitmap_ior_cg drop it. That convention is opposite from what is used in sbitmap, where _cg indicates that it returns the bool. I think returning the value will be the less common case. -- Lawrence Crowl
Re: Normalizing the bitmap APIs.
On 2012-10-11 16:25 , Lawrence Crowl wrote: On 10/11/12, Diego Novillo wrote: On 2012-10-11 13:26 , Lawrence Crowl wrote: My only other concern was that the mapping between those function names and the tasks to be done sometimes seemed less than obvious. So, I proposed the name change. However, I think the current names are workable, assuming an acceptable solution to the above problem. I would say, add both variants and make the empty ones drop the return value. So, for instance, bitmap_ior returns a value, so make bitmap_ior_cg drop it. That convention is opposite from what is used in sbitmap, where _cg indicates that it returns the bool. I think returning the value will be the less common case. Sorry, I mixed the two up. I meant the version that makes sense. Diego.
possible typo in gcc/java/expr.c at line 1053
this code looks bogus, i think that the "== INTEGER_CST" needs to disappear.
kenny
tree
build_newarray (int atype_value, tree length)
{
tree type_arg;
tree prim_type = decode_newarray_type (atype_value);
tree type
= build_java_array_type (prim_type,
host_integerp (length, 0) == INTEGER_CST
? tree_low_cst (length, 0) : -1);
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
Diego Novillo wrote, On Friday 12 October 2012 01:41 AM:
On Thu, Oct 11, 2012 at 11:53 AM, Uday P. Khedker wrote:
That's actually not true. In fact existing GCC pointer analysis is
flow-sensitive for all SSA pointers.
SSA provides partial flow sensitivity to the top level pointers. For deeper
pointers, one needs to interleave SSA and points-to analysis. Besides, it
cannot
handle global pointers which are important at the interprocedural level.
Yes, for global pointers, but in GIMPLE we do not have 'deeper'
pointers. Unless I'm misunderstanding you. By 'deep pointers' you
mean 'foo->ptr1->ptr2'? There are no memory expressions of that kind
in GIMPLE.
I meant pointers that are pointed to by other pointers. However I see that
GCC manages to solve common cases as a consequence of other optimizations so
I will need some time to create an example that shows problems with deeper
pointers but my main reason for not using SSA is that it seems fine for
local analysis of scalars. When we introduce globals (the example that I gave in
my previous mail http://gcc.gnu.org/ml/gcc/2012-10/msg00164.html) OR
have function calls to which we pass pointers, SSA is helpless.
Here's an example:
main()
{
int **p;
int *a, *d;
int w, x;
a = &w;
f1(a);
p = &a;
a = &x;
f2(p);
d = a;
return *d;
}
It is clear that d can only point to x and can never point to w. However,
the points-to sets dumped in file .052i.pta show that d can point to w.
ANYTHING = { ANYTHING }
READONLY = { READONLY }
ESCAPED = { ESCAPED NONLOCAL a w x } same as main.clobber
NONLOCAL = { ESCAPED NONLOCAL } same as f1
STOREDANYTHING = { }
INTEGER = { ANYTHING }
main.clobber = { ESCAPED NONLOCAL a w x }
main.use = { ESCAPED NONLOCAL a w x } same as main.clobber
main.result = { ESCAPED NONLOCAL } same as D.1958_4
main.varargs = { }
a = { ESCAPED NONLOCAL w x } same as a.0_1
w = { ESCAPED NONLOCAL }
a.0_1 = { ESCAPED NONLOCAL w x }
f1 = { ESCAPED NONLOCAL }
x = { ESCAPED NONLOCAL }
f2 = { ESCAPED NONLOCAL } same as f1
d_3 = { ESCAPED NONLOCAL w x } same as a.0_1
D.1958_4 = { ESCAPED NONLOCAL }
The basic point I am trying to make is that SSA is primarily defined for
locally scoped scalars and works excellently for them. In some cases
it can be extended to handle other situations too. However, for
pointers, starting from the first principles could be cleaner (and
certainly more precise).
Uday.
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
On Thu, Oct 11, 2012 at 9:41 PM, Uday P. Khedker wrote:
>
>
> Diego Novillo wrote, On Friday 12 October 2012 01:41 AM:
>
>> On Thu, Oct 11, 2012 at 11:53 AM, Uday P. Khedker
>> wrote:
>>>
>>>
That's actually not true. In fact existing GCC pointer analysis is
flow-sensitive for all SSA pointers.
>>>
>>>
>>>
>>> SSA provides partial flow sensitivity to the top level pointers. For
>>> deeper
>>> pointers, one needs to interleave SSA and points-to analysis. Besides, it
>>> cannot
>>> handle global pointers which are important at the interprocedural level.
>>
>>
>> Yes, for global pointers, but in GIMPLE we do not have 'deeper'
>> pointers. Unless I'm misunderstanding you. By 'deep pointers' you
>> mean 'foo->ptr1->ptr2'? There are no memory expressions of that kind
>> in GIMPLE.
>
>
> I meant pointers that are pointed to by other pointers. However I see that
> GCC manages to solve common cases as a consequence of other optimizations so
> I will need some time to create an example that shows problems with deeper
> pointers but my main reason for not using SSA is that it seems fine for
> local analysis of scalars. When we introduce globals (the example that I
> gave in
> my previous mail http://gcc.gnu.org/ml/gcc/2012-10/msg00164.html) OR
> have function calls to which we pass pointers, SSA is helpless.
>
> Here's an example:
>
> main()
> {
> int **p;
> int *a, *d;
> int w, x;
>
> a = &w;
> f1(a);
> p = &a;
> a = &x;
> f2(p);
> d = a;
>
> return *d;
> }
>
> It is clear that d can only point to x and can never point to w.
I think you are wrong there.
int *a1;
void f1(int *a)
{
a1 = a;
}
void f2(int **p)
{
*p = a1;
}
That will change a to &w after f2 is called. So it looks like your
aliasing analysis does not take into account escaping like it should.
This is the whole point of marking a as escaped. Maybe I missed
something here though but d can point w with my functions for f1 and
f2.
Thanks,
Andrew Pinski
> However,
> the points-to sets dumped in file .052i.pta show that d can point to w.
>
>
> ANYTHING = { ANYTHING }
> READONLY = { READONLY }
> ESCAPED = { ESCAPED NONLOCAL a w x } same as main.clobber
> NONLOCAL = { ESCAPED NONLOCAL } same as f1
>
> STOREDANYTHING = { }
> INTEGER = { ANYTHING }
> main.clobber = { ESCAPED NONLOCAL a w x }
> main.use = { ESCAPED NONLOCAL a w x } same as main.clobber
> main.result = { ESCAPED NONLOCAL } same as D.1958_4
> main.varargs = { }
> a = { ESCAPED NONLOCAL w x } same as a.0_1
> w = { ESCAPED NONLOCAL }
> a.0_1 = { ESCAPED NONLOCAL w x }
> f1 = { ESCAPED NONLOCAL }
> x = { ESCAPED NONLOCAL }
> f2 = { ESCAPED NONLOCAL } same as f1
> d_3 = { ESCAPED NONLOCAL w x } same as a.0_1
> D.1958_4 = { ESCAPED NONLOCAL }
>
> The basic point I am trying to make is that SSA is primarily defined for
> locally scoped scalars and works excellently for them. In some cases
> it can be extended to handle other situations too. However, for
> pointers, starting from the first principles could be cleaner (and
> certainly more precise).
>
> Uday.
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
Andrew Pinski wrote, On Friday 12 October 2012 10:29 AM:
Here's an example:
main()
{
int **p;
int *a, *d;
int w, x;
a = &w;
f1(a);
p = &a;
a = &x;
f2(p);
d = a;
return *d;
}
It is clear that d can only point to x and can never point to w.
I think you are wrong there.
int *a1;
void f1(int *a)
{
a1 = a;
}
void f2(int **p)
{
*p = a1;
}
That will change a to &w after f2 is called. So it looks like your
aliasing analysis does not take into account escaping like it should.
This is the whole point of marking a as escaped. Maybe I missed
something here though but d can point w with my functions for f1 and
f2.
Ah, you caught me there, but I think I can escape, at least in this situation
:-)
The call to f1 is not central to the point I am making; I had included it only
to ensure
that the assignment a=&w doesn't get eliminated by dead code elimination. Since
you
decided to hold the address of a into a1 through function f1, let me eliminate
the
call to f1 and make the assignment a=&w live in some other way. Here's the
changed code:
main()
{
int **p;
int *a, *d;
int w, x;
d = &x;
a = &w;
if (f1())
{
p = &a;
a = &x;
f2(p);
d = a;
}
return *d + *a;
}
Now when f2 is called, a definitely does not point to w. Hence d should not
point to w.
And yet, the dump shows that d continue to point to w.
In any case, your point about escaping variables strengthens my point about
inappropriateness
of SSA for pointer analysis, although not through this example.
Uday.
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
decided to hold the address of a into a1 through function f1, let me eliminate the call to f1 and make the assignment a=&w live in some other way. Here's the changed code: Please read it as "eliminate the call passing a to f1". Uday.
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
On Thu, Oct 11, 2012 at 10:41 PM, Uday P. Khedker wrote:
>
>
> Andrew Pinski wrote, On Friday 12 October 2012 10:29 AM:
>
>
>>> Here's an example:
>>>
>>> main()
>>> {
>>> int **p;
>>> int *a, *d;
>>> int w, x;
>>>
>>> a = &w;
>>> f1(a);
>>> p = &a;
>>> a = &x;
>>> f2(p);
>>> d = a;
>>>
>>> return *d;
>>> }
>>>
>>> It is clear that d can only point to x and can never point to w.
>>
>>
>> I think you are wrong there.
>>
>> int *a1;
>> void f1(int *a)
>> {
>>a1 = a;
>> }
>>
>> void f2(int **p)
>> {
>>*p = a1;
>> }
>>
>> That will change a to &w after f2 is called. So it looks like your
>> aliasing analysis does not take into account escaping like it should.
>> This is the whole point of marking a as escaped. Maybe I missed
>> something here though but d can point w with my functions for f1 and
>> f2.
>
>
> Ah, you caught me there, but I think I can escape, at least in this
> situation :-)
>
> The call to f1 is not central to the point I am making; I had included it
> only to ensure
> that the assignment a=&w doesn't get eliminated by dead code elimination.
> Since you
> decided to hold the address of a into a1 through function f1, let me
> eliminate the
> call to f1 and make the assignment a=&w live in some other way. Here's the
> changed code:
>
>
> main()
> {
> int **p;
> int *a, *d;
> int w, x;
>
> d = &x;
> a = &w;
> if (f1())
>
> {
> p = &a;
> a = &x;
> f2(p);
> d = a;
> }
>
> return *d + *a;
> }
>
> Now when f2 is called, a definitely does not point to w. Hence d should not
> point to w.
> And yet, the dump shows that d continue to point to w.
>
> In any case, your point about escaping variables strengthens my point about
> inappropriateness
> of SSA for pointer analysis, although not through this example.
Except the problem here is just about what f1 clobbers. Since a has
not escaped by the time f1 is called, f1 cannot clobber a (or d).
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23384 for reference on why
GCC gets this incorrect. GCC does not have a flow sensitive clobber
list yet.
>
> Uday.
>
>
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
Andrew Pinski wrote, On Friday 12 October 2012 11:26 AM: Except the problem here is just about what f1 clobbers. Since a has not escaped by the time f1 is called, f1 cannot clobber a (or d). http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23384 for reference on why GCC gets this incorrect. GCC does not have a flow sensitive clobber list yet. Agreed. However, two pertinent points are: - I can replace the call to f1 by some statically indeterminate boolean condition that does not involve any function call. So my basic point although details could vary. - It is this flow insensitivity that I dislike :-) I have been trying for over five years to do away with flow and context insensitivity without hampering efficiency. Now I know that avoiding them could actually aid efficiency, apart from the guaranteed benefit of precision :-) Uday.
Re: possible typo in gcc/java/expr.c at line 1053
On 10/11/2012 06:59 PM, Kenneth Zadeck wrote:
> this code looks bogus, i think that the "== INTEGER_CST" needs to disappear.
>
> tree
> build_newarray (int atype_value, tree length)
> {
>tree type_arg;
>
>tree prim_type = decode_newarray_type (atype_value);
>tree type
> = build_java_array_type (prim_type,
> host_integerp (length, 0) == INTEGER_CST
> ? tree_low_cst (length, 0) : -1);
>
Thanks, you're right. This bug was introduced by Kenner in March 2000!
Andrew.
encoding all aliases options in .opt files
Hi Joseph, I am trying to encode the relationship between Wstrict-aliasing and Wstrict-aliasing= in the .opt files, and the same for Wstrict-overflow and Wstrict-overflow=. However, the parameters of Alias() are taken as strings, so we get "3" and "WARN_STRICT_OVERFLOW_CONDITIONAL". Do you have a suggestion how to handle this? My next step would be to handle aliases also when internally generating options, so I can add EnabledBy(Wall) to Wstrict-aliasing. Does this sound ok to you? Cheers, Manuel. Wstrict-aliasing -Common Warning +Common Alias(Wstrict-aliasing=, 3, 0) Warn about code which might break strict aliasing rules Wstrict-aliasing= Common Joined RejectNegative UInteger Var(warn_strict_aliasing) Init(-1) Warning Warn about code which might break strict aliasing rules Wstrict-overflow -Common Warning +Common Alias(Wstrict-overflow=, WARN_STRICT_OVERFLOW_CONDITIONAL, 0) Warn about optimizations that assume that signed overflow is undefined
