greg@utcsri.UUCP (Gregory Smith) (04/16/86)
In article <708@bentley.UUCP> kwh@bentley.UUCP (KW Heuer) writes: >In article <2516@utcsri.UUCP> utcsri!greg (Gregory Smith) writes: >>What it should do next is .., call itself recursively to sort the shortest >>list. It should then *loop back* to sort the longest list (if it is more >>than one item). Thus a stack frame is saved while sorting the longer one. > >A good optimizer should compile tail-recursion into a jump anyway. (But >there are few good optimizers by that standard.) This intrigues me... I would not have expected an optimizer to catch this sort of thing, and would be interested in hearing details of any that do. The salient parts of my code were: func(a,b){ do{ foo bar; a = aa; b = bb; }while( cond ); } The 'recursive version' is: func( a,b ){ foo bar; if( cond ) func(aa,bb); } The following is equivalent, and *might* be easier to catch, but shouldn't be if proper control-flow analysis is done: func(a,b){ foo bar; if(!cond) return; func(aa,bb); } /* any comments? */ Does anybody end up with the do-while jump after compiling ( and optimizing ) one of the recursive ones? I tried a few variations and it didn't happen. ( 4.2 BSD vax 11/780 ). This reminds me of one of the commonest 'tricks' in assembler - instead of CALL X/RET, you write JMP X and then hopefully apologize in the comments. Of course X must not be expecting any stack context. One of the DEC libraries I was using to write pdp11 code had a macro CALLR X which was just JMP X ! I once wrote a CRT driver in Z80 code - if I hadn't used this trick, it would have used about 10 levels of stack - with this trick, the maximum was 2 ( This was significant - there was ..very.. little RAM available :-) ). -- "If you aren't making any mistakes, you aren't doing anything". ---------------------------------------------------------------------- Greg Smith University of Toronto UUCP: ..utzoo!utcsri!greg
cg@myrias.UUCP (Chris Gray) (04/16/86)
When I was playing around with a compiler (not a C compiler) for CP/M-80 I included the following peephole optimization: call x => jmp x ret Of course it was only done if the call wasn't preceded by a PUSH. Unfortunately, some of the built-in constructs which required run-time support had arguments that were pushed onto the stack at some indeterminate time in the past. I put in some kludges to handle them (flushing the peephole after the call), but there were still problems. In the end the amount of kludging to get it right outweighed the benefits, so I just ripped out the optimization. This is a much simpler case than recognizing tail recursion, but it does illustrate some of the things compiler writers will try to do. Chris Gray (ihnp4!alberta!myrias!cg)