Update appNew update is available. Click here to update.
Last Updated: Jun 30, 2023
Easy

Backpatching in Compiler Design

Author Divyansh Jain
1 upvote

Introduction

Backpacking in compiler design refers to reducing the size of a compiler by removing unnecessary components, such as unused variables, functions, or code, to make it more efficient and optimized. This process is known as "compiler backpacking" or "compiler slimming".

Backpatching in Compiler Design

During the code generation phase, the compiler must conduct leaps, but the values required for these jumps may not be known in one pass, so it improvises by putting in values that will be replaced once the correct values are known, a process known as backpatching.

Also see, Code Generator

What is Backpatching?

Backpatching is a technique used in compiler design to delay the assignment of addresses to code or data structures until a later stage of the compilation process. This allows the compiler to generate code with placeholder addresses that are later updated or "backpatched" with the correct addresses once they are known. Backpatching is commonly used in compilers for languages that support complex control structures or dynamic memory allocation.

Also See, Top Down Parsing

One-Pass Code Generation Using Backpatching

Backpatching can be used to generate a boolean expressions program and the flow of control statements in a single pass. In jumping code for Boolean statements, the synthesized properties truelist and falselist of non-terminal B are utilized to handle labels.

  • B.truelist, which is a list of the jump or conditional jump instructions, should contain the label to which control should move if B is true.
  • When B is false, B.falselist is a list of instructions that will eventually result in the label to which control will be assigned. 
     

All of the jumps to true and false, as well as the label field, are left blank when the program for B is created. The lists B.truelist and B.falselist include these early leaps.

A list of jumps to the instruction immediately after the code for S is displayed by the synthesized attribute S.nextlist on a statement S, for example. It can generate instructions into an instruction array, with labels acting as indexes. Three functions are used to change the list of leaps:

  • Makelist (i): Make a new list with only i, an index into the array of instructions, then return a pointer to the newly produced list with the makelist command.
     
  • Merge (p1,p2): Returns a pointer to the concatenated list after concatenating the lists pointed to by p1 and p2.
     
  • Backpatch (p, i): For each of the instructions on the record pointed to by p, inserts i like the target label.

Boolean Expressions

It can construct a translation scheme suitable for generating code for Boolean expressions during bottom-up parsing.

In grammar, a non-terminal marker M creates a semantic action that picks up the index of the next instruction to be created at the proper time.

The steps for backpatching using boolean expressions are as follows:

  1. Production Table
  2. Finding Three address codes 
  3. Making the parse tree for the expression
     

Let’s look at an example to understand this concept clearly.

x < 100 || y > 200 && x != y

Let us first understand the expression: II stands for OR operation means either of the statements if true results the whole expression as TRUE. && stands for AND operation means both statements must be true if the expression needs to be true. 

In our expression, if x<100 is true, then there is no need to go to the next statement after the OR operation. If it is not the case, there is a need to go to the next statement. The next statement is again an expression that contains AND operation meaning both the statements must be true. If either statement fails then the whole expression will be considered false. Since in single pass where to go next is undefined as shown below:  

100: if x < 100 goto ____

101: goto ____ 

102: if y > 200 goto ____ 

103: goto ____ 

104: if x!=y goto ____ 

105: goto ____ 

106: true

107: false

Now using backpatching,

100: if x < 100 goto __106__

101: goto __102__

102: if y > 200 goto __104__

103: goto __107__

104: if x!=y goto __106__

105: goto __107__

106: true

107: false

Generating Translation Rules: 

B → B1 || MB2

{ Backpatch(B1.fl,M.instr);

B.tl = merge(B1.tl,B2.tl);

B.fl = B2.fl }

B → B1 && MB2 

{Backpatch(B1.tl,M.instr);

B.tl = B2.tl;

B.fl = merge(B1.fl,B2.fl);}

B → !B1  

{B.tl = B1.fl ;

B.fl = B1.tl;}

B → B1 

{B.tl = B1.tl;

B.fl = B1.fl;}

M→ ε{m.instr = nextinstr; }

Parse tree: 

Parse tree

Flow of Control Statement

Control statements are those that change the execution order of statements. Statements such as If, If-else, Switch-Case, and while-do are examples. In computer languages, Boolean statements are widely used to: 

  • Alter the flow of control−Conditional expressions that change the flow of control in a statement are known as Boolean expressions. The program's location implies the value of such a Boolean statement. For example, if claim S is met, the phrase E must be true.
     
  • Compute logical values− True or false values can be expressed using a Boolean expression. Three address instructions with logical operators can be used to compute such Boolean expressions in parallel to arithmetic expressions.

Labels and Gotos

Labels and Gotos are programming constructs that allow programmers to control the flow of execution in their code. A label is a named location in code that a goto statement can reference. A goto statement allows a programmer to transfer control to the labelled location in code, bypassing any statements in between. While powerful, goto statements are usually discouraged because they make code more difficult to understand and maintain. Goto statements are not supported by many computer languages, including Java and Python.

Some Competitive Questions on Backpatching

Question.1: If (a<b then t=1) else t=0.

Fill in the missing goto statements.

  1. if (a < b) goto ____
  2. t = 0 
  3. Goto ____
  4. t = 1 
  5.  

Solution:

In the above question, we need to fill the black spaces with the indexing of the lines where we have to jump in order to create a program that is mentioned in the above question. 

  1. First of all in Line-1 if (a<b) we need to jump to line no 4 in order to get (t = 1).
     
  2. Now if the condition in line no 1 is false then we will not jump and proceed further to the next line hence getting (t = 0).
     
  3. To avoid going to line no 4 we need to exit the code at the last line so now we will jump to line no 5 from line no 3 in order to avoid line no 4 and hence we have filled all the black spaces. 
     

The answer to the above question is given below:

  1. if (a < b) goto __4__
  2. t = 0 
  3. Goto __5__
  4. t = 1 
  5.  

Question.2: If (a<b) && (c<d) then t=1 else t=0.

Fill in the missing goto statements.

  1. if (a < b) goto ____
  2. t  = 0
  3. goto ____
  4. if (c < d) goto ____
  5. goto ____
  6. t = 1 
  7.  

Solution: In this question, a nested condition is given where we need to take the union of two conditions.

  1. We need to get (t = 1) when the two conditions (a<b && c<d). This is possible when we travel along line 1 to line 4 and then get the value of t at line 6 and terminate at line 7.
     
  2. When the first condition is false we need to get the value of t in line 2 and then terminate at line no 7. 
     
  3. When the second condition is false, we need to jump to line 2 to get the t = 0 and terminate the immediate goto to 7. 
     

The answer to the above question is given below:

  1. if (a < b) goto __4__
  2. t  = 0
  3. goto __7__
  4. if (c < d) goto __6__
  5. goto __2__
  6. t = 1 
  7.  

Question.3: For (i = 1; i <= n; i++){

X = a+b*c;

}

Fill In the missing goto statements.

  1. i  = 1
  2. if (i <= n) goto ____
  3. goto ____
  4. t1 = b * c 
  5. t2 = a + t1 
  6. x = t2
  7. i = i +1
  8. goto ____
  9.  

Solution: In the question above, there is a need for a loop to be created in order to perform the task under a specific condition. Hence the explanation is given below.

  1. First of all initialization of variables takes place in line no 1.
     
  2. Now every loop has a necessary condition under which the loop repeats itself hence if (i <= n) we need to update the values of t1 and t2 and this can be done by jumping to line no 4 and then we again need to check the condition hence we need to return from line 8 to line no 2 back. 
     
  3. If the condition in line no 2 is false then we need to end the loop and exit from line no 9 hence we will jump to line no 9. 
     

The answer to the above question is given below: 

  1. i  = 1
  2. if (i <= n) goto __4__
  3. goto __9__
  4. t1 = b * c 
  5. t2 = a + t1 
  6. x = t2
  7. i = i +1
  8. goto __2__
  9.  

 

Applications of Backpatching

  • It aids in the resolution of code that has been seeded with forwarding branches.
     
  • Backpatching is a technique for converting flow-of-control statements into a single pass.
     
  • During the code generation process, it is the action of filling in blank labels with undetermined data.
     
  • During bottom-up parsing, backpatching is utilized to generate quadruples for boolean expressions.

Frequently Asked Questions

What are the three functions used in Backpatching?

To generate code using backpatching, three procedures are run in two passes: makelist(), merge(), and backpatch(). 

What does backpatching entail?

Backpatching is a technique for converting flow-of-control statements into a single pass. During bottom-up parsing, backpatching is utilized to generate quadruples for boolean expressions. During the code generation process, it is the action of filling in unspecified information on labels. 

What is meant by back patching?

Back patching is a technique used in compiler design to delay the assignment of addresses to code or data structures until a later stage of the compilation process. This allows the compiler to generate code with placeholder addresses that are later updated with the correct addresses once they are known.

What are the methods of translating boolean expressions?

The two common methods of translating boolean expressions are algebraic and truth table methods. In the algebraic method, boolean expressions are manipulated using laws of boolean algebra. In the truth table method, the possible input combinations are listed and the output values are determined for each combination.

What are the three kinds of intermediate representation in compiler design?

The three kinds of intermediate representation (IR) in compiler design are high-level IR, mid-level IR, and low-level IR. High - level IR is the source code and is easy to read. Low- level IR is the optimization for efficient execution. Mid - level acts as a bridge between the High level and Low level.

Conclusion

Hope you learned something. But the knowledge never stops, we have gained knowledge of concepts of compiler design like backpatching for boolean expressions, Flow of control Statements, etc. and now we can easily do any question related to backpatching. To learn more you can visit our website for more articles. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning Ninja :) 

Previous article
Control Flow
Next article
Switch Statements