MIT 21 Live Variable Analysis (slides) (798427)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Problem• Abstract assembly contains arbitrarily manyregisters tiCS 4120Introduction to Compilers• Want to replace all such nodes with registernodes for e[a-d]x, e[sd]i, (ebp)• Local variables allocated to TEMP’s too• Only 6-7 usable registers: need to allocatemultiple ti to each registerAndrew MyersCornell UniversityLecture 21: Live Variable Analysis14 Oct 09• For each statement, need to know whichvariables are live to reuse registersCS 4120 Introduction to CompilersUsing scopeLive variable analysis• Goal: for each statement, identify whichtemporaries are live• Analysis will be conservative (may overestimate liveness, will never underestimate)But more precise than simple scope analysis(will estimate fewer live temporaries)• Observation: temporaries, variables have boundedscope in program• Simple idea: use information about program scopeto decide which variables are live• Problem: overestimates liveness{ int b = a + 2;int c = b*b;int d = c + 1;return d; }b is livec is live, b is notwhat is live here?CS 4120 Introduction to Compilers23CS 4120 Introduction to Compilers4Control Flow GraphLiveness• Canonical IR forms control flow graph (CFG ) :statements are nodes; jumps, fall-throughs are edges• Liveness is associated with edges of controlflow graph, not nodes (statements)live: a, c, eMOVEfall-through edgeslive: b, cEXPin-edgesCJUMPJUMP• Same register can be used for differenttemporaries manipulated by one stmtout-edgesCS 4120 Introduction to Compilers5Examplea=b+1Use/Def• Every statement uses some set of variables(reads from them) and defines some set ofvariables (writes to them)• For statement s define:MOVE(TEMP(ta), TEMP(tb) + 1)mov ta, tbadd ta, 1Live: tbmov ta, tbadd ta,1– use[s] : set of variables used by sLive: ta (maybe)Register allocation: ta ! eax, tb ! eaxmov eax, eaxadd eax, 1CS 4120 Introduction to Compilers6CS 4120 Introduction to Compilers7– def [s] : set of variables defined by s• Example:a=b+ca=a+1use = b,cuse = aCS 4120 Introduction to Compilersdef = adef = a8LivenessSimple algorithm: Backtracing“variable v is live on edge e if there is a node n in CFG thatuses it and a directed path from e to n passing throughno def ”Variable v is live on edge e if:There is–a node n in the CFG that uses it and–a directed path from e to n passing throughno def(Slow) algorithm: Try all paths from each use of a variable,tracing backward in the control flow graph until a defnode or previously visited node is reached.

Markvariable live on each edge traversed.How to compute efficiently?How to use?CS 4120 Introduction to Compilers9Dataflow Analysis10Dataflow values• Idea: compute liveness for all variablessimultaneously• Approach: define equations that must besatisfied by any liveness determination• Solve equations by iteratively converging onsolution• Instance of general technique forcomputing program properties: dataflowanalysisCS 4120 Introduction to CompilersCS 4120 Introduction to Compilers11use[n] : set of variables used by ndef [n] : set of variables defined by nin[n] : variables live on entry to nout[n] : variables live on exit from nClearly: in[n] " use[n]What other constraints are there?CS 4120 Introduction to Compilers12Dataflow constraintsIterative dataflow analysis• Initial assignment to in[n], out[n] is empty set Ø : will notsatisfy constraintsin[n] " use[n]– A variable must be live on entry to n if it isused by the statement itselfin[n] " use[n]in[n] " out[n] – def [n]in[n] " out[n] – def [n]out[n] " in[n’ ] if n’ # succ [n]– If a variable is live on output and the statementdoes not define it, it must be live on input tooout[n] " in[n’ ] if n’ # succ [n]in’[n] = use[n] $ (out[n] – def [n])out’[n] = $n’ # succ[n] in[n’]– if live on input to n’, must be live on outputfrom nCS 4120 Introduction to Compilers• Idea: iteratively re-compute in[n], out[n] when forced to byconstraints.

Live variable sets will increase monotonically.• Dataflow equations:13Complete algorithm14CS 4120 Introduction to CompilersExample• For simplicity: pseudo-codefor all n, in[n] = out[n] = Ørepeat until no changefor all n12out[n] = !n’ # succ[n] in[n’]in[n] = use[n] ! (out[n] – def3use: edef: z[n])e=1 def: euse: xif x>0z=e*e4return x use: x5use: e, x y=e*xdef: yendenduse: x• Finds fixed point of in, out equations• Problem: does extra work recomputing in, out values whenno change can happenCS 4120 Introduction to Compilers156if x&17use: ze=z def:eCS 4120 Introduction to Compilers8e=y use: ydef: e16Example12e=1 def: euse: xif x>04use: e 3z=e*ereturn x use: xdef: z56y=e*x use: e, xdef: yif x&1 use: x87use: ze=z def:ee=y use: ydef: e2: in={x}3: in={e}4: in={x}5: in={e,x}6: in={x}7: out={x}, in={x,z}8: out={x}, in={x,y}1: out={x}, in={x}2: out={e,x}, in={e,x}3: out={e,x}, in={e,x}5: out={x}, in={e,x}6: out={x,y,z}, in={x,y,z}7: out={e,x}, in={x,z}8: out={e,x}, in={x,y}1: out={e,x}, in={x}5: out={x,y,z}, in={e,x,z}3: out={e,x,z}, in={e,x}all equations satisfiedCS 4120 Introduction to Compilers17Worklist algorithm• Idea: keep track of nodes that might need to beupdated in worklist : FIFO queuefor all n, in[n] = out[n] = Øw = { set of all nodes }repeat until w emptyn = w.pop( )out[n] = $n’ # succ [n] in[n’]in[n] = use[n] $ (out[n] — def [n])if change to in[n],for all predecessors m of n, w.push(m)endCS 4120 Introduction to Compilers19Faster algorithm• Information only propagates betweennodes because of this equation:out[n] =$n’ # succ [n]in[n’]• Node is updated from its successors– If successors haven’t changed, no need toapply equation for node– Should start with nodes at “end” and workbackwardCS 4120 Introduction to Compilers18.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов статьи