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