Loop-invariant Code Motion
In rco: The R Code Optimizer

library("rco")
library("microbenchmark")
library("ggplot2")
autoplot.microbenchmark <- function(obj) {
  levels(obj$expr) <- paste0("Expr_", seq_along(levels(obj$expr)))
  microbenchmark:::autoplot.microbenchmark(obj)
}
speed_up <- function(obj) {
  levels(obj$expr) <- paste0("Expr_", seq_along(levels(obj$expr)))
  obj <- as.data.frame(obj)
  summaries <- do.call(rbind, by(obj$time, obj$expr, summary))
  res <- c()
  for (i in seq_len(nrow(summaries) - 1) + 1) {
    res <- rbind(res, summaries[1, ] / summaries[i, ])
  }
  rownames(res) <- levels(obj$expr)[-1]
  return(res)
}

Loop-invariant Code Motion

Background

Loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program. Loop-invariant code motion is a compiler optimization which performs this movement automatically.

For example, consider the following code:

i <- 0
n <- 1000
y <- rnorm(1)
z <- rnorm(1)
a <- c()
while (i < n) {
  x <- y + z
  a[i] <- 6 * i + x * x
  i <- i + 1
}

Here, x is assigned a value y + z that is constant in each loop execution. In this example, the assignment would be executed n times. The same result, but much faster, would be obtained by doing the assign outside the loop.

Example

Consider the previous example to be automatically optimized.

code <- paste(
  "i <- 0",
  "n <- 1000",
  "y <- rnorm(1)",
  "z <- rnorm(1)",
  "a <- c()",
  "while (i < n) {",
  "  x <- y + z",
  "  a[i] <- 6 * i + x * x",
  "  i <- i + 1",
  "}",
  sep = "\n"
)
cat(code)

Then, the automatically optimized code would be:

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

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)

Implementation

The opt_loop_invariant optimizer does:

Finds for and while loops in the code.
Discards loops that have function calls inside, as function calls can edit the environment.
Gets which variables are variant inside the loop.
Detects which expressions do not use any variant variable.
Gets these invariant variables, and moves them outside the loop, but inside an if statement (with the same conditional as the loop).

To-Do

if/else code motion?

Actually, the opt_loop_invariant does not consider if/else expressions to move. In this sense, the code:

r while (i < n) { if (n > 3) { something_without_i } }

Will not be optimized to its equivalent code:

r if (i < n) { if (n > 3) { something_without_i } } while (i < n) { }

Invariant subexpressions motion?

Actually, the opt_loop_invariant considers only full expressions, it is not working on subexpressions, for instance, the code:

r while (i < n) { i <- (x * y) + 1 }

as x and y are invariant, could be optimized to:

r is_1 <- (x * y) while (i < n) { i <- is_1 + 1 }

Include repeat optimization?

Since determining the conditional that causes a repeat loop to stop is not that simple, it is not easy to remove invariant variables and place them in an if.

For example, the code:

r y <- 1 repeat{ if (y > 4) { break } x <- 8 * 8 y <- y + 1 }

Must be optimized to:

r y <- 1 if (y <= 4) { x <- 8 * 8 } repeat{ if (y > 4) { break } y <- y + 1 }