DOC PREVIEW
CMU CS 15745 - Lecture

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

lect. SSA construction © Seth Copen Goldstein 2001-7 115-745SSADominatorsCopyright © Seth Copen Goldstein 2001-7lect. SSA construction © Seth Copen Goldstein 2001-7 2The Φ function• Φ merges multiple definitions along multiple control paths into a single definition.• At a BB with p predecessors, there are p arguments to the Φ function.xnew← Φ(x1, x1, x1, … , xp)• How do we choose which xito use?– Most compiler writers don’t really care!– If we care, use moves on each incoming edge(Or, as in pegasus use a mux)lect. SSA construction © Seth Copen Goldstein 2001-7 3Trivial SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for all live variables.y ← xy ← 2z ← y + xx ← 1y1← x1y2← 2x2← Φ(x1,x1)y3← Φ(y1,y2)z1← y3+ x2x1← 1Way too many Φfunctions inserted.lect. SSA construction © Seth Copen Goldstein 2001-7 4Minimal SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for all variables with multiple outstanding defs.y ← xy ← 2z ← y + xx ← 1y1← x1y2← 2y3← Φ(y1,y2)z1← y3+ x1x1← 1lect. SSA construction © Seth Copen Goldstein 2001-7 5When do we insert Φ?11156 781323491012CFGIf there is a def of a in block 5, which nodes need a Φ()?Note: a is implicitly defined in block 1lect. SSA construction © Seth Copen Goldstein 2001-7 6When do we insert Φ?•Insert a Φ function for variable A in block Z iff:– A was defined more than once before(i.e., A defined in X and Y AND X ≠ Y)– Z is the first block that joins the paths from X to Z and Y to Z• Entry block implicitly defines of all vars•Note: A = Φ(…) is a def of Alect. SSA construction © Seth Copen Goldstein 2001-7 7When do we insert Φ?•Insert a Φ function for variable A in block Z iff:– A was defined more than once before(i.e., A defined in X and Y AND X ≠ Y)– There exists a non-empty path from x to z, Pxz, and a non-empty from y to z, Pyzs.t.•Pxz∩ Pyz= { z }•z ∉ Pxqor z ∉ Pyrwhere Pxz= Pxq→ z and Pyz= Pyr→ z• Entry block implicitly defines all vars•Note: A = Φ(…) is a def of Alect. SSA construction © Seth Copen Goldstein 2001-7 8When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 9When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 10When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 11When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 12Def-use property of SSA•If xiis used in x ← Φ(…, xi, …), thenNO BBs in any path from BB(xi) to BB(Φ) include def of x except BB(Xi) and BB(Φ)• If x is used in y ← … x …, then no BBs in path from BB(x) to BB(y) define x except BB(x)11156 781323491012Another way to say this:Definitions dominate useslect. SSA construction © Seth Copen Goldstein 2001-7 13Dominance Property of SSA• In SSA definitions dominate uses.–If xiis used in x ← Φ(…, xi, …), thenBB(xi) dominates ith pred of BB(PHI)– If x is used in y ← …x …, then BB(x) dominates BB(y)• Use this for an efficient alg to convert to SSA11156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 14A little side trip• Computing dominators• d dom n iff every path from s to n goes through d• n dom n for all n• Some definitions:– immediate dominator: d idom n iff•d ≠ n•d domn• d doesn’t dominate any other dominator of n– strictly dominates: s sdom n iff•s domn•s ≠ nlect. SSA construction © Seth Copen Goldstein 2001-7 15Examples•d domniff every path from Entry to n contains d.1 dom 1 ; 1 dom 2 ; 1 dom 3 ; 1 dom 4 ; 2 dom 2 ; 2 dom 3 ; 2 dom 4 ; 3 dom 3 ; 4 dom 4•s strictly dominates n, (s sdom n), iff s dom n and s ≠ n.1 sdom 2 ; 1 sdom 3 ; 1 sdom 4 ;2 sdom 3 ; 2 sdom 4•d immediately dominates n, d=idom(n), iff d sdom n and there is no node x such that d dom x and x dom n.1 idom 2 ; 2 idom 3; 2 idom 4BB 1BB 2BB 3 BB 4EntryExit(adapted from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 16Properties of dominators• idom(n) is unique• The dominance relation is a partial ordering; that is, it is reflexive, anti-symmetric and transitive:–reflexive: x dom x– anti-symmetric: x dom y and y dom x → x = y–transitive : x dom y and y dom z → x dom z(adapted from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 17The dominator tree• One can represent dominators in a cfg as a tree of immediate dominators.• In dominator tree, edge from parent to child if parent idom child in the cfg• The set of dominators of a node are the nodes from the root to the node.BB 1BB 2BB 3 BB 4EntryBB 1BB 2BB 3 BB 4EntryExitlect. SSA construction © Seth Copen Goldstein 2001-7 18Computing Dominators• d dom n iff every path from s to n goes through d• Note: n dom n for all n• If s dom d & d ≠ n & pi∈ pred(n) & d dom pi,then d dom n•• How can we use this?np1p2 pksdlect. SSA construction © Seth Copen Goldstein 2001-7 19Computing Dominators• d dom n iff every path from s to n goes through d• Note: n dom n for all n• If s dom d & d ≠ n & pi∈ pred(n) & d dom pi,then d dom n•np1p2 pksdUI)()(}{)(npredppdomnndom∈=lect. SSA construction © Seth Copen Goldstein 2001-7 20Simple iterative alg• dom(Entry) = Entryfor all other nodes, n, dom(n) = all nodeschanged = truewhile (changed) {changed = falsefor each n, n≠Entry {old = dom(n)if (dom(n) != old) changed = true}}UI)()(}{)(npredppdomnndom∈=(adapted from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 21ExampleDOM (Entry) = {Entry}DOM (1) = {Entry,1}DOM (2) = {Entry,1,2}DOM (3) = {Entry,1,2,3}DOM (4) = {Entry,1,2,3,4}DOM (5) = {Entry,1,2,3,4,5}DOM (6) = {Entry,1,2,3,4,5,6}DOM (7) = {Entry,1,2,3,4,5,7}DOM (8) = {Entry,1,2,3,4,5,8}DOM (9) = {Entry,1,2,3,4,9}DOM (10) = {Entry,1,2,10)BB 1BB 2BB 3BB 4BB 5BB 6BB 8BB 9BB 10ExitBB 7Entry(Borrowed from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 22Finding immediate dominators• idom(n) dominates n, isn’t n, and, doesn’t strictly dominate any other sdom n• Init idom(n) to nodes


View Full Document

CMU CS 15745 - Lecture

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

5 pages

Lecture

Lecture

6 pages

lecture

lecture

17 pages

Lecture 3

Lecture 3

12 pages

Lecture

Lecture

17 pages

Lecture

Lecture

18 pages

lecture

lecture

14 pages

lecture

lecture

8 pages

lecture

lecture

5 pages

lecture

lecture

10 pages

Lecture

Lecture

20 pages

Lecture

Lecture

8 pages

Lecture

Lecture

7 pages

lecture

lecture

59 pages

Lecture

Lecture

10 pages

Task 2

Task 2

2 pages

Handout

Handout

18 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?