COMP 3002 Assignment 4

For this Assignment you will be continuing the implementation of the JVM code optimizer jopt available in this archive. This includes some aspects of peephole optimization and some aspects of global analysis of flow-of-control.

Note that your optimizer should be iterative. That is, it should apply all the optimizations below repeatedly until no more optimizations are possible. This will allow, for example, the second part of Questions 3 and 4 to happen without any extra work.

  1. [5 marks] In the current implementation of JasminOptimizer, every label encountered starts a new block. Modify the implementation to check if a label is ever the target of a jump instruction. If a label is not the target of a jump instruction and the last instruction of the previous block does not affect flow-of-control then merge the two blocks (and delete the label). 
       ;; Begin Block 22
   ... some instructions
   ; Block 22 exits to block 23
   ;; End Block 22
   ;; Begin Block 23 
mylabel:
   ... some more instructions
   ;; End Block 23
    		==> 
       ;; Begin Block 22
   ... some instructions
   ... some more instructions
   ;; End Block 22
  2. [5 marks] Implement a reduction in strength peephole optimization that replaces multiplication by 2 with a single addition. This would do an optimization like 
      fload 3
  ldc 2.0
  fmul
    		==> 
      fload 3
  dup
  fadd
    This optimization should work for expression like 2*a as well as a*2.
  3. [5 marks] Implement a peephole optimization that precalculates the results of calculations over arithmetic constants. For example: 
      ldc 1.0
  ldc 2.0
  fadd
    		==> 
      ldc 3.0
    Implement this optimization for fadd, fsub, fmul, and fdiv. Note that you get more sophisticated optimizations for free when this optimization is iterated. For example: 
      ldc 1.0
  ldc 2.0
  fadd
  ldc 5.0
  fmul
    		==> 
      ldc 3.0
  ldc 5.0
  fmul
    		==> 
      ldc 15.0
    Furthermore: 
      ldc 5.0
  ldc 1.0
  ldc 2.0
  fadd
  fmul
    		==> 
      ldc 5.0
  ldc 3.0
  fmul
    		==> 
      ldc 15.0
  4. [5 marks] Implement a flow-of-control peephole optimization that optimizes jumps to unconditional jumps, so that 
      goto labelA
  ...
  ifxxx labelA
  ...
labelA:
  goto labelB
  ...
    		==> 
      goto labelB
  ...
  ifxxx labelB
  ...
labelA:
  goto labelB
    Iterating this can get rid of several levels of indirection, so that 
      ifxxx labelA1
  ...
labelA1:
  goto labelA
  ...
labelA:
  goto labelB
  ...
    		==> 
      ifxxx labelA
  ...
labelA1:
  goto labelB
  ...
labelA:
  goto labelB
  ...
    		==> 
      ifxxx labelB
  ...
labelA1:
  goto labelB
  ...
labelA:
  goto labelB
  ...
  5. [5 marks] Currently, the only optimization performed by jopt is the removal of useless load/pop pairs. However, the existence of any pop instruction indicates that some useless information has been pushed onto the operand stack. Generalize the current optimization by beginning at every pop instruction and working backwards eliminating as many useless instructions as possible. For example, a snippet of code like 
      fload 7
  ldc 8.0
  fmul
  fload 2
  ldc 5.0
  fadd
  fmul
  pop
    should simplify down to nothing.
  6. [5 marks] Find and eliminate all unreachable and useless CodeBlocks. These are any CodeBlocks that do not contain any directives and for which there is no execution path from the first block of the method in which they are defined to themselves. (Hint: You may want to lookup depth-first search in one of your algorithms or data structures textbooks.)
  7. [5 marks] Find all useless istore, fstore, and astore instructions. Such an operation is useless if every execution path from that operation leads to a dead-end (a block with no successors) or another store of the same local variable before any load operation on that variable. Once you have determined that a store instruction is useless you can replace it with a pop instruction.