Global variables (no testcase yet)

[timkaler]

We need a plan for automatically handling global variables without explicitly giving annotations. Can we summarize the challenges involved in handling globals here?

Here are a few preliminary thoughts that come to mind:

There are a few categories of global use (unsure if list is complete):
(a) globals that are constant for entire duration of program.
(b) globals that are precomputed during the program and constant for subsequent uses.
(c) globals acting as a scratch-space --- e.g. a static array of floats.
(d) globals for caching: e.g. a static lookup table.

(a),(b) can probably be identified via analysis; (c) can either be disallowed or handled by duplicating static storage; (d) is tricky because the data structure may be manipulated/initialized prior to the enzyme_autodiff call.

[wsmoses]

The problem is that for an arbitrary global we will likely have to be conservative and assume it is active (unless we prove it’s used otherwise in that function). If it is active, we need shadow memory for that global — which is presently done by looking up the annotation. So the two ways to resolve are to either prove that the global doesn’t impact derivatives or some other way to get the shadow

[wsmoses]

We could have a mode where you specify the mapping from active global to shadow and snything else is considered inactive

[timkaler]

I updated my original comment with a few cases/thoughts. I feel like we need to handle at least (a) and (b) in order to work with reasonably complex programs, and ideally we'd have a catch-all scheme that is able to, perhaps inefficiently and with specially defined behavior, handle the general case.

This is just brainstorming at the moment. Why can't we find all the globals in the program and then pass them through to different functions as arguments. We probably wouldn't actually do it that way, but what goes wrong?

[wsmoses]

I agree a and b could be handled by inter procedural active analysis, though you do need more information — namely knowledge whether the global is something you care about as being active.

I.e I might want the output of a function with respect to a global. We might be able to make assumptions that you only care about a set of global specified to resolve.

Also analysis I don’t think is sufficient for indirect calls wherein you don’t know how they touch global a priori.

This doesn’t mean we shouldn’t special case allow that, but something to be cognizant of.

As a truly general case passing in all global won’t work with indirect functions or functions in other translation units since you won’t be able to determine the globals used in advanced

[timkaler]

As a truly general case passing in all global won’t work with indirect functions or functions in other translation units since you won’t be able to determine the globals used in advanced

Indirect calls are a difficult case that I think we will want to consider out of scope, for now at least. Already, I think we have made compromises that have made indirect function calls incorrect. Disallowing indirect function calls seems to be a reasonable and clearly-defined way of restricting enzyme's scope. Similarly for functions in other translation units, although I think that case is easier to handle/work-around.

Continuing the brainstorming...

For (c) (statically allocated array of floats) I think the challenge here is initialization of the shadow data. We could disallow using global variables to provide "input gradients" to a top level enzyme_autodiff call. Then, I think it would be correct to zero-initialize the shadow data at the start of the top-level call.

For (d) things are more challenging. Let's consider a simpler case that's similar to (c). Instead of a statically allocated array of floats, we have a statically allocated pointer that points to a dynamically allocated array of floats. In this case, the actual dynamic allocation may be performed outside of the enzyme_autodiff call. It's unclear how one figures out how to allocate the data pointed-to by the shadow pointer.

As a side question, consider this case:

stdlike::map<int, float>* v = new stdlike::map();
stdlike::map<int, float>* d_v = new stdlike::map();

__enzyme_autodiff(foo, v, d_v, ...);

If the implementation stdlike::map is deterministic --- i.e. the internal structure is deterministic modulo memory addresses --- then I think things are fine. Suppose the maps use randomization, e.g. to maintain balance of a tree. If the maps are empty initially and in an identical starting state, then I think we are still fine (but require a careful argument) because we are going to record the random bits used for modifying v and use the same random bits to modify d_v. If the maps use randomization, and are not empty, then I think we need to require that they are in the same internal state.

A category of realistic codes that some of these examples are motivated by are those that use global data structures for handling memory allocation. These codes may need to be considered out-of-scope for now, but I'd prefer to hammer-down the precise, ideally minimal, set of excluded uses we require.