Removing memory states from constant memory may prevent forwarding

[haved]

In order to keep the number of state edges manageable, and make it clear to later passes that memory is constant, we currently avoid routing any memory states for constant memory locations.

For many loads, this allows SVF to instead trace the address of the load back to a delta node. Since the memory is constant, the initializer of the delta node can be directly copied into the region of, and replace, the load node.

However, some loads from constant memory originate from imported symbols, such as in the following C program:

extern const int a;

int func()
{
    if(a != 0)
        return a;
    return 0;
}

If we were to route a memory state through all references to a, the load inside the if would be traced back to the first load, and be replaced through forwarding in the SVF pass. However, since we know that a is constant, there are no memory state edges in this function. Since a is imported, SVF is not able to replace all loads, but we would still like to replace the inner load.

The RVSDG looks like this:

There are multiple ways this could be resolved:

• Route memory states through constant memory after all, but skip propagating them through calls? Maybe do this but only for imported symbols, not symbols defined in with delta nodes? Not really a clean solution.
• Remove IO Barriers from these load operations, since we know that symbols are always legal to load from (at least as long as we do not apply unknown pointer offsets), and let NodePushOut + CommonNodeElimination handle the duplicated loads.
• Make CommonNodeElimination slightly smarter, so that it is able to detect common nodes across parent and subregions, and do forwarding directly without needing to push nodes out first? I think this might be the best solution, since it is not always legal to push nodes out.

[phate]

For the proposed solutions:

1. I do not like it as it basically goes against a lot what we have done so far. This would introduce a lot of overhead for very little gain. It does not feel clean at all.
2. I like that solution. The removal of unnecessary IOBarrier nodes should happen anyway. However, just because we have a load node without any memory states does not mean that we can hoist it out of a gamma node. A load node that is directly connected to null pointer also has no memory states. Thus, what would be required on top of it is a pass that annotates loads with something like "it always loads from a legal address".
3. I see the appeal for it, but it feels like we are all on a sudden mixing SVF stuff into CNE. This all in a sudden a partial redundancy elimination flavor to it.

I think what can happen is that we can implement a simple normalization / node reduction that removes those unnecessary IOBarrier nodes. This should be rather uncontroversial.

I think what we need then on top of it is some kind of "framework" that propagates information/values along the paths, something along the lines of value range propagation. This is not the first time this comes up in all fairness.

@caleridas I would love to hear your opinion here of how this could be handled?

[haved]

I would not describe making CNE able to recognize identical values across regions as "mixing it with SVF". Partial redundancy elimination, absolutely, but that is inherently related to CNE. It would not just apply to load forwarding.

I am a bit uncertain about the semantics of the IOBarrier, which I would like to figure out no matter how we choose to resolve this GitHub issue.

The IO Barrier was originally added because we needed to ensure that operations that may trap are not executed if they come after a non-terminating loop or non-returning call in the original program order. If this were the only task of the IOBarrier, it would be safe to push it out of gamma subregions.

However, we have also given the IOBarrier an additional meaning of "you may not speculatively execute the following node". To enforce these semantics, IOBarriers are prevented from being pushed out of gammas in the NodePushOut pass. This in turn keeps its dependents within the subregion.

My final mental model for speculation ends up being:

All RVSDG operations can be "speculated" (pushed out of a gamma subregion), when the following conditions are met:

• All operands are available in the parent region
• The operation does not consume the IO state (which keeps IO barriers inside gammas)
• The operation does not consume memory states, unless it is a load

The "unless it is a load" part is a bit unfortunate, as it adds special handling to NodePushOut (and maybe CNE/PRE as well in the future). However, moving a load out of a gamma needs special handling anyways to make the memory states correct, so there might not really be any magic workaround for this.

You suggest adding an annotation for marking a load as "allowed to be speculated", but I'm not sure that is necessary? If we already have the IOBarrier, then it should prevent speculating illegal loads. You bring up loads from NULL, but they should already have an IOBarrier, no?

With all of this in mind, my two questions are:

1. If there is an IOBarrier that consumes the value X, next to a gamma whose subregion contains an IOBarrier that also consumes X, should it always be OK to remove the inner IOBarrier and use the value from the outer IOBarrier instead?

2. If all subregions of a gamma contain the same IOBarrier, should we be allowed to move it out of the gamma, as there is no longer any "speculation"; The same IOBarrier will always be reached?

It would be very nice if the answer to these two questions were yes, as it would greatly simplify any future attempts at Partial Redundancy Elimination, and gives us a nice mental model for working with IOBarrier elimination in general.

One prerequisite for allowing this is that all IOBarriers on a value X have the same meaning:

• An IOBarrier on a pointer type always means "the pointer is dereferencable"
• An IOBarrier on an integer currently means "the integer is non-zero", since we use it for division.

These meanings are currently quite implicit, so it might make sense to make the IOBarrier operation take some sort of enum for indicating what kind of "check" it performs (even though no check is actually performed).

@phate @caleridas

[caleridas]

IOBarrier is indeed a bit overloaded, I am not fully clear about it's semantics. However the reasoning that it should not be there to begin with for constants is definitely sound.
If CNE can do what SVF does in other cases then that is sensible. If the aliases representation is perfect, then (almost) any redundant load ought to be caught by CNE (or at least some store-load-inverse-aware variant of it), but SVF can certainly do more things in the presence of more dynamic information.
Not sure what I can really comment about, but the proposed solutions look sensible.