Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(5)

Delta Between Two Patch Sets: 2014/static-analysis.slide

Issue 172590043: code review 172590043: 2014/static-analysis: add slides for gomeetup presentation. (Closed)
Left Patch Set: diff -r 1a303e2eaf127ae0a75d5998b44f719d8f3e6176 https://code.google.com/p/go.talks Created 9 years, 4 months ago
Right Patch Set: diff -r 1a303e2eaf127ae0a75d5998b44f719d8f3e6176 https://code.google.com/p/go.talks Created 9 years, 4 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « no previous file | 2014/static-analysis/demo.go » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
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
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
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
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
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?
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b