What is a flow graphExplain its significance in code generation System Programming and Compiler Construction Sem 6 Mumbai University May 2015

We are building EduLadder(ELADR) - Protocol

The Eladr Protocol is a decentralized, security and efficiency enhanced Web3 noSQL database powered by IPFS as the data storage layer https://ipfs.io/, and the Cardano block chain as the rewards token platform, https://cardano.org/. It provides a JSON based, IPFS layer 2 solution for data indexing and retrieval in an 'append only' file system built with open source Node.js API libraries.

The ELADR token was designed to incentivize and reward community members as a proof of contribution. Token holders are also granted access to EduLadder.com premium features as well as associated ELADR token enabled apps.

WHITE PAPER Buy Now Try BETA

Real Problems! Real Experts!

Join Our Telegram Channel !

The Eduladder is a community of students, teachers, and programmers. We help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions

GATE GMAT CBSE NCERT Career Interview Railway UPSC NID NIFT-UG NIFT-PG PHP AJAX JavaScript Node Js Shell Script Research

Sixth-Semester-BE-Degree-Examination-JuneJuly-2013-Compiler-Design-Question-paper-->View question

What is a flow graph?Explain its significance in code generation-System Programming and Compiler Construction-Sem 6-Mumbai University-May 2015

It is related to system programming and compiler construction.

Asked On2017-12-19 15:08:53 by:leo

Taged users:
Salomon-Dalmet JAINAM-JAIN

Likes:
Purnima

Dislikes:
Be first to dislike this question
Talk about this Like Dislike

View all questions

Answers

Machine Dependent Optimization

•Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture.

•It involves CPU registers and may have absolute memory references rather than relative references.

•Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.

Basic Blocks

•Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code.

•These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.

•A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.

Basic Block Identification

We may use the following algorithm to find the basic blocks in a program:

Search header statements of all the basic blocks from where a basic block starts:

i. First statement of a program.

ii. Statements that are target of any branch (conditional/unconditional).

iii. Statements that follow any branch statement.

Header statements and the statements following them form a basic block.

•A basic block does not include any header statement of any other basic block.

•Basic blocks are important concepts from both code generation and optimization point of view.

•Basic blocks play an important role in identifying variables, which are being used more than once in a single basic block.

•If any variable is being used more than once, the register memory allocated to that variable need not be emptied unless the block finishes execution.

Control Flow Graphs

•Basic blocks in a program can be represented by means of control flow graphs.

•A control flow graph depicts how the program control is being passed among the blocks. It is a useful tool that helps in optimization by help locating any unwanted loops in the program.

•In a control flow graph each node in the graph represents a basic block, i.e. a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. Directed edges are used to represent jumps in the control flow.

•There are, in most presentations, two specially designated blocks: the entry block, through which control enters into the flow graph, and the exit block, through which all control flow leaves.

•Because of its construction procedure, in a non-trivial CFG (i.e. one with more than zero edges), every edge A→B has the property that:

outdegree (A) > 1 or indegree (B) > 1 (or both).

•The CFG can thus be obtained, at least conceptually, by starting from the program's (full) flow graph—i.e. the graph in which every node represents an individual instruction—and performing an edge contraction for every edge that falsifies the predicate above, i.e. contracting every edge whose source has a single exit and whose destination has a single entry.

•This contraction-based algorithm is of no practical importance, except as a visualization aid for understanding the CFG construction, because the CFG can be more efficiently constructed directly from the program by scanning it for basic blocks.

(d) an irreducible CFG: a loop with two entry points, e.g. goto into a while or for loop

Example

Consider the following fragment of code:

0: (A) t0 = read_num

1: (A) if t0 mod 2 == 0

2: (B) print t0 + " is even."

3: (B) goto 5

4: (C) print t0 + “is odd."

5: (D) end program

In the above, we have 4 basic blocks: A from 0 to 1, B from 2 to 3, C at 4 and D at 5. In particular, in this case, A is the "entry block", D the "exit block" and lines 4 and 5 are jump targets. A graph for this fragment has edges from A to B, A to C, B to D and C to D.

Answerd on:2018-06-06 Answerd By:aksingh1818

Likes:
|aksingh1818

Dislikes:
Be first to dislike this answer
Talk about this Like Dislike

Lets together make the web is a better place

We made eduladder by keeping the ideology of building a supermarket of all the educational material available under one roof. We are doing it with the help of individual contributors like you, interns and employees. So the resources you are looking for can be easily available and accessible also with the freedom of remix reuse and reshare our content under the terms of creative commons license with attribution required close.

You can also contribute to our vision of "Helping student to pass any exams" with these.
Answer a question: You can answer the questions not yet answered in eduladder.How to answer a question
Career: Work or do your internship with us.Work with us
Create a video: You can teach anything and everything each video should be less than five minutes should cover the idea less than five min.How to upload a video on eduladder

Welcome to Eduladder V 4.0

Ads

What is a flow graph?Explain its significance in code generation-System Programming and Compiler Construction-Sem 6-Mumbai University-May 2015

It is related to system programming and compiler construction.

Similar Questions

Notes