OnestopGate   OnestopGate
   Wednesday, March 29, 2017 Login  
Home | Overview | Syllabus | Tutorials | FAQs | Downloads | Recommended Websites | Advertise | Payments | Contact Us | Forum

GATE Resources
Gate Articles
Gate Books
Gate Colleges 
Gate Downloads 
Gate Faqs
Gate Jobs
Gate News 
Gate Sample Papers
Training Institutes

GATE Overview
GATE Eligibility
Structure Of GATE
GATE Coaching Centers
Colleges Providing M.Tech/M.E.
GATE Score
GATE Results
PG with Scholarships
Article On GATE
Admission Process For M.Tech/ MCP-PhD
GATE Topper 2012-13
GATE Forum

GATE 2018 Exclusive
Organizing Institute
Important Dates
How to Apply
Discipline Codes
GATE 2018 Exam Structure

GATE 2018 Syllabus
Aerospace Engg..
Agricultural Engg..
Architecture and Planning
Chemical Engg..
Civil Engg..
Computer Science / IT
Electronics & Communication Engg..
Electrical Engg..
Engineering Sciences
Geology and Geophysics
Instrumentation Engineering
Life Sciences
Mechanical Engg..
Metallurgical Engg..
Mining Engg..
Production & Industrial Engg..
Pharmaceutical Sciences
Textile Engineering and Fibre Science

GATE Study Material
Aerospace Engg..
Agricultural Engg..
Chemical Engg..
Civil Engg..
Computer Science / IT
Electronics & Communication Engg..
Electrical Engg..
Engineering Sciences
Instrumentation Engg..
Life Sciences
Mechanical Engg..
Pharmaceutical Sciences
Textile Engineering  and Fibre Science

GATE Preparation
GATE Pattern
GATE Tips N Tricks
Compare Evaluation
Sample Papers 
Gate Downloads 
Experts View

CEED 2013
CEED Exams
Application Forms
Important Dates
Contact Address
Examination Centres
CEED Sample Papers

Discuss GATE
GATE Forum
Exam Cities
Contact Details
Bank Details

Contact Us

Home » GATE Study Material » Computer Science » Compiler Design

Compiler Design

Looking for GATE Preparation Material? Join & Get here now!

** Gate 2013 Question Papers.. ** CEED 2013 Results.. ** Gate 2013 Question Papers With Solutions.. ** GATE 2013 CUT-OFFs.. ** GATE 2013 Results.. **

<<Previous Next>>
Code Optimiztion

Criteria for Code-Improving Transformations

Simply stated, the best program transformations are those that yield the most benefit for the least effort. The transformations provided by an optimizing compiler should have several properties.

First, a transformation must preserve the meaning of programs. That is, an "optimization" must not change the output produced by a program for a given input, or cause an error, such as a division by zero, that was not present in the original version of the source program. The influence of this criterion pervades this chapter; at all times we take the "safe" approach of missing an opportunity to apply a transformation rather than risk changing what the program does.

Second, a transformation must, on the average, speed up programs by a measurable amount. Sometimes we are interested in reducing the space taken by the compiled code, although the size of code has less importance than it once had. Of course, not every transformation succeeds in improving every program, and occasionally an "optimization" may slow down a program slightly, as long as on the average it improves things.

Third, a transformation must be worth the effort. It does not make sense for a compiler writer to expend the intellectual effort to implement a code improving transformation and to have the compiler expend the additional time compiling source programs if this effort is not repaid when the target programs are executed. Certain local or "peephole" transformations of the kind are simple enough and beneficial enough to be included in any compiler.

Some transformations can only be applied after detailed, often time-consuming, analysis of the source program, so there is little point in applying them to programs that will be run only a few times. For example, a fast, nonoptimizing, compiler is likely to be more helpful during debugging or for "student jobs” that will be run successfully a few times and thrown away. Only when the program in question takes up a significant fraction of the machine's cycles does improved code quality justify the time spent running an optimizing compiler on the program.

Before we get into optimization as such we need to familiarize ourselves with a few things


Countless algebraic transformations can be used to change the set of expressions computed by a basic block into an algebraically equivalent set. The useful ones are those that simplify expressions or replace expensive operations by cheaper ones. For example, statements

such as x := x +0 Or x := x*1

can be eliminated from a basic block without changing the set of expressions it computes. The exponentiation operator in the statements

x := y ** 2

usually requires a function call to implement. Using an algebraic transformation, this statement can be replaced by cheaper, but equivalent statement

x := y*y


We can add the flow-of –control information to the set of basic blocks making up a program by constructing a directed graph called a flow graph. The nodes of the flow graph are the basic blocks. One node is distinguished as initial; it is the block whose leader is the first statement. There is a directed edge from block B1 to block B2can be immediately follow B1in some execution sequence; that is, if

1. there is a conditional or unconditional jump from the last statement of B2, or 2. B2 immediately follow B1in the order of the program, and B1 does not end in the unconditional jump

B1 is a predecessor of B2, and B2is a successor of B1.

Example 4:The flow graph of the program of fig. 7 is shown in fig. 9, B1 is the initial node.



Basic Blocks are represented by variety of data structures. For example, after partitioning the three address statements by Algorithm 1, each basic block can be represented by a record consisting of a count of number of quadruples in the block, followed by a pointer to the leader of the block, and by the list of predecessors and successors of the block. For example the block B2 running from the statement (3) through (12) in the intermediate code of figure 2 were moved elsewhere in the quadruples array or were shrunk, the (3) in if i<=20 goto(3) would have to be changed.


Loop is a collection of nodes in a flow graph such that


1. All nodes in the collection are strongly connected; from any node in the loop to any other, there is path of length one or more, wholly within the loop, and

2. The collection of nodes has a unique entry, a node in the loop such that is, a node in the loop such that the only way to reach a node of the loop from a node outside the loop is to first go through the entry.

A loop that contains no other loops is called an inner loop.


A statement-by-statement code-generations strategy often produce target code that contains redundant instructions and suboptimal constructs .The quality of such target code can be improved by applying “optimizing” transformations to the target program.

A simple but effective technique for improving the target code is peephole optimization, a method for trying to improving the performance of the target program by examining a short sequence of target instructions (called the peephole) and replacing these instructions by a shorter or faster sequence, whenever possible.

The peephole is a small, moving window on the target program. The code in the peephole need not contiguous, although some implementations do require this. We shall give the following examples of program transformations that are characteristic of peephole optimizations:

• Redundant-instructions elimination • Flow-of-control optimizations • Algebraic simplifications • Use of machine idioms
<<Previous Next>>

Discussion Center







Email ID:

  Forgot Password?
 New User? Register!

Get 9,000+ Interview Questions & Answers in an eBook. Interview Question & Answer Guide
  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades
  • Gate Books
  • Training Institutes
  • Gate FAQs
  • Mechanical Engineeering Books
  • Robotics Automations Engineering Books
  • Civil Engineering Books
  • Chemical Engineering Books
  • Environmental Engineering Books
  • Electrical Engineering Books
  • Electronics Engineering Books
  • Information Technology Books
  • Software Engineering Books
  • GATE Preparation Books
  • Exciting Offers

    GATE Exam, Gate 2009, Gate Papers, Gate Preparation & Related Pages

    GATE Overview | GATE Eligibility | Structure Of GATE | GATE Training Institutes | Colleges Providing M.Tech/M.E. | GATE Score | GATE Results | PG with Scholarships | Article On GATE | GATE Forum | GATE 2009 Exclusive | GATE 2009 Syllabus | GATE Organizing Institute | Important Dates for GATE Exam | How to Apply for GATE | Discipline / Branch Codes | GATE Syllabus for Aerospace Engineering | GATE Syllabus for Agricultural Engineering | GATE Syllabus for Architecture and Planning | GATE Syllabus for Chemical Engineering | GATE Syllabus for Chemistry | GATE Syllabus for Civil Engineering | GATE Syllabus for Computer Science / IT | GATE Syllabus for Electronics and Communication Engineering | GATE Syllabus for Engineering Sciences | GATE Syllabus for Geology and Geophysics | GATE Syllabus for Instrumentation Engineering | GATE Syllabus for Life Sciences | GATE Syllabus for Mathematics | GATE Syllabus for Mechanical Engineering | GATE Syllabus for Metallurgical Engineering | GATE Syllabus for Mining Engineering | GATE Syllabus for Physics | GATE Syllabus for Production and Industrial Engineering | GATE Syllabus for Pharmaceutical Sciences | GATE Syllabus for Textile Engineering and Fibre Science | GATE Preparation | GATE Pattern | GATE Tips & Tricks | GATE Compare Evaluation | GATE Sample Papers | GATE Downloads | Experts View on GATE | CEED 2009 | CEED 2009 Exam | Eligibility for CEED Exam | Application forms of CEED Exam | Important Dates of CEED Exam | Contact Address for CEED Exam | CEED Examination Centres | CEED Sample Papers | Discuss GATE | GATE Forum of | GATE Exam Cities | Contact Details for GATE | Bank Details for GATE | GATE Miscellaneous Info | GATE FAQs | Advertisement on GATE | Contact Us on OneStopGATE |
    Copyright © 2017. One Stop All rights reserved Testimonials |Link To Us |Sitemap |Privacy Policy | Terms and Conditions|About Us
    Our Portals : Academic Tutorials | Best eBooksworld | Beyond Stats | City Details | Interview Questions | India Job Forum | Excellent Mobiles | Free Bangalore | Give Me The Code | Gog Logo | Free Classifieds | Jobs Assist | Interview Questions | One Stop FAQs | One Stop GATE | One Stop GRE | One Stop IAS | One Stop MBA | One Stop SAP | One Stop Testing | Web Hosting | Quick Site Kit | Sirf Dosti | Source Codes World | Tasty Food | Tech Archive | Software Testing Interview Questions | Free Online Exams | The Galz | Top Masala | Vyom | Vyom eBooks | Vyom International | Vyom Links | Vyoms | Vyom World
    C Interview Questions | C++ Interview Questions | Send Free SMS | Placement Papers | SMS Jokes | Cool Forwards | Romantic Shayari