start writing provenance-optimization blog post

[web.git] / personal / _posts / 2020-07-15-unused-data.md

diff --git a/personal/_posts/2020-07-15-unused-data.md b/personal/_posts/2020-07-15-unused-data.md
index afdfff91d7aae85c5e652e8642292bbfbcdc9949..dcd6b78ad9b28513550d882db6a2adf292a5f618 100644 (file)
--- a/personal/_posts/2020-07-15-unused-data.md
+++ b/personal/_posts/2020-07-15-unused-data.md
@@ -30,6 +30,9 @@ fn example(b: bool) -> i32 {
 
 I hope it is not very surprising that calling `example` on, e.g., `3` transmuted to `bool` is Undefined Behavior (UB).
 When compiling `if`, the compiler assumes that `0` and `1` are the only possible values; there is no saying what could go wrong when that assumption is violated.
 
 I hope it is not very surprising that calling `example` on, e.g., `3` transmuted to `bool` is Undefined Behavior (UB).
 When compiling `if`, the compiler assumes that `0` and `1` are the only possible values; there is no saying what could go wrong when that assumption is violated.

+For example, the compiler might use a [jump table](https://en.wikipedia.org/wiki/Branch_table); an out-of-bounds index in that table could literally execute any code, so there is no way to bound the behavior in that case.
+(This is a compiler-understood *validity invariant* that is fixed in the language specification, which is very different from a user-defined *safety invariant*.
+See [this earlier post]({% post_url 2018-08-22-two-kinds-of-invariants %}) for more details on that distinction.)

 
 What is less obvious is why calling `example` on `3` is UB even when there is no such `if` being executed.
 To understand why that is important, let us consider the following example:
 
 What is less obvious is why calling `example` on `3` is UB even when there is no such `if` being executed.
 To understand why that is important, let us consider the following example:


@@ -53,7 +56,7 @@ That transformation can be used to turn our `example` function into the followin
 {% highlight rust %}
 fn example(b: bool, num: u32) -> i32 {
   let mut acc = 0;
 {% highlight rust %}
 fn example(b: bool, num: u32) -> i32 {
   let mut acc = 0;

-  let incr = if b { 42 } else { 23 }
+  let incr = if b { 42 } else { 23 };

   for _i in 0..num {
     acc += incr;
   }
   for _i in 0..num {
     acc += incr;
   }


@@ -72,7 +75,9 @@ Before the optimization, that call was fine.
 After the optimization, that call is UB because we are doing `if b` where `b` is `3`.
 
 This is because loop-invariant code motion makes dead code live when the loop is not actually executed.
 After the optimization, that call is UB because we are doing `if b` where `b` is `3`.
 
 This is because loop-invariant code motion makes dead code live when the loop is not actually executed.

-To fix this, we could require the compiler to prove that the loop runs at least once, but in general that will be hard (and in `example` it is impossible, since `num` can indeed be `0`).
+(We can think of this as a form of "speculative execution", though entirely unrelated to CPU-level speculative execution.)
+To fix the optimization, we could require the compiler to prove that the loop runs at least once (i.e., we could avoid speculative execution), but in general that will be hard (and in `example` it is impossible, since `num` can indeed be `0`).
+Another option is to restructure the code to only compute `incr` if `num > 0`, but again this can be hard to do in general.

 So the alternative that Rust uses is to require that even "unused" data satisfies some basic validity.
 That makes `example(transmute(3u8), 0)` UB in *both* versions of `example`, and as such the optimization is correct for this input (and indeed for all possible inputs).
 
 So the alternative that Rust uses is to require that even "unused" data satisfies some basic validity.
 That makes `example(transmute(3u8), 0)` UB in *both* versions of `example`, and as such the optimization is correct for this input (and indeed for all possible inputs).