From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x642.google.com (mail-ej1-x642.google.com [IPv6:2a00:1450:4864:20::642]) by sourceware.org (Postfix) with ESMTPS id 5FF6F383F85E for ; Wed, 6 May 2020 12:25:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 5FF6F383F85E Received: by mail-ej1-x642.google.com with SMTP id s3so1143870eji.6 for ; Wed, 06 May 2020 05:25:48 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=5lnNm00QirKalGkvSAS/riFFQVqSMImGcomrafm/2Tk=; b=b92+r3OtQ6bdX9clzAR6dVK9KTObTP8+8qTUmNUVszKCV2U4G7V03xzp21E1QHO/7h 9+kDuxJc/4IdnNanuDdf5veWWS/RjD/v9ZKh7zGwvRx62kVRcY2fLahNndI8kT8h7WEw BE33uRfC+zMBHUCgtWmt72thoQN8YpIubAGae5OYjdumv7ufQVho1E434j5vLC2D/gmm MeQcYTJNiYA2U6K8QhfDYiL56Em1QQvOXgwWR0I37seNH/Ok2T81flRONHwWm8NAGr+K 3e0ksROJ9OWOp2v9y6Z+cERMxH4GgbSod9rfVeRGdLrPEaphulMtAATvuoTsIImDpRy/ PCew== X-Gm-Message-State: AGi0Pubgt5PjSYmbMwAcR4/koG+6gEtym10wNpnHJOioJpFQeZfdcXic YelbC1rh9qKTlfiyfkz8hRFXmUfUFuk1wdh5Pyo= X-Google-Smtp-Source: APiQypIbARerkIX7fFtd0valS/YJmjPS39VZ1ARAoc7yZX39AXXnKjh34lhOeiT8bLr9V6e/veOLBq3y3rOuP2XGSr8= X-Received: by 2002:a17:906:74c:: with SMTP id z12mr7315525ejb.87.1588767947207; Wed, 06 May 2020 05:25:47 -0700 (PDT) MIME-Version: 1.0 References: <27adfbd4-8b65-00bf-d5f9-89fafa423e10@theobroma-systems.com> In-Reply-To: <27adfbd4-8b65-00bf-d5f9-89fafa423e10@theobroma-systems.com> From: Richard Biener Date: Wed, 6 May 2020 14:25:36 +0200 Message-ID: Subject: Re: Question about alias or points-to analysis To: Erick Ochoa Cc: GCC Development , Philipp Tomsich , =?UTF-8?Q?Christoph_M=C3=BCllner?= Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-8.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 06 May 2020 12:25:50 -0000 On Wed, May 6, 2020 at 12:26 PM Erick Ochoa 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; > > : > if (argc_2(D) > 2) > goto ; [INV] > else > goto ; [INV] > > : > iftmp.0_4 = &a; > goto ; [INV] > > : > iftmp.0_3 = 0B; > > : > # iftmp.0_1 = PHI > b_5 = iftmp.0_1; > c_6 = b_5; > a ={v} {CLOBBER}; > _9 = 0; > > : > : > 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; > > : > i = 1; > _3 = i; > > : > : > 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