[Ada] Speed up enumeration'Value with perfect hash function

[Ada] Speed up enumeration'Value with perfect hash function

[Pierre-Marie de Rodat]

[-- Attachment #1: Type: text/plain, Size: 4523 bytes --]

This speeds up the implementation of the Value attribute for enumeration
types with more than 3 values by using a perfect hash function to do the
lookup instead of a linear search.  This also generizes the implementation
of the associated support routines in the runtime, as well as that of the
support routines for the Image attribute.  Finally this removes the long
obsolete System.Img_Enum unit and makes System.Img_Enum_New obsolete but
keeps it because of bootstrap considerations.

This is achieved by splitting GNAT.Perfect_Hash_Generators into the bulk
implementation put in System.Perfect_Hash_Generators and the primary user
interface left in GNAT.Perfect_Hash_Generators. The secondary interface is
entirely moved to System.Perfect_Hash_Generators because it is presumably
not used, but it can be easily forwarded from GNAT.Perfect_Hash_Generators
again if need be. The compiler can then use this secondary interface from
System.Perfect_Hash_Generators to generate the hash function and build its
associated tables when it is compiling an enumeration type.

The new circuitry can be entirely disabled by the -gnatd_h debug switch.

Tested on x86_64-pc-linux-gnu, committed on trunk

gcc/ada/

	* Makefile.rtl (GNATRTL_NONTASKING_OBJS): Add s-imagen, s-imen16,
	s-imen32, s-imenu8, s-pehage, s-valuen, s-vaen16, s-vaen32 and
	s-vaenu8.  Remove s-imenne, s-imgenu and s-valenu.
	* debug.adb (d_h): Document new usage.
	* einfo.ads (Lit_Hash): New attribute for enumeration types.
	(Set_Lit_Hash): Declare.
	* einfo.adb (Lit_Hash): New function.
	(Set_Lit_Hash): New procedure.
	(Write_Field21_Name): Print Lit_Hash for Enumeration_Kind.
	* exp_imgv.ads (Build_Enumeration_Image_Tables): Fix description
	and document the hash function and its tables.
	* exp_imgv.adb: Add with/use clauses for Debug.  Add with clause
	for System.Perfect_Hash_Generators.
	(Append_Table_To): New helper routine.
	(Build_Enumeration_Image_Tables): Call it to build the tables.
	In the main unit, register the literals with the hash generator.
	If they are sufficiently many and -gnatd_h is not passed, generate
	a perfect hash function and its tables; otherwise, generate a dummy
	hash function.  For the other units, generate only the declaration.
	In all cases, set Lit_Hash to the entity of the function, if any.
	(Expand_Value_Attribute): Pass the 'Unrestricted_Access of Lit_Hash,
	if any, as third argument to the Value_Enumeration_NN function.
	* gnat1drv.adb (Adjust_Global_Switches): force simpler implementation
	of 'Value in CodePeer_Mode.
	* lib.ads (Synchronize_Serial_Number): Add SN parameter.
	* lib.adb (Synchronize_Serial_Number): Assert that it is larger than
	the serial number of the current unit and set the latter to it only
	in this case.
	* rtsfind.ads (RTU_Id): Add System_Img_Enum_8, System_Img_Enum_16,
	System_Img_Enum_32, System_Val_Enum_8, System_Val_Enum_16 and
	System_Val_Enum_32.  Remove System_Img_Enum, System_Img_Enum_New
	and System_Val_Enum.
	* sem_attr.adb (Analyze_Access_Attribute): Do not flag a compiler
	generated Unrestricted_Access attribute as illegal in a declare
	expression.
	(RE_Unit_Table): Adjust to above changes.
	* libgnat/g-heasor.ads: Add pragma Compiler_Unit_Warning.
	* libgnat/g-table.ads: Likewise.
	* libgnat/g-pehage.ads: Add with clause and local renaming for
	System.Perfect_Hash_Generators.
	(Optimization): Turn into derived type.
	(Verbose): Turn into renaming.
	(Too_Many_Tries): Likewise.
	(Table_Name): Move to System.Perfect_Hash_Generators.
	(Define): Likewise.
	(Value): Likewise.
	* libgnat/g-pehage.adb: Remove with clause for Ada.Directories,
	GNAT.Heap_Sort_G and GNAT.Table.  Move bulk of implementation
	to System.Perfect_Hash_Generators, only keep the output part.
	* libgnat/s-imagen.ads: New generic unit.
	* libgnat/s-imagen.adb: New body.
	* libgnat/s-imen16.ads: New unit.
	* libgnat/s-imen32.ads: Likewise.
	* libgnat/s-imenu8.ads: Likewise.
	* libgnat/s-imenne.ads: Adjust description.
	* libgnat/s-imgenu.ads: Delete.
	* libgnat/s-imgenu.adb: Likewise.
	* libgnat/s-pehage.ads: New unit from GNAT.Perfect_Hash_Generators.
	* libgnat/s-pehage.adb: New body from GNAT.Perfect_Hash_Generators.
	* libgnat/s-valuen.ads: New generic unit.
	* libgnat/s-valuen.adb: New body.
	* libgnat/s-vaen16.ads: New unit.
	* libgnat/s-vaen32.ads: Likewise.
	* libgnat/s-vaenu8.ads: Likewise.
	* libgnat/s-valenu.ads: Delete.
	* libgnat/s-valenu.adb: Likewise.
	* gcc-interface/Make-lang.in (GNAT_ADA_OBJS): Add s-pehage.o.
	(GNATBIND_OBJS): Remove s-imgenu.o.

[-- Attachment #2: patch.diff.gz --]
[-- Type: application/gzip, Size: 48349 bytes --]