NewCompiler

Overview

This web holds work done by LukeSkorupski on the new compile. The indents on the Lisp code and Algorithm don't work out too well, if someone fixed these it would be much more readable. If you want to read the description in its native format, you can find it at Structural_Analysis.doc

It has since been extended to include the work of PatrickMoran? on the implementation of this compiler.

Description

Structural Analysis of Common Lisp Code

The input to structural analysis is a control tree for some code. The goal is to identify the control structures (while loops, if-thens, etc.) that make up a tree in order to better optimize the code. These control structures are referred to as regions. Each region is made up of one or more nodes. Each node represents a line of code or a region. As regions are identified, the nodes that make up the region are collapsed into a single abstract node that represents the region and denotes its type (e.g. while loop, if-then, etc.). After everything is collapsed, the end result is a single region. Below is a simplified example of the structural analysis process. Note that dummy nodes representing the code's entry and exit are always the first and last nodes of the control tree.

Code that makes a factorial function:

(lambda (n)

(let ((fact 1))

(loop for i from 2 to n

do (setq fact (* fact i)))

(print fact)))

Macro expansion of code (simplified):

#’(lambda (n)

(let ((fact 1))

(let ((i 2) (j292 n))

(tagbody

next-loop

(if (> i j292) (go end-loop))

(setq fact (* fact i))

(setq i (1+ i))

(go next-loop)

end-loop))

(print fact)))

Each node in the region (except for the region's entry and exit nodes) is connected only to other nodes inside the region. Regions are divided into two types: acyclic and cyclic. For our purposes, acyclic regions include blocks, if-thens, if-then-elses and proper intervals. A block is a region of code in which there is only a single edge connecting each node to the next (i.e. 2 or more consecutive statements that are not looped over or jumped into or out of). A proper region is any acyclic region that cannot be broken down into any of the other acyclic regions. Cyclic regions include self loops, while loops, natural loops, and improper regions. A while loop has an entry node that is also an exit point for the loop and another node that has the entry node as its only predecessor and successor. A natural loop is similar to a while loop except that it is schematic and may exit from any of its nodes. It is schematic because it may have any number of nodes each of which may exit the loop. An improper region contains a multiple entry cycle. If there are two different paths of entry into a cycle, there is an improper region. In addition to natural loop regions, block, proper and improper regions are also schematic. See Example 2 for examples of each type of region.

Below is an algorithm to perform structural analysis derived from Muchnick’s algorithm. It starts with the first node visited in a post-order traversal of the control tree. It looks for regions surrounding that node. First it looks for acyclic regions and then, if none are found, cyclic ones. If/when a region is found its nodes are collapsed into a single new node representing the found region's type and nodes. Then the control tree is repaired to reflect this. All edges that once came from or went to any node in this region are either no longer needed (e.g. a edge from one node to another both inside the region is typically no longer needed) and are removed, or are still relevant, but need to be updated so that they come from and/or go to the new node representing the region. After a region is identified and collapsed the algorithm continues by looking for regions surrounding it. Whenever no acyclic or cyclic region is found for a given node, the algorithm goes to the next node in the post-order traversal and looks there. The algorithm continues in this manner going up the tree in post order until it has reached the entry node of the control tree or until the entire tree has been collapsed into a single node. If it reaches the entry node without completely collapsing the tree, then the entire algorithm is re-applied to the control tree .

Algorithm for Structural Analysis

1. Number the nodes:

a. Complete a post-order traversal of the control tree numbering the nodes as they are visited.

b. Start at the bottom:

i. Let current-working-node be the lowest-numbered node.

2. Look for each type of acyclic region (block, if-then-else, if-then, and proper region):

a. Look for a block:

i. Let set-of-nodes contain current-working-node.

ii. Let current-node be current-working-node.

iii. While current-node has only one successor, next-node, and next-node has only one predecessor (current-node)

1) Add next-node to set-of-nodes.

2) Let current-node be next-node.

iv. Let current-node be current-working-node.

v. While current-node has only one predecessor, previous-node, and previous-node has only one successor (current-node)

1) Add previous-node to set-of-nodes.

2) Let current-node be previous-node.

vi. If set-of-nodes contains at least two nodes then

1) There is a block, whose nodes are in set-of-nodes.

2) Go to step 4.

b. If current-working-node has only one predecessor, previous-node, then for the rest of steps 2 and 3 let current-working-node be previous-node.

c. Look for an if-then-else:

i. If all of the below are true

a) current-working-node has exactly two successors

b) each of current-working-node's successors has current-working-node as its only predecessor

c) current-working-node's successors have only one successor which they share

2) then

a) There is an if-then-else.

b) Let set-of-nodes contain the current-working-node (the if's test) and each of current-working-node's successors (the then and else).

c) Go to step 4.

d. Look for an if-then:

i. If all of the below are true

a) Current-working-node has exactly two successors

b) One of the successors to current-working-node, then-node, has the other, exit-node, as its only successor

c) Then-node has current-working-node as its only predecessor

2) then

a) There is an if-then.

b) Let set-of-nodes contain current-working-node and then-node.

c) Go to step 4.

e. Look for a proper region:

i. If all the below are true

a) current-working-node does not have a back edge leaving it

b) current-working-node has two successors

c) there exists a node, join-node, that is the join node nearest the current-working-node

d) the nodes in the interval between (exclusive) the current-working-node and the join node have

i) no back edges coming from or going to them

ii) no edges coming to them from nodes that are not in the interval other than those that go to the current-working-node

2) then

a) There is a proper interval.

b) Let set-of-nodes contain current-working-node and all nodes between (exclusive) current-working-node and join-node.

c) Go to step 4.

f. No acyclic region was found:

i. Fall through to step 3 to look for a cyclic region.

3. Look for a cyclic region (a self loop, a while loop, a natural loop, or an improper region):

a. Let n be current-working-node.

b. Let set-of-nodes contain n and each node, m, where

i. there is a node, k, such that there is a (possible empty (i.e. m = k)) path from m to k that does pass through n

ii. and there is a back edge from k to n

c. If all of the below are true

1) set-of-nodes only contains one node (n)

2) there is an edge that comes from and goes to the node

ii. then

1) There is a self loop.

2) Go to step 4.

d. If set-of-nodes only contains one node then

i. There is no cyclic region to be found.

ii. Go to step 5.

e. If there is a node in set-of-nodes to which there is not a path from n then

i. There is an improper region.

ii. Let entry-set contain the entry nodes (all members of set-of-nodes) of the smallest multiple entry cycle of which n is one of the entries.

iii. Let common-dominator be the nearest common dominator of the nodes in entry-set.*

iv. Let set-of-nodes contain common-dominator, the nodes in entry-set and each node, i, where there is a path

1) from common-dominator to i

2) and from i to a node in entry-set that does not pass through common-dominator

v. Go to step 4.

f. If all the following are true

1) set-of-nodes contains two nodes

a) One of the nodes is n. Let the other be other-node.

2) n has two successors

3) other-node has one successor

4) n has two predecessors

5) other-node has one predecessor

ii. then

1) The nodes in set-of-nodes make up a while loop.

2) Go to step 4.

iii. else

1) The nodes in set-of-nodes make up a natural loop.

2) Go to step 4.

4. Collapse set-of-nodes into a new region node and update the control tree:

a. Let a new region node, new-node, represent the nodes in set-of-nodes and the type of the found region.

b. Let new-node be numbered the same as the highest-numbered node in set-of-nodes.

c. Set current-working-node to new-node.

d. If the region found was acyclic and there is a back edge from a node in set-of-nodes to another node in set-of-nodes, then replace it with a (back) edge going from new-node to itself.

e. For every edge, outgoing-edge, that comes from a node in set-of-nodes and goes to a node not in set-of-nodes, to-node,

i. if there is not already an edge from new-node to to-node create one

ii. remove outgoing-edge

f. Do the vice-versa: for every edge, incoming-edge, that goes from a node not in set-of-nodes, from-node, to a node in set-of-nodes

i. if there is not already an edge from from-node to new-node create one

ii. remove incoming-edge

g. If there is more than one node remaining in the control tree

i. then go to step 2 with current-working-node being new-node.

ii. else terminate: only one node remains so the algorithm is finished.

5. Bump current-working-node up the tree:

a. If there is a node in the control tree with a number (from the numbering in step 1) greater than the number of current-working-node

i. then

1) Let current-working-node be the node with the lowest number that is greater than current-working-node's number

2) Go to step 3.

ii. else go to step 1.

The search for an acyclic region begins by looking for a block surrounding the current node. If a block is not found and the current node has only one predecessor the algorithm does all of its future looking from the predecessor (i.e. current node, from here on, refers to the predecessor). If a block was not found then the algorithm looks for an if-then-else and if that is not found an if-then. If an if-then is not found, it needs to determine if there is a proper interval whose entry node/point is the current node. The algorithm goes up the tree in post-order and it has already looked for a surrounding region of every other acyclic type, so if there is an acyclic interval that begins at the current node then as long as there are no edges coming into the interval from outside the interval, it must be a proper interval. Note that it being an acyclic interval implies that there are no edges going out from any node (other than the exit node) inside the interval to any node outside the interval. So to identify a proper region the algorithm needs to find the join/exit node/point of the proper interval from the current node, verify that the interval is acyclic and verify that the interval has no edges coming from a node outside the region to a node (other than the current node) inside the region. The join node is the node nearest to the current node through which every path from the current node must pass on its way to the control tree's exit node. If the nodes between (inclusive) the current node and the join node have no back edges coming to or going from them (with the exception that a back edge coming from the join-node or a node outside the interval and going to the current node is allowed in order for an inner proper region to be identified and collapsed before an outer cyclic region is), then the region is acyclic. A back edge is an edge that goes from a node, a, to a node, b, where b is equally (in the case of a self loop) or higher-numbered (according to the post-order traversal) than a and there exists a path from b to a that does not use a back edge.

If no acyclic regions were found, the search continues with cyclic regions. If the current node has a back edge coming to it, then it is part of a cyclic interval. The algorithm identifies a self loop, improper, while loop or natural loop region in that order. The algorithm first identifies the relevant nodes of a possible cycle. The relevant nodes include the current node, n, and any node, m, from which where there is a path that does not pass through n to a node, k, from which there is a back edge to n. For intervals that are not improper the relevant nodes are those that form the cycle. For improper intervals the relevant node set will also contain all nodes from which there are paths to enter the cycle without going through n. From the set of nodes a self loop can easily be identified by checking for a single node that has an edge going to itself. If a self loop was not identified and there is only one node in the set of nodes, then there is no cyclic (or acyclic) region to be identified and the algorithm continues with the next node in the post-order traversal and looks for surrounding regions from there. Otherwise the algorithm checks for an improper interval next. An improper interval is one that has multiple entries into a cycle. For improper intervals there is always at least one node from which there is a path into the cycle that does not pass through n. This is essentially the same as saying that if, and only if, there is a non-descendant of n in the set of nodes then there is an improper region.

Once it is determined that there is an improper interval, the algorithm needs to identify the nodes that will make up the region. Note that this differs from the set of nodes used to determine that the improper region existed. For other types of cyclic structures the set of nodes identified earlier was also the set of nodes that would make up the new region node. However, this set of nodes may include nodes that don't need to be included in the improper region. Also note that since the new region to be created for the improper interval can only have one entry (as is true for all regions), it must include more than just the nodes of the cycle. In order to ensure that the region node will have only one entry, the algorithm must find a node that dominates the cycle's entry nodes. It is said that one node y dominates a node x when all paths from entry to x pass through y. The cycle's entry nodes, referred to as the entry set, include all the cycle's nodes that provide entry (i.e. have a node coming to them from outside the cycle) to the cycle. If the algorithm can find a dominator in common to the nodes in entry set and make it the entry node for the region, then we can be sure that there is only one entry into the new region node. We want this dominator to be as low in the tree as possible so that we don't unnecessarily include nodes in the region. Thus the algorithm needs to find the nearest common dominator of the nodes in the entry set. Once found the nodes which need to be in the region can be determined. These nodes include the dominator, the entry set and each node, i, where there is a path from the common dominator to i and a path from i to a node in entry set that does pass through the common dominator. These are the nodes that need to be collapsed into a new region node.

If the algorithm didn't find an improper interval, then it needs to look for a while loop next. By this point, a while loop will always have exactly two nodes. Any consecutive nodes inside the while loop will have already been collapsed into a single block node. So if there is a while loop, then there are only be two nodes in the set of nodes identified earlier. If a while loop is identified, the nodes in set of nodes need to be collapsed into a new region node for the while loop. If no while loop is identified then the cyclic region must be a natural loop. The nodes in set of nodes need to be collapsed into a new region node for the natural loop.

Note that there are special cases for a do loop. The algorithm identifies the nodes in a do loop as part of a block. Because of this there is a special case when collapsing regions where the algorithm needs to look for a back edge going from a node in the region to another node in the region and preserve the edge by creating an edge that goes from and to the new block region node. After collapsing the block's nodes, the result is a block node with a self loop. So although do-while loops fit the schema for a natural while loop, the algorithm ends up identifying them as a block region inside a self loop region.

Other Notes

The goal of this guide is to give an overview of structural analysis, as it applies to CLForJava? . For a more in-depth approach to structural analysis see the structural analysis section in Steven S. Muchnick's Advanced Compiler Design & Implementation from which this was derived.

*Muchnick says that the nearest common dominator "can easily be computed from the flowgraph's dominator tree." So we may need to create a dominator tree in order to find the nearest common dominator.

. However an example of Lisp code that will generate such a control tree has yet to be found. So one pass may always suffice, but if we ever come up with a case where this is not true, there may need to be at least one modification to the algorithm: when finding a proper interval we might need to also verify that the interval does not contain any of the other acyclic region types. These regions may not have been identified for the same reason that more than one pass is required.

Diagrams

I don't know what these mean, but these were under the depot/CLforJava/Papers/Structural Analysis/ section of perforce, which is where I was pointed to after talking to Professor Boetje about the architecture of the new compiler.

24 Node

42 Node

Block

Factorial

References

HyperSpec	CLtL
link 1	Link 2

Implementation

Details of implementation

Core Java Classes	Javadoc Links

Discussions

Links to Blog issues

Current Status of NewCompiler

Status:

Release Level:

Open bug count:

Test Suites

Links to JUnit results