* Question about alias or points-to analysis
@ 2020-05-06 10:24 Erick Ochoa
2020-05-06 12:25 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Erick Ochoa @ 2020-05-06 10:24 UTC (permalink / raw)
To: GCC Development; +Cc: Philipp Tomsich, Christoph Müllner
Hi,
I am trying to find out how to use the alias and/or points-to analysis
in GCC. Ideally, I would like to find a function that given an
allocation site, the return value is a set of pointers which may point
to memory allocated from that allocation site.
For example:
int
main(int argc, char** argv)
{
int a;
int *b = argc > 2 ? &a : NULL;
int *c = b;
}
Here, querying the allocation site corresponding to the declaration of
local variable "a", should return { "b", "c" }.
I've found the following documentation on Alias-Analysis [0] and two
source files[1][2] which seem to implement some (distinct?) alias analysis.
I am trying to keep the discussion a bit high level, otherwise I would
have a lot of questions, but given this C example, **how would someone
be able to use any of the alias analyses in GCC to determine that "b"
and "c" may-alias "a"?**
I compiled my example and placed an pass to experiment with alias
analysis at link time. (I include the patch at the end). This is the
gimple produced by the example above.
main (int argc, char * * argv)
{
int * c;
int * b;
int a;
int D.4170;
int * iftmp.0;
int * iftmp.0_1;
int * iftmp.0_3;
int * iftmp.0_4;
int _9;
<bb 2> :
if (argc_2(D) > 2)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
<bb 3> :
iftmp.0_4 = &a;
goto <bb 5>; [INV]
<bb 4> :
iftmp.0_3 = 0B;
<bb 5> :
# iftmp.0_1 = PHI <iftmp.0_4(3), iftmp.0_3(4)>
b_5 = iftmp.0_1;
c_6 = b_5;
a ={v} {CLOBBER};
_9 = 0;
<bb 6> :
<L3>:
return _9;
}
I include this example because looking at the Alias Analysis [0]
section, it mentions memory SSA form. But I do not see any #.MEM_n
assignments.
Furthermore, I made an equivalent code to the example of Memory SSA form
and I still don't see any Memory SSA forms:
```c
int i;
int foo()
{
i = 1;
return i;
}
```
```gimple
foo ()
{
int D.4164;
int _3;
<bb 2> :
i = 1;
_3 = i;
<bb 3> :
<L0>:
return _3;
}
```
So, I am not sure how the gimple shown on the Alias-analysis page is
produced. **Does anyone know why the gimple produced is not showing the
virtual SSA names?**
Afterwards, instead of looking at the virtual SSA names, I then focused
on finding out whether SSA_NAME_PTR_INFO but I found that it was not
set. **Do I need I need to run something to make sure that
SSA_NAME_PTR_INFO is set?** Maybe the example I chose for compilation
did not trigger the path for setting SSA_NAME_PTR_INFO. What would be an
example of some code that does set SSA_NAME_PTR_INFO?
Here is the patch, and in order to compile an example and dump the log:
/path/to/gcc -fdump-ipa-hello-world -fipa-hello-world a.c
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 543b477ff18..bc1af09cbf8 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1399,6 +1399,7 @@ OBJS = \
incpath.o \
init-regs.o \
internal-fn.o \
+ ipa-hello-world.o \
ipa-cp.o \
ipa-sra.o \
ipa-devirt.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index d33383b523c..09cabeb114d 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -3408,4 +3408,8 @@ fipa-ra
Common Report Var(flag_ipa_ra) Optimization
Use caller save register across calls if possible.
+fipa-hello-world
+Common Report Var(flag_ipa_hello_world) Optimization
+TBD
+
; This comment is to ensure we retain the blank line above.
diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
new file mode 100644
index 00000000000..00e276a4bd7
--- /dev/null
+++ b/gcc/ipa-hello-world.c
@@ -0,0 +1,126 @@
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple-expr.h"
+#include "predict.h"
+#include "alloc-pool.h"
+#include "tree-pass.h"
+#include "cgraph.h"
+#include "diagnostic.h"
+#include "fold-const.h"
+#include "gimple-fold.h"
+#include "symbol-summary.h"
+#include "tree-vrp.h"
+#include "ipa-prop.h"
+#include "tree-pretty-print.h"
+#include "tree-inline.h"
+#include "ipa-fnsummary.h"
+#include "ipa-utils.h"
+#include "tree-ssa-ccp.h"
+#include "stringpool.h"
+#include "attribs.h"
+#include "tree-ssa-alias.h"
+#include "tree-ssanames.h"
+#include "gimple.h"
+#include "cfg.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+
+void inline
+log(const char* const fmt, ...)
+{
+ if (!dump_file) return;
+
+ va_list args;
+ va_start(args, fmt);
+ vfprintf(dump_file, fmt, args);
+ va_end(args);
+}
+
+static void
+alias_experiment_gimple_body(const cgraph_node *cnode)
+{
+ gcc_assert(cnode);
+
+ function *func = DECL_STRUCT_FUNCTION(cnode->decl);
+
+ // We are looking first into SSA becaues of
+ // this documentation...
+ // Points-to and escape analysis.
+ // Points-to analysis builds a set of constraints from the GIMPLE SSA IL
+ // representing all pointer operations and facts we do or do not know
+ // about pointers. Solving this set of constraints yields a
conservatively
+ // correct solution for each pointer variable in the program (though
we are
+ // only interested in SSA name pointers) as to what it may possibly
point to.
+ // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
+
+ size_t j = 0;
+ tree var_decl = NULL;
+ FOR_EACH_LOCAL_DECL(func, j, var_decl)
+ {
+ const_tree identifier_node = DECL_NAME(var_decl);
+ if (!identifier_node) continue;
+ const char* const identifier_pointer =
IDENTIFIER_POINTER(identifier_node);
+ log("var_decl = %s\n", identifier_pointer);
+ if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break;
+ }
+
+ size_t i = 0;
+ tree ssa_name = NULL;
+ push_cfun(func);
+ FOR_EACH_SSA_NAME(i, ssa_name, cfun)
+ {
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name);
+ if (!pi) continue;
+ log("i have a pi");
+ pt_solution_includes(&pi->pt, var_decl);
+ }
+ pop_cfun();
+
+
+}
+
+static unsigned int
+iphw_execute()
+{
+ cgraph_node *node = NULL;
+ FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
+ {
+ alias_experiment_gimple_body (node);
+ }
+ return 0;
+}
+
+namespace {
+const pass_data pass_data_ipa_hello_world =
+{
+ SIMPLE_IPA_PASS,
+ "hello-world",
+ OPTGROUP_NONE,
+ TV_NONE,
+ (PROP_cfg | PROP_ssa),
+ 0,
+ 0,
+ TODO_rebuild_alias,
+ 0,
+};
+
+class pass_ipa_hello_world : public simple_ipa_opt_pass
+{
+public:
+ pass_ipa_hello_world (gcc::context *ctx)
+ : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
+ {}
+
+ virtual bool gate(function*) { return flag_ipa_hello_world; }
+ virtual unsigned execute (function*) { return iphw_execute(); }
+};
+} // anon namespace
+
+simple_ipa_opt_pass*
+make_pass_ipa_hello_world (gcc::context *ctx)
+{
+ return new pass_ipa_hello_world (ctx);
+}
diff --git a/gcc/passes.def b/gcc/passes.def
index 2bf2cb78fc5..66f333f81dc 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_ipa_profile);
NEXT_PASS (pass_ipa_icf);
NEXT_PASS (pass_ipa_devirt);
+ NEXT_PASS (pass_ipa_hello_world);
NEXT_PASS (pass_ipa_cp);
NEXT_PASS (pass_ipa_sra);
NEXT_PASS (pass_ipa_cdtor_merge);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index a1207a20a3c..377dda689cc 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary
(gcc::context *ctxt);
extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context
*ctxt);
extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary
(gcc::context *ctxt);
+extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
[0] https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
[1] tree-ssa-alias.c
[2] tree-ssa-structalias.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Question about alias or points-to analysis
2020-05-06 10:24 Question about alias or points-to analysis Erick Ochoa
@ 2020-05-06 12:25 ` Richard Biener
2020-05-06 13:04 ` Erick Ochoa
0 siblings, 1 reply; 6+ messages in thread
From: Richard Biener @ 2020-05-06 12:25 UTC (permalink / raw)
To: Erick Ochoa; +Cc: GCC Development, Philipp Tomsich, Christoph Müllner
On Wed, May 6, 2020 at 12:26 PM Erick Ochoa
<erick.ochoa@theobroma-systems.com> wrote:
>
> Hi,
>
> I am trying to find out how to use the alias and/or points-to analysis
> in GCC. Ideally, I would like to find a function that given an
> allocation site, the return value is a set of pointers which may point
> to memory allocated from that allocation site.
>
> For example:
>
> int
> main(int argc, char** argv)
> {
> int a;
> int *b = argc > 2 ? &a : NULL;
> int *c = b;
> }
>
> Here, querying the allocation site corresponding to the declaration of
> local variable "a", should return { "b", "c" }.
So that's a "reverse query" to that you are asking for below ...
> I've found the following documentation on Alias-Analysis [0] and two
> source files[1][2] which seem to implement some (distinct?) alias analysis.
>
> I am trying to keep the discussion a bit high level, otherwise I would
> have a lot of questions, but given this C example, **how would someone
> be able to use any of the alias analyses in GCC to determine that "b"
> and "c" may-alias "a"?**
... here? Otherwise for a pointer "b" you can query whether it may-alias
"a" by using ptr_deref_may_alias_decl_p (b, a) or of 'a' is not a decl
but a general reference there is ptr_deref_may_alias_ref_p_1
(not exported - there wasn't any need sofar).
> I compiled my example and placed an pass to experiment with alias
> analysis at link time. (I include the patch at the end). This is the
> gimple produced by the example above.
>
> main (int argc, char * * argv)
> {
> int * c;
> int * b;
> int a;
> int D.4170;
> int * iftmp.0;
> int * iftmp.0_1;
> int * iftmp.0_3;
> int * iftmp.0_4;
> int _9;
>
> <bb 2> :
> if (argc_2(D) > 2)
> goto <bb 3>; [INV]
> else
> goto <bb 4>; [INV]
>
> <bb 3> :
> iftmp.0_4 = &a;
> goto <bb 5>; [INV]
>
> <bb 4> :
> iftmp.0_3 = 0B;
>
> <bb 5> :
> # iftmp.0_1 = PHI <iftmp.0_4(3), iftmp.0_3(4)>
> b_5 = iftmp.0_1;
> c_6 = b_5;
> a ={v} {CLOBBER};
> _9 = 0;
>
> <bb 6> :
> <L3>:
> return _9;
>
> }
>
> I include this example because looking at the Alias Analysis [0]
> section, it mentions memory SSA form. But I do not see any #.MEM_n
> assignments.
You need to dump with the -vops modifier (to get virtual operands dumped).
And you can use the -alias modifier to dump points-to results.
> Furthermore, I made an equivalent code to the example of Memory SSA form
> and I still don't see any Memory SSA forms:
>
> ```c
> int i;
> int foo()
> {
> i = 1;
> return i;
> }
> ```
>
> ```gimple
> foo ()
> {
> int D.4164;
> int _3;
>
> <bb 2> :
> i = 1;
> _3 = i;
>
> <bb 3> :
> <L0>:
> return _3;
>
> }
> ```
>
> So, I am not sure how the gimple shown on the Alias-analysis page is
> produced. **Does anyone know why the gimple produced is not showing the
> virtual SSA names?**
>
> Afterwards, instead of looking at the virtual SSA names, I then focused
> on finding out whether SSA_NAME_PTR_INFO but I found that it was not
> set. **Do I need I need to run something to make sure that
> SSA_NAME_PTR_INFO is set?** Maybe the example I chose for compilation
> did not trigger the path for setting SSA_NAME_PTR_INFO. What would be an
> example of some code that does set SSA_NAME_PTR_INFO?
SSA_NAME_PTR_INFO is computed by points-to analysis, for a simple
IPA pass run at LTRANS time that will not be computed yet (it is not
streamed into the IL because it's not in a convenient form and it can be
and is re-computed early enough - just not for you ;)). Without LTO
the info should be still there from the early optimization pipeline computation.
Hope this helps,
Richard.
> Here is the patch, and in order to compile an example and dump the log:
>
> /path/to/gcc -fdump-ipa-hello-world -fipa-hello-world a.c
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 543b477ff18..bc1af09cbf8 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1399,6 +1399,7 @@ OBJS = \
> incpath.o \
> init-regs.o \
> internal-fn.o \
> + ipa-hello-world.o \
> ipa-cp.o \
> ipa-sra.o \
> ipa-devirt.o \
> diff --git a/gcc/common.opt b/gcc/common.opt
> index d33383b523c..09cabeb114d 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -3408,4 +3408,8 @@ fipa-ra
> Common Report Var(flag_ipa_ra) Optimization
> Use caller save register across calls if possible.
>
> +fipa-hello-world
> +Common Report Var(flag_ipa_hello_world) Optimization
> +TBD
> +
> ; This comment is to ensure we retain the blank line above.
> diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
> new file mode 100644
> index 00000000000..00e276a4bd7
> --- /dev/null
> +++ b/gcc/ipa-hello-world.c
> @@ -0,0 +1,126 @@
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "backend.h"
> +#include "tree.h"
> +#include "gimple-expr.h"
> +#include "predict.h"
> +#include "alloc-pool.h"
> +#include "tree-pass.h"
> +#include "cgraph.h"
> +#include "diagnostic.h"
> +#include "fold-const.h"
> +#include "gimple-fold.h"
> +#include "symbol-summary.h"
> +#include "tree-vrp.h"
> +#include "ipa-prop.h"
> +#include "tree-pretty-print.h"
> +#include "tree-inline.h"
> +#include "ipa-fnsummary.h"
> +#include "ipa-utils.h"
> +#include "tree-ssa-ccp.h"
> +#include "stringpool.h"
> +#include "attribs.h"
> +#include "tree-ssa-alias.h"
> +#include "tree-ssanames.h"
> +#include "gimple.h"
> +#include "cfg.h"
> +#include "gimple-iterator.h"
> +#include "gimple-ssa.h"
> +
> +void inline
> +log(const char* const fmt, ...)
> +{
> + if (!dump_file) return;
> +
> + va_list args;
> + va_start(args, fmt);
> + vfprintf(dump_file, fmt, args);
> + va_end(args);
> +}
> +
> +static void
> +alias_experiment_gimple_body(const cgraph_node *cnode)
> +{
> + gcc_assert(cnode);
> +
> + function *func = DECL_STRUCT_FUNCTION(cnode->decl);
> +
> + // We are looking first into SSA becaues of
> + // this documentation...
> + // Points-to and escape analysis.
> + // Points-to analysis builds a set of constraints from the GIMPLE SSA IL
> + // representing all pointer operations and facts we do or do not know
> + // about pointers. Solving this set of constraints yields a
> conservatively
> + // correct solution for each pointer variable in the program (though
> we are
> + // only interested in SSA name pointers) as to what it may possibly
> point to.
> + // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
> +
> + size_t j = 0;
> + tree var_decl = NULL;
> + FOR_EACH_LOCAL_DECL(func, j, var_decl)
> + {
> + const_tree identifier_node = DECL_NAME(var_decl);
> + if (!identifier_node) continue;
> + const char* const identifier_pointer =
> IDENTIFIER_POINTER(identifier_node);
> + log("var_decl = %s\n", identifier_pointer);
> + if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break;
> + }
> +
> + size_t i = 0;
> + tree ssa_name = NULL;
> + push_cfun(func);
> + FOR_EACH_SSA_NAME(i, ssa_name, cfun)
> + {
> + struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name);
> + if (!pi) continue;
> + log("i have a pi");
> + pt_solution_includes(&pi->pt, var_decl);
> + }
> + pop_cfun();
> +
> +
> +}
> +
> +static unsigned int
> +iphw_execute()
> +{
> + cgraph_node *node = NULL;
> + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
> + {
> + alias_experiment_gimple_body (node);
> + }
> + return 0;
> +}
> +
> +namespace {
> +const pass_data pass_data_ipa_hello_world =
> +{
> + SIMPLE_IPA_PASS,
> + "hello-world",
> + OPTGROUP_NONE,
> + TV_NONE,
> + (PROP_cfg | PROP_ssa),
> + 0,
> + 0,
> + TODO_rebuild_alias,
> + 0,
> +};
> +
> +class pass_ipa_hello_world : public simple_ipa_opt_pass
> +{
> +public:
> + pass_ipa_hello_world (gcc::context *ctx)
> + : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
> + {}
> +
> + virtual bool gate(function*) { return flag_ipa_hello_world; }
> + virtual unsigned execute (function*) { return iphw_execute(); }
> +};
> +} // anon namespace
> +
> +simple_ipa_opt_pass*
> +make_pass_ipa_hello_world (gcc::context *ctx)
> +{
> + return new pass_ipa_hello_world (ctx);
> +}
> diff --git a/gcc/passes.def b/gcc/passes.def
> index 2bf2cb78fc5..66f333f81dc 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see
> NEXT_PASS (pass_ipa_profile);
> NEXT_PASS (pass_ipa_icf);
> NEXT_PASS (pass_ipa_devirt);
> + NEXT_PASS (pass_ipa_hello_world);
> NEXT_PASS (pass_ipa_cp);
> NEXT_PASS (pass_ipa_sra);
> NEXT_PASS (pass_ipa_cdtor_merge);
> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> index a1207a20a3c..377dda689cc 100644
> --- a/gcc/tree-pass.h
> +++ b/gcc/tree-pass.h
> @@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary
> (gcc::context *ctxt);
> extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
> extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context
> *ctxt);
> extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary
> (gcc::context *ctxt);
> +extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
> extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
> extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
> extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
>
>
>
> [0] https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
> [1] tree-ssa-alias.c
> [2] tree-ssa-structalias.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Question about alias or points-to analysis
2020-05-06 12:25 ` Richard Biener
@ 2020-05-06 13:04 ` Erick Ochoa
2020-05-06 16:40 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Erick Ochoa @ 2020-05-06 13:04 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Development, Philipp Tomsich, Christoph Müllner
On 06/05/2020 14:25, Richard Biener wrote:
> On Wed, May 6, 2020 at 12:26 PM Erick Ochoa
> <erick.ochoa@theobroma-systems.com> wrote:
>>
>> Hi,
>>
>> I am trying to find out how to use the alias and/or points-to analysis
>> in GCC. Ideally, I would like to find a function that given an
>> allocation site, the return value is a set of pointers which may point
>> to memory allocated from that allocation site.
>>
>> For example:
>>
>> int
>> main(int argc, char** argv)
>> {
>> int a;
>> int *b = argc > 2 ? &a : NULL;
>> int *c = b;
>> }
>>
>> Here, querying the allocation site corresponding to the declaration of
>> local variable "a", should return { "b", "c" }.
>
> So that's a "reverse query" to that you are asking for below ...
>
>> I've found the following documentation on Alias-Analysis [0] and two
>> source files[1][2] which seem to implement some (distinct?) alias analysis.
>>
>> I am trying to keep the discussion a bit high level, otherwise I would
>> have a lot of questions, but given this C example, **how would someone
>> be able to use any of the alias analyses in GCC to determine that "b"
>> and "c" may-alias "a"?**
>
> ... here? Otherwise for a pointer "b" you can query whether it may-alias
> "a" by using ptr_deref_may_alias_decl_p (b, a) or of 'a' is not a decl
> but a general reference there is ptr_deref_may_alias_ref_p_1
> (not exported - there wasn't any need sofar).
Thanks Richard. I'll look into the Tree alias-oracle API.
>
>> I compiled my example and placed an pass to experiment with alias
>> analysis at link time. (I include the patch at the end). This is the
>> gimple produced by the example above.
>>
>> main (int argc, char * * argv)
>> {
>> int * c;
>> int * b;
>> int a;
>> int D.4170;
>> int * iftmp.0;
>> int * iftmp.0_1;
>> int * iftmp.0_3;
>> int * iftmp.0_4;
>> int _9;
>>
>> <bb 2> :
>> if (argc_2(D) > 2)
>> goto <bb 3>; [INV]
>> else
>> goto <bb 4>; [INV]
>>
>> <bb 3> :
>> iftmp.0_4 = &a;
>> goto <bb 5>; [INV]
>>
>> <bb 4> :
>> iftmp.0_3 = 0B;
>>
>> <bb 5> :
>> # iftmp.0_1 = PHI <iftmp.0_4(3), iftmp.0_3(4)>
>> b_5 = iftmp.0_1;
>> c_6 = b_5;
>> a ={v} {CLOBBER};
>> _9 = 0;
>>
>> <bb 6> :
>> <L3>:
>> return _9;
>>
>> }
>>
>> I include this example because looking at the Alias Analysis [0]
>> section, it mentions memory SSA form. But I do not see any #.MEM_n
>> assignments.
>
> You need to dump with the -vops modifier (to get virtual operands dumped).
> And you can use the -alias modifier to dump points-to results.
> >> Furthermore, I made an equivalent code to the example of Memory SSA form
>> and I still don't see any Memory SSA forms:
>>
>> ```c
>> int i;
>> int foo()
>> {
>> i = 1;
>> return i;
>> }
>> ```
>>
>> ```gimple
>> foo ()
>> {
>> int D.4164;
>> int _3;
>>
>> <bb 2> :
>> i = 1;
>> _3 = i;
>>
>> <bb 3> :
>> <L0>:
>> return _3;
>>
>> }
>> ```
>>
>> So, I am not sure how the gimple shown on the Alias-analysis page is
>> produced. **Does anyone know why the gimple produced is not showing the
>> virtual SSA names?**
>>
>> Afterwards, instead of looking at the virtual SSA names, I then focused
>> on finding out whether SSA_NAME_PTR_INFO but I found that it was not
>> set. **Do I need I need to run something to make sure that
>> SSA_NAME_PTR_INFO is set?** Maybe the example I chose for compilation
>> did not trigger the path for setting SSA_NAME_PTR_INFO. What would be an
>> example of some code that does set SSA_NAME_PTR_INFO?
>
> SSA_NAME_PTR_INFO is computed by points-to analysis, for a simple
> IPA pass run at LTRANS time that will not be computed yet (it is not
> streamed into the IL because it's not in a convenient form and it can be
> and is re-computed early enough - just not for you ;)). Without LTO
> the info should be still there from the early optimization pipeline computation.
>
So, does this mean that there's no alias information available at LTO?
Or are you saying that I should store alias information at LGEN time and
use it at WPA time to make my transformation plan and finally transform
at LTRANS time?
> Hope this helps,
> Richard.
>
>> Here is the patch, and in order to compile an example and dump the log:
>>
>> /path/to/gcc -fdump-ipa-hello-world -fipa-hello-world a.c
>>
>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>> index 543b477ff18..bc1af09cbf8 100644
>> --- a/gcc/Makefile.in
>> +++ b/gcc/Makefile.in
>> @@ -1399,6 +1399,7 @@ OBJS = \
>> incpath.o \
>> init-regs.o \
>> internal-fn.o \
>> + ipa-hello-world.o \
>> ipa-cp.o \
>> ipa-sra.o \
>> ipa-devirt.o \
>> diff --git a/gcc/common.opt b/gcc/common.opt
>> index d33383b523c..09cabeb114d 100644
>> --- a/gcc/common.opt
>> +++ b/gcc/common.opt
>> @@ -3408,4 +3408,8 @@ fipa-ra
>> Common Report Var(flag_ipa_ra) Optimization
>> Use caller save register across calls if possible.
>>
>> +fipa-hello-world
>> +Common Report Var(flag_ipa_hello_world) Optimization
>> +TBD
>> +
>> ; This comment is to ensure we retain the blank line above.
>> diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
>> new file mode 100644
>> index 00000000000..00e276a4bd7
>> --- /dev/null
>> +++ b/gcc/ipa-hello-world.c
>> @@ -0,0 +1,126 @@
>> +#include "config.h"
>> +#include "system.h"
>> +#include "coretypes.h"
>> +#include "backend.h"
>> +#include "tree.h"
>> +#include "gimple-expr.h"
>> +#include "predict.h"
>> +#include "alloc-pool.h"
>> +#include "tree-pass.h"
>> +#include "cgraph.h"
>> +#include "diagnostic.h"
>> +#include "fold-const.h"
>> +#include "gimple-fold.h"
>> +#include "symbol-summary.h"
>> +#include "tree-vrp.h"
>> +#include "ipa-prop.h"
>> +#include "tree-pretty-print.h"
>> +#include "tree-inline.h"
>> +#include "ipa-fnsummary.h"
>> +#include "ipa-utils.h"
>> +#include "tree-ssa-ccp.h"
>> +#include "stringpool.h"
>> +#include "attribs.h"
>> +#include "tree-ssa-alias.h"
>> +#include "tree-ssanames.h"
>> +#include "gimple.h"
>> +#include "cfg.h"
>> +#include "gimple-iterator.h"
>> +#include "gimple-ssa.h"
>> +
>> +void inline
>> +log(const char* const fmt, ...)
>> +{
>> + if (!dump_file) return;
>> +
>> + va_list args;
>> + va_start(args, fmt);
>> + vfprintf(dump_file, fmt, args);
>> + va_end(args);
>> +}
>> +
>> +static void
>> +alias_experiment_gimple_body(const cgraph_node *cnode)
>> +{
>> + gcc_assert(cnode);
>> +
>> + function *func = DECL_STRUCT_FUNCTION(cnode->decl);
>> +
>> + // We are looking first into SSA becaues of
>> + // this documentation...
>> + // Points-to and escape analysis.
>> + // Points-to analysis builds a set of constraints from the GIMPLE SSA IL
>> + // representing all pointer operations and facts we do or do not know
>> + // about pointers. Solving this set of constraints yields a
>> conservatively
>> + // correct solution for each pointer variable in the program (though
>> we are
>> + // only interested in SSA name pointers) as to what it may possibly
>> point to.
>> + // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
>> +
>> + size_t j = 0;
>> + tree var_decl = NULL;
>> + FOR_EACH_LOCAL_DECL(func, j, var_decl)
>> + {
>> + const_tree identifier_node = DECL_NAME(var_decl);
>> + if (!identifier_node) continue;
>> + const char* const identifier_pointer =
>> IDENTIFIER_POINTER(identifier_node);
>> + log("var_decl = %s\n", identifier_pointer);
>> + if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break;
>> + }
>> +
>> + size_t i = 0;
>> + tree ssa_name = NULL;
>> + push_cfun(func);
>> + FOR_EACH_SSA_NAME(i, ssa_name, cfun)
>> + {
>> + struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name);
>> + if (!pi) continue;
>> + log("i have a pi");
>> + pt_solution_includes(&pi->pt, var_decl);
>> + }
>> + pop_cfun();
>> +
>> +
>> +}
>> +
>> +static unsigned int
>> +iphw_execute()
>> +{
>> + cgraph_node *node = NULL;
>> + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
>> + {
>> + alias_experiment_gimple_body (node);
>> + }
>> + return 0;
>> +}
>> +
>> +namespace {
>> +const pass_data pass_data_ipa_hello_world =
>> +{
>> + SIMPLE_IPA_PASS,
>> + "hello-world",
>> + OPTGROUP_NONE,
>> + TV_NONE,
>> + (PROP_cfg | PROP_ssa),
>> + 0,
>> + 0,
>> + TODO_rebuild_alias,
>> + 0,
>> +};
>> +
>> +class pass_ipa_hello_world : public simple_ipa_opt_pass
>> +{
>> +public:
>> + pass_ipa_hello_world (gcc::context *ctx)
>> + : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
>> + {}
>> +
>> + virtual bool gate(function*) { return flag_ipa_hello_world; }
>> + virtual unsigned execute (function*) { return iphw_execute(); }
>> +};
>> +} // anon namespace
>> +
>> +simple_ipa_opt_pass*
>> +make_pass_ipa_hello_world (gcc::context *ctx)
>> +{
>> + return new pass_ipa_hello_world (ctx);
>> +}
>> diff --git a/gcc/passes.def b/gcc/passes.def
>> index 2bf2cb78fc5..66f333f81dc 100644
>> --- a/gcc/passes.def
>> +++ b/gcc/passes.def
>> @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see
>> NEXT_PASS (pass_ipa_profile);
>> NEXT_PASS (pass_ipa_icf);
>> NEXT_PASS (pass_ipa_devirt);
>> + NEXT_PASS (pass_ipa_hello_world);
>> NEXT_PASS (pass_ipa_cp);
>> NEXT_PASS (pass_ipa_sra);
>> NEXT_PASS (pass_ipa_cdtor_merge);
>> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
>> index a1207a20a3c..377dda689cc 100644
>> --- a/gcc/tree-pass.h
>> +++ b/gcc/tree-pass.h
>> @@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary
>> (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
>> extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context
>> *ctxt);
>> extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary
>> (gcc::context *ctxt);
>> +extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
>> extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
>>
>>
>>
>> [0] https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
>> [1] tree-ssa-alias.c
>> [2] tree-ssa-structalias.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Question about alias or points-to analysis
2020-05-06 13:04 ` Erick Ochoa
@ 2020-05-06 16:40 ` Richard Biener
2020-05-06 19:25 ` Erick Ochoa
0 siblings, 1 reply; 6+ messages in thread
From: Richard Biener @ 2020-05-06 16:40 UTC (permalink / raw)
To: Erick Ochoa; +Cc: GCC Development, Philipp Tomsich, Christoph Müllner
On Wed, May 6, 2020 at 3:04 PM Erick Ochoa
<erick.ochoa@theobroma-systems.com> wrote:
>
>
>
> On 06/05/2020 14:25, Richard Biener wrote:
> > On Wed, May 6, 2020 at 12:26 PM Erick Ochoa
> > <erick.ochoa@theobroma-systems.com> wrote:
> >>
> >> Hi,
> >>
> >> I am trying to find out how to use the alias and/or points-to analysis
> >> in GCC. Ideally, I would like to find a function that given an
> >> allocation site, the return value is a set of pointers which may point
> >> to memory allocated from that allocation site.
> >>
> >> For example:
> >>
> >> int
> >> main(int argc, char** argv)
> >> {
> >> int a;
> >> int *b = argc > 2 ? &a : NULL;
> >> int *c = b;
> >> }
> >>
> >> Here, querying the allocation site corresponding to the declaration of
> >> local variable "a", should return { "b", "c" }.
> >
> > So that's a "reverse query" to that you are asking for below ...
> >
> >> I've found the following documentation on Alias-Analysis [0] and two
> >> source files[1][2] which seem to implement some (distinct?) alias analysis.
> >>
> >> I am trying to keep the discussion a bit high level, otherwise I would
> >> have a lot of questions, but given this C example, **how would someone
> >> be able to use any of the alias analyses in GCC to determine that "b"
> >> and "c" may-alias "a"?**
> >
> > ... here? Otherwise for a pointer "b" you can query whether it may-alias
> > "a" by using ptr_deref_may_alias_decl_p (b, a) or of 'a' is not a decl
> > but a general reference there is ptr_deref_may_alias_ref_p_1
> > (not exported - there wasn't any need sofar).
>
> Thanks Richard. I'll look into the Tree alias-oracle API.
>
> >
> >> I compiled my example and placed an pass to experiment with alias
> >> analysis at link time. (I include the patch at the end). This is the
> >> gimple produced by the example above.
> >>
> >> main (int argc, char * * argv)
> >> {
> >> int * c;
> >> int * b;
> >> int a;
> >> int D.4170;
> >> int * iftmp.0;
> >> int * iftmp.0_1;
> >> int * iftmp.0_3;
> >> int * iftmp.0_4;
> >> int _9;
> >>
> >> <bb 2> :
> >> if (argc_2(D) > 2)
> >> goto <bb 3>; [INV]
> >> else
> >> goto <bb 4>; [INV]
> >>
> >> <bb 3> :
> >> iftmp.0_4 = &a;
> >> goto <bb 5>; [INV]
> >>
> >> <bb 4> :
> >> iftmp.0_3 = 0B;
> >>
> >> <bb 5> :
> >> # iftmp.0_1 = PHI <iftmp.0_4(3), iftmp.0_3(4)>
> >> b_5 = iftmp.0_1;
> >> c_6 = b_5;
> >> a ={v} {CLOBBER};
> >> _9 = 0;
> >>
> >> <bb 6> :
> >> <L3>:
> >> return _9;
> >>
> >> }
> >>
> >> I include this example because looking at the Alias Analysis [0]
> >> section, it mentions memory SSA form. But I do not see any #.MEM_n
> >> assignments.
> >
> > You need to dump with the -vops modifier (to get virtual operands dumped).
> > And you can use the -alias modifier to dump points-to results.
> > >> Furthermore, I made an equivalent code to the example of Memory SSA form
> >> and I still don't see any Memory SSA forms:
> >>
> >> ```c
> >> int i;
> >> int foo()
> >> {
> >> i = 1;
> >> return i;
> >> }
> >> ```
> >>
> >> ```gimple
> >> foo ()
> >> {
> >> int D.4164;
> >> int _3;
> >>
> >> <bb 2> :
> >> i = 1;
> >> _3 = i;
> >>
> >> <bb 3> :
> >> <L0>:
> >> return _3;
> >>
> >> }
> >> ```
> >>
> >> So, I am not sure how the gimple shown on the Alias-analysis page is
> >> produced. **Does anyone know why the gimple produced is not showing the
> >> virtual SSA names?**
> >>
> >> Afterwards, instead of looking at the virtual SSA names, I then focused
> >> on finding out whether SSA_NAME_PTR_INFO but I found that it was not
> >> set. **Do I need I need to run something to make sure that
> >> SSA_NAME_PTR_INFO is set?** Maybe the example I chose for compilation
> >> did not trigger the path for setting SSA_NAME_PTR_INFO. What would be an
> >> example of some code that does set SSA_NAME_PTR_INFO?
> >
> > SSA_NAME_PTR_INFO is computed by points-to analysis, for a simple
> > IPA pass run at LTRANS time that will not be computed yet (it is not
> > streamed into the IL because it's not in a convenient form and it can be
> > and is re-computed early enough - just not for you ;)). Without LTO
> > the info should be still there from the early optimization pipeline computation.
> >
>
> So, does this mean that there's no alias information available at LTO?
> Or are you saying that I should store alias information at LGEN time and
> use it at WPA time to make my transformation plan and finally transform
> at LTRANS time?
There is no points-to information available during WPA. There is no
points-to information during LTRANS until pass_build_alias is run
which is before the first user (if you exclude your simple IPA pass).
If you need points-to information at WPA you either need to compute it
(it looks like you need to stream in function bodies anyway to use it,
so you could simply call compute_may_aliases on each function) or
what seems to be a better strathegy try to compute as much as
possible during IPA analysis and do final verification at LTRANS stage.
If that's possible of course depends on the exact things you need to do.
Richard.
> > Hope this helps,
> > Richard.
> >
> >> Here is the patch, and in order to compile an example and dump the log:
> >>
> >> /path/to/gcc -fdump-ipa-hello-world -fipa-hello-world a.c
> >>
> >> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> >> index 543b477ff18..bc1af09cbf8 100644
> >> --- a/gcc/Makefile.in
> >> +++ b/gcc/Makefile.in
> >> @@ -1399,6 +1399,7 @@ OBJS = \
> >> incpath.o \
> >> init-regs.o \
> >> internal-fn.o \
> >> + ipa-hello-world.o \
> >> ipa-cp.o \
> >> ipa-sra.o \
> >> ipa-devirt.o \
> >> diff --git a/gcc/common.opt b/gcc/common.opt
> >> index d33383b523c..09cabeb114d 100644
> >> --- a/gcc/common.opt
> >> +++ b/gcc/common.opt
> >> @@ -3408,4 +3408,8 @@ fipa-ra
> >> Common Report Var(flag_ipa_ra) Optimization
> >> Use caller save register across calls if possible.
> >>
> >> +fipa-hello-world
> >> +Common Report Var(flag_ipa_hello_world) Optimization
> >> +TBD
> >> +
> >> ; This comment is to ensure we retain the blank line above.
> >> diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
> >> new file mode 100644
> >> index 00000000000..00e276a4bd7
> >> --- /dev/null
> >> +++ b/gcc/ipa-hello-world.c
> >> @@ -0,0 +1,126 @@
> >> +#include "config.h"
> >> +#include "system.h"
> >> +#include "coretypes.h"
> >> +#include "backend.h"
> >> +#include "tree.h"
> >> +#include "gimple-expr.h"
> >> +#include "predict.h"
> >> +#include "alloc-pool.h"
> >> +#include "tree-pass.h"
> >> +#include "cgraph.h"
> >> +#include "diagnostic.h"
> >> +#include "fold-const.h"
> >> +#include "gimple-fold.h"
> >> +#include "symbol-summary.h"
> >> +#include "tree-vrp.h"
> >> +#include "ipa-prop.h"
> >> +#include "tree-pretty-print.h"
> >> +#include "tree-inline.h"
> >> +#include "ipa-fnsummary.h"
> >> +#include "ipa-utils.h"
> >> +#include "tree-ssa-ccp.h"
> >> +#include "stringpool.h"
> >> +#include "attribs.h"
> >> +#include "tree-ssa-alias.h"
> >> +#include "tree-ssanames.h"
> >> +#include "gimple.h"
> >> +#include "cfg.h"
> >> +#include "gimple-iterator.h"
> >> +#include "gimple-ssa.h"
> >> +
> >> +void inline
> >> +log(const char* const fmt, ...)
> >> +{
> >> + if (!dump_file) return;
> >> +
> >> + va_list args;
> >> + va_start(args, fmt);
> >> + vfprintf(dump_file, fmt, args);
> >> + va_end(args);
> >> +}
> >> +
> >> +static void
> >> +alias_experiment_gimple_body(const cgraph_node *cnode)
> >> +{
> >> + gcc_assert(cnode);
> >> +
> >> + function *func = DECL_STRUCT_FUNCTION(cnode->decl);
> >> +
> >> + // We are looking first into SSA becaues of
> >> + // this documentation...
> >> + // Points-to and escape analysis.
> >> + // Points-to analysis builds a set of constraints from the GIMPLE SSA IL
> >> + // representing all pointer operations and facts we do or do not know
> >> + // about pointers. Solving this set of constraints yields a
> >> conservatively
> >> + // correct solution for each pointer variable in the program (though
> >> we are
> >> + // only interested in SSA name pointers) as to what it may possibly
> >> point to.
> >> + // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
> >> +
> >> + size_t j = 0;
> >> + tree var_decl = NULL;
> >> + FOR_EACH_LOCAL_DECL(func, j, var_decl)
> >> + {
> >> + const_tree identifier_node = DECL_NAME(var_decl);
> >> + if (!identifier_node) continue;
> >> + const char* const identifier_pointer =
> >> IDENTIFIER_POINTER(identifier_node);
> >> + log("var_decl = %s\n", identifier_pointer);
> >> + if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break;
> >> + }
> >> +
> >> + size_t i = 0;
> >> + tree ssa_name = NULL;
> >> + push_cfun(func);
> >> + FOR_EACH_SSA_NAME(i, ssa_name, cfun)
> >> + {
> >> + struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name);
> >> + if (!pi) continue;
> >> + log("i have a pi");
> >> + pt_solution_includes(&pi->pt, var_decl);
> >> + }
> >> + pop_cfun();
> >> +
> >> +
> >> +}
> >> +
> >> +static unsigned int
> >> +iphw_execute()
> >> +{
> >> + cgraph_node *node = NULL;
> >> + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
> >> + {
> >> + alias_experiment_gimple_body (node);
> >> + }
> >> + return 0;
> >> +}
> >> +
> >> +namespace {
> >> +const pass_data pass_data_ipa_hello_world =
> >> +{
> >> + SIMPLE_IPA_PASS,
> >> + "hello-world",
> >> + OPTGROUP_NONE,
> >> + TV_NONE,
> >> + (PROP_cfg | PROP_ssa),
> >> + 0,
> >> + 0,
> >> + TODO_rebuild_alias,
> >> + 0,
> >> +};
> >> +
> >> +class pass_ipa_hello_world : public simple_ipa_opt_pass
> >> +{
> >> +public:
> >> + pass_ipa_hello_world (gcc::context *ctx)
> >> + : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
> >> + {}
> >> +
> >> + virtual bool gate(function*) { return flag_ipa_hello_world; }
> >> + virtual unsigned execute (function*) { return iphw_execute(); }
> >> +};
> >> +} // anon namespace
> >> +
> >> +simple_ipa_opt_pass*
> >> +make_pass_ipa_hello_world (gcc::context *ctx)
> >> +{
> >> + return new pass_ipa_hello_world (ctx);
> >> +}
> >> diff --git a/gcc/passes.def b/gcc/passes.def
> >> index 2bf2cb78fc5..66f333f81dc 100644
> >> --- a/gcc/passes.def
> >> +++ b/gcc/passes.def
> >> @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see
> >> NEXT_PASS (pass_ipa_profile);
> >> NEXT_PASS (pass_ipa_icf);
> >> NEXT_PASS (pass_ipa_devirt);
> >> + NEXT_PASS (pass_ipa_hello_world);
> >> NEXT_PASS (pass_ipa_cp);
> >> NEXT_PASS (pass_ipa_sra);
> >> NEXT_PASS (pass_ipa_cdtor_merge);
> >> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> >> index a1207a20a3c..377dda689cc 100644
> >> --- a/gcc/tree-pass.h
> >> +++ b/gcc/tree-pass.h
> >> @@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary
> >> (gcc::context *ctxt);
> >> extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
> >> extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context
> >> *ctxt);
> >> extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary
> >> (gcc::context *ctxt);
> >> +extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
> >> extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
> >> extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
> >> extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
> >>
> >>
> >>
> >> [0] https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
> >> [1] tree-ssa-alias.c
> >> [2] tree-ssa-structalias.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Question about alias or points-to analysis
2020-05-06 16:40 ` Richard Biener
@ 2020-05-06 19:25 ` Erick Ochoa
2020-05-07 7:19 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Erick Ochoa @ 2020-05-06 19:25 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Development, Philipp Tomsich, Christoph Müllner
On 06/05/2020 18:40, Richard Biener wrote:
> On Wed, May 6, 2020 at 3:04 PM Erick Ochoa
> <erick.ochoa@theobroma-systems.com> wrote:
>>
>>
>>
>> On 06/05/2020 14:25, Richard Biener wrote:
>>> On Wed, May 6, 2020 at 12:26 PM Erick Ochoa
>>> <erick.ochoa@theobroma-systems.com> wrote:
>>>>
>>>> Hi,
>>>>
>>>> I am trying to find out how to use the alias and/or points-to analysis
>>>> in GCC. Ideally, I would like to find a function that given an
>>>> allocation site, the return value is a set of pointers which may point
>>>> to memory allocated from that allocation site.
>>>>
>>>> For example:
>>>>
>>>> int
>>>> main(int argc, char** argv)
>>>> {
>>>> int a;
>>>> int *b = argc > 2 ? &a : NULL;
>>>> int *c = b;
>>>> }
>>>>
>>>> Here, querying the allocation site corresponding to the declaration of
>>>> local variable "a", should return { "b", "c" }.
>>>
>>> So that's a "reverse query" to that you are asking for below ...
>>>
>>>> I've found the following documentation on Alias-Analysis [0] and two
>>>> source files[1][2] which seem to implement some (distinct?) alias analysis.
>>>>
>>>> I am trying to keep the discussion a bit high level, otherwise I would
>>>> have a lot of questions, but given this C example, **how would someone
>>>> be able to use any of the alias analyses in GCC to determine that "b"
>>>> and "c" may-alias "a"?**
>>>
>>> ... here? Otherwise for a pointer "b" you can query whether it may-alias
>>> "a" by using ptr_deref_may_alias_decl_p (b, a) or of 'a' is not a decl
>>> but a general reference there is ptr_deref_may_alias_ref_p_1
>>> (not exported - there wasn't any need sofar).
>>
>> Thanks Richard. I'll look into the Tree alias-oracle API.
>>
>>>
>>>> I compiled my example and placed an pass to experiment with alias
>>>> analysis at link time. (I include the patch at the end). This is the
>>>> gimple produced by the example above.
>>>>
>>>> main (int argc, char * * argv)
>>>> {
>>>> int * c;
>>>> int * b;
>>>> int a;
>>>> int D.4170;
>>>> int * iftmp.0;
>>>> int * iftmp.0_1;
>>>> int * iftmp.0_3;
>>>> int * iftmp.0_4;
>>>> int _9;
>>>>
>>>> <bb 2> :
>>>> if (argc_2(D) > 2)
>>>> goto <bb 3>; [INV]
>>>> else
>>>> goto <bb 4>; [INV]
>>>>
>>>> <bb 3> :
>>>> iftmp.0_4 = &a;
>>>> goto <bb 5>; [INV]
>>>>
>>>> <bb 4> :
>>>> iftmp.0_3 = 0B;
>>>>
>>>> <bb 5> :
>>>> # iftmp.0_1 = PHI <iftmp.0_4(3), iftmp.0_3(4)>
>>>> b_5 = iftmp.0_1;
>>>> c_6 = b_5;
>>>> a ={v} {CLOBBER};
>>>> _9 = 0;
>>>>
>>>> <bb 6> :
>>>> <L3>:
>>>> return _9;
>>>>
>>>> }
>>>>
>>>> I include this example because looking at the Alias Analysis [0]
>>>> section, it mentions memory SSA form. But I do not see any #.MEM_n
>>>> assignments.
>>>
>>> You need to dump with the -vops modifier (to get virtual operands dumped).
>>> And you can use the -alias modifier to dump points-to results.
>>> >> Furthermore, I made an equivalent code to the example of Memory SSA form
>>>> and I still don't see any Memory SSA forms:
>>>>
>>>> ```c
>>>> int i;
>>>> int foo()
>>>> {
>>>> i = 1;
>>>> return i;
>>>> }
>>>> ```
>>>>
>>>> ```gimple
>>>> foo ()
>>>> {
>>>> int D.4164;
>>>> int _3;
>>>>
>>>> <bb 2> :
>>>> i = 1;
>>>> _3 = i;
>>>>
>>>> <bb 3> :
>>>> <L0>:
>>>> return _3;
>>>>
>>>> }
>>>> ```
>>>>
>>>> So, I am not sure how the gimple shown on the Alias-analysis page is
>>>> produced. **Does anyone know why the gimple produced is not showing the
>>>> virtual SSA names?**
>>>>
>>>> Afterwards, instead of looking at the virtual SSA names, I then focused
>>>> on finding out whether SSA_NAME_PTR_INFO but I found that it was not
>>>> set. **Do I need I need to run something to make sure that
>>>> SSA_NAME_PTR_INFO is set?** Maybe the example I chose for compilation
>>>> did not trigger the path for setting SSA_NAME_PTR_INFO. What would be an
>>>> example of some code that does set SSA_NAME_PTR_INFO?
>>>
>>> SSA_NAME_PTR_INFO is computed by points-to analysis, for a simple
>>> IPA pass run at LTRANS time that will not be computed yet (it is not
>>> streamed into the IL because it's not in a convenient form and it can be
>>> and is re-computed early enough - just not for you ;)). Without LTO
>>> the info should be still there from the early optimization pipeline computation.
>>>
>>
>> So, does this mean that there's no alias information available at LTO?
>> Or are you saying that I should store alias information at LGEN time and
>> use it at WPA time to make my transformation plan and finally transform
>> at LTRANS time?
>
> There is no points-to information available during WPA. There is no
> points-to information during LTRANS until pass_build_alias is run
> which is before the first user (if you exclude your simple IPA pass).
>
> If you need points-to information at WPA you either need to compute it
> (it looks like you need to stream in function bodies anyway to use it,
> so you could simply call compute_may_aliases on each function) or
> what seems to be a better strathegy try to compute as much as
> possible during IPA analysis and do final verification at LTRANS stage.
> If that's possible of course depends on the exact things you need to do.
>
> Richard.
Thanks Richard!
I understood one of the two approaches you discuss here. It is indeed
simple to call compute_may_aliases on each of the functions. However, I
do not understand what you mean by "compute as much as possible during
IPA analaysis". Can you please elaborate?
For "compute" do you mean computing the may-points to set on my own?
Perhaps using some of GCC's infrastructure as a foundation? Or do you
also mean calling compute_may_aliases on each function?
By "during IPA analysis" which of the three stages of IPA analysis do
you mean? Do you mean WPA or LGEN?
If I understand correctly, the final verification at LTRANS might be
needed because earlier IPA passes might have transformed the functions.
And our points-to information might be outdated. Is this correct?
Also, what about ipa_pta?
>
>>> Hope this helps,
>>> Richard.
>>>
>>>> Here is the patch, and in order to compile an example and dump the log:
>>>>
>>>> /path/to/gcc -fdump-ipa-hello-world -fipa-hello-world a.c
>>>>
>>>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>>>> index 543b477ff18..bc1af09cbf8 100644
>>>> --- a/gcc/Makefile.in
>>>> +++ b/gcc/Makefile.in
>>>> @@ -1399,6 +1399,7 @@ OBJS = \
>>>> incpath.o \
>>>> init-regs.o \
>>>> internal-fn.o \
>>>> + ipa-hello-world.o \
>>>> ipa-cp.o \
>>>> ipa-sra.o \
>>>> ipa-devirt.o \
>>>> diff --git a/gcc/common.opt b/gcc/common.opt
>>>> index d33383b523c..09cabeb114d 100644
>>>> --- a/gcc/common.opt
>>>> +++ b/gcc/common.opt
>>>> @@ -3408,4 +3408,8 @@ fipa-ra
>>>> Common Report Var(flag_ipa_ra) Optimization
>>>> Use caller save register across calls if possible.
>>>>
>>>> +fipa-hello-world
>>>> +Common Report Var(flag_ipa_hello_world) Optimization
>>>> +TBD
>>>> +
>>>> ; This comment is to ensure we retain the blank line above.
>>>> diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
>>>> new file mode 100644
>>>> index 00000000000..00e276a4bd7
>>>> --- /dev/null
>>>> +++ b/gcc/ipa-hello-world.c
>>>> @@ -0,0 +1,126 @@
>>>> +#include "config.h"
>>>> +#include "system.h"
>>>> +#include "coretypes.h"
>>>> +#include "backend.h"
>>>> +#include "tree.h"
>>>> +#include "gimple-expr.h"
>>>> +#include "predict.h"
>>>> +#include "alloc-pool.h"
>>>> +#include "tree-pass.h"
>>>> +#include "cgraph.h"
>>>> +#include "diagnostic.h"
>>>> +#include "fold-const.h"
>>>> +#include "gimple-fold.h"
>>>> +#include "symbol-summary.h"
>>>> +#include "tree-vrp.h"
>>>> +#include "ipa-prop.h"
>>>> +#include "tree-pretty-print.h"
>>>> +#include "tree-inline.h"
>>>> +#include "ipa-fnsummary.h"
>>>> +#include "ipa-utils.h"
>>>> +#include "tree-ssa-ccp.h"
>>>> +#include "stringpool.h"
>>>> +#include "attribs.h"
>>>> +#include "tree-ssa-alias.h"
>>>> +#include "tree-ssanames.h"
>>>> +#include "gimple.h"
>>>> +#include "cfg.h"
>>>> +#include "gimple-iterator.h"
>>>> +#include "gimple-ssa.h"
>>>> +
>>>> +void inline
>>>> +log(const char* const fmt, ...)
>>>> +{
>>>> + if (!dump_file) return;
>>>> +
>>>> + va_list args;
>>>> + va_start(args, fmt);
>>>> + vfprintf(dump_file, fmt, args);
>>>> + va_end(args);
>>>> +}
>>>> +
>>>> +static void
>>>> +alias_experiment_gimple_body(const cgraph_node *cnode)
>>>> +{
>>>> + gcc_assert(cnode);
>>>> +
>>>> + function *func = DECL_STRUCT_FUNCTION(cnode->decl);
>>>> +
>>>> + // We are looking first into SSA becaues of
>>>> + // this documentation...
>>>> + // Points-to and escape analysis.
>>>> + // Points-to analysis builds a set of constraints from the GIMPLE SSA IL
>>>> + // representing all pointer operations and facts we do or do not know
>>>> + // about pointers. Solving this set of constraints yields a
>>>> conservatively
>>>> + // correct solution for each pointer variable in the program (though
>>>> we are
>>>> + // only interested in SSA name pointers) as to what it may possibly
>>>> point to.
>>>> + // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
>>>> +
>>>> + size_t j = 0;
>>>> + tree var_decl = NULL;
>>>> + FOR_EACH_LOCAL_DECL(func, j, var_decl)
>>>> + {
>>>> + const_tree identifier_node = DECL_NAME(var_decl);
>>>> + if (!identifier_node) continue;
>>>> + const char* const identifier_pointer =
>>>> IDENTIFIER_POINTER(identifier_node);
>>>> + log("var_decl = %s\n", identifier_pointer);
>>>> + if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break;
>>>> + }
>>>> +
>>>> + size_t i = 0;
>>>> + tree ssa_name = NULL;
>>>> + push_cfun(func);
>>>> + FOR_EACH_SSA_NAME(i, ssa_name, cfun)
>>>> + {
>>>> + struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name);
>>>> + if (!pi) continue;
>>>> + log("i have a pi");
>>>> + pt_solution_includes(&pi->pt, var_decl);
>>>> + }
>>>> + pop_cfun();
>>>> +
>>>> +
>>>> +}
>>>> +
>>>> +static unsigned int
>>>> +iphw_execute()
>>>> +{
>>>> + cgraph_node *node = NULL;
>>>> + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
>>>> + {
>>>> + alias_experiment_gimple_body (node);
>>>> + }
>>>> + return 0;
>>>> +}
>>>> +
>>>> +namespace {
>>>> +const pass_data pass_data_ipa_hello_world =
>>>> +{
>>>> + SIMPLE_IPA_PASS,
>>>> + "hello-world",
>>>> + OPTGROUP_NONE,
>>>> + TV_NONE,
>>>> + (PROP_cfg | PROP_ssa),
>>>> + 0,
>>>> + 0,
>>>> + TODO_rebuild_alias,
>>>> + 0,
>>>> +};
>>>> +
>>>> +class pass_ipa_hello_world : public simple_ipa_opt_pass
>>>> +{
>>>> +public:
>>>> + pass_ipa_hello_world (gcc::context *ctx)
>>>> + : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
>>>> + {}
>>>> +
>>>> + virtual bool gate(function*) { return flag_ipa_hello_world; }
>>>> + virtual unsigned execute (function*) { return iphw_execute(); }
>>>> +};
>>>> +} // anon namespace
>>>> +
>>>> +simple_ipa_opt_pass*
>>>> +make_pass_ipa_hello_world (gcc::context *ctx)
>>>> +{
>>>> + return new pass_ipa_hello_world (ctx);
>>>> +}
>>>> diff --git a/gcc/passes.def b/gcc/passes.def
>>>> index 2bf2cb78fc5..66f333f81dc 100644
>>>> --- a/gcc/passes.def
>>>> +++ b/gcc/passes.def
>>>> @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see
>>>> NEXT_PASS (pass_ipa_profile);
>>>> NEXT_PASS (pass_ipa_icf);
>>>> NEXT_PASS (pass_ipa_devirt);
>>>> + NEXT_PASS (pass_ipa_hello_world);
>>>> NEXT_PASS (pass_ipa_cp);
>>>> NEXT_PASS (pass_ipa_sra);
>>>> NEXT_PASS (pass_ipa_cdtor_merge);
>>>> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
>>>> index a1207a20a3c..377dda689cc 100644
>>>> --- a/gcc/tree-pass.h
>>>> +++ b/gcc/tree-pass.h
>>>> @@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary
>>>> (gcc::context *ctxt);
>>>> extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
>>>> extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context
>>>> *ctxt);
>>>> extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary
>>>> (gcc::context *ctxt);
>>>> +extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
>>>> extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
>>>> extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
>>>> extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
>>>>
>>>>
>>>>
>>>> [0] https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
>>>> [1] tree-ssa-alias.c
>>>> [2] tree-ssa-structalias.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Question about alias or points-to analysis
2020-05-06 19:25 ` Erick Ochoa
@ 2020-05-07 7:19 ` Richard Biener
0 siblings, 0 replies; 6+ messages in thread
From: Richard Biener @ 2020-05-07 7:19 UTC (permalink / raw)
To: Erick Ochoa; +Cc: GCC Development, Philipp Tomsich, Christoph Müllner
On Wed, May 6, 2020 at 9:25 PM Erick Ochoa
<erick.ochoa@theobroma-systems.com> wrote:
>
>
>
> On 06/05/2020 18:40, Richard Biener wrote:
> > On Wed, May 6, 2020 at 3:04 PM Erick Ochoa
> > <erick.ochoa@theobroma-systems.com> wrote:
> >>
> >>
> >>
> >> On 06/05/2020 14:25, Richard Biener wrote:
> >>> On Wed, May 6, 2020 at 12:26 PM Erick Ochoa
> >>> <erick.ochoa@theobroma-systems.com> wrote:
> >>>>
> >>>> Hi,
> >>>>
> >>>> I am trying to find out how to use the alias and/or points-to analysis
> >>>> in GCC. Ideally, I would like to find a function that given an
> >>>> allocation site, the return value is a set of pointers which may point
> >>>> to memory allocated from that allocation site.
> >>>>
> >>>> For example:
> >>>>
> >>>> int
> >>>> main(int argc, char** argv)
> >>>> {
> >>>> int a;
> >>>> int *b = argc > 2 ? &a : NULL;
> >>>> int *c = b;
> >>>> }
> >>>>
> >>>> Here, querying the allocation site corresponding to the declaration of
> >>>> local variable "a", should return { "b", "c" }.
> >>>
> >>> So that's a "reverse query" to that you are asking for below ...
> >>>
> >>>> I've found the following documentation on Alias-Analysis [0] and two
> >>>> source files[1][2] which seem to implement some (distinct?) alias analysis.
> >>>>
> >>>> I am trying to keep the discussion a bit high level, otherwise I would
> >>>> have a lot of questions, but given this C example, **how would someone
> >>>> be able to use any of the alias analyses in GCC to determine that "b"
> >>>> and "c" may-alias "a"?**
> >>>
> >>> ... here? Otherwise for a pointer "b" you can query whether it may-alias
> >>> "a" by using ptr_deref_may_alias_decl_p (b, a) or of 'a' is not a decl
> >>> but a general reference there is ptr_deref_may_alias_ref_p_1
> >>> (not exported - there wasn't any need sofar).
> >>
> >> Thanks Richard. I'll look into the Tree alias-oracle API.
> >>
> >>>
> >>>> I compiled my example and placed an pass to experiment with alias
> >>>> analysis at link time. (I include the patch at the end). This is the
> >>>> gimple produced by the example above.
> >>>>
> >>>> main (int argc, char * * argv)
> >>>> {
> >>>> int * c;
> >>>> int * b;
> >>>> int a;
> >>>> int D.4170;
> >>>> int * iftmp.0;
> >>>> int * iftmp.0_1;
> >>>> int * iftmp.0_3;
> >>>> int * iftmp.0_4;
> >>>> int _9;
> >>>>
> >>>> <bb 2> :
> >>>> if (argc_2(D) > 2)
> >>>> goto <bb 3>; [INV]
> >>>> else
> >>>> goto <bb 4>; [INV]
> >>>>
> >>>> <bb 3> :
> >>>> iftmp.0_4 = &a;
> >>>> goto <bb 5>; [INV]
> >>>>
> >>>> <bb 4> :
> >>>> iftmp.0_3 = 0B;
> >>>>
> >>>> <bb 5> :
> >>>> # iftmp.0_1 = PHI <iftmp.0_4(3), iftmp.0_3(4)>
> >>>> b_5 = iftmp.0_1;
> >>>> c_6 = b_5;
> >>>> a ={v} {CLOBBER};
> >>>> _9 = 0;
> >>>>
> >>>> <bb 6> :
> >>>> <L3>:
> >>>> return _9;
> >>>>
> >>>> }
> >>>>
> >>>> I include this example because looking at the Alias Analysis [0]
> >>>> section, it mentions memory SSA form. But I do not see any #.MEM_n
> >>>> assignments.
> >>>
> >>> You need to dump with the -vops modifier (to get virtual operands dumped).
> >>> And you can use the -alias modifier to dump points-to results.
> >>> >> Furthermore, I made an equivalent code to the example of Memory SSA form
> >>>> and I still don't see any Memory SSA forms:
> >>>>
> >>>> ```c
> >>>> int i;
> >>>> int foo()
> >>>> {
> >>>> i = 1;
> >>>> return i;
> >>>> }
> >>>> ```
> >>>>
> >>>> ```gimple
> >>>> foo ()
> >>>> {
> >>>> int D.4164;
> >>>> int _3;
> >>>>
> >>>> <bb 2> :
> >>>> i = 1;
> >>>> _3 = i;
> >>>>
> >>>> <bb 3> :
> >>>> <L0>:
> >>>> return _3;
> >>>>
> >>>> }
> >>>> ```
> >>>>
> >>>> So, I am not sure how the gimple shown on the Alias-analysis page is
> >>>> produced. **Does anyone know why the gimple produced is not showing the
> >>>> virtual SSA names?**
> >>>>
> >>>> Afterwards, instead of looking at the virtual SSA names, I then focused
> >>>> on finding out whether SSA_NAME_PTR_INFO but I found that it was not
> >>>> set. **Do I need I need to run something to make sure that
> >>>> SSA_NAME_PTR_INFO is set?** Maybe the example I chose for compilation
> >>>> did not trigger the path for setting SSA_NAME_PTR_INFO. What would be an
> >>>> example of some code that does set SSA_NAME_PTR_INFO?
> >>>
> >>> SSA_NAME_PTR_INFO is computed by points-to analysis, for a simple
> >>> IPA pass run at LTRANS time that will not be computed yet (it is not
> >>> streamed into the IL because it's not in a convenient form and it can be
> >>> and is re-computed early enough - just not for you ;)). Without LTO
> >>> the info should be still there from the early optimization pipeline computation.
> >>>
> >>
> >> So, does this mean that there's no alias information available at LTO?
> >> Or are you saying that I should store alias information at LGEN time and
> >> use it at WPA time to make my transformation plan and finally transform
> >> at LTRANS time?
> >
> > There is no points-to information available during WPA. There is no
> > points-to information during LTRANS until pass_build_alias is run
> > which is before the first user (if you exclude your simple IPA pass).
> >
> > If you need points-to information at WPA you either need to compute it
> > (it looks like you need to stream in function bodies anyway to use it,
> > so you could simply call compute_may_aliases on each function) or
> > what seems to be a better strathegy try to compute as much as
> > possible during IPA analysis and do final verification at LTRANS stage.
> > If that's possible of course depends on the exact things you need to do.
> >
> > Richard.
>
> Thanks Richard!
>
> I understood one of the two approaches you discuss here. It is indeed
> simple to call compute_may_aliases on each of the functions. However, I
> do not understand what you mean by "compute as much as possible during
> IPA analaysis". Can you please elaborate?
I mean do what you want to do with alias/points-to info at IPA analysis
time (thus LGEN time, not WPA or LTRANS) and stream the result
of that analysis so you eventually do not need alias/points-to in its
'raw' form during WPA. (yes, your attached pass is a "simple IPA" pass
which only runs during LTRANS)
> For "compute" do you mean computing the may-points to set on my own?
> Perhaps using some of GCC's infrastructure as a foundation? Or do you
> also mean calling compute_may_aliases on each function?
>
> By "during IPA analysis" which of the three stages of IPA analysis do
> you mean? Do you mean WPA or LGEN?
LGEN, at LGEN points-to is available.
> If I understand correctly, the final verification at LTRANS might be
> needed because earlier IPA passes might have transformed the functions.
> And our points-to information might be outdated. Is this correct?
I was thinking of IPA ICF as an example - at LGEN ICF computes
a hash of each function body, at WPA it collects the functions with
the same hash (thus they optimistically are the same) and decides
to eventually merge them. But at LTRANS it has to prove they are
actually equal and not just hash collisions. This makes the streaming
overhead of the pass very small (one hash per function!) and the
WPA compute cheap (integer compare) defering the actual work
th LTRANS where function bodies are available again. (this is
a very simplified view of ICF)
> Also, what about ipa_pta?
Not sure what you mean here - IPA PTA is a simple IPA pass and
thus only runs on local (LTRANS) TU scope.
I suppose you're asking all these questions with struct-reorg in mind?
If so I'd sugget to try to compute a set of objects / allocations you
can track conservatively during LGEN, giving you a set of interesting
object candidates (and their types). That you somehow unify / transform
during WPA, likely involving pulling in some extra function bodies for
verification and commit the decision during LTRANS. LGEN would
give you something like "allocation A of type T done in function X,
escapes through calls to (external) function Y" and at WPA you
have to pull in Y and follow the allocation further. Of course you can
do all this fully at LTRANS as well. I'd _not_ use points-to or
alias analysis for this simply because I don't think it would scale
and at least for the transform phase you need "must points-to"
or "must alias" analysis anyway. So I'd implement a separate
analysis for tracking allocations.
Richard.
> >
> >>> Hope this helps,
> >>> Richard.
> >>>
> >>>> Here is the patch, and in order to compile an example and dump the log:
> >>>>
> >>>> /path/to/gcc -fdump-ipa-hello-world -fipa-hello-world a.c
> >>>>
> >>>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> >>>> index 543b477ff18..bc1af09cbf8 100644
> >>>> --- a/gcc/Makefile.in
> >>>> +++ b/gcc/Makefile.in
> >>>> @@ -1399,6 +1399,7 @@ OBJS = \
> >>>> incpath.o \
> >>>> init-regs.o \
> >>>> internal-fn.o \
> >>>> + ipa-hello-world.o \
> >>>> ipa-cp.o \
> >>>> ipa-sra.o \
> >>>> ipa-devirt.o \
> >>>> diff --git a/gcc/common.opt b/gcc/common.opt
> >>>> index d33383b523c..09cabeb114d 100644
> >>>> --- a/gcc/common.opt
> >>>> +++ b/gcc/common.opt
> >>>> @@ -3408,4 +3408,8 @@ fipa-ra
> >>>> Common Report Var(flag_ipa_ra) Optimization
> >>>> Use caller save register across calls if possible.
> >>>>
> >>>> +fipa-hello-world
> >>>> +Common Report Var(flag_ipa_hello_world) Optimization
> >>>> +TBD
> >>>> +
> >>>> ; This comment is to ensure we retain the blank line above.
> >>>> diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c
> >>>> new file mode 100644
> >>>> index 00000000000..00e276a4bd7
> >>>> --- /dev/null
> >>>> +++ b/gcc/ipa-hello-world.c
> >>>> @@ -0,0 +1,126 @@
> >>>> +#include "config.h"
> >>>> +#include "system.h"
> >>>> +#include "coretypes.h"
> >>>> +#include "backend.h"
> >>>> +#include "tree.h"
> >>>> +#include "gimple-expr.h"
> >>>> +#include "predict.h"
> >>>> +#include "alloc-pool.h"
> >>>> +#include "tree-pass.h"
> >>>> +#include "cgraph.h"
> >>>> +#include "diagnostic.h"
> >>>> +#include "fold-const.h"
> >>>> +#include "gimple-fold.h"
> >>>> +#include "symbol-summary.h"
> >>>> +#include "tree-vrp.h"
> >>>> +#include "ipa-prop.h"
> >>>> +#include "tree-pretty-print.h"
> >>>> +#include "tree-inline.h"
> >>>> +#include "ipa-fnsummary.h"
> >>>> +#include "ipa-utils.h"
> >>>> +#include "tree-ssa-ccp.h"
> >>>> +#include "stringpool.h"
> >>>> +#include "attribs.h"
> >>>> +#include "tree-ssa-alias.h"
> >>>> +#include "tree-ssanames.h"
> >>>> +#include "gimple.h"
> >>>> +#include "cfg.h"
> >>>> +#include "gimple-iterator.h"
> >>>> +#include "gimple-ssa.h"
> >>>> +
> >>>> +void inline
> >>>> +log(const char* const fmt, ...)
> >>>> +{
> >>>> + if (!dump_file) return;
> >>>> +
> >>>> + va_list args;
> >>>> + va_start(args, fmt);
> >>>> + vfprintf(dump_file, fmt, args);
> >>>> + va_end(args);
> >>>> +}
> >>>> +
> >>>> +static void
> >>>> +alias_experiment_gimple_body(const cgraph_node *cnode)
> >>>> +{
> >>>> + gcc_assert(cnode);
> >>>> +
> >>>> + function *func = DECL_STRUCT_FUNCTION(cnode->decl);
> >>>> +
> >>>> + // We are looking first into SSA becaues of
> >>>> + // this documentation...
> >>>> + // Points-to and escape analysis.
> >>>> + // Points-to analysis builds a set of constraints from the GIMPLE SSA IL
> >>>> + // representing all pointer operations and facts we do or do not know
> >>>> + // about pointers. Solving this set of constraints yields a
> >>>> conservatively
> >>>> + // correct solution for each pointer variable in the program (though
> >>>> we are
> >>>> + // only interested in SSA name pointers) as to what it may possibly
> >>>> point to.
> >>>> + // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
> >>>> +
> >>>> + size_t j = 0;
> >>>> + tree var_decl = NULL;
> >>>> + FOR_EACH_LOCAL_DECL(func, j, var_decl)
> >>>> + {
> >>>> + const_tree identifier_node = DECL_NAME(var_decl);
> >>>> + if (!identifier_node) continue;
> >>>> + const char* const identifier_pointer =
> >>>> IDENTIFIER_POINTER(identifier_node);
> >>>> + log("var_decl = %s\n", identifier_pointer);
> >>>> + if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break;
> >>>> + }
> >>>> +
> >>>> + size_t i = 0;
> >>>> + tree ssa_name = NULL;
> >>>> + push_cfun(func);
> >>>> + FOR_EACH_SSA_NAME(i, ssa_name, cfun)
> >>>> + {
> >>>> + struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name);
> >>>> + if (!pi) continue;
> >>>> + log("i have a pi");
> >>>> + pt_solution_includes(&pi->pt, var_decl);
> >>>> + }
> >>>> + pop_cfun();
> >>>> +
> >>>> +
> >>>> +}
> >>>> +
> >>>> +static unsigned int
> >>>> +iphw_execute()
> >>>> +{
> >>>> + cgraph_node *node = NULL;
> >>>> + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node)
> >>>> + {
> >>>> + alias_experiment_gimple_body (node);
> >>>> + }
> >>>> + return 0;
> >>>> +}
> >>>> +
> >>>> +namespace {
> >>>> +const pass_data pass_data_ipa_hello_world =
> >>>> +{
> >>>> + SIMPLE_IPA_PASS,
> >>>> + "hello-world",
> >>>> + OPTGROUP_NONE,
> >>>> + TV_NONE,
> >>>> + (PROP_cfg | PROP_ssa),
> >>>> + 0,
> >>>> + 0,
> >>>> + TODO_rebuild_alias,
> >>>> + 0,
> >>>> +};
> >>>> +
> >>>> +class pass_ipa_hello_world : public simple_ipa_opt_pass
> >>>> +{
> >>>> +public:
> >>>> + pass_ipa_hello_world (gcc::context *ctx)
> >>>> + : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx)
> >>>> + {}
> >>>> +
> >>>> + virtual bool gate(function*) { return flag_ipa_hello_world; }
> >>>> + virtual unsigned execute (function*) { return iphw_execute(); }
> >>>> +};
> >>>> +} // anon namespace
> >>>> +
> >>>> +simple_ipa_opt_pass*
> >>>> +make_pass_ipa_hello_world (gcc::context *ctx)
> >>>> +{
> >>>> + return new pass_ipa_hello_world (ctx);
> >>>> +}
> >>>> diff --git a/gcc/passes.def b/gcc/passes.def
> >>>> index 2bf2cb78fc5..66f333f81dc 100644
> >>>> --- a/gcc/passes.def
> >>>> +++ b/gcc/passes.def
> >>>> @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see
> >>>> NEXT_PASS (pass_ipa_profile);
> >>>> NEXT_PASS (pass_ipa_icf);
> >>>> NEXT_PASS (pass_ipa_devirt);
> >>>> + NEXT_PASS (pass_ipa_hello_world);
> >>>> NEXT_PASS (pass_ipa_cp);
> >>>> NEXT_PASS (pass_ipa_sra);
> >>>> NEXT_PASS (pass_ipa_cdtor_merge);
> >>>> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> >>>> index a1207a20a3c..377dda689cc 100644
> >>>> --- a/gcc/tree-pass.h
> >>>> +++ b/gcc/tree-pass.h
> >>>> @@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary
> >>>> (gcc::context *ctxt);
> >>>> extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt);
> >>>> extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context
> >>>> *ctxt);
> >>>> extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary
> >>>> (gcc::context *ctxt);
> >>>> +extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt);
> >>>> extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt);
> >>>> extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt);
> >>>> extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt);
> >>>>
> >>>>
> >>>>
> >>>> [0] https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html
> >>>> [1] tree-ssa-alias.c
> >>>> [2] tree-ssa-structalias.c
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2020-05-07 7:19 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-05-06 10:24 Question about alias or points-to analysis Erick Ochoa
2020-05-06 12:25 ` Richard Biener
2020-05-06 13:04 ` Erick Ochoa
2020-05-06 16:40 ` Richard Biener
2020-05-06 19:25 ` Erick Ochoa
2020-05-07 7:19 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).