Top
Contact
Blog Roll
Tags
Search

Essays
« SquirrelFish JIT code | Main | The Virtual Register Allocator »
Monday
Jan122009

The Difference Between Extended Basic Blocks and Traces

DateMonday, January 12, 2009 at 10:44PM

So far, our group at UCI has submitted two papers related to tracing JavaScript and ActionScript. Both reviews mentioned extended basic blocks (EBBs) as the same thing as traces. It's amazing how much stuff people know, and it's been helpful to me as a way to learn more. Wikipedia has an excellent article on what a basic block is. However, nothing for extended basic blocks. Upon querying the almighty Google, I found out that a strict definition difference was lacking between what a trace tree is and what an extended basic block is. Some papers even make a collection of traces synonymous with extended basic blocks ("The result is a set of traces that are extended basic blocks"). To settle it, I did some of that research thing we're supposed to do by Googling and talking to people in the lab. We got a lot of different definitions for an EBB:

  1. University of Waterloo - An extended basic block is a set of basic blocks that may be
    entered only at the first instruction.
  2. Advanced Compiler Design and Implementation - An extended basic block is a maximal sequence of instructions beginning with a leader that contains no join nodes other than the first node (which need not be a join node itself if, e.g., it is the entry node). * AKA any basic block other than a merge node in a CFG.
I can see why there may be confusion between trace trees and EBBs. To clarify, we came up with this differentiation:
  • Extended Basic Blocks - A set of basic blocks that has one entry point and multiple exit points that DO NOT include control flow graph join nodes.
  • Trace Trees - A set of basic blocks that has one entry point and multiple exit points, that CAN include control flow graph join nodes.
Depending on your definition, EBBs and Trace Trees can be the same thing from a purely compiler pointer of view. Fundamentally, both are methods that take basic blocks and compile them as one unit. With the loosest definition of an EBB, a set of basic blocks with one entry point and multiple exit points, both are theoretically the same. In practice, trace trees are usually much longer than EBBs traditionally are. If you take the stricter definition of EBBs, trace trees also include join nodes in a control flow graph.

CommentPost a Comment | |
tagged

PrintView Printer Friendly Version

EmailEmail Article to Friend

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>
Alert
Comment Moderation Enabled
Your comment will not appear until it has been cleared by a website editor.

Notify me of follow-up comments via email.