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)
## 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
## }

Then, the automatically optimized code would be:

opt_code <- opt_loop_invariant(list(code))
cat(opt_code$codes[[1]])
## i <- 0
## n <- 1000
## y <- rnorm(1)
## z <- rnorm(1)
## a <- c()
## if (i < n) {
##   x <- y + z
## } 
## while (i < n) {
##   a[i] <- 6 * i + x * x
##   i <- i + 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)

plot of chunk unnamed-chunk-5

speed_up(bmark_res)
##            Min. 1st Qu.   Median     Mean  3rd Qu.     Max.
## Expr_2 62.17502 62.3752 52.84374 57.15049 51.75126 76.25026

Implementation

The opt_loop_invariant optimizer does:

To-Do