Jump to content
Jamie

Boost C 6.95 Recursion Bug

Recommended Posts

I was experimenting to see how the compiler handled recursion, and wrote the following simple problem:

 

#include <system.h>

unsigned char recur(unsigned char r, unsigned char x)
{
if(r > 0)
{
	return recur (r-1, x+x) + x;
}
else
{
	return x;
}
}

void main()
{
unsigned char c = recur(3, 1);
}

 

This should give the value '15', but gives the value '32', consistent across all optimization levels as far as I can tell.

Generated code (default optimization) is as follows:

;/////////////////////////////////////////////////////////////////////////////////
;// Code Generator: BoostC Compiler - http://www.sourceboost.com
;// Version	   : 6.95
;// License Type  : Full License
;// Limitations   : PIC12,PIC16 max code size:Unlimited, max RAM banks:Unlimited, Non commercial use only
;/////////////////////////////////////////////////////////////////////////////////

ORG 0x00000000
0000  281F	  GOTO	_startup
ORG 0x00000004
0004		recur_00000
0004	   ; { recur; function begin
0004  0821	  MOVF recur_00000_arg_r, W
0005  3C00	  SUBLW 0x00
0006  1803	  BTFSC STATUS,C
0007  2812	  GOTO	label1
0008  0321	  DECF recur_00000_arg_r, W
0009  00A1	  MOVWF recur_00000_arg_r
000A  0822	  MOVF recur_00000_arg_x, W
000B  0722	  ADDWF recur_00000_arg_x, W
000C  00A2	  MOVWF recur_00000_arg_x
000D  2004	  CALL recur_00000
000E  0822	  MOVF recur_00000_arg_x, W
000F  0723	  ADDWF CompTempVarRet579, W
0010  00A3	  MOVWF CompTempVarRet579
0011  0008	  RETURN
0012		label1
0012  0822	  MOVF recur_00000_arg_x, W
0013  00A3	  MOVWF CompTempVarRet579
0014  0008	  RETURN
0015	   ; } recur function end

ORG 0x00000015
0015		main
0015	   ; { main; function begin
0015  3003	  MOVLW 0x03
0016  1283	  BCF STATUS, RP0
0017  1303	  BCF STATUS, RP1
0018  00A1	  MOVWF recur_00000_arg_r
0019  3001	  MOVLW 0x01
001A  00A2	  MOVWF recur_00000_arg_x
001B  2004	  CALL recur_00000
001C  0823	  MOVF CompTempVarRet579, W
001D  00A0	  MOVWF main_1_c
001E  0008	  RETURN
001F	   ; } main function end

ORG 0x0000001F
001F		_startup
001F  118A	  BCF PCLATH,3
0020  120A	  BCF PCLATH,4
0021  2815	  GOTO	main

Not sure if this is even intended to be supported or not.

Thanks!

-

Jamie

Share this post


Link to post
Share on other sites

Hi Jamie,

 

SourceBoost C does not support reentant functions. Probably because arguments are not passed on the very small stack that the PIC provides. A software stack could be used I suppose but you would need to declare a block of RAM large enough to cope with the worst case recursion you would be expecting.

 

I think there should be a note in the manual stating that reentrant functions are not supported and/or some way for the compiler to detect recursion and throw up an error message.

 

Cheers

 

Reynard

Share this post


Link to post
Share on other sites

Jamie,

I was experimenting to see how the compiler handled recursion, and wrote the following simple problem:

...

Recursion will work but strange things may happen if you use function arguments and local variables as these will be modified on reentry as the same software stack locations are used (the software stack is static). It maybe that your code correctly handles the reentrency issues, so creating an error during the project build for this condition may not desirable.

 

Regards

Dave

Share this post


Link to post
Share on other sites

I think any recursion with Boost C is high risk. Unless the user studies the generated assembler code in detail for compiler created temp variables etc. it should be avoided. What may work with one version of Boost C may not work with a future version due to changed in code generation.

 

If not an error message then a warning that you have recursion in your program that may cause unpredictable results. Assuming it is not already there that is.

 

Cheers

 

Reynard

Share this post


Link to post
Share on other sites
Jamie,
I was experimenting to see how the compiler handled recursion, and wrote the following simple problem:

...

Recursion will work but strange things may happen if you use function arguments and local variables as these will be modified on reentry as the same software stack locations are used (the software stack is static). It maybe that your code correctly handles the reentrency issues, so creating an error during the project build for this condition may not desirable.

 

Regards

Dave

Hi Dave, I was seeing if you did anything special to handle recursion because of the nature of the static stack :unsure:.

 

You should be able to identify the bad cases by analysis. It's useful to analyze recursion to identify potential return stack overflow too. I would second Reynard's request to give a warning (do you have a #pragma to turn on/off warnings?)

 

Thoughts for improvement (on that huge list I'm sure you have :lol::

  • * Identify a recursion scenario - give at least a warning unless the recursion can be verified to be safe -- this I think, along with ability to turn warnings on/off is very desirable
    * flatten out tail-call recursion (maybe you do this already?)
    * In a recursion scenario, determine if it's bounded (above example it is) - this gives opportunity to flatten the recursion
    * Determine if modified 'stack' variables are used after the recursive call returns (this can be used at least to determine if recursion is safe or not)
    * introduce a temporary value stack in the recursive call

Out of all of this, I particularly vote the first point. I don't think it's a hardship asking someone to avoid recursion, and those warnings help alert the more naive programmer. Flattening out tail-call recursion should be a trivial optimization if you've not done this already (I haven't checked) given the static stack.

-

Jamie

Share this post


Link to post
Share on other sites

Join the conversation

You are posting as a guest. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

×
×
  • Create New...