petit/doc/wolfe_tiny.roff

   1 .\" process with 'troff -ms', with no preprocessors
   2 .de HL
   3 .br
   4 \\l'16c'
   5 .br
   6 ..
   7 .de PT
   8 .nr PN \\n%
   9 ..
  10 .       \" roman numeral page numbers
  11 .nr Nc 0
  12 .de Br
  13 .nr PF \\n(.f
  14 .nr PX \\n(.s
  15 .ft R
  16 .ps \\n(PS
  17 .lt \\n(LTu
  18 .po \\n(POu
  19 .pc %
  20 .af % i
  21 .if !\\n(Nc .if o .tl ' ' '%'
  22 .if !\\n(Nc .if e .tl '%' ' '
  23 .if \\n(Nc .tl ' '%' '
  24 .ft \\n(PF
  25 .ps \\n(PX
  26 ..
  27 .       \" arabic numeral page numbers
  28 .de Ba
  29 .nr PF \\n(.f
  30 .nr PX \\n(.s
  31 .ft R
  32 .ps \\n(PS
  33 .lt \\n(LTu
  34 .po \\n(POu
  35 .pc %
  36 .af % 1
  37 .if !\\n(Nc .if o .tl ' ' '%'
  38 .if !\\n(Nc .if e .tl '%' ' '
  39 .if \\n(Nc .tl ' '%' '
  40 .ft \\n(PF
  41 .ps \\n(PX
  42 ..
  43 .de BT
  44 .Ba
  45 ..
  46 .       \" choose roman page numbers
  47 .de Nr
  48 .nr % 1
  49 .de BT
  50 .Br
  51 \\..
  52 ..
  53 .de Na
  54 .nr % 1
  55 .de BT
  56 .Ba
  57 \\..
  58 ..
  59 .de Nn
  60 .de BT
  61 \\..
  62 ..
  63 .de Nc
  64 .nr Nc 1
  65 ..
  66 .de Dp
  67 .br
  68 .nr Ps \\n(PS
  69 .nr Vs \\n(VS
  70 .nr VS \\n(PSp
  71 .nr VS +2p
  72 .DS
  73 .ft L
  74 ..
  75 .de Dq
  76 .br
  77 .nr Ps \\n(PS
  78 .nr Vs \\n(VS
  79 .nr VS \\n(PSp
  80 .nr VS +2p
  81 .DS L
  82 .ft L
  83 ..
  84 .de De
  85 .ft R
  86 .DE
  87 .ps \\n(Ps
  88 .vs \\n(Vs
  89 .nr VS \\n(Vs
  90 .nr PS \\n(Ps
  91 ..
  92 .de []
  93 ..
  94 .LP
  95 .de Dx
  96 .br
  97 .nr Ps \\n(PS
  98 .nr Vs \\n(VS
  99 .nr PS 9
 100 .nr VS 11
 101 .DS L
 102 .B1
 103 .ft L
 104 ..
 105 .de Dy
 106 .sp 0.5
 107 .B2
 108 .De
 109 ..
 110 .ds t T\s-3INY\s+3
 111 .\"
 112 .\"
 113 .\" definitions done
 114 .\" Start text here
 115 .\"
 116 .\"
 117 .\"
 118 .\" title page
 119 .\"
 120 .Nn
 121 .sv 1i
 122 .ce 99
 123 .ft B
 124 .LG
 125 .LG
 126 .LG
 127 TINY
 128 .NL
 129 .sp 2
 130 .LG
 131 A Loop Restructuring Research Tool
 132 .NL
 133 .sp 3
 134 .ft R
 135 Michael Wolfe
 136 Oregon Graduate Institute of Science and Technology
 137 19600 NW von Neumann Drive
 138 Beaverton, OR 97006 USA
 139 tel: 503-690-1153
 140 fax: 503-690-1029
 141 email: mwolfe@cse.ogi.edu
 142 .sp 2
 143 December 1990
 144 .ce 0
 145 .bp
 146 .\"
 147 .\" First page of real text
 148 .\"
 149 .Nc
 150 .NH 1
 151 Keys to Remember
 152 .XS
 153 1. Keys to Remember
 154 .XE
 155 .PP
 156 \*t is designed around a character menu interface (for the nonce);
 157 to choose a menu item, move the menu bar between menu items
 158 by using the space or backspace key, then typing the return key
 159 when the desired choice is highlighted.
 160 A quicker method is to type the leading character of the desired choice;
 161 uppercase or lowercase may be used.
 162 .PP
 163 Three keys always (almost) have special meaning.
 164 .IP Q
 165 at any menu should quit \*t and take
 166 you back to the shell prompt.
 167 .IP X
 168 at any menu should escape or exit out of this menu.
 169 Alternatively, the 'escape' key has the same effect.
 170 .IP ^L
 171 A control-L will refresh the screen.
 172 Occasional junk gets by the Curses package and will not be corrected by ^L.
 173 .NH 1
 174 Starting \*t
 175 .XS
 176 2. Starting \*t
 177 .XE
 178 .PP
 179 The screen display shows positions via highlighting, though
 180 the screen dumps in this documentation don't show that highlighting.
 181 To save space, multiple blank lines in the screen dumps are deleted.
 182 .PP
 183 When starting up \*t with no file argument, you get the screen:
 184 .Dx
 185
 186 Tiny Tool [as of December 1990]
 187 *Browse  File    Parse   Restor  System  Trans   Write   Msgs    Quit
 188 .Dy
 189 The first 22 lines (on a standard 24 line display) are the main window;
 190 the next to last line is a message line, and the bottom line is the
 191 current menu.
 192 The message would give the file name of the current program,
 193 if one was chosen.
 194 The main menu has 8 choices; choices can be made from any menu by
 195 using the space bar and backspace key to
 196 move the menu position (shown with highlighting and the asterisk)
 197 to the desired choice and hitting the return key, or (faster) by typing
 198 the leading character of the choice.
 199 Here, for instance, typing 'Q' will quit \*t.
 200 All menus in \*t have the Msgs, Quit and Xcape options
 201 (except for the main menu, which has no Xcape).
 202 Choosing Quit from any menu will quit \*t completely and
 203 immediately (in the absence of bugs).
 204 Choosing Msgs from any menu will display the most recent
 205 saved messages in the main window.
 206 Choosing Xcape from any menu returns to the previous menu;
 207 Xcape may also be chosen by typing the 'Escape' key on your keyboard.
 208 .PP
 209 To read in a program from a file after starting up \*t, we choose the
 210 Parse option; \*t then asks for the name of the file we wish
 211 to parse:
 212 .Dx
 213
 214
 215 Tiny Tool [as of December 1990]
 216 File:
 217 .Dy
 218 We then respond with the name of a file name:
 219 .Dx
 220
 221
 222 Tiny Tool [as of December 1990]
 223 File: ch
 224 .Dy
 225 and this file is read in and displayed:
 226 .Dx
 227   1: Entry
 228   1: real a(1:100,1:100)
 229   1: real b(1:100)
 230   3: integer n
 231   5: for k = 1,n do
 232   7:  a(k,k) = sqrt(a(k,k))
 233   9:  for i = k+1,n do
 234  11:   a(i,k) = a(i,k)/a(k,k)
 235  13:   for j = k+1,i do
 236  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 237  13:   endfor
 238   9:  endfor
 239   5: endfor
 240
 241 Parsed ch
 242  Browse  File   *Parse   Restor  System  Trans   Write   Msgs    Quit
 243 .Dy
 244 A quicker way to start up \*t on a file is to give the file
 245 name on the command line:
 246 .Dp
 247 % t ch
 248 .De
 249 which will start up by first parsing and displaying the program.
 250 .bp
 251 .NH 1
 252 Transformations
 253 .XS
 254 3. Transformations
 255 .XE
 256 .LP
 257 \*t currently implements 8 elementary loop restructuring transformations,
 258 with plans for several more to be added.
 259 The list is:
 260 .IP
 261 bumping
 262 .IP
 263 circulation
 264 .IP
 265 distribution
 266 .IP
 267 interchanging
 268 .IP
 269 negation
 270 (or reversal)
 271 .IP
 272 parallelization
 273 .IP
 274 skewing
 275 .IP
 276 vectorization (simple)
 277 .LP
 278 Each of these is explained here with examples.
 279 .NH 2
 280 Loop Bumping
 281 .XS
 282 3.1 Loop Bumping
 283 .XE
 284 .LP
 285 Bumping is simple adjusting loop lower and upper limits by adding
 286 (or subtracting) a constant integer.
 287 This is occasionally used to make lower or upper limits of two
 288 loops match exactly, for instance to satisfy the strict requirements
 289 of loop interchanging for non-tightly nested loops.
 290 A more sophisticated tool would notice the need for bumping automatically.
 291 An example is given under loop interchanging.
 292 .NH 2
 293 Loop Circulation
 294 .XS
 295 3.2 Loop Circulation
 296 .XE
 297 .LP
 298 Circulation is a generalization of loop interchanging;
 299 it is equivalent to interchanging a loop inside of (or outside of)
 300 multiple inner (outer) loops in a single step.
 301 For example, take the smoothing program:
 302 .Dx
 303   1: Entry
 304   1: real a(1:100,1:100,1:100)
 305   3: integer n
 306   5: for k = 2,n do
 307   7:  for i = 2,n do
 308   9:   for j = 2,n do
 309  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
 310 i,j)
 311   9:   endfor
 312   7:  endfor
 313   5: endfor
 314
 315 Parsed wave3a
 316  Browse  File   *Parse   Restor  System  Trans   Write   Msgs    Quit
 317 .Dy
 318 The outermost 'k' loop can be 'innermosted', or interchanged to the
 319 innermost position, or 'intercirculated' inside of the 'j' loop in
 320 one step by choosing the Circ menu item, then choosing the circulate
 321 inside of the 'j' loop:
 322 .Dx
 323   1: Entry
 324   1: real a(1:100,1:100,1:100)
 325   3: integer n
 326   7: for i = 2,n do
 327   9:  for j = 2,n do
 328   5:   for k = 2,n do
 329  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
 330 i,j)
 331   5:   endfor
 332   9:  endfor
 333   7: endfor
 334
 335 Intercirculating loop k inside of j
 336  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 337 .Dy
 338 In contrast, outercirculating the 'j' loop (of the original program)
 339 to the outermost position, in one step, would produce:
 340 .Dx
 341   1: Entry
 342   1: real a(1:100,1:100,1:100)
 343   3: integer n
 344   9: for j = 2,n do
 345   5:  for k = 2,n do
 346   7:   for i = 2,n do
 347  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
 348 i,j)
 349   7:   endfor
 350   5:  endfor
 351   9: endfor
 352
 353 Outercirculating loop j outside of k
 354  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 355 .Dy
 356 The data dependence tests for intercirculation and outercirculation
 357 are explained in two recent papers:
 358 Utpal Banerjee, "A Theory of Loop Permutations" (which appears
 359 in the Springer-Verlag monograph
 360 .ul
 361 Languages and Compilers for Parallel Computing,
 362 Gelernter, Nicolau and Padua (eds.), 1990) and
 363 Michael Wolfe, "Data Dependence and Program Restructuring"
 364 (to appear in
 365 .ul
 366 The Journal of Supercomputing
 367 in late 1990 or early 1991).
 368 After these transformations, dependence direction or distance vectors
 369 are modified to account for the new loop ordering.
 370 .br
 371 .ne 15
 372 .NH 2
 373 Loop Distribution
 374 .XS
 375 3.3 Loop Distribution
 376 .XE
 377 .LP
 378 Loop distribution is a well-known transformation which is often used
 379 to distribute an outer loop around non-tightly nested inner loops.
 380 As an example, we use a Cholesky decomposition program:
 381 .Dx
 382   1: Entry
 383   1: real a(1:100,1:100)
 384   1: real b(1:100)
 385   3: integer n
 386   5: for k = 1,n do
 387   7:  a(k,k) = sqrt(a(k,k))
 388   9:  for i = k+1,n do
 389  11:   a(i,k) = a(i,k)/a(k,k)
 390  13:   for j = k+1,i do
 391  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 392  13:   endfor
 393   9:  endfor
 394   5: endfor
 395
 396 Parsed ch
 397  Bump   Circ  *Dist   Inter  Neg    Par    Skew   Vec    Msgs   Quit   Xcape
 398 .Dy
 399 After distribution, the loop looks like:
 400 .Dx
 401   1: Entry
 402   1: real a(1:100,1:100)
 403   1: real b(1:100)
 404   3: integer n
 405   5: for k = 1,n do
 406   7:  a(k,k) = sqrt(a(k,k))
 407   9:  for i = k+1,n do
 408  11:   a(i,k) = a(i,k)/a(k,k)
 409   9:  endfor
 410   9:  for i = k+1,n do
 411  13:   for j = k+1,i do
 412  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 413  13:   endfor
 414   9:  endfor
 415   5: endfor
 416
 417 Distributing loop i
 418  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 419 .Dy
 420 The dependence test for loop distribution involves finding dependence cycles,
 421 and keeping all dependence cycles in a single distributed loop.
 422 .br
 423 .ne 15
 424 .NH 2
 425 Loop Interchanging
 426 .XS
 427 3.4 Loop Interchanging
 428 .XE
 429 .PP
 430 In \*t, choosing Interchanging will interchange the current loop
 431 with its immediate outer loop.
 432 Taking the distributed loops from the loop distribution example,
 433 we can move to the 'j' loop and interchange it with the 'i' loop to get:
 434 .Dx
 435   1: Entry
 436   1: real a(1:100,1:100)
 437   1: real b(1:100)
 438   3: integer n
 439   5: for k = 1,n do
 440   7:  a(k,k) = sqrt(a(k,k))
 441   9:  for i = k+1,n do
 442  11:   a(i,k) = a(i,k)/a(k,k)
 443   9:  endfor
 444  13:  for j = k+1,n do
 445   9:   for i = max(k+1,j),n do
 446  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 447   9:   endfor
 448  13:  endfor
 449   5: endfor
 450
 451 Interchanging loops i and j
 452  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 453 .Dy
 454 Note how the triangular loop limits have been modified;
 455 some future version of \*t will simplify the loop limits of the 'i'
 456 loop to be simply 'j,n', eliminating the 'max' when unnecessary.
 457 Loop interchanging is legal if there are no (<,>) dependence relations,
 458 and the dependence direction and distance vector elements for the
 459 interchanged loops are also interchanged.
 460 .PP
 461 Non-tightly nested loops can also be interchanged.
 462 For instance, we can take the above example (after interchanging
 463 the 'i' and 'j' loops) and choose to interchange the 'j' loop outwards.
 464 This produces the result:
 465 .Dx
 466   1: Entry
 467   1: real a(1:100,1:100)
 468   1: real b(1:100)
 469   3: integer n
 470  13: for j = 1,n do
 471   5:  for k = 1,j-1 do
 472   9:   for i = max(k+1,j),n do
 473  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 474   9:   endfor
 475   5:  endfor
 476   7:  a(j,j) = sqrt(a(j,j))
 477   9:  for i = j+1,n do
 478  11:   a(i,j) = a(i,j)/a(j,j)
 479   9:  endfor
 480  13: endfor
 481
 482 Interchanging loops k and j
 483  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 484 .Dy
 485 Note that lines 4 through 6 have been moved from above the inner loop
 486 to below the inner loop, and that the loop index 'k' has been replaced by 'j'.
 487 Currently, interchanging nontightly nested loops requires the loop limits
 488 to be perfectly square or triangular;
 489 while other loops limits could be handled by adding 'if' statements or
 490 adjusting the loop limits automatically, this current restriction
 491 sometimes requires 'bumping' a loop limit.
 492 For instance, suppose we take the original Cholesky decomposition
 493 and instead of distributing the 'i' loop, we interchange the 'i' loop
 494 outwards, producing:
 495 .Dx
 496   1: Entry
 497   1: real a(1:100,1:100)
 498   1: real b(1:100)
 499   3: integer n
 500   9: for i = 1,n do
 501   5:  for k = 1,i-1 do
 502  11:   a(i,k) = a(i,k)/a(k,k)
 503  13:   for j = k+1,i do
 504  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 505  13:   endfor
 506   5:  endfor
 507   7:  a(i,i) = sqrt(a(i,i))
 508   9: endfor
 509
 510 Interchanging loops k and i
 511  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 512 .Dy
 513 Now suppose we want to interchange the 'j' and 'k' loops.
 514 If we try to distribute the 'k' loop, we get the message:
 515 .Dx
 516
 517 Can't distribute
 518  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 519 .Dy
 520 since there is a dependence cycle involving lines 6 and 8.
 521 If we try to interchange the 'j' loop outwards, we get the message:
 522 .Dx
 523
 524 Imperfect loop interchanging requires square/triangular loops
 525  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 526 .Dy
 527 The loop limits can be made triangular by subtracting one from the 'j' loop
 528 limits (or adding one to the 'k' loop limits).
 529 We can choose to bump the 'j' loop limits by choosing the 'Bump' menu item
 530 at the 'j' loop:
 531 .Dx
 532   1: Entry
 533   1: real a(1:100,1:100)
 534   1: real b(1:100)
 535   3: integer n
 536   9: for i = 1,n do
 537   5:  for k = 1,i-1 do
 538  11:   a(i,k) = a(i,k)/a(k,k)
 539  13:   for j = k+1,i do
 540  15:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 541  13:   endfor
 542   5:  endfor
 543   7:  a(i,i) = sqrt(a(i,i))
 544   9: endfor
 545
 546 Imperfect loop interchanging requires square/triangular loops
 547 *Bump   Circ   Dist   Inter  Neg    Par    Skew   Vec    Msgs   Quit   Xcape
 548 .Dy
 549 \*t then asks what constant to add to the loop limits:
 550 .Dx
 551
 552 Interchanging loops k and i
 553 Bump by how much:
 554 .Dy
 555 We answer with '-1', which then produces the program:
 556 .Dx
 557   1: Entry
 558   1: real a(1:100,1:100)
 559   1: real b(1:100)
 560   3: integer n
 561   9: for i = 1,n do
 562   5:  for k = 1,i-1 do
 563  11:   a(i,k) = a(i,k)/a(k,k)
 564  13:   for j = k+1-1,i-1 do
 565  15:    a(i,j+1) = a(i,j+1)-a(i,k)*a(j+1,k)
 566  13:   endfor
 567   5:  endfor
 568   7:  a(i,i) = sqrt(a(i,i))
 569   9: endfor
 570
 571 Bump loop j by -1
 572  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 573 .Dy
 574 Notice that within the loop, 'j' is replaced by 'j+1';
 575 (also notice that no expression simplification is done).
 576 Now the two loops can be successfully interchanged:
 577 .Dx
 578   1: Entry
 579   1: real a(1:100,1:100)
 580   1: real b(1:100)
 581   3: integer n
 582   9: for i = 1,n do
 583  13:  for j = 1,i-1 do
 584  11:   a(i,j) = a(i,j)/a(j,j)
 585   5:   for k = 1,j do
 586  15:    a(i,j+1) = a(i,j+1)-a(i,k)*a(j+1,k)
 587   5:   endfor
 588  13:  endfor
 589   7:  a(i,i) = sqrt(a(i,i))
 590   9: endfor
 591
 592 Interchanging loops k and j
 593  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 594 .Dy
 595 .br
 596 .ne 15
 597 .NH 2
 598 Loop Negation
 599 .XS
 600 3.5 Loop Negation
 601 .XE
 602 .LP
 603 Loop negation (also called loop reversal) involves running the loop
 604 backward.
 605 \*t shows a negated loop by negating and switching
 606 the lower and upper limits of a loop, and negating the loop index within
 607 the body of the loop.
 608 Negating the 'j' loop in the first interchanging example gives:
 609 .Dx
 610   1: Entry
 611   1: real a(1:100,1:100)
 612   1: real b(1:100)
 613   3: integer n
 614   5: for k = 1,n do
 615   7:  a(k,k) = sqrt(a(k,k))
 616   9:  for i = k+1,n do
 617  11:   a(i,k) = a(i,k)/a(k,k)
 618   9:  endfor
 619  13:  for j = -n,-(k+1) do
 620   9:   for i = max(k+1,-j),n do
 621  15:    a(i,-j) = a(i,-j)-a(i,k)*a(-j,k)
 622   9:   endfor
 623  13:  endfor
 624   5: endfor
 625
 626 Negate loop j
 627  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 628 .Dy
 629 Loop negation is legal if the loop carries no dependence relations,
 630 and the dependence graph is modified to negate any dependence distance
 631 or directions.
 632 .NH 2
 633 Loop Parallelization
 634 .XS
 635 3.6 Loop Parallelization
 636 .XE
 637 .LP
 638 A loop can be parallelized as long as it carries no data dependence relations.
 639 Unlike other transformations, this cannot be 'Undone', nor will it
 640 show up in the 'Restore' display.
 641 In the previous example, the loops that can be parallelized are:
 642 .Dx
 643   1: Entry
 644   1: real a(1:100,1:100)
 645   1: real b(1:100)
 646   3: integer n
 647   5: for k = 1,n do
 648   7:  a(k,k) = sqrt(a(k,k))
 649   9:  doall i = k+1,n do
 650  11:   a(i,k) = a(i,k)/a(k,k)
 651   9:  endfor
 652  13:  doall j = -n,-(k+1) do
 653   9:   doall i = max(k+1,-j),n do
 654  15:    a(i,-j) = a(i,-j)-a(i,k)*a(-j,k)
 655   9:   endfor
 656  13:  endfor
 657   5: endfor
 658
 659 Parallelize loop i
 660  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 661 .Dy
 662 .NH 2
 663 Loop Skewing
 664 .XS
 665 3.7 Loop Skewing
 666 .XE
 667 .LP
 668 Forward (reverse) loop skewing involves adding (subtracting) an outer loop
 669 index to the lower and upper limits for an inner loop.
 670 Loop skewing is always legal, but modifies the direction and distance
 671 vectors by adding the outer loop elements to the inner loop element.
 672 Thus, a (<,=) direction is changed to a (<,<) direction;
 673 this means that after loop interchanging, the dependence relation
 674 will be carried by the outer loop, allowing parallel execution of the inner
 675 loop.
 676 This is useful in a smoothing algorithm, as in the circulation example.
 677 Forward skewing the inner 'j' loop with respect to the 'k' loop gives:
 678 .Dx
 679   1: Entry
 680   1: real a(1:100,1:100,1:100)
 681   3: integer n
 682   5: for k = 2,n do
 683   7:  for i = 2,n do
 684   9:   for j = 2+k,n+k do
 685  11:    a(k,i,j-k) = a(k,i-1,j-k)+a(k,i,j-k-1)+a(k,i,j-k+1)+a(k,i+1,j-k)+a(k-1,i
 686 ,j-k)+a(k+1,i,j-k)
 687   9:   endfor
 688   7:  endfor
 689   5: endfor
 690
 691 Forward skew loop j with respect to k
 692  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 693 .Dy
 694 Forward skewing the 'j' loop again with respect to the 'i' loop gives:
 695 .Dx
 696   1: Entry
 697   1: real a(1:100,1:100,1:100)
 698   3: integer n
 699   5: for k = 2,n do
 700   7:  for i = 2,n do
 701   9:   for j = 2+k+i,n+k+i do
 702  11:    a(k,i,j-i-k) = a(k,i-1,j-i-k)+a(k,i,j-i-k-1)+a(k,i,j-i-k+1)+a(k,i+1,j-i-
 703 k)+a(k-1,i,j-i-k)+a(k+1,i,j-i-k)
 704   9:   endfor
 705   7:  endfor
 706   5: endfor
 707
 708 Forward skew loop j with respect to i
 709  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 710 .Dy
 711 Now we see the advantage of loop skewing, by circulating
 712 the 'j' loop all the way outside:
 713 .Dx
 714   1: Entry
 715   1: real a(1:100,1:100,1:100)
 716   3: integer n
 717   9: for j = 2+2+2,n+n+n do
 718   5:  for k = max(2,j-(n+n)),min(n,j-(2+2)) do
 719   7:   for i = max(2,j-(n+k)),min(n,j-(2+k)) do
 720  11:    a(k,i,j-i-k) = a(k,i-1,j-i-k)+a(k,i,j-i-k-1)+a(k,i,j-i-k+1)+a(k,i+1,j-i-
 721 k)+a(k-1,i,j-i-k)+a(k+1,i,j-i-k)
 722   7:   endfor
 723   5:  endfor
 724   9: endfor
 725
 726 Outercirculating loop j outside of k
 727  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 728 .Dy
 729 And now we can parallelize the inner 'k' and 'i' loops:
 730 .Dx
 731   1: Entry
 732   1: real a(1:100,1:100,1:100)
 733   3: integer n
 734   9: for j = 2+2+2,n+n+n do
 735   5:  doall k = max(2,j-(n+n)),min(n,j-(2+2)) do
 736   7:   doall i = max(2,j-(n+k)),min(n,j-(2+k)) do
 737  11:    a(k,i,j-i-k) = a(k,i-1,j-i-k)+a(k,i,j-i-k-1)+a(k,i,j-i-k+1)+a(k,i+1,j-i-
 738 k)+a(k-1,i,j-i-k)+a(k+1,i,j-i-k)
 739   7:   endfor
 740   5:  endfor
 741   9: endfor
 742
 743 Parallelize loop i
 744  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 745 .Dy
 746 .NH 2
 747 Vectorization
 748 .XS
 749 3.8 Vectorization
 750 .XE
 751 .LP
 752 Vectorization is legal when there are no loop-carried dependence cycles
 753 in the inner loop.
 754 Vectorization in \*t works only for trivial cases, as it does not
 755 even recognize simple reduction operators;
 756 non-inner loops cannot be vectorized, though vectorization within
 757 an outer parallel loop is legal.
 758 Vectorization does not change the dependence graph at all.
 759 As an example, taking the program from the Skewing section, we can
 760 vectorize the inner loop to get:
 761 .Dx
 762   1: Entry
 763   1: real a(1:100,1:100,1:100)
 764   3: integer n
 765   9: for j = 2+2+2,n+n+n do
 766   5:  doall k = max(2,j-(n+n)),min(n,j-(2+2)) do
 767   7:   forall i = max(2,j-(n+k)),min(n,j-(2+k)) do
 768  11:    a(k,i,j-i-k) = a(k,i-1,j-i-k)+a(k,i,j-i-k-1)+a(k,i,j-i-k+1)+a(k,i+1,j-i-
 769 k)+a(k-1,i,j-i-k)+a(k+1,i,j-i-k)
 770   7:   endfor
 771   5:  endfor
 772   9: endfor
 773
 774 Parallelize loop i
 775  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
 776 .Dy
 777 .bp
 778 .NH 1
 779 \*t Language
 780 .XS
 781 4. \*t Language
 782 .XE
 783 .LP
 784 The \*t language is very simple.
 785 It comprises scalar and array variables,
 786 loops, assignments and block-structured IF statements.
 787 The language BNF is:
 788 .Dp
 789 program         ::= stlist
 790
 791 stlist          ::= statement [';' statement]...
 792
 793 statement       ::= integerdecl
 794                 ::= realdecl
 795                 ::= constdecl
 796                 ::= assignment
 797                 ::= loop
 798                 ::= if
 799
 800 .De
 801 .Dp
 802 constdecl       ::= 'const' constassignment [',' constassignment]...
 803
 804 constassignment ::= ID '=' expression
 805
 806 integerdecl     ::= 'integer' vardecllist
 807 realdecl        ::= 'real' vardecllist
 808
 809 vardecllist     ::= vardecl [',' vardecl]...
 810
 811 vardecl         ::= ID
 812                 ::= ID '(' [expression ':'] expression
 813                         [',' [expression ':'] expression]... ')'
 814
 815 .De
 816 .Dp
 817 assignment      ::= lhs '=' expression
 818
 819 lhs             ::= ID
 820                 ::= ID '(' expression [',' expression]... ')'
 821
 822 loop            ::= ['for' | 'doall']
 823                         ID '=' expression ['to' | ',' | ':'] expression
 824                         [ ['by' | ',' | ':'] expression]
 825                         'do' stlist 'endfor'
 826
 827 if              ::= 'if' expression 'then' stlist ['else' stlist] 'endif'
 828
 829 .De
 830 .Dp
 831 expression      ::= ID
 832                 ::= ID '(' expression [',' expression]... ')'
 833                 ::= INTCONST
 834                 ::= FLOATCONST
 835                 ::= expression '+' expression
 836                 ::= expression '-' expression
 837                 ::= expression '*' expression
 838                 ::= expression '/' expression
 839                 ::= expression '**' expression
 840                 ::= '-' expression
 841                 ::= '+' expression
 842                 ::= '(' expression ')'
 843                 ::= expression '<' expression
 844                 ::= expression '<=' expression
 845                 ::= expression '=' expression
 846                 ::= expression '<>' expression
 847                 ::= expression '>' expression
 848                 ::= expression '>=' expression
 849                 ::= expression 'mod' expression
 850                 ::= expression 'max' expression
 851                 ::= expression 'min' expression
 852                 ::= 'sqrt' '(' expression ')'
 853                 ::= 'floor' '(' expression '/' expression ')'
 854                 ::= 'ceiling' '(' expression '/' expression ')'
 855                 ::= 'max' '(' expression [',' expression]... ')'
 856                 ::= 'min' '(' expression [',' expression]... ')'
 857 .De
 858 .bp
 859 .NH 1
 860 Sample Session
 861 .XS
 862 5. Sample Session
 863 .XE
 864 .PP
 865 Start out by firing up \*t with the command line:
 866 .Dp
 867 % t
 868 .De
 869 \*t will return with the display:
 870 .Dx
 871
 872 Tiny Tool [as of December 1990]
 873 *Browse  File    Parse   Restor  System  Trans   Write   Msgs    Quit
 874 .Dy
 875 Go to the File menu by typing 'f', getting the list of files:
 876 .Dx
 877 /ogc1/staff/mwolfe/tiny
 878 Announcement  doc/          fix/          source/       test/
 879 dif           doc.log       make.out      t*            todo
 880
 881 Tiny Tool [as of December 1990]
 882 *Down    Edit    Newdir  Redo    Sh      Up      Msgs    Quit    Xcape
 883 .Dy
 884 To move to the 'test' subdirectory, choose 'Down' by typing 'd',
 885 getting the prompt:
 886 .Dx
 887
 888 Tiny Tool [as of December 1990]
 889 Directory:
 890 .Dy
 891 Respond by typing 'test', following by the return key;
 892 \*t then displays the files in the 'test' subdirectory:
 893 .Dx
 894 /ogc1/staff/mwolfe/tiny/test
 895 ave3       dd.4       doc2.log   lu         parenb     wave2
 896 ch         dd.t1      dynamic    ludecomp   rev        wave3
 897 dd.1       dd.t2      example.1  paren      rn1        wave3a
 898 dd.2       dd.t3      example.2  paren2     wave       wave3b
 899 dd.3       doc.log    example.3  parena     wave.8wa
 900
 901 Tiny Tool [as of December 1990]
 902 *Down    Edit    Newdir  Redo    Sh      Up      Msgs    Quit    Xcape
 903 .Dy
 904 To check the contents of a file, type 'E' to edit the file;
 905 \*t prompts for the file name, so a response of 'ch' gets:
 906 .Dx
 907 real a(100,100), b(100)
 908 integer n
 909 for k = 1 to n do
 910 a(k,k) = sqrt(a(k,k))
 911 for i = k+1 to n do
 912 a(i,k) = a(i,k)/a(k,k)
 913 for j = k+1 to i do
 914 a(i,j) = a(i,j)-a(i,k)*a(j,k)
 915 endfor
 916 endfor
 917 endfor
 918 ~
 919 ~
 920 "ch" 11 lines, 191 characters
 921 .Dy
 922 Exiting the editor returns to the same File menu.
 923 Return to the Main menu by typing the 'escape' key:
 924 .Dx
 925
 926 Tiny Tool [as of December 1990]
 927  Browse *File    Parse   Restor  System  Trans   Write   Msgs    Quit
 928 .Dy
 929 Notice that the default menu selection when returning from a submenu
 930 is left at the most recent choice;
 931 to enter the 'File' menu again, type 'return'.
 932 To parse one of those files, so type 'p':
 933 .Dx
 934
 935 Tiny Tool [as of December 1990]
 936 File:
 937 .Dy
 938 Respond with the file name 'decomp.cholesky', followed by 'return':
 939 .Dx
 940   1: Entry
 941   1: real a(1:100,1:100)
 942   1: real b(1:100)
 943   2: integer n
 944   3: for k = 1,n do
 945   4:  a(k,k) = sqrt(a(k,k))
 946   5:  for i = k+1,n do
 947   6:   a(i,k) = a(i,k)/a(k,k)
 948   7:   for j = k+1,i do
 949   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 950   7:   endfor
 951   5:  endfor
 952   3: endfor
 953
 954 Parsed ch
 955  Browse  File   *Parse   Restor  System  Trans   Write   Msgs    Quit
 956 .Dy
 957 To explore some interactive restructuring, go to
 958 the Browse menu by typing 'B':
 959 .Dx
 960   1: Entry
 961   1: real a(1:100,1:100)
 962   1: real b(1:100)
 963   2: integer n
 964   3: for k = 1,n do
 965   4:  a(k,k) = sqrt(a(k,k))
 966   5:  for i = k+1,n do
 967   6:   a(i,k) = a(i,k)/a(k,k)
 968   7:   for j = k+1,i do
 969   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 970   7:   endfor
 971   5:  endfor
 972   3: endfor
 973
 974 Parsed ch
 975 *Browse  DD      Loop    Restr   See     Undo    Var     Msgs    Quit    Xcape
 976 .Dy
 977 Notice that when entering a new menu, the default menu item is
 978 always the first choice, not necessarily the one most often chosen.
 979 Notice that in the Browse menu, there is always a current position
 980 in the file; initially the current position is the 'Entry' node, at the
 981 top of the file.
 982 To look at the data dependence relations in the program,
 983 enter the DD Browse Menu by typing 'D':
 984 .Dx
 985   1: Entry
 986   1: real a(1:100,1:100)
 987   1: real b(1:100)
 988   2: integer n
 989   3: for k = 1,n do
 990   4:  a(k,k) = sqrt(a(k,k))
 991   5:  for i = k+1,n do
 992   6:   a(i,k) = a(i,k)/a(k,k)
 993   7:   for j = k+1,i do
 994   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
 995   7:   endfor
 996   5:  endfor
 997   3: endfor
 998
 999 No DD successors.
1000 *Cycle  Goto   Next   Pred   Succ   Var    Write  Msgs   Quit   Xcape
1001 .Dy
1002 The message tells that the current position has no DD successors;
1003 this is not surprising since the current position is the Entry node.
1004 (Some future version of \*t may link upwardly-exposed uses to the Entry node.)
1005 Two ways to browse the DD graph are given.
1006 The most useful way is to cycle through all the dependences in the program
1007 by using the Cycle menu choice;
1008 this moves the current position to the next variable reference that has
1009 data dependence successors and displays that dependence relation on the
1010 message line.
1011 It will display each dependence successor from that variable reference, then
1012 move on to the next reference.
1013 Typing 'C' (or just return, since Cycle is the default menu item) gives the
1014 display:
1015 .Dx
1016   1: Entry
1017   1: real a(1:100,1:100)
1018   1: real b(1:100)
1019   2: integer n
1020   3: for k = 1,n do
1021   4:  a(k,k) = sqrt(a(k,k))
1022   5:  for i = k+1,n do
1023   6:   a(i,k) = a(i,k)/a(k,k)
1024   7:   for j = k+1,i do
1025   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1026   7:   endfor
1027   5:  endfor
1028   3: endfor
1029
1030 flow dependence 4: --> 6:(=)  (0)
1031 *Cycle  Goto   Next   Pred   Succ   Var    Write  Msgs   Quit   Xcape
1032 .Dy
1033 Notice the highlighting in lines 4 and 6 showing the variable
1034 references in question.
1035 The message line shows the kind of dependence (flow, anti, output),
1036 the line numbers involved, the direction vector and the distance
1037 vector (unknown directions or distances appear as "*").
1038 Typing 'C' again gives the next dependence relation:
1039 .Dx
1040   1: Entry
1041   1: real a(1:100,1:100)
1042   1: real b(1:100)
1043   2: integer n
1044   3: for k = 1,n do
1045   4:  a(k,k) = sqrt(a(k,k))
1046   5:  for i = k+1,n do
1047   6:   a(i,k) = a(i,k)/a(k,k)
1048   7:   for j = k+1,i do
1049   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1050   7:   endfor
1051   5:  endfor
1052   3: endfor
1053
1054 flow dependence 6: --> 8:(=,=)  (0,0)
1055 *Cycle  Goto   Next   Pred   Succ   Var    Write  Msgs   Quit   Xcape
1056 .Dy
1057 and so on.
1058 .PP
1059 The other method to browse the dependence relations interactively
1060 is to use the Var menu option to move the current position
1061 to the next variable reference.
1062 The first predecessor or successor of that variable reference may be
1063 displayed by using the Pred or Succ menu items, and Next will show
1064 the next predecessor or successor, as appropriate.
1065 Goto will move the current position to the dependence predecessor or
1066 successor reference shown on the message line.
1067 .PP
1068 In any case, all these messages are saved in the message buffer, and
1069 may be displayed by typing the 'M' key:
1070 .Dx
1071 Parsed ch
1072 No DD successors.
1073 flow dependence 4: --> 6:(=)  (0)
1074 flow dependence 6: --> 8:(=,=)  (0,0)
1075 flow dependence 6: --> 8:(=,<=)  (0,*)
1076 anti dependence 8: --> 4:(<)  (*)
1077 anti dependence 8: --> 6:(<,=)  (*,0)
1078 anti dependence 8: --> 8:(<,=,=)  (*,0,0)
1079 flow dependence 8: --> 4:(<)  (*)
1080 output dependence 8: --> 4:(<)  (*)
1081 flow dependence 8: --> 6:(<,=)  (*,0)
1082 flow dependence 8: --> 6:(<,<)  (*,*)
1083 output dependence 8: --> 6:(<,=)  (*,0)
1084 flow dependence 8: --> 8:(<,=,=)  (*,0,0)
1085 flow dependence 8: --> 8:(<,=,<)  (*,0,*)
1086 flow dependence 8: --> 8:(<,<=,<)  (*,*,*)
1087 output dependence 8: --> 8:(<,=,=)  (*,0,0)
1088 No DD successors.
1089
1090 No DD successors.
1091 *Xcape  Quit
1092 .Dy
1093 The dependence relations can all be written to a file by
1094 choosing the Write menu option;
1095 \*t prompts for the file to which to write the dependence information.
1096 The file for this program would look like:
1097 .Dp
1098 flow dependence:  4 -->  6      (=)  (0)        a(k,k) --> a(k,k)
1099 flow dependence:  6 -->  8      (=,=)  (0,0)    a(i,k) --> a(i,k)
1100 flow dependence:  6 -->  8      (=,<=)  (0,*)   a(i,k) --> a(j,k)
1101 anti dependence:  8 -->  4      (<)  (*)        a(i,j) --> a(k,k)
1102 anti dependence:  8 -->  6      (<,=)  (*,0)    a(i,j) --> a(i,k)
1103 anti dependence:  8 -->  8      (<,=,=)  (*,0,0)        a(i,j) --> a(i,j)
1104 flow dependence:  8 -->  4      (<)  (*)        a(i,j) --> a(k,k)
1105 output dependence:  8 -->  4    (<)  (*)        a(i,j) --> a(k,k)
1106 flow dependence:  8 -->  6      (<,=)  (*,0)    a(i,j) --> a(i,k)
1107 flow dependence:  8 -->  6      (<,<)  (*,*)    a(i,j) --> a(k,k)
1108 output dependence:  8 -->  6    (<,=)  (*,0)    a(i,j) --> a(i,k)
1109 flow dependence:  8 -->  8      (<,=,=)  (*,0,0)        a(i,j) --> a(i,j)
1110 flow dependence:  8 -->  8      (<,=,<)  (*,0,*)        a(i,j) --> a(i,k)
1111 flow dependence:  8 -->  8      (<,<=,<)  (*,*,*)       a(i,j) --> a(j,k)
1112 output dependence:  8 -->  8    (<,=,=)  (*,0,0)        a(i,j) --> a(i,j)
1113 .De
1114 .PP
1115 Now to do some transformations.
1116 Type 'X' from the DD Browse Menu to get to the Browse menu:
1117 .Dx
1118   1: Entry
1119   1: real a(1:100,1:100)
1120   1: real b(1:100)
1121   2: integer n
1122   3: for k = 1,n do
1123   4:  a(k,k) = sqrt(a(k,k))
1124   5:  for i = k+1,n do
1125   6:   a(i,k) = a(i,k)/a(k,k)
1126   7:   for j = k+1,i do
1127   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1128   7:   endfor
1129   5:  endfor
1130   3: endfor
1131
1132 No DD successors.
1133  Browse *DD      Loop    Restr   See     Undo    Var     Msgs    Quit    Xcape
1134 .Dy
1135 Currently the only transformations supported are loop transformations.
1136 To perform a loop transformation, move the current
1137 position to the loop to be transformed.
1138 Typing 'L' twice will move the current position from
1139 Entry to the first 'for' loop, then to the second 'for' loop:
1140 .Dx
1141   1: Entry
1142   1: real a(1:100,1:100)
1143   1: real b(1:100)
1144   2: integer n
1145   3: for k = 1,n do
1146   4:  a(k,k) = sqrt(a(k,k))
1147   5:  for i = k+1,n do
1148   6:   a(i,k) = a(i,k)/a(k,k)
1149   7:   for j = k+1,i do
1150   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1151   7:   endfor
1152   5:  endfor
1153   3: endfor
1154
1155 No DD successors.
1156  Browse  DD     *Loop    Restr   See     Undo    Var     Msgs    Quit    Xcape
1157 .Dy
1158 Choose the Restructure menu by typing 'R':
1159 .Dx
1160   1: Entry
1161   1: real a(1:100,1:100)
1162   1: real b(1:100)
1163   2: integer n
1164   3: for k = 1,n do
1165   4:  a(k,k) = sqrt(a(k,k))
1166   5:  for i = k+1,n do
1167   6:   a(i,k) = a(i,k)/a(k,k)
1168   7:   for j = k+1,i do
1169   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1170   7:   endfor
1171   5:  endfor
1172   3: endfor
1173
1174 No DD successors.
1175 *Bump   Circ   Dist   Inter  Neg    Par    Skew   Vec    Msgs   Quit   Xcape
1176 .Dy
1177 The choices are loop bumping,
1178 loop circulation (generalized loop interchanging for tightly nested loops),
1179 loop distribution,
1180 loop interchanging (for tightly or non-tightly nested loops),
1181 loop negation,
1182 loop parallelization,
1183 and loop skewing (along with the standard MQX menu choices).
1184 Distribute loop 'i' by typing 'D':
1185 .Dx
1186   1: Entry
1187   1: real a(1:100,1:100)
1188   1: real b(1:100)
1189   2: integer n
1190   3: for k = 1,n do
1191   4:  a(k,k) = sqrt(a(k,k))
1192   5:  for i = k+1,n do
1193   6:   a(i,k) = a(i,k)/a(k,k)
1194   5:  endfor
1195   5:  for i = k+1,n do
1196   7:   for j = k+1,i do
1197   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1198   7:   endfor
1199   5:  endfor
1200   3: endfor
1201
1202 Distributing loop i
1203  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1204 .Dy
1205 Now type 'L' to move to the 'j' loop, and go to the restructuring menu
1206 again:
1207 .Dx
1208   1: Entry
1209   1: real a(1:100,1:100)
1210   1: real b(1:100)
1211   2: integer n
1212   3: for k = 1,n do
1213   4:  a(k,k) = sqrt(a(k,k))
1214   5:  for i = k+1,n do
1215   6:   a(i,k) = a(i,k)/a(k,k)
1216   5:  endfor
1217   5:  for i = k+1,n do
1218   7:   for j = k+1,i do
1219   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1220   7:   endfor
1221   5:  endfor
1222   3: endfor
1223
1224 Distributing loop i
1225 *Bump   Circ   Dist   Inter  Neg    Par    Skew   Vec    Msgs   Quit   Xcape
1226 .Dy
1227 This time, let's see what happens when the 'j' loop is
1228 negated by typing 'N':
1229 .Dx
1230   1: Entry
1231   1: real a(1:100,1:100)
1232   1: real b(1:100)
1233   2: integer n
1234   3: for k = 1,n do
1235   4:  a(k,k) = sqrt(a(k,k))
1236   5:  for i = k+1,n do
1237   6:   a(i,k) = a(i,k)/a(k,k)
1238   5:  endfor
1239   5:  for i = k+1,n do
1240   7:   for j = -i,-(k+1) do
1241   8:    a(i,-j) = a(i,-j)-a(i,k)*a(-j,k)
1242   7:   endfor
1243   5:  endfor
1244   3: endfor
1245
1246 Negate loop j
1247  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1248 .Dy
1249 This negates and switches the loop limits, and negates
1250 the index variable inside the range of the loop.
1251 It also affects the dependence relations of the loop.
1252 But if this turns out to be uninteresting, and the original
1253 version of the program with the forward loop is desired.
1254 One could re-negate the loop, but it is simpler to undo the negation
1255 by typing 'U' for Undo:
1256 .Dx
1257   1: Entry
1258   1: real a(1:100,1:100)
1259   1: real b(1:100)
1260   2: integer n
1261   3: for k = 1,n do
1262   4:  a(k,k) = sqrt(a(k,k))
1263   5:  for i = k+1,n do
1264   6:   a(i,k) = a(i,k)/a(k,k)
1265   5:  endfor
1266   5:  for i = k+1,n do
1267   7:   for j = k+1,i do
1268   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1269   7:   endfor
1270   5:  endfor
1271   3: endfor
1272
1273 Negate loop j
1274  Browse  DD      Loop    Restr   See    *Undo    Var     Msgs    Quit    Xcape
1275 .Dy
1276 Notice that the current position is moved back to the Entry node.
1277 Again move to the 'j' loop (typing 'L') and go to the
1278 Restructure menu, choosing instead the Intchg (interchange) menu item.
1279 This interchanges the 'i' and 'j' loops:
1280 .Dx
1281   1: Entry
1282   1: real a(1:100,1:100)
1283   1: real b(1:100)
1284   2: integer n
1285   3: for k = 1,n do
1286   4:  a(k,k) = sqrt(a(k,k))
1287   5:  for i = k+1,n do
1288   6:   a(i,k) = a(i,k)/a(k,k)
1289   5:  endfor
1290   7:  for j = k+1,n do
1291   5:   for i = max(k+1,j),n do
1292   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1293   5:   endfor
1294   7:  endfor
1295   3: endfor
1296
1297 Interchanging loops i and j
1298  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1299 .Dy
1300 Parallelize the j loop by going to the Restructure menu
1301 and typing P for Parallelize, giving:
1302 .Dx
1303   1: Entry
1304   1: real a(1:100,1:100)
1305   1: real b(1:100)
1306   2: integer n
1307   3: for k = 1,n do
1308   4:  a(k,k) = sqrt(a(k,k))
1309   5:  for i = k+1,n do
1310   6:   a(i,k) = a(i,k)/a(k,k)
1311   5:  endfor
1312   7:  doall j = k+1,n do
1313   5:   for i = max(k+1,j),n do
1314   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
1315   5:   endfor
1316   7:  endfor
1317   3: endfor
1318
1319 Parallelize loop j
1320  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1321 .Dy
1322 Now type X to escape to the main menu, and type W to write this version
1323 of the program to a file.
1324 The file will contain the program:
1325 .Dp
1326 real a(1:100,1:100)
1327 real b(1:100)
1328 integer n
1329 for k = 1,n do
1330 a(k,k) = sqrt(a(k,k))
1331 for i = k+1,n do
1332 a(i,k) = a(i,k)/a(k,k)
1333 endfor
1334 doall j = k+1,n do
1335 for i = max(k+1,j),n do
1336 a(i,j) = a(i,j)-a(i,k)*a(j,k)
1337 endfor
1338 endfor
1339 endfor
1340 .De
1341 To work with the wave program,
1342 type 'P' at the main menu (to parse a new program) and
1343 type 'wave' in response to the prompt for the filename.
1344 The new program is displayed:
1345 .Dx
1346   1: Entry
1347   1: real a(1:100,1:100)
1348   3: integer n
1349   5: for k = 1,100 do
1350   7:  for i = 2,n-1 do
1351   9:   for j = 2,n-1 do
1352  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1353   9:   endfor
1354   7:  endfor
1355   5: endfor
1356
1357 Parsed wave
1358  Browse  File   *Parse   Restor  System  Trans   Write   Msgs    Quit
1359 .Dy
1360 To try to parallelize the 'j' loop,
1361 enter the 'Browse' menu (by typing 'b') and move to the 'j' loop by
1362 using the 'L' key:
1363 .Dx
1364   1: Entry
1365   1: real a(1:100,1:100)
1366   3: integer n
1367   5: for k = 1,100 do
1368   7:  for i = 2,n-1 do
1369   9:   for j = 2,n-1 do
1370  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1371   9:   endfor
1372   7:  endfor
1373   5: endfor
1374
1375 Parsed wave
1376  Browse  DD     *Loop    Restr   See     Undo    Var     Msgs    Quit    Xcape
1377 .Dy
1378 Parallelize the 'j' loop by typing 'R' and choosing the Parallelize
1379 menu item:
1380 .Dx
1381   1: Entry
1382   1: real a(1:100,1:100)
1383   3: integer n
1384   5: for k = 1,100 do
1385   7:  for i = 2,n-1 do
1386   9:   for j = 2,n-1 do
1387  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1388   9:   endfor
1389   7:  endfor
1390   5: endfor
1391
1392 Parsed wave
1393  Bump   Circ   Dist   Inter  Neg   *Par    Skew   Vec    Msgs   Quit   Xcape
1394 .Dy
1395 Unfortunately, parallel execution of the 'j' loop would be illegal;
1396 \*t responds by telling about the offending
1397 data dependence relations:
1398 .Dx
1399   1: Entry
1400   1: real a(1:100,1:100)
1401   3: integer n
1402   5: for k = 1,100 do
1403   7:  for i = 2,n-1 do
1404   9:   for j = 2,n-1 do
1405  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1406   9:   endfor
1407   7:  endfor
1408   5: endfor
1409
1410 flow dependence 11: --> 11:(<=,=,<)  (*,0,1)
1411 *Accept    Next      Override  Msgs      Quit      Xcape
1412 .Dy
1413 From this menu, you can accept the facts of life, or look at the next
1414 dependence relation, or override all these dependence relations
1415 (perform the transformation anyway).
1416 Typing 'N' to see the next dependence relation gives:
1417 .Dx
1418   1: Entry
1419   1: real a(1:100,1:100)
1420   3: integer n
1421   5: for k = 1,100 do
1422   7:  for i = 2,n-1 do
1423   9:   for j = 2,n-1 do
1424  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1425   9:   endfor
1426   7:  endfor
1427   5: endfor
1428
1429 anti dependence 11: --> 11:(<=,=,<)  (*,0,1)
1430  Accept   *Next      Override  Msgs      Quit      Xcape
1431 .Dy
1432 Any transformation which would violate a data dependence relation
1433 gets to this menu;
1434 typing 'A' to accept these relations (or 'x' to escape)
1435 returns to the restructuring menu, without performing the transformation:
1436 .Dx
1437   1: Entry
1438   1: real a(1:100,1:100)
1439   3: integer n
1440   5: for k = 1,100 do
1441   7:  for i = 2,n-1 do
1442   9:   for j = 2,n-1 do
1443  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1444   9:   endfor
1445   7:  endfor
1446   5: endfor
1447
1448 Data Dependence prevents loop parallelization
1449  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1450 .Dy
1451 In order to run one of 'i' or 'j' in parallel, since they both
1452 carry dependence relations, one of the loops must be skewed.
1453 Move to the 'j' loop and enter the restructuring menu again:
1454 .Dx
1455   1: Entry
1456   1: real a(1:100,1:100)
1457   3: integer n
1458   5: for k = 1,100 do
1459   7:  for i = 2,n-1 do
1460   9:   for j = 2,n-1 do
1461  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1462   9:   endfor
1463   7:  endfor
1464   5: endfor
1465
1466 Data Dependence prevents loop parallelization
1467  Bump   Circ   Dist   Inter  Neg    Par   *Skew   Vec    Msgs   Quit   Xcape
1468 .Dy
1469 Choose 'Skew', to get to the skew menu.
1470 Loop skewing with respect to outer loops is always legal;
1471 this menu allows me to choose the loop with respect to which to
1472 skew, though the skewing factor is always one:
1473 .Dx
1474   1: Entry
1475   1: real a(1:100,1:100)
1476   3: integer n
1477   5: for k = 1,100 do
1478   7:  for i = 2,n-1 do
1479   9:   for j = 2,n-1 do
1480  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
1481   9:   endfor
1482   7:  endfor
1483   5: endfor
1484
1485 Data Dependence prevents loop parallelization
1486  Out       *Forward    Reverse    By_Factor  Msgs       Quit       Xcape
1487 .Dy
1488 Choosing 'Out' here moves the marker to the next outer loop; choosing
1489 'Forward' or 'Reverse' chooses forward (+1 factor) or reverse
1490 (-1 factor )skewing with respect to the marked loop;
1491 choosing By_Factor will skew by any constant integer factor.
1492 To choose forward skewing with respect to the 'i' loop, type 'f':
1493 .Dx
1494   1: Entry
1495   1: real a(1:100,1:100)
1496   3: integer n
1497   5: for k = 1,100 do
1498   7:  for i = 2,n-1 do
1499   9:   for j = 2+i,n-1+i do
1500  11:    a(i,j-i) = (a(i-1,j-i)+a(i,j-i-1)+a(i+1,j-i)+a(i,j-i+1))/4
1501   9:   endfor
1502   7:  endfor
1503   5: endfor
1504
1505 Forward skew loop j with respect to i
1506  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1507 .Dy
1508 Forward loop skewing simply adds the outer loop index to the lower and upper
1509 limit expressions (adds 'i' to the limits of 'j'), and subtracts
1510 the outer loop index from the inner loop index within the body of the loop.
1511 The other effect is on the data dependence relations, changing
1512 a (<,=) to a (<,<).
1513 Now, interchanging the 'j' and 'i' loops gives:
1514 .Dx
1515   1: Entry
1516   1: real a(1:100,1:100)
1517   3: integer n
1518   5: for k = 1,100 do
1519   9:  for j = 2+2,n-1+(n-1) do
1520   7:   for i = max(2,j-(n-1)),min(n-1,j-2) do
1521  11:    a(i,j-i) = (a(i-1,j-i)+a(i,j-i-1)+a(i+1,j-i)+a(i,j-i+1))/4
1522   7:   endfor
1523   9:  endfor
1524   5: endfor
1525
1526 Interchanging loops i and j
1527  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1528 .Dy
1529 This is the 'wavefront' formulation of the loop.
1530 Now, parallelizing the 'i' loop is legal:
1531 .Dx
1532   1: Entry
1533   1: real a(1:100,1:100)
1534   3: integer n
1535   5: for k = 1,100 do
1536   9:  for j = 2+2,n-1+(n-1) do
1537   7:   doall i = max(2,j-(n-1)),min(n-1,j-2) do
1538  11:    a(i,j-i) = (a(i-1,j-i)+a(i,j-i-1)+a(i+1,j-i)+a(i,j-i+1))/4
1539   7:   endfor
1540   9:  endfor
1541   5: endfor
1542
1543 Parallelize loop i
1544  Browse  DD      Loop   *Restr   See     Undo    Var     Msgs    Quit    Xcape
1545 .Dy
1546 This version of the program can be written to a file
1547 by escaping to the main menu and choosing 'Write'.
1548 .bp
1549 .NH 1
1550 Menu Descriptions
1551 .XS
1552 6. Menu Descriptions
1553 .XE
1554 .PP
1555 The various menus are described here.
1556 The main menu is first, and the remaining menus are listed
1557 alphabetically.
1558 The menus, along with their parentage, are:
1559 .IP Main  14
1560 from command line
1561 .IP AutoParallel
1562 from System menu
1563 .IP Browse
1564 from Main Menu
1565 .IP Browse:Browse
1566 from Browse Menu
1567 .IP Circulate
1568 from Restructure Menu
1569 .IP "DD Browse"
1570 from Browse Menu
1571 .IP "DD Algorithm"
1572 from System Menu
1573 .IP "DD Prevents"
1574 from restructuring transformation
1575 .IP File
1576 from Main Menu
1577 .IP Find
1578 from See or Step Menu
1579 .IP Msgs
1580 from any menu
1581 .IP Redo
1582 from File Menu
1583 .IP Restore
1584 from Main Menu
1585 .IP Restructure
1586 from Browse Menu
1587 .IP See
1588 from Browse Menu
1589 .IP Skew
1590 from Restructure Menu
1591 .IP Step
1592 from Browse:Browse Menu
1593 .IP System
1594 from Main Menu
1595 .IP Trans
1596 from Main Menu
1597 .sp 2
1598 .LP
1599 A pictorial diagram of the menu lineage is:
1600 .Dp
1601 Main
1602   |
1603   +--- Browse
1604   |       +--- Browse:Browse
1605   |       |          +--- Step
1606   |       +--- DD
1607   |       |
1608   |       +--- Restructure
1609   |       |          +--- Circulate
1610   |       |          +--- Skew
1611   |       +--- See
1612   |
1613   +--- File
1614   |       +--- Redo
1615   |
1616   +--- Restore
1617   |
1618   +--- System
1619   |       +--- AutoParallel
1620   |       +--- DDAlg
1621   |
1622   +--- Trans
1623 .De
1624 .LP
1625 Again, typing 'M' at any menu will get to the Msgs menu, displaying
1626 recent messages from \*t;
1627 typing 'Q' from any menu will quit \*t immediately;
1628 typing 'X' (or the escape key)
1629 from any menu except the Main menu will exit (escape) to the parent menu.
1630 .br
1631 .NH 2
1632 Main Menu
1633 .XS
1634 6.1 Main Menu
1635 .XE
1636 .LP
1637 .Dx
1638
1639 Tiny Tool [as of December 1990]
1640 *Browse  File    Parse   Restor  System  Trans   Write   Msgs    Quit
1641 .Dy
1642 .PP
1643 From the main menu, there are the following eight choices:
1644 .IP Browse 10
1645 Go to the Browse menu to create new program version via
1646 interactive restructuring or to browse the data structures.
1647 .IP File
1648 Go to the File menu to move around directories, edit files,
1649 start command shells, etc.
1650 .IP Parse
1651 Choose an initial file (if no file was given on the command line)
1652 or choose a different file to parse and then browse.
1653 \*t will ask for the file name to parse.
1654 .IP Restor
1655 Go to the Restore menu to restore an old program version.
1656 .IP System
1657 Go to the System menu to change dependence decision algorithm
1658 or verify data structures.
1659 .IP Trans
1660 Go to the Translate menu to change the display language, or
1661 to write out an assembler file.
1662 .IP Write
1663 Write the current program version to a file;
1664 \*t will ask for the name of the file to write.
1665 .IP Msgs
1666 Go to the Msgs menu and display the most recent messages.
1667 .IP Quit
1668 Quit \*t.
1669 .bp
1670 .NH 2
1671 AutoParallel Menu
1672 .XS
1673 6.2 AutoParallel Menu
1674 .XE
1675 .LP
1676 This menu lets you decide whether or not \*t should attempt to
1677 parallelize every loop after each transformation.
1678 This is a simple way to see how your transformations have affected the
1679 parallelism in the program.
1680 Initially this option is disabled;
1681 you can enter this menu from the System menu.
1682 .Dx
1683
1684 Tiny Tool [as of December 1990]
1685 *AutoParallel    NoAutoParallel  Msgs            Quit            Xcape
1686 .Dy
1687 .IP AutoParallel 10
1688 Enable automatic parallelization.
1689 .IP NoAutoParallel
1690 Disable automatic parallelization.
1691 .br
1692 .bp
1693 .NH 2
1694 Browse Menu
1695 .XS
1696 6.3 Browse Menu
1697 .XE
1698 .LP
1699 This is the menu where you will probably spend lots of time.
1700 When you enter the Browse Menu, \*t highlights a 'current position'
1701 in the program.
1702 This will generally be a loop or a variable reference.
1703 When you first enter this mode, the current position will be
1704 at the entry.
1705 .Dx
1706   1: Entry
1707   1: real a(1:100,1:100,1:100)
1708   3: integer n
1709   5: for k = 2,n do
1710   7:  for i = 2,n do
1711   9:   for j = 2,n do
1712  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
1713 i,j)
1714   9:   endfor
1715   7:  endfor
1716   5: endfor
1717
1718 Parsed wave3a
1719 *Browse  DD      Loop    Restr   See     Undo    Var     Msgs    Quit    Xcape
1720 .Dy
1721 From this menu you can browse around the data structures,
1722 move the current position to another loop or variable,
1723 and perform or undo restructuring transformations.
1724 .IP Browse 10
1725 Go to the Browse:Browse menu (all right, it's a stupid name).
1726 .IP DD
1727 Go to the DD Browse Menu to examine dependence relations.
1728 .IP Loop
1729 Move the current position to the next loop.
1730 .IP Restr
1731 Go to the Restructure Menu, to perform a restructuring transformation
1732 on this loop; the current position must be a loop.
1733 .IP See
1734 Traverse the abstract syntax tree (AST) data structure interactively,
1735 by going to the See menu.
1736 .IP Undo
1737 Undo the most recent restructuring transformation.
1738 See the discussion under 'Restore Menu' to see how this is implemented.
1739 .IP Var
1740 Move the current position to the next variable reference.
1741 Note that due to the data structure for assignments, the right
1742 hand side expressions are visited 'before' the left hand side.
1743 .bp
1744 .NH 2
1745 Browse:Browse Menu
1746 .XS
1747 6.4 Browse:Browse Menu
1748 .XE
1749 .LP
1750 This is a simple way to traverse the abstract syntax tree (AST)
1751 in detail, by moving to sibling, parent or child tree nodes one at a time.
1752 As in the Browse menu, the current position is highlighted.
1753 .Dx
1754   1: Entry
1755   1: real a(1:100,1:100,1:100)
1756   3: integer n
1757   5: for k = 2,n do
1758   7:  for i = 2,n do
1759   9:   for j = 2,n do
1760  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
1761 i,j)
1762   9:   endfor
1763   7:  endfor
1764   5: endfor
1765
1766 Parsed wave3a
1767 *Back  Decl  Jump  Loop  Next  Step  Var   Msgs  Quit  Xcap
1768 .Dy
1769 The various menu choices move the current position around:
1770 .IP Back 10
1771 Move the current position to the last position.
1772 .IP Decl
1773 If the current position is on a variable reference, move the current
1774 position to the declaration of that variable.
1775 .IP Jump
1776 Move to the next non-trivial operator or variable reference.
1777 .IP Loop
1778 Move the current position to the next loop.
1779 .IP Next
1780 If the current position is on a variable reference, move the current
1781 position to the next reference of that variable.
1782 .IP Step
1783 Go to the Step Menu.
1784 .IP Var
1785 Move the current position to the next variable reference.
1786 .bp
1787 .NH 2
1788 Circulate Menu
1789 .XS
1790 6.5 Circulate Menu
1791 .XE
1792 .LP
1793 When you want to circulate a loop ordering, this menu
1794 allows you to choose what type of circulation you want.
1795 Intercirculation is a circulation of the current loop to a position
1796 inside of some inner loop;
1797 outercirculation is a circulation of the current loop to a position
1798 outside of some enclosing loop.
1799 The Circulate Menu display highlights the loop inside or outside
1800 of which the current loop can be circulated.
1801 The Out menu choice highlights the next possible choice, and
1802 the Circulate menu choice enables circulation to inside of or outside
1803 of the highlighted loop.
1804 .Dx
1805   1: Entry
1806   1: real a(1:100,1:100,1:100)
1807   3: integer n
1808   5: for k = 2,n do
1809   7:  for i = 2,n do
1810   9:   for j = 2,n do
1811  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
1812 i,j)
1813   9:   endfor
1814   7:  endfor
1815   5: endfor
1816
1817 Parsed wave3a
1818 *Circulate  Out        Msgs       Quit       Xcape
1819 .Dy
1820 .IP Circulate 10
1821 attempt to circulate the current loop inside of or outside of
1822 the highlighted loop.
1823 .IP Out
1824 move the highlight to the next tightly-nested outer loop.
1825 .bp
1826 .NH 2
1827 DD Browse Menu
1828 .XS
1829 6.6 DD Browse Menu
1830 .XE
1831 .LP
1832 At this menu you can inspect the data dependence relations in the program.
1833 .Dx
1834   1: Entry
1835   1: real a(1:100,1:100,1:100)
1836   3: integer n
1837   5: for k = 2,n do
1838   7:  for i = 2,n do
1839   9:   for j = 2,n do
1840  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
1841 i,j)
1842   9:   endfor
1843   7:  endfor
1844   5: endfor
1845
1846 No DD successors.
1847 *Cycle  Goto   Next   Pred   Succ   Var    Write  Msgs   Quit   Xcape
1848 .Dy
1849 The message line will display the first dependence relation from the
1850 current position; if there are no dependence relations (as, for instance,
1851 for non-variable reference nodes) then this will also be displayed.
1852 The kind of dependence, line numbers, direction vector and distance
1853 vector are displayed; direction or distance vector elements which are unknown
1854 are displayed as asterisks.
1855 By default, this will display dependence successors of the current node,
1856 and both source and target of the dependence relation are highlighted.
1857 .IP Cycle 10
1858 perhaps the most useful menu choice, this cycles through all the
1859 dependence relations in the program, moving the current position
1860 as necessary.
1861 .IP Goto
1862 move the current position to the 'other end' of the dependence relation
1863 being displayed.
1864 .IP Next
1865 display the next dependence successor or predecessor of the current node.
1866 .IP Pred
1867 display dependence predecessors of the current node.
1868 .IP Succ
1869 display dependence successors of the current node.
1870 .IP Var
1871 move the current position to the next variable reference.
1872 .IP Write
1873 prompts for a file name, and write the dependence relations to that file.
1874 .bp
1875 .NH 2
1876 DD Algorithm Menu
1877 .XS
1878 6.7 DD Algorithm Menu
1879 .XE
1880 .LP
1881 This menu lets the user choose what decision algorithm to use to
1882 solve the subscript dependence equation.
1883 This option will not take effect until the next program is
1884 parsed (using the Parse item from the Main Menu).
1885 .Dx
1886
1887 *Simple  Triang  GGCD    Lambda  Power   Msgs    Quit    Xcape
1888 .Dy
1889 .IP Simple 10
1890 Use a simple set of tests, including an exact test when only a single
1891 loop index variable appears in a subscript (to get dependence distances),
1892 and the GCD and simple Banerjee's Inequalities otherwise (to get
1893 dependence directions).
1894 These tests are applied subscript-by-subscript.
1895 .IP Triang
1896 As above, except use triangular Banerjee's Inequalities instead of
1897 the simple Inequalities.
1898 .IP GGCD
1899 Use Banerjee's Generalized GCD simultaneous subscript test;
1900 this gives dependence distances if fixed.
1901 .IP Lambda
1902 Use an implementation of the Lambda Test (see Li, Yew and Zhu's paper
1903 "Data Dependence Analysis on Multi-Dimensional Array References"
1904 in the 1989 ACM Int'l Conf. on Supercomputing proceedings, or
1905 Grunwald's paper
1906 "Data Dependence Analysis: The Lambda Test Revisited"
1907 in the 1990 Int'l Conf. on Parallel Processing proceedings).
1908 .IP Power
1909 Use Banerjee's Generalized GCD test, extended by a different
1910 search for an empty solution space by modified Fourier-Motzgin search.
1911 .bp
1912 .NH 2
1913 DD Prevents Menu
1914 .XS
1915 6.8 DD Prevents Menu
1916 .XE
1917 .LP
1918 When data dependence relations prevent application of a restructuring
1919 transformation, those dependence relations are displayed.
1920 The user can view all the relations (using the Next menu option),
1921 Accept the restriction, or Override the dependence relations.
1922 Note: Choosing Override will blindly apply the transformation;
1923 the modified dependence graph after the transformation will probably
1924 no longer be valid.
1925 In the example shown, the user tried to parallelize the 'k' loop.
1926 Since the 'k' loop carries a dependence relation (actually, two dependence
1927 relations), parallel execution is not allowed.
1928 .Dx
1929   1: Entry
1930   1: real a(1:100,1:100,1:100)
1931   3: integer n
1932   5: for k = 2,n do
1933   7:  for i = 2,n do
1934   9:   for j = 2,n do
1935  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
1936 i,j)
1937   9:   endfor
1938   7:  endfor
1939   5: endfor
1940
1941 flow dependence 11: --> 11:(=,=,<)  (0,0,1)
1942 *Accept    Next      Override  Msgs      Quit      Xcape
1943 .Dy
1944 .IP Accept 10
1945 accept this dependence restriction; do not apply the transformation.
1946 .IP Next
1947 display the next data dependence relations that prevents this dependence.
1948 .IP Override
1949 override the dependence restrictions and apply the transformation anyway.
1950 .bp
1951 .NH 2
1952 File Menu
1953 .XS
1954 6.9 File Menu
1955 .XE
1956 .LP
1957 The file menu appears with a listing of the file names in the
1958 current directory.
1959 Subdirectory names are shown with a '/', and executable file
1960 names are shown with a '*', much as the command 'ls\ -F' does;
1961 the current directory name is shown at the top of the file listing:
1962 .Dx
1963 /ogc1/staff/mwolfe/tiny/test
1964 ave3        dd.t1       doc.wave    example.3   parenb      wave3
1965 ch          dd.t2       doc2.log    lu          rev         wave3a
1966 dd.1        dd.t3       doc3.log    ludecomp    rn1         wave3b
1967 dd.2        doc.ch      dynamic     paren       wave
1968 dd.3        doc.ddfile  example.1   paren2      wave.8wa
1969 dd.4        doc.log     example.2   parena      wave2
1970
1971 Data Dependence prevents loop parallelization
1972 *Down    Edit    Newdir  Redo    Sh      Up      Msgs    Quit    Xcape
1973 .Dy
1974 .IP Down 10
1975 Move down to a subdirectory; \*t will prompt for the subdirectory
1976 name to which to change.
1977 Currently the whole subdirectory name must be typed.
1978 .IP Edit
1979 Edit a file; currently, the editor to use is hard-coded in \*t as 'vi'.
1980 .IP Newdir
1981 Make a new directory; \*t will prompt for the name of the subdirectory
1982 name to create.
1983 .IP Redo
1984 Go to the Redo (Restart) menu, from which stopped subprocesses
1985 can be restarted.
1986 Currently, the only processes that can be stopped are editor subprocesses.
1987 .IP Sh
1988 Start up a command shell; currently, the shell to use is
1989 hard-coded in \*t as 'csh'.
1990 .IP Up
1991 Move Up to the parent menu (a la 'cd ..').
1992 .IP Msgs
1993 Go to the Message display and menu.
1994 .IP Quit
1995 Quit \*t.
1996 .IP Xcape
1997 Return to the Main Menu.
1998 .bp
1999 .NH 2
2000 Find Menu
2001 .XS
2002 6.10 Find Menu
2003 .XE
2004 .LP
2005 From the See or Step Menu, this menu moves the current position to the
2006 next operator of the specified type:
2007 .Dx
2008   1: Entry
2009   1: real a(1:100,1:100)
2010   3: integer n
2011   5: for k = 1,100 do
2012   7:  for i = 2,n-1 do
2013   9:   for j = 2,n-1 do
2014  11:    a(i,j) = (a(i-1,j)+a(i,j-1)+a(i+1,j)+a(i,j+1))/4
2015   9:   endfor
2016   7:  endfor
2017   5: endfor
2018
2019 Parsed wave
2020 *Asgn   Entry  Index  Loop   Oper   Var    Msgs   Quit   Xcap
2021 .Dy
2022 .IP Asgn 10
2023 move the current position to the next assignment operator.
2024 .IP Entry
2025 move the current position to the entry node.
2026 .IP Index
2027 move the current position to the next loop index reference.
2028 .IP Loop
2029 move the current position to the next loop.
2030 .IP Oper
2031 move the current position to the next operator.
2032 .IP Var
2033 move the current position to the next variable reference.
2034 .bp
2035 .NH 2
2036 Redo Menu
2037 .XS
2038 6.11 Redo Menu
2039 .XE
2040 .LP
2041 A list of stopped processes is given.
2042 .Dx
2043     3a16 [0] edit ch
2044     3a28 [1] edit ave3
2045
2046 spawned process 3a28 edit ave3 can be restarted
2047 *Start  Msgs   Quit   Xcape
2048 .Dy
2049 Any one process can be restarted by choosing the menu item Start,
2050 and typing the number (0-9, in square brackets) corresponding
2051 to that process.
2052 Currently only 9 stopped processes are saved, and only
2053 editor processes may be stopped.
2054 .IP Start 10
2055 Start one of the stopped processes.
2056 .bp
2057 .NH 2
2058 Restore Menu
2059 .XS
2060 6.12 Restore Menu
2061 .XE
2062 .LP
2063 This interface is all new since the last version.
2064 When you restructure programs, or parse new programs, as long as you
2065 do not quit \*t, the data structures for each version of each program is saved.
2066 Using the Restore Menu, you can return to any previously parsed or
2067 restructured version of a program in this \*t session.
2068 The Restore display shows the chain of restructuring transformations
2069 taken to get to the 'current' version of the program:
2070 .Dx
2071 File: wave3a
2072  Original Program
2073   Skew loop j with respect to i
2074    Skew loop j with respect to k
2075     Circulate loop j outside of loop k
2076
2077 Outercirculating loop j outside of k
2078 *Child   Parent  Next    Prev    Msgs    Quit    Xcape
2079 .Dy
2080 This display says that the original program was read from
2081 file 'wave3a', then skewed the 'j' loop with respect to 'i' and 'k', then
2082 circulated (interchanged) the 'j' loop to outside the 'k' loop.
2083 To return to a previous version, choose Parent from the menu,
2084 which will effectively 'undo' the bottom transformation;
2085 this is exactly how the 'Undo' menu item in the Browse Menu is implemented.
2086 That transformation can be effectively reapplied by choosing 'Child'
2087 from the menu.
2088 If there are 'children' programs or derived programs from the current
2089 one, they are displayed with number identifiers:
2090 .Dx
2091 File: wave3a
2092  Original Program
2093   Skew loop j with respect to i
2094    Skew loop j with respect to k
2095     0: Circulate loop j outside of loop k
2096
2097 Outercirculating loop j outside of k
2098  Child  *Parent  Next    Prev    Msgs    Quit    Xcape
2099 .Dy
2100 Choosing Child will cause Tiny to ask which child you want,
2101 and you are expected to respond with a digit, 0 through 9.
2102 .IP Child 10
2103 Choose a child version of the program as the current version,
2104 effectively 'reapplying' a transformation.
2105 .IP Parent
2106 Choose the parent version of the program as the current version,
2107 effectively 'undoing' a transformation.
2108 .IP Next
2109 Choose the next version of the program, essentially the next child
2110 of the parent.
2111 For a top-level program, this goes to a 'later-parsed' program.
2112 .IP Prev
2113 Choose the previous version of the program, essentially the previous child
2114 of the parent.
2115 For a top-level program, this goes to an 'earlier-parsed' program.
2116 .bp
2117 .NH 2
2118 Restructure Menu
2119 .XS
2120 6.13 Restructure Menu
2121 .XE
2122 .LP
2123 Here you choose one of several restructuring transformations
2124 to perform on the current loop.
2125 The current position must be a loop.
2126 .Dx
2127   1: Entry
2128   1: real a(1:100,1:100)
2129   1: real b(1:100)
2130   2: integer n
2131   3: for k = 1,n do
2132   4:  a(k,k) = sqrt(a(k,k))
2133   5:  for i = k+1,n do
2134   6:   a(i,k) = a(i,k)/a(k,k)
2135   7:   for j = k+1,i do
2136   8:    a(i,j) = a(i,j)-a(i,k)*a(j,k)
2137   7:   endfor
2138   5:  endfor
2139   3: endfor
2140
2141 Parsed ch
2142 *Bump   Circ   Dist   Inter  Neg    Par    Skew   Vec    Msgs   Quit   Xcape
2143 .Dy
2144 Most transformations have dependence tests which must be satisfied for
2145 the transformation to be legal.
2146 They also may modify the dependence relations, such as changing
2147 the dependence direction or distance.
2148 The restructuring transformations allowed are:
2149 .IP Bump 10
2150 bump a loop by adding a signed integer constant to both lower and upper limits.
2151 .IP Circ
2152 circulate the current loop inside or outside of a nest of tightly-nested loops.
2153 .IP Dist
2154 distribute the current loop.
2155 .IP Inter
2156 interchange the current loop with its immediately surrounding tightly
2157 nested surrounding loop.
2158 .IP Neg
2159 negate (reverse) the current loop.
2160 .IP Par
2161 parallelize the current loop.
2162 .IP Skew
2163 skew the current loop with respect to an outer loop.
2164 .IP Vec
2165 vectorize the current loop, if it is an inner loop and has
2166 no dependence cycles (change to a 'forall').
2167 .LP
2168 Transformations in the works are loop rotation, tiling and vectorization.
2169 .bp
2170 .NH 2
2171 See Menu
2172 .XS
2173 6.14 See Menu
2174 .XE
2175 .LP
2176 This allows you to see a 'binary dump' of each abstract syntax tree
2177 node, and to move around the AST:
2178 .Dx
2179 [   50150,  4]
2180 fetch, array a
2181 value:    50578 (329080)
2182 extra:        0        0 (0 0)
2183 wpos:  420
2184                500a8
2185           +----------+
2186         0 |    50150 |        0
2187           +----------+
2188          /     50118
2189         0
2190   5:  endfor
2191
2192 Parsed ch
2193  Down *Find  Goto  Left  Mark  Rght  Up    Msgs  Quit  Xcap
2194 .Dy
2195 The binary dump includes the hexadecimal address of the node, with
2196 its line number (in square brackets), the node operator,
2197 its value in hex and decimal, the extra nodes and window position,
2198 and graphical display of the parent, child, sibling and link
2199 relationships.
2200 The menu choices are the same as for the Step Menu.
2201 .IP Down 10
2202 Move the current position to its first child.
2203 .IP Find
2204 Go to the Find Menu, to move the current position
2205 to the next operator of a particular type.
2206 .IP Goto
2207 Move the current position to one of the 26 previously marked positions.
2208 .IP Left
2209 Move the current position to its left sibling.
2210 .IP Mark
2211 Mark the current position as one of 26 saved positions;
2212 \*t will prompt for a single-letter position name, [a-z].
2213 .IP Rght
2214 Move the current position to its right sibling.
2215 .IP Up
2216 Move the current position to its parent.
2217 .bp
2218 .NH 2
2219 Skew Menu
2220 .XS
2221 6.15 Skew Menu
2222 .XE
2223 .LP
2224 When you want to skew a loop, this menu
2225 allows you to choose what type of skewing (forward or reverse)
2226 and the loop with respect to which you want to skew.
2227 Forward skewing means skewing with a factor of +1, and reverse
2228 skewing is with a factor of -1.
2229 The Circulate Menu display highlights the outer loop with respect to which
2230 the skewing will be done.
2231 The Out menu choice highlights the next possible choice, and
2232 the Forward or Reverse menu choice enables the appropriate kind of skewing.
2233 .Dx
2234   1: Entry
2235   1: real a(1:100,1:100,1:100)
2236   3: integer n
2237   5: for k = 2,n do
2238   7:  for i = 2,n do
2239   9:   for j = 2,n do
2240  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
2241 i,j)
2242   9:   endfor
2243   7:  endfor
2244   5: endfor
2245
2246 No saved program in that direction
2247 *Out        Forward    Reverse    By_Factor  Msgs       Quit       Xcape
2248 .Dy
2249 .IP Out 10
2250 Move the highlight to the next outer loop.
2251 .IP Forward
2252 Enable loop skewing by factor of +1.
2253 .IP Reverse
2254 Enable loop skewing by factor of -1.
2255 .IP By_Factor
2256 Prompts for a (optionally signed) constant integer skewing factor;
2257 enables skewing by that factor.
2258 .bp
2259 .NH 2
2260 Step Menu
2261 .XS
2262 6.16 Step Menu
2263 .XE
2264 .LP
2265 This is reached from the Browse:Browse Menu, and allows detailed traversal of
2266 the data structures.
2267 .Dx
2268   1: Entry
2269   1: real a(1:100,1:100,1:100)
2270   3: integer n
2271   5: for k = 2,n do
2272   7:  for i = 2,n do
2273   9:   for j = 2,n do
2274  11:    a(k,i,j) = a(k,i-1,j)+a(k,i,j-1)+a(k,i,j+1)+a(k,i+1,j)+a(k-1,i,j)+a(k+1,
2275 i,j)
2276   9:   endfor
2277   7:  endfor
2278   5: endfor
2279
2280 No saved program in that direction
2281 *Down  Find  Goto  Left  Mark  Rght  Up    Msgs  Quit  Xcap
2282 .Dy
2283 .IP Down 10
2284 Move the current position to its first child.
2285 .IP Find
2286 Go to the Find Menu, to move the current position
2287 to the next operator of a particular type.
2288 .IP Goto
2289 Move the current position to one of the 26 previously marked positions.
2290 .IP Left
2291 Move the current position to its left sibling.
2292 .IP Mark
2293 Mark the current position as one of 26 saved positions;
2294 \*t will prompt for a single-letter position name, [a-z].
2295 .IP Rght
2296 Move the current position to its right sibling.
2297 .IP Up
2298 Move the current position to its parent.
2299 .bp
2300 .NH 2
2301 System Menu
2302 .XS
2303 6.17 System Menu
2304 .XE
2305 .LP
2306 The system menu lets the user change certain special options.
2307 .Dx
2308
2309 *Auto    DDalg   File    Output  Struc   Verify  Write   Msgs    Quit    Xcape
2310 .Dy
2311 .IP Auto 10
2312 Go to the AutoParallel Menu to decide whether or not to autoparallelize
2313 every loop after each transformation.
2314 .IP DDalg
2315 Go to the DD Algorithm Menu to change the DD decision algorithm.
2316 .IP File
2317 Prompts for a file name, then reopens 'debug' as that file.
2318 .IP Output
2319 Reopens 'debug' as standard output.
2320 .IP Struc
2321 Dump the abstract syntax tree (AST) data structure to the current 'debug' file.
2322 .IP Verify
2323 Verifies that the abstract syntax tree (AST) has no bogus pointers.
2324 The verifier reports any data structure inconsistencies.
2325 This is useful when debugging new transformations.
2326 .IP Write
2327 Writes the program to the current 'debug' file.
2328 This is useful when 'debug' is another file.
2329 .bp
2330 .NH 2
2331 Trans Menu
2332 .XS
2333 6.18 Trans Menu
2334 .XE
2335 .LP
2336 This menu lets you choose to view the program in a Fortran syntax
2337 as opposed to \*t syntax, or to compile the program
2338 into Alliant assembler code.
2339 .Dx
2340
2341 *Fortran  Tiny     Asm      Quit     Xcape
2342 .Dy
2343 .IP Fortran 10
2344 This option lets you view the program using Fortran syntax for loops.
2345 You may have to type ^L (control-L) to get the Fortran to show up.
2346 Here, Alliant directives are used to show parallel and vector loops.
2347 If Fortran is chosen, then when the program is written out, it will also
2348 use Fortran syntax.
2349 Note that Tiny does NOT have a Fortran parser, so it will not accept this
2350 syntax as input.
2351 Also note that the output may need modifications to be compiled and executed,
2352 since the Tiny language has no procedure header statements and the like.
2353 .IP Tiny
2354 This option lets you view the program in the default Tiny syntax.
2355 .IP Asm
2356 This option will "compile" the program, as it has been transformed,
2357 into Alliant FX/8 assembler code.
2358 .bp
2359 .NH 1
2360 AST Dump Information
2361 .XS
2362 7. AST Dump Information
2363 .XE
2364 .LP
2365 A sample 'dump' is given here.
2366 For the program:
2367 .Dp
2368 real a(10,10)
2369 for i = 1 to 10 do
2370  for j = 2 to 10 do
2371   a(i,j) = a(i,j-1) + 1
2372  endfor
2373 endfor
2374 .De
2375 the interactive display is:
2376 .Dx
2377   1: Entry
2378   1: real a(1:10,1:10)
2379   2: for i = 1,10 do
2380   3:  for j = 2,10 do
2381   4:   a(i,j) = a(i,j-1)+1
2382   3:  endfor
2383   2: endfor
2384
2385
2386 Parsed a1
2387  Auto    DDalg   File    Output *>Struc<   Verify  Write   Msgs    Quit    Xcape
2388 .Dy
2389 The dump (to the 'debug' file, whether it be opened to standard output,
2390 the default, or to a file) would be:
2391 .sp 2
2392 .nf
2393 .ft L
2394  .[   35424]        0=Child,    353f0=Next, entry
2395  .                  0=Parnt,        0=Prev,        0=Val
2396  .[   353f0]    353bc=Child,    3521c=Next, declare
2397  .                  0=Parnt,    35424=Prev,    21404=Val
2398  ..[   353bc]    35388=Child,    35320=Next, bounds
2399  ..              353f0=Parnt,        0=Prev,        0=Val
2400  ...[   35388]        0=Child,    35354=Next, constant
2401  ...              353bc=Parnt,        0=Prev,        1=Val
2402  ...[   35354]        0=Child,        0=Next, constant
2403  ...              353bc=Parnt,    35388=Prev,        a=Val
2404  ..[   35320]    352ec=Child,        0=Next, bounds
2405  ..              353f0=Parnt,    353bc=Prev,        0=Val
2406  ...[   352ec]        0=Child,    352b8=Next, constant
2407  ...              35320=Parnt,        0=Prev,        1=Val
2408  ...[   352b8]        0=Child,        0=Next, constant
2409  ...              35320=Parnt,    352ec=Prev,        a=Val
2410  .[   3521c]    351e8=Child,        0=Next, do
2411  .                  0=Parnt,    353f0=Prev,        1=Val
2412  ..[   351e8]    3514c=Child,    35284=Next, dolimit
2413  ..              3521c=Parnt,        0=Prev,    21444=Val
2414  ...[   3514c]    35118=Child,        0=Next, do
2415  ...              351e8=Parnt,        0=Prev,        2=Val
2416  ....[   35118]    34edc=Child,    351b4=Next, dolimit
2417  ....              3514c=Parnt,        0=Prev,    21484=Val
2418  .....[   34edc]    34ea8=Child,    34e40=Next, stmtnumber
2419  .....              35118=Parnt,        0=Prev,        1=Val
2420  ......[   34ea8]        0=Child,    34e74=Next, index
2421  ......              34edc=Parnt,        0=Prev,    351e8=Val
2422  ......[   34e74]        0=Child,        0=Next, index
2423  ......              34edc=Parnt,    34ea8=Prev,    35118=Val
2424  .....[   34e40]    34f10=Child,        0=Next, assign
2425  .....              35118=Parnt,    34edc=Prev,        0=Val
2426  ......[   34f10]    35048=Child,    350e4=Next, add
2427  ......              34e40=Parnt,        0=Prev,        0=Val
2428  .......[   35048]    35014=Child,    34f44=Next, fetch_array
2429  .......              34f10=Parnt,        0=Prev,    353f0=Val
2430  ........[   35014]        0=Child,    34f78=Next, index
2431  ........              35048=Parnt,        0=Prev,    351e8=Val
2432  ........[   34f78]    34fe0=Child,        0=Next, subtract
2433  ........              35048=Parnt,    35014=Prev,        0=Val
2434  .........[   34fe0]        0=Child,    34fac=Next, index
2435  .........              34f78=Parnt,        0=Prev,    35118=Val
2436  .........[   34fac]        0=Child,        0=Next, constant
2437  .........              34f78=Parnt,    34fe0=Prev,        1=Val
2438  .......[   34f44]        0=Child,        0=Next, constant
2439  .......              34f10=Parnt,    35048=Prev,        1=Val
2440  ......[   350e4]    350b0=Child,        0=Next, store
2441  ......              34e40=Parnt,    34f10=Prev,    353f0=Val
2442  .......[   350b0]        0=Child,    3507c=Next, index
2443  .......              350e4=Parnt,        0=Prev,    351e8=Val
2444  .......[   3507c]        0=Child,        0=Next, index
2445  .......              350e4=Parnt,    350b0=Prev,    35118=Val
2446  ....[   351b4]        0=Child,    35180=Next, constant
2447  ....              3514c=Parnt,    35118=Prev,        2=Val
2448  ....[   35180]        0=Child,        0=Next, constant
2449  ....              3514c=Parnt,    351b4=Prev,        a=Val
2450  ..[   35284]        0=Child,    35250=Next, constant
2451  ..              3521c=Parnt,    351e8=Prev,        1=Val
2452  ..[   35250]        0=Child,        0=Next, constant
2453  ..              3521c=Parnt,    35284=Prev,        a=Val
2454 .ft P
2455 .fi
2456 .sp 2
2457 The number in brackets is the hexadecimal address of that AST entry.
2458 The Child, Next, Parnt and Prev numbers are the hexadecimal addresses
2459 of the AST entries pointed to by the Child, Next, Parent and Previous pointers.
2460 The Node Operator is given in text, and the Value is given is hex.
2461 .bp
2462 .NH 1
2463 Installation and Distribution
2464 .XS
2465 8. Installation and Distribution
2466 .XE
2467 .LP
2468 \*t was designed to be relatively portable, but it's pretty rough;
2469 in many cases, a choice between elegance, portability and simplicity
2470 was made in favor of ease of implementation.
2471 It has been installed on many a Unix system using native compilers
2472 and the Gnu 'gcc', and on an IBM PC-clone using the Turbo C++ compiler.
2473 The entire design and implementation is geared toward supporting
2474 a research effort into elementary program restructuring, not toward
2475 developing an industrial-strength product.
2476 It is written in ANSI 'C' (bleah), with special hooks to be able
2477 to compile it on compilers without ANSI function headers
2478 (just about the only ANSI C features used).
2479 \*t uses a character-based interface, using the 'Curses' character windowing
2480 package to manage the screen (bleah) under Unix, and uses
2481 the Turbo C screen addressing routines on a PC.
2482 I would like to install \*t on an X-window interface, but
2483 that awaits some other interested graduate student.
2484 .PP
2485 In the best of cases, a simple 'make t' do all the compiles and links.
2486 Some modifications may be necessary.
2487 .PP
2488 I will gladly accept bug reports, suggestions or enhancements, but
2489 I cannot promise that anything will get fixed, except that I'll do my best,
2490 given the time and resources at my command.
2491 .PP
2492 The source or object code of
2493 \*t may be freely redistributed and reused as you see fit.
2494 Have fun.
2495 .bp
2496 .Nr
2497 .PX