Package org.jruby.ir.representations

Class CFGLinearizer

java.lang.Object

org.jruby.ir.representations.CFGLinearizer

public class CFGLinearizer
extends Object

This produces a linear list of BasicBlocks so that the linearized instruction list is in executable form. In generating this list, we will also add jumps where required and remove as many jumps as possible. Ordinary BasicBlocks will follow FollowThrough edges and just concatenate together eliminating the need for executing a jump instruction during execution. Notes: 1. Basic blocks ending in branches have two edges (FollowTrough/NotTaken and Taken) 2. All BasicBlocks can possibly have two additional edges related to exceptions: - one that transfers control to a rescue block (if one exists that protects the excepting instruction) which is also responsible for running ensures - one that transfers control to an ensure block (if one exists) for situations where we bypass the rescue block (breaks and thread-kill). 3. Branch, Jump, Return, and Exceptions are all boundaries for BasicBlocks 4. Dummy Entry and Exit BasicBlocks exist in all CFGs NOTE: When the IR builder first builds its list, and the CFG builder builds the CFG, the order in which BBs are created should already be a linearized list. Need to verify this and we might be able to skip linearization if the CFG has not been transformed by any code transformation passes. This might be the case when JRuby first starts up when we may just build the IR and start interpreting it right away without running any opts. In that scenario, it may be worth it to not run the linearizer at all.

Constructor Summary

Constructors

Constructor	Description
CFGLinearizer()

Method Summary

Modifier and Type	Method	Description
private static void	addJumpIfNextNotDestination(CFG cfg, BasicBlock next, Instr lastInstr, BasicBlock current)
private static void	fixupList(CFG cfg, BasicBlock[] list, int listSize)	Process (fixup) list of instruction and add or remove jumps.
static BasicBlock[]	linearize(CFG cfg)
private static int	linearizeInner(CFG cfg, BasicBlock[] list, int listSize, BitSet processed, BasicBlock current)
private static void	tryAndRemoveUnneededJump(BasicBlock next, CFG cfg, Instr lastInstr, BasicBlock current)
private static void	verifyAllBasicBlocksProcessed(CFG cfg, BitSet processed)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

CFGLinearizer

public CFGLinearizer()

Method Details

linearize

public static BasicBlock[] linearize(CFG cfg)

linearizeInner

private static int linearizeInner(CFG cfg,
 BasicBlock[] list,
 int listSize,
 BitSet processed,
 BasicBlock current)

fixupList

private static void fixupList(CFG cfg,
 BasicBlock[] list,
 int listSize)

Process (fixup) list of instruction and add or remove jumps.

tryAndRemoveUnneededJump

private static void tryAndRemoveUnneededJump(BasicBlock next,
 CFG cfg,
 Instr lastInstr,
 BasicBlock current)

addJumpIfNextNotDestination

private static void addJumpIfNextNotDestination(CFG cfg,
 BasicBlock next,
 Instr lastInstr,
 BasicBlock current)

verifyAllBasicBlocksProcessed

private static void verifyAllBasicBlocksProcessed(CFG cfg,
 BitSet processed)
                                           throws RuntimeException

Throws:

RuntimeException