Maximale Anzahl an Instruktionen



  • Moin,

    ich hab ne Aufgabe bekommen und weiß nicht so recht wie ich ansetzen soll.

    • A C or C++ program should be written whose compilation according to part 1 generates as
    many LLVM instructions as possible.
    • The program may only consist of one source file whose size is limited to a maximum of 512
    bytes.
    • Only header files from the C++11 standard may be included.

    Hierbei kommen 828 Instruktionen raus:

    #include <atomic>
    #include <memory>
    
    template <typename T> T calc( T a, T b )
    {
      auto i = std::make_unique<T>( a );
      *i = a + b * a / b - a;
      return *i;
    }
    
    int main()
    {
      double d = calc( 2, 3 );
      double d2 = calc( 2u, 3u );
      int i = calc( 2.0, 3.0 );
      unsigned int ui = calc( 2.0, 3.0 );
      intptr_t ptr  = (intptr_t)&i;
      int* ptr2 = (int*)ptr;
      bool b = !i;
      b = !b || d > d2 ? true : false;
      i = i & ( ui | 2 );
      std::atomic_int ai {41};
      ++ai;
      i = (i >> 2) + (i << 2) % 4;
      ui = ui >> 2;
    }
    

    Angeblich sollen problemlos 100000 und mehr möglich sein. Irgendwie steh ich auf dem Schlauch.



  • @Tyrdal sagte in Maximale Anzahl an Instruktionen:

    whose compilation according to part 1

    Part 1 = ?



  • @Tyrdal sagte in Maximale Anzahl an Instruktionen:

    Angeblich sollen problemlos 100000 und mehr möglich sein. Irgendwie steh ich auf dem Schlauch.

    Das ist auch eine Aufgabe, wo es definitiv keine einzig wahre Antwort gibt - ich vermute es ist eher so ein Experimentier-Ding um vertrauter mit dem Code zu werden, den der Compiler erzeugt. Witzige Aufgabe jedenfalls 😉

    Ich würde es mal mit folgendem versuchen: Eine Template-Funktion mit einem Zähler als Parameter, die als __attribute__((always_inline)) markiert ist (falls erlaubt) und sich endrekursiv selbst aufruft. Sowas habe ich schonmal genutzt, als ich via Template-Metaprogrammierung explizit steuerbares Loop Unrolling brauchte.

    Sicher gibts aber auch noch tausende anderer Tricks 😉

    Edit: Bei "LLVM Istructions" bin ich mir aber nicht mehr so sicher, das da oben erzeugt zumindest jede Menge Instruktionen im Maschinencode-Endresultat. Wenn du, wie du schreibst schon am LLVM Optimizer rumgebastelt hast, dann hast du womöglich bessere Ideen als ich, wie man da viele Instruktionen rausbekommt - da klink ich mich aus 😉



  • Ist der wichtig?

    Part 1:
    • For the LLVM compiler i a command line utility should be developed, which outputs the total
    number of LLVM instructions of a C/C++ file.
    • The total number of LLVM instructions should be identical to the number of LLVM
    instructions contained in the file generated by the following command:
    clang++ -O2 -S -emit-llvm test.cpp -o test.ll
    • Hint: You can use the llvm-dis utility as a basis and change its source code accordingly. It can
    call a precompiled clang executable in the background.

    Die Anzahl der Instruktionen bekomme ich ja schon. Dafür hab ich einen FunctionPass für den llvm optimizer gebaut.
    Was mir gerade auffällt ist das Optimierungslevel. Bei -O2 würde er bei mir alles wegoptimieren. Hm.

    Ausgabe wäre sowas:

    clang++-8 -O0 -std=c++11 -emit-llvm max_instructions.cpp -c -o max_instructions.bc;bin/opt -load lib/LLVMCountInstructions.so -CountInstructions < max_instructions.bc > /dev/null
    Instructions: __cxx_global_var_init: 3
    main: 84
    Z4calcIiET_S0_S0: 39
    Z4calcIjET_S0_S0: 39
    Z4calcIdET_S0_S0: 39
    _ZNSt13__atomic_baseIiEppEv: 13
    _ZNKSt13__atomic_baseIiEcviEv: 31
    _ZNSt10unique_ptrIiSt14default_deleteIiEEC2IS1_vEEPi: 13
    _ZNKSt10unique_ptrIiSt14default_deleteIiEEdeEv: 5
    _ZNSt10unique_ptrIiSt14default_deleteIiEED2Ev: 23
    _ZNSt15__uniq_ptr_implIiSt14default_deleteIiEEC2EPi: 11
    __clang_call_terminate: 3
    _ZNSt5tupleIJPiSt14default_deleteIiEEEC2IS0_S2_Lb1EEEv: 6
    _ZNSt15__uniq_ptr_implIiSt14default_deleteIiEE6_M_ptrEv: 6
    _ZNSt11_Tuple_implILm0EJPiSt14default_deleteIiEEEC2Ev: 8
    _ZNSt11_Tuple_implILm1EJSt14default_deleteIiEEEC2Ev: 6
    _ZNSt10_Head_baseILm0EPiLb0EEC2Ev: 6
    _ZNSt10_Head_baseILm1ESt14default_deleteIiELb1EEC2Ev: 5
    ZSt3getILm0EJPiSt14default_deleteIiEEERNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERS7: 6
    _ZSt12__get_helperILm0EPiJSt14default_deleteIiEEERT0_RSt11_Tuple_implIXT_EJS3_DpT1_EE: 5
    ZNSt11_Tuple_implILm0EJPiSt14default_deleteIiEEE7_M_headERS3: 6
    ZNSt10_Head_baseILm0EPiLb0EE7_M_headERS1: 5
    _ZNKSt10unique_ptrIiSt14default_deleteIiEE3getEv: 10
    _ZNKSt15__uniq_ptr_implIiSt14default_deleteIiEE6_M_ptrEv: 7
    ZSt3getILm0EJPiSt14default_deleteIiEEERKNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERKS7: 6
    _ZSt12__get_helperILm0EPiJSt14default_deleteIiEEERKT0_RKSt11_Tuple_implIXT_EJS3_DpT1_EE: 5
    ZNSt11_Tuple_implILm0EJPiSt14default_deleteIiEEE7_M_headERKS3: 6
    ZNSt10_Head_baseILm0EPiLb0EE7_M_headERKS1: 5
    _ZNSt10unique_ptrIiSt14default_deleteIiEE11get_deleterEv: 10
    _ZNKSt14default_deleteIiEclEPi: 12
    _ZNSt15__uniq_ptr_implIiSt14default_deleteIiEE10_M_deleterEv: 6
    ZSt3getILm1EJPiSt14default_deleteIiEEERNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERS7: 6
    _ZSt12__get_helperILm1ESt14default_deleteIiEJEERT0_RSt11_Tuple_implIXT_EJS2_DpT1_EE: 5
    ZNSt11_Tuple_implILm1EJSt14default_deleteIiEEE7_M_headERS2: 6
    ZNSt10_Head_baseILm1ESt14default_deleteIiELb1EE7_M_headERS2: 5
    _ZNSt10unique_ptrIjSt14default_deleteIjEEC2IS1_vEEPj: 13
    _ZNKSt10unique_ptrIjSt14default_deleteIjEEdeEv: 5
    _ZNSt10unique_ptrIjSt14default_deleteIjEED2Ev: 23
    _ZNSt15__uniq_ptr_implIjSt14default_deleteIjEEC2EPj: 11
    _ZNSt5tupleIJPjSt14default_deleteIjEEEC2IS0_S2_Lb1EEEv: 6
    _ZNSt15__uniq_ptr_implIjSt14default_deleteIjEE6_M_ptrEv: 6
    _ZNSt11_Tuple_implILm0EJPjSt14default_deleteIjEEEC2Ev: 8
    _ZNSt11_Tuple_implILm1EJSt14default_deleteIjEEEC2Ev: 6
    _ZNSt10_Head_baseILm0EPjLb0EEC2Ev: 6
    _ZNSt10_Head_baseILm1ESt14default_deleteIjELb1EEC2Ev: 5
    ZSt3getILm0EJPjSt14default_deleteIjEEERNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERS7: 6
    _ZSt12__get_helperILm0EPjJSt14default_deleteIjEEERT0_RSt11_Tuple_implIXT_EJS3_DpT1_EE: 5
    ZNSt11_Tuple_implILm0EJPjSt14default_deleteIjEEE7_M_headERS3: 6
    ZNSt10_Head_baseILm0EPjLb0EE7_M_headERS1: 5
    _ZNKSt10unique_ptrIjSt14default_deleteIjEE3getEv: 10
    _ZNKSt15__uniq_ptr_implIjSt14default_deleteIjEE6_M_ptrEv: 7
    ZSt3getILm0EJPjSt14default_deleteIjEEERKNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERKS7: 6
    _ZSt12__get_helperILm0EPjJSt14default_deleteIjEEERKT0_RKSt11_Tuple_implIXT_EJS3_DpT1_EE: 5
    ZNSt11_Tuple_implILm0EJPjSt14default_deleteIjEEE7_M_headERKS3: 6
    ZNSt10_Head_baseILm0EPjLb0EE7_M_headERKS1: 5
    _ZNSt10unique_ptrIjSt14default_deleteIjEE11get_deleterEv: 10
    _ZNKSt14default_deleteIjEclEPj: 12
    _ZNSt15__uniq_ptr_implIjSt14default_deleteIjEE10_M_deleterEv: 6
    ZSt3getILm1EJPjSt14default_deleteIjEEERNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERS7: 6
    _ZSt12__get_helperILm1ESt14default_deleteIjEJEERT0_RSt11_Tuple_implIXT_EJS2_DpT1_EE: 5
    ZNSt11_Tuple_implILm1EJSt14default_deleteIjEEE7_M_headERS2: 6
    ZNSt10_Head_baseILm1ESt14default_deleteIjELb1EE7_M_headERS2: 5
    _ZNSt10unique_ptrIdSt14default_deleteIdEEC2IS1_vEEPd: 13
    _ZNKSt10unique_ptrIdSt14default_deleteIdEEdeEv: 5
    _ZNSt10unique_ptrIdSt14default_deleteIdEED2Ev: 23
    _ZNSt15__uniq_ptr_implIdSt14default_deleteIdEEC2EPd: 11
    _ZNSt5tupleIJPdSt14default_deleteIdEEEC2IS0_S2_Lb1EEEv: 6
    _ZNSt15__uniq_ptr_implIdSt14default_deleteIdEE6_M_ptrEv: 6
    _ZNSt11_Tuple_implILm0EJPdSt14default_deleteIdEEEC2Ev: 8
    _ZNSt11_Tuple_implILm1EJSt14default_deleteIdEEEC2Ev: 6
    _ZNSt10_Head_baseILm0EPdLb0EEC2Ev: 6
    _ZNSt10_Head_baseILm1ESt14default_deleteIdELb1EEC2Ev: 5
    ZSt3getILm0EJPdSt14default_deleteIdEEERNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERS7: 6
    _ZSt12__get_helperILm0EPdJSt14default_deleteIdEEERT0_RSt11_Tuple_implIXT_EJS3_DpT1_EE: 5
    ZNSt11_Tuple_implILm0EJPdSt14default_deleteIdEEE7_M_headERS3: 6
    ZNSt10_Head_baseILm0EPdLb0EE7_M_headERS1: 5
    _ZNKSt10unique_ptrIdSt14default_deleteIdEE3getEv: 10
    _ZNKSt15__uniq_ptr_implIdSt14default_deleteIdEE6_M_ptrEv: 7
    ZSt3getILm0EJPdSt14default_deleteIdEEERKNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERKS7: 6
    _ZSt12__get_helperILm0EPdJSt14default_deleteIdEEERKT0_RKSt11_Tuple_implIXT_EJS3_DpT1_EE: 5
    ZNSt11_Tuple_implILm0EJPdSt14default_deleteIdEEE7_M_headERKS3: 6
    ZNSt10_Head_baseILm0EPdLb0EE7_M_headERKS1: 5
    _ZNSt10unique_ptrIdSt14default_deleteIdEE11get_deleterEv: 10
    _ZNKSt14default_deleteIdEclEPd: 12
    _ZNSt15__uniq_ptr_implIdSt14default_deleteIdEE10_M_deleterEv: 6
    ZSt3getILm1EJPdSt14default_deleteIdEEERNSt13tuple_elementIXT_ESt5tupleIJDpT0_EEE4typeERS7: 6
    _ZSt12__get_helperILm1ESt14default_deleteIdEJEERT0_RSt11_Tuple_implIXT_EJS2_DpT1_EE: 5
    ZNSt11_Tuple_implILm1EJSt14default_deleteIdEEE7_M_headERS2: 6
    ZNSt10_Head_baseILm1ESt14default_deleteIdELb1EE7_M_headERS2: 5
    _ZStanSt12memory_orderSt23__memory_order_modifier: 8
    _GLOBAL__sub_I_max_instructions.cpp: 2
    Total number of instruction: 861



  • @Tyrdal sagte in Maximale Anzahl an Instruktionen:

    Moin,

    • A C or C++ program should be written whose compilation according to part 1 generates as
    many LLVM instructions as possible.
    Angeblich sollen problemlos 100000 und mehr möglich sein. Irgendwie steh ich auf dem Schlauch.

    Dein Code ist zu einfach.

    Als allererste Maßnahme kannst du make_unique durch make_shared ersetzen. Und dann such dir weitere Algorithmen etc. aus der STL und mach irgendwas damit.

    Sowas wie b = !b || d > d2 ? true : false; und vor allem

    i = (i >> 2) + (i << 2) % 4;
      ui = ui >> 2;
    

    kann doch sicher nicht viel Code generieren.



  • Jut, mit ner map drin kommt schon mehr. Ich verfolg den Gedanken mal.



  • Hilft das hier auch bei LLVM-Instruktionen, oder bläht das nur den erzeugten Maschinencode am Ende der Pipeline auf?

    volatile int x;
    
    template <unsigned N>
    struct F
    {
        __attribute__((always_inline)) static void f()
        {
            // Hier mehr Code zum aufblähen einfügen
            x = x + 1;
            
            F<N - 1>::f();
        }
    };
    
    template <>
    struct F<0>
    {
        static void f() {}
    };
    
    void test()
    {
        F<1000>::f();
    }
    

    https://godbolt.org/z/BgCWep

    Mit dem Template-Argument für N lässt sich der Code quasi beliebig aufblähen - vorausgesetzt __attribute__((always_inline)) ist erlaubt. Ansonsten geht mit dem Ansatz vielleicht trotzdem was, wenn man etwas findet, dass er immer inlinen muss.

    Zusatz: Jo, oder so. Einfach N zu x addieren. Da es volatile ist, muss er jeden addierten Wert einmal schreiben:

    https://godbolt.org/z/R8PasR

    Hoffe das hilft bei den LLVM Instructions in der Aufgabenstellung und ist nicht am eigentlichen Sinn der Aufgabe vorbei - man kan das durchaus als "billigen Trick" werten 😉



  • @Tydral
    Tip 1: Template-Metaprogramming.
    Tip 2: Dicke Template-Schweine aus der Standard-Library verwenden (std::map, std::sort, ...).

    Wobei (1) eigentlich schon reichen sollte.
    Im Prinzip kann man damit das Programm schon gross genug machen. Das Problem wird da vermutlich eher sein dass der Compiler ab einer bestimmten Grösse aufgibt.



  • @Finnegan

    Ich glaub das sollte schon reichen. Und wenn nicht würde ich mal "no inline" statt "always inline" probieren. Bei "always inline" könnte der Compiler am Ende noch schlau genug sein zu sehen dass er das zu einer Schleife zusammenwickeln kann. Also das Gegenteil von Loop-Unrolling. Wobei solche Optimierungen glaube ich von LLVM gemacht werden, d.h. die mega-vielen LLVM Instructions hätte man trotzdem - sie würden nur zu weniger Instructions im Ziel-Format compiliert.



  • Weils so lustig ist, hab ich noch ne kleine Instruktions-Bombe gebaut. 239 Bytes, scheint zuverlässig unter Clang, GCC und MSVC zu funktionieren und sollte mindestens 2E12^E-1 Instruktionen erzeugen:

    constexpr int E = 8;
    using U = unsigned long long;
    volatile U x;
    template <int N, U X = 1>
    struct F { void f() { x+=X+N; F<N-1, X*2>{}.f(); F<N-1, X*2+1>{}.f(); } };
    template <U X> struct F<0, X> { void f() {} };
    int main() { F<E>{}.f(); }
    

    https://godbolt.org/z/VxfcYj

    Aber vorsicht mit dem E, da gibts zumindest bei Godbolt schnell nen Timeout oder nen Out-Of-Memory-Crash 😉

    @hustbaer Danke, wegen der LLVM-Instruktionen war ich mir nicht so ganz sicher, ob damit nicht sowas wie die Intermediate Language des Compilers gemeint sein konnte, wo solche Templates nicht unbedingt bereits voll expandiert sein müssen. Ich sollte mich mal mehr mit LLVM abseits vom Kompilieren mit Clang befassen, das ist ja durchaus ein ganz cooler Werkzeugkasten.



  • Nachdem ich krank war, habe ich jetzt wieder Gelegenheit zu antworten. Ja, es sind die Instruktionen der Intermediate Language gemeint.


Log in to reply