Dead Store Elimination

Background

Dead Store Elimination is an optimization that intends to remove an assignation of a variable that is not read by any subsequent instruction.

For instance, consider the following code:

foo <- function(x) {
  i <- 8818
  return(x ^ 3)
}

Variable i is never used, so this assignation could be removed, resulting in:

foo <- function(x) {
  8818 # this line can be removed by Dead Expression Elimination
  return(x ^ 3)
}

After applying other optimizations, such as Constant Propagation, some variables become dead stores.

For example, consider:

foo <- function(x) {
  i <- 0
  n <- 8818
  res <- 0
  while (i < n) {
    res <- res + i
    i <- i + 1
  }
  return(res)
}

After Constant Propagation we would get:

foo <- function(x) {
  i <- 0
  n <- 8818
  res <- 0
  while (i < 8818) {
    res <- res + i
    i <- i + 1
  }
  return(res)
}

And thus, n would become a dead store.

Example

Consider the following example:

code <- paste(
  "foo <- function(n) {",
  "  i <- 0",
  "  res <- 0",
  "  while (i < n) {",
  "    res <- res + i",
  "    i <- i + 1",
  "    a <- i + 1",
  "  }",
  "  res",
  "}",
  "foo(10000)",
  sep = "\n"
)
cat(code)
## foo <- function(n) {
##   i <- 0
##   res <- 0
##   while (i < n) {
##     res <- res + i
##     i <- i + 1
##     a <- i + 1
##   }
##   res
## }
## foo(10000)

Then, the automatically optimized code would be:

opt_code <- opt_dead_store(list(code))
cat(opt_code$codes[[1]])
## foo <- function(n) {
##   i <- 0
##   res <- 0
##   while (i < n) {
##     res <- res + i
##     i <- i + 1
##     i + 1
##   }
##   res
## }
## foo(10000)

And if we measure the execution time of each one, and the speed-up:

bmark_res <- microbenchmark({
  eval(parse(text = code))
}, {
  eval(parse(text = opt_code))
})
autoplot(bmark_res)

plot of chunk unnamed-chunk-8

speed_up(bmark_res)
##            Min.  1st Qu.   Median     Mean  3rd Qu.     Max.
## Expr_2 20.35789 20.56051 19.44692 19.79184 17.76742 25.58596

Implementation

A dead store will be an assignment of a variable that is not read by any subsequent instruction. To be considered dead store, the assignment must be given within the definition of a function, since otherwise, the assignment would affect the global environment and therefore could be aimed to be used by the user.

The opt_dead_store detects which code chunks are function definitions. Then for each function, the optimizer gets it body, detects dead stores, i.e., assigned but not read variables, and eliminates them.

To-Do