Jak utworzyć nieskończoną pustą pętlę, która nie zostanie zoptymalizowana?

131

Standard C11 wydaje się sugerować, że instrukcje iteracji ze stałymi wyrażeniami kontrolującymi nie powinny być optymalizowane. Czerpię radę z tej odpowiedzi , która konkretnie cytuje sekcję 6.8.5 projektu standardu:

Instrukcja iteracji, której wyrażenie kontrolne nie jest wyrażeniem stałym ... może zostać przyjęte przez implementację jako zakończona.

W tej odpowiedzi wspomniano, że taka pętla while(1) ;nie powinna podlegać optymalizacji.

Więc ... dlaczego Clang / LLVM optymalizuje poniższą pętlę (z kompilacją cc -O2 -std=c11 test.c -o test)?

#include <stdio.h>

static void die() {
    while(1)
        ;
}

int main() {
    printf("begin\n");
    die();
    printf("unreachable\n");
}

Na mojej maszynie drukuje się begin, a następnie ulega awarii na niedozwolonej instrukcji ( ud2pułapka umieszczona po die()). W Godbolt możemy zobaczyć, że nic nie jest generowane po wezwaniu do puts.

Zaskakująco trudne zadanie sprawiło, że Clang wyprowadził nieskończoną pętlę poniżej -O2- podczas gdy mogłem wielokrotnie testować volatilezmienną, która wymaga odczytu pamięci, którego nie chcę. A jeśli zrobię coś takiego:

#include <stdio.h>

static void die() {
    while(1)
        ;
}

int main() {
    printf("begin\n");
    volatile int x = 1;
    if(x)
        die();
    printf("unreachable\n");
}

... Odbitki Clanga, begina po nich unreachablejakby nieskończona pętla nigdy nie istniała.

Jak sprawić, by Clang wyprowadził prawidłową nieskończoną pętlę bez dostępu do pamięci z włączonymi optymalizacjami?

nneonneo
źródło
3
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Bhargav Rao
2
Nie ma przenośnego rozwiązania, które nie wiązałoby się z efektem ubocznym. Jeśli nie chcesz dostępu do pamięci, możesz mieć nadzieję, że zarejestrujesz niestabilny znak bez znaku; ale rejestr odchodzi w C ++ 17.
Scott M
25
Może to nie wchodzi w zakres pytania, ale jestem ciekawy, dlaczego chcesz to zrobić. Z pewnością istnieje inny sposób na zrealizowanie prawdziwego zadania. A może ma to charakter wyłącznie akademicki?
Cruncher
1
@Cruncher: Efekty konkretnej próby uruchomienia programu mogą być przydatne, zasadniczo bezużyteczne lub znacznie gorsze niż bezużyteczne. Wykonanie, w wyniku którego program utknie w nieskończonej pętli, może być bezużyteczne, ale nadal jest lepsze niż inne zachowania, które może zastąpić kompilator.
supercat
6
@Cruncher: Ponieważ kod może działać w kontekście wolnostojącym, w którym nie ma pojęcia exit(), i ponieważ kod mógł odkryć sytuację, w której nie może zagwarantować, że skutki dalszego wykonywania nie będą gorsze niż bezużyteczne . Pętla przeskakiwania do siebie jest dość kiepskim sposobem radzenia sobie z takimi sytuacjami, ale może jednak być najlepszym sposobem radzenia sobie w złej sytuacji.
supercat

Odpowiedzi:

77

Norma C11 mówi 6.8.5 / 6:

Instrukcja iteracyjna, której wyrażenie kontrolne nie jest wyrażeniem stałym, 156), które nie wykonuje żadnych operacji wejścia / wyjścia, nie ma dostępu do obiektów lotnych i nie wykonuje żadnych synchronizacji ani operacji atomowych w swoim ciele, kontroluje wyrażenie lub (w przypadku instrukcja) jego wyrażenie-3 może zostać przyjęte przez implementację jako zakończone. 157)

Dwie nuty nie są normatywne, ale dostarczają przydatnych informacji:

156) Pominięte wyrażenie kontrolne jest zastępowane niezerową stałą, która jest wyrażeniem stałym.

157) Ma to na celu umożliwienie transformacji kompilatora, takich jak usuwanie pustych pętli, nawet jeśli nie można udowodnić zakończenia.

W twoim przypadku while(1)jest to krystalicznie czyste stałe wyrażenie, więc implementacja nie może założyć, że zakończy się. Taka implementacja byłaby beznadziejnie zepsuta, ponieważ pętle „na zawsze” są powszechną konstrukcją programistyczną.

O ile wiem, co dzieje się z „nieosiągalnym kodem” po pętli, nie jest dobrze zdefiniowane. Jednak klang rzeczywiście zachowuje się bardzo dziwnie. Porównanie kodu maszynowego z gcc (x86):

gcc 9.2 -O3 -std=c11 -pedantic-errors

.LC0:
        .string "begin"
main:
        sub     rsp, 8
        mov     edi, OFFSET FLAT:.LC0
        call    puts
.L2:
        jmp     .L2

klang 9.0.0 -O3 -std=c11 -pedantic-errors

main:                                   # @main
        push    rax
        mov     edi, offset .Lstr
        call    puts
.Lstr:
        .asciz  "begin"

gcc generuje pętlę, clang po prostu wpada do lasu i kończy pracę z błędem 255.

Pochylam się nad tym, że zachowanie klangu jest niezgodne z przeznaczeniem. Ponieważ próbowałem rozszerzyć twój przykład w ten sposób:

#include <stdio.h>
#include <setjmp.h>

static _Noreturn void die() {
    while(1)
        ;
}

int main(void) {
    jmp_buf buf;
    _Bool first = !setjmp(buf);

    printf("begin\n");
    if(first)
    {
      die();
      longjmp(buf, 1);
    }
    printf("unreachable\n");
}

Dodałem C11, _Noreturnaby pomóc kompilatorowi dalej. Powinno być jasne, że ta funkcja się rozłączy, na podstawie samego słowa kluczowego.

setjmpzwróci 0 po pierwszym uruchomieniu, więc ten program powinien po prostu uderzyć w while(1)i zatrzymać się tam, wypisując tylko „start” (zakładając, że \ n opróżnia standardowe wyjście). Dzieje się tak z gcc.

Jeśli pętla została po prostu usunięta, powinna wypisać „rozpocząć” 2 razy, a następnie wydrukować „nieosiągalny”. Jednak w przypadku clang ( godbolt ) wypisuje „ start ” 1 raz, a następnie „nieosiągalny” przed zwróceniem kodu wyjścia 0. To po prostu źle, bez względu na to, jak to określisz.

Nie mogę znaleźć tutaj powodu do twierdzenia o nieokreślonym zachowaniu, więc uważam, że jest to błąd. W każdym razie takie zachowanie sprawia, że ​​clang jest w 100% bezużyteczny dla programów takich jak systemy wbudowane, w których po prostu musisz polegać na wiecznych pętlach zawieszających program (podczas oczekiwania na watchdoga itp.).

Lundin
źródło
15
Nie zgadzam się co do „tego krystalicznie czystego stałego wyrażenia, więc implementacja nie może założyć, że zakończy się” . To naprawdę zajmuje się wybrednym językiem prawniczym, ale 6.8.5/6ma postać, jeśli (te), możesz założyć (to) . To nie znaczy, że jeśli nie (te), możesz nie założyć (tego) . Jest to specyfikacja tylko wtedy, gdy warunki są spełnione, a nie wtedy, gdy są niespełnione, gdzie możesz zrobić, co chcesz, stosując standardy. A jeśli nie ma żadnych obserwowalnych ...
kabanus
7
@kabanus Cytowana część to szczególny przypadek. Jeśli nie (przypadek szczególny), oceń i uporządkuj kod w normalny sposób. Jeśli będziesz dalej czytać ten sam rozdział, wyrażenie kontrolne zostanie ocenione zgodnie ze specyfikacją dla każdej instrukcji iteracji („zgodnie z semantyką”), z wyjątkiem cytowanego przypadku specjalnego. Postępuje zgodnie z tymi samymi zasadami, co ocena każdego obliczenia wartości, które jest sekwencjonowane i dobrze zdefiniowane.
Lundin
2
Zgadzam się, ale nie można się dziwić, że w zestawie int z=3; int y=2; int x=1; printf("%d %d\n", x, z);nie ma żadnego 2, więc w pustym znaczeniu bezużytecznym xnie został przypisany po, yale po zoptymalizacji. Wychodząc od ostatniego zdania, przestrzegamy normalnych zasad, zakładamy, że czas został zatrzymany (ponieważ nie byliśmy już lepiej ograniczeni) i pozostawiony w ostatecznym, „nieosiągalnym” druku. Teraz optymalizujemy to bezużyteczne stwierdzenie (ponieważ nie wiemy nic lepszego).
kabanus
2
@MSalters Jeden z moich komentarzy został usunięty, ale dziękuję za wkład - i zgadzam się. Mój komentarz powiedział, że myślę, że jest to sedno debaty - jest to while(1);to samo, co int y = 2;stwierdzenie pod względem tego, jaką semantykę możemy zoptymalizować, nawet jeśli ich logika pozostaje w źródle. Od roku 1528 miałem wrażenie, że mogą być tacy sami, ale ponieważ ludzie o wiele bardziej doświadczeni niż ja kłócą się w drugą stronę, i najwyraźniej jest to oficjalny błąd, poza filozoficzną debatą na temat tego, czy sformułowanie w normie jest wyraźne , argument jest dyskusyjny.
kabanus
2
„Taka implementacja byłaby beznadziejnie zepsuta, ponieważ pętle„ na zawsze ”to wspólny konstrukt programistyczny.” - Rozumiem sentyment, ale argument jest wadliwy, ponieważ można go zastosować identycznie do C ++, ale kompilator C ++, który zoptymalizowałby tę pętlę, nie zostałby zepsuty, ale zgodny.
Konrad Rudolph
52

Musisz wstawić wyrażenie, które może powodować efekt uboczny.

Najprostsze rozwiązanie:

static void die() {
    while(1)
       __asm("");
}

Link Godbolt

P__J__
źródło
21
Nie tłumaczy jednak, dlaczego działa brzęk.
Lundin
4
Wystarczy jednak powiedzieć „to błąd w brzęczeniu”. Chciałbym jednak najpierw wypróbować kilka rzeczy, zanim zacznę krzyczeć „błąd”.
Lundin
3
@Lundin Nie wiem, czy to błąd. Standard nie jest technicznie precyzyjny w tym przypadku
P__J__
4
Na szczęście GCC jest oprogramowaniem typu open source i mogę napisać kompilator, który zoptymalizuje twój przykład. I mógłbym to zrobić dla każdego przykładu, jaki wymyślisz, teraz iw przyszłości.
Thomas Weller
3
@ThomasWeller: deweloperzy GCC nie zaakceptują łatki optymalizującej tę pętlę; naruszyłoby to udokumentowane = zachowanie gwarantowane. Zobacz mój poprzedni komentarz: asm("")jest niejawny, asm volatile("");a zatem instrukcja asm musi być uruchamiana tyle razy, ile dzieje się na abstrakcyjnej maszynie gcc.gnu.org/onlinedocs/gcc/Basic-Asm.html . (Pamiętaj, że nie jest bezpieczne, aby skutki uboczne obejmowały pamięć lub rejestry; potrzebujesz Extended asm z "memory"clobber, jeśli chcesz czytać lub zapisywać pamięć, do której kiedykolwiek masz dostęp z C. Basic asm jest bezpieczny tylko dla rzeczy takich jak asm("mfence")lub cli.)
Peter Cordes
50

Inne odpowiedzi zawierały już sposoby na to, aby Clang emitował nieskończoną pętlę z wbudowanym językiem asemblera lub innymi efektami ubocznymi. Chcę tylko potwierdzić, że to rzeczywiście błąd kompilatora. W szczególności jest to długotrwały błąd LLVM - stosuje koncepcję C ++ „wszystkie pętle bez efektów ubocznych muszą się kończyć” w językach, w których nie powinien, takich jak C.

Na przykład język programowania Rust pozwala również na nieskończone pętle i wykorzystuje LLVM jako backend i ma ten sam problem.

W krótkim okresie wydaje się, że LLVM będzie nadal zakładać, że „wszystkie pętle bez skutków ubocznych muszą się zakończyć”. Dla każdego języka, który zezwala na nieskończone pętle, LLVM oczekuje, że front-end wstawi llvm.sideeffectkody do takich pętli. To właśnie planuje zrobić Rust, więc Clang (podczas kompilacji kodu C) prawdopodobnie będzie musiał to zrobić.

Arnavion
źródło
5
Nie ma to jak zapach błędu starszego niż dekada ... z wieloma proponowanymi poprawkami i łatkami ... ale wciąż nie został naprawiony.
Ian Kemp
4
@IanKemp: Aby naprawić błąd, trzeba będzie teraz potwierdzić, że naprawienie błędu zajęło dziesięć lat. Lepiej mieć nadzieję, że Standard się zmieni, aby uzasadnić swoje zachowanie. Oczywiście, nawet jeśli standard się zmienił, nadal nie usprawiedliwiałoby to jego zachowania, chyba że w oczach osób, które uznałyby zmianę standardu za wskazówkę, że wcześniejszy mandat behawioralny normy był wadą, którą należy naprawić z mocą wsteczną.
supercat
4
Zostało „naprawione” w tym sensie, że LLVM dodał sideeffectoperację (w 2017 r.) I oczekuje, że interfejsy wstawią tę operację w pętle według własnego uznania. LLVM musiał wybrać pewne domyślne ustawienia dla pętli i zdarzyło się wybrać taki, który jest zgodny z zachowaniem C ++, celowo lub w inny sposób. Oczywiście pozostało jeszcze wiele do zrobienia optymalizacji, na przykład połączenie kolejnych sideeffectoperacji w jeden. (To właśnie blokuje korzystanie z frontonu przez Rust.) Na tej podstawie błąd znajduje się w interfejsie (clang), który nie wstawia op w pętle.
Arnavion
@Arnavion: Czy jest jakiś sposób na wskazanie, że operacje mogą zostać odroczone, chyba że wyniki zostaną użyte, lub dopóki nie zostaną użyte, ale jeśli dane spowodowałyby nieskończone zapętlenie programu, próba przejścia przez zależności między danymi sprawiłaby, że program byłby gorszy niż bezużyteczny ? Konieczność dodawania fałszywych efektów ubocznych, które uniemożliwiałyby wcześniejsze użyteczne optymalizacje, aby optymalizator nie spowodował, że program był gorszy niż bezużyteczny, nie brzmi jak przepis na wydajność.
supercat
Ta dyskusja prawdopodobnie należy do list mailingowych LLVM / clang. FWIW, zatwierdzenie LLVM, które dodało operację, nauczyło również kilku przejść optymalizacji. Ponadto Rust eksperymentował z wstawianiem sideeffectoperacji na początku każdej funkcji i nie widział regresji wydajności środowiska wykonawczego. Jedynym problemem jest kompilacja regresji czasu , najwyraźniej z powodu braku połączenia kolejnych operacji, jak wspomniałem w poprzednim komentarzu.
Arnavion
32

To jest błąd Clanga

... podczas wstawiania funkcji zawierającej nieskończoną pętlę. Zachowanie jest inne, gdy while(1);pojawia się bezpośrednio w głównym, który pachnie dla mnie bardzo błędnie.

Zobacz odpowiedź @ Arnavion na podsumowanie i linki. Reszta tej odpowiedzi została napisana, zanim otrzymałem potwierdzenie, że był to błąd, a tym bardziej znany błąd.


Aby odpowiedzieć na pytanie tytułowe: Jak utworzyć nieskończoną pustą pętlę, która nie będzie zoptymalizowana? ? -
utworzyć die()makro, a nie funkcję , aby obejść ten błąd w Clang 3.9 i nowszych. (Wcześniejsze wersje Clanga albo utrzymywały pętlę, albo wysyłały „a”call do nieliniowej wersji funkcji z nieskończoną pętlą.) Wydaje się to bezpieczne, nawet jeśli print;while(1);print;funkcja włącza się w jej wywołującym ( Godbolt ). -std=gnu11vs. -std=gnu99nic nie zmienia.

Jeśli zależy ci tylko na GNU C, P__J ____asm__(""); wewnątrz pętli również działa i nie powinno zaszkodzić optymalizacji żadnego otaczającego kodu dla żadnego kompilatora, który go rozumie. Podstawowe instrukcje asm GNU C Basic są domyślnievolatile , więc liczy się to jako widoczny efekt uboczny, który musi „wykonać” tyle razy, ile by to miało miejsce w maszynie abstrakcyjnej C. (I tak, Clang implementuje dialekt GNU języka C, jak udokumentowano w instrukcji GCC.)


Niektórzy twierdzą, że optymalizacja pustej nieskończonej pętli może być legalna. Nie zgadzam się 1 , ale nawet jeśli to zaakceptujemy, Clang nie może również legalnie zakładać, że instrukcje po osiągnięciu pętli są nieosiągalne, i pozwolić , aby wykonanie spadło z końca funkcji do następnej lub do śmieci który dekoduje jako losowe instrukcje.

(Byłoby to zgodne ze standardami dla Clang ++ (ale nadal niezbyt przydatne); nieskończone pętle bez żadnych skutków ubocznych są UB w C ++, ale nie C.
Jest while (1); niezdefiniowane zachowanie w C? UB pozwala kompilatorowi emitować praktycznie wszystko dla kodu na ścieżce wykonania, która na pewno napotka UB. asmInstrukcja w pętli unikałaby tego UB dla C ++. Ale w praktyce Clang kompiluje jako C ++ nie usuwa nieskończonych pustych pętli o stałym wyrażeniu, z wyjątkiem wstawiania, tak jak wtedy, gdy kompilacja jako C.)


Ręczne wstawianie while(1);zmienia sposób kompilacji Clanga: nieskończona pętla obecna w asm. Tego oczekujemy od prawnika POV.

#include <stdio.h>
int main() {
    printf("begin\n");
    while(1);
    //infloop_nonconst(1);
    //infloop();
    printf("unreachable\n");
}

W eksploratorze kompilatorów Godbolt Clang 9.0 -O3 kompiluje się jako C ( -xc) dla x86-64:

main:                                   # @main
        push    rax                       # re-align the stack by 16
        mov     edi, offset .Lstr         # non-PIE executable can use 32-bit absolute addresses
        call    puts
.LBB3_1:                                # =>This Inner Loop Header: Depth=1
        jmp     .LBB3_1                   # infinite loop


.section .rodata
 ...
.Lstr:
        .asciz  "begin"

Ten sam kompilator z tymi samymi opcjami kompiluje najpierw ten , mainktóry wywołuje infloop() { while(1); }ten sam puts, ale potem przestaje wydawać instrukcje dla maintego punktu. Tak jak powiedziałem, wykonanie po prostu spada z końca funkcji, do dowolnej funkcji, która będzie następna (ale przy stosie przesuniętym względem wejścia funkcji, więc nie jest to nawet poprawne wywołanie ogona).

Prawidłowe opcje to

  • emitują label: jmp labelnieskończoną pętlę
  • lub (jeśli zaakceptujemy, że nieskończona pętla może zostać usunięta) wysyłamy kolejne wywołanie, aby wydrukować 2. ciąg, a następnie return 0z main.

Awaria lub kontynuacja bez drukowania „nieosiągalnego” najwyraźniej nie jest odpowiednia dla implementacji C11, chyba że istnieje UB, którego nie zauważyłem.


Przypis 1:

Dla przypomnienia, zgadzam się z odpowiedzią @ Lundin, która przytacza standard dla dowodów, że C11 nie pozwala na założenie zakończenia dla nieskończonych pętli o stałym wyrażeniu, nawet gdy są one puste (brak we / wy, niestabilność, synchronizacja lub inne widoczne efekty uboczne).

Jest to zestaw warunków, które pozwoliłyby skompilować pętlę do pustej pętli asm dla normalnego procesora. (Nawet jeśli treść nie była pusta w źródle, przypisania do zmiennych nie mogą być widoczne dla innych wątków lub procedur obsługi sygnałów bez UB wyścigu danych, gdy pętla jest uruchomiona. Zatem zgodna implementacja mogłaby usunąć takie treści pętli, gdyby chciała To pozostawia pytanie, czy samą pętlę można usunąć. ISO C11 wyraźnie mówi nie.)

Biorąc pod uwagę, że C11 wyróżnia ten przypadek jako przypadek, w którym implementacja nie może zakładać, że pętla się kończy (i że nie jest to UB), wydaje się jasne, że zamierzają być obecni w pętli w czasie wykonywania. Implementacja ukierunkowana na procesory z modelem wykonania, który nie może wykonać nieskończonej ilości pracy w skończonym czasie, nie ma uzasadnienia dla usuwania pustej stałej pętli nieskończonej. Lub nawet ogólnie, dokładne sformułowanie dotyczy tego, czy można je „założyć, że wygasną”, czy nie. Jeśli pętla nie może się zakończyć, oznacza to, że późniejszy kod jest nieosiągalny, bez względu na argumenty dotyczące matematyki i nieskończoności oraz czas potrzebny na wykonanie nieskończonej ilości pracy na jakiejś hipotetycznej maszynie.

Co więcej, Clang nie jest jedynie DeathStation 9000 zgodnym z ISO C, ale ma być przydatny do programowania systemów niskopoziomowych w świecie rzeczywistym, w tym do jąder i osadzonych elementów. Niezależnie od tego, czy akceptujesz argumenty dotyczące C11 zezwalające na usunięcie while(1);, nie ma sensu, aby Clang chciał to zrobić. Jeśli napiszesz while(1);, to prawdopodobnie nie był wypadek. Usuwanie pętli, które przypadkowo kończą się nieskończonością (z wyrażeniami kontrolnymi zmiennych wykonawczych), może być przydatne i ma to sens dla kompilatorów.

Rzadko zdarza się, że chcesz się kręcić do następnego przerwania, ale jeśli napiszesz to w C, to na pewno tego się spodziewasz. (I co dzieje się w GCC i Clang, z wyjątkiem Clanga, gdy nieskończona pętla znajduje się w funkcji otoki).

Na przykład w prymitywnym jądrze systemu operacyjnego, gdy program planujący nie ma zadań do uruchomienia, może uruchomić zadanie bezczynne. Pierwszą implementacją tego może być while(1);.

Lub w przypadku sprzętu bez funkcji bezczynności oszczędzania energii, może to być jedyna implementacja. (Do wczesnych lat 2000., tak myślę, nie było to rzadkie na x86. Chociaż hltinstrukcja istniała, IDK jeśli oszczędzał znaczącą ilość energii, dopóki procesory nie zaczęły mieć stanów bezczynności o niskiej mocy).

Peter Cordes
źródło
1
Z ciekawości, czy ktoś faktycznie używa clang do systemów wbudowanych? Nigdy tego nie widziałem i pracuję wyłącznie z osadzonymi. gcc dopiero niedawno (10 lat temu) weszło na rynek wbudowany i używam go sceptycznie, najlepiej z niskimi optymalizacjami i zawsze z -ffreestanding -fno-strict-aliasing. Działa dobrze z ARM i być może ze starszą AVR.
Lundin
1
@Lundin: IDK o osadzonych, ale tak, ludzie budują jądra z clang, przynajmniej czasami Linux. Prawdopodobnie także Darwin na MacOS.
Peter Cordes
2
bugs.llvm.org/show_bug.cgi?id=965 ten błąd wygląda na istotny, ale nie jestem pewien, czy to właśnie tutaj widzimy.
bracco23
1
@lundin - Jestem prawie pewien, że korzystaliśmy z GCC (i wielu innych zestawów narzędzi) do pracy osadzonej przez całe lata 90-te, z RTOS jak VxWorks i PSOS. Nie rozumiem, dlaczego mówisz, że GCC niedawno weszło na rynek urządzeń wbudowanych.
Jeff Learman
1
@JeffLearman W takim razie ostatnio stałeś się głównym nurtem? W każdym razie fiasko ścisłego aliasingu gcc miało miejsce dopiero po wprowadzeniu C99, a nowsze wersje nie wydają się już bananami po napotkaniu surowych naruszeń aliasingu. Mimo to jestem sceptyczny, ilekroć go używam. Jeśli chodzi o clang, najnowsza wersja jest najwyraźniej całkowicie zepsuta, jeśli chodzi o wieczne pętle, więc nie można jej używać w systemach osadzonych.
Lundin
14

Dla przypomnienia Clang również źle się zachowuje goto:

static void die() {
nasty:
    goto nasty;
}

int main() {
    int x; printf("begin\n");
    die();
    printf("unreachable\n");
}

Daje takie same wyniki jak w pytaniu, tj .:

main: # @main
  push rax
  mov edi, offset .Lstr
  call puts
.Lstr:
  .asciz "begin"

Widzę, że nie widzę żadnego sposobu, aby odczytać to jako dozwolone w C11, który mówi tylko:

6.8.6.1 (2) gotoInstrukcja powoduje bezwarunkowy skok do instrukcji poprzedzonej nazwaną etykietą w funkcji zamykającej.

Ponieważ gotonie jest to „oświadczenie iteracja” (6.8.5 listy while, doa for) nic o specjalnej „ustanie-zakłada” odpusty stosuje się jednak chcesz je przeczytać.

Według oryginalnego pytania kompilator Godbolt link to x86-64 Clang 9.0.0 i flagi są -g -o output.s -mllvm --x86-asm-syntax=intel -S --gcc-toolchain=/opt/compiler-explorer/gcc-9.2.0 -fcolor-diagnostics -fno-crash-diagnostics -O2 -std=c11 example.c

Z innymi, takimi jak x86-64 GCC 9.2, otrzymujesz całkiem nieźle idealny:

.LC0:
  .string "begin"
main:
  sub rsp, 8
  mov edi, OFFSET FLAT:.LC0
  call puts
.L2:
  jmp .L2

Flagi: -g -o output.s -masm=intel -S -fdiagnostics-color=always -O2 -std=c11 example.c

jonathanjo
źródło
Zgodna implementacja może mieć nieudokumentowane ograniczenie translacji czasu wykonywania lub cykli procesora, które może spowodować dowolne zachowanie, jeśli zostanie przekroczone, lub jeśli wejściowe programy przekroczą limit nieuchronnie. Takie rzeczy są kwestią Jakości Wdrożenia, poza jurysdykcją Standardu. Wydaje się dziwne, że opiekunowie clang tak bardzo nalegają na swoje prawo do wykonania niskiej jakości implementacji, ale Standard na to zezwala.
supercat
2
@ superuper dzięki za komentarz ... dlaczego przekroczenie limitu tłumaczeń miałoby zrobić coś innego niż nieudana faza tłumaczenia i odmówić wykonania? Ponadto: „ 5.1.1.3 Diagnostyka Zgodna implementacja powinna wygenerować… komunikat diagnostyczny… jeśli jednostka tłumacząca lub jednostka tłumacząca zawiera naruszenie jakiejkolwiek reguły lub ograniczenia składni …”. Nie widzę, jak błędne zachowanie na etapie wykonania może się kiedykolwiek dostosować.
jonathanjo
Norma byłaby całkowicie niemożliwa do wdrożenia, gdyby wszystkie ograniczenia implementacji musiały zostać rozwiązane w czasie kompilacji, ponieważ można by napisać program ściśle zgodny, który wymagałby więcej bajtów stosu niż atomów we wszechświecie. Nie jest jasne, czy ograniczenia czasu wykonywania należy łączyć z „limitami tłumaczeń”, ale taka koncesja jest wyraźnie konieczna i nie ma innej kategorii, w której można by ją umieścić.
supercat
1
Odpowiedziałem na twój komentarz dotyczący „limitów tłumaczeń”. Oczywiście istnieją również limity wykonania, przyznaję, że nie rozumiem, dlaczego sugerujesz, że należy je łączyć z limitami tłumaczeń lub dlaczego uważasz, że jest to konieczne. Po prostu nie widzę żadnego powodu, aby mówić, że nasty: goto nastymoże być zgodny i nie obracać procesora (CPU), dopóki interwencja użytkownika lub zasoby nie zainterweniuje.
jonathanjo
1
Standard nie zawiera odniesienia do „limitów wykonania”, które mogłem znaleźć. Rzeczy takie jak wywołanie funkcji zagnieżdżania są zazwyczaj obsługiwane przez alokacji stosu, ale Wykonanie zgodne limity wywołania funkcji głębokości 16 mógł zbudować 16 kopii każdej funkcji i mają połączenia do bar()wewnątrz foo()być przetwarzane jako wezwanie __1foodo __2barod __2foodo __3bar, itd. i od __16foodo __launch_nasal_demons, co pozwoliłoby na statyczne przydzielenie wszystkich automatycznych obiektów i spowodowałoby, że zwykle limit czasu wykonywania stałby się limitem translacji.
supercat
5

Wcielę się w adwokata diabła i argumentuję, że standard nie zabrania kompilatorowi optymalizacji nieskończonej pętli.

Instrukcja iteracyjna, której wyrażenie kontrolne nie jest wyrażeniem stałym, 156), które nie wykonuje żadnych operacji wejścia / wyjścia, nie ma dostępu do obiektów lotnych i nie wykonuje żadnych synchronizacji ani operacji atomowych w swoim ciele, kontroluje wyrażenie lub (w przypadku instrukcja) jego wyrażenie-3 może zostać przyjęte przez implementację jako terminate.157)

Przeanalizujmy to. Można przyjąć, że wypowiedź iteracyjna, która spełnia określone kryteria, kończy się:

if (satisfiesCriteriaForTerminatingEh(a_loop)) 
    if (whatever_reason_or_just_because_you_feel_like_it)
         assumeTerminates(a_loop);

Nie mówi to nic o tym, co się stanie, jeśli kryteria nie zostaną spełnione, a zakładanie, że pętla może się zakończyć nawet wtedy nie jest wyraźnie zabronione, o ile przestrzegane są inne reguły standardu.

do { } while(0)lub while(0){}są przecież instrukcjami iteracyjnymi (pętlami), które nie spełniają kryteriów, które pozwalają kompilatorowi na przyjęcie kaprysu, że kończą, a jednak oczywiście kończą.

Ale czy kompilator może po prostu zoptymalizować while(1){}?

5.1.2.3p4 mówi:

W maszynie abstrakcyjnej wszystkie wyrażenia są obliczane zgodnie z semantyką. Rzeczywista implementacja nie musi oceniać części wyrażenia, jeśli można wywnioskować, że jego wartość nie jest używana i że nie powstają żadne potrzebne skutki uboczne (w tym wszelkie wywołane wywołaniem funkcji lub dostępem do lotnego obiektu).

Wspomina o wyrażeniach, a nie o wyrażeniach, więc nie jest w 100% przekonujący, ale z pewnością umożliwia wywołania takie jak:

void loop(void){ loop(); }

int main()
{
    loop();
}

do pominięcia. Co ciekawe, clang go pomija, a gcc nie .

PSkocik
źródło
„Nie mówi to nic o tym, co się stanie, jeśli kryteria nie zostaną spełnione”, ale tak jest, 6.8.5.1 Instrukcja while: „Ocena wyrażenia kontrolnego odbywa się przed każdym wykonaniem treści pętli”. Otóż ​​to. Jest to obliczanie wartości (ciągłego wyrażenia), podlega zasadzie abstrakcyjnej maszyny 5.1.2.3, która definiuje pojęcie oceny: „ Ogólna ocena wyrażenia obejmuje zarówno obliczenia wartości, jak i inicjację skutków ubocznych”. I zgodnie z tym samym rozdziałem wszystkie takie oceny są sekwencjonowane i oceniane zgodnie z semantyką.
Lundin
1
@Lundin Czy zatem while(1){}nieskończona sekwencja 1ocen przeplata się z {}ocenami, ale gdzie w normie mówi się, że oceny te muszą zająć niezerowy czas? Sądzę, że zachowanie gcc jest bardziej przydatne, ponieważ nie potrzebujesz sztuczek związanych z dostępem do pamięci lub sztuczek poza językiem. Ale nie jestem przekonany, że standard zabrania tej optymalizacji w clang. Jeśli while(1){}intencją jest nieoptymalizowanie, norma powinna być jednoznacznie na ten temat, a nieskończone zapętlenie powinno być wymienione jako zauważalny efekt uboczny w 5.1.2.3p2.
PSkocik
1
Myślę, że jest określony, jeśli traktujesz 1warunek jako obliczenie wartości. Czas wykonania nie ma znaczenia - liczy się to, co while(A){} B;może nie być zoptymalizowane z dala całkowicie, nie zoptymalizowane B;i nie re-sekwencjonowaniu w celu B; while(A){}. Cytując maszynę abstrakcyjną C11, podkreśl moją: „Obecność punktu sekwencji między oceną wyrażeń A i B oznacza, że każde obliczenie wartości i efekt uboczny związany z A jest sekwencjonowane przed każdym obliczeniem wartości i efektem ubocznym związanym z B ”. Wartość Ajest wyraźnie używana (przez pętlę).
Lundin
2
+1 Chociaż wydaje mi się, że „wykonanie zawiesza się w nieskończoność bez żadnego wyniku” jest „efektem ubocznym” w dowolnej definicji „efektu ubocznego”, który ma sens i jest użyteczny poza standardem w próżni, pomaga to wyjaśnić sposób myślenia, z którego może to mieć dla kogoś sens.
mtraceur
1
W pobliżu „optymalizacji nieskończonej pętli” : Nie jest całkowicie jasne, czy „to” odnosi się do standardu czy kompilatora - być może przeformułowania? Biorąc pod uwagę „chociaż prawdopodobnie powinno”, a nie „chociaż prawdopodobnie nie powinno” , prawdopodobnie jest to standard, do którego odnosi się „to” .
Peter Mortensen
2

Byłem przekonany, że to zwykły stary błąd. Moje testy zostawiam poniżej, w szczególności odniesienie do dyskusji w komisji standardowej z pewnych powodów, które wcześniej miałem.


Myślę, że jest to niezdefiniowane zachowanie (patrz koniec), a Clang ma tylko jedną implementację. GCC rzeczywiście działa zgodnie z oczekiwaniami, optymalizując tylko instrukcję unreachableprint, ale pozostawiając pętlę. Trochę dziwnego sposobu, w jaki Clang dziwnie podejmuje decyzje, łącząc wstawianie i określając, co może zrobić z pętlą.

Zachowanie jest wyjątkowo dziwne - usuwa końcowy nadruk, więc „widzi” nieskończoną pętlę, ale także pozbywa się jej.

O ile mogę powiedzieć, jest jeszcze gorzej. Usuwając wstawkę otrzymujemy:

die: # @die
.LBB0_1: # =>This Inner Loop Header: Depth=1
  jmp .LBB0_1
main: # @main
  push rax
  mov edi, offset .Lstr
  call puts
.Lstr:
  .asciz "begin"

więc funkcja została utworzona, a połączenie zoptymalizowane. Jest to nawet bardziej odporne niż oczekiwano:

#include <stdio.h>

void die(int x) {
    while(x);
}

int main() {
    printf("begin\n");
    die(1);
    printf("unreachable\n");
}

skutkuje bardzo nieoptymalnym zestawem funkcji, ale wywołanie funkcji jest ponownie zoptymalizowane! Nawet gorzej:

void die(x) {
    while(x++);
}

int main() {
    printf("begin\n");
    die(1);
    printf("unreachable\n");
}

Zrobiłem kilka innych testów, dodając zmienną lokalną i zwiększając ją, przekazując wskaźnik, używając gotoetc ... W tym momencie zrezygnowałem. Jeśli musisz użyć clang

static void die() {
    int volatile x = 1;
    while(x);
}

wykonuje pracę. Jest do bani w optymalizacji (oczywiście) i pozostawia zbędny finał printf. Przynajmniej program się nie zatrzymuje. Może w końcu GCC?

Uzupełnienie

Po dyskusji z Davidem stwierdzam, że standard nie mówi „jeśli warunek jest stały, możesz nie założyć, że pętla się kończy”. Jako taki, i zgodnie ze standardem nie ma obserwowalnego zachowania (jak zdefiniowano w standardzie), argumentowałbym tylko za spójnością - jeśli kompilator optymalizuje pętlę, ponieważ zakłada, że ​​się kończy, nie powinien optymalizować następujących instrukcji.

Heck n1528 ma to jako niezdefiniowane zachowanie, jeśli dobrze to przeczytam. konkretnie

Głównym problemem jest to, że pozwala on na przemieszczanie się kodu w potencjalnie nie kończącej się pętli

Odtąd myślę, że może ona przerodzić się w dyskusję o tym, czego chcemy (oczekiwaliśmy?), A nie o to, co jest dozwolone.

kabanus
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Bhargav Rao
Re „zwykły cały błąd” : Czy masz na myśli zwykły stary błąd” ?
Peter Mortensen
@PeterMortensen „ole” również byłby ze mną w porządku.
kabanus
2

Wygląda na to, że jest to błąd w kompilatorze Clanga. Jeśli nie ma żadnego przymusu, aby die()funkcja była funkcją statyczną, usuń ją statici zrób to inline:

#include <stdio.h>

inline void die(void) {
    while(1)
        ;
}

int main(void) {
    printf("begin\n");
    die();
    printf("unreachable\n");
}

Działa zgodnie z oczekiwaniami po kompilacji z kompilatorem Clang, a także jest przenośny.

Eksplorator kompilatorów (godbolt.org) - klang 9.0.0-O3 -std=c11 -pedantic-errors

main:                                   # @main
        push    rax
        mov     edi, offset .Lstr
        call    puts
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        jmp     .LBB0_1
.Lstr:
        .asciz  "begin"
HS
źródło
Co static inline?
SS Anne
1

Wydaje się, że dla mnie działają:

#include <stdio.h>

__attribute__ ((optnone))
static void die(void) {
    while (1) ;
}

int main(void) {
    printf("begin\n");
    die();
    printf("unreachable\n");
}

w godbolt

Jawne mówienie Clangowi, aby nie optymalizował, że jedna funkcja powoduje, że nieskończona pętla jest emitowana zgodnie z oczekiwaniami. Mamy nadzieję, że istnieje sposób, aby selektywnie wyłączyć poszczególne optymalizacje zamiast po prostu je wszystkie wyłączyć. Jednak Clang nadal odmawia wydania kodu dla drugiego printf. Aby to zmusić, musiałem dodatkowo zmodyfikować kod wewnątrz, mainaby:

volatile int x = 0;
if (x == 0)
    die();

Wygląda na to, że musisz wyłączyć optymalizacje dla funkcji nieskończonej pętli, a następnie upewnić się, że twoja nieskończona pętla jest wywoływana warunkowo. W prawdziwym świecie i tak jest to prawie zawsze.

bta
źródło
1
Nie jest konieczne printfgenerowanie drugiego, jeśli pętla rzeczywiście trwa wiecznie, ponieważ w takim przypadku drugi printfnaprawdę jest nieosiągalny i dlatego można go usunąć. (Błąd Clanga polega zarówno na wykryciu nieosiągalności, jak i na usunięciu pętli, aby osiągnąć nieosiągalny kod).
nneonneo
Dokumenty GCC __attribute__ ((optimize(1))), ale clang ignoruje je jako nieobsługiwane: godbolt.org/z/4ba2HM . gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html
Peter Cordes
0

Implementacja zgodna może, i wiele praktycznych, może narzucić dowolne limity czasu trwania programu lub liczby instrukcji, które wykona, i zachowywać się w sposób arbitralny, jeśli limity te zostaną naruszone lub - zgodnie z zasadą „jak gdyby” - jeśli stwierdzi, że zostaną one nieuchronnie naruszone. Pod warunkiem, że wdrożenie może z powodzeniem przetworzyć co najmniej jeden program, który nominalnie wykonuje wszystkie limity wymienione w N1570 5.2.4.1, nie przekraczając żadnych limitów translacji, istnienia limitów, zakresu ich udokumentowania i skutków ich przekroczenia są: wszystkie kwestie dotyczące jakości wdrożenia poza jurysdykcją normy.

Myślę, że intencja Standardu jest całkiem jasna, że ​​kompilatory nie powinny zakładać, że while(1) {}pętla bez efektów ubocznych i breakinstrukcji nie zostanie zakończona. Wbrew temu, co niektórzy mogą sądzić, autorzy Standardu nie zapraszali pisarzy kompilatorów, aby byli głupi lub tępi. Implementacja zgodna może być przydatna do podjęcia decyzji o zakończeniu dowolnego programu, który, jeśli nie zostanie przerwany, wykona więcej instrukcji wolnych od skutków ubocznych niż atomów we wszechświecie, ale implementacja wysokiej jakości nie powinna wykonywać takich działań na podstawie jakichkolwiek założeń dotyczących zakończenie, ale raczej na tej podstawie, że może to być przydatne i nie byłoby (w przeciwieństwie do zachowania klanu) gorsze niż bezużyteczne.

supercat
źródło
-2

Pętla nie ma skutków ubocznych, dlatego można ją zoptymalizować. Pętla jest w rzeczywistości nieskończoną liczbą iteracji zerowych jednostek pracy. Jest to niezdefiniowane w matematyce i logice, a standard nie mówi, czy implementacja jest dozwolona do wykonania nieskończonej liczby rzeczy, jeśli każda rzecz może być wykonana w czasie zerowym. Interpretacja Clanga jest całkowicie rozsądna w traktowaniu nieskończoności razy zero jako nieskończoności. Standard nie mówi, czy nieskończona pętla może się zakończyć, jeśli cała praca w pętli zostanie faktycznie zakończona.

Kompilator może optymalizować wszystko, co nie jest możliwe do zaobserwowania, zgodnie z definicją zawartą w standardzie. Obejmuje to czas wykonania. Nie jest konieczne zachowanie faktu, że pętla, jeśli nie zostanie zoptymalizowana, zajmie nieskończoną ilość czasu. Dozwolone jest zmienianie tego na znacznie krótszy czas działania - w rzeczywistości jest to punkt większości optymalizacji. Twoja pętla została zoptymalizowana.

Nawet jeśli clang przetłumaczył kod naiwnie, można sobie wyobrazić optymalizujący procesor, który może ukończyć każdą iterację w połowie czasu poprzedniej iteracji. To dosłownie uzupełniłoby nieskończoną pętlę w skończonym czasie. Czy taki optymalizujący procesor narusza standard? Absurdalne wydaje się stwierdzenie, że optymalizujący procesor naruszyłby standard, jeśli jest zbyt dobry w optymalizacji. To samo dotyczy kompilatora.

David Schwartz
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Samuel Liew
4
Sądząc z twojego doświadczenia (z twojego profilu) mogę jedynie stwierdzić, że ten post został napisany w złej wierze, tylko w celu obrony kompilatora. Poważnie argumentujesz, że coś, co zajmuje nieskończoną ilość czasu, można zoptymalizować w celu wykonania w połowie tego czasu. To niedorzeczne na każdym poziomie i wiesz o tym.
rura
@pipe: Myślę, że opiekunowie clang i gcc mają nadzieję, że przyszła wersja Standardu pozwoli na zachowanie ich kompilatorów, a opiekunowie tych kompilatorów będą mogli udawać, że taka zmiana była jedynie korektą długotrwałej usterki w standardzie. Tak na przykład potraktowali gwarancje wspólnej sekwencji początkowej C89.
supercat
@SSAnne: Hmm ... Nie sądzę, że to wystarcza, aby zablokować niektóre niesłuszne wnioski gcc i clang wyciągnąć z wyników porównań wskaźnik-równość.
supercat
@ superuper Istnieje <s> innych </s> ton.
SS Anne
-2

Przepraszam, jeśli tak absurdalnie nie jest, natknąłem się na ten post i wiem, ponieważ moje lata z dystrybucją Gentoo Linux, że jeśli chcesz, aby kompilator nie zoptymalizował twojego kodu, powinieneś użyć opcji -O0 (zero). Byłem ciekawy tego, skompilowałem i uruchomiłem powyższy kod, a pętla robi się bez końca. Kompilacja przy użyciu clang-9:

cc -O0 -std=c11 test.c -o test
Fellipe Weno
źródło
1
Chodzi o to, aby stworzyć nieskończoną pętlę z włączonymi optymalizacjami.
SS Anne
-4

Pusta whilepętla nie ma żadnych skutków ubocznych w systemie.

Dlatego Clang go usuwa. Istnieją „lepsze” sposoby osiągnięcia zamierzonego zachowania, które zmuszają cię do bardziej oczywistych zamiarów.

while(1); jest baaadd.

Znani Jamei
źródło
6
W wielu wbudowanych konstrukcjach nie ma koncepcji abort()lub exit(). Jeśli pojawi się sytuacja, w której funkcja ustali, że (być może w wyniku uszkodzenia pamięci) dalsze wykonywanie byłoby gorsze niż niebezpieczne, częstym domyślnym zachowaniem bibliotek osadzonych jest wywoływanie funkcji, która wykonuje funkcję while(1);. Może to być przydatne dla kompilatora mieć opcje , aby zastąpić bardziej przydatnych zachowań, ale każdy pisarz kompilator, którzy nie mogą dowiedzieć się, jak traktować taką prostą konstrukcję jako bariera dla dalszego wykonywania programu jest niekompetentny można ufać złożonych optymalizacje.
supercat
Czy istnieje sposób, abyś mógł bardziej wyrazić swoje zamiary? optymalizator służy do optymalizacji programu, a usuwanie zbędnych pętli, które nic nie robią, JEST optymalizacją. jest to naprawdę filozoficzna różnica między abstrakcyjnym myśleniem świata matematyki a bardziej stosowanym światem inżynierii.
Słynny Jameis
Większość programów ma zestaw przydatnych akcji, które powinny wykonać, gdy jest to możliwe, oraz zestaw gorszych niż bezużytecznych akcji, których nigdy nie mogą wykonać w żadnych okolicznościach. Wiele programów ma zestaw akceptowalnych zachowań w każdym konkretnym przypadku, z których jeden, jeśli czas wykonania nie jest możliwy do zaobserwowania, zawsze byłby „odczekać dowolnie, a następnie wykonać jakąś akcję z zestawu”. Gdyby wszystkie działania inne niż oczekiwanie były zestawem gorszych niż bezużyteczne działań, nie byłoby liczby sekund N, dla których „czekanie wieczne” byłoby
wyraźnie
... „poczekaj N + 1 sekundę, a następnie wykonaj inną akcję”, więc nie można zaobserwować, że zestaw tolerowanych akcji innych niż oczekiwanie jest pusty. Z drugiej strony, jeśli fragment kodu usunie pewną niedopuszczalną akcję z zestawu możliwych akcji, a jedna z tych akcji zostanie mimo to wykonana , należy to uznać za obserwowalne. Niestety, reguły języka C i C ++ używają słowa „zakładaj” w dziwny sposób, w przeciwieństwie do innych dziedzin logiki lub ludzkich działań, które mogę zidentyfikować.
supercat
1
@FamousJame jest w porządku, ale Clang nie tylko usuwa pętlę - statycznie analizuje wszystko później jako nieosiągalne i wydaje nieprawidłową instrukcję. Nie tego oczekujesz, jeśli po prostu „usunie” pętlę.
nneonneo