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:
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 allemi = (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(); }
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
zux
addieren. Da esvolatile
ist, muss er jeden addierten Wert einmal schreiben: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.
-
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 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(); }
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.