Bug 49903 - [avr] Redundant comparisons in binary-search switch/case expansion
Summary: [avr] Redundant comparisons in binary-search switch/case expansion
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: target (show other bugs)
Version: 4.7.0
: P3 enhancement
Target Milestone: 4.7.0
Assignee: Georg-Johann Lay
URL:
Keywords: missed-optimization, patch
Depends on:
Blocks:
 
Reported: 2011-07-29 15:01 UTC by Georg-Johann Lay
Modified: 2011-08-14 09:11 UTC (History)
3 users (show)

See Also:
Host:
Target: avr
Build:
Known to work:
Known to fail:
Last reconfirmed: 2011-08-11 00:00:00


Attachments
cswitch.c: C test case (178 bytes, text/plain)
2011-07-29 15:01 UTC, Georg-Johann Lay
Details
opt-cswitch.diff (3.26 KB, patch)
2011-08-11 17:43 UTC, Georg-Johann Lay
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Georg-Johann Lay 2011-07-29 15:01:01 UTC
Created attachment 24864 [details]
cswitch.c: C test case

avr-gcc emits redundant comparisons like these:

cpi r24,lo8(55)	 ;  22	*cmpqi/3	[length = 1]
breq .L10	 ;  23	branch	[length = 1]
cpi r24,lo8(56)	 ;  24	*cmpqi/3	[length = 1]
brge .L19	 ;  25	branch	[length = 1]

which could just as well be

cpi r24,lo8(55)	 ;  22	*cmpqi/3	[length = 1]
breq .L10	 ;  23	branch	[length = 1]
brge .L19	 ;  25	branch	[length = 1]

or these:

cpi r24,lo8(100)	 ;  61	*cmpqi/3	[length = 1]
breq .L16	 ;  62	branch	[length = 1]
cpi r24,lo8(100)	 ;  63	*cmpqi/3	[length = 1]
brlt .L15	 ;  64	branch	[length = 1]

which could just as well be

cpi r24,lo8(100)	 ;  61	*cmpqi/3	[length = 1]
breq .L16	 ;  62	branch	[length = 1]
brlt .L15	 ;  64	branch	[length = 1]

This concernes signed/unsigned comparisons for QI/HI/SI

-- command line ----------------------------------------------

avr-gcc cswitch.c -dp -S -Os

-- configure -------------------------------------------------

../../gcc.gnu.org/trunk/configure --target=avr --prefix=/home/john/gnu/install/gcc-4.7 --disable-nls --disable-shared --enable-languages=c,c++ --with-dwarf2 --disable-lto

-- GCC  -------------------------------------------------

as of 4.7.0 trunk, r176818 from 2011-07-27
Comment 1 Eric Weddington 2011-07-29 15:07:52 UTC
Johann,
Would some type of peephole optimization help out on this?
Comment 2 Georg-Johann Lay 2011-07-29 16:11:12 UTC
(In reply to comment #1)
> Johann,
> Would some type of peephole optimization help out on this?

RTL peephole won't work because they operate just inside basic blocks.

Don't know the retionale behind that limitation, appears that it's just for technical and implementational reasons.  RTL peep need not to be confused by BBs, just code_labels etc. would bother.

Text peepholes match but it might be tedious and error prone to work out instructions lengths or the correct instructions if jump offsets don't match.

Maybe a way is in avr_reorg, but it would be quite tedious to work out all QI/HI/SI signed and unsigned combinations.  And it must ensure that no other transformation takes place.  There's bunch of special treatment in md and c and cc0 handling.  E.g. I don't quite understand why jumps clobber cc0; btw not clobbering cc0 will not fix this PR.
Comment 3 Richard Henderson 2011-08-02 00:11:34 UTC
It would certainly be quite a lot of work, but this sort of thing *is*
handled by pass_compare_elim_after_reload.  That requires exposing the
flags register as a CCmode quantity.

C.f. the mn10300 port.
Comment 4 Georg-Johann Lay 2011-08-11 17:43:38 UTC
Created attachment 24984 [details]
opt-cswitch.diff

See http://gcc.gnu.org/ml/gcc-patches/2011-08/msg01029.html
Comment 5 Hans-Peter Nilsson 2011-08-12 22:54:27 UTC
I'd guess you're just looking at a NOTICE_UPDATE_CC bug in the AVR port.
Comment 6 Georg-Johann Lay 2011-08-14 09:10:20 UTC
Author: gjl
Date: Sun Aug 14 09:10:13 2011
New Revision: 177744

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=177744
Log:
	
	* PR target/49903
	* config/avr/avr.md (UNSPEC_IDENTITY): New c_enum.
	(branch_unspec): New insn.
	(branch): Beauty farm.
	* config/avr/avr.c (compare_condition): Use JUMP_P.  Test SET_SRC
	to be IF_THEN_ELSE.
	(avr_compare_pattern, avr_reorg_remove_redundant_compare):
	New static functions.
	(avr_reorg): Use them.  Use next_real_insn instead of NEXT_INSN.
	Use CONST_INT_P.  Beauty.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/avr/avr.c
    trunk/gcc/config/avr/avr.md
Comment 7 Georg-Johann Lay 2011-08-14 09:11:26 UTC
Closed with this patch.