branch probability hinting

["Frank Ch. Eigler" <fche at redhat dot com>]

Hi -

In cgen-generated files, as well as in other places in the simulator,
code such as the following occurs in some critical places:

	void foo () {
		process_a_bit ();
		if (error) {
			elaborate_error_handling () ;
		}
		process_a_bit_more ();
		if (need_to_trace) {
			elaborate_tracing ();
		}
		process_dangly_bits ();
	}

The elaborate_* pieces of code are very rarely or never executed
in normal high-speed modes, but nevertheless, the compiler must
emit code.  Without other knowledge, the compiler usually leaves
the generated code right in line, and branches around the mostly-dead
code.  If the compiler had enough information, it could move these
blocks of code out of line (and out of the hot parts of the icache).

How to give it this information?  Two ways -- profile-directed
feedback, or manual hints.  While infrequently used, they are not
that difficult.  The second (manual hinting) is particularly
straightforward in gcc, using the "__builtin_expect" function.
I plan to commit to sid some changes that add macros that
conveniently wrap this hinting:

#ifdef __GNUC__
#define LIKELY(expression) (__builtin_expect(!!(expression), 1))
#define UNLIKELY(expression) (__builtin_expect(!!(expression), 0))
#else
#define LIKELY(expression) (expression)
#define UNLIKELY(expression) (expression)
#endif

One is used thusly (and the other, vice versa):

	void foo () {
		process_a_bit ();
		if UNLIKELY(error) {
			elaborate_error_handling () ;
		}
		process_a_bit_more ();
		if UNLIKELY(need_to_trace) {
			elaborate_tracing ();
		}
		process_dangly_bits ();
	}

I plan to commit to cgen changes to emit calls to UNLIKELY(),
just for the tracing calls in sid decoding and semantics blocks:
all the sid/component/cgen-cpu/*/FOO-sem.cxx and FOO_decode.cxx
files would be minorly affected.  At the same time, I looked
through a couple pieces of other sid code (sidutil, scheduler,
mapper, memory, etc.), and added some hinting to a few obvious
places.  (No need to go overboard.)

While other command-line options are often required
(-O2/-O3/-freorder-blocks), depending on gcc version) to activate
the more aggressive optimizations that use these hints, the mere
presence of the hints, if unused, doesn't cause any degradation.
In other words, I think it is safe to add these hints now, even
if your builds doen't use them -- someday, they will help somewhat.

In the mean time, I'm running a couple of crude speed tests to
see whether the effect is detectable right now.


- FChE

PGP signature