com.google.javascript.jscomp

Class SideEffectsAnalysis

java.lang.Object

com.google.javascript.jscomp.SideEffectsAnalysis

All Implemented Interfaces:

CompilerPass

class SideEffectsAnalysis
extends java.lang.Object
implements CompilerPass

A pass that analyzes side effects to determine when it is safe to move code from one program point to another. In its current form, SideEffectsAnalysis is very incomplete; this is mostly a sketch to prototype the interface and the broad strokes of a possible implementation based on flow-insensitive MOD and REF sets. See: Banning, John. "An efficient way to find the side effects of procedure calls and the aliases of variables." POPL '79. For an introduction to MOD and REF sets.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SideEffectsAnalysis.AbstractMotionEnvironment Represents an environment across which code might be moved, i.e.
static class	SideEffectsAnalysis.CrossModuleMotionEnvironment An environment for motion between modules.
private static class	SideEffectsAnalysis.DegenerateLocationAbstraction A very imprecise location abstraction in which there are only two abstract locations: one representing all concrete locations and one for bottom (no concrete locations).
private static interface	SideEffectsAnalysis.EffectLocation Interface representing the notion of an effect location -- an abstract location that can be modified or referenced.
static class	SideEffectsAnalysis.IntraproceduralMotionEnvironment An environment for motion within a function.
private static class	SideEffectsAnalysis.LocationAbstraction An abstract class representing a location abstraction.
(package private) static class	SideEffectsAnalysis.LocationAbstractionMode The type of location abstraction to use for this analysis.
private static class	SideEffectsAnalysis.LocationSummary
static class	SideEffectsAnalysis.RawMotionEnvironment A low-level concrete environment that allows the client to specify the environment nodes directly.
private static class	SideEffectsAnalysis.VariableUseDeclarationMap Maps NAME nodes that refer to variables to the NAME nodes that declared them.
private static class	SideEffectsAnalysis.VisibilityLocationAbstraction A location abstraction based on the visibility of concrete locations.

Field Summary

Fields

Modifier and Type	Field and Description
private AbstractCompiler	compiler
private SideEffectsAnalysis.LocationAbstraction	locationAbstraction The location abstraction used to calculate the effects of code
private SideEffectsAnalysis.LocationAbstractionMode	locationAbstractionIdentifier The kind of location abstraction to use
private static com.google.common.base.Predicate<Node>	NOT_FUNCTION_PREDICATE

Constructor Summary

Constructors

Constructor and Description
SideEffectsAnalysis(AbstractCompiler compiler)
SideEffectsAnalysis(AbstractCompiler compiler, SideEffectsAnalysis.LocationAbstractionMode locationAbstractionMode) Constructs a new SideEffectsAnalysis with the given location abstraction.

Method Summary

Modifier and Type	Method and Description
private static Node	closestControlDependentAncestor(Node node)
private SideEffectsAnalysis.LocationAbstraction	createVisibilityAbstraction(Node externs, Node root)
private static boolean	isControlDependentChild(Node child) Returns true if the number of times the child executes depends on the parent.
private static boolean	isPure(Node node) Returns true if the node is pure, that is it side effect free and does it not depend on its environment?
private static boolean	nodeHasAncestor(Node node, Node possibleAncestor) Returns true if possibleAncestor is an ancestor ofnode.
private static boolean	nodeHasCall(Node node) Returns true if a node has a CALL or a NEW descendant.
private static boolean	nodesHaveSameControlFlow(Node node1, Node node2) Returns true if the two nodes have the same control flow properties, that is, is node1 be executed every time node2 is executed and vice versa?
void	process(Node externs, Node root) Process the JS with root node root.
boolean	safeToMoveBefore(Node source, SideEffectsAnalysis.AbstractMotionEnvironment environment, Node destination) Determines whether it is safe to move code (source) across an environment to another program point (immediately preceding destination).

Methods inherited from class java.lang.Object

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

Field Detail

NOT_FUNCTION_PREDICATE

private static final com.google.common.base.Predicate<Node> NOT_FUNCTION_PREDICATE

compiler

private AbstractCompiler compiler

locationAbstraction

private SideEffectsAnalysis.LocationAbstraction locationAbstraction

The location abstraction used to calculate the effects of code

locationAbstractionIdentifier

private final SideEffectsAnalysis.LocationAbstractionMode locationAbstractionIdentifier

The kind of location abstraction to use

Constructor Detail

SideEffectsAnalysis

public SideEffectsAnalysis(AbstractCompiler compiler,
                           SideEffectsAnalysis.LocationAbstractionMode locationAbstractionMode)

Constructs a new SideEffectsAnalysis with the given location abstraction.

Parameters:

compiler - A compiler instance

locationAbstractionMode - The location abstraction to use. DEGENERATE will use SideEffectsAnalysis.DegenerateLocationAbstraction while VISIBILITY_BASED will use SideEffectsAnalysis.VisibilityLocationAbstraction

SideEffectsAnalysis

public SideEffectsAnalysis(AbstractCompiler compiler)

Method Detail

process

public void process(Node externs,
                    Node root)

Description copied from interface: CompilerPass

Process the JS with root node root. Can modify the contents of each Node tree

Specified by:

process in interface CompilerPass

Parameters:

externs - Top of external JS tree

root - Top of JS tree

createVisibilityAbstraction

private SideEffectsAnalysis.LocationAbstraction createVisibilityAbstraction(Node externs,
                                                                            Node root)

safeToMoveBefore

public boolean safeToMoveBefore(Node source,
                                SideEffectsAnalysis.AbstractMotionEnvironment environment,
                                Node destination)

Determines whether it is safe to move code (source) across an environment to another program point (immediately preceding destination).

The notion of "environment" is optimization-specific, but it should include any code that could be executed between the source program point and the destination program point. destination must not be a descendant of source.

Parameters:

source - The node that would be moved

environment - An environment representing the code across which the source will be moved.

destination - The node before which the source would be moved

Returns:

Whether it is safe to move the source to the destination

isPure

private static boolean isPure(Node node)

Returns true if the node is pure, that is it side effect free and does it not depend on its environment?

Parameters:

node - node to check.

nodesHaveSameControlFlow

private static boolean nodesHaveSameControlFlow(Node node1,
                                                Node node2)

Returns true if the two nodes have the same control flow properties, that is, is node1 be executed every time node2 is executed and vice versa?

isControlDependentChild

private static boolean isControlDependentChild(Node child)

Returns true if the number of times the child executes depends on the parent. For example, the guard of an IF is not control dependent on the IF, but its two THEN/ELSE blocks are. Also, the guard of WHILE and DO are control dependent on the parent since the number of times it executes depends on the parent.

closestControlDependentAncestor

private static Node closestControlDependentAncestor(Node node)

nodeHasAncestor

private static boolean nodeHasAncestor(Node node,
                                       Node possibleAncestor)

Returns true if possibleAncestor is an ancestor ofnode. A node is not considered to be an ancestor of itself.

nodeHasCall

private static boolean nodeHasCall(Node node)

Returns true if a node has a CALL or a NEW descendant.