Write short notes on:

• Back patching
• Thompson’s construction
• Constant folding and copy propagation

Back patching: The problem in generating three address codes in a single pass is that we may not know the labels that control must go to at the time jump statements are generated. So to get around this problem a series of branching statements with the targets of the jumps temporarily left unspecified is generated. BackPatching is putting the address instead of labels when the proper label is determined.

Backpatching Algorithms perform three types of operations:

1. makelist(i) – creates a new list containing only i, an index into the array of quadruples and returns pointer to the list it has made.
2. merge(i,j) – concatenates the lists pointed to by i and j ,and returns a pointer to the concatenated list.
3. backpatch(p,i) – inserts i as the target label for each of the statements on the list pointed to by p.

The Translation scheme is as follows :-

• We use emit to generate code that contains place holders to be filled in later by the backpatch procedure.

• The attributes E.truelist, E.falselist are synthesized.

• When the code for E is generated, addresses of jumps corresponding to the values true and false are left unspecified and put on the lists E.truelist and E.falselist, respectively.
• A marker non-terminal M is used to capture the numerical address of a statement we want to branch to.
• nextaddr is a global variable that stores the number of the next statement to be generated. In all examples we assume that nextaddr is initialized to 100.
• makelist is a function which creates a new list from one item.
• merge is a function which creates a sorted list of addresses from two such lists.

Ex.-

E → E1 or M E2

backpatch(E1.falselist, M.quad)

E.truelist = merge(E1.truelist, E2.truelist)

E.falselist = E2.falselist

Thompson’s construction:  To construct NFA (Non-deterministic Finite Automata) from a Regular expression, we present a technique that can be used as a recognizer for tokens corresponding to a regular expression. In this technique, a regular expression is first broken into simpler sub-expressions, then the corresponding NFA are constructed and finally, these small NFAs are combined with the help of regular expression operations. This construction is known as Thompson’s construction.

The algorithm

The algorithm works recursively by splitting an expression into its constituent sub-expressions, from which the NFA will be constructed using a set of rules. More precisely, from a regular expression E, the obtained automaton A with the transition function δ respects the following properties:

• A has exactly one initial state q₀, which is not accessible from any other state. That is, for any state q and any letter a,  does not contain q₀.
•  has exactly one final state q_f, which is not co-accessible from any other state. That is, for any letter a,.
• Let c be the number of concatenation of the regular expression E and let s be the number of symbols apart from parentheses — that is, |, *, a and ε. Then, the number of states of A is 2s − c (linear in the size of E).
• The number of transitions leaving any state is at most two.
• Since an NFA of m states and at most e transitions from each state can match a string of length n in time O(emn), a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.

Rules

N(s) and N(t) is the NFA of the subexpression s and t, respectively.

1. The empty-expression ε is converted to
2. A symbol a of the input alphabet is converted to
3. The union expression s|t is converted to              State q goes via ε either to the initial state of N(s) or N(t). Their final states become intermediate states of the whole NFA and merge via two ε-transitions into the final state of the NFA.
4. The concatenation expression st is converted to          The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final state of N(t) is the final state of the whole NFA.
5. The Kleene star expression s^* is converted to        An ε-transition connects initial and final state of the NFA with the sub-NFA N(s) in between. Another ε-transition from the inner final to the inner initial state of Ns) allows for repetition of expression s according to the star operator.

• The parenthesized expression (s) is converted to N(s) itself.

Constant folding and copy propagation:

Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the nteger literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

  i = 320 * 200 * 32;

Most modern compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000). The resulting code would load the computed value and store it rather than loading and multiplying several values.

Constant folding can even use arithmetic identities. When x is an integer type, the value of 0 * x is zero even if the compiler does not know the value of x.

Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def" may be replaced with "abcdef".

Constant folding can be done in a compiler's front end on the IR tree that represents the high-level source language, before it is translated into three-address code, or in the back end, as an adjunct to constant propagation.

In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values.  A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.

From the following code:

y = x

z = 3 + y

Copy propagation would yield:

z = 3 + x

Copy propagation often makes use of reaching definitions, use-def chains and def-use chains when computing which occurrences of the target may be safely replaced. If all upwards exposed uses of the target may be safely modified, the assignment operation may be eliminated.

Copy propagation is a useful "clean up" optimization frequently used after other optimizations have already been run. Some optimizations—such as elimination of common sub expressions—require that copy propagation be run afterwards in order to achieve an increase in efficiency.