Table of contents
1.
Introduction
2.
Questions
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024
Easy

Code generation and optimization

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

We say that code optimization is writing code, so a program uses the least possible memory disk space, minimizes its CPU time or network bandwidth, or makes the best use of additional cores.

Code generation is when a compiler's code generator converts the intermediate representation of source code into a form (e.g., machine code) that a machine can readily execute.

Questions

1. Consider the code segment

int i, j, x, y, m, n;
n=20;
 for (i = 0, i < n; i++)
  {
    for (j = 0; j < n; j++)
    {
        if (i % 2)
        {
        x + = ((4*j) + 5*i);
        y += (7 + 4*j);
        }
    }
  }
  m = x + y;
You can also try this code with Online C++ Compiler
Run Code

 

Which one of the following is false?

  1. The code contains invariant loop computation
  2. In this code, there is a scope of common sub-expression elimination.
  3. There is a scope of strength reduction in this code.
  4. There is a scope of dead code elimination in this code.

Solution: d. There is a scope of dead code elimination in this code.

Option d is false because, in the process of elimination technique, it removes dead code as suggested by the name. Code statements are called dead code where the code is never used or accessed, or the output is never used is deleted, but no such kind of statements or code. Here we reduce the strength by switching "4 * j by 4 << j," and the code has common sub-expression and loop invariant computations.

 

2. Peephole optimization is a form of-

  1. Loop optimization
  2. Local optimization
  3. Constant folding
  4. Data flow analysis

Solution: b. Local optimization

In the optimization technique, we optimize the code during compilation, reducing space and time complexity and eliminating redundant code. Peephole optimization is one of the techniques performed on a small set of compiler-generated instructions, and the small set is known as the peephole or window. Peephole optimization does change the small set of instructions to the equivalent set with better performance.

 

3. Which of the option is NOT represented in a subroutine's activation record frame for a stack-based programming language?

  1. Values of local variables
  2. Return address
  3. Heap area
  4. Information is needed to access non-local variables.

Solution: c. Heap area

Activation record is another name for Stack Frame. It's a data structure that composes a call stack. It is composed of:- Locals to the callee Return address to the caller Parameters of the callee Heap area are required for dynamic variables. So, option (C) is correct.

 

4. In compiler terminology, reduction in strength means

  1. Replacing runtime computation with compile-time computation
  2. Removing invariant loop computation
  3. Removing common subexpressions
  4. Replacing a costly operation with a relatively cheaper one

Solution: d. Replacing a costly operation with a relatively cheaper one

Strength Reduction is a compiler optimization in which cheaper ones replace costly operations. Example:- Exponentiation is replaced by multiplication, and multiplication is replaced by addition. 

 

5. Which of the following option about peephole optimization is not True?

  1. It is applied to only a small part of code.
  2. It is used to optimize intermediate code.
  3. It has to be applied repeatedly to get the best out of this.
  4. It can be applied to a not contiguous portion of the code.

Solution: d. It can be applied to a not contiguous portion of the code.

Peephole optimization is a kind of optimization technique in which it is applied to a small portion of code called a 'peep or window,' The peep optimization technique is used to improve code in moderate coding and to get the best of the whole process, should be used repeatedly but cannot be used in part of the code which is not a combined method. So option (D) is false.
 

6. The use of multiple register windows with overlap causes a reduction in the number of memory accesses for 

I. Function locals and parameters 

II. Register saves and restores 

III. Instruction fetches

  1. I only
  2. II only
  3. III only
  4. I, II, and III

Solution: a. I only

I. is true because using multiple register windows, we eliminate the need to access the variable values again and again from memory. Rather, we store them in the registers.

II. is false because register saves and restores would still be required for each and every variable.

III. is also false because instruction fetch is not affected by memory access using multiple register windows.

So, only I. is true.

 

7. Substitution of values for names is done in

  1. Local optimization
  2. Loop optimization
  3. Constant folding
  4. Strength reduction

Solution: c. Constant folding.

Constant folding recognizes and evaluates constant expressions at compile time rather than computing them at runtime.

 

8. Relative to the program translated by a compiler, the same program, when interpreted, runs

  1. At the Faster
  2. At the Slower
  3. Same speed
  4. It may be faster or slower.

Solution: At the slower,

An interpreter translates the program process one statement at a time. It scans the whole program and translates it as a whole into machine code. It takes less time to analyze the source code, but the execution time is very slow. The compiler can scan the entire program and translates it into machine code. It required a large amount of time to analyze the source code, but the overall execution time was comparatively faster. So, option (B) is correct.

 

9. In a resident – OS computer, which of the following systems must reside in the main memory under all situations?

  1. Assembler
  2. Linker
  3. Loader
  4. Compiler

Solution: c. Loader

The loader is part of the operating system responsible for loading programs and libraries. It is one of the most important stages in the process, as it puts the programs in memory and prepares them for implementation. Downloading the program involves tasks such as reading the contents of a usable file containing program instructions in memory and performing other tasks that are necessary to prepare the usable application. The operating system starts the program by transferring control to the downloaded program code once the download process is complete. Option (C) is correct.

 

10. Which of the following statements usually produces no executable code when compiled?

  1. declaration
  2. assignment statements
  3. input and output statements
  4. structural statement

Solution: a. declaration

Declaration usually produces no executable code when compiled.

 

11. Which option are comparisons between static and dynamic type checking not correct?

  1. Dynamic type checking can slow down the execution.
  2. Dynamic type checking provides more flexibility to the programmers.
  3. In comparison to Static type checking, dynamic type checking may cause failure while runtime due to type errors.
  4. Unlike static type checking, dynamic type checking is done during compilation.

Solution: a. Dynamic type checking can slow down the execution.

A language is statically-typed if the variable type is known at compile time instead of runtime. Common examples of statically-typed languages include Ada, C, C++, C#, JADE, Java, Fortran, Haskell, ML, Pascal, and Scala. Common dynamically-typed languages include Groovy, JavaScript, Lisp, Lua, Objective-C, PHP, Prolog, Python, Ruby, Smalltalk, and Tcl. So, dynamic type checking offers more flexibility to the programmers at the expense of runtime type checking overhead and possible runtime type errors.

 

12. Which of the option comment about peephole optimization is correct?

  1. It can apply to a small part of the code and use repeatedly.
  2. It is used to optimize intermediate code.
  3. It is applied to a portion of the code that is not contiguous.
  4. It is applied in the symbol table to optimize the memory requirements.

Solution: a. It can apply to a small part of the code and use repeatedly.

Peephole optimization is a technique applied to a small part of the code called 'peep.' Peephole optimization involves changing a small set of instructions to an equivalent set that gives better performance than other optimization techniques and applies repeatedly. Hence option (A) is correct.

 

13. Because of this, several code optimizations are performed on the intermediate code:-

  1. They improve the compiler's portability to other target CPUs.
  2. On intermediate code, B program analysis is more accurate than machine code.
  3. Dataflow analysis information cannot be used for optimization in any other way.
  4.  Front-end information cannot be used for optimization in any other way.

Solution: a. They improve the compiler's portability to other target CPUs.

Option (B) is correct as well. However, the primary goal of conducting some code optimization on intermediate code generation is to improve the compiler's portability to target processors. As a result, Option A) is more appropriate in this case. Intermediate code is code that is not dependent on the machine or architecture. As a result, a compiler can optimize it without caring about the architecture on which the code will run (it may be the same or the other ). As a result, that type of compiler can be used by various architectures. In contrast, if code optimization is performed on the machine/architecture-dependent target code, the compiler must be precise about the optimizations performed on that type of code. Because the target code is not portable, the compiler cannot be utilized by many architectures in this instance.

 

14. Which of the following statements is FALSE?

  1. A basic block is an instruction sequence in which control enters at the beginning and exits at the conclusion.
  2. For common subexpression removal, available expression analysis might be employed.
  3. For dead code elimination, live variable analysis can be employed.
  4. A frequent subexpression elimination example is x = 4 ∗ 5 => x = 20.

Solution: d. A frequent subexpression elimination example is x = 4 ∗ 5 => x = 20.

(A) A basic block is a TRUE sequence of instructions in which control enters at the start and exits at the end. 

(B) Available expression analysis can indeed be used to eliminate common subexpressions. Available expression is an analytical algorithm that determines the set of expressions that do not need to be recomputed at each place in the program. Available expression analysis is used to eliminate common global subexpressions (CSE). There's no need to re-evaluate an expression if it's already available. 

(C)Live variable analysis can be utilized to eliminate dead code. 

(D) x = 4*5 => x = 20 is a frequent subexpression elimination example that is FALSE.

 

15. One of the goals of using intermediate code in compilers is to improve performance.

  1. By simplifying parsing and semantic analysis.
  2. By enhances error recovery & reporting.
  3. Enhance the likelihood of the machine-independent code optimizer being reused in other compilers
  4. By making the register allocation better.

Solution: c. Enhance the likelihood of the machine-independent code optimizer being reused in other compilers

Following semantic analysis, the code is converted into intermediate code that is platform (OS + hardware) independent. The benefit of converting into intermediate code is that it improves code generation performance and increases the chances of reusing the machine-independent code optimizer in other compilers. 

 

16. Consider the arithmetic expressions grammar rule E → E1 → E2. The resulting code is intended for a CPU with a single user register. The first operand must be in the register for the subtraction operation to work. If E1 and E2 don't have any subexpressions in common, in order to get the shortest code possible, 

  1. The evaluation of E1 should come first.
  2. The evaluation of E2 should come first.
  3. E1 and E2 evaluations must always be done together.
  4. The order in which E1 and E2 are evaluated makes no difference.

Solution: b. The evaluation of E2 should come first.

E -> E1 - E2  Given that E1 and E2 do not share any subexpressions, the most efficient use of a single user register for evaluating this production rule would be when E2 is evaluated first. This is because, by the time E1 is evaluated in the register, E2 has already been computed and placed elsewhere in memory. As a result, we may simply utilize the subtraction operation to get the value of the user register as the first operand, i.e., E1 and E2, from its memory address referenced using some index register or some other form as specified in the instruction.

 

17. Understand the code given below:-

i = 1
j = 1
t1 = 5 * i
t2 = t1 + j
t3 = 4 * t2
t4 = t3
a[t4] = -1
j = j + 1
 if j <= 5 goto(3)
i = i + 1
 if i < 5 goto(2) 
You can also try this code with Online C++ Compiler
Run Code

 

The control-flow-graph created for the above code has the following number of nodes and edges:

  1. 5 and 7
  2. 6 and 7
  3. 5 and 5
  4. 7 and 8

Solution: c. 6 and 7

Control flow graph of above code.  

 

18. Understand the code given below:-

x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y; 
You can also try this code with Online C++ Compiler
Run Code

To convert the above code segment to a static single assignment form, the minimum number of total variables necessary is. Note that this was a Numerical Answer Type question.

  1. 6
  2. 8
  3. 9
  4. 10

Solution: d. 10

In compiler design, Static Single Assignment is used for intermediate code. Each assignment to a variable in the Static Single Assignment form (SSA) should have its own name. To separate each definition of a variable, we utilize subscripts.

 

19. For a non-terminal, a grammar that is both left and right recursive is

  1. Ambiguous
  2. Unambiguous
  3. Information is not sufficient to decide whether it is ambiguous or Unambiguous.
  4. None of the above

Solution: c. Information is not sufficient to decide whether it is ambiguous or Unambiguous.

Consider the following grammar: S →  n, B →  BbB. We can see that grammar is both left and right recursive, but it is still unambiguous grammar because A is a pointless production but still belongs to grammar. As a result, we may claim that grammar with both left and right recursion is either ambiguous or not. Let's take another example: if we have a grammar like AAA, we won't be able to construct any infinite string steps because the grammar's language is the empty set. As a result, we can conclude that if a language has both left and right recursion, it is either ambiguous or not. The correct answer is (C).

 

20. A linker reads four modules, each of which is 200, 800, 600, and 500 words long. What are the relocation constants if they're loaded in that order?

  1. 0, 200, 500, 600
  2. 0, 200, 1000, 1600
  3. 200, 500, 600, 800
  4. 200, 700, 1300, 2100

Solution: b. 0, 200, 1000, 1600

A linker, according to the question, reads four modules with lengths of 200, 800, 600, and 500 words. If the first module is loaded, it will begin at address 0, and the Size will be 200. As a result, it will occupy the first 200 addresses and the last 199 addresses because it starts with 0. As a result, the second module will be present from 200 to 999 as it has a length of 800, and the third module will be present from 1000 to 1599 as it has a length of 600. Similarly, the fourth module will begin at 1600 and end at 500 B. As a result, the relocation constants are 0, 200, 1000, and 1600.

Related Article Intermediate Code Generation in Compiler Design.

FAQs

1. How is the quality of the object program measured?

The quality of an object program is measured by its Size or its running time. Large computations running time is important. For small computations, Size may be as important or even more.

 

2. What are the three areas of code optimization?

  • Local optimization
     
  • Loop optimization
     
  • Data flow analysis
     

3. What are the properties of optimizing compilers?

  • Transformation must preserve the meaning of programs.
     
  • Transformation must, on average, speed up the programs by a measurable amount.
     
  • A Transformation must be worth the effort.
     

4. ​​What does "peephole optimization" imply?

  • Peephole optimization is a technique employed by numerous compilers to improve the performance of their code.
     
  • Optimization of intermediate or object code is possible. It's actually an attempt to get around the challenges of syntax-directed code creation.

Key takeaways

In this article, we have gone through critical previous years' GATE exam questions. Optimization is a technique for transformation programs, In which tries to improvise the code by making it consume fewer resources and deliver high speed. In optimization, high-level general programming constructs are replaced by very efficient low-level programming codes.

Recommended Readings:

 

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.

Live masterclass