Idea

The basic idea behind the dead expression elimination optimizer is to remove all those expressions whose result is neither used in the program, nor the removal of which affects the result of the code. Therefore this dead expression elimination frees up memory, saves computation time, and provides a speed boost.

Background

Dead Expression Elimination intends to remove those expressions that do not modify the environment.

In R, when evaluating an expression which is not assigned to any variable, its result will be seen in the console. However, when the expression is within a function definition, the value will not be printed, the environment will not be modified, and anyway the computational cost will be incurred.

For example, in the code:

foo <- function() {
  val <- rnorm(1)
  e <- exp(1)
  val
  res <- e ^ val
}

The unassigned val expression is a dead expression, and could be removed.

This optimization strategy is closely related to dead store elimination, since when a dead store is deleted, it is possible that a dead expression is generated.

Example

Consider the following example:

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

## foo <- function(n) {
##   i <- 0
##   res <- 0
##   while (i < n) {
##     res <- res + i
##     i <- i + 1
##     res
##   }
##   res
## }
## foo(10000)

Then, the automatically optimized code would be:

opt_code <- opt_dead_expr(list(code))
cat(opt_code$codes[[1]])

## foo <- function(n) {
##   i <- 0
##   res <- 0
##   while (i < n) {
##     res <- res + i
##     i <- 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)

speed_up(bmark_res)

##           Min.  1st Qu.   Median     Mean  3rd Qu.     Max.
## Expr_2 27.6881 28.21503 27.86797 27.90957 27.01548 75.89559

Implementation

The opt_dead_expr detects which code chunks are function definitions. Then for each function, the optimizer gets it body, detects dead expressions, i.e., not assigned expressions, and eliminates them if they are not returned by the function.

An expression will be considered a dead expression if:

• Its result is not assigned to a variable.
• It contains subexpressions only in: NUM_CONST, STR_CONST, NULL_CONST, ‘+’, ‘-’, ’*‘,’/‘,’^‘, GT, GE, LT, LE, EQ, NE,’!‘, AND, OR, AND2, OR2,’(‘,’)‘,’{‘,’}’, expr, SYMBOL.

To-Do

• Check if dead expressions have never-assigned vars?

  The optimizer is currently eliminating any dead expression, however, the code:

  foo <- function() {
    x
    return(8818)
  }

  is not equivalent to

  foo <- function() {
    return(8818)
  }

  Both functions will return the same value, however, the first one will give an error similar to:

  foo()
  ## Error in foo() : object 'x' not found