chris@mimsy.UUCP (Chris Torek) (07/26/89)
>>In article <24CB9E07.9547@marob.masa.com> cowan@marob.masa.com (John Cowan) wrote: >>>Ufcawss, if you talk to the people who wrote VMS C, they'll tell you that >>>all one-pass implementations of C are unacceptable! (This has something to >>>do with generating good code for the 'switch' statement.) >In article <18729@mimsy.UUCP> I (Chris Torek) answered: >>They are both right and wrong. One-pass code generation means there >>are few opportunities for optimsiation; but generating good switches >>is easy. Simply emit a branch at the top of the switch, code at each >>of the labels, a branch at the bottom, and then generate the code >>that actually implements the switch. E.g., given >> >> [Clever example deleted] Now in article <686@ftp.COM> wjr@ftp.COM (Bill Rust) writes: >... two ways to implement switches: jump tables and compare and execute >when equal. Jump tables (ie jmp switch_list[ix] where ix is some easy >transformation of the switch variable) are much more efficient when >the range of values that the switch variable can assume is limited (ie >switch variable in range of 1 to 20 and it assumes 75% of values). The >only way to tell if a jump table is better than compare and jump is to >see what the range of the switch variable is and how many values it >actually assumes. So far so good. >This is very difficult to do in a one pass compiler. Competely wrong. See text above and example in <18729@mimsy.UUCP>, and see below. >The previous correspondent completely ignored this in his response. False. ``Simply emit a branch at the top of the switch, code at each of the labels, a branch at the bottom, and then generate the code that actually implements the switch.'' Since the code that implements the switch is not generated until after all the cases are known, the compiler can select one of the various alternatives. (Incidentally, heap switches are better for sparse tables above a moderate number of comparisons. PCC has used all three of these forms---direct, heap, and jump table switches---for years, and PCC is a one-pass compiler.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
dave@motto.UUCP (dave brown) (07/27/89)
In article <18735@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >Since the code that implements the switch is not generated until after >all the cases are known, the compiler can select one of the various >alternatives. (Incidentally, heap switches are better for sparse >tables above a moderate number of comparisons. PCC has used all three >of these forms---direct, heap, and jump table switches---for years, and >PCC is a one-pass compiler.) I understand direct and jump table switches, but what's a heap switch? ----------------------------------------------------------------------------- | David C. Brown | uunet!mnetor!motto!dave | | Motorola Canada, Ltd. | 416-499-1441 ext 3708 | | Communications Division | Disclaimer: Motorola is a very big company | -----------------------------------------------------------------------------
chris@mimsy.UUCP (Chris Torek) (07/27/89)
>In article <18735@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >>... PCC has used ... direct, heap, and jump table switches ... In article <67@motto.UUCP> dave@motto.UUCP (dave brown) writes: >I understand direct and jump table switches, but what's a heap switch? This might be PCC's private name for it; everyone else seems to call it a binary switch. Basically, if you have a complete, sorted binary tree, you can start at the root, compare, branch to case if equal, branch to `must be on the right' if >, handle left subtree, branch to default, generate label for `must be on the right', handle right subtree. Having a complete binary tree (which is a condition for heaps) means shorter code paths. A plain binary tree will work, but if it is unbalanced you will end up doing more comparisons than necessary. (`Complete' means that if you number the nodes like this: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 that the `holes' are at the bottom right, in the highest numbered slots; this means there is a compact array representation for the tree. A tree can be balanced without being complete, but not vice versa.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
gwyn@smoke.BRL.MIL (Doug Gwyn) (07/29/89)
In article <18764@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >In article <67@motto.UUCP> dave@motto.UUCP (dave brown) writes: >>I understand direct and jump table switches, but what's a heap switch? >This might be PCC's private name for it; everyone else seems to call >it a binary switch. ... Maybe it would help to explain that one of the several meanings for the term "heap" is a data structure that in effect implements a binary tree, usually as an array. So far as I can tell, most compilers that support this form of code generation actually generate individual test instructions, using branches to construct the binary tree, rather than using an explicit heap data structure.