Re: More questions on points-to analysis

[Richard Biener <richard.guenther@gmail.com>]

On Wed, Mar 17, 2021 at 11:34 AM Erick Ochoa via Gcc <gcc@gcc.gnu.org> wrote:
>
> Hello,
>
> I'm still trying to compare the solution generated from the
> intraprocedural points-to analysis in GCC against an external solver.
>
> Yesterday it was pointed out that "NULL is not conservatively
> correctly represented in the constraints". Can someone expand on this?
> To me this sounds like a couple of things:
> * even though malloc may return NULL, NULL is not added to the
> points-to sets of whatever variable is on the left hand side of the
> malloc call.
> * the process in GCC that generates the constraints for NULL somehow
> does not generate enough constraints to treat NULL conservatively and
> therefore there might be points-to sets which should contain NULL but
> don't. (However, doesn't this mean that feeding the constraints to an
> external solver should still give the same answers?)

Yes, there is an unknown number of places that get this "wrong".  Getting
it "right" wasn't needed until we started using pt->null for anything.

> * the process in GCC that generates the constraints for NULL works
> fine (i.e., feeding the constraints generated by GCC to an external
> solver should yield a conservatively correct answer) but the process
> that solves the constraints relaxes the solutions for the NULL
> constraint variable (i.e., GCC has deviated from the constraint
> solving algorithm somehow)

No, that part should work OK.

> Also, "at some point we decided to encode optimistic info into
> pt->null which means points-to now has to compute a conservatively
> correct pt->null." Doesn't this contradict itself? How is a pt->null
> first optimistically and now conservatively? Is what this is trying to
> say that:
>
> * NULL constraints were conservative first
> * pt->null optimistic first
> * Then conversion to SSA happened and NULL constraints became not
> conservatively represented in the constraints (effectively becoming
> somewhat optimistic)
> * To avoid NULL and pt->null be both unsafe, pt->null was changed to
> be conservative

The SSA points-to solution is what gets used, it is now populated not only
by PTA but also by range analysis which eventually sets pt->null to false.

PTA now simply sets pt->null to true as a conservative measure because
it cannot guarantee that when !pt->null the pointer is actually never NULL
(because of the above issues).

> I've been looking at find_what_vars_points_to and have changed my code
> which verifies the constraint points-to sets. Basically, I now find
> which variables have been collapsed and only for "real" constraint
> pointer variables I take a look at the points to solution struct.
> Before looking into vars, I take a look at the fields and compare the
> null, anything, escape, etc, against the id of the pointee-variable.
> Checking vars is slightly confusing for me at the moment, since it
> appears that there are at least 3 plausible ways of validating the
> solution (I haven't actually gotten there because assertions are being
> triggered).
>
> ```
> for (auto &output : *orel) {
>        int from_i;
>        int to_i;
>
>       // Since find_what_var_points_to
>       // doesn't change the solution for collapsed
>       // variables, only verify the answer for the real ones.
>        varinfo_t from_var = get_varinfo(from_i);
>        varinfo_t vi = get_varinfo (find (from_i));
>        if (from_var->id != vi->id) continue;
>        if (!from_var->may_have_pointers) continue;
>
>        // compute the pt_solution
>        pt_solution solution = find_what_var_points_to (cfun->decl, from_var);
>
>        // pointee variable according to external analysis
>        varinfo_t vi_to = get_varinfo(to_i);
>
>        // Since some artificial variables are stored in fields instead
> of the bitset
>        // assert based on field values.
>       // However you can see that I already had to disable some of the
> assertions.
>        if (vi_to->is_artificial_var)
>         {
>           if (vi_to->id == nothing_id)
>           {
>             gcc_assert(solution.null && vi_to->id == nothing_id);
>             continue;
>           }
>           else if (vi_to->id == escaped_id)
>             {
>               if (in_ipa_mode)
>               {
>                 gcc_assert(solution.ipa_escaped && vi_to->id == escaped_id);
>               }
>               else
>               {
>                 //gcc_assert(solution.escaped && vi_to->id == escaped_id);
>               }
>               continue;
>               /* Expand some special vars of ESCAPED in-place here. ??*/
>             }
>           // More...
>      }
>
>        if (solution.anything) continue;
>
>        bitmap vars = solution.vars;
>        if (!vars) continue;
>
>
>        if (dump_file) fprintf(dump_file, "SAME = %s\n",
> bitmap_bit_p(vars, DECL_PT_UID(vi_to->decl)) ? "true" : "false");
>        if (dump_file) fprintf(dump_file, "SAME2 = %s\n",
> bitmap_bit_p(vars, to_i) ? "true" : "false");
>        if (dump_file) fprintf(dump_file, "SAME3 = %s\n",
> bitmap_bit_p(from_var->solution, to_i) ? "true" : "false");
> ```
>
> Can someone help me figure out why even though I have a "real"
> variable and I compute its solution with the "find_what_var_points_to"
> method the solution does not have the fields that I expect to be set?
> (I would expect solution.escaped to be escaped if the pointee variable
> vi_to has an id = escaped_id).

solution.escaped is 1 if the pointer variable may point to everything
that escaped.  That is, solution.vars is really solution.vars |
cfun->gimple_df->escaped
(there is also ipa_escaped).  Have a look at pt_solution_includes_1 for an
outline how to interpret the fields when asking whether DECL is a member of
the points-to solution.

>
> And also, how is the DECL_PT_UID different from the varinfo id field?
> Shouldn't they be the same? It seems that during
> "find_what_var_points_to" DECL_PT_UID is being used to set the bit in
> the bitmap, but in previous instances it was the varinfo id offset?

The "SSA" points-to sets contain DECL_UIDs, not varinfo IDs which are
only transitional during points-to computation.  DECL_PT_UID maintains
the original UID also after inlining duplicates decls so the points-to solutions
remain valid even after inlining (or cloning, or IPA ICF, etc.).

Richard.