[Pearcolator-devel] SF.net SVN: pearcolator: [153] src/org/binarytranslator

[<mic...@us...>]

Revision: 153
          http://pearcolator.svn.sourceforge.net/pearcolator/?rev=153&view=rev
Author:   michael_baer
Date:     2007-08-02 05:22:44 -0700 (Thu, 02 Aug 2007)

Log Message:
-----------
- Allowing to load/save branch profiles
- Added generic profiling to the Interpreter
- Added support for staged emulation

Modified Paths:
--------------
    src/org/binarytranslator/DBT_Options.java
    src/org/binarytranslator/Main.java
    src/org/binarytranslator/arch/arm/decoder/ARM_Disassembler.java
    src/org/binarytranslator/arch/arm/decoder/ARM_Interpreter.java
    src/org/binarytranslator/arch/arm/decoder/ARM_Translator.java
    src/org/binarytranslator/arch/arm/os/abi/semihosting/AngelSystemCalls.java
    src/org/binarytranslator/generic/branchprofile/BranchProfile.java
    src/org/binarytranslator/generic/branchprofile/CallAndReturnAddress.java
    src/org/binarytranslator/generic/branchprofile/ProcedureInformation.java
    src/org/binarytranslator/generic/execution/ExecutionController.java
    src/org/binarytranslator/generic/execution/InterpreterController.java
    src/org/binarytranslator/generic/execution/PredecodingThreadedInterpreter.java

Added Paths:
-----------
    src/org/binarytranslator/generic/execution/ProfilingInterpreterController.java
    src/org/binarytranslator/generic/execution/StagedEmulationController.java

Modified: src/org/binarytranslator/DBT_Options.java
===================================================================
--- src/org/binarytranslator/DBT_Options.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/DBT_Options.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -49,7 +49,13 @@
   
   /** Determines how the program will be run (i.e. interpreted, translated etc.) */
   public static ExecutionController.Type executionController = ExecutionController.Type.Translator;
+  
+  /** A filename to which the runtime profiling information shall be saved. */
+  public static String saveProfileToFile = null;
 
+  /** A filename from which the runtime profiling information shall be loaded. */
+  public static String loadProfileFromFile = null;
+
   /**
    * Favour backward branch optimization. Translate backward branch addresses
    * before the next instructions (this is the manner of the 601's branch
@@ -183,7 +189,12 @@
       gdbStubPort = Integer.parseInt(value);
     } else if (arg.equalsIgnoreCase("controller")) {
       executionController = ExecutionController.Type.valueOf(value);
-    } else {
+    } else if (arg.equalsIgnoreCase("loadProfile")) {
+      loadProfileFromFile = arg;
+    } else if (arg.equalsIgnoreCase("saveProfile")) {
+      saveProfileToFile = arg;
+    }
+    else {
       throw new Error("Unknown DBT option: " + arg);
     }
   }

Modified: src/org/binarytranslator/Main.java
===================================================================
--- src/org/binarytranslator/Main.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/Main.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -9,12 +9,14 @@
 package org.binarytranslator;
 
 import java.io.File;
-
 import org.binarytranslator.generic.execution.PredecodingThreadedInterpreter;
 import org.binarytranslator.generic.execution.DynamicTranslationController;
 import org.binarytranslator.generic.execution.ExecutionController;
 import org.binarytranslator.generic.execution.GdbController;
 import org.binarytranslator.generic.execution.InterpreterController;
+import org.binarytranslator.generic.execution.ProfilingInterpreterController;
+import org.binarytranslator.generic.execution.ProfilingPredecodingInterpreter;
+import org.binarytranslator.generic.execution.StagedEmulationController;
 import org.binarytranslator.generic.os.loader.Loader;
 import org.binarytranslator.generic.os.process.ProcessSpace;
 
@@ -93,10 +95,6 @@
       System.err.println("Error accesing file: " + args[0] + ". " + e.getMessage());
       return;
     }
-    /*catch (Error e) {
-      System.err.println(e.getMessage());
-      return;
-    }*/
 
     report("Sucessfully created process.");
     
@@ -108,20 +106,35 @@
     //on SUN's VM, only the interpreter has been tested 
     if (DBT_Options.buildForSunVM) {
       DBT_Options.executionController = ExecutionController.Type.PredecodingInterpreter;
-      
     }
     
+    //load a previously saved branch profile from file, if the user requested it
+    try {
+      if (DBT_Options.loadProfileFromFile != null)
+        ps.branchInfo.loadFromXML(DBT_Options.loadProfileFromFile);
+    } catch (Exception e) {
+      System.err.println("Error loading branch profile from: " + DBT_Options.loadProfileFromFile);
+      e.printStackTrace();
+      return;
+    }
+    
     //Create an execution controller and pass execution on to it
     ExecutionController controller = null;
     
     switch (DBT_Options.executionController) {
     
+      case StagedEmulation:
+        controller = new StagedEmulationController(ps);
+        break;
+    
       case PredecodingInterpreter:
-        controller = new PredecodingThreadedInterpreter(ps); //new PredecodingThreadedInterpreter(ps);
-      break;
+        controller = DBT_Options.profileDuringInterpretation ? 
+            new ProfilingPredecodingInterpreter(ps) : new PredecodingThreadedInterpreter(ps);
+        break;
       
       case Interpreter:
-        controller = new InterpreterController(ps);
+        controller = DBT_Options.profileDuringInterpretation ? 
+            new ProfilingInterpreterController(ps) : new InterpreterController(ps);
         break;
         
       case Translator:
@@ -143,10 +156,11 @@
   public static void onExit(int exitcode) {
     System.out.println("\nProgram has finished. Exitcode: " + exitcode);
     
-    /*try {
-      //ps.branchInfo.saveAsXML("/tmp/profile.xml");
-    } catch (IOException e) {
+    try {
+      if (DBT_Options.saveProfileToFile != null)
+        ps.branchInfo.saveAsXML(DBT_Options.saveProfileToFile);
+    } catch (Exception e) {
       e.printStackTrace();
-    }*/
+    }
   }
 }

Modified: src/org/binarytranslator/arch/arm/decoder/ARM_Disassembler.java
===================================================================
--- src/org/binarytranslator/arch/arm/decoder/ARM_Disassembler.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/arch/arm/decoder/ARM_Disassembler.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -20,7 +20,6 @@
 import org.binarytranslator.arch.arm.decoder.ARM_Instructions.UndefinedInstruction;
 import org.binarytranslator.arch.arm.decoder.ARM_Instructions.Instruction.Condition;
 import org.binarytranslator.arch.arm.os.process.ARM_ProcessSpace;
-import org.binarytranslator.generic.decoder.DisassembledInstruction;
 import org.binarytranslator.generic.decoder.Disassembler;
 
 /**

Modified: src/org/binarytranslator/arch/arm/decoder/ARM_Interpreter.java
===================================================================
--- src/org/binarytranslator/arch/arm/decoder/ARM_Interpreter.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/arch/arm/decoder/ARM_Interpreter.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -385,7 +385,7 @@
       this.conditionalInstruction = i;
       
       conditionTrueSuccessor = conditionalInstruction.getSuccessor(pc);
-      boolean inThumbMode = (pc & 1) == 0;
+      boolean inThumbMode = (pc & 1) == 1;
       
       if (conditionTrueSuccessor == pc + 4 && !inThumbMode)
         successorInstruction = conditionTrueSuccessor; //ARM may have conditional instruction that are not jumps

Modified: src/org/binarytranslator/arch/arm/decoder/ARM_Translator.java
===================================================================
--- src/org/binarytranslator/arch/arm/decoder/ARM_Translator.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/arch/arm/decoder/ARM_Translator.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -58,11 +58,10 @@
   public int translateInstruction(int pc, ARM_Laziness lazy) {
     this.pc = pc;
     this.lazy = lazy;
-    boolean thumb = (pc & 1) != 0;
     int instruction;
     
     try {
-      if (thumb)
+      if (inThumb())
         instruction = ps.memory.loadInstruction16(pc & 0xFFFFFFFE);
       else
         instruction = ps.memory.loadInstruction32(pc);
@@ -88,7 +87,7 @@
     }
     ARM_Instruction instr;
     
-    if (thumb)
+    if (inThumb())
       instr = ARM_InstructionDecoder.Thumb.decode((short)instruction, translatorFactory);
     else
       instr = ARM_InstructionDecoder.ARM32.decode(instruction, translatorFactory);
@@ -756,79 +755,99 @@
       arm2ir.getCurrentBlock().insertOut(nextInstruction);
       arm2ir.getCurrentBlock().insertOut(condBlock);
       
+      //Query the branch profile to get the probability that this instruction is going to get executed
+      float skipProbability = ps.branchInfo.getBranchProbability(pc, pc + (inThumb() ? 2 : 4));
+      OPT_BranchProfileOperand profileOperand;
+      
+      if (skipProbability == -1 || skipProbability == 0.5f) {
+        profileOperand = new OPT_BranchProfileOperand();
+      }
+      else if (skipProbability > 0.8f) {
+        profileOperand = OPT_BranchProfileOperand.always();
+      }
+      else if (skipProbability > 0.5f) {
+        profileOperand = OPT_BranchProfileOperand.likely();
+      }
+      else if (skipProbability < 0.2f) {
+        profileOperand = OPT_BranchProfileOperand.never();
+      }
+      else {
+        profileOperand = OPT_BranchProfileOperand.unlikely();
+      }
+      
       switch (condition) {
       case AL:
         throw new RuntimeException("ARM32 instructions with a condition of AL (always) should not be decorated with a ConditionalDecorator.");
         
       case CC:
         //return !regs.isCarrySet();
-        translateCondition(nextInstruction, arm2ir.getCarryFlag(), OPT_ConditionOperand.NOT_EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getCarryFlag(), OPT_ConditionOperand.NOT_EQUAL());
         break;
         
       case CS:
         //return regs.isCarrySet();
-        translateCondition(nextInstruction, arm2ir.getCarryFlag(), OPT_ConditionOperand.EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getCarryFlag(), OPT_ConditionOperand.EQUAL());
         break;
         
       case EQ:
         //return regs.isZeroSet();
-        translateCondition(nextInstruction, arm2ir.getZeroFlag(), OPT_ConditionOperand.EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getZeroFlag(), OPT_ConditionOperand.EQUAL());
         break;
         
       case GE:
         //return regs.isNegativeSet() == regs.isOverflowSet();
-        translateCondition(nextInstruction, arm2ir.getNegativeFlag(), OPT_ConditionOperand.EQUAL(), arm2ir.getOverflowFlag());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getNegativeFlag(), OPT_ConditionOperand.EQUAL(), arm2ir.getOverflowFlag());
         break;
         
       case GT:
-        translateCondition_GT(nextInstruction);
+        translateCondition_GT(nextInstruction, profileOperand);
         break;
         
       case HI:
-        translateCondition_HI(nextInstruction);
+        translateCondition_HI(nextInstruction, profileOperand);
         break;
         
       case LE:
-        translateCondition_LE(nextInstruction);
+        translateCondition_LE(nextInstruction, profileOperand);
         break;
         
       case LS:
-        translateCondition_LS(nextInstruction, condBlock);
+        translateCondition_LS(nextInstruction, profileOperand, condBlock);
         break;
         
       case LT:
         //return regs.isNegativeSet() != regs.isOverflowSet();
-        translateCondition(nextInstruction, arm2ir.getNegativeFlag(), OPT_ConditionOperand.NOT_EQUAL(), arm2ir.getOverflowFlag());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getNegativeFlag(), OPT_ConditionOperand.NOT_EQUAL(), arm2ir.getOverflowFlag());
         break;
         
       case MI:
         //return regs.isNegativeSet();
-        translateCondition(nextInstruction, arm2ir.getNegativeFlag(), OPT_ConditionOperand.EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getNegativeFlag(), OPT_ConditionOperand.EQUAL());
         break;
         
       case NE:
         //return !regs.isZeroSet();
-        translateCondition(nextInstruction, arm2ir.getZeroFlag(), OPT_ConditionOperand.NOT_EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getZeroFlag(), OPT_ConditionOperand.NOT_EQUAL());
         break;
         
       case NV:
         //never execute this instruction
-        translateCondition(nextInstruction, new OPT_IntConstantOperand(0), OPT_ConditionOperand.EQUAL());
+        translateCondition(nextInstruction, profileOperand, new OPT_IntConstantOperand(0), OPT_ConditionOperand.EQUAL());
         break;
         
       case PL:
         //return !regs.isNegativeSet();
-        translateCondition(nextInstruction, arm2ir.getNegativeFlag(), OPT_ConditionOperand.NOT_EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getNegativeFlag(), OPT_ConditionOperand.NOT_EQUAL());
         break;
         
       case VC:
         //return !regs.isOverflowSet();
-        translateCondition(nextInstruction, arm2ir.getOverflowFlag(), OPT_ConditionOperand.NOT_EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getOverflowFlag(), OPT_ConditionOperand.NOT_EQUAL());
         break;
         
       case VS:
         //return regs.isOverflowSet();
-        translateCondition(nextInstruction, arm2ir.getOverflowFlag(), OPT_ConditionOperand.EQUAL());
+        translateCondition(nextInstruction, profileOperand, arm2ir.getOverflowFlag(), OPT_ConditionOperand.EQUAL());
         break;
         
         default:
@@ -839,17 +858,17 @@
       conditionalInstruction.translate();
     }
     
-    private void translateCondition(OPT_BasicBlock nextInstruction, OPT_Operand operand, OPT_ConditionOperand condition) {
-      translateCondition(nextInstruction, operand, condition, new OPT_IntConstantOperand(1));
+    private void translateCondition(OPT_BasicBlock nextInstruction, OPT_BranchProfileOperand skipProbability, OPT_Operand operand, OPT_ConditionOperand condition) {
+      translateCondition(nextInstruction, skipProbability, operand, condition, new OPT_IntConstantOperand(1));
     }
     
-    private void translateCondition(OPT_BasicBlock nextInstruction, OPT_Operand lhs, OPT_ConditionOperand condition, OPT_Operand rhs) {
+    private void translateCondition(OPT_BasicBlock nextInstruction, OPT_BranchProfileOperand skipProbability, OPT_Operand lhs, OPT_ConditionOperand condition, OPT_Operand rhs) {
       
       condition = condition.flipCode();
-      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), lhs, rhs, condition, nextInstruction.makeJumpTarget(), new OPT_BranchProfileOperand()));
+      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), lhs, rhs, condition, nextInstruction.makeJumpTarget(), skipProbability));
     }
     
-    private void translateCondition_HI(OPT_BasicBlock nextInstruction) {
+    private void translateCondition_HI(OPT_BasicBlock nextInstruction, OPT_BranchProfileOperand skipProbability) {
       //return regs.isCarrySet() && !regs.isZeroSet();
       OPT_Operand carry = arm2ir.getCarryFlag();
       OPT_Operand zero = arm2ir.getZeroFlag();
@@ -858,10 +877,10 @@
       arm2ir.appendInstruction(BooleanCmp2.create(BOOLEAN_CMP2_INT_OR, result, carry,
           new OPT_IntConstantOperand(0), OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand(), zero, new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand()));
       
-      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), new OPT_BranchProfileOperand()));
+      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), skipProbability));
     }
     
-    private void translateCondition_LS(OPT_BasicBlock nextInstruction, OPT_BasicBlock actualInstruction) {
+    private void translateCondition_LS(OPT_BasicBlock nextInstruction, OPT_BranchProfileOperand skipProbability, OPT_BasicBlock actualInstruction) {
       //return !regs.isCarrySet() || regs.isZeroSet();
       OPT_Operand carry = arm2ir.getCarryFlag();
       OPT_Operand zero = arm2ir.getZeroFlag();
@@ -869,7 +888,7 @@
       OPT_RegisterOperand result = arm2ir.getTempInt(0);
       
       arm2ir.appendInstruction(BooleanCmp2.create(BOOLEAN_CMP2_INT_AND, result, carry, new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand(), zero, new OPT_IntConstantOperand(0), OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand()));
-      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), new OPT_BranchProfileOperand()));
+      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), skipProbability));
       
 /*      cond1.deleteNormalOut();
       cond1.insertOut(cond2);
@@ -885,7 +904,7 @@
       cond2.insertOut(actualInstruction);*/
     }
     
-    private void translateCondition_GT(OPT_BasicBlock nextInstruction) {
+    private void translateCondition_GT(OPT_BasicBlock nextInstruction, OPT_BranchProfileOperand skipProbability) {
       //return (regs.isNegativeSet() == regs.isOverflowSet()) && !regs.isZeroSet();
       OPT_Operand negative = arm2ir.getNegativeFlag();
       OPT_Operand overflow = arm2ir.getOverflowFlag();
@@ -895,10 +914,10 @@
       arm2ir.appendInstruction(BooleanCmp2.create(BOOLEAN_CMP2_INT_OR, result, negative,
           overflow, OPT_ConditionOperand.NOT_EQUAL(), new OPT_BranchProfileOperand(), zero, new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand()));
       
-      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), new OPT_BranchProfileOperand()));
+      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), skipProbability));
     }
     
-    private void translateCondition_LE(OPT_BasicBlock nextInstruction) {
+    private void translateCondition_LE(OPT_BasicBlock nextInstruction, OPT_BranchProfileOperand skipProbability) {
       //return regs.isZeroSet() || (regs.isNegativeSet() != regs.isOverflowSet());
       OPT_Operand negative = arm2ir.getNegativeFlag();
       OPT_Operand overflow = arm2ir.getOverflowFlag();
@@ -908,7 +927,7 @@
       arm2ir.appendInstruction(BooleanCmp2.create(BOOLEAN_CMP2_INT_AND, result, negative,
           overflow, OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand(), zero, new OPT_IntConstantOperand(0), OPT_ConditionOperand.EQUAL(), new OPT_BranchProfileOperand()));
       
-      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), new OPT_BranchProfileOperand()));
+      arm2ir.appendInstruction(IfCmp.create(INT_IFCMP, arm2ir.getTempValidation(0), result.copy(), new OPT_IntConstantOperand(1), OPT_ConditionOperand.EQUAL(), nextInstruction.makeJumpTarget(), skipProbability));
     }
     
     @Override

Modified: src/org/binarytranslator/arch/arm/os/abi/semihosting/AngelSystemCalls.java
===================================================================
--- src/org/binarytranslator/arch/arm/os/abi/semihosting/AngelSystemCalls.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/arch/arm/os/abi/semihosting/AngelSystemCalls.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -13,6 +13,7 @@
 
 import org.binarytranslator.DBT;
 import org.binarytranslator.DBT_Options;
+import org.binarytranslator.Main;
 import org.binarytranslator.arch.arm.os.process.ARM_ProcessSpace;
 
 /**
@@ -691,6 +692,7 @@
     @Override
     public void execute() {
       ps.finished = true;
+      Main.onExit(0);
     }
     
   }

Modified: src/org/binarytranslator/generic/branchprofile/BranchProfile.java
===================================================================
--- src/org/binarytranslator/generic/branchprofile/BranchProfile.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/generic/branchprofile/BranchProfile.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -121,7 +121,7 @@
           throw new IOException("File is not a valid XML branch profile.");
         
         int targetAddress = Integer.parseInt(((Element)target).getAttribute("address"));
-        int branchCount = Integer.parseInt(((Element)target).getAttribute("address"));
+        int branchCount = Integer.parseInt(((Element)target).getAttribute("branchCount"));
         targetsAndFrequencies.put(targetAddress, branchCount);
       }
       
@@ -131,8 +131,6 @@
     public void toXML(Document doc, Element parentNode) {
       Element branchInfo = parentNode;
       
-      Element targets = doc.createElement("targets");
-      
       for (Entry<Integer, Integer> branchTarget : destinationsAndFrequencies.entrySet()) {
         int targetAddress = branchTarget.getKey();
         int branchCount = branchTarget.getValue();
@@ -142,8 +140,6 @@
         branchTargetElement.setAttribute("address", Integer.toString(targetAddress));
         branchTargetElement.setAttribute("branchCount", Integer.toString(branchCount));
       }
-      
-      branchInfo.appendChild(targets);
     }
   }
 
@@ -243,6 +239,33 @@
       branchSites.put(origin, branch);
     }
   }
+  
+  /**
+   * Returns the probability of a branch from <code>origin</code> to <code>target</code>.
+   * 
+   * @param origin
+   *  The address at which the branch is taking place.
+   * @param target
+   *  The address to which the branch is taking place.
+   * @return
+   *  The probability of the branch as a value between 0 and 1. The function returns -1, if the probability
+   *  cannot be estimated.
+   */
+  public float getBranchProbability(int origin, int target) {
+    BranchInformation branch = branchSites.get(origin);
+    
+    if (branch == null || branch.executionCount == 0) {
+      return -1f;
+    }
+    
+    Integer branchesToTarget = branch.getTargetsAndFrequencies().get(target);
+    
+    if (branchesToTarget == null) {
+      return 0f;
+    }
+    
+    return branchesToTarget / (float)branch.executionCount;
+  }
 
   /**
    * Given an address within a procedure, returns the (most likely) procedure
@@ -271,7 +294,15 @@
    *  The address to which it took place.
    */
   public void profileBranch(int origin, int target) {
-    throw new RuntimeException("Not yet implemented.");
+ 
+    BranchInformation branch = branchSites.get(origin);
+    
+    if (branch == null) {
+      branch = new BranchInformation();
+      branchSites.put(origin, branch);
+    }
+    
+    branch.profile(target);
   }
   
   /**
@@ -288,8 +319,21 @@
     return (branch == null) ? null : branch.getTargets();
   }
   
+  /**
+   * Loads a branch profile from a file.
+   * 
+   * @param filename
+   *  The name of the file that the branch profile is loaded from.
+   * @throws IOException
+   *  An exception that is thrown if an error occurs reading that file.
+   */
   public void loadFromXML(String filename) throws IOException {
 
+    //clear previous profile data
+    procedures.clear();
+    branchSites.clear();
+    
+    //create a XML document builder and an XML document
     DocumentBuilderFactory docBuilderFactory = DocumentBuilderFactory.newInstance();
     Document doc;
     try {
@@ -303,34 +347,54 @@
     
     if (DBT.VerifyAssertions) DBT._assert(doc != null);
     
+    //Check the root-name of the document
     Element root = doc.getDocumentElement();
-
     if (!root.getNodeName().equals("branch-profile"))
       throw new IOException("File is not a valid XML branch profile.");
     
-    Node branches = null;
-    
+    //interate over the main document, parsing the different sections
     for (int i = 0; i < root.getChildNodes().getLength(); i++) {
-      Node node = root.getChildNodes().item(0);
+      Node node = root.getChildNodes().item(i);
+      String nodeName = node.getNodeName();
       
-      if (node.getNodeName().equals("branches")) {
-        branches = node;
-        break;
+      if (node.getNodeType() != Node.ELEMENT_NODE) {
+        continue;
       }
-    }
-    
-    if (branches == null)
-      throw new IOException("File is not a valid XML branch profile.");
-    
-    for (int i = 0; i < branches.getChildNodes().getLength(); i++) {
-      Node siteNode = branches.getChildNodes().item(i);
       
-      if (!siteNode.getNodeName().equals("origin") || siteNode.getNodeType() != Node.ELEMENT_NODE)
-        throw new IOException("File is not a valid XML branch profile.");
+      if (nodeName.equals("branches")) {
       
-      int address = Integer.parseInt(((Element)siteNode).getAttribute("address"));
-      BranchInformation branchInfo = BranchInformation.fromXML((Element)siteNode);
-      branchSites.put(address, branchInfo);
+        //this is the section which contains the branch information.
+        for (int n = 0; n < node.getChildNodes().getLength(); n++) {
+          Node branchNode = node.getChildNodes().item(n);
+          
+          if (branchNode.getNodeType() != Node.ELEMENT_NODE)
+            continue;
+          
+          if (!branchNode.getNodeName().equals("branch"))
+            throw new IOException("File is not a valid XML branch profile.");
+          
+          int address = Integer.parseInt(((Element)branchNode).getAttribute("address"));
+          BranchInformation branchInfo = BranchInformation.fromXML((Element)branchNode);
+          branchSites.put(address, branchInfo);
+        }
+      }
+      else
+      if (nodeName.equals("procedures")) {
+        
+        //this is the section with procedure information
+        for (int n = 0; n < node.getChildNodes().getLength(); n++) {
+          Node procedureInfo = node.getChildNodes().item(n);
+          
+          if (procedureInfo.getNodeType() != Node.ELEMENT_NODE)
+            continue;
+          
+          ProcedureInformation pi = ProcedureInformation.fromXML((Element)procedureInfo);
+          procedures.put(pi.getEntryAddress(), pi);
+        }
+      }
+      else {
+        throw new IOException("This is not a valid XML branch profile.");
+      }
     }
   }
   
@@ -387,6 +451,15 @@
       branchInfo.toXML(doc, branchSiteElement);
     }
     
+    Element proceduresElement = doc.createElement("procedures");
+    root.appendChild(proceduresElement);
+    
+    for (ProcedureInformation procedure : procedures.values()) {
+      Element procedureElement = doc.createElement("procedure");
+      proceduresElement.appendChild(procedureElement);
+      procedure.toXML(doc, procedureElement);
+    }
+    
     //Output the resulting XML document
     TransformerFactory tFactory = TransformerFactory.newInstance();
     Transformer transformer;
@@ -395,6 +468,7 @@
       DOMSource source = new DOMSource(doc);
       StreamResult result = new StreamResult(outputStream);
       transformer.transform(source, result);
+      outputStream.close();
       
     } catch (Exception e) {
       e.printStackTrace();

Modified: src/org/binarytranslator/generic/branchprofile/CallAndReturnAddress.java
===================================================================
--- src/org/binarytranslator/generic/branchprofile/CallAndReturnAddress.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/generic/branchprofile/CallAndReturnAddress.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -12,14 +12,11 @@
  * Object for recording a call site and its corresponding return address
  */
 class CallAndReturnAddress {
-  /**
-   * Call site address
-   */
+  
+  /** The address at which the call is taking place.*/
   private int callSite;
 
-  /**
-   * Return address
-   */
+  /** The address to which the call shall return. */
   private int returnAddress;
 
   /**
@@ -35,24 +32,29 @@
     this.returnAddress = returnAddress;
   }
 
-  /**
-   * Get call site address
-   */
+  /** Get call site address */
   int getCallSite() {
     return callSite;
   }
 
-  /**
-   * Get return address
-   */
+  /** Get return address */
   int getReturnAddress() {
     return returnAddress;
   }
+  
+  @Override
+  public int hashCode() {
+    return callSite;
+  }
 
-  /**
-   * Are two call sites the same?
-   */
+  @Override
   public boolean equals(Object obj) {
-    return ((CallAndReturnAddress) obj).callSite == callSite;
+    
+    if (!(obj instanceof CallAndReturnAddress)) {
+      return false;
+    }
+    
+    CallAndReturnAddress other = ((CallAndReturnAddress) obj);
+    return other.callSite == callSite && other.returnAddress == returnAddress;
   }
 }

Modified: src/org/binarytranslator/generic/branchprofile/ProcedureInformation.java
===================================================================
--- src/org/binarytranslator/generic/branchprofile/ProcedureInformation.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/generic/branchprofile/ProcedureInformation.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -19,20 +19,15 @@
  * Objects capturing information about what looks like a method
  */
 class ProcedureInformation {
-  /**
-   * Entry point to the procedure
-   */
+  
+  /** Entry point to the procedure */
   private final int entry;
 
-  /**
-   * Set of locations that call the procedure and the corressponding return
-   * address
-   */
+  /** Set of locations that call the procedure and the corressponding return
+   *  address. */
   private HashSet<CallAndReturnAddress> callSitesAndReturnAddresses;
 
-  /**
-   * Set of locations within the procedure that return
-   */
+  /** Set of locations within the procedure that return */
   private HashSet<Integer> returnSites;
 
   /**
@@ -50,8 +45,15 @@
     }
   }
   
-  private ProcedureInformation(int entry) {
+  /**
+   * Constructor
+   * 
+   * @param entry
+   *          starting address of the procedure
+   */
+  public ProcedureInformation(int entry) {
     this.entry = entry;
+    callSitesAndReturnAddresses = new HashSet<CallAndReturnAddress>();
   }
 
   /**
@@ -64,23 +66,32 @@
    * @param returnAddress
    *          the corresponding return address
    */
-  ProcedureInformation(int entry, int callSite, int returnAddress) {
-    this.entry = entry;
-    callSitesAndReturnAddresses = new HashSet<CallAndReturnAddress>();
+  public ProcedureInformation(int entry, int callSite, int returnAddress) {
+    this(entry);
+    
     callSitesAndReturnAddresses.add(new CallAndReturnAddress(callSite,
         returnAddress));
   }
+  
+  /**
+   * Returns the address at which this procedure starts.
+   * @return
+   *  The address at which the procedure starts.
+   */
+  public int getEntryAddress() {
+    return entry;
+  }
 
   /**
    * Register a call (branch and link) instruction
    * 
-   * @param pc
-   *          the address of the branch instruction
+   * @param atAddress
+   *          the address of the call instruction
    * @param ret
    *          the address that will be returned to
    */
-  public void registerCall(int pc, int ret) {
-    CallAndReturnAddress call_tuple = new CallAndReturnAddress(pc, ret);
+  public void registerCall(int atAddress, int ret) {
+    CallAndReturnAddress call_tuple = new CallAndReturnAddress(atAddress, ret);
     if (!callSitesAndReturnAddresses.contains(call_tuple)) {
       callSitesAndReturnAddresses.add(call_tuple);
     }
@@ -89,15 +100,15 @@
   /**
    * Register a return (branch to link register) instruction
    * 
-   * @param pc
+   * @param atAddress
    *          the address of the branch instruction
    */
-  public void registerReturn(int pc) {
+  public void registerReturn(int atAddress) {
     if (returnSites == null) {
       returnSites = new HashSet<Integer>();
     }
     
-    returnSites.add(new Integer(pc));
+    returnSites.add(new Integer(atAddress));
   }
   
   /**
@@ -121,13 +132,17 @@
     }
     procedure.appendChild(callSites);
     
-    Element returnSites = doc.createElement("returnsites");
-    for (Integer returnSite : this.returnSites) {
-      Element returnSiteNode = doc.createElement("return");
-      returnSiteNode.setAttribute("at", returnSite.toString());
-      returnSites.appendChild(returnSiteNode);
+    if (returnSites != null) {
+      Element returnSitesElement = doc.createElement("returnsites");
+      procedure.appendChild(returnSitesElement);
+      
+      for (Integer returnSite : returnSites) {
+        Element returnSiteNode = doc.createElement("return");
+        returnSiteNode.setAttribute("at", returnSite.toString());
+        returnSitesElement.appendChild(returnSiteNode);
+      }
+     
     }
-    procedure.appendChild(returnSites);
   }
   
   /**
@@ -156,7 +171,7 @@
           if (callsite.getNodeType() != Node.ELEMENT_NODE)
             continue;
           
-          if (callsite.getNodeName().equals("call"))
+          if (!callsite.getNodeName().equals("call"))
             throw new Error("The given XML node is not a valid ProcedureInformation entity.");
           
           int callFrom = Integer.parseInt(((Element)callsite).getAttribute("from"));
@@ -166,6 +181,9 @@
         }
       }
       else if (childNode.getNodeName().equals("returnsites")) {
+        
+        pi.returnSites = new HashSet<Integer>();
+        
         //parse return sites
         for (int n = 0; n < childNode.getChildNodes().getLength(); n++) {
           Node callsite = childNode.getChildNodes().item(n);
@@ -174,7 +192,7 @@
           if (callsite.getNodeType() != Node.ELEMENT_NODE)
             continue;
           
-          if (callsite.getNodeName().equals("return"))
+          if (!callsite.getNodeName().equals("return"))
             throw new Error("The given XML node is not a valid ProcedureInformation entity.");
           
           int returnAt = Integer.parseInt(((Element)callsite).getAttribute("at"));

Modified: src/org/binarytranslator/generic/execution/ExecutionController.java
===================================================================
--- src/org/binarytranslator/generic/execution/ExecutionController.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/generic/execution/ExecutionController.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -9,6 +9,7 @@
     Translator,
     Interpreter,
     PredecodingInterpreter,
+    StagedEmulation,
     GDB
   }
   

Modified: src/org/binarytranslator/generic/execution/InterpreterController.java
===================================================================
--- src/org/binarytranslator/generic/execution/InterpreterController.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/generic/execution/InterpreterController.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -13,23 +13,16 @@
   @Override
   public void run() {
     Interpreter interpreter = ps.createInterpreter();
-    
     int pc = ps.getCurrentInstructionAddress();
 
     while (!ps.finished) {
       
-      Interpreter.Instruction instruction = interpreter.decode(pc);
-      //System.out.println(String.format("[0x%x] %s", pc, instruction.toString()));
-      
+      Interpreter.Instruction instruction = interpreter.decode(pc);     
       instruction.execute();
-      //System.out.println(ps.toString());
       int nextInstruction = instruction.getSuccessor(pc);
       
       if (nextInstruction == -1) {
         nextInstruction = ps.getCurrentInstructionAddress();
-        
-        if (DBT_Options.profileDuringInterpretation)
-          ps.branchInfo.profileBranch(pc, ps.getCurrentInstructionAddress());
       }
       else {
         ps.setCurrentInstructionAddress(nextInstruction);

Modified: src/org/binarytranslator/generic/execution/PredecodingThreadedInterpreter.java
===================================================================
--- src/org/binarytranslator/generic/execution/PredecodingThreadedInterpreter.java	2007-07-29 13:13:16 UTC (rev 152)
+++ src/org/binarytranslator/generic/execution/PredecodingThreadedInterpreter.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -8,10 +8,33 @@
 import org.binarytranslator.generic.decoder.Interpreter;
 import org.binarytranslator.generic.os.process.ProcessSpace;
 
+/**
+ * Execution controller that implements predecoding, threaded interpretation.
+ *
+ */
 public class PredecodingThreadedInterpreter extends ExecutionController {
+  /** The controller keeps a cache of commonly used code traces. Each trace is essentially a dynamic basic block. 
+   * This HashMap maps the address of a trace's first instruction to its dynamic basic block. */
   private final HashMap<Integer, List<Interpreter.Instruction>> traceCache = new HashMap<Integer, List<Interpreter.Instruction>>();
+  
+  /** The interpreter that is used to perform the actual execution of single instructions. */
   private final Interpreter interpreter;
   
+  /** Default constructor. */
+  public PredecodingThreadedInterpreter(ProcessSpace ps) {
+    super(ps);
+    interpreter = ps.createInterpreter();
+  }
+  
+  /**
+   * Returns the dynamic basic block of instructions, starting it at address <code>pc</code>.
+   * This function also manages the trace cache ({@link #traceCache}).
+   * 
+   * @param pc
+   *  The address at which the dynamic basic block starts.
+   * @return
+   *  A list of instructions that form the dynamic basic block.
+   */
   private List<Interpreter.Instruction> getTrace(int pc) {
     List<Interpreter.Instruction> cachedTrace = traceCache.get(pc);
     
@@ -42,6 +65,14 @@
     return newTrace;
   }
   
+  /**
+   * Executes a list of instructions. It is assumed that the first instruction starts at address <code>pc</code>.
+   * 
+   * @param trace
+   *  The list of instructions that is to be executed.
+   * @param pc
+   *  The address of the first instruction.
+   */
   protected void executeTrace(List<Interpreter.Instruction> trace, int pc) {
     
     Iterator<Interpreter.Instruction> instructions = trace.iterator();
@@ -57,11 +88,6 @@
         break;
     }
   }
-  
-  public PredecodingThreadedInterpreter(ProcessSpace ps) {
-    super(ps);
-    interpreter = ps.createInterpreter();
-  }
 
   @Override
   public final void run() {

Added: src/org/binarytranslator/generic/execution/ProfilingInterpreterController.java
===================================================================
--- src/org/binarytranslator/generic/execution/ProfilingInterpreterController.java	                        (rev 0)
+++ src/org/binarytranslator/generic/execution/ProfilingInterpreterController.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -0,0 +1,36 @@
+package org.binarytranslator.generic.execution;
+
+import org.binarytranslator.generic.decoder.Interpreter;
+import org.binarytranslator.generic.os.process.ProcessSpace;
+
+public class ProfilingInterpreterController extends ExecutionController {
+
+  public ProfilingInterpreterController(ProcessSpace ps) {
+    super(ps);
+  }
+
+  @Override
+  public void run() {
+    Interpreter interpreter = ps.createInterpreter();
+    
+    int pc = ps.getCurrentInstructionAddress();
+
+    while (!ps.finished) {
+      Interpreter.Instruction instruction = interpreter.decode(pc);
+      
+      instruction.execute();
+      int nextInstruction = instruction.getSuccessor(pc);
+      
+      if (nextInstruction == -1) {
+        nextInstruction = ps.getCurrentInstructionAddress();
+        ps.branchInfo.profileBranch(pc, ps.getCurrentInstructionAddress());
+      }
+      else {
+        ps.setCurrentInstructionAddress(nextInstruction);
+      }
+      
+      pc = nextInstruction;
+    }
+  }
+
+}

Added: src/org/binarytranslator/generic/execution/StagedEmulationController.java
===================================================================
--- src/org/binarytranslator/generic/execution/StagedEmulationController.java	                        (rev 0)
+++ src/org/binarytranslator/generic/execution/StagedEmulationController.java	2007-08-02 12:22:44 UTC (rev 153)
@@ -0,0 +1,121 @@
+package org.binarytranslator.generic.execution;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+
+import org.binarytranslator.DBT;
+import org.binarytranslator.DBT_Options;
+import org.binarytranslator.generic.decoder.Interpreter;
+import org.binarytranslator.generic.os.process.ProcessSpace;
+import org.binarytranslator.vmInterface.DBT_Trace;
+import org.binarytranslator.vmInterface.DynamicCodeRunner;
+import org.jikesrvm.ArchitectureSpecific.VM_CodeArray;
+
+public class StagedEmulationController extends ExecutionController {
+
+  private final class Trace {
+    public final List<Interpreter.Instruction> instructions;
+    public int value;
+    public DBT_Trace compiledTrace;
+    
+    public Trace(List<Interpreter.Instruction> instructions) {
+      this.instructions = instructions;
+      value = 0;
+    }
+  }
+  
+  private final HashMap<Integer, Trace> traceCache = new HashMap<Integer, Trace>();
+  private final Interpreter interpreter;
+  
+  private Trace getTrace(int pc) {
+    Trace cachedTrace = traceCache.get(pc);
+    
+    if (cachedTrace != null)
+      return cachedTrace;
+    
+    int traceStart = pc;
+    ArrayList<Interpreter.Instruction> instructions = new ArrayList<Interpreter.Instruction>(5);
+    
+    while (true)  {
+      Interpreter.Instruction instruction = interpreter.decode(pc);
+      pc = instruction.getSuccessor(pc);
+      instructions.add(instruction);
+      
+      //is the successor to this instruction known?
+      if (pc == -1) {
+        //No, so stop and create a trace from the decoded instructions
+        Trace newTrace = new Trace(instructions);
+        
+        if (instructions.size() > 3) {
+          //add this trace to the trace cache, if it contains enough instructions
+          traceCache.put(traceStart, newTrace);
+        }
+        
+        return newTrace;
+      }
+    }
+  }
+  
+  private void compileTrace(Trace trace, int pc) {
+    if (DBT.VerifyAssertions) DBT._assert(trace.compiledTrace == null);
+    
+    trace.compiledTrace = new DBT_Trace(ps, pc);
+    trace.compiledTrace.compile();
+  }
+  
+  private void executeTrace(Trace trace, int pc) {
+    
+    //check if the trace is being executed very frequently... 
+    if (trace.value > 20) {
+      
+      if (DBT_Options.debugTranslation)
+        System.out.println("Switching to interpretation at address 0x" + Integer.toHexString(pc));
+      
+      //yes, so we should rather try to execute a translated version
+      if (trace.compiledTrace == null) {
+        //compile the trace, if necessary
+        compileTrace(trace, pc);
+        if (DBT.VerifyAssertions) DBT._assert(trace.compiledTrace != null);
+      }
+      
+      //execute the trace
+      VM_CodeArray code = trace.compiledTrace.getCurrentCompiledMethod().getEntryCodeArray();
+      ps.setCurrentInstructionAddress(DynamicCodeRunner.invokeCode(code, ps));
+    }
+    else {
+      trace.value += trace.instructions.size();
+    }
+    
+    Iterator<Interpreter.Instruction> instructions = trace.instructions.iterator();
+    while (true) {
+      Interpreter.Instruction instr = instructions.next();
+      instr.execute();
+      
+      if (instructions.hasNext()) {
+        pc = instr.getSuccessor(pc);
+        ps.setCurrentInstructionAddress(pc);
+      }
+      else
+        break;
+    }
+  }
+  
+  public StagedEmulationController(ProcessSpace ps) {
+    super(ps);
+    interpreter = ps.createInterpreter();
+  }
+
+  @Override
+  public void run() {
+    int pc = ps.getCurrentInstructionAddress();
+
+    while (!ps.finished) {
+      
+      Trace trace = getTrace(pc);
+      executeTrace(trace, pc);
+      pc = ps.getCurrentInstructionAddress();
+    }
+  }
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.