]>
Commit | Line | Data |
---|---|---|
041b39d2 XL |
1 | # Aliasing |
2 | ||
13cf67c4 | 3 | First off, let's get some important caveats out of the way: |
041b39d2 XL |
4 | |
5 | * We will be using the broadest possible definition of aliasing for the sake | |
6 | of discussion. Rust's definition will probably be more restricted to factor | |
7 | in mutations and liveness. | |
8 | ||
9 | * We will be assuming a single-threaded, interrupt-free, execution. We will also | |
10 | be ignoring things like memory-mapped hardware. Rust assumes these things | |
11 | don't happen unless you tell it otherwise. For more details, see the | |
12 | [Concurrency Chapter](concurrency.html). | |
13 | ||
14 | With that said, here's our working definition: variables and pointers *alias* | |
15 | if they refer to overlapping regions of memory. | |
16 | ||
136023e0 | 17 | ## Why Aliasing Matters |
041b39d2 XL |
18 | |
19 | So why should we care about aliasing? | |
20 | ||
21 | Consider this simple function: | |
22 | ||
23 | ```rust | |
24 | fn compute(input: &u32, output: &mut u32) { | |
25 | if *input > 10 { | |
26 | *output = 1; | |
27 | } | |
28 | if *input > 5 { | |
29 | *output *= 2; | |
30 | } | |
136023e0 | 31 | // remember that `output` will be `2` if `input > 10` |
041b39d2 XL |
32 | } |
33 | ``` | |
34 | ||
35 | We would *like* to be able to optimize it to the following function: | |
36 | ||
37 | ```rust | |
38 | fn compute(input: &u32, output: &mut u32) { | |
136023e0 | 39 | let cached_input = *input; // keep `*input` in a register |
041b39d2 | 40 | if cached_input > 10 { |
136023e0 XL |
41 | // If the input is greater than 10, the previous code would set the output to 1 and then double it, |
42 | // resulting in an output of 2 (because `>10` implies `>5`). | |
43 | // Here, we avoid the double assignment and just set it directly to 2. | |
44 | *output = 2; | |
041b39d2 XL |
45 | } else if cached_input > 5 { |
46 | *output *= 2; | |
47 | } | |
48 | } | |
49 | ``` | |
50 | ||
51 | In Rust, this optimization should be sound. For almost any other language, it | |
52 | wouldn't be (barring global analysis). This is because the optimization relies | |
53 | on knowing that aliasing doesn't occur, which most languages are fairly liberal | |
54 | with. Specifically, we need to worry about function arguments that make `input` | |
55 | and `output` overlap, such as `compute(&x, &mut x)`. | |
56 | ||
57 | With that input, we could get this execution: | |
58 | ||
136023e0 | 59 | <!-- ignore: expanded code --> |
041b39d2 XL |
60 | ```rust,ignore |
61 | // input == output == 0xabad1dea | |
62 | // *input == *output == 20 | |
63 | if *input > 10 { // true (*input == 20) | |
64 | *output = 1; // also overwrites *input, because they are the same | |
65 | } | |
66 | if *input > 5 { // false (*input == 1) | |
67 | *output *= 2; | |
68 | } | |
69 | // *input == *output == 1 | |
70 | ``` | |
71 | ||
72 | Our optimized function would produce `*output == 2` for this input, so the | |
73 | correctness of our optimization relies on this input being impossible. | |
74 | ||
75 | In Rust we know this input should be impossible because `&mut` isn't allowed to be | |
76 | aliased. So we can safely reject its possibility and perform this optimization. | |
77 | In most other languages, this input would be entirely possible, and must be considered. | |
78 | ||
79 | This is why alias analysis is important: it lets the compiler perform useful | |
80 | optimizations! Some examples: | |
81 | ||
82 | * keeping values in registers by proving no pointers access the value's memory | |
83 | * eliminating reads by proving some memory hasn't been written to since last we read it | |
84 | * eliminating writes by proving some memory is never read before the next write to it | |
85 | * moving or reordering reads and writes by proving they don't depend on each other | |
86 | ||
87 | These optimizations also tend to prove the soundness of bigger optimizations | |
88 | such as loop vectorization, constant propagation, and dead code elimination. | |
89 | ||
90 | In the previous example, we used the fact that `&mut u32` can't be aliased to prove | |
064997fb | 91 | that writes to `*output` can't possibly affect `*input`. This lets us cache `*input` |
041b39d2 XL |
92 | in a register, eliminating a read. |
93 | ||
532ac7d7 | 94 | By caching this read, we knew that the write in the `> 10` branch couldn't |
041b39d2 XL |
95 | affect whether we take the `> 5` branch, allowing us to also eliminate a |
96 | read-modify-write (doubling `*output`) when `*input > 10`. | |
97 | ||
98 | The key thing to remember about alias analysis is that writes are the primary | |
99 | hazard for optimizations. That is, the only thing that prevents us | |
100 | from moving a read to any other part of the program is the possibility of us | |
101 | re-ordering it with a write to the same location. | |
102 | ||
103 | For instance, we have no concern for aliasing in the following modified version | |
104 | of our function, because we've moved the only write to `*output` to the very | |
105 | end of our function. This allows us to freely reorder the reads of `*input` that | |
106 | occur before it: | |
107 | ||
108 | ```rust | |
109 | fn compute(input: &u32, output: &mut u32) { | |
110 | let mut temp = *output; | |
111 | if *input > 10 { | |
112 | temp = 1; | |
113 | } | |
114 | if *input > 5 { | |
115 | temp *= 2; | |
116 | } | |
117 | *output = temp; | |
118 | } | |
119 | ``` | |
120 | ||
064997fb FG |
121 | We're still relying on alias analysis to assume that `input` doesn't alias |
122 | `temp`, but the proof is much simpler: the value of a local variable can't be | |
041b39d2 XL |
123 | aliased by things that existed before it was declared. This is an assumption |
124 | every language freely makes, and so this version of the function could be | |
125 | optimized the way we want in any language. | |
126 | ||
127 | This is why the definition of "alias" that Rust will use likely involves some | |
128 | notion of liveness and mutation: we don't actually care if aliasing occurs if | |
129 | there aren't any actual writes to memory happening. | |
130 | ||
131 | Of course, a full aliasing model for Rust must also take into consideration things like | |
132 | function calls (which may mutate things we don't see), raw pointers (which have | |
133 | no aliasing requirements on their own), and UnsafeCell (which lets the referent | |
134 | of an `&` be mutated). |