Compilers use static analysis to determine where transformations can be safely applied. Control flow and data flow analysis are two techniques often used in compiler optimization. Control-flow analysis seeks to understand the flow of control between operations, and data-flow analysis(DFA) analyses the flow of actual values through the code and operations. SSA is an intermediate representation that embeds a Control Flow Graph(CFG), and makes DFA relatively trivial.
I’ll be looking at it from a concurrency-focused lens, not so much code optimization. Understanding how both controls and data flow then becomes especially important when you want to understand how different concurrency primitives are applied. The question i’ll be exploring is whether a goroutine will leak.
To motivate this, let’s look at a simple example:
func f(cond bool) {
ch := make(chan int)
go func() { for range ch {} }() // line 4
if cond {
close(ch) // line 6 — after goroutine, but only reachable when cond==true
}
// when cond==false: goroutine leaks
}
For the above example, we want to be able to detect if there is a goroutine leak, an instance where the channel is not closed after the goroutine blocks forever because the channel it ranges over is never closed. One trivial way to check for this is to literally compare the line-number ordering. If the close(ch) is after the goroutine, then we can probably assume that the goroutine is not going to leak(assuming we can correctly match the channel identifier). This approach, however, wouldnt work in the above case because the channel is closed conditionally.
With a CFG, you can ask some questions like Does every path from the goroutine launch to function exit pass through a close? This is called a dominance or post-dominance check.
This is an illustration of how the control flows in the example above.
graph TD
entry["entry: ch = make(chan int)"]
goStmt["go func() { range ch }"]
ifCond{"cond?"}
closeCh["close(ch)"]
noClose["(no close)"]
ret["return"]
entry --> goStmt
goStmt --> ifCond
ifCond -->|true| closeCh
ifCond -->|false| noClose
closeCh --> ret
noClose --> ret
To understand CFGs, we need to understand what post-dominators are. A node X post-dominates node Y if every path from Y to the function exit must pass through X. The post-dominator tree encodes this relationship: X post-dominates Y if and only if X is an ancestor of Y in the tree. We can look at the post-dominator tree for this code:
graph TD
ret["return (EXIT)"]
ifCond{"cond?"}
goStmt["go func() { range ch }"]
entry["entry: ch = make(chan int)"]
closeCh["close(ch)"]
noClose["(no close)"]
ret --> ifCond
ret --> closeCh
ret --> noClose
ifCond --> goStmt
goStmt --> entry
Look at where close(ch) sits in the post-dominator tree. It hangs directly off return. It’s not an ancestor of go func() { range ch }. That tells us close(ch) does not post-dominate the goroutine launch. So basically, there exists a path from the goroutine launch to function exit that never passes through close(ch).
Compare that with ifCond, which is an ancestor of goStmt in the post-dominator tree. Every path from the goroutine launch to the exit must pass through the cond branch.
So back to the question: “does the channel get closed on every path after the goroutine starts?” reduces to: “is close(ch) an ancestor of go func() in the post-dominator tree?” Here, the answer is no which tells us the goroutine can leak.
Data flow Analysis
Now, consider another extension to the example above:
func f() {
ch := make(chan int)
x := ch
go func() { for range x {} }()
close(ch)
}
In this case, we are assigning ch to another variable. The flow is trivially linear so you would think our initial line-numbering tool would work? But it actually wouldnt. A post-dominance check here would be fine in the sense that close(ch) is indeed on every path, but the range loops over x and we are closing ch. And so we would end up assuming that the channel x that the goroutine is ranging(not sure that’s a word) over was not closed. We clearly need a deeper understanding of the flow of values. That’s essentially where DFA comes into place. DFA tracks values. The specific form of DFA that helps here is called reaching definitions
ch := make(chan int) // def₁: ch = <new channel>
x := ch // def₂: x = ch
go func() {
for range x {} // using x. which definition reaches here?
}()
close(ch) // using ch — which definition reaches here?
This is what the DFA looks like:
graph LR
def1["def1: ch = make(chan int)"]
def2["def2: x = ch"]
useX["use: range x"]
useCh["use: close(ch)"]
def1 -->|"ch flows to"| def2
def1 -->|"ch flows to"| useCh
def2 -->|"x flows to"| useX
def1 -.->|"same underlying value"| useX
def₁ creates the channel. def₂ copies it into x. The reaching definition for range x is def₂, which in turn got its value from def₁. The reaching definition for close(ch) is def₁ directly. Both trace back to the same make(chan int) so they operate on the same channel.
Static Single Assignment.
If you imagine a case like in a real-world program where you have branches, loops, or reassignments, doing this kind of analysis on raw code is a lot of work. SSA makes this relatively easy to do, and go makes it even easier with the ssa package. In SSA, every variable is assigned exactly once. If the original code assigns a variable twice, SSA creates two different names. Here’s what the example looks like in SSA form:
t0 = make chan int ; the one and only channel value
t1 = t0 ; x := ch so SSA shows t1 IS t0
go func() {
range t1 ; uses t1, which IS t0
}
close(t0) ; same value
If you process the SSA, and not the raw code, you can see that range and close operate on the same object. This example was fairly trivial and to be honest, might be handled by regular data flow analysis. What makes SSA more interesting is when you have different control flows that need to merged. So let’s look at another example.
func f(cond bool) {
ch1 := make(chan int)
ch2 := make(chan int)
var x chan int
if cond {
x = ch1
} else {
x = ch2
}
close(x) // which channel does this close?
}
The fairly reasonable answer would be either channel would be closed right? I mean depending on if cond is true or false. In SSA, this would be:
t0 = make chan int ; ch1
t1 = make chan int ; ch2
if cond goto block1 else block2
block1:
jump block3
block2:
jump block3
block3:
t2 = phi [block1: t0, block2: t1] ; "x is t0 if we came from block1, t1 if block2"
close(t2)
Looks a bit scary, but really the most important thing here is the phi node. This essentially encodes that its value depends on the path we took. This allows us to define SSA’s exclusive ‘every variable is assigned once’ property. For concurrency, specifically these phi node representations are important because they can represent runtime conditions such as whether to use a buffered or unbuffered channel or which server to connect to.
What we’ve looked at are just single-function definitions. A more common use-case is when channels are created at one place, passed to consumers, producers or cleanup functions.
Take this example for instance:
func produce(ch chan<- int) {
for i := 0; i < 5; i++ {
ch <- i
}
close(ch)
}
func consume(ch <-chan int) {
go func() {
for range ch {}
}()
}
func main() {
ch := make(chan int)
consume(ch)
produce(ch)
}
Within main, the CFG is straight-line. SSA tells us that consume and produce both receive the same channel value (the MakeChan from main). But neither of them tell us whether the goroutine launched inside consume eventually sees a close on its channel. There’s three different functions here, and none of the analysis we’ve done earlier can connect them. As you would imagine, we need some kind of call-graph.
Enter Interprocedural analysis. The call-graph looks something like this.
graph TD
main["main()"]
consume["consume(ch)"]
produce["produce(ch)"]
anonFn["go func() { range ch }"]
main -->|"calls"| consume
main -->|"calls"| produce
consume -->|"launches goroutine"| anonFn
This tells us who calls whom, but what we really wanna know is what happens to the channel. You could absolutely walk through each callee body and re-analyze it, but you quickly run into performance issues if say produce is called multiple times, or recursively. A better approach is to track a compact description of what a function does with its parameters without re-analyzing its entire body. This is called a function summary. You compute it once, then reuse it everywhere the function is called. Summaries are also nice because you can do cross-package analysis. The contrived function summaries look like this:
produce(ch chan<- int):
sends to: param#0
closes: param#0
launches: (none)
consume(ch <-chan int):
sends to: (none)
closes: (none)
launches: goroutine that ranges param#0
From the perspective of main:
main():
ch = make(chan int)
consume(ch):
→ launches goroutine that ranges ch
produce(ch):
→ sends to ch
→ closes ch
We can see here that produce does indeed close the same ch we created in main which answers our question from earlier.
We started with a deceptively simple question: does a goroutine leak? Answering it pulled us through four layers of analysis. Control flow analysis gave us the CFG, post-dominance and the ability to reason about which paths exist. Data flow analysis gave us reaching definitions — the ability to track which values flow along those paths. SSA unified both into a single representation where the answers are structural, not computed. Interprocedural analysis extended the picture across function boundaries through call graphs and function summaries. Each technique answers a different dimension of the same question: paths, values, and boundaries. The goroutine leak was the motivating example, but these same tools generalize to any concurrency question you can think of really. Double closes, sends to channels no one receives from, mutexes held across goroutine boundaries. Just need to ask the right questions!