Transforming and optimizing loops

In this recipe, we will see how we can transform and optimize loops to get shorter execution times. We will mainly be looking into the Loop-Invariant Code Motion (LICM) optimization technique, and see how it works and how it transforms the code. We will also look at a relatively simpler technique called loop deletion, where we eliminate loops with non-infinite, computable trip counts that have no side effects on a function's return value.

Getting ready

You must have the opt tool built for this recipe.

How to do it…

1. Write the test cases for the LICM pass:

   $ cat testlicm.ll
   define void @testfunc(i32 %i) {
   ; <label>:0
     br label %Loop
   Loop:        ; preds = %Loop, %0
     %j = phi i32 [ 0, %0 ], [ %Next, %Loop ]        ; <i32> [#uses=1]
     %i2 = mul i32 %i, 17        ; <i32> [#uses=1]
     %Next = add i32 %j, %i2        ; <i32> [#uses=2]
     %cond = icmp eq i32 %Next, 0        ; <i1> [#uses=1]
     br i1 %cond, label %Out, label %Loop
   Out:  ...