
Technical background for the calltree (V0.3-) skin
=================================================


Cachegrind uses structure BBCC as basic block cost center.
Each BB gets a BBCC at instrumentation time. Costs are incremented
on execution of this BB.

The Calltree skin extends this:
* There can be multiple BBCCs for one BB if we want independed traces for
  - different threads
  - different recursion levels
  - different callers

Additionally, there are JCCs, jump cost centers.
In each BB there is exactly one jump from the original x86 code:
either conditional or unconditional. The latter can be a CALL or RET.
Therefore, a jump target of a BB is unique and we manage a list of
call arcs (JCCs) from the jump instruction of this BB.

A JCC is assoziated to a (BBCC source, BBCC target) pair. That is
important as a BBCC can be distinguished according to thread ID and so on.

For fast lookup, BBCCs and JCCs are accessable over resizable
hash tables.
- BBCC hash key is (BB start address, thread ID, rec. level, caller address).
If we don't want to distinguish one of the key parts, use a default.
- JCC hash key is (BBCC source, BBCC target).



Sequence of actions in the BBCC setup routine
=============================================

Each instrumented basic block first calls the helper function
setup_bbcc(). This function has two purposes:

1) Tracing function calls and returns
2) Set up the pointer to the BBCC struct which should get the
   events happening in the execution of the basic block

There can be multiple BBCCs of the same BB, depending on the options
choosen for the calltree run. The following properties of the execution
context of a BB can lead to different BBCCs that have to be used:

- The current thread ID
- The function context currently executed. This can involve
  * the last non-skipped function currently running
  * the recursion level of the currently running function
  * a number of functions in the call chain
  
For this, item (2) above depends on (1).
For call tracing, we use the struct JCC. These structs or stored in
a hash table by using a BBCC pair: The BBCC address of the last BB
where the call happened and the BBCC of the BB the call is targeted to.
Because of this, the actual sequence of actions is:

a) Update JmpKind:
   - for a call into a skipped function, ignore it
   - for a jump into another elf object, emulate a call
b) Update current context if there's a call
c) Calculate BBCC for new BB using the new context and a recursion counter
d) Trace a happening call

Used Data Structures
====================













Sinn von Kontexten:

Vielleicht koennte man noch eine Option hinzufuegen, die im gesamten Cachegrind die Prozentanzeige relativ zu den Gesamtkosten anzeigt...

Ich wuerde so eine Option ganz gerne verallgemeinern und fuer die GUI global gelten lassen.
Prozentanzeigen sind bisher relativ zu
* Gesamtkosten (aller ausgewaehlten Traceparts) in Funktionsliste
* Funktionskosten (bei Direktaufrufen/Coverage/Calltree/Quellanzeige)

Nun gibt es noch Funktionsgruppen:
* alle Funktionen in selbem ELF Object / selber Quelldatei / selbe C++ Klasse
* alle Funktionen in einem rekursiven Zyklus

Was mit der naechsten Calltree-Version dazukommt, sind Kontexte, in denen Funktionen ablaufen koennen. Dies habe ich eingefuehrt, um rekursive/falsche Zyklen bereits beim Profiling vermeiden zu koennen.
Bei grossen Programmen (besonders mit GUI) ist das ein riesiges Problem:
Bei einem KDE-Programm liefert KCachegrind Zyklen mit > 1000 Funktionen. Damit ist keine Performanzanalyse mehr moeglich.

Calltree haengt eine Kontextbeschreibung einfach an den Symbolnamen, getrennt
durch ein Apostroph; kann das ein Problem werden? Gibt es Programmiersprachen, in denen ein Apostroph in Symbolnamen auftauchen?

Wenn man nun rekursive Aufrufe unterscheidet, ergibt eine Aufruffolge
A > B > A keinen Zyklus, sondern wird von Calltree als A > B > A'2 beschrieben. A'2 wird wie eine komplett andere Funktion behandelt bzgl. aufgezeichneter Kosten. Das heisst, dass KCachegrind keine Anpassung benoetigt. Sinnvoll ist es nur, kontextbezogene Funktionen zu gruppieren (hier also A und A'2).

Anderes Beispiel fuer sinnvolle Kontexte:
2 Aufrufe "A > B > C" und "A > C > B" fuehren ohne Sonderbehandlung zum falschen Zyklus "B <> C". Unterscheidet man B und C am Aufrufer, so wird dies zu "A > B'A > C'B" und "A > C'A > B'C". Damit ist der Zyklus verschwunden.

Leider reicht das nicht, um alle falsche Zyklen zu erkennen.
Bsp: "A > B > C > D > E", "A > D > E > B > C": "C'B" kommt in beiden vor, damit haben wir den falschen Zyklus.
 Um Namen wie "A'B'C'D" zu vermeiden fuer die Funktion A, wenn sie im Kontext der Aufrufkette "D>C>B" aufgerufen wurde (viel zu lang!!!), werde ich Kontexte einfach durchnummerieren - der Anwender waere mit der Interpretation sowieso ueberfordert.

Damit die von Calltree erzeugte Datenmenge nicht explodiert, sollte man Kontexte nur bzgl. bestimmter Funktionen unterscheiden: Naemlich so, dass falsche Zyklen aufgeloest werden.
Das beste waere ein adaptives, automatisches Verfahren innerhalb von Calltree. Ich glaube allerdings, dass dies unmoeglich ist (ohne dass die Simulation noch langsamer wird).
KCachegrind kann jedoch entscheiden, wo Funktionskontexte sinnvoll sind.
Dies waere dann
