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.
- 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: ; preds = %Loop ret void }
- Execute the LICM pass on this test code:
$ opt licmtest.ll -licm -S ; ModuleID = 'licmtest.ll' define void @testfunc(i32 %i) { %i2 = mul i32 %i, 17 br label %Loop Loop: ; preds = %Loop, %0 %j = phi i32 [ 0, %0 ], [ %Next, %Loop ] %Next = add i32 %j, %i2 %cond = icmp eq i32 %Next, 0 br i1 %cond, label %Out, label %Loop Out: ; preds = %Loop ret void }
- Write the test code for the loop deletion pass:
$ cat deletetest.ll define void @foo(i64 %n, i64 %m) nounwind { entry: br label %bb bb: %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb2 ] %t0 = add i64 %x.0, 1 %t1 = icmp slt i64 %x.0, %n br i1 %t1, label %bb2, label %return bb2: %t2 = icmp slt i64 %x.0, %m br i1 %t1, label %bb, label %return return: ret void }
- Finally, run the loop deletion pass over the test code:
$ opt deletetest.ll -loop-deletion -S ; ModuleID = "deletetest.ll' ; Function Attrs: nounwind define void @foo(i64 %n, i64 %m) #0 { entry: br label %return return: ; preds = %entry ret void } attributes #0 = { nounwind }
The LICM pass performs loop-invariant code motion; it tries to move the code that is not modified in the loop out of the loop. It can go either above the loop in the pre-header block, or after the loop exits from the exit block.
In the example shown earlier, we saw the %i2 = mul i32 %i, 17 part of the code being moved above the loop, as it is not getting modified within the loop block shown in that example.
The loop deletion pass looks out for loops with non-infinite trip counts that have no effect on the return value of the function.
In the test code, we saw how both the basic blocks bb: and bb2:, which have the loop part, get deleted. We also saw how the foo function directly branches to the return statement.
There are many other techniques for optimizing loops, such as loop-rotate, loop-unswitch, and loop-unroll, which you can try yourself. You will then see how they affect the code.