[Patch, AVR]: QI builtins for parity, popcount, 1<< n

Georg-Johann Lay avr@gjlay.de
Fri Jun 17 19:03:00 GMT 2011


Joseph S. Myers schrieb:
> On Fri, 17 Jun 2011, Georg-Johann Lay wrote:
> 
>> I don't see what's bat with the patch, it's straight forward.
> 
> C is a high-level language, defined in terms of high-level
> semantics rather than machine instructions.  C code should be
> written where possible using machine-independent functionality,
> falling into machine-dependent operations only where the semantics
> cannot readily be represented in a machine-independent way; the
> compiler should generally be responsible for picking optimal
> instructions for the source code.
> 
> C code should write "1 << n" (or "1 << (n & 7)" if that's what it
> wants) for shifts rather than __builtin_avr_pow2.  That way it's
> more portable and more readable to general C programmers who aren't
> familiar with all the machine-specific interfaces.  Similarly, code
> wanting to add values should use the "+" operator rather than each
> target having its own __builtin_<arch>_add.  And since parity and
> population-count operations are widely present and generically
> useful, GNU C has generic built-in functions for those, so code
> should use __builtin_parity and __builtin_popcount on all machines
> rather than machine-specific variants; such machine-specific
> variants should not exist.
> 
> The machine-independent parts of the compiler should know about the
>  equivalence of (popcount X) and (popcount (zero_extend X)),
> (parity X) and (parity (zero_extend X)) and (parity X) and (parity
> (sign_extend X)) if the sign-extension is by an even number of bits
> - in fact, there is already code in simplify_unary_operation_1 that
> does know this (the assumption that all sign-extensions are by an
> even number of bits is hardcoded).  The target should just need to
> describe how to code these operations on various modes.  If the
> existing code doesn't suffice to cause popcountqi etc. patterns to
> be used for the generic built-in functions, the appropriate fix is
> generic rather than adding new target-specific built-in functions -
> just as if the compiler didn't generate your target's addition
> instruction from the '+' operator, the right fix is not to add
> __builtin_<arch>_add to generate that instruction but rather to
> make '+' generate it.
> 
>
> Joseph S. Myers

Thanks for you detailed explanations.  For popcount and parity I
agree, the patch is cleaner now and there are no ad-hoc builtins
needed to get the QI versions produced.

Trying popcountsi2 confused be a bit: Without popcountsi2 in md,
optabs expands to a function as HI = popcount (SI) as I expect from
the prototype/documentation.  For the expander, however, destination
(operand0) must be SI in order to get it to work. With HI destination
the expander is ignored.

For the 1 << n type of shifts the situation on a 8-bit µC is
considerably different to a PC:

On bare metal with RAM of 128 bytes, 2K for the program and at your
option also hard real time constraints, the situation is different and
sometimes each instruction/tick/byte counts.  In my programs I avoid
shifting by variable offsets if possible; but some guys do it.
The resulting code is a loop because AVR can only shift by one bit.
Together with C spec that results in a bulky 16-bit loop, see PR29560.

A typical piece of code might look like this:

#define SFR (*((volatile unsigned char*) 0x2b))

void set_port (unsigned char pin)
{
    SFR |= (1 << pin);
}

which compiles to

set_port:
	in r25,43-0x20	 ;  7	*movqi/4	[length = 1]
	ldi r18,lo8(1)	 ;  9	*movhi/4	[length = 2]
	ldi r19,hi8(1)
	rjmp 2f	 ;  10	ashlhi3/1	[length = 6]
1:	lsl r18
	rol r19
2:	dec r24
	brpl 1b
	or r25,r18	 ;  11	iorqi3/1	[length = 1]
	out 43-0x20,r25	 ;  13	*movqi/3	[length = 1]
	ret	 ;  21	return	[length = 1]

Trying to hack around that and to get at least an 8-bit loop fails.
Sprinkling (unsigned char) casts won't help and writing
  1 << (pin & 7)
will add just another instruction (andqi3).

Insn combine does not come up with more than
(set (reg:HI)
     (ashift:HI (const_int 1)
                (reg:QI)))
and even if a suitable pattern would show up it is not nice to clutter
a backend with this sorts of code like
(set (reg:QI)
     (subreg:QI (ashift:HI (const_int 1)
                           (and:QI (reg:QI)
                                   (const_int 7))) 0))
or whatever.  There is a ashlqi3 pattern in avr BE but I never managed
to produce it (except with -mint8 which changes ABI and is not really
supported any more).

For the addition, some users torture poor AVR with long long.
I agree that it's overkill and anyone that writes that in C must know
what he is doing.

Anyway, there are programmers that write such code and expect avr-gcc
to come up with code like

  subi r18, -1
  sbci r19, -1
  sbci r20, -1
  sbci r21, -1
  sbci r22, -1
  sbci r23, -1
  sbci r24, -1
  sbci r25, -1

for x=x+1.  What they actually will get is

	mov r14,r18	 ;  215	*movqi/1	[length = 1]
	inc r14	 ;  24	addqi3/3	[length = 1]
	ldi r30,lo8(1)	 ;  25	*movqi/2	[length = 1]
	cp r14,r18	 ;  26	*cmpqi/2	[length = 1]
	brlo .L5	 ;  27	branch	[length = 1]
	ldi r30,lo8(0)	 ;  28	*movqi/1	[length = 1]
.L5:
	mov r15,r30	 ;  216	*movqi/1	[length = 1]
	add r15,r19	 ;  36	addqi3/1	[length = 1]
	ldi r16,lo8(1)	 ;  37	*movqi/2	[length = 1]
	cp r15,r19	 ;  38	*cmpqi/2	[length = 1]
	brlo .L7	 ;  39	branch	[length = 1]
	ldi r16,lo8(0)	 ;  40	*movqi/1	[length = 1]
.L7:
	add r16,r20	 ;  50	addqi3/1	[length = 1]
	ldi r17,lo8(1)	 ;  51	*movqi/2	[length = 1]
	cp r16,r20	 ;  52	*cmpqi/2	[length = 1]
	brlo .L9	 ;  53	branch	[length = 1]
	ldi r17,lo8(0)	 ;  54	*movqi/1	[length = 1]
.L9:
	add r17,r21	 ;  64	addqi3/1	[length = 1]
	ldi r27,lo8(1)	 ;  65	*movqi/2	[length = 1]
	cp r17,r21	 ;  66	*cmpqi/2	[length = 1]
	brlo .L11	 ;  67	branch	[length = 1]
	ldi r27,lo8(0)	 ;  68	*movqi/1	[length = 1]
.L11:
	add r27,r22	 ;  78	addqi3/1	[length = 1]
	ldi r26,lo8(1)	 ;  79	*movqi/2	[length = 1]
	cp r27,r22	 ;  80	*cmpqi/2	[length = 1]
	brlo .L13	 ;  81	branch	[length = 1]
	ldi r26,lo8(0)	 ;  82	*movqi/1	[length = 1]
.L13:
	add r26,r23	 ;  92	addqi3/1	[length = 1]
	ldi r31,lo8(1)	 ;  93	*movqi/2	[length = 1]
	cp r26,r23	 ;  94	*cmpqi/2	[length = 1]
	brlo .L15	 ;  95	branch	[length = 1]
	ldi r31,lo8(0)	 ;  96	*movqi/1	[length = 1]
.L15:
	add r31,r24	 ;  106	addqi3/1	[length = 1]
	ldi r30,lo8(1)	 ;  107	*movqi/2	[length = 1]
	cp r31,r24	 ;  108	*cmpqi/2	[length = 1]
	brlo .L17	 ;  109	branch	[length = 1]
	ldi r30,lo8(0)	 ;  110	*movqi/1	[length = 1]
.L17:
	mov r18,r14	 ;  138	*movqi/1	[length = 1]
	mov r19,r15	 ;  139	*movqi/1	[length = 1]
	mov r20,r16	 ;  140	*movqi/1	[length = 1]
	mov r21,r17	 ;  141	*movqi/1	[length = 1]
	mov r22,r27	 ;  142	*movqi/1	[length = 1]
	mov r23,r26	 ;  143	*movqi/1	[length = 1]
	mov r24,r31	 ;  144	*movqi/1	[length = 1]
	add r25,r30	 ;  145	addqi3/1	[length = 1]

I agree with Denis that 64-bit support in avr is too complex.

However, if someone sees such code and asks what can be done about it,
there is no straight forward solution (movdi in avr BE is not really
straight forward), and typical reactions are complete lack of
understanding and comments like
"free software = scrap, use another compiler"

Guys that write such code would be glad if there was something like
builtin_add64...

So here is my question: Would it be big deal to teach optabs to expand
plus:di, minus:di as libcall?  Maybe even compare is feasible? Like so:

* Just test if there is a corresponding insn
* if not, look if there is a corresponding optab entry
* if not, lower to word_mode.

To come back to the original topic, here is a tentative patch for
better popcount and parity:

	* config/avr/t-avr (LIB1ASMFUNCS): Rename _loop_ffsqi2 to
	_ffsqi2_nz.
	* confif/avr/libgcc.S: Ditto. Rename __loop_ffsqi2 to __ffsqi2_nz.
	(__ctzsi2, __ctzhi2): Map zero to 255.
	(__popcounthi2): Use r27 instead of r30.
	(__popcountdi2): Use r30 instead of r27.
	* config/avr/avr.md (parityhi2): New expander.
	(popcounthi2): New expander.
	(popcountsi2): New expander.
	(*parityhi2.libgcc): New insn.
	(*parityqihi2.libgcc): New insn.
	(*popcounthi2.libgcc): New insn.
	(*popcountsi2.libgcc): New insn.
	(*popcountqi2.libgcc): New insn.
	(*popcountqihi2.libgcc): New insn_and_split.

Johann

BTW, combine tests for
   (parity:HI (reg:QI))
it does not try
   (parity:HI (zero_extend:HI (reg:QI)))

-------------- next part --------------
A non-text attachment was scrubbed...
Name: builtin-pop.diff
Type: text/x-patch
Size: 5232 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20110617/17f38205/attachment.bin>


More information about the Gcc-patches mailing list