mips.cpp

一个面向对像语言的编译器

/*
 * File: mips.cc
 * -------------
 * Implementation of Mips class, which is responsible for TAC->MIPS
 * translation, register allocation, etc.
 *
 * Julie Zelenski academic year 2001-02 for CS143
 * Loosely based on some earlier work by Steve Freund
 *
 * A simple final code generator to translate Tac to MIPS.
 * It uses simplistic algorithms, in particular, its register handling
 * and spilling strategy is inefficient to the point of begin mocked
 * by elementary school children.
 */

#include "mips.h"
#include "declaration.h"
#include <stdarg.h>

/* Method: GetRegister
 * -------------------
 * Given a decl for a current var, a reason (ForRead or ForWrite)
 * and up to two registers to avoid, this method will assign
 * to a var to register trying these alternatives in order:
 *  1) if that var is already in a register ("same" is determined
 *     by matching name and same scope), we use that one
 *  2) find an empty register to use for the var
 *  3) find an in-use register that is not dirty.  We don't need
 *     to write value back to memory since it's clean, so we just
 *     replace with the new var
 *  4) spill an in-use, dirty register, by writing its contents to
 *     memory and then replace with the new var
 * For steps 3 & 4, we respect the registers given to avoid (ie the
 * other operands in this operation). The register descriptors are
 * updated to show the new state of the world. If for read, we
 * load the current value from memory into the register. If for
 * write, we mark the register as dirty (since it is getting a
 * new value).
 */
Mips::Register Mips::GetRegister(Declaration *var, Reason reason,
					   Register avoid1, Register avoid2)
{
  Register reg;

  if (!FindRegisterWithContents(var, reg)) {
    if (!FindRegisterWithContents(NULL, reg)) { 
	reg = SelectRegisterToSpill(avoid1, avoid2);
	SpillRegister(reg);
    }
    regs[reg].decl = var;
    if (reason == ForRead) {                 // load current value
	Assert(var->GetOffset() != Unassigned);
	const char *offsetFromWhere = var->IsGlobal() ? regs[gp].name : regs[fp].name;
	Emit("lw %s, %d(%s)\t# load %s from %s%+d into %s", regs[reg].name,
	     var->GetOffset(), offsetFromWhere, var->GetName(),
	     offsetFromWhere, var->GetOffset(), regs[reg].name);
	regs[reg].isDirty = false;
    }
  }
  if (reason == ForWrite)
    regs[reg].isDirty = true;
  return reg;
}


// Two covers for the above method to make it slightly more
// convenient to call it
Mips::Register Mips::GetRegister(Declaration *var, Register avoid1)
{
  return GetRegister(var, ForRead, avoid1, zero);
}

Mips::Register Mips::GetRegisterForWrite(Declaration *var, Register avoid1,
						     Register avoid2)
{
  return GetRegister(var, ForWrite, avoid1, avoid2);
} 



/* Helper function: SameDecl
 * -------------------------
 * Two decls are considered the same if they have the same name and
 * the same scope. We use this when determining if the current variable
 * slaved to a register is the same as a variable we are trying to
 * locate.
 */
static bool SameDecl(Declaration *one, Declaration *two)
{
  if (one == two) return true;
  if (!one || !two ) return false;
  return (!strcmp(one->GetName(), two->GetName()) &&
	    one->GetScope() == two->GetScope());
}


/* Method: FindRegisterWithContents
 * --------------------------------
 * Searches the descriptors for one with contents var. Assigns
 * register by reference, and returns true/false on whether match found.
 */
bool Mips::FindRegisterWithContents(Declaration *var, Register& reg)
{
  for (reg = zero; reg < NumRegs; reg = Register(reg+1)) {
    if (regs[reg].isGeneralPurpose && SameDecl(var, regs[reg].decl))
	return true;
  }
  return false;
}


/* Method: SelectRegisterToSpill
 * -----------------------------
 * Chooses an in-use register to replace with a new variable. We
 * prefer to replace a non-dirty once since we would not have to
 * write its contents back to memory, so the first loop searches
 * for a clean one. If none found, we take a dirty one.  In both
 * loops we deliberately won't choose either of the registers we
 * were asked to avoid.  We track the last dirty register spilled
 * and advance on each subsequent spill as a primitive means of
 * trying to not throw out things we just loaded and thus are likely
 * to need.
 */
Mips::Register Mips::SelectRegisterToSpill(Register avoid1, Register avoid2)
{
            // first hunt for a non-dirty one, since no work to spill
  for (Register i = zero; i < NumRegs; i = (Register)(i+1)) {
    if (i != avoid1 && i != avoid2 && regs[i].isGeneralPurpose &&
	  !regs[i].isDirty)
	return i;
  }
  do {      // otherwise just pick the next usuable register
    lastUsed = (Register)((lastUsed + 1) % NumRegs);
  } while (lastUsed == avoid1 || lastUsed == avoid2 ||
           !regs[lastUsed].isGeneralPurpose);
  return lastUsed;
}


/* Method: SpillRegister
 * ---------------------
 * "Empties" register.  If variable is currently slaved in this register
 * and its contents are out of synch with memory (isDiry), we write back
 * the current contents to memory. We then clear the descriptor so we
 * realize the register is empty.
 */
void Mips::SpillRegister(Register reg)
{
  Declaration *var = regs[reg].decl;
  if (var && regs[reg].isDirty) {
    const char *offsetFromWhere = var->IsGlobal() ? regs[gp].name : regs[fp].name;
    Assert(var->GetOffset() != Unassigned);
    Emit("sw %s, %d(%s)\t# spill %s from %s to %s%+d", regs[reg].name,
	   var->GetOffset(), offsetFromWhere, var->GetName(), regs[reg].name,
	   offsetFromWhere,var->GetOffset());
  }
  regs[reg].decl = NULL;
}       


/* Method: SpillAllDirtyRegisters
 * ------------------------------
 * Used before flow of control change (branch, label, jump, etc.) to
 * save contents of all dirty registers. This synchs the contents of
 * the registers with the memory locations for the variables.
 */
void Mips::SpillAllDirtyRegisters()
{
  Register i;
  for (i = zero; i < NumRegs; i = Register(i+1)) 
    if (regs[i].decl && regs[i].isDirty) break;
  if (i != NumRegs) // none are dirty, don't print message to avoid confusion
    Emit("# (save modified registers before flow of control change)");
  for (i = zero; i < NumRegs; i = Register(i+1)) 
    SpillRegister(i);
}


/* Method: SpillForEndFunction
 * ---------------------------
 * Slight optimization on the above method used when spilling for
 * end of function (return/fall off). In such a case, we do not
 * need to save values for locals, temps, and parameters because the
 * function is about to exit and those variables are going away
 * immediately, so no need to bother with updating contents.
 */
void Mips::SpillForEndFunction()
{
  for (Register i = zero; i < NumRegs; i = Register(i+1)) {
    if (regs[i].isGeneralPurpose && regs[i].decl) {
	if (regs[i].decl->IsGlobal())
	  SpillRegister(i);
	else  // all stack variables can just be tossed at end func
	  regs[i].decl = NULL;
    }
  }
}


/* Method: Emit
 * ------------
 * General purpose helper used to emit assembly instructions in
 * a reasonable tidy manner.  Takes printf-style formatting strings
 * and variable arguments.
 */
void Mips::Emit(const char *fmt, ...)
{
  va_list args;
  char buf[1024];
  
  va_start(args, fmt);
  vsprintf(buf, fmt, args);
  va_end(args);
  if (buf[strlen(buf) - 1] != ':') printf("\t"); // don't tab in labels
  if (buf[0] != '#') printf("  ");   // outdent comments a little
  printf("%s", buf);
  if (buf[strlen(buf)-1] != '\n') printf("\n"); // end with a newline
}



/* Method: EmitLoadConstant
 * ------------------------
 * Used to assign variable an integer constant value.  Slaves dst into
 * a register (using GetRegister above) and then emits an li (load
 * immediate) instruction with the constant value.
 */
void Mips::EmitLoadConstant(Declaration *dst, int val)
{
  Register reg = GetRegisterForWrite(dst);
  Emit("li %s, %d\t\t# load constant value %d into %s", regs[reg].name,
	 val, val, regs[reg].name);
}

/* Method: EmitLoadStringConstant
 * ------------------------------
 * Used to assign a variable a pointer to string constant. Emits
 * assembly directives to create a new null-terminated string in the
 * data segment and assigns it a unique label. Slaves dst into a register
 * and loads that label address into the register.
 */
void Mips::EmitLoadStringConstant(Declaration *dst, const char *str)
{
  static int strNum = 1;
  char label[16];
  sprintf(label, "_string%d", strNum++);
  Emit(".data\t\t\t# create string constant marked with label");
  Emit("%s: .asciiz %s", label, str);
  Emit(".text");
  EmitLoadLabel(dst, label);
}


/* Method: EmitLoadLabel
 * ---------------------
 * Used to load a label (ie address in text/data segment) into a variable.
 * Slaves dst into a register and emits an la (load address) instruction
 */
void Mips::EmitLoadLabel(Declaration *dst, const char *label)
{
  Register reg = GetRegisterForWrite(dst);
  Emit("la %s, %s\t# load label", regs[reg].name, label);
}
 

/* Method: EmitCopy
 * ----------------
 * Used to copy the value of one variable to another.  Slaves both
 * src and dst into registers and then emits a move instruction to
 * copy the contents from src to dst.
 */
void Mips::EmitCopy(Declaration *dst, Declaration *src)
{
  Register rSrc = GetRegister(src), rDst = GetRegisterForWrite(dst, rSrc);
  Emit("move %s, %s\t\t# copy value", regs[rDst].name, regs[rSrc].name);

}


/* Method: EmitLoad
 * ----------------
 * Used to assign dst the contents of memory at the address in reference,
 * potentially with some positive/negative offset (defaults to 0).
 * Slaves both ref and dst to registers, then emits a lw instruction
 * using constant-offset addressing mode y(rx) which accesses the address
 * at an offset of y bytes from the address currently contained in rx.
 */
void Mips::EmitLoad(Declaration *dst, Declaration *reference, int offset)
{
  Register rSrc = GetRegister(reference), rDst = GetRegisterForWrite(dst, rSrc);
  Emit("lw %s, %d(%s) \t# load with offset", regs[rDst].name,
	 offset, regs[rSrc].name);
}


/* Method: EmitStore
 * -----------------
 * Used to write value to  memory at the address in reference,
 * potentially with some positive/negative offset (defaults to 0).
 * Slaves both ref and dst to registers, then emits a sw instruction
 * using constant-offset addressing mode y(rx) which writes to the address
 * at an offset of y bytes from the address currently contained in rx.
 */
void Mips::EmitStore(Declaration *reference, Declaration *value, int offset)
{
  Register rVal = GetRegister(value), rRef = GetRegister(reference, rVal);
  Emit("sw %s, %d(%s) \t# store with offset",
	 regs[rVal].name, offset, regs[rRef].name);
}


/* Method: EmitBinaryOp
 * --------------------
 * Used to perform a binary operation on 2 operands and store result
 * in dst. All binary forms for arithmetic, logical, relational, equality
 * use this method. Slaves both operands and dst to registers, then
 * emits the appropriate instruction by looking up the mips name
 * for the particular op code.
 */
void Mips::EmitBinaryOp(Tac::OpCode code, Declaration *dst, 
				 Declaration *op1, Declaration *op2)
{
  Register rLeft = GetRegister(op1), rRight = GetRegister(op2, rLeft);
  Register rDst = GetRegisterForWrite(dst, rLeft, rRight);
  Emit("%s %s, %s, %s\t", NameForTac(code), regs[rDst].name,
	 regs[rLeft].name, regs[rRight].name);

}


/* Method: EmitLabel
 * -----------------
 * Used to emit label marker. Before a label, we spill all registers since
 * we can't be sure what the situation upon arriving at this label (ie
 * starts new basic block), and rather than try to be clever, we just
 * wipe the slate clean.
 */
void Mips::EmitLabel(const char *label)
{ 
  SpillAllDirtyRegisters(); 
  Emit("%s:", label);
}


/* Method: EmitGoto
 * ----------------
 * Used for an unconditional transfer to a named label. Before a goto,
 * we spill all registers, since we don't know what the situation is
 * we are heading to (ie this ends current basic block) and rather than
 * try to be clever, we just wipe slate clean.
 */
void Mips::EmitGoto(const char *label)
{
  SpillAllDirtyRegisters(); 
  Emit("b %s\t\t# unconditional branch", label);
}


/* Method: EmitIfZ
 * ---------------
 * Used for a conditional branch based on value of test variable.
 * We slave test var to register and use in the emitted test instruction,
 * either beqz. See comments above on Goto for why we spill