Warum wird aus einem right-shift eines uint8_t ein 16-Bit arithm.-shift beim avr-gcc

[Randy B. (rbrecker)]

Hallo zusammen,

folgender simpler Code:

volatile unsigned char x;
volatile unsigned char y;

int main() {
    x >>= 1;
    y /= 2;
}

ergibt mit avr-gcc (7.3.0 oder auch 8.0.1)

main:
        lds r24,x        ;  x.0_1, x
        ldi r25,0        ;  x.0_1
        asr r25  ;  tmp50
        ror r24  ;  tmp50
        sts x,r24        ;  x, tmp50

        lds r24,y        ;  y.1_5, y
        lsr r24  ;  _6
        sts y,r24        ;  y, _6

        ldi r25,0        ; 
        ldi r24,0        ; 
        ret

Nach meinem Verständnis sollte der avr-gcc aus einem right-shift bei 
einem 8-Bit unsigned Typ auch ein 8-Bit logical-shift machen, genauso 
wie bei der Division. Aber warum wird es ein 16-Bit arithmetic-shift?

Compilerflags: -Os -Wall

[Andreas M. (amesser)]

Weil du einen Right Shift mit einem int16 machst. Bei einer Division 
greift vermutlich eine Optimierung die sieht das es unerheblich ist ob 
hier 8 oder 16 bit gemacht wird. Normalerweise müsste die Division auch 
mit 16 Bit gemacht werden wegen type promotion.

[Randy B. (rbrecker)]

Andreas M. schrieb:
> Weil du einen Right Shift mit einem int16 machst.

Selbst ein

    x = ((uint8_t)x) >> 1;

liefert dasselbe Resultat.

Ausserdem bin ich der Meinung, das im Code ganz oben auch keine 
Promotion stattfindet.

[Andreas M. (amesser)]

x >>= (uint8_t)1;

[Randy B. (rbrecker)]

Leider nein!

[(prx) A. K. (prx)]

An sich gibt es in C überhaupt keine 8 Bit Rechnungen, per 
Sprachdefinition. GCC gibt sich zwar mittlerweile einge Mühe, unnötige 
16 Bit Rechnung zu vermeiden, aber irgendwo findet sich immer etwas, das 
nicht optimal umgesetzt wird.

[Stefan E. (sternst)]

Randy B. schrieb:
> Ausserdem bin ich der Meinung, das im Code ganz oben auch keine
> Promotion stattfindet.

Damit liegst du falsch. Du kannst dich noch so sehr mit Casts und 
Umformulieren der Zeile verrenken, die eigentliche Shift-Operation wird 
immer mindestens in signed int durchgeführt. Das legen die 
Promotion-Regeln so fest. Das davon im resultierenden Code meist nichts 
mehr zu sehen ist, liegt an der Optimierung.

Die eigentliche Frage lautet also, warum die Optimierung im vorliegenden 
Fall versagt. Und die kann ich dir nicht beantworten.

[Luther B. (luther-blissett)]

Scheint mir ein "missed optimization bug" zu sein. gcc-4.9.2 macht 
daraus einfach:

  lds r24,x
  lsr r24
  sts x,r24
  lds r24,y
  lsr r24
  sts y,r24

Wie GCC optimiert ist allerdings immer gerne mal ein Rätsel. Bei "-Os" 
(s wir size) kommt für x64 bei mir das hier raus:

  movzbl x(%rip), %eax // 6 bytes
  sarl %eax            // 2 bytes 
  movb %al, x(%rip)    // 6 bytes 
  movb y(%rip), %al
  shrb %al
  movb %al, y(%rip)

Während clang wie erwartet so was macht:

  shrb  x(%rip)  // 6 bytes
  shrb  y(%rip)

[(prx) A. K. (prx)]

Randy B. schrieb:
> Ausserdem bin ich der Meinung, das im Code ganz oben auch keine
> Promotion stattfindet.

Doch. Aber das Ergebnis hängt nicht davon ab.

[Stefan E. (sternst)]

A. K. schrieb:
> GCC gibt sich zwar mittlerweile einge Mühe, unnötige
> 16 Bit Rechnung zu vermeiden, aber irgendwo findet sich immer etwas, das
> nicht optimal umgesetzt wird.

Wobei es in diesem Fall eine Regression zu sein scheint.
Ein GCC 5.4.0 z.B. macht aus beidem ein lds-lsr-sts.

[Andreas M. (amesser)]

Ich habe mir mal den C-Standard angesehen. Ich bin mir nicht ganz 
sicher, interpretiere den Standard jedoch so das bei Shift Operationen 
eine Integer-Promotion durchgeführt werden darf, selbst wenn beide 
Seiten den gleichen, kleineren Typ haben. (Muss nicht, aber darf) Bei 
Division ist das nicht der Fall.

[Randy B. (rbrecker)]

Unter

http://en.cppreference.com/w/cpp/language/operator_arithmetic

steht, dass eine Promotion durchgeführt werden muss.
Also haben wir hier eine fehlschlagende Optimierung. Da es bei den 
älteren gcc-Versionen geht, ist es wohl ein Regression.

[(prx) A. K. (prx)]

Andreas M. schrieb:
> Ich habe mir mal den C-Standard angesehen. Ich bin mir nicht ganz
> sicher, interpretiere den Standard jedoch so das bei Shift Operationen
> eine Integer-Promotion durchgeführt werden darf, selbst wenn beide
> Seiten den gleichen, kleineren Typ haben. (Muss nicht, aber darf) Bei
> Division ist das nicht der Fall.

Kannst du dieses Gefühl irgenwie belegen? Alle Berechnungen mit Typen 
kleiner int finden per Definition in int statt. Egal ob Addition, Shift 
oder Division.

Der Compiler hat aber die Freiheit, bei gleichem Ergebnis anders zu 
handeln.

[Stefan E. (sternst)]

Andreas M. schrieb:
> Ich bin mir nicht ganz
> sicher, interpretiere den Standard jedoch so das bei Shift Operationen
> eine Integer-Promotion durchgeführt werden darf, selbst wenn beide
> Seiten den gleichen, kleineren Typ haben. (Muss nicht, aber darf)

Welcher C Standard soll das sein, wo man es so interpretieren kann?
In C99 steht z.B

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand.

Das ist ganz klar ein "muss", kein "darf".

[Andreas M. (amesser)]

A. K. schrieb:
> Andreas M. schrieb:
>> Ich habe mir mal den C-Standard angesehen. Ich bin mir nicht ganz
>> sicher, interpretiere den Standard jedoch so das bei Shift Operationen
>> eine Integer-Promotion durchgeführt werden darf, selbst wenn beide
>> Seiten den gleichen, kleineren Typ haben. (Muss nicht, aber darf) Bei
>> Division ist das nicht der Fall.
>
> Kannst du dieses Gefühl irgenwie belegen? Alle Berechnungen mit Typen
> kleiner int finden per Definition in int statt. Egal ob Addition, Shift
> oder Division.

Aus C11:

The following may be used in an expression wherever an int or unsigned int may be used:
— An object or expression with an integer type (other than int or unsigned int)
whose integer conversion rank is less than or equal to the rank of int and
unsigned int.
— A bit-field of type _Bool, int, signed int, or unsigned int.

If an int can represent all values of the original type (as restricted by the width, for a
bit-field), the value is converted to an int; otherwise, it is converted to an unsigned
int. These are called the integer promotions. 58) All other types are unchanged by the integer promotions.

Ich interpretiere das "May" im ersten Satz erstmal als "darf".

Dazu dann die Note 58)

58) The integer promotions are applied only: as part of the usual arithmetic conversions, to certain
argument expressions, to the operands of the unary +, -, and ~ operators, and to both 
operands of the
shift operators, as specified by their respective subclauses.

Welche sich explizit nochmal auf Shift bezieht. Bei Shift selbst steht 
das explizit nochmal drinnen, das zuerst promoted wird, bei den anderen 
Operationen jedoch nicht. Für mich bedeutet das ich bei einer Division 
beio der beide Seiten bereits den selben Typ haben nicht promoten muss 
(aber darf), bei einem Shift jedoch muss, weil explizit jeder Operand 
laut Spec zuerst promoted werden muss. Daher mein Gefühl.

Edit: Zitate durch Code ersetzt.

[Stefan E. (sternst)]

Andreas M. schrieb:
> Ich interpretiere das "May" im ersten Satz erstmal als "darf".

Nur dass sich das "darf" nicht auf das Promoten bezieht, sondern darauf, 
was an Stelle von int oder unsigned int noch verwendet werden "darf". Im 
zweiten Absatz des Zitats steht dann "is converted" und nicht "may be 
converted".

[Yalu X. (yalu) (Moderator)]

Randy B. schrieb:
> ergibt mit avr-gcc (7.3.0 oder auch 8.0.1)

Mein AVR-GCC 7.3.0 (Arch Linux, ungepatcht) liefert dieses hier:

main:
  lds r24,x
  lsr r24
  sts x,r24
  lds r24,y
  lsr r24
  sts y,r24
  ldi r25,0
  ldi r24,0
  ret

Einen 8.0.1 habe ich gerade nicht greifbar.

[Randy B. (rbrecker)]

Vielen Dank, Leute.

Für mich ist das gelöst, s.a. mein eigener Beitrag von oben.
Ich werde auch einen missed optimization bug beim gcc reporten.

[Oliver S. (oliverso)]

DAs ist löblich, dient dann aber nur der Vollständigkeit halber, denn 
ändern wird das vermutlich nichts. Wenn Johann sich nicht erbarmt, 
passiert im avr-gcc leidet gar nichts.

Oliver

[2⁵ (Gast)]

Oliver S. schrieb:
> Wenn Johann sich nicht erbarmt, passiert im avr-gcc leidet gar nichts.

So sieht es aus: Beitrag "Re: newlib fuer AVR?"

[Yalu X. (yalu) (Moderator)]

Yalu X. schrieb:
> Einen 8.0.1 habe ich gerade nicht greifbar.

Inzwischen habe ich auch mit dem AVR-GCC 8.0.1-RC-20180425 getestet. Er
liefert bei mir den gleichen (optimierten) Code wie der 7.3.0 (s. mein
Beitrag weiter oben).

Randy B. schrieb:
> Ich werde auch einen missed optimization bug beim gcc reporten.

Bevor du dir die Mühe machst, sollte man versuchen herauszufinden, warum
deine beiden Compiler-Installationen trotz gleicher Versionsnummer und
gleicher Kommandozeilenoptionen schlechteren Code liefern als meine.

[Randy B. (rbrecker)]

Doch, ich werde den Bug eintragen ;-)

Aber: für den avr-g++ und nicht für den avr-gcc.

Denn: Asche auf mein Haupt, ich habe das Beispiel im Language-Mode C++ 
übersetzt. Übersetzt man es im Language-Mode C, dann findet die 
Optimierung auch statt.

Nun: DAS ist echt merkwürdig.

Deswegen: werde ich den Bug eintragen.

[Yalu X. (yalu) (Moderator)]

Randy B. schrieb:
> Denn: Asche auf mein Haupt, ich habe das Beispiel im Language-Mode C++
> übersetzt.

Stimmt, damit kann ich das Problem mit beiden Compilern reproduzieren.

> Deswegen: werde ich den Bug eintragen.

Ja, mach das.

[Randy B. (rbrecker)]

FYI: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85533

[Andreas M. (amesser)]

Stefan E. schrieb:
> Andreas M. schrieb:
>> Ich interpretiere das "May" im ersten Satz erstmal als "darf".
>
> Nur dass sich das "darf" nicht auf das Promoten bezieht, sondern darauf,
> was an Stelle von int oder unsigned int noch verwendet werden "darf". Im
> zweiten Absatz des Zitats steht dann "is converted" und nicht "may be
> converted".

Ja stimmt wohl, muss mein Englisch mal nachjustieren.

[Johann L. (gjlayde)]

https://gcc.gnu.org/PR82658

Hier liegt es also am C++ Frontend.  Mit Testfall

// avr-g++ -Os -save-temps -dp -fdump-rtl-combine-details -c main.c

unsigned char x;

void fun1 ()
{
    x >>= 1;
}

int fun2 (unsigned char x)
{
    return x >> 1;
}

finden sich im .combine Dump folgende Versuche:

Failed to match this instruction:
(set (reg:HI 45)
     (lshiftrt:HI (zero_extend:HI (reg:QI 44 [ x ]))
                  (const_int 1)))

Es wird also versucht, eine Instruktion bzw. Pattern zu finden, das 
zunächst ein 8-Bit (QI) Register zu einem 16-Bit (HI) Wert erweitert und 
den Wert dann um 1 nach rechts schiebt.

Prinzipiell wäre es also möglich, die Optimierung im avr Backend 
unterzubringen, auch wenn das keine gute Stelle dafür ist. Shift und 
Erweiterung kommutieren, so dass stattdessen

(set (reg:HI 45)
     (zero_extend:HI (lshiftrt:QI (reg:QI 44)
                                  (const_int 1))))

möglich wäre. Das spart zunächt den Shift des MSB.  Danach wirds 
hässlich, denn man will dies abbilden auf

(set (subreg:QI (reg:HI 45) 0)
     (lshiftrt:QI (reg:QI 44)
                  (const_int 1)))

(set (subreg:QI (reg:HI 45) 1)
     (const_int 0))

damit Setzen des MSB gegebenenfalls vor der Register-Allokation 
entsorgt werden kann, so dass dem MSB dann kein Register zugewiesen 
wird.  Der Reg-Allokator behandelt Subregs leider nicht immer optimal, 
so dass man optimierungstechnisch durchaus vom Regen in die Traufe 
kommen könnte...

Ab besten stehen die Chancen für den Fix eines solchen Problems, wenn es 
auf einer populäreren Architektur reproduziert werden kann.  Hier nach 
Möglichkeit auf einer, welche wie avr sizeof(int) > sizeof(word) 
erfüllt, d.h. >> promotet zu int.