New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Adele Schaden MD


Adele Schaden MD
GPA 3.88

Rajiv Gupta

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Rajiv Gupta
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 9 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 201 at University of California Riverside taught by Rajiv Gupta in Fall. Since its upload, it has received 32 views. For similar materials see /class/231744/cs-201-university-of-california-riverside in ComputerScienence at University of California Riverside.

Similar to CS 201 at UCR

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
33009 CS 201 Compiler ConsTrucTion LecTure 2 ConTrol Flow Analysis WhaT is a loop A subgraph of CFG wiTh The following properTies STrongly ConnecTed There is a paTh from any node in The loop To any oTher node in The loop and Single EnTry There is a single enTry inTo The loop from ouTside The loop The enTry node of The loop is called The loop header E Z Loop nodes 2 3 5 EL Header node 2 LSJ Loop back edge 592 Tail Head ProperTy Given Two loops They are eiTher disjoinT or39 one is compleTely nesTed wiThin The oTher39 J LLJ in L Loops 124 Loop 56 is Loop 56 is and 56 are nesTed wiThin nesTed wiThin DisjoinT oop 2456 oop 23456 IdenTifying Loops DefiniTions DominoTes node n dominoTes node m iff all poThs from sTor39T node To node m pass Through node n ie To visiT node m we musT firsT visiT node n A NoTur39ol Loop hos A single enTr39y 9 The enTr39y node dominoTes all nodes in The loop and A back edge and edge A98 such ThoT B dominoTes A B is The head amp A is The Toil 33009 33009 Identifying Loops AlgoriThm for finding loops 1 CompuTe DominaTor InformaTion 2 IdenTify Back Edges 3 ConsTrucT NaTural Loops corresponding To Back Edges DominaTors Characfers cs H Every node dominaTes iTself N STarT node dominaTes every node in The flow graph A If N DOM M and M DOM R Then N DOM R 4gt If N DOM M and O DOM M Then eiTher N DOM O or O DOM N 5 SeT of dominaTors of a given node can be linearly ordered according To dominaTor relaTionships Domina rors Characfers cs 6 Domina l39or inform l ion can be represen l39ed by a Domina l or Tree Edges in The domina l or 139ree represen l39 immedia l e domina l or rela l39ionships ag 9 6 a CFG Domina l39or Tree 7 1 is The immedia l e domina l or of 2 3 amp 4 Compu ring Domina ror Se rs Observa l39ion node m donimc l39es node n iff m domina l es all predecessors of n Le I39 Dn set of domina l ors of n 301 fry U m Dp Perdp Where Predn is set of immedia l e predecessors of n in The CFG 33009 33009 CompuTing DominaTor SeTs I III 170 A pproxima fion A IgorTh rn Dno no Dm m D lsl1hosrfg fnie form n en a 079 quotin 1 N N is seT of all nodes w I Lmnjei 0 on Dn ocw M W n m N Tanyao IferafiveyRef ne Dn s39 D6 my U n Dr Mn m u 1 00 WW FEW PfPr dewle Example Compufing Dom SeTs D0 1 W 2 U D0 12 D3 3 U D0 13 D4 4 U DZM D3n W 14 D5 5 U D40 D10 145 D6 e u D5n 07 1456 07 7 u 05 1457 08 8 u D6r 010 14568 09 9 u 08 145689 010 10 u 08 1456810 Bock Edges 994 1098 1095 33009 No rur39ol Loop Given a back edge N 9 D Na rur al loop of edge N 9 D X s r X can reach N wi rhou r going Through D 1 dominates 6 2 691 is a back edge Natural Loop of 691 7 3456 73456 Algor39i rhm for39 Loop Consfr39uc rion Given a Back Edge N9D Sfack emp ry Inser rm if m no r in Loop rhen Loop Loop U m push m onfo S rack While sfack no emp ry do pop m rop elemen r of s rack for each p in predm do endif Inser rp End Inser r endfor Endwhi Ie Example Back Edge 792 E D 1 L L P 27 6 4 5 3 5 Li suck xwm a La 1 NEI Examples P if While A do 9 L2 9 B 52 51 L39 6 L19 A51B52 Wm Bd r L7 L2 neS I39ed in L1 Endwhile e Endwhile L39 U L19 515253S4 L2 9 525354 53 L1 L2 neS I39ed in L1 14 33009 Reducible Flow Graph The edges of a reducible flow graph can be parTiTioned im o Two disjoim SeTs Forward from an acyclic graph in which every node can be reached from The iniTial node Back edges whOSe heads sink domina ie Tails source Any flow graph ThaiL cannoT be parTiTioned as above is a nonreducible or irreducible Reducible Flow Graph How To check reducibiliTy Remove all back edges and see if The resulting graph is acyclic Irred ucible Node Spli r rinq 2 5 i i I 293 MT 0 back edge Conver rs irreducible 7 392 MT 0 back edge To reducible graph is no r acyclic Reducible 15 33009 Loop De rec rion in Reducible Graphs DepThfrs f Ordering numbering of nodes in The reverse order in which They were IasT visi red during depTh firsT search M N is a back edge iff DFNM gt DFNN Forward edge M N Depthfirst M is descendan r of N in DFST Ordering Back edge M N N is ances ror of M in DFST Algori rhm for DFN Compu ra rion DFSX mark X as Visited for each successor S ofX do Mark all nodes as unvisited ifs is ccunvisited then DFST add edge XS to DFST set of edges ofDFST can DFSS I of nodes in the graph endif DFSno endfor DFNX 1 I I 7 1 33009


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.