Optimize inline function merging

[sim642]

In #72 we disabled the merging of inline functions. One of the reasons being a slowdown claimed by an old comment:

cil/src/mergecil.ml

Lines 65 to 68 in c47bbbd

	(* Try to merge definitions of inline functions. They can appear in multiple
	* files and we would like them all to be the same. This can slow down the
	* merger an order of magnitude !!! *)
	let merge_inlines = ref false

It would be useful to figure out the root of that slowdown and possibly optimize it, because as it turns out, not merging inline functions can lead to large number of identical functions, which in themselves cause slowdown due to their sheer number.

Just by looking at the little code there is for them, this gem caught my eye:

cil/src/mergecil.ml

Lines 1459 to 1495 in c47bbbd

	let printout =
	(* Temporarily turn off printing of lines *)
	let oldprintln = !lineDirectiveStyle in
	lineDirectiveStyle := None;
	(* Temporarily set the name to all functions in the same way *)
	let newname = fdec'.svar.vname in
	fdec'.svar.vname <- "@@alphaname@@";
	(* If we must do alpha conversion then temporarily set the
	* names of the local variables and formals in a standard way *)
	let nameId = ref 0 in
	let oldNames : string list ref = ref [] in
	let renameOne (v: varinfo) =
	oldNames := v.vname :: !oldNames;
	incr nameId;
	v.vname <- "___alpha" ^ string_of_int !nameId
	in
	let undoRenameOne (v: varinfo) =
	match !oldNames with
	n :: rest ->
	oldNames := rest;
	v.vname <- n
	| _ -> E.s (bug "undoRenameOne")
	in
	(* Remember the original type *)
	let origType = fdec'.svar.vtype in
	if mergeInlinesWithAlphaConvert () then begin
	(* Rename the formals *)
	List.iter renameOne fdec'.sformals;
	(* Reflect in the type *)
	setFormals fdec' fdec'.sformals;
	(* Now do the locals *)
	List.iter renameOne fdec'.slocals
	end;
	(* Now print it *)
	let res = d_global () g' in
	lineDirectiveStyle := oldprintln;
	fdec'.svar.vname <- newname;

The merging happens based on the Pretty.doc printout of the function. I haven't profiled this, but that seems incredibly stupid. It's almost like comparing their string representations (which in fact might actually be faster since strings are continuous memory instead of the doc trees that are compared polymorphically).

[sim642]

One idea @vesalvojdani had was to simply compare their locations and nothing else (i.e. to ignore the bodies entirely). If an inline function is included into two files during preprocessing that are now being merged, that inline function came from the same location in the headers. Therefore if the locations are equal, we should reasonably assume that so are their bodies. The reasonable assumption of course being that the header files don't change between the preprocessing of different files.

Of course such heuristic might miss some pairs of inline functions that the printout approach currently merges, but I would assume such cases are very unlikely. Why would there be two identical implementation of an inline functions be in different locations in the headers? It's more reasonable to assume that most of the duplication is simply from the same header being preprocessed into everything.