source: etc/campbell/dev-notes/2012-07-03-switch-costs.txt

Last change on this file was 2394, checked in by campbell, 7 years ago

I've kept the odd note on bits of CerCo? work I've been doing. James suggested
that it might be useful if these were recorded in the repository just in case
they contain some useful information that doesn't get recorded elsewhere.

File size: 2.0 KB
Line 
1I realised while we were talking today about the correctness of switch removal
2that we don't deal properly with cost labels.  Our costs basically assume that
3the switch takes a constant amount of time to compute, then we have a cost
4label on each branch.  This is roughly consistent with using a jump table, but
5our switch removal does not take a constant amount of time to reach the
6branch.  Instead, it does something like
7
8  switch(e) {
9  case i1 : s1;
10  case i2 : s2;
11  ...
12  case in : sn;
13  default : sd;
14  }
15 
16to
17
18  tmp = e;
19  if (tmp == i1) { s1; goto l2; }
20  if (tmp == i2) { l2: s2; goto l3; }
21  ...
22  if (tmp == in) { ln: sn; goto ld; }
23  ld: sd;
24  lb: skip;
25 
26with "break;" being transformed into "goto lb;".  (Other variants are
27possible, but are likely to have similar problems.)
28
29The cost labelling attaches a cost label to each si, but the transformed
30program will not enjoy the properties that we want: each branch is supposed to
31be followed by a cost label, yet each failure case here is not.
32
33One (hacky) way to fix this might be to have the semantics of switch generate
34cost labels for each case passed by.  Another (currently infeasible) way would
35be to have a dependent cost label at the top.  One that doesn't quite work is
36to push the cost of getting to the branch into the cost label added in that
37branch.  Unfortunately, falling through from the previous case will hit the
38cost label, leading to imprecision.
39
40The prototype cheats by transforming away switches into if-then-else trees and
41gotos before adding the cost labels.
42
43[Sep 5th:]
44
45Claudio points out that their proposal to handle pipelining can also be used
46to solve this: instead of just summing costs independently attached to labels
47you take into account the recent history of cost labels (so that the cost
48can vary on where you came from as an approximation of the possible pipeline
49states).  Then for switches you take the cost for each branch's cost label
50to depend on whether the previous cost label was another branch or the cost
51label covering the switch (when you also include the jump cost).
Note: See TracBrowser for help on using the repository browser.