- along with GNU CC; see the file COPYING. If not, write to
- the Free Software Foundation, 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA. */
-
-/* References:
-
- "Profile Guided Code Positioning"
- Pettis and Hanson; PLDI '90.
-
- TODO:
-
- (1) Consider:
-
- if (p) goto A; // predict taken
- foo ();
- A:
- if (q) goto B; // predict taken
- bar ();
- B:
- baz ();
- return;
-
- We'll currently reorder this as
-
- if (!p) goto C;
- A:
- if (!q) goto D;
- B:
- baz ();
- return;
- D:
- bar ();
- goto B;
- C:
- foo ();
- goto A;
-
- A better ordering is
-
- if (!p) goto C;
- if (!q) goto D;
- B:
- baz ();
- return;
- C:
- foo ();
- if (q) goto B;
- D:
- bar ();
- goto B;
-
- This requires that we be able to duplicate the jump at A, and
- adjust the graph traversal such that greedy placement doesn't
- fix D before C is considered.
-
- (2) Coordinate with shorten_branches to minimize the number of
- long branches.
-
- (3) Invent a method by which sufficiently non-predicted code can
- be moved to either the end of the section or another section
- entirely. Some sort of NOTE_INSN note would work fine.
-
- This completely scroggs all debugging formats, so the user
- would have to explicitly ask for it.
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+/* This (greedy) algorithm constructs traces in several rounds.
+ The construction starts from "seeds". The seed for the first round
+ is the entry point of function. When there are more than one seed
+ that one is selected first that has the lowest key in the heap
+ (see function bb_to_key). Then the algorithm repeatedly adds the most
+ probable successor to the end of a trace. Finally it connects the traces.
+
+ There are two parameters: Branch Threshold and Exec Threshold.
+ If the edge to a successor of the actual basic block is lower than
+ Branch Threshold or the frequency of the successor is lower than
+ Exec Threshold the successor will be the seed in one of the next rounds.
+ Each round has these parameters lower than the previous one.
+ The last round has to have these parameters set to zero
+ so that the remaining blocks are picked up.
+
+ The algorithm selects the most probable successor from all unvisited
+ successors and successors that have been added to this trace.
+ The other successors (that has not been "sent" to the next round) will be
+ other seeds for this round and the secondary traces will start in them.
+ If the successor has not been visited in this trace it is added to the trace
+ (however, there is some heuristic for simple branches).
+ If the successor has been visited in this trace the loop has been found.
+ If the loop has many iterations the loop is rotated so that the
+ source block of the most probable edge going out from the loop
+ is the last block of the trace.
+ If the loop has few iterations and there is no edge from the last block of
+ the loop going out from loop the loop header is duplicated.
+ Finally, the construction of the trace is terminated.
+
+ When connecting traces it first checks whether there is an edge from the
+ last block of one trace to the first block of another trace.
+ When there are still some unconnected traces it checks whether there exists
+ a basic block BB such that BB is a successor of the last bb of one trace
+ and BB is a predecessor of the first block of another trace. In this case,
+ BB is duplicated and the traces are connected through this duplicate.
+ The rest of traces are simply connected so there will be a jump to the
+ beginning of the rest of trace.
+
+
+ References:
+
+ "Software Trace Cache"
+ A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
+ http://citeseer.nj.nec.com/15361.html
+