x/tools/go/analysis/passes/unusedwrite: detect dead stores to local vars

[adonovan]

During review of https://go.dev/cl/581555, @timothy-king pointed out that I had defined a local variable using an if/else statement and then failed to use it after the statement, something like this:

 func f(pass *Pass), filename string) {
 	readFile := pass.ReadFile
 	if readFile == nil {
 		readFile = os.ReadFile
 	}
 	os.ReadFile(filename) // oops, I meant readFile
 }

The assignment to readFile is a dead store. We should flag this as a likely error.

[bensiauu]

hi, can i work on this issue?

[bensiauu]

actually after taking a look at the code, we do have a deadstore function but is there a reason why it is limited to only structs and arrays?

https://github.com/golang/tools/blob/master/go/analysis/passes/unusedwrite/unusedwrite.go#L86

[adonovan]

The unusedwrite analysis is specifically about components of local variables of aggregate types (structs and arrays). The analogous treatment for local variables themselves is often unnecessary because the Go spec disallows variables all of whose uses are in lvalue positions, for example https://go.dev/play/p/7xAvQRbI_zP:

func main() {
	x := 1 // error: declared and not used
	if true {
		x = 2
	}
}

But the example at the top illustrates why locals would benefit from analysis too.

hi, can i work on this issue?

Thanks, that would be great, but please discuss your plan of attack before sending code as it may save us all time.

[bensiauu]

Thanks, that would be great, but please discuss your plan of attack before sending code as it may save us all time.

Sure! Have fleshed out my plan below, do let me know if i'm missing anything or if there's anything wrong with my approach.

Implementation Plan

1. Setup the Analysis struct

2. Build the Control Flow Graph (CFG)
   Use the golang.org/x/tools/go/ssa package to build the SSA form and CFG
   for the function being analyzed.

3. Track Assignments and Reads

   • Assignments: Detect ssa.Store instructions that assign values to
     variables.
   • Reads: Detect ssa.Load instructions or any usage of the variable.

4. Analyze Control Flow
   Use the SSA and CFG together to analyze the flow of control between
   blocks. For each variable:

• Track assignments across basic blocks.
• Check if an assignment reaches a read along a valid execution path.
• Handle branches and loops to ensure proper propagation of information.

5. Detect Dead Stores
   A variable write is considered a "dead store" if:

• The variable is assigned a value but never read.
• The variable is assigned a value, and this value is overwritten by
  another assignment without being read in between.

Handling Loops and Branches

Branches

if condition {
    x = 42 // Write to x
} else {
    y = 5 // Write to y
}
fmt.Println(x) // Read x

1. Track variable writes by branch
2. Merge information at join paths
3. Check reads after paths have joined.

Loops

1. Track variables written before the loop starts (entry point).
2. Check if the loop writes a variable that is never read, either
   inside the loop or after it exits.
3. A write to a variable inside a loop is "dead" if:
   • The variable is never read inside the loop.
   • The variable is not read in any block reachable after the loop.

Question

Would like some input on how we should handle the following case:

var x int
for i := 0; i < 5; i++ {
    x = i * 2
    if i == 4 {
        fmt.Println(x)
    }
}

Would we still consider this a dead store?

Cases to cover

Overwritten before read

x := 0 // want "dead store: value assigned here is never used"
for i := 0; i < 10; i++ {
    x = i // want "dead store: value assigned here is overwritten"
}
println(x)

func overwrittenValue() {
    x := 0         // want "dead store: value assigned here is never used"
    x = 42
    println(x)
}

func loopWithDeadStores() {
    x := 0         // want "dead store: value assigned here is never used"
    for i := 0; i < 10; i++ {
        x = i      // want "dead store: value assigned here is overwritten"
    }
    println(x)
}


// possible false positive
func loopNoDead() {
    x := 0

    for i := 0; i < 10; i++ {
        if i == 3 && x == 0 {
            x = 2
        }
    }
    fmt.Println(x)


}

variable is assigned but overwritten before being read.

Reassigned in branches

func reassignedInBranches(y int) {
    x := 0
    if condition {
        x = 42// want "dead store: value assigned here is never used"
    } else {
        y = 99// want "dead store: value assigned here is never used"
    }
    println(y)
}

variable is used for if checks, but after being reassigned in if/else
block it is not used.

Nested loops

    var sum int
    for i := 0; i < 5; i++ { // Outer loop
        for j := 0; j < 5; j++ { // Inner loop
            sum = i + j // Dead store: sum is overwritten in every iteration
        }
    }

[adonovan]

Sure! Have fleshed out my plan below, do let me know if i'm missing anything or if there's anything wrong with my approach.

Thanks. Questions inline.

Implementation Plan

1. Setup the Analysis struct
2. Build the Control Flow Graph (CFG)
   Use the golang.org/x/tools/go/ssa package to build the SSA form and CFG
   for the function being analyzed.

This change should be a modification to the existing unusedwrite analyzer, which already takes care of these steps.

A variable write is considered a "dead store" if:

• The variable is assigned a value but never read.
• The variable is assigned a value, and this value is overwritten by
  another assignment without being read in between.

How would these rules detect the problem with the original example?

 	readFile := pass.ReadFile
 	if readFile == nil {
 		readFile = os.ReadFile
 	}

The value of the variable is read, and neither of the assignments is overwritten before being read in between. The problem here is that the final assignment is never followed by a read.

Branches

if condition {
    x = 42 // Write to x
} else {
    y = 5 // Write to y
}
fmt.Println(x) // Read x

1. Track variable writes by branch
2. Merge information at join paths
3. Check reads after paths have joined.

Loops...

What is the abstract state, and how is it merged at a control join? Is it a "may" or a "must" dataflow analysis? That is, do we record facts of the form "v may have been read" and compute the union, or "v must have been read" and compute the intersection?

How will you deal with reads from other functions? For example, v = 1 is not a dead store because its effects may be observed by other functions, since the 'share' call may have caused v to escape.

func f() { 
   var v int
   share(&v)
   v = 1
}

var x int
for i := 0; i < 5; i++ {
    x = i * 2
    if i == 4 {
        fmt.Println(x)
    }
}

Would we still consider this a dead store?

This is not a dead store. The value of x is always computed, and only sometimes used; there's nothing wrong with that, especially if the value assigned to x is more conveniently computed in advance than only when needed.

Cases to cover

Overwritten before read

x := 0 // want "dead store: value assigned here is never used"
for i := 0; i < 10; i++ {
    x = i // want "dead store: value assigned here is overwritten"
}
println(x)

This is a dead store only because the upper bound (10) is provably greater than zero. If it had been a variable n, then there is the possibility that zero iterations of the loop were executed, and the loop's successor block could see either assignment, 0 or i, so neither is dead.

Since you didn't mention trying to evaluate control conditions (nor should you), this example should not be considered a dead store.

func loopWithDeadStores() {
    x := 0         // want "dead store: value assigned here is never used"
    for i := 0; i < 10; i++ {
        x = i      // want "dead store: value assigned here is overwritten"
    }
    println(x)
}

This is the same case as before.

// possible false positive
func loopNoDead() {
x := 0

for i := 0; i < 10; i++ {
    if i == 3 && x == 0 {
        x = 2
    }
}
fmt.Println(x)

}

variable is assigned but overwritten before being read.

Also not a dead store, for the same reason.

Reassigned in branches

func reassignedInBranches(y int) {
    x := 0
    if condition {
        x = 42// want "dead store: value assigned here is never used"
    } else {
        y = 99// want "dead store: value assigned here is never used"
    }
    println(y)
}

variable is used for if checks, but after being reassigned in if/else block it is not used.

The assignment to x is indeed dead, but the assignment to y is very much alive, and used by the println(y). Why would we want to report it as dead?

[bensiauu]

thanks for the comments and clarifications, here's an updated implementation plan.

Implementation Plan

1. Build the Control Flow Graph (CFG)

Generate CFG for function.

2. Abstract State for Variables

Track the state of each variable using three attributes:

• Written: Whether the variable has been assigned a value.
• Read: Whether the variable has been read after its last write.
• Escaped: Whether the variable has escaped (e.g., passed to another function or global variable).

Example State Representation:

type VarState struct {
    Written  bool 
    Read     bool 
    Escaped  bool 
}

For each variable, maintain its state across all instructions.

---

3. Merge Strategy at Control Joins

At control flow joins after branches:

• Use may analysis to compute merged states:
  • If a variable is written in one branch but not another, record Written = true.
  • If a variable is read in one branch but not another, record Read = true.
  • If a variable escapes in one branch, record Escaped = true.

Example:

if condition {
    x = 42 // Written = true
} else {
    y = 5  // Written = true
}
println(x) // Read = true for x

• At the join point:
  • x.Written = true, x.Read = true (if used after the join).
  • y.Written = true, y.Read = false (if not used after the join).

Example 2 (nested branch):

if condition1 {
    if condition2 {
        x = 10  // Written = true
    }
    y = 20      // Written = true
} else {
    z = 30      // Written = true
}
println(x)

At Join:

• x.Written = true (written in sub-branch 1.1).
• x.Read = true (read after the join).
• y.Written = true (written in sub-branch 1.2, not in branch 2).
• z.Written = true (written in branch 2, not in others).

---

4. Escape Handling

• Perform escape analysis to determine if a variable escapes:
  • If a variable is passed by reference or to another function, assume it may be used elsewhere.
  • If a variable escapes, treat all writes to it as meaningful and not dead stores.
  • Variable should also be considered escaped if passed to a global variable.

Example:

func f() {
    var v int
    share(&v) // v escapes
    v = 1     // Not a dead store
}

For variables that escape:

• Set Escaped = true.
• Skip dead store analysis for subsequent writes.

---

5. Handle Loops

Detect Dead Stores in Loops

• If a variable is written in the loop but never read inside or after the loop, it is a dead store.
• Handle loop-carried dependencies:
  • Ensure reads and writes across iterations are considered.

Example:

var x int
for i := 0; i < 5; i++ {
    x = i * 2 // Written in each iteration
    if i == 4 {
        fmt.Println(x) // Read in the final iteration
    }
}

• x is not a dead store because it is read in the final iteration.

---

6. Analyze Assignments and Reads

x := 2       // Initial assignment
println(x)   // Read
x = 4        // Reassignment (new value, not read)

The states of x after each operation should be updated as follows:

• After x := 2:

x.Written = true (assigned 2)
x.Read = false (not read yet)

• After println(x):

x.Written = false (no new assignment in this operation)
x.Read = true (read in println(x))

• After x = 4:

x.Written = true (assigned 4)
x.Read = false (no read after reassignment)

we also reset the Read flag after a reassignment, until a corresponding variable read sets it to true.

---

7. Detect Dead Stores

Dead Store Rules

A variable write is a dead store if:

1. The variable is assigned a value but never read.
2. The variable is assigned a value, and this value is overwritten without being read in between.

Example Cases

Case 1: Overwritten Before Read

x := 0 // Dead store: value is never used
x = 3
println(x)

• First write to x is never read.

Case 2: Escaped Variable

func f() {
    var x int
    share(&x) // x escapes
    x = 42    // Not a dead store
}

• Since x escapes, its writes are considered meaningful.

Case 3: Branching

if condition {
    x = 42 // Dead store: value not used
} else {
    y = 99 
}
println(y) 

• Writes to x and y in their respective branches are not followed by reads.

Case 4: Never read

readFile := pass.ReadFile
if readFile == nil {
    readFile = os.ReadFile // Dead store: value is never read
}

• The readFile assignment is not overwritten, but it is also never followed by a read. This requires resetting the read state of the variable when there is a write.

---

[adonovan]

type VarState struct {
Written bool
Read bool
Escaped bool
}
For each variable, maintain its state across all instructions.

FWIW, the SSA construction does (must do) a conservative escape analysis to decide whether it is safe to stack-allocate a variable. It uses the simplest of all algorithms: if a variable's address is taken, it escapes. So, your analysis could assume that all variables in ssa.Function.Locals are non-escaping, and ignore all variables created by dynamic ssa.Alloc instructions.

(Of course, more precise results are possible if you consider disjoint live ranges separately, for example x:=1; print(x); x=2; use(&x) is really two different variables, only the second of which escapes. I wouldn't start with that though.)

3. Merge Strategy at Control Joins
   At control flow joins after branches:
   Use may analysis to compute merged states:
   If a variable is written in one branch but not another, record Written = true.
   If a variable is read in one branch but not another, record Read = true.

If the problematic condition is "there is no control path from a definite write to a possible read", then I think you need to use intersection not union of Written bits. In other words: if only one arm of an if/else is a write, then the if/else as a whole is not considered a definite write. But if only one arm of an if/else is a read, then the if/else as a whole is a possible read.