  Cache coherence protocols based on self-invalidation and self-downgrade have
recently seen increased popularity due to their simplicity, potential
performance efficiency, and low energy consumption. However, such protocols
result in memory instruction reordering, thus causing extra program behaviors
that are often not intended by the programmers. We propose a novel formal model
that captures the semantics of programs running under such protocols, and
features a set of fences that interact with the coherence layer. Using the
model, we design an algorithm to analyze the reachability and check whether a
program satisfies a given safety property with the current set of fences. We
describe a method for insertion of optimal sets of fences that ensure
correctness of the program under such protocols. The method relies on a
counter-example guided fence insertion procedure. One feature of our method is
that it can handle a variety of fences (with different costs). This diversity
makes optimization more difficult since one has to optimize the total cost of
the inserted fences, rather than just their number. To demonstrate the strength
of our approach, we have implemented a prototype and run it on a wide range of
examples and benchmarks. We have also, using simulation, evaluated the
performance of the resulting fenced programs.
