1 | I realised while we were talking today about the correctness of switch removal |
---|

2 | that we don't deal properly with cost labels. Our costs basically assume that |
---|

3 | the switch takes a constant amount of time to compute, then we have a cost |
---|

4 | label on each branch. This is roughly consistent with using a jump table, but |
---|

5 | our switch removal does not take a constant amount of time to reach the |
---|

6 | branch. 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 | |
---|

16 | to |
---|

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 | |
---|

26 | with "break;" being transformed into "goto lb;". (Other variants are |
---|

27 | possible, but are likely to have similar problems.) |
---|

28 | |
---|

29 | The cost labelling attaches a cost label to each si, but the transformed |
---|

30 | program will not enjoy the properties that we want: each branch is supposed to |
---|

31 | be followed by a cost label, yet each failure case here is not. |
---|

32 | |
---|

33 | One (hacky) way to fix this might be to have the semantics of switch generate |
---|

34 | cost labels for each case passed by. Another (currently infeasible) way would |
---|

35 | be to have a dependent cost label at the top. One that doesn't quite work is |
---|

36 | to push the cost of getting to the branch into the cost label added in that |
---|

37 | branch. Unfortunately, falling through from the previous case will hit the |
---|

38 | cost label, leading to imprecision. |
---|

39 | |
---|

40 | The prototype cheats by transforming away switches into if-then-else trees and |
---|

41 | gotos before adding the cost labels. |
---|

42 | |
---|

43 | [Sep 5th:] |
---|

44 | |
---|

45 | Claudio points out that their proposal to handle pipelining can also be used |
---|

46 | to solve this: instead of just summing costs independently attached to labels |
---|

47 | you take into account the recent history of cost labels (so that the cost |
---|

48 | can vary on where you came from as an approximation of the possible pipeline |
---|

49 | states). Then for switches you take the cost for each branch's cost label |
---|

50 | to depend on whether the previous cost label was another branch or the cost |
---|

51 | label covering the switch (when you also include the jump cost). |
---|