basic block scheduling for Alpha 21064 (two-way superscalar)

  double a,x[N],y[N];

  for(i=0;i<N;i+=2){
    x[i  ] = x[i  ] + a*y[i  ];
    x[i+1] = x[i+1] + a*y[i+1];
  }

  // register allocation
  // F0 = y[i  ]
  // F1 = y[i+1]
  // F5 = a
  // F8 = x[i  ]
  // F9 = x[i+1]



Basic block before code scheduling - 24 cycles

|01234567890123456789| Cycle   Offset Number Instruction
|I                   |     0 00000000      0 LDD      F0,0(R16)
|.I                  |     1 00000004      1 LDD      F8,0(R0)
|  I                 |     2 00000008      2 LDD      F1,8(R16)
|  .I                |     3 0000000C      3 LDD      F9,8(R0)
|    I               |     4 00000010      4 MULG     F0,F5,F0
|    ......I         |    10 00000014      5 ADDG     F8,F0,F8
|           I        |    11 00000018      6 MULG     F1,F5,F1
|           ......I  |    17 0000001C      7 ADDG     F9,F1,F9
|                  I |    18 00000020      8 LDA      R16,16(R16)
|                  .I|    19 00000024      9 CMPLT    R16,R10,R11
|I                   |    20 00000028     10 LDA      R0,16(R0)
|..I                 |    22 0000002C     11 STD      F8,-16(R0)
|   I                |    23 00000030     12 STD      F9,-8(R0)
|   I                |    23 00000034     13 BNE      R11,0


Basic block after code scheduling - 15 cycles

|01234567890123456789| Cycle   Offset Number Instruction
|I                   |     0 00000000      0 LDD      F0,0(R16)
|.I                  |     1 00000004      2 LDD      F1,8(R16)
|  I                 |     2 00000008      1 LDD      F8,0(R0)
|  I                 |     2 0000000C      8 LDA      R16,16(R16)
|   I                |     3 00000010      4 MULG     F0,F5,F0
|   I                |     3 00000014      3 LDD      F9,8(R0)
|    I               |     4 00000018      6 MULG     F1,F5,F1
|    I               |     4 0000001C     10 LDA      R0,16(R0)
|     I              |     5 00000020      9 CMPLT    R16,R10,R11
|     ....I          |     9 00000024      5 ADDG     F8,F0,F8
|          I         |    10 00000028      7 ADDG     F9,F1,F9
|          ...I      |    13 0000002C     11 STD      F8,-16(R0)
|              I     |    14 00000030     12 STD      F9,-8(R0)
|              I     |    14 00000034     13 BNE      R11,0


scheduling DAG

      R16     R0    R16     R0                         input regs
      LDD.   LDD`   LDD.   LDD`                          opcode
       F0 .   F8 `   F1 .   F9 `                        output reg
        |  ....|..`...|......|..`........ 
        |      |   `- | - - -|- -`       .
        |      |      |      |    |WAR   .WAR
        |      |      |      |    |R0    .R16
        |      |      |      |    |      .
        V      |      V      |    v      v
     F5 F0     |   F5 F1     |   R0     R16
      MULG     |    MULG     |  LDA     LDA
       F0     /      F1     /    R0     R16
        |    /        |    /      |      |
        |   /         |   /       |      |
        V  V          V  V        |      V
       F0 F8         F1 F9        |     R16 R10
        ADDG          ADDG        |      CMPLT
         F8            F9         |       R11
          |             |         |        |
          |    ---------|---------'        |
          |   '         |   '              |
          V  V          V  V               V
         F8 R0         F9 R0              R11
          STD           STD               BNE