The hardware and bandwidth for this mirror is donated by dogado GmbH, the Webhosting and Full Service-Cloud Provider. Check out our Wordpress Tutorial.
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[@]dogado.de.

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)

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:

• 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:

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

  Will not be optimized to its equivalent code:

  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:

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

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

  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:

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

  Must be optimized to:

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

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.
Health stats visible at Monitor.