Merging fails incorrectly while converting bc benchmark

[john-h-kastner]

In this example, merging the second declaration of free fails even though the declarations should be compatible. This affects the bc benchmark in PtrDist.

_Itype_for_any(T) void free(void * : itype(_Array_ptr<T>));
void b(void) {
  char **c;
  free(c);
}
void free(void *);

/home/john/b.c:6:6: fatal error: merging failed for 'free' due to conflicting types for parameter 0
void free(void *);
     ^

[john-h-kastner]

@kyleheadley, you've been working on the declaration merging code, so maybe you can figure out what's going wrong. I see the same error both on main and your PR branch.

[kyleheadley]

What's happening here is:

• The first free is constructed as normal, with 1 atom for the parameter
• Within b, free is called with c, modifying free's atom count
  • c has 2 atoms, free's parameter has 1
  • free is generic, so its parameter gets a new atom constrained to c's inner one
• a second free is declared, the parameter has 1 atom
• merge fails because of unequal atom count

As discussed today at status, there are 2 main solutions:

• when constraining c, succeed with the first pointer level and make no more constraints
  • Unfortunately, c will be _Array_ptr<_Ptr<char>> regardless of the code in the body of free, this changes our handling of generics
• when merging free, recognize that one is generic and allow it
  • Unfortunately, c will be constrained to free's parameter and transitively all other callers of free, this happens currently

We could also split the first conversion stage into two, merging functions in the first and constraining parameters in the second. I don't know how much work that would be, and it wouldn't change our current handling of generics.

@mwhicks1 could you weigh in on this? Any additional thoughts?

[mwhicks1]

• The first free is constructed as normal, with 1 atom for the parameter
• Within b, free is called with c, modifying free's atom count

Why are we modifying the called function's atom count based on the thing being passed in? This seems like a weakness to our handling of generics? Since free is a generic type, it should be used polymorphically. I.e., I should be able to call free(p) and free(q) when p and q have different atom counts (e.g., p is a _Ptr<int> while q is a _Ptr<_Ptr<int>>). The fact that I call with p should have no influence on whether/how I call with q.

• c has 2 atoms, free's parameter has 1
• free is generic, so its parameter gets a new atom constrained to c's inner one

Maybe I've misread what you mean by "modifies its atom count;" perhaps you mean that a new atom is created, for the call, which is then used to constrain the one attached to the declaration parameter's atom?

In any case, why is it the "inner" atom that's constrained? If I have

char **c;
free(c)

then it is the outer * that should be constrained (i.e., char ** is parsed (char *)* and it's the pointer outside the parens that matches the void * in free's parameter).

• a second free is declared, the parameter has 1 atom
• merge fails because of unequal atom count

As discussed today at status, there are 2 main solutions:

• when constraining c, succeed with the first pointer level and make no more constraints

  • Unfortunately, c will be _Array_ptr<_Ptr<char>> regardless of the code in the body of free, this changes our handling of generics

There is no "body of free" in this example. Can you elaborate on what you mean?

• when merging free, recognize that one is generic and allow it

  • Unfortunately, c will be constrained to free's parameter and transitively all other callers of free, this happens currently

This seems wrong, per my comment above about what a generic is: One caller's instantiation should not affect the instantiations at other callers.

We could also split the first conversion stage into two, merging functions in the first and constraining parameters in the second. I don't know how much work that would be, and it wouldn't change our current handling of generics.

@mwhicks1 could you weigh in on this? Any additional thoughts?

I like the idea of having a pass over the whole program that deals with merging, all at once, and only after that's done deals with generating constraints through the examination of definitions. How hard would this be to do?

[kyleheadley]

Why are we modifying the called function's atom count based on the thing being passed in? This seems like a weakness to our handling of generics?

Yes, this is our weakness. We don't have constraint variables per-call, but per function. But I suppose context-sensitivity is how to properly handle polymorphic function calls.

perhaps you mean that a new atom is created, for the call, which is then used to constrain the one attached to the declaration parameter's atom?

Do we have separate atoms for a call site? Regardless, in this case the parameter's atom count is changed when constrained to equality with the argument. Code execution reaches this point which allows size differences in Cvars if one is generic. It handles it with calls to getAtom which adds an atom when one more is requested of a generic than are available.

In any case, why is it the "inner" atom that's constrained?

It is constrained to the newly created atom(s), which pad out the pointer depth beyond the generic "T"

There is no "body of free" in this example. Can you elaborate on what you mean?

Sorry, this is hypothetical, since we don't have a larger example. A variable with more pointer levels than "T" should have them constrained to other variables within the body of a function it's an argument for. (If for example there's a dereference loop). If we do not add atoms to "T", we would lose this ability.

This seems wrong, per my comment above about what a generic is: One caller's instantiation should not affect the instantiations at other callers.

Unfortunately, this is the current situation. Our code handles polymorphism properly when "T" is a base type, but with additional pointer levels it over-constrains them all.

I like the idea of having a pass over the whole program that deals with merging, all at once, and only after that's done deals with generating constraints through the examination of definitions. How hard would this be to do?

This was a last-minute suggestion. I'll review some of that code today for an estimate.

[mwhicks1]

I guess one takeaway here is that for things to work as generally as Checked C will allow, we have to handle generic instantiations context-sensitively, and we are not doing that now. Maybe when/if that happens, this issue will go away. But I don't see how this issue gets fixed if fundamentally you cannot instantiate a polymorphic function with different (pointer) types.