## sdcc-devel

 [sdcc-devel] Optimized compares From: Scott Dattalo - 2001-12-22 16:59:47 ```Sandeep, How hard is to track the flow for the following situation: char x; char y; .... if(x < 20) y |= 1; if(x < 40) y |= 2; if(x < 60) y |= 4; ..... Now this can implemented fairly efficiently in assembly: if(x<20) goto L1; if(x<40) goto L2; if(x<60) goto L3; goto L4; L1: y |= 1; L2: y |= 2; L3: y |= 4; L4: In other words, if we know x is less than 20, then we don't even need to bother with the compares to 40 and 60. Scott ```
 RE: [sdcc-devel] Optimized compares From: Sandeep Dutta - 2001-12-23 21:19:43 ```Hi Scott, This kind of transformations will not be very easy to implement. However I do have plans to implement some space optimizations like if (something) k |= 3; else k |= 4; will become if (something) temp1=3; else temp1=4; k |= temp1; This optimization is a little bit of work, and I need to think about the implementation details some more. So if you rewrite the code in the form if (x < 20) { y |= 7; } else if (x < 40) { y |= 6; } else if (x < 60) { y |= 4; } It will be able to utilize this optimization. I think there is an underlying question can we track value ranges ? Yes this should not be very difficult to do....for each basic block the incoming definitions can be tagged with a value range ...The value ranges will depend on assignments & operations performed on it . I will put this on my to-do list as well. Sandeep > -----Original Message----- > From: sdcc-devel-admin@... > [mailto:sdcc-devel-admin@...]On Behalf Of Scott > Dattalo > Sent: Saturday, December 22, 2001 9:00 AM > To: sdcc-devel@... > Subject: [sdcc-devel] Optimized compares > > > > Sandeep, > > How hard is to track the flow for the following situation: > > char x; > char y; > > ..... > > > if(x < 20) > y |= 1; > > if(x < 40) > y |= 2; > > if(x < 60) > y |= 4; > > ...... > > Now this can implemented fairly efficiently in assembly: > > if(x<20) > goto L1; > > if(x<40) > goto L2; > > if(x<60) > goto L3; > > goto L4; > L1: > y |= 1; > L2: > y |= 2; > L3: > y |= 4; > > L4: > > In other words, if we know x is less than 20, then we don't > even need to > bother with the compares to 40 and 60. > > Scott > > > _______________________________________________ > sdcc-devel mailing list > sdcc-devel@... > https://lists.sourceforge.net/lists/listinfo/sdcc-devel > > > ```
 RE: [sdcc-devel] Optimized compares From: Scott Dattalo - 2001-12-24 03:05:17 ```On Sun, 23 Dec 2001, Sandeep Dutta wrote: > Hi Scott, > > This kind of transformations will not be very easy to implement. > However I do have plans to implement some space optimizations like > > if (something) > k |= 3; > else > k |= 4; > > will become > > if (something) > temp1=3; > else > temp1=4; > k |= temp1; If temp1 is the accumulator, then this would be more efficient. For the pic port, however, if temp1 is not the accumulator then this "optimization" is less efficient. One of my goals with pCode is to optimize snippets such as these into: temp1=4; if(something) temp1=3; k |= temp1; Which in PIC code is: movlw 4 btfss something,bit movlw 3 iorwf k,f If you look at signed compares, you can already find a lot of the pre-condition programming in the PIC port. > > This optimization is a little bit of work, and I need to think > about the implementation details some more. > > So if you rewrite the code in the form > if (x < 20) { > y |= 7; > } else if (x < 40) { > y |= 6; > } else if (x < 60) { > y |= 4; > } > > It will be able to utilize this optimization. I think there > is an underlying question can we track value ranges ? Yes this > should not be very difficult to do....for each basic block the > incoming definitions can be tagged with a value range ...The value > ranges will depend on assignments & operations performed on it . > I will put this on my to-do list as well. I wasn't asking so much about tracking ranges as I was about tracking flow. We already do this to some degree by changing <='s into >'s with the goto conditions reversed. However, I know that tracking flow is not an easy thing to do in general! Scott ```
 RE: [sdcc-devel] Optimized compares From: Sandeep Dutta - 2001-12-24 03:23:58 ```Hi Scott, > I wasn't asking so much about tracking ranges as I was about tracking > flow. We already do this to some degree by changing <='s into > >'s with the > goto conditions reversed. However, I know that tracking flow is not an > easy thing to do in general! > Actually we do track flow (data & control flow) very well, try --cyclomatic will give a brief statistic of a function. Now the question becomes what you want to do with the information. The transformation you are suggesting is indeed very interesting and could speed up execution. SDCCdflow.c will give you an idea, we know exactly which basic block, follows which basic block, and variables that are alive at the entry of each basic block and the definitions that come into the block. I guess we will need to add the information on what conditions are guarding the entry to a basic block. And then do this transformation based on the guards. Would have to think about this some more :) ..interesting problem though ... Sandeep ```
 Re: [sdcc-devel] Optimized compares From: Johan Knol - 2001-12-23 21:24:49 ```Although not addressed to me, I would say impossible. Besides, it is not the task of a compiler to take over the intelligence of the programmer. It's task is only to prevent him/her to do (or at least warn him/her for doing) obvious (but more often: unnoticed) stupid/inefficient things, but generate code at the programmers wish ... Johan ----- Original Message ----- From: Scott Dattalo To: Sent: Saturday, December 22, 2001 5:59 PM Subject: [sdcc-devel] Optimized compares > > Sandeep, > > How hard is to track the flow for the following situation: > > char x; > char y; > > .... > > > if(x < 20) > y |= 1; > > if(x < 40) > y |= 2; > > if(x < 60) > y |= 4; > > ..... > > Now this can implemented fairly efficiently in assembly: > > if(x<20) > goto L1; > > if(x<40) > goto L2; > > if(x<60) > goto L3; > > goto L4; > L1: > y |= 1; > L2: > y |= 2; > L3: > y |= 4; > > L4: > > In other words, if we know x is less than 20, then we don't even need to > bother with the compares to 40 and 60. > > Scott > > > _______________________________________________ > sdcc-devel mailing list > sdcc-devel@... > https://lists.sourceforge.net/lists/listinfo/sdcc-devel > > ```
 Re: [sdcc-devel] Optimized compares From: Scott Dattalo - 2001-12-24 02:48:05 ```On Sun, 23 Dec 2001, Johan Knol wrote: > Although not addressed to me, I would say impossible. Besides, it is not the > task of a compiler to take over the intelligence of the programmer. It's > task is only to prevent him/her to do (or at least warn him/her for doing) > obvious (but more often: unnoticed) stupid/inefficient things, but generate > code at the programmers wish ... No offense, Johan, but one of the reasons I chose to implement the PIC Port for SDCC was because of the stupid/inefficient things that the compiler has done to my C code in the past. I think the compiler's primary job is to exactly implement the code the user has written in C. It's goal should be to do this as efficiently as possible. I'm an obsessed perfectionist when it comes to PIC code and I've contorted SDCC to generate some wonderfully tight code. But that's only because you and Sandeep and others have created a wonderful framework upon which others can create. I think the request I proposed is perfectly reasonable. I first *thought* I saw it in another compiler. Upon closer inspection it turned out that I was doing something boneheaded, but still, I think it's doable and SDCC will be the better if it's really possible. If it's not implemented in the iCode portion, then I'll figure a way to do it in the pCode. The way I'd structure it is by partitioning the code into contiguous blocks. Each entry into the block is the result as a branch, as is each exit. If a static compare is performed to obtain entry into a block, then that's a simple piece of information to retain. Consecutive blocks with mutually exclusive entry conditions can be easily monitored and decisions can be made up front to determine which block will execute. Similarly, consecutive blocks with inclusive entry conditions can save a comparison in many cases. It's just the associative law... The only hard part with the implementation is designing the infrastructure. That's why I prefaced the question with "How hard would it be ...". I know it can be done, it's just a matter of writing the code :). Scott ```