chord.program
Class CFGLoopFinder

java.lang.Object
  chord.program.CFGLoopFinder

public class CFGLoopFinder
extends java.lang.Object

Inference of all loops in a control-flow graph.

Author:

Mayur Naik (mhn@cs.stanford.edu)

Field Summary

static boolean

DEBUG

Constructor Summary

CFGLoopFinder()

Method Summary

java.util.Map<joeq.Compiler.Quad.BasicBlock,java.util.Set<joeq.Compiler.Quad.BasicBlock>>	getHeadToBodyMap() Provides a map from each loop header in this control-flow graph to the set of all basic blocks in that loop's body.
java.util.Map<joeq.Compiler.Quad.BasicBlock,java.util.Set<joeq.Compiler.Quad.BasicBlock>>	getHeadToExitsMap() Provides a map from each loop header in this control-flow graph to the set of all basic blocks in that loop's body that have an immediate successor outside that loop's body.
java.util.Set<joeq.Compiler.Quad.BasicBlock>	getLoopBody(joeq.Compiler.Quad.BasicBlock head) Provides the set of all basic blocks in the body of the loop specified by the given loop header.
java.util.Set<joeq.Compiler.Quad.BasicBlock>	getLoopExits(joeq.Compiler.Quad.BasicBlock head) Provides the set of all basic blocks in the body of the loop specified by the given loop header that have an immediate successor outside that loop's body.
java.util.Set<joeq.Compiler.Quad.BasicBlock>	getLoopHeads() Provides the set of all loop header basic blocks in this control-flow graph.
void	visit(joeq.Compiler.Quad.ControlFlowGraph cfg) Computes all loops in a given control-flow graph.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

public static final boolean DEBUG

See Also:

Constant Field Values

Constructor Detail

CFGLoopFinder

public CFGLoopFinder()

Method Detail

visit

public void visit(joeq.Compiler.Quad.ControlFlowGraph cfg)

Computes all loops in a given control-flow graph. It builds two maps:

• headToBody: from each loop header to the set of all basic blocks in that loop's body.
• headToExits: from each loop header to the set of all basic blocks in that loop's body that have an immediate successor outside that loop's body.

Parameters:

cfg - A control-flow graph.

getLoopHeads

public java.util.Set<joeq.Compiler.Quad.BasicBlock> getLoopHeads()

Provides the set of all loop header basic blocks in this control-flow graph.

Returns:

The set of all loop header basic blocks in this control-flow graph.

getLoopBody

public java.util.Set<joeq.Compiler.Quad.BasicBlock> getLoopBody(joeq.Compiler.Quad.BasicBlock head)

Provides the set of all basic blocks in the body of the loop specified by the given loop header.

Parameters:

head - A loop header.

Returns:

The set of all basic blocks in the body of the loop specified by the given loop header.

getLoopExits

public java.util.Set<joeq.Compiler.Quad.BasicBlock> getLoopExits(joeq.Compiler.Quad.BasicBlock head)

Provides the set of all basic blocks in the body of the loop specified by the given loop header that have an immediate successor outside that loop's body.

Parameters:

head - A loop header.

Returns:

The set of all basic blocks in the body of the loop specified by the given loop header that have an immediate successor outside that loop's body.

getHeadToExitsMap

public java.util.Map<joeq.Compiler.Quad.BasicBlock,java.util.Set<joeq.Compiler.Quad.BasicBlock>> getHeadToExitsMap()

Provides a map from each loop header in this control-flow graph to the set of all basic blocks in that loop's body that have an immediate successor outside that loop's body.

Returns:

A map from each loop header in this control-flow graph to the set of all basic blocks in that loop's body that have an immediate successor outside that loop's body.

getHeadToBodyMap

public java.util.Map<joeq.Compiler.Quad.BasicBlock,java.util.Set<joeq.Compiler.Quad.BasicBlock>> getHeadToBodyMap()

Provides a map from each loop header in this control-flow graph to the set of all basic blocks in that loop's body.

Returns:

A map from each loop header in this control-flow graph to the set of all basic blocks in that loop's body.