Local Reordering

As an example of local reordering we have implemented a list scheduling algorithm using SALTO. The main function is reorder, which builds the dependence matrix for the instructions of the current block: dep[i][j] equals to 1 if instruction number i depends on instruction number j. The main loop computes the scheduling cycle for each instruction until a branch is seen: verify_predecessors checks if all instructions that have a data dependence have already been scheduled. earliest_cycle then computes the delays before all previous results are obtained. IsConflict is used to detect resource conflicts. The branch instructions, if they exist, and the delay slot are processed afterwards. The blocks are effectively reordered by orderAccordingToCycles and NOPs are added if necessary by addNecessaryNops.

#include "salto.h"

int verify_predecessors(int verif, int **dep, INST **inst) {
  for (int i=0; i<verif; i++) 
    if ( (dep[verif][i]) && (inst[i]->getCycle() < 0) ) return 0;
  return 1;
}

int earliest_cycle(int s, int **dep, INST **inst) {
  int   i, z, max = 0;
  for (i=0; i<s; i++)
    if (dep[s][i]) {
      z = inst[i] -> getCycle() + inst[s] -> getDelay(inst[i]);
      if (z>max) max = z;
    }
  return max;
}

void build_dep_matrix(int **dep, INST **inst, int n) {
  for (int i=0; i<n; i++) {
    dep[i][i]=0;
    for (int j=0; j<i; j++)
      dep[i][j] = ( inst[i]->IsDep(inst[j]) != 0 );
  }
}

INST   **instr;
int    **dep;

void reorder(BB *bb) {
  int    i, to_be_scheduled, cycle_min, nasm, offset, branch_seen,brindex,last_cycle;
  TRES   *res_table = new TRES;  // need a reservation table

  nasm = bb -> numberOfAsm();
  instr = new (INST *)[nasm];   // to avoid calling getAsm each time we need it
  for (i=0; i<nasm; i++) instr[i] = bb -> getAsm(i+1);

  build_dep_matrix(dep, instr, nasm);  // build the dependence matrix
  branch_seen = last_cycle = 0;

  to_be_scheduled = nasm;     // number of instructions to be scheduled
  while (to_be_scheduled && !branch_seen) { // before a branch instruction
    for (i=0; i < nasm; i++) {
      if (instr[i] -> isCTI()) {
	brindex = i;
	branch_seen = 1;
	break;
      }
      // Is this instruction already scheduled ?
      if ( (instr[i]->getCycle()) < 0 ) { 
	// Are all the predecessors scheduled ?
	if (verify_predecessors(i, dep, instr)) {  
	  // Wait for data dependencies to be resolved
	  cycle_min = earliest_cycle(i, dep, instr);
	  // Now wait for resources to be available...
	  offset = 0; 
	  while (res_table->IsConflict(instr[i],cycle_min+offset)) offset++;
	  // Mark resources occupancy into reservation table
	  res_table -> markRes(instr[i], cycle_min + offset);
	  if (cycle_min + offset > last_cycle) last_cycle = cycle_min+offset;
	  // Specify the cycle
	  instr[i] -> setCycle(cycle_min + offset); 
	  to_be_scheduled--;
	  break;
	}
      }
    }
  }
  // The case of the branch instruction
  if (branch_seen) { 
    instr[brindex] -> setCycle(last_cycle + 1);
    to_be_scheduled--;
  }
  // The delay slot instruction, if any
  if (to_be_scheduled) instr[nasm-1] -> setCycle(last_cycle + 2);

  // Reorder according to values specified by setCycle()
  bb -> orderAccordingToCycles(); 
  bb -> addNecessaryNops();
  delete res_table; 
  delete instr;
}