今日の英語 - Control flow analysis in scheme その7

english

速読の練習。速読はしない。文の構造を意識しつつ読み進める習慣をつける。方法論はTOEFLテスト速読・速聴大特訓 基礎編で。

ルールは以下の通り。まだ読み終わっていないがべつの題材を探そうと思う。後半は式の説明ばかりだ。

  • トピックセンテンスは {{ }} で囲む
  • シグナルワードは == ==
  • パラグラフのトピックは必ず書く。
  • サポート情報のスタイルを書く
  • 列挙には(1)(2)(3)と振る
  • 対比には (A)(a) のように目印
  • 例示は何に対するサポートかを一言書き添える
  • 原因・結果には => を

6. Side Effects

Side effects in Lisp is not important

{{For the purposes of doing control flow analysis of Lisp, tracking
side effects is not of primary importance.}} ==Since(原因・理由)== Lisp makes
variable binding convenient and cheap, side effects occur ==relatively（比較：ALGOL系）==
infrequently. (This is especially true of well written
Lisp.) The pieces of Lisp we are most interested in flow
analysing - inner loops - use side effects primarily for updating
iteration variables, which are rarely functional values. The
control flow of inner loops is usually explicitly written out, and
tends not to use functions as first class citizens.

Updating of loop variables is a task of loop packages

{{To further editorialise, I believe that the updating of loop
variables is a task best left to loop packages such as Waters’
Lets [Lets] or the Yale Loop [YLoop], where the actual updating
technique can be left to the macro writer to implement
efficiently, and ignored by the application programmer.}} ==Even==
the standard Common Lisp and Scheme looping construct, do,
permits a binding interpretation of its iteration variable update
semantics.

side effects on control flow analsys

For these reasons, we can afford to settle for a solution that
is merely correct, without being very informative. {{==Therefore==,
the control flow analysis presented here uses a very weak technique
to deal with side effects.}} The CPS transformation discussed
in section 3 removes all side effects to variables. Only
side effects to data structures are allowed. All side effects and
accesses to data structures are performed by primops. Among
these primopsare cons, rplaca, rplacd.car.cdr,vref,
and vset. We divide these into ==two== sets: data 1(stashers), and
2(datafetchers). Stashers. such as cons, rplaca, rplacd,
and vset, take functions and tuck them away into some data
structure. Fetchers - car, cdr, vref - fetch functions
from some data structure.

Stashers and fetchers.

The analysis takes the simple view that once a function is
stashed into a data structure, it has escaped from the analyser’s
ability to track it. It could potentially be the value of
any data structure access, or escape outside the program to the
ESCAPED set. Thus we have ==two rules== for side effects:
1. Any lambda passed to a stasher primop is included in the
ESCAPED set.
(cons a d kont) 3 [S-1]
Defs(a), Defs(d) ⊂ ESCAPED
(vset vec index val kont) [S-2]
Defs(val) C ESCAPED
etc.
2. A fetcher primop can pass any ESCAPED function to its
continuation:
(fetcher . . . cont) (F-1)
V (lambda (xl . . . ) ∈ Defs(cont),
ESCAPED ⊂ Defs(x)
{{In a sense, stashers and fetchers act as black and white holes:
values disappear into stasher primops and pop out at fetcher
primops.}}

7. Induction Variable Elimination: An Application

control flow analysis can usefor other data flow analysis

{{Once we’ve performed control flow analysis on a program, we
can use the information gained to do other data flow analyses.}}
Control flow analysis by itself does not provide enough information
to do all the data flow problems we might desire - the
limitations of control flow analysis are discussed in the section
8 -but we can still solve some useful problem

Example of induction variables elimination

{{As an ==example==, consider induction variable elimination. Induction
variable elimination is a technique used to transform
array references inside loops into pointer incrementing operations.}}
For example, suppose we have the following C routine:

int a[50] [30];
example() {
integer r, c;
for(r=O; r<50; r++)
  for(c=O; c<30; c++)
  a[r][c] = 4;
}

We can remove the entire address calculation

The example function assigns 4 to all the elements of array
a. The array reference a [r] [c] on a byte addressed machine
is equivalent to the address computation a+4* (c+30*r).
This calculation requires two multiplications and two additions.
{{By replacing the array indices with a pointer variable, we can
remove the entire address calculation:}}

example () {
  integer *ptr;
  for(ptr=a; ptr<a+1500; ptr++)
  *ptr = 4;
}

Induction variable elimination is a technique for automatically performing the above transformation.

{{Induction variable elimination is a technique for automatically
performing the above transformation.}} The Lisp variant
uses control flow analysis.