CSE411: Introduction to Compilers

Loop Optimization

Jooyong Yi (UNIST)

Example

              |---------|
          L0: |  t = 0  |                                                    
              |---------|
                   ↓                                                      
          L1: |------------------| <----|
              | i = i + 1        |      |
              | t = a * b        |      |
              | M[i] = t         |      |
              | if i < N goto L1 |      |
              |------------------| ------
                  ↓
          L2: |---------|
              |  x = t  |
              |---------| 

• t = a * b is a loop-invariant.
  • The value of a * b does not change over the loop iterations.

Loop-invariant Hoisting

                                                                  |-------------|
              |---------|                                     L0: |  t = 0      |
          L0: |  t = 0  |                                         |  t = a * b  |                
              |---------|                                         |-------------|
                   ↓                                                    ↓                                                      
          L1: |------------------| <----|                     L1: |------------------| <----|     
              | i = i + 1        |      |                         | i = i + 1        |      |
              | t = a * b        |      |                         |                  |      |
              | M[i] = t         |      |    ------>              | M[i] = t         |      |
              | if i < N goto L1 |      |                         | if i < N goto L1 |      |
              |------------------| ------                         |------------------| ------
                  ↓                                                     ↓
          L2: |---------|                                     L2: |---------|
              |  x = t  |                                         |  x = t  |
              |---------|                                         |---------| 

• t = a * b is a loop-invariant.
  • The value of a * b does not change over the loop iterations.

Example

              |---------|
          L0: |  t = 0  |                                                    
              |---------|
                   ↓                                                      
          L1: |-------------------| ------------
              | if i >= N goto L2 | <----|     |        
              |-------------------|      |     |
                   ↓                     |     |
              |-------------|            |     |
              | i = i + 1   |            |     |
              | t = a * b   |            |     |
              | M[i] = t    |            |     |
              | goto L1     |            |     |
              |-------------| ------------     |
                  ↓                            |
          L2: |---------|                      |
              |  x = t  | <---------------------
              |---------|                                                                              

• Hoisting t = a * b?

Difference

                 CFG1                                                 CFG2

              |---------|                                         |---------|
          L0: |  t = 0  |                                     L0: |  t = 0  |                                                    
              |---------|                                         |---------|
                   ↓                                                   ↓  
          L1: |------------------| <----|                     L1: |-------------------| ------------
              | i = i + 1        |      |                         | if i >= N goto L2 | <----|     |        
              | t = a * b        |      |                         |-------------------|      |     |
              | M[i] = t         |      |                              ↓                     |     |
              | if i < N goto L1 |      |                         |-------------|            |     |
              |------------------| ------                         | i = i + 1   |            |     |
                  ↓                                               | t = a * b   |            |     |
          L2: |---------|                                         | M[i] = t    |            |     |
              |  x = t  |                                         | goto L1     |            |     |
              |---------|                                         |-------------| ------------     |
                                                                      ↓                            |
                                                              L2: |---------|                      |
                                                                  |  x = t  | <---------------------
                                                                  |---------|

Difference

                 CFG1                                                 CFG2

              |---------|                                         |---------|
          L0: |  t = 0  |                                     L0: |  t = 0  |                                                    
              |---------|                                         |---------|
                   ↓                                                   ↓  
          L1: |------------------| <----|                     L1: |-------------------| ------------
              | i = i + 1        |      |                         | if i >= N goto L2 | <----|     |        
              | t = a * b        |      |                         |-------------------|      |     |
              | M[i] = t         |      |                              ↓                     |     |
              | if i < N goto L1 |      |                         |-------------|            |     |
              |------------------| ------                         | i = i + 1   |            |     |
                  ↓                                               | t = a * b   |            |     |
          L2: |---------|                                         | M[i] = t    |            |     |
              |  x = t  |                                         | goto L1     |            |     |
              |---------|                                         |-------------| ------------     |
                                                                      ↓                            |
                                                              L2: |---------|                      |
                                                                  |  x = t  | <---------------------
                                                                  |---------|

• In CFG1, in order to exit the loop, t = a * b must be executed.
  • t = a * b dominates all loop exits.

Dominators

• Given a CFG, a node d dominates a node n if every path from the entry node to n must go through d.
  • d is a dominator of n.

Example

              |---------|
          L0: |  t = 0  |                                                    
              |---------|
                   ↓                                                      
          L1: |------------------| <----|
              | i = i + 1        |      |
              | t = a * b        |      |
              | M[i] = t         |      |
              | t = 0            |      |
              | M[j] = t         |      |
              | if i < N goto L1 |      |
              |------------------| ------
                  ↓
          L2: |---------|
              |  x = t  |
              |---------| 

• Hoisting t = a * b?

Example

              |---------|
          L0: |  t = 0  |                                                    
              |---------|
                   ↓                                                      
          L1: |------------------| <----|
              | i = i + 1        |      |
              | t = a * b        |      |
              | M[i] = t         |      |
              | t = 0            |      |
              | M[j] = t         |      |
              | if i < N goto L1 |      |
              |------------------| ------
                  ↓
          L2: |---------|
              |  x = t  |
              |---------| 

• Hoisting t = a * b?
  • No, because there are multiple definitions of t in the loop body.

Example

              |---------|
          L0: |  t = 0  |                                                    
              |---------|
                   ↓                                                      
          L1: |------------------| <----|
              | M[j] = t         |      |          
              | i = i + 1        |      |
              | t = a * b        |      |
              | M[i] = t         |      |
              | if i < N goto L1 |      |
              |------------------| ------
                  ↓
          L2: |---------|
              |  x = t  |
              |---------| 

• Hoisting t = a * b?

Example

              |---------|
          L0: |  t = 0  |                                                    
              |---------|
                   ↓                                                      
          L1: |------------------| <----|
              | M[j] = t         |      |          
              | i = i + 1        |      |
              | t = a * b        |      |
              | M[i] = t         |      |
              | if i < N goto L1 |      |
              |------------------| ------
                  ↓
          L2: |---------|
              |  x = t  |
              |---------| 

• Hoisting t = a * b?
  • No, because t is live at the exit of L0.

Loop-invariant Hoisting

• A loop-invariant for variable is a computation whose value does not change over the loop iterations.
• Move the loop invariant to the loop preheader.
• Loop-invariant hoisting can be conducted when:
  • dominates all loop exits.
  • there is only one definition of in the loop body.
  • is not live at the exit of the loop preheader.