1 Definition Bersntein's conditions [4] are a simple test for deciding if statements or operations can be interchanged without modifying the program results. The test applies to operations which read and write memory at well defined addresses. If u is an operation, let M(u) be the set of (adresses of) the memory cells it modifies, and R(u) the set of cells it reads. Operations u and v can be reordered if: M(u) ∩ M(v) = M(u) ∩ R(v) = R(u) ∩ M(v) = ∅ (1) If these conditions are met, one says that u and v commute or are independent. Note that in most languages, each operation writes at most one memory cell: W (u) is a singleton. However, there are exceptions: multiple and parallel assignments, vector assignments among others. The importance of this result stems from the fact that most program optimizations consist-or at least, involve-moving operations around. For instance, to improve cache performance, one must move all uses of a datum as near as possible to its definition. In parallel programming, if u and v are assigned to different threads or processors, their order of execution may be unpredictable, due to arbitrary decisions of a scheduler or to the presence of competing processes. In this case, if Bernstein's conditions are not met, u and v must be kept in the same thread. Checking Bernstein's conditions is easy for operations accessing scalars-but beware of aliases-, is more difficult for array accesses, and is almost impossible for pointer dereferencing.