LEFT | RIGHT |
1 Static analysis tools | 1 Static analysis tools |
2 for Go code comprehension and refactoring | 2 for Go code comprehension and refactoring |
3 | 3 |
4 golang nyc meetup | 4 golang nyc meetup |
5 13 Nov 2014 | 5 13 Nov 2014 |
6 | 6 |
7 Alan Donovan | 7 Alan Donovan |
8 Google, New York | 8 Google, New York |
9 adonovan@google.com | 9 adonovan@google.com |
10 | 10 |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
93 Programs are lowered into Static Single-Assignment form (SSA): | 93 Programs are lowered into Static Single-Assignment form (SSA): |
94 - simplifies dataflow analyses since _reaching_ _definitions_ are implicit | 94 - simplifies dataflow analyses since _reaching_ _definitions_ are implicit |
95 - invented 1991, now mainstream (gcc, llvm) | 95 - invented 1991, now mainstream (gcc, llvm) |
96 | 96 |
97 All Go programs can be expressed using only ~30 basic instructions | 97 All Go programs can be expressed using only ~30 basic instructions |
98 | 98 |
99 Simple, explicit, high-level, high source fidelity | 99 Simple, explicit, high-level, high source fidelity |
100 | 100 |
101 .link http://godoc.org/golang.org/x/tools/go/ssa golang.org/x/tools/go/ssa | 101 .link http://godoc.org/golang.org/x/tools/go/ssa golang.org/x/tools/go/ssa |
102 | 102 |
103 llgo project is using go/ssa as a front-end for LLVM | 103 The llgo project is using go/ssa as a front-end for LLVM |
104 | 104 |
105 | 105 |
106 | 106 |
107 * Demo: ssadump | 107 * Demo: ssadump |
108 | 108 |
109 # Simple fibonacci function | 109 # Simple fibonacci function |
110 # % ssadump -build=F fib.go basic | 110 # % ssadump -build=F fib.go basic |
111 # % ssadump -build=FD fib.go debug info | 111 # % ssadump -build=FD fib.go debug info |
112 # % ssadump -test -run unicode toy interpreter | 112 # % ssadump -test -run unicode toy interpreter |
113 | 113 |
114 | 114 |
115 | 115 |
116 * go/pointer: pointer analysis | 116 * go/pointer: pointer analysis |
117 | 117 |
118 Pointers complicate reasoning about program behaviour | 118 Pointers complicate reasoning about program behaviour |
119 - functions may be called dynamically | 119 - functions may be called dynamically |
120 - a variable may be updated and accessed via different names ("aliases") | 120 - a variable may be updated and accessed via different names ("aliases") |
121 - runtime types are values too: `interface`, `reflect.Type` | 121 - runtime types are values too: `interface`, `reflect.Type` |
122 | 122 |
123 We use *pointer* *analysis* to answer the question: | 123 We use *pointer* *analysis* to answer the question: |
124 what variables might this pointer point to? | 124 which variables might this pointer point to? |
125 | 125 |
126 .link http://godoc.org/golang.org/x/tools/go/pointer golang.org/x/tools/go/point
er | 126 .link http://godoc.org/golang.org/x/tools/go/pointer golang.org/x/tools/go/point
er |
127 | 127 |
128 # comment on go's appropriateness for this analysis: | 128 # comment on go's appropriateness for this analysis: |
129 # (closed program---no dlopen, classloading, no generics, typesafe) | 129 # (closed program---no dlopen, classloading, no generics, typesafe) |
130 | 130 |
131 | 131 |
132 * Pointer analysis | 132 * Pointer analysis |
133 | 133 |
134 Let `pts(p)` be the _points-to_ _set_ of pointer p | 134 Let `pts(p)` be the _points-to_ _set_ of pointer p |
(...skipping 26 matching lines...) Expand all Loading... |
161 But we don't care! This isn't a compiler | 161 But we don't care! This isn't a compiler |
162 | 162 |
163 The constraint system is: | 163 The constraint system is: |
164 - *field-sensitive*: struct fields x.f and x.g have distinct solutions | 164 - *field-sensitive*: struct fields x.f and x.g have distinct solutions |
165 - *flow-insensitive*: the order of statements is ignored | 165 - *flow-insensitive*: the order of statements is ignored |
166 - *context-insensitive*: each function is analyzed only once | 166 - *context-insensitive*: each function is analyzed only once |
167 - *whole-program*: Go source is required for all dependencies | 167 - *whole-program*: Go source is required for all dependencies |
168 - *inclusion-based*: i.e. Andersen's analysis | 168 - *inclusion-based*: i.e. Andersen's analysis |
169 | 169 |
170 Optimization: don't make constraints for "uninteresting" types | 170 Optimization: don't make constraints for "uninteresting" types |
171 e.g. types not related to a one-shot Oracle query | 171 such as types not related to a one-shot Oracle query |
172 | 172 |
173 * Pointer analysis: pre-solver optimizations | 173 * Pointer analysis: pre-solver optimizations |
174 | 174 |
175 Constraint system for 124KLoC program (oracle) has: | 175 Constraint system for 124KLoC program (oracle) has: |
176 | 176 |
177 254,000 variables | 177 254,000 variables |
178 184,000 equations | 178 184,000 equations |
179 | 179 |
180 Solving phase is in O(|v|³), so pre-solver optimisation is crucial | 180 Solving phase is in O(|v|³), so pre-solver optimisation is crucial |
181 | 181 |
(...skipping 11 matching lines...) Expand all Loading... |
193 } | 193 } |
194 | 194 |
195 .image static-analysis/hvn.svg | 195 .image static-analysis/hvn.svg |
196 | 196 |
197 Hash-Value Numbering | 197 Hash-Value Numbering |
198 | 198 |
199 * Pointer analysis: solving | 199 * Pointer analysis: solving |
200 | 200 |
201 It's transitive closure of a graph, essentially | 201 It's transitive closure of a graph, essentially |
202 | 202 |
203 Lots of optimizations | 203 Lots of optimizations, for example: |
204 | 204 |
205 e.g. _sparse_bit_vectors_, a very compact representation for points-to sets | 205 _sparse_bit_vectors_, a very compact representation for points-to sets |
206 | 206 |
207 .link http://godoc.org/golang.org/x/tools/container/ints golang.org/x/tools/cont
ainer/ints | 207 .link http://godoc.org/golang.org/x/tools/container/ints golang.org/x/tools/cont
ainer/ints |
208 | 208 |
209 Solver log is >1GB. Debugging is fun. | 209 Solver log is >1GB. Debugging is fun. |
210 | 210 |
211 | 211 |
212 #* Sparse bit vector | 212 #* Sparse bit vector |
213 #`golang.org/x/tools/container/ints` | 213 #`golang.org/x/tools/container/ints` |
214 # | 214 # |
215 #.image sparsebitvector.svg | 215 #.image sparsebitvector.svg |
(...skipping 28 matching lines...) Expand all Loading... |
244 | 244 |
245 Sound: either a conflict is reported, or the refactoring preserves behaviour* | 245 Sound: either a conflict is reported, or the refactoring preserves behaviour* |
246 | 246 |
247 *except reflection | 247 *except reflection |
248 | 248 |
249 .link http://godoc.org/golang.org/x/tools/cmd/gorename golang.org/x/tools/cmd/go
rename | 249 .link http://godoc.org/golang.org/x/tools/cmd/gorename golang.org/x/tools/cmd/go
rename |
250 | 250 |
251 * Demo: gorename | 251 * Demo: gorename |
252 | 252 |
253 | 253 |
254 * eg: example-based refactoring | 254 * Example-based refactoring with eg |
255 | 255 |
256 A Go port of the Java _Refaster_ tool | 256 A Go port of the Java _Refaster_ tool |
257 | 257 |
258 A template specifies the pattern and replacement as Go expressions: | 258 A template specifies the pattern and replacement as Go expressions: |
259 | 259 |
260 package P | 260 package P |
261 | 261 |
262 import ( "errors"; "fmt" ) | 262 import ( "errors"; "fmt" ) |
263 | 263 |
264 func before(s string) error { return fmt.Errorf("%s", s) } | 264 func before(s string) error { return fmt.Errorf("%s", s) } |
265 func after(s string) error { return errors.New(s) } | 265 func after(s string) error { return errors.New(s) } |
266 | 266 |
267 Parameters are _wildcards_ | 267 Parameters are _wildcards_ |
268 | 268 |
269 % eg -t template.go <package> ... | 269 % eg -t template.go <package> ... |
270 | 270 |
271 .link http://godoc.org/golang.org/x/tools/cmd/eg golang.org/x/tools/cmd/eg | 271 .link http://godoc.org/golang.org/x/tools/cmd/eg golang.org/x/tools/cmd/eg |
272 | 272 |
273 * Demo: eg | 273 * Demo: eg |
274 | 274 |
275 * Conclusion | 275 * Conclusion |
276 | 276 |
277 From the outset, Go has been renowned for its tools: `go`, `gofmt` | 277 From the outset, Go has been renowned for its tools: `go`, `gofmt` |
278 | 278 |
279 We have many building blocks for sophisticated source analysis tools | 279 We have many building blocks for sophisticated source analysis tools |
280 | 280 |
281 What should we build next? | 281 What should we build next? |
LEFT | RIGHT |