How should we model the "side effects" of modulo and division operations?

[haved]

The issues with #526 are caused by the following situation:

#include <stdlib.h>

int x;

void foo() {
    exit(0);
}

int main() {
    int a = x;
    if (a == 0)
        foo();
    return 6 % a;
}

Using a build of jlm-opt from and executing the following commands:

clang -S -emit-llvm example.c -o example.ll -Xclang -disable-O0-optnone
opt -S --passes=mem2reg example.ll -o example-m2r.ll
jlm-opt example-m2r.ll -o example-jlm.ll
clang example-jlm.ll -o example.out
./example.out

The program terminates with SIGFPE (Floating Point Exception), as it attempts to do modulo by 0.

For reference, the definition of main in example-m2r.ll is

define dso_local i32 @main() #0 {
  %1 = load i32, ptr @x, align 4
  %2 = icmp eq i32 %1, 0
  br i1 %2, label %3, label %4

3:                                                ; preds = %0
  call void @foo()
  br label %4

4:                                                ; preds = %3, %0
  %5 = srem i32 6, %1
  ret i32 %5
}

We need to exit via the foo function to prevent LLVM from adding unreachable right below the call, but we could just as well imagine foo being an external function that somehow calls exit.

The RVSDG produced by jlm-opt ends up looking like

As you can see, the modulo operation BitSMod32 ends up neither higher nor lower in the DAG than the gamma containing the call. When the program is converted back into LLVM IR, it (more or less randomly) ends up like so:

define i32 @main() #0 {
bb0:
  %0 = load i32, ptr @x, align 4
  %1 = icmp eq i32 %0, 0
  %2 = srem i32 6, %0
  br i1 %1, label %bb2, label %bb1

bb1:                                              ; preds = %bb2, %bb0
  ret i32 %2

bb2:                                              ; preds = %bb0
  call void @foo()
  br label %bb1
}

This means the modulo by 0, which normally would never occur, happens before the terminating call to foo().

We somehow need to model the possible side effect of modulo and division by 0 sending a signal.

This raises a few questions:

• Should we use the I/O state edge to enforce the original sequence of operations? A signal is I/O in a sense.
• What about other things that raise signals? Dereferencing a NULL pointer typically raises a signal, but is at the same time undefined behavior, so it does not have to.
  • What are the rules for re-ordering memory operations around function calls? What do other compilers do?
  • Is division by 0 "undefined behavior" or is it mearly implementation defined?

@caleridas @phate @sjalander

[caleridas]

Division by 0 is UB, and UB is really only "UB" if it is reached in a program (i.e. if no execution path leads to, or an UB expression is not evaluated then it is irrelevant -- cf. also forced lazy evaluation for && and ||). Termination is an observable side effect of a program, so needs to be modelled and affects reachability. Reordering may obviously not introduce UB into a UB-free program (where UB-free as above conditioned on runtime control flow). Therefore yes, I think you would need to mark all operations that are conditionally-UB as sequentialized wrt to any effects concerning control flow, and if premature program exit is modelled using I/O state then conditionally-UB needs to be marked the same as well. That may also affect pointer dereferences.

Yes that gets rather nasty in practice, consider example 1:

*p = 0;
call_something();
*p = 42;

vs example 2:

call_something();
*p = 42;

Assuming that compiler would "know" that call_something does not read *p, then it would be allowed to reorder the assignment *p = 42 before the call in the first case, but not the second case. Reason: in the second case, the operation is masked by call_something which might be essential to establishing a pre-condition for the pointer dereference to be valid. In the first case OTOH *p = 0 establishes a precondition that the pointer dereference is valid and not actually dependent on call_something(). Therefore, the compiler might also reorder (and remove the redundant store).

This actually came practically biting at some point like this:

int a = *p;
// some code ...
if (p == nullptr) {
  // handle case of p being nullptr
}

The condition p == nullptr cannot hold due to the precondition of *p being valid and was statically optimized away (and caused a security issue).

[haved]

LLVM IR has a bunch of function / function call attributes like willreturn, nounwind, nofree and memory(none) etc., which help enable transformations across function call boundaries.

In our case, routing the I/O state through division and modulo is probably quite cheap. If a region contains multiple, the I/O state can be split up across them, like we do with loads that share memory state edges.

For memory operations, I am more inclined to use memory state edges to maintain the conservative ordering, rather than sending I/O states through all loads and stores.

Throwing out some more examples:

void foo();

static int test1(int* p) {
    *p = 7; // Can not be moved, but this case is already handled by memory state encoding
    foo();
    *p = 10; // Can not be moved, but already handled
    ....
}

int test2() {
    int* p = malloc(4); // This malloc is private to this function (even stronger guarantee than not escaping module)
    *p = 7; // Can be moved below, If p is NULL UB is triggered here already
    foo();
    *p = 10; // Can be moved above since we know p is not NULL
    ..
}

PROBLEM:

int test3() {
    int* p = malloc(4);
    foo();
    *p = 10; // Can not be moved above, as p might be NULL, which is only UB if foo terminates
    ...
}

int test4() {
    int* p = alloca(4);
    foo();
    *p = 10; // Can be moved above, since alloca can never be NULL
    ...
}

PROBLEM:

int test5(int x) {
    int* p = NULL;
    if (x < 10)
        p = &x;

    foo(x);
    *p = 10; // Can not be moved, as p might still be NULL
}

So from what I can tell the only examples that are not already correctly handled by (non-buggy) memory state encoding is the case where a function has its own private malloc, or when a pointer has multiple possible targets, one of which is NULL.

In all cases where a pointer has unknown origin, the memory state encoding will already conservatively assume that it points to something that the call is clobbering.

NULL is here of course a stand-in for any invalid pointer, such as a pointer that used to be valid but has since been freed. Memory state encoding will already ensure that a situation like the following is not a problem:

static int* q;
int test6() {
    q = malloc(4);
    *q = 8; // Can not be moved, as *q may be mod/ref, or no longer exist after foo
    foo();
    *q = 10; // Can not be moved either, as *q may be mod/ref by foo()
}

// Exported functions that foo() may call
void callback() {
    free(q);
}

void callback2() {
    *q = 20;
}

As far as I can tell, there are only two situations where NULL values appear, that are not already handled because the pointer is marked as "PointingToExternal" and thus handled conservatively.

• The result of a malloc
• The operation jlm::llvm::ConstantPointerNull

In the Alias Analysis, there is no concept of a NULL pointer, or any other "invalid" pointee for that matter. I would definitely not want to add a "memory location" that is called NULL, as that would create several edge cases (aliasing because two pointers both may target NULL, trying to extend the points-to-set of NULL during solving). At the very most there would be a flag, I think, added to pointers that may target NULL.

I think it might be better if the memory state encoding handles the NULL cases, as there appears to be very few of them. This would also allow the memory state encoding to "remove" the "might be NULL" flag as soon as a pointer is actually used for anything.

What do you think, @phate, @caleridas?

[phate]

I will reply in more detail later. I am not sure that I fully agree with all the examples you have drawn up (or I misunderstand something...) @haved

It seems we agree that the best way to solve the side-effect of the division/module operators is to implement another division/module operator that also takes an IO state. Those are used conservatively by the front-end when an RVSDG is created. Once we can assert that a modulo/division operator can not have a zero as second operand, we can replace them with the side-effect free equivalent. Does this make sense @haved @caleridas? Any concerns?