On Wed, May 6, 2020 at 12:26 PM Erick Ochoa
<[email protected]> 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
