org.jruby.ir.representations

Class CFG

java.lang.Object

org.jruby.ir.representations.CFG

public class CFG
extends java.lang.Object

Represents the base build of a CFG. All information here is accessed via delegation from the CFG itself so this is meant as an internal organizational structure for a build.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CFG.EdgeType

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.Map<Label,BasicBlock>	bbMap
private java.util.Map<BasicBlock,BasicBlock>	ensurerMap
private BasicBlock	entryBB Entry BB
private BasicBlock	exitBB Exit BB
private BasicBlock	globalEnsureBB BB that traps all exception-edges out of the cfg where we could add any cleanup/ensure code (ex: pop frames, etc.)
private DirectedGraph<BasicBlock>	graph The graph itself
private static Logger	LOG
private int	nextBBId
private java.util.List<ExceptionRegion>	outermostERs
(package private) java.util.LinkedList<BasicBlock>	postOrderList
private java.util.Map<BasicBlock,BasicBlock>	rescuerMap
private IRScope	scope

Constructor Summary

Constructors

Constructor and Description
CFG(IRScope scope)

Method Summary

Modifier and Type	Method and Description
void	addBasicBlock(BasicBlock bb)
void	addEdge(BasicBlock source, BasicBlock destination, java.lang.Object type)
private void	addEdge(BasicBlock src, Label targetLabel, java.util.Map<Label,java.util.List<BasicBlock>> forwardRefs)
void	addGlobalEnsureBB(BasicBlock geb)
boolean	bbIsProtected(BasicBlock b)
DirectedGraph<BasicBlock>	build(java.util.List<Instr> instrs) Build the Control Flow Graph
private BasicBlock	buildExitBasicBlock(java.util.Stack<ExceptionRegion> nestedExceptionRegions, BasicBlock firstBB, java.util.List<BasicBlock> returnBBs, java.util.List<BasicBlock> exceptionBBs, boolean nextIsFallThrough, BasicBlock currBB, BasicBlock entryBB) Create special empty exit BasicBlock that all BasicBlocks will eventually flow into.
private java.util.LinkedList<BasicBlock>	buildPostOrderList()
CFG	cloneForCloningClosure(IRScope scope, InlinerInfo ii)
void	collapseStraightLineBBs()
private BasicBlock	createBB(Label label, java.util.Stack<ExceptionRegion> nestedExceptionRegions)
private BasicBlock	createBB(java.util.Stack<ExceptionRegion> nestedExceptionRegions)
private void	deleteOrphanedBlocks(DirectedGraph<BasicBlock> graph)
java.util.Collection<BasicBlock>	getBasicBlocks()
BasicBlock	getBBForLabel(Label label)
BasicBlock	getEnsurerBBFor(BasicBlock block)
BasicBlock	getEntryBB()
BasicBlock	getExitBB()
BasicBlock	getGlobalEnsureBB()
Edge<BasicBlock>	getIncomingEdgeOfType(BasicBlock block, java.lang.Object type)
java.lang.Iterable<Edge<BasicBlock>>	getIncomingEdges(BasicBlock block)
BasicBlock	getIncomingSource(BasicBlock block)
BasicBlock	getIncomingSourceOfType(BasicBlock block, java.lang.Object type)
java.lang.Iterable<BasicBlock>	getIncomingSources(BasicBlock block)
int	getMaxNodeID()
int	getNextBBID()
java.util.List<ExceptionRegion>	getOutermostExceptionRegions()
BasicBlock	getOutgoingDestination(BasicBlock block)
BasicBlock	getOutgoingDestinationOfType(BasicBlock block, java.lang.Object type)
java.lang.Iterable<BasicBlock>	getOutgoingDestinations(BasicBlock block)
java.lang.Iterable<BasicBlock>	getOutgoingDestinationsNotOfType(BasicBlock block, java.lang.Object type)
java.lang.Iterable<BasicBlock>	getOutgoingDestinationsOfType(BasicBlock block, java.lang.Object type)
Edge<BasicBlock>	getOutgoingEdgeOfType(BasicBlock block, java.lang.Object type)
java.util.Set<Edge<BasicBlock>>	getOutgoingEdges(BasicBlock block)
java.lang.Iterable<Edge<BasicBlock>>	getOutgoingEdgesNotOfType(BasicBlock block, java.lang.Object type)
java.util.ListIterator<BasicBlock>	getPostOrderTraverser()
BasicBlock	getRescuerBBFor(BasicBlock block)
java.util.ListIterator<BasicBlock>	getReversePostOrderTraverser()
IRScope	getScope()
java.util.Collection<BasicBlock>	getSortedBasicBlocks()
int	inDegree(BasicBlock b)
private boolean	mergeBBs(BasicBlock a, BasicBlock b)
private void	optimize()
int	outDegree(BasicBlock b)
java.util.LinkedList<BasicBlock>	postOrderList()
private void	printError(java.lang.String message)
void	removeAllOutgoingEdgesForBB(BasicBlock b)
void	removeBB(BasicBlock b)
void	removeEdge(BasicBlock a, BasicBlock b)
void	removeEdge(Edge edge)
void	resetState()
void	setEnsurerBB(BasicBlock block, BasicBlock ensureBlock)
void	setRescuerBB(BasicBlock block, BasicBlock rescuerBlock)
int	size()
java.lang.String	toStringGraph()
java.lang.String	toStringInstrs()

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final Logger LOG

scope

private IRScope scope

bbMap

private java.util.Map<Label,BasicBlock> bbMap

rescuerMap

private java.util.Map<BasicBlock,BasicBlock> rescuerMap

ensurerMap

private java.util.Map<BasicBlock,BasicBlock> ensurerMap

outermostERs

private java.util.List<ExceptionRegion> outermostERs

entryBB

private BasicBlock entryBB

Entry BB

exitBB

private BasicBlock exitBB

Exit BB

globalEnsureBB

private BasicBlock globalEnsureBB

BB that traps all exception-edges out of the cfg where we could add any cleanup/ensure code (ex: pop frames, etc.)

graph

private DirectedGraph<BasicBlock> graph

The graph itself

nextBBId

private int nextBBId

postOrderList

java.util.LinkedList<BasicBlock> postOrderList

Constructor Detail

CFG

public CFG(IRScope scope)

Method Detail

getNextBBID

public int getNextBBID()

getMaxNodeID

public int getMaxNodeID()

bbIsProtected

public boolean bbIsProtected(BasicBlock b)

getBBForLabel

public BasicBlock getBBForLabel(Label label)

getEnsurerBBFor

public BasicBlock getEnsurerBBFor(BasicBlock block)

getEntryBB

public BasicBlock getEntryBB()

getExitBB

public BasicBlock getExitBB()

getGlobalEnsureBB

public BasicBlock getGlobalEnsureBB()

getOutermostExceptionRegions

public java.util.List<ExceptionRegion> getOutermostExceptionRegions()

postOrderList

public java.util.LinkedList<BasicBlock> postOrderList()

getPostOrderTraverser

public java.util.ListIterator<BasicBlock> getPostOrderTraverser()

getReversePostOrderTraverser

public java.util.ListIterator<BasicBlock> getReversePostOrderTraverser()

resetState

public void resetState()

getScope

public IRScope getScope()

size

public int size()

getBasicBlocks

public java.util.Collection<BasicBlock> getBasicBlocks()

getSortedBasicBlocks

public java.util.Collection<BasicBlock> getSortedBasicBlocks()

addEdge

public void addEdge(BasicBlock source,
                    BasicBlock destination,
                    java.lang.Object type)

inDegree

public int inDegree(BasicBlock b)

outDegree

public int outDegree(BasicBlock b)

getIncomingSources

public java.lang.Iterable<BasicBlock> getIncomingSources(BasicBlock block)

getIncomingEdges

public java.lang.Iterable<Edge<BasicBlock>> getIncomingEdges(BasicBlock block)

getIncomingSource

public BasicBlock getIncomingSource(BasicBlock block)

getIncomingSourceOfType

public BasicBlock getIncomingSourceOfType(BasicBlock block,
                                          java.lang.Object type)

getIncomingEdgeOfType

public Edge<BasicBlock> getIncomingEdgeOfType(BasicBlock block,
                                              java.lang.Object type)

getOutgoingEdgeOfType

public Edge<BasicBlock> getOutgoingEdgeOfType(BasicBlock block,
                                              java.lang.Object type)

getOutgoingDestination

public BasicBlock getOutgoingDestination(BasicBlock block)

getOutgoingDestinationOfType

public BasicBlock getOutgoingDestinationOfType(BasicBlock block,
                                               java.lang.Object type)

getOutgoingDestinations

public java.lang.Iterable<BasicBlock> getOutgoingDestinations(BasicBlock block)

getOutgoingDestinationsOfType

public java.lang.Iterable<BasicBlock> getOutgoingDestinationsOfType(BasicBlock block,
                                                                    java.lang.Object type)

getOutgoingDestinationsNotOfType

public java.lang.Iterable<BasicBlock> getOutgoingDestinationsNotOfType(BasicBlock block,
                                                                       java.lang.Object type)

getOutgoingEdges

public java.util.Set<Edge<BasicBlock>> getOutgoingEdges(BasicBlock block)

getOutgoingEdgesNotOfType

public java.lang.Iterable<Edge<BasicBlock>> getOutgoingEdgesNotOfType(BasicBlock block,
                                                                      java.lang.Object type)

getRescuerBBFor

public BasicBlock getRescuerBBFor(BasicBlock block)

addGlobalEnsureBB

public void addGlobalEnsureBB(BasicBlock geb)

setEnsurerBB

public void setEnsurerBB(BasicBlock block,
                         BasicBlock ensureBlock)

setRescuerBB

public void setRescuerBB(BasicBlock block,
                         BasicBlock rescuerBlock)

build

public DirectedGraph<BasicBlock> build(java.util.List<Instr> instrs)

Build the Control Flow Graph

addEdge

private void addEdge(BasicBlock src,
                     Label targetLabel,
                     java.util.Map<Label,java.util.List<BasicBlock>> forwardRefs)

buildExitBasicBlock

private BasicBlock buildExitBasicBlock(java.util.Stack<ExceptionRegion> nestedExceptionRegions,
                                       BasicBlock firstBB,
                                       java.util.List<BasicBlock> returnBBs,
                                       java.util.List<BasicBlock> exceptionBBs,
                                       boolean nextIsFallThrough,
                                       BasicBlock currBB,
                                       BasicBlock entryBB)

Create special empty exit BasicBlock that all BasicBlocks will eventually flow into. All Edges to this 'dummy' BasicBlock will get marked with an edge type of EXIT. Special BasicBlocks worth noting: 1. Exceptions, Returns, Entry(why?) -> ExitBB 2. Returns -> ExitBB

createBB

private BasicBlock createBB(Label label,
                            java.util.Stack<ExceptionRegion> nestedExceptionRegions)

createBB

private BasicBlock createBB(java.util.Stack<ExceptionRegion> nestedExceptionRegions)

addBasicBlock

public void addBasicBlock(BasicBlock bb)

removeEdge

public void removeEdge(Edge edge)

removeAllOutgoingEdgesForBB

public void removeAllOutgoingEdgesForBB(BasicBlock b)

deleteOrphanedBlocks

private void deleteOrphanedBlocks(DirectedGraph<BasicBlock> graph)

mergeBBs

private boolean mergeBBs(BasicBlock a,
                         BasicBlock b)

removeBB

public void removeBB(BasicBlock b)

collapseStraightLineBBs

public void collapseStraightLineBBs()

optimize

private void optimize()

toStringGraph

public java.lang.String toStringGraph()

toStringInstrs

public java.lang.String toStringInstrs()

removeEdge

public void removeEdge(BasicBlock a,
                       BasicBlock b)

buildPostOrderList

private java.util.LinkedList<BasicBlock> buildPostOrderList()

cloneForCloningClosure

public CFG cloneForCloningClosure(IRScope scope,
                                  InlinerInfo ii)

printError

private void printError(java.lang.String message)