org.jikesrvm.compilers.opt.controlflow

Class TailRecursionElimination

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.compilers.opt.controlflow.TailRecursionElimination

public final class TailRecursionElimination
extends CompilerPhase

Transform tail recursive calls into loops.

NOTES:

• This pass does not attempt to optimize all tail calls, just those that are directly recursive.
• Even the small optimization we are doing here destroys the ability to accurately support stack frame inspection.
• This phase assumes that is run before Yieldpoints and thus does not need to insert a yieldpoint in the newly created loop header.

Field Summary

Fields

Modifier and Type	Field and Description
private BranchOptimizations	branchOpts
private static Constructor<CompilerPhase>	constructor Constructor for this compiler phase
private static boolean	DEBUG

Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

container

Constructor Summary

Constructors

Constructor and Description
TailRecursionElimination()

Method Summary

Modifier and Type	Method and Description
Constructor<CompilerPhase>	getClassConstructor() Get a constructor object for this compiler phase
String	getName()
(package private) boolean	isTailRecursion(Instruction call, IR ir) Is the argument call instruction a tail recursive call?
CompilerPhase	newExecution(IR ir) This method is called immediately before performPhase.
void	perform(IR ir) Perform tail recursion elimination.
boolean	shouldPerform(OptOptions options) This method determines if the phase should be run, based on the Options object it is passed.
(package private) Instruction	transform(Instruction call, Instruction prologue, BasicBlock target, IR ir) Transform the tail recursive call into a loop.

Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

dumpIR, dumpIR, getCompilerPhaseConstructor, getCompilerPhaseConstructor, performPhase, printingEnabled, reportAdditionalStats, setContainer, verify

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

branchOpts

private final BranchOptimizations branchOpts

constructor

private static final Constructor<CompilerPhase> constructor

Constructor for this compiler phase

Constructor Detail

TailRecursionElimination

public TailRecursionElimination()

Method Detail

getClassConstructor

public Constructor<CompilerPhase> getClassConstructor()

Get a constructor object for this compiler phase

Overrides:

getClassConstructor in class CompilerPhase

Returns:

compiler phase constructor

shouldPerform

public boolean shouldPerform(OptOptions options)

Description copied from class: CompilerPhase

This method determines if the phase should be run, based on the Options object it is passed. By default, phases are always performed. Subclasses should override this method if they only want to be performed conditionally.

Overrides:

shouldPerform in class CompilerPhase

Parameters:

options - the compiler options for the compilation

Returns:

true if the phase should be performed

getName

public String getName()

Specified by:

getName in class CompilerPhase

Returns:

a String which is the name of the phase.

newExecution

public CompilerPhase newExecution(IR ir)

Description copied from class: CompilerPhase

This method is called immediately before performPhase. Phases that do not need to create a new instance for each execution may override this method to return this, but this must be done carefully! Classes that don't override this method need to override getClassConstructor.

Overrides:

newExecution in class CompilerPhase

Parameters:

ir - the IR that is about to be passed to performPhase

Returns:

an opt compiler phase on which performPhase may be invoked.

perform

public void perform(IR ir)

Perform tail recursion elimination.

Specified by:

perform in class CompilerPhase

Parameters:

ir - the IR to optimize

isTailRecursion

boolean isTailRecursion(Instruction call,
                        IR ir)

Is the argument call instruction a tail recursive call?

Parameters:

call - the call in question

ir - the enclosing IR

Returns:

true if call is tail recursive and false if it is not.

transform

Instruction transform(Instruction call,
                      Instruction prologue,
                      BasicBlock target,
                      IR ir)

Transform the tail recursive call into a loop.

Parameters:

call - The recursive call

prologue - The IR_Prologue instruction

target - The loop head

ir - the containing IR

Returns:

the bbend instruction of the call's basic block