For the 30-line HERA assembly language program below, do the following
steps. This is a really long statement for a mini-homework, but I
think each step should be fairly quick --- don't spend more than 30
minutes on this, and, as always, feel free to work in groups.


A) Break it into "basic blocks"
   * How many basic blocks are there?      _____
   * How many labels do you need to add?   _____
   * How many branches do you need to add? _____


B) Label each basic block with a letter ("A", "B", "C", ...) and draw
   a directed graph in which nodes correspond to basic blocks, and
   arcs correspond to possible execution sequences (so if block X can
   by followed by block Y or block Z, there are arcs from X to Y and
   from X to Z).


C) Read Appel's discussion under the heading "Traces" (about 6
   paragraphs in Section 8.2, in the 1st edition of the text),
   and generate a new order for the basic blocks. Your order should,
   to the extent possible, ensure that each block is immediately
   followed in the program by the one that will "usually" follow it
   during execution --- for this program, assume that a while loop
   usually _does_ execute its body (rather than exiting the loop), and
   that an "if" usually _does_ execute the "then" clause.

   I suggest you do this by highlight the "usual" branches in your
   graph from part B, and then write the new sequence of letters, in
   order, and finally use a word processor to cut and paste the blocks
   into place.


D) In the final trace, you can remove any branch that is immediately
   followed by its target. The original program (below) has 7 branch
   instructions.

   How many branch instructions are needed in your final program? ____


E) Optional, if you have time: effects of this "optimization" ---

   E.1) The loop in the original program (from the START_OF_WHILE_1
   label to the final BR to this label) has 20 lines that are neither
   comment nor label. This means the program will need an "instruction
   cache" of about size 20 (labels don't actually take space in the
   machine-language version of the program). Many of the first
   processors with instruction cache's could hold 8-16 instructions
   there.

   How many instructions are in the main body of the loop for your program? ____
   
   How would your answer change if there were another 8 instructions
   in an "else" clause for the "if" in this program?

   E.2) If we start R9 (i.e., X) at 320, and R8 (Y) at -7000, we'll
   go through the loop 16 times, running the body of the "if" each
   time. If "taking" a branch (i.e. going to something other than the
   instruction that directly follows it in the program text) takes
   twice as long as "falling through" a conditional branch (to that
   next instruction in the text), compare the costs of the branch
   instructions in the original code and your final result. ____________

   E.3) Unsually we have only one copy of each basic block in the
   final result. If we allow two copies of the "X := X - 17" block,
   essentially adding an "else" clause to the if and moving this block
   into both the "then" and "else", how would this affect your answers
   to E.1 and E.2?


/* 
   Example for trace scheduling, based on the Tiger input

(
   while (X > 60) do (
     if (Y < 565) then
	Y := Y + X;
     X := X - 17
   );
printint(Y)
)
*/

//   This could be translated into the the code starting "SETCB()" below,
//    if we assume X is in R9, and Y in R8.
//   (Your compilers will typically LOAD and STORE X and Y every time.)

// Tests --- uncomment one before running
SET(R9, 70)
SET(R8, 12)
// should print 12 + 70 --> 82
// SET(R9, 70)
// SET(R8, 640)
// should print 640
// SET(R9, 87)
// SET(R8, 12)
// should print 12 + 87 + 70 --> 169
// SET(R9, 121)
// SET(R8, 12)
// should print 12 + 121 + 104 + 87 + 70 --> 394
// SET(R9, 121)
// SET(R8, 350)
// should print 350 + 121 + 104 --> 575


SETCB()  /// ALWAYS PUT THIS AT THE START

LABEL(START_OF_WHILE_1)
     // X > 60
     SET(R1, 60)
     CMP(R9, R1)
   BG(X_more_than_60)
     SET(R1, 0)  // comparison is false
   BR(DONE_COMPARISON_1)
LABEL(X_more_than_60)
     SET(R1, 1)  // comparison is true
LABEL(DONE_COMPARISON_1)
     // now we have True or False in R1, for the while
     FLAGS(R1)
   BZ(DONE_WITH_WHILE_1)
     // now the loop body, starting with the "if" at line 8
     // Y < 565
     SET(R1, 565)
     CMP(R8, R1)
   BL(Y_less_than_565)
     SET(R1, 0)  // comparison is false
   BR(DONE_COMPARISON_2)
LABEL(Y_less_than_565)
     SET(R1, 1)  // comparison is true
LABEL(DONE_COMPARISON_2)
     // the X > 65 has put true in R1 if it was true, false otherwise
     // now the "if" selects the "then" or skips it, based on R1
     FLAGS(R1)
   BZ(SKIP_IF_1)
     // NEXT, CHANGE Y := Y + X
     ADD(R8, R8, R9)
LABEL(SKIP_IF_1)
     // LAST LINE OF LOOP: X := X - 17
     SET(R1, 17)
     SUB(R9, R9, R1)
     // THAT'S THE END OF THE BODY OF THE WHILE LOOP
   BR(START_OF_WHILE_1)
LABEL(DONE_WITH_WHILE_1)
     // Put Y on the stack as 1st function call parameter
     STORE(R8, 3, FP)
     CALL(4, printint)