// Problems:
// - check that an internal reference is created for reference to an entry node if
//   it is the current entry node.
// - garbage collection with DETERMINE_ENTRY_NODES has not been test. 
#define EXTRAATJE


// should also change 
#include "globals.c"
#include "gts_debug.c"

#include "gts_type_object_type.c"

#ifdef COLLECT_AND_RENUMBER_EXTERNAL_TYPE_REFERENCES
#else
#define REPLACE_MODULE_ID_BY_DISK_ID					// !CHECKED!
#define CONVERT_RUNTIME_ID_TO_RUNTIME_ID_ON_DISK		// !CHECKED!
#define COLLECT_TYPE_STRING_FOR_LAZY_RUN_TIME_IDS		// !CHECKED!
#error "dfkfklf"
#endif


//
#define CONVERT_LAZY_RUN_TIME_ID		// handles lazy type references
#define LAZY_DYNAMICS					// handles build__block and build_lazy_block closures

#define LAZY_DYNAMICS_2					// compute descriptor replaces build_blocks by build_lazy_blocks
#define LAZY_DYNAMICS_3					// ignore build_blocks (should also ignore build_lazy_blocks)

#define COPIED_DYNAMICS

#define DYNAMIC_STRINGS					// store dynamic strings

#define USE_CGTSA_AND_CGTSR
#define USE_USED_CODE_LIBRARY_INSTANCE_ARRAY

//#define DEBUG

// includes
#define MAKE_DUS_SYMBOLIC				// should be *always* be defined, !CHECKED! 
#define EXTEND_DUS_WITH_LIBARY_NUMBER	// !CHECKED! 

//#include "globals.c"
#include "global_registers.c"
#include "gts_stack.c"
#include "extra_heap.c"
#include "colour.c"
#include "descriptor_usage.c"
#include "gts_need_debug.c"
#include "gts_build_block.c"
#include "gts_gdi.c"
// #define DETERMINE_ENTRY_NODES // extra pass to determine entry nodes
// TODO:
// - small changes to support REPLACE_MODULE_ID_BY_DISK_ID
#define DETERMINE_ENTRY_NODES

// Macro's which should always be defined.
#define EXTRA_HEAP_ENTRY

#define COMPUTE_TYPETABLE_ID_FROM_MODULE_ID		// !CHECKED!

# ifdef COLOUR_GRAPH

	// User definable
# define N_LB_ENTRIES		8			// n entries = 2 ^ N_LB_ENTRIES_EXP
# define N_LB_ENTRIES_EXP	3

# define LB_ENTRY_BSIZE		4			// entry size = 2 ^ LB_ENTRY_BSIZE_EXP (in bytes)
# define LB_ENTRY_BSIZE_EXP	2			
# define MAKE_ID(x)			x##_DL			// data

# define MAKE_ID_NDL(x)		x##_fixed_DL	// no stack
# define MAKE_ID_UDL(x)		x##_unfixed_DL	// unfixed stack
# define MAKE_ID_FDL(x)		x##_fixed_DL	// fixed stack
# define SPECIAL								// To be removed
# define BOTH_FIXEDNESS		

# include "LinkedBlock.c"

	// User definable
# define N_LB_ENTRIES		8			// n entries = 2 ^ N_LB_ENTRIES_EXP
# define N_LB_ENTRIES_EXP	3

# define NOT_A_POWER_OF_TWO_ENTRY_SIZE
# define LB_ENTRY_WSIZE		5			//5

# define MAKE_ID(x)			x##_EN				// data

# define MAKE_ID_NEN(x)		x##_fixed_EN		// no stack
# define MAKE_ID_UEN(x)		x##_unfixed_EN		// unfixed stack
# define MAKE_ID_FEN(x)		x##_fixed_EN		// fixed stack
# define SPECIAL									// To be removed
# define BOTH_FIXEDNESS							// used in both unfixed and fixed contents		

# define MAKE_ID_EN(x)		x##_EN

# include "LinkedBlock.c"
// Format EN:
// word 0: 	descP
// word 1 (1234):
//			- 12 offset array index i.e. id of entry node
//			- 34 except for two least significant bits represents the block_id in offset array
// word 2:
//			Offset from block start to the entry node
// word 3: unused (might come in handy for nodeP)

# define EN_DESCP			0
# define EN_COLOUR			4

// EN/SN-node, EN_COLOUR (1234): 1 = reserved
# define ENSN_COLOUR_GET_COLOUR				0x00ffffff 		// 0x3fffffff// 1234, 12 reserverd, 34 = colour

// byte 1, bit 4: set iff EN-node otherwise it is an SN-node
# define ENSN_COLOUR_SET_EN_BIT				0x80000000

#  ifdef DETERMINE_ENTRY_NODES
// byte 1, bit 3: set iff EN/SN-node has already been visited, used in 2nd pass (determination of EN-nodes)
#  define ENSN_COLOUR_ALREADY_VISITED_MASK	0x40000000

// Multiple combinations of bits
#  define ENSN_COLOUR_EN_BIT_AND_COLOUR		0xbfffffff

#  endif

# define EN_NODE_INDEX		8

# define EN_BLOCK_OFFSET	12
# define EN_NODEP			12			// used in pass 2 (determine en nodes)

# define EN_NODE_LIST		16			// used in pass 3 (copying)
# define EN_NODE			16			// first used in pass 4 //3

# define INITIAL_BLOCK_N	4			// 0 is reservered for top-level dynamic; two least significant bits are unused
# define BLOCK_INCREASEMENT	4

	// User definable
# define N_LB_ENTRIES		8			// n entries = 2 ^ N_LB_ENTRIES_EXP
# define N_LB_ENTRIES_EXP	3


# define LB_ENTRY_BSIZE		8		/*4	*/		// entry size = 2 ^ LB_ENTRY_BSIZE_EXP (in bytes)
# define LB_ENTRY_BSIZE_EXP	3		/* 2 */		
# define MAKE_ID(x)			x##_BI

# define BI_INFO				0
# define BI_N_EN_NODES		4

# define MAKE_ID_FBI(x)		x##_fixed_BI		// fixed stack
# define SPECIAL
# define FIXED

# define MAKE_ID_BI(x)		x##_BI

# include "LinkedBlock.c"


#  ifdef DYNAMIC_STRINGS
	// User definable
#  define N_LB_ENTRIES		8			// n entries = 2 ^ N_LB_ENTRIES_EXP
#define N_LB_ENTRIES_EXP	3

#define NOT_A_POWER_OF_TWO_ENTRY_SIZE
#define LB_ENTRY_WSIZE		3			//5

#define MAKE_ID(x)			x##_DS			// data

#define MAKE_ID_NDS(x)		x##_fixed_DS	// no stack
#define MAKE_ID_UDS(x)		x##_unfixed_DS	// unfixed stack
#define MAKE_ID_FDS(x)		x##_fixed_DS	// fixed stack
#define SPECIAL								// To be removed
#define BOTH_FIXEDNESS		

#define MAKE_ID_DS(x)		x##_DS			

#include "LinkedBlock.c"
#endif // DYNAMIC_STRINGS

#include "gts_undo.c"

# ifdef CONVERT_LAZY_RUN_TIME_ID
// also change RunTimeIDW in DynamicLinkerInterface

# define RTID_LAST_FIELD			RTID_ASSIGNED_DISK_ID
# define RTID_SIZE					(RTID_LAST_FIELD + 4)

	// User definable
# define N_LB_ENTRIES		8			// n entries = 2 ^ N_LB_ENTRIES_EXP
# define N_LB_ENTRIES_EXP	3

//# define LB_ENTRY_BSIZE		16		/*4	*/		// entry size = 2 ^ LB_ENTRY_BSIZE_EXP (in bytes)
//# define LB_ENTRY_BSIZE_EXP	4		/* 2 */		

# define NOT_A_POWER_OF_TWO_ENTRY_SIZE
# define LB_ENTRY_WSIZE		3

# define MAKE_ID(x)			x##_RTID			// data

# define MAKE_ID_NRTID(x)	x##_fixed_RTID		// no stack
# define MAKE_ID_URTID(x)	x##_unfixed_RTID	// unfixed stack
# define MAKE_ID_FRTID(x)	x##_fixed_RTID		// fixed stack
# define SPECIAL								// To be removed
# define BOTH_FIXEDNESS		

# define MAKE_ID_RTID(x)		x##_RTID			

# define DEBUG_RTID			// debug

# include "LinkedBlock.c"
# undef DEBUG_RTID			// debug


# include "gts_runtime_id.c"
# endif

# ifdef COMPUTE_TYPETABLE_ID_FROM_MODULE_ID
#include "gts_range_id.c"
# endif

# endif

#include "gts_lazy_dynamic_reference.c"	
#include "gts_build_lazy_block_id.c"

# ifdef USE_CGTSA_AND_CGTSR
# include "gts_copy_graph_to_string_arguments.c"
# include "gts_copy_graph_to_string_results.c"
# endif // USE_CGTSA_AND_CGTSR

// -------------------------------------------------------------------------------------------
// HEADER
//
// Notice that part of the header is shared by different applications
//
// To add a new field:
// 1. add the field either in the common section or just for dumpDynamic
// 2. if its the last field, then mention it as the last field by replacing it in the
//    HEADER_SIZE-macro. (just below)

// Shared by:
// StdDynamicLowLevelInterface.{icl,dcl}; build_dynamic_header
// in application dumpDynamic & dynamic linker

// OBSOLETE:
// - StdDynamic.icl (StdEnv)
// - read_dynamic.icl (dumpDynamic)
// - dynamics.icl (dumpDynamic,dynamic linker)
//
// Probably only by StdDynamicLowLevelInterface.icl
#define HEADER_SIZE_OFFSET		8		// header size (in bytes)
#define VERSION_NUMBER_OFFSET	12		// version (major,minor) 		// little or big endian format?
#define GRAPH_OFFSET			16		// graph offset
#define GRAPH_SIZE				20		// graph size
#define BLOCK_TABLE_OFFSET		24
#define BLOCK_TABLE_SIZE		28
#define DYNAMIC_RTS_INFO_OFFSET	32		// info from dynamic rts; filled in by StdDynamic.icl
#define DYNAMIC_RTS_INFO_SIZE	36
// End sharing for StdDynamic.icl

#define STRINGTABLE_OFFSET		40		// stringtable offset
#define STRINGTABLE_SIZE		44		// stringtable size
#define DESCADDTRESTABLE_OFFSET	48		// descriptor address table offset
#define DESCADDRESSTABLE_SIZE	52		// descriptor address table size
#define N_NODES					56		// n_dynamics

#define HEADER_SIZE				(N_NODES-4)		//((last_field + 4)	- 8)=last_field-4  //32

#define HEADER_SIZE_IN_WORDS	(HEADER_SIZE / 4)	// in words

#define INITIAL_EXTRA_HEAP_SIZE				0				// in words (each word is 4 bytes)
#define INITIAL_EXTRA_HEAP_SIZE_IN_BYTES	(INITIAL_EXTRA_HEAP_SIZE * 4)

// Descriptor for graph_to_string function
// called by writeDynamic
	.data
# ifdef DEBUG
nth_call:
	.long 0
# endif


type_string_ptr:
	.long 0

m__StdDynamic:
	.long	10
	.ascii	"StdDynamic"
	.byte	0,0
	
	.align 4
	.long	m__StdDynamic
	.align	4
	.long	e____SystemDynamic__dcopy__graph__to__string__0x00010101+2
	.word	0
	.word	1
	.globl	e____SystemDynamic__dcopy__graph__to__string__0x00010101
e____SystemDynamic__dcopy__graph__to__string__0x00010101:
	.word	0
	.word	0
	.long	e____SystemDynamic__lcopy__graph__to__string__0x00010101
	.word	1
	.word	8
i_133:
l_39:
	.long	23
	.ascii	"copy_graph_to_st"
	.ascii	"ring_OK"
	.byte	0

	.align 4
test_string:
	.ascii 	"test_string"
	.byte 0
		
// Global variables across passes
	.align	4	
t_stackP:
	.long 	0
initfree:	
	.long 0										// initial free words (4 bytes)

// backup variables
ecx_backup:
	.long	0
edx_backup:
	.long	0
	
old_heap_pointer:
	.long 0										// %edi before encoding started
	
root_node:
	.long 0										// graph to be encoded	

type_table_usage:
	.long 0
range_table:
	.long	0
	
# ifdef USE_USED_CODE_LIBRARY_INSTANCE_ARRAY
used_code_library_instance_array:
	.long	0
# endif

esp_backup:
	.long 0
esi_backup:
	.long 0
	
	
// -------------------------------------------------------------------------------------------
// .text

	.align 	4
	.text
	.align	4
e____SystemDynamic__lcopy__graph__to__string__0x00010101:
	cmpl	end_b_stack,%esp
	jb		stack_overflow
	call	ea11
	cmpl	end_heap,%edi
	jae		i_408
i_409:
	movl	$e____SystemDynamic__rWrap+2,(%edi)
	movl	%ecx,4(%edi)
	movl	%edi,%ecx
	addl	$8,%edi
	ret

i_408:
	call	collect_1
	jmp	i_409

ea11:
	testb	$2,(%ecx)
	jne	e_44
	cmpl	end_a_stack,%esi
	jae	stack_overflow
	call	(%ecx)
e_44:
	movl	4(%ecx),%ecx
	
	// pass1
copy__graph__to__string__0x00010101:
# ifdef DEBUG
	incl	nth_call
# endif

# ifdef DYNAMIC_STRINGS
	call	init_lazy_block_id
# endif

	/*
	** Warning: 
	** This function needs at least some space to operate. Because the run-time system
	** probably uses memory both before and after the call, not enough memory will 
	** cause an access violation.
	** called by the Clean and the garbage collector
	*/	
	// backup state; DO_NOT_CHANGE ...
# ifdef USE_CGTSA_AND_CGTSR
	movl	%ecx,ecx_backup
	
# define temp %eax
	movl	CGTSA_DYNAMIC(%ecx),temp				// find root
	movl	temp,root_node

	movl	8(%ecx),%edx							// get arg block

	movl	CGTSA_TYPE_LIBRARY_INSTANCES(%edx),temp	// copy type library instances array
	movl	temp,type_table_usage
	
#  ifdef USE_USED_CODE_LIBRARY_INSTANCE_ARRAY
	movl	CGTSA_CODE_LIBRARY_INSTANCES(%edx),temp	// copy type library instances array
	movl	temp,used_code_library_instance_array
#  endif 

	movl	CGTSA_RANGE_TABLE(%edx),temp			// copy range table
	movl	temp,range_table
# undef temp
	
# else // not USE_CGTSA_AND_CGTSR
	movl	%ecx,type_table_usage
	movl	%edx,root_node
	
# define temp %eax
	movl	-4(%esi),temp
	movl	temp,range_table
# undef temp
# endif // not USE_CGTSA_AND_CGTSR
	
	pushl 	%esi							// backup A-stack pointer
	movl	%esp,esp_backup					// backup esp
	movl	%esi,esi_backup					// backup esi
	
	movl	heapP,old_heap_pointer			// backup heap pointer
	
	// compute free space
	movl	end_heap,free
	leal	32(free),free		
	subl 	heapP,free						// free = stackP - heapP (in bytes)
	shrl 	$2,free							// free /= 4 (in longs)
	movl	free,initfree					// initfree = initial amount of memory available
	// ... DO_NOT_CHANGE (The garbage collector handler depends upon correct initialization)
	
# ifdef COLOUR_GRAPH
	_set_default_undo_handler

	// After the first pass, the stack size will be fixed but the second pass which deletes
	// indirections in SN-nodes traverses the graph as a whole in contrast to the first 
	// colouring pass which traverses the graph on a dynamic base.
	// However, the graph has almost been traversed completely because the top-level dynamic
	// has been traversed. Additional 8 bytes for its two arguments are needed, to increase
	// the maximum stack size.
	// At label copy_done_colouring_finished the stack is enlarged by the size of the two
	// arguments of the top-level dynamic by subtracting 2 * 4 bytes from the StackTop. In
	// this way the stack is always big enough.
	subl	$2,free
	js 		GC_NO_STACK

# endif // COLOUR_GRAPH	
	// initialize stack
	subl	$ INITIAL_EXTRA_HEAP_SIZE,free	// try to reserve INITIAL_EXTRA_HEAP_SIZE 
	js		GC_NO_STACK
	
	movl	end_heap,stackP
	leal	32(stackP),stackP				// end_heap + 32 is invalid; thus 32 - 4 = 28
	movl	stackP,extraheapBottom
	movl	stackP,extraP
	subl	$ INITIAL_EXTRA_HEAP_SIZE_IN_BYTES,stackP
	movl	stackP,stackBottom

	movl	stackP,stackTop
	
	subl	$(2 + HEADER_SIZE_IN_WORDS),free			
	js 		GC_NO_STACK

	movl 	$__STRING__+2,(heapP)					// store STRING descriptor
	movl 	$0,4(heapP)								// string length is zero

	leal	((2 * 4) + HEADER_SIZE)(heapP),heapP

	movl	%ecx,nodeP								// top node of graph to be encoded 
	
# ifdef CONVERT_LAZY_RUN_TIME_ID
	call 	MAKE_ID_NRTID(lb_init)
# endif
	
# ifdef COLOUR_GRAPH
	call	MAKE_ID_NSN(lb_init)
	call	MAKE_ID_NDL(lb_init)
	jmp		copy_done
# else 
# define ML_COPY(x)	x##_1
	jmp 	ML_COPY(copy_next_node_in_nodeP)

// pass 1; COPY
# define ML(x)				x##_1
# define EXIT_LABEL			copy_done
# define ENTRY_LABEL		copy_next_node_1
# define ENTRY_LABEL_NODEP	copy_next_node_in_nodeP_1

# define UNFIXED_STACK

# define COPY_PASS
# include "gts_copy.c"
# undef COPY_PASS

# undef EXIT_LABEL
# endif 
	
// --------------------------------------------------------------------------------------------------------
// 2nd pass
function_name_list:
	.long 0
module_name_list:
	.long 0
n_nodes:
	.long 0
		
	.align 4
#include "prefixes.c"
	
# ifdef COLOUR_GRAPH
	.align 4
	.data
	.align	4
s_copy_done:
	.long	__STRING__+2
	.long	9
	.ascii	"copy_done"
	//       012345678901234567890123456789012345678901234567890123456
	.byte 	0
	.byte 	0
	.byte 	0
	.byte	0	
s_interleaved_subcomponents:
	.long	__STRING__+2
	.long	66
	.ascii	"graph_to_string ERROR: interleaved subcomponents are unimplemented"
	//       012345678901234567890123456789012345678901234567890123456789012345
	.byte 	0
	.byte 	0
	.byte 	0
	.byte	0	

	.align 4

debug_count:
	.long 	0
counter:
	.long	0
en_list_base_address:
	.long	0
	
	.data
	.align	4
blocks_are_not_successive:
	.long	__STRING__+2
	.long	117
//	.ascii	"(graph_to_string; internal error) blocks are not successive"
	//       012345678901234567890123456789012345678901234567890123456789012345
	//		 0         1         2         3         4         5
	.ascii  "(graph_to_string.c; internal error; blocks are not successive): pa"
	.ascii	"ss the HyperStrictEvaluation-option to WriteDynamic"
	.byte 	0
	.byte 	0
	.byte 	0
	.byte	0
	
	.align	4
build_block_cannot_be_stored:
	.long	__STRING__+2
	.long	72
	//       012345678901234567890123456789012345678901234567890123456789012345
	//		 0         1         2         3         4         5
	.ascii  "(graph_to_string.c; internal error; build_block-closure cannot be "
	.ascii	"stored."
	.byte 	0
	.byte 	0
	.byte 	0
	.byte	0	
	.align 	4
counter_backup:
	.long	0
	.align	4
current_colour:
	.long	0
block_n:
	.long	0						// points to free block number
old_heapP:
	.long	0						// point to start address of block
	
#  ifdef EXTEND_DESCRIPTOR_USAGE_TABLE
dus_entry_bsize:					// size of descriptor usage set-entry
	.long 	0	
	
// adapt also function read_descriptor_usage_table in StdDynamicLowLevelInterface.icl
#   ifdef EXTEND_DUS_WITH_LIBARY_NUMBER
// fixed part:
#   define DUS_DESC_ADDRESS_ENTRY	0
#   define DUS_LIBRARY_NUMBER		4

#   define DUS_FIXED_ENTRY_BSIZE	(DUS_LIBRARY_NUMBER + 4)
#   define DUS_FIXED_ENTRY_WSIZE	(DUS_FIXED_ENTRY_BSIZE / MACHINE_WORD_BSIZE)

// variable part:
#   define DUS_SET					8
#   else
// fixed part:
#   define DUS_DESC_ADDRESS_ENTRY	0

#   define DUS_FIXED_ENTRY_BSIZE	(DUS_DESC_ADDRESS_ENTRY + 4)
#   define DUS_FIXED_ENTRY_WSIZE	(DUS_FIXED_ENTRY_BSIZE / MACHINE_WORD_BSIZE)

// variable part:
#   define DUS_SET					4
#   endif // EXTEND_DUS_WITH_LIBARY_NUMBER

#  endif // EXTEND_DESCRIPTOR_USAGE_TABLE

# endif // COLOUR_GRAPH
	// -------------------------------------------------------------
	// pass2
	.data
ptr_to_dynamic_to_be_added:
	.long	0
stored_ptr_to_dynamic:
	.long 	0
# ifdef COPIED_DYNAMICS
current_dynamic_node:
	.long 	0 
# endif


	.text
#include "gts_colour_graph.c"
	
reset_colour_table_entry:
	movl	$0,(%ecx)							// should be initialized at zero
	ret
	
//reset_colour_table_entry2:
//	ret

copy_done_no_top_level_dynamic:
	int3
	int3
	nop
	nop
	jmp		copy_done_no_top_level_dynamic


	// PASS 1: colour graph
copy_done: // delete_indirections
# ifdef DEBUG
	call	need_debug
	movl	root_node,nodeP
# endif

# ifdef COLOUR_GRAPH
	call	MAKE_ID_NEN(lb_init)					// initialize Entry Node (EN) array
# define en_node %ecx	
	movl	root_node,nodeP

	call	MAKE_ID_NEN(lb_alloc_entry)
	movl	(nodeP),descP
	movl	descP,EN_DESCP(en_node)
	
	movl	$ TOPLEVEL_COLOUR,EN_COLOUR(en_node)
	
	_set_undo_handler $undo_colouring
	
	// update root node (from this point on: only U and F permitted)
	leal	1(en_node),en_node
	movl	en_node,(nodeP)
# undef en_node

	// colour rest of graph
	cmpl	$e____SystemDynamic__rDynamicTemp+2,descP
	jne 	copy_done_no_top_level_dynamic
	
copy_done_top_level_dynamic:
	call 	MAKE_ID_UDL(lb_alloc_entry)			// add top level dynamic to dynamic list
	movl	nodeP,(%ecx)

	call	init_colour_table					// initialize colour table
		
# define counter %ecx
# define limit %ebx
	movl	$1,limit
	movl	$0,counter							// counter initialized at zero

copy_done_loop:
	pushl	limit

	movl	counter,counter_backup

	// body ...
	call	MAKE_ID_UDL(lb_index_of_entry)
	movl	(%ecx),nodeP						// nodeP is a DynamicTemp node
# ifdef COPIED_DYNAMICS
	movl	nodeP,current_dynamic_node
# endif

	// colour value
	call	MAKE_ID_UCT(lb_size)				
	movl	%ecx,previous_colour_combinations
	
	pushl	8(nodeP)							// backup type node
	movl	4(nodeP),nodeP						// current node is value node
	
	movl	$ reset_colour_table_entry,%ecx
	call	MAKE_ID_UCT(lb_map_array)			// reset colour table
	
	call	visit_nodes_from_nodeP				// colour it
	
	// colour type
	call	MAKE_ID_UCT(lb_size)
	movl	%ecx,previous_colour_combinations

	popl	nodeP

	movl	$ reset_colour_table_entry,%ecx
	call	MAKE_ID_UCT(lb_map_array)			// reset colour table

	call	visit_nodes_from_nodeP				// colour it
	// ... body

	movl	counter_backup,counter

	popl	limit

	cmpl	$0,counter
	jne 	limit_does_not_change_any_more
	pushl	counter
	call	MAKE_ID_UDL(lb_size)				// n_dynamics
	movl	%ecx,limit
	popl	counter
	
limit_does_not_change_any_more:
	incl 	counter

	cmpl	counter,limit
	jne		copy_done_loop	
	
# undef counter
# undef limit
	movl	MAKE_ID_SN(lb_root),%eax
#  ifdef DEBUG
	call	need_debug
#  endif

	// --------------------------------------------------------------------------------------
	// PASS 2: determing entry nodes
copy_done_colouring_finished:		
	// The 8 bytes have already been reserved during initialization. It is mainly
	// done for making the undo_colouring-routine more simple.
	subl	$8,stackTop
	
# define sh_entry descP
# undef sh_entry
	movl	$ reset_colour_table_entry,%ecx
	call	MAKE_ID_FCT(lb_map_array)			// reset colour table
		
	movl	$ 0,%ecx
	call	MAKE_ID_FEN(lb_index_of_entry)
# define entry_node %ecx
	
# define temp nodeP
	movl	SN_COLOUR(entry_node),temp
	orl		$ ENSN_COLOUR_SET_EN_BIT,temp				
	movl	temp,EN_COLOUR(entry_node)		// mark as entry node
# undef temp

	movl	$0,EN_NODE_INDEX(entry_node)

#  ifndef DETERMINE_ENTRY_NODES	
	movl	$ ((2 * 4) + HEADER_SIZE),EN_BLOCK_OFFSET(entry_node)
#  else
#  define temp nodeP
	movl	root_node,nodeP
	movl	nodeP,EN_NODEP(entry_node)			// NEW!!! set nodeP to be used in pass 2
#  undef temp
#  endif

# undef entry_node

	movl	$ INITIAL_BLOCK_N,block_n			// initialize block_n
	
	call	MAKE_ID_FBI(lb_init)

	// assumption: at least one dynamic
# define temp2 %ecx
	movl	root_node,nodeP						// nodeP = root nodeP

	// set colour of root dynamic
	movl	$ 0,temp2
	call	MAKE_ID_FEN(lb_index_of_entry)
	movl	EN_COLOUR(temp2),temp2
	andl	$ ENSN_COLOUR_GET_COLOUR,temp2
	movl	temp2,current_colour	
	
# ifdef DETERMINE_ENTRY_NODES
#  ifdef COMPUTE_TYPETABLE_ID_FROM_MODULE_ID
	call	init_range_id
#  endif

# include "gts_determine_entry_nodes.c"
# else // not DETERMINE_ENTRY_NODES
#  ifdef COMPUTE_TYPETABLE_ID_FROM_MODULE_ID
	call	init_range_id
#  endif

	_set_undo_handler $undo_copying
	
	// Each node now has a colour associated with it.
	// 
	// For the moment it is assumed that pieces graph are allocated in successive
	// space.
	// 
	// Each site in the code where descP are copied in the string should be 
	// changed e.g. arrays. Look for '// also for array'.
# undef temp2

	movl	heapP,graph_start						// backup start of encoded graph
			
# define ML(x)				x##_ccn
# define ENTRY_LABEL		copy_next_node_ccn
# define ENTRY_LABEL_NODEP	copy_next_node_in_nodeP_ccn

# define OLD_COPY_PASS

copy_nodes_with_current_colour:
	movl	heapP,old_heapP
	
	jmp		ML(copy_next_node_in_nodeP)				// encode nodes having current colour
# define EXIT_LABEL		copy_done_current_colour_copied

# define COPY_PASS
# include "gts_copy.c"
# undef COPY_PASS

EXIT_LABEL:
# define newHeapP descP
	movl	heapP,newHeapP							// new heap pointer
	subl	old_heapP,newHeapP						// newHeapP = newHeapP - old_heapP
# define block_size newHeapP
	shll	$16,block_size

	movl	current_colour,%ecx
	call	MAKE_ID_FCT(lb_index_of_entry)			
	
	movl	(%ecx),%ecx
	andl	$0x0000fffc,%ecx
	orl		%ecx,block_size							// 1234; 12 = (partial) block size, 34 = block index
# define block_info block_size
	
	call	MAKE_ID_FBI(lb_alloc_entry)				// alloc block info entry
	
	movl	block_info,(%ecx)			
# undef newHeapP
# undef block_size

	cmpl	esp_backup,%esp
	je		copy_equally_coloured_nodes_finished
	
	// assumption:
	// - the stack contains only nodes which colour has not yet been
	//   current_colour NIET WAAR. Furthermore the copy algorithm leaves different
	//   colours than the current colour unmodified. Thus it is always
	//   a pointer to a sn.
	popl	nodeP
	movl	(nodeP),descP
	cmpl	heapP,descP							// descP <= heapP; can be removed once assumption holds
	jbe		EXIT_LABEL							// node has already been encoded	
		
# define new_current_colour %ecx
	decl	descP
	movl	SN_COLOUR(descP),new_current_colour	// get new current colour
	andl	$ ENSN_COLOUR_GET_COLOUR,new_current_colour
	movl	new_current_colour,current_colour
# undef temp

	jmp		copy_nodes_with_current_colour
# undef EXIT_LABEL

# endif // DETERMINE_ENTRY_NODES	

	// --------------------------------------------------------------------------------------
copy_equally_coloured_nodes_finished:


# ifdef DEBUG2
	int3
	int3
	int3
	int3
# endif 

# ifdef COMPUTE_TYPETABLE_ID_FROM_MODULE_ID
	call	restore__Module_descriptors
# endif

	movl	heapP,graph_end							// backup end of graph encoding
	
#define temp nodeP
	call 	MAKE_ID_FBI(lb_size)					// # blocks allocated + allocated root block
	
	movl	block_n,temp
	shrl	$2,temp							
	cmpl	%ecx,temp
	je		0f

	// I think blocks are never interleaved because after the first pass it is
	// known which nodes belong to a block. Equally coloured nodes are encoded
	// together.
	// Using DETERMINE_ENTRY_NODES blocks are never interspersed with other
	// blocks
1:	
	int3

	movl	MAKE_ID_EN(lb_root),%ebx
	nop
	nop
	nop
	nop
	
	movl	root_node,%eax
	
	movl	$ blocks_are_not_successive,%ecx
	jmp		abort

0:
#undef temp

#define temp nodeP
	// The associated descriptors of a block are computed here and stored just after the
	// stringtable.
	movl	block_n,temp
	
	shrl	$2,temp
	addl	$31,temp
	shrl	$5,temp								// temp = set size (in words)
	movl	temp,usage_bit_set_size
	
# ifdef MAKE_DUS_SYMBOLIC
	addl	$ DUS_FIXED_ENTRY_WSIZE,temp		// temp = set size + size of fixed part
# else
	incl	temp								// temp = set size + backup first characters of string
# endif

	movl	temp,set_entry_size_in_words		// store entry size in words
	
	shll	$2,temp
	movl	temp,set_entry_size_in_bytes		// store entry size in bytes
	
# ifdef EXTEND_DESCRIPTOR_USAGE_TABLE
	movl	temp,dus_entry_bsize

	movl	heapP,dus_start
# endif

#define STORE_USAGE_BIT_SET_SIZE
# ifdef STORE_USAGE_BIT_SET_SIZE
# define DUS_USAGE_BIT_SIZE			0
# define DUS_N_USAGE_ENTRIES		4

# define DUS_HEADER_BSIZE		(DUS_N_USAGE_ENTRIES + 4)
# define DUS_HEADER_WSIZE		(DUS_N_USAGE_ENTRIES / MACHINE_WORD_BSIZE)

	subl	$2,free
	js		garbage_collection2

# define temp2 %ecx
	movl	usage_bit_set_size,temp2			// store entry size in words
	movl	temp2,DUS_USAGE_BIT_SIZE(heapP)
	
	movl	$0,n_usage_entries					// intilialize usage entry counter
	
	addl	$ DUS_HEADER_BSIZE,heapP
# undef temp2
# endif

	_set_undo_handler $undo_descriptor_usage

	movl	$ compute_descriptor_usage,%ecx
	call	MAKE_ID_FSN(lb_map_array)
	
	// The top-level dynamic is only inserted in the EN-table and not in the SN-table. Thus
	// compute_descriptor_usage 
	
	movl	$ 0,%ecx
	call	MAKE_ID_FEN(lb_index_of_entry)
	
	call	compute_descriptor_usage
	
	movl	$ compute_descriptor_usage,%ecx
	call	MAKE_ID_FEN(lb_map_array)
	
# ifdef EXTEND_DESCRIPTOR_USAGE_TABLE

# define dus_n_usage_entries %eax
	movl	dus_start,dus_n_usage_entries
	
# define temp3 %ebx
	movl	n_usage_entries,temp3
	movl	temp3,DUS_N_USAGE_ENTRIES(dus_n_usage_entries)
# undef temp3
# undef dus_n_usage_entries

	movl	heapP,dus_end
# endif

	jmp		delete_indirections
#undef temp

	// compute_descriptor_usage:
	// 
	// the descriptor usage table is constructed for each SN-node. The algorithm can
	// be divided in:
	// - creating a dus-entry
	// - marking a dus-entry as used by a colour
	//
	// A dus entry looks like this:
	// 0	first four characters, backuped from the descriptor name
	// 4	library instance number
	// 12	marking set. Size is number of colours.
	// ?
	//
	// dynamicTemp voor root dynamic moet ook een entry in EN krijgen
	// call MAKE_ID_EN (het aflopen van SN is genoeg moet alleen nog root toevoegen)
	// descriptors van arrays 'inherit
	// TODO:
	// - descriptors van arrays (gaat goed)
compute_descriptor_usage:
#define sn_entry %ecx
	// compute pointer to descriptor name (similar to fragment in _copy_name)
#define temp nodeP
	movl	SN_COLOUR(sn_entry),temp
	andl	$ ENSN_COLOUR_GET_COLOUR,temp
	pushl	temp

# ifdef ARRAY_DESCP
	movl	temp,array_colour					// backup array colour for its elements
# endif
	
	movl	SN_DESCP(sn_entry),descP
	
#define LAZY_DYNAMICS_3
# ifdef LAZY_DYNAMICS_3
	cmpl	$ e____SystemDynamic__nbuild__block,descP
	jne		hiero
	movl	$ e____SystemDynamic__nbuild__lazy__block,descP
hiero:
# endif
	
	
#undef sn_entry

# ifdef ARRAY_DESCP
	// descP = descriptor pointer
	// tos	 = colour of parent node
compute_descriptor_usage_got_descP:
	movl	descP,descP_backup
# endif

	call	compute_label_name_ptr
#define desc_nameP source

#define setP descP
	movl	4(desc_nameP),setP
	testl	setP,setP
	jns		3f									// allocate space for four characters and set
	
	shll	$1,setP
	jmp		compute_descriptor_usage_got_space_for_set

	// allocate space
3:
	subl	set_entry_size_in_words,free
	js		GC_FIXED_STACK
	
	// initialize new block
# ifdef STORE_USAGE_BIT_SET_SIZE
	incl	n_usage_entries						// count usage table entries
# endif

	movl	setP,(heapP)						// backup first four characters
	
#define setP_backup arity
	movl	heapP,setP_backup					// backup pointer
	
#define temp nodeP
	movl	heapP,temp
	stc
	rcrl	$1,temp
	movl	temp,4(desc_nameP)					// first four characters of descriptor are marked and are pointer to dus-entry
#undef temp

#define counter nodeP
#define limit descP
	movl	$0,counter
	movl	set_entry_size_in_words,limit
	decl	limit
	addl	$4,heapP
	
4:
	movl	$0,(heapP)
	addl	$4,heapP
	incl	counter
	cmpl	counter,limit
	jne		4b									// empty descriptor usage set					
#undef counter
#undef limit
	
	
# ifdef EXTEND_DUS_WITH_LIBARY_NUMBER
	pushl	setP_backup							// backup ptr to dus entry

	movl	desc_nameP,%ebx						// load address in library
	
	call	find_code_library_instance_nr		// %eax = library instance number

	popl	setP								// restore ptr to dus_entry	
//	movl	$0x99999999,%eax
	movl	%eax,DUS_LIBRARY_NUMBER(setP)		// store library number
# else
	movl	setP_backup,setP					// restore setP
# endif // EXTEND_DUS_WITH_LIBARY_NUMBER
	
#undef setP_backup
compute_descriptor_usage_got_space_for_set:
	// setP = address of set entry
	// tos	= current colour
#define current_colour arity
	popl	current_colour
	call	MAKE_ID_FCT(lb_index_of_entry)		
#define associated_block current_colour
	movl	(associated_block),associated_block
	andl	$0x0000fffc,associated_block

	shrl	$2,associated_block					// get block_n
	
#define word_index_in_set nodeP
	movl	associated_block,word_index_in_set
	shrl	$5,word_index_in_set				// word index in set
	
	movl	word_index_in_set,word_index_in_set

#define bit_index_in_set_word associated_block
	movl	associated_block,bit_index_in_set_word	// index of bit to be set in that word
	andl	$31,bit_index_in_set_word
	
#define temp source
	movl	$1,temp
	shll	%cl,temp							// build proper mask
#undef associated_block
#undef bit_index_in_set_word
	
#define set_word arity
	movl	DUS_FIXED_ENTRY_BSIZE(setP,word_index_in_set,4),set_word
	orl		temp,set_word
	movl	set_word,DUS_FIXED_ENTRY_BSIZE(setP,word_index_in_set,4)
#undef set_word


#undef setP

#undef temp

#undef current_colour

#undef desc_nameP

# ifdef ARRAY_DESCP
	movl	descP_backup,descP

	cmpl	$__ARRAY__+2,descP
	jne 	0f
	
	movl	8(nodeP),descP
	pushl	array_colour
	jmp		compute_descriptor_usage_got_descP
0:
# endif
	ret
# endif // COLOUR_GRAPH

# ifdef COLOUR_GRAPH
// ****
// compute_label_name_ptr
// precondition:
// - descP contains a valid (unmodified) descriptor pointer
// postcondition:
// - source contains the descName

compute_label_name_ptr:
	testl	$2,descP							
	je		0f									// closure detected
	
	movzwl	-2(descP),arity
	cmpl	$256,arity
	jb		1f
	
#define desc_nameP source
	movl	-6(descP),desc_nameP				// get descriptor name
	jmp		compute_descriptor_usage_got_name
	
1:	
# define temp nodeP
	movzwl	(descP),temp						// temp = partial arity * 8
	
	leal	-2(descP),desc_nameP				// desc_nameP = descP - 2
	subl	temp,desc_nameP						// desc_nameP = descP - arity * 8
	
	movzwl	-2(desc_nameP),temp					// temp = total arity of descriptor
	
	leal	4(desc_nameP,temp,8),desc_nameP		// desc_nameP = ptr to descriptor name
	jmp		compute_descriptor_usage_got_name
	
	// closures
0:
	movl	-8(descP),desc_nameP				// get descP
	
	movl	-4(descP),arity
	cmpl	$0xffffffff,arity
	jne		3f
	movl	$1,arity
3:
	cmpl	$256,arity
	jae		2f
	
	movzwl	-2(desc_nameP),temp
	leal	4(desc_nameP,temp,8),desc_nameP
	jmp		compute_descriptor_usage_got_name
# undef temp
	
2:
	leal	-8(desc_nameP),desc_nameP

compute_descriptor_usage_got_name:
# undef desc_nameP
	ret
# endif // COLOUR_GRAPH

// -----------------------------------------------------------------------------------------
// Heap situation:
// - the modified descriptors i.e. first four characters have been backup and replaced by a pointer in the
//	 descriptor address table.
// - (nodeP) has bit#0 set. Two cases:
//		1) (nodeP) < heapP i.e. an indirection via the encoded graph
//		2) otherwise i.e. (nodeP) is a SN/EN-pointer

// pass 1; DELETE
#define ML(x)				x##_1
#define ENTRY_LABEL			delete_next_indirection_1
#define ENTRY_LABEL_NODEP	delete_next_indirection_in_nodeP_1
#define EXIT_LABEL			deletion_done_1

#define DELETE_PASS

# ifdef COLLECT_AND_RENUMBER_EXTERNAL_TYPE_REFERENCES
# define IGNORE_TYPE_CONS_SYMBOL
# else 
# define RESTORE_MODULE_ID
# error "ddd"
# endif 

#define RESTORE_BUILD_BLOCK
delete_indirections:	
	movl	$0,n_nodes

#define t0 %eax
	movl	stackTop,t0
	movl	t0,descStackTop
#undef t0
	movl	root_node,nodeP
	
	// descriptor prefix table may never start at offset 0
	movl	$0,function_name_list
	movl	$0,module_name_list

	movl	heapP,string_table_base

	jmp		ML(delete_next_indirection_in_nodeP)

#include "gts_delete.c"

#undef EXIT_LABEL


# include "gts_adjust_descriptor_offsets.c"

	.align 4
deletion_done_1:
	movl	heapP,string_table_end
	
#define	name_p arity
#define temp   nodeP
#define temp2 descP
removing_forwarding_pointers_in_strings:
	movl	function_name_list,name_p
#define t0 stackP
#define t1 source
#define t2 heapP
	pushl	t0
	pushl	t1
	pushl	t2
	movl	stackTop,t0
	movl	string_table_base,t2
	
remove_function_names:
 	jecxz	end_remove_function_names
 	
	movl	(name_p),temp					// temp = address function name in descriptor
	shll	$1,temp						
	
	movl	(temp),temp
	andl	$0x00ffffff,temp
	nop
	leal	(t2,temp),temp					// temp = address in string table
	nop 
		
	movl	-4(temp),temp2					// get length
	movl	temp2,(name_p)					// restore length in descriptor string
	
	movl	(temp),temp2					// get 1st four characters
	xchg	temp2,4(name_p)					// exchange name_p with 1st four chars
	
	movl	temp2,name_p
	jmp	remove_function_names

end_remove_function_names:
	popl	t2
	popl	t1
	popl	t0
#undef t2
#undef t1
#undef t0

	movl	module_name_list,name_p
	
remove:
	jecxz	end_remove_forwarding_pointers

	movl	(name_p),temp		
	shll	$1,temp							// temp = pointer to name of function
	
	movl	-4(temp),temp2					// get length
	movl	temp2,(name_p)					// restore length in descriptor string
	
	movl	(temp),temp2					// get 1st four characters
	xchg	temp2,4(name_p)					// exchange name_p with 1st four chars
	
	movl	temp2,name_p
	jmp	remove
	
end_remove_forwarding_pointers:
#undef temp
#undef name_p
#undef temp2	

# ifdef COLOUR_GRAPH
	testl	free,free
	js		garbage_collection2				// graph has been restored, do a gc (graph has been restored)

	_set_default_undo_handler
	
	movl	$ mark_EN_nodes_as_such,%ecx 	// EN-nodes are marked by setting bit#0
	call	MAKE_ID_FEN(lb_map_array)
	
	// computing the proper descP offset within a single component. The dynamic linker
	// will use the order of the descriptor address table to build a table for each block
	// separately.
	//
	// First the entry nodes of a particular block are traversed and marked as having been
	// visited, offsets are adapted accordingly.	
	
	pushl	%edi
	movl	$ adjust_offset_per_block,%ecx
	call	MAKE_ID_FBI(lb_map_array)
	
	movl	$ unmark_EN_nodes_as_such,%ecx
	call	MAKE_ID_FEN(lb_map_array)
	
	popl	%edi
	// encode descriptor prefix table ...
	
# define dus_p		arity
# define dus_end_p	descP

	movl	dus_start,dus_p
#  ifdef STORE_USAGE_BIT_SET_SIZE
	leal	DUS_HEADER_BSIZE(dus_p),dus_p	// skip usage entry size
#  endif // STORE_USAGE_BIT_SET_SIZE

	movl	dus_end,dus_end_p
0:
# define temp nodeP
	movl	(dus_p),temp					// get descriptor prefix table ptr
	movl	DPT_PREFIX_SET_AND_STRING_PTR(temp),temp
	movl	temp,(dus_p)
# undef temp	

	addl	dus_entry_bsize,dus_p
	
	cmpl	dus_end_p,dus_p
	jb		0b
# undef dus_p
# undef dus_end_p
	// ... encode descriptor prefix table	

# else
# include "gts_old_shared_prefixes"
# endif // COLOUR_GRAPH

#include "gts_return.c"