The hardware and bandwidth for this mirror is donated by METANET, the Webhosting and Full Service-Cloud Provider.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]metanet.ch.

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

Intelligent dead store?

If within a function, a variable is assigned multiple times, but just the last assignation is read, then the optimizer could keep just the last one.

For example:
```
foo <- function() {
a <- 8
a <- 8818
return(a ^ 2)
}
```
Would be equivalent to:
```
foo <- function() {
8
a <- 8818
return(a ^ 2)
}
```
Remove variables that do not affect the returned value?

Eliminate all those variables that are assigned, read or not, but that do not affect the value returned by the function.

For example:
```
foo <- function() {
a <- 8818
b <- 0
c <- 1000
res <- 0
for (b < c) {
  b <- b + 1
  res <- res + b
}
return(a ^ 2)
}
```
Would be equivalent to:
```
foo <- function() {
a <- 8818
return(a ^ 2)
}
```

These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.