X-Git-Url: http://nitlanguage.org

diff --git a/src/analysis/allocate_iregister_slots.nit b/src/analysis/allocate_iregister_slots.nit
index 3d22c30..98c8e89 100644
--- a/src/analysis/allocate_iregister_slots.nit
+++ b/src/analysis/allocate_iregister_slots.nit
@@ -18,6 +18,7 @@
 package allocate_iregister_slots
 
 import icode
+private import primitive_info
 
 # The main class that performs the iregister slot allocation
 # The algorithm is quite naive but works
@@ -26,26 +27,34 @@ import icode
 #  * register aliasing
 #  * IMove optimization
 class IRegisterSlotAllocationVisitor
-special ICodeVisitor
+	super ICodeVisitor
 	# The visitor works in two pass:
 	# First pass is used to detect first and last iregisters occurences and slot groups
 	# Second pass is used to assign an effective slot to iregsiters
 	var _pass: Int = 0
 
+	# Update locality information of r according to the current iroutine
+	fun mark_locality(r: IRegister)
+	do
+		if r._is_local and r._local_iroutine != _current_ir then
+			if r._local_iroutine == null then
+				r._local_iroutine = _current_ir
+			else
+				r._is_local = false
+			end
+		end
+	end
+
 	redef fun visit_iregister_read(ic: ICode, r: IRegister)
 	do
+		# Note: the algo considers that a read implies that a write occured before:
+		#       it is why there is no _first assigment nor register call
 		var pass = _pass
 		if pass == 0 then
-			if r._is_local and r._local_iroutine != _current_ir then
-				if r._local_iroutine == null then
-					r._local_iroutine = _current_ir
-				else
-					r._is_local = false
-				end
-			end
-			_lasts[r] = ic
+			mark_locality(r)
+			r._last = ic
 			r._slot_index = null
-		else if pass == 1 and _lasts.has_key(r) and _lasts[r] == ic then
+		else if pass == 1 and r._last == ic then
 			free(r)
 		end
 	end
@@ -54,63 +63,59 @@ special ICodeVisitor
 	do
 		var pass = _pass
 		if pass == 0 then
-			# Process locality
-			if r._is_local and r._local_iroutine != _current_ir then
-				if r._local_iroutine == null then
-					r._local_iroutine = _current_ir
-				else
-					r._is_local = false
-				end
-			end
+			mark_locality(r)
 			r._slot_index = null
 			# The first write make it live
-			if not _firsts.has_key(r) then _firsts[r] = ic
-			# A read iregistre is stile live on a write
-			if _lasts.has_key(r) then _lasts[r] = ic
+			if r._first == null then r._first = ic
+			# A read iregistre is still live on a write
+			if r._last != null then r._last = ic
 		else if pass == 1 then
-			if _firsts[r] == ic then
+			if r._first == ic then
 				register(r)
-			else if _lasts.has_key(r) and _lasts[r] == ic then
+			else if r._last == ic then
 				free(r)
 			end
 		end
 	end
 
+
+	# The current loop/closure identifier.
 	# Iregister from outside a loop/closure cannot die inside the loop/closure
 	# So, the only register that can die in loops/closure are those born inside the loop/closure
+	var _current_rank: Int = 0
 
-	# Registers born in the current loop/closure
-	# So they can die immediatly if needed
-	var _live: HashSet[IRegister] = new HashSet[IRegister]
+	# The number of the last loop/closure created
+	var _max_rank: Int = 0
 
-	# Registers born outsde the current loop/closure that wanted to die
-	# Thez will be effectively freed at the end of the loop/closure
-	var _deferred: HashSet[IRegister] = new HashSet[IRegister]
+	# List of iregisters whose free is delayed because of a loop/closure
+	# They will be freed at the end of each loop/closure if possible
+	var _deferred_list: List[IRegister] = new List[IRegister]
 
-	# Free the deferred that can be freed
-	# "Can" because of neested loops/closures
-	# new_def will be cleared and used as the new _deferred attribute
-	fun deferred_free(new_def: HashSet[IRegister])
+	# Free the deferred registers (from _deferred_list) that can be freed
+	# Registers that cannot be freed remain in the list
+	fun deferred_free
 	do
-		var old_def = _deferred
-		if not old_def.is_empty then
-			new_def.clear
-			_deferred = new_def
-			for r in old_def do
+		var def = _deferred_list.iterator
+		var cur = _current_rank
+		while def.is_ok do
+			var r = def.item
+			if r._born_rank >= cur then
 				free(r)
+				def.delete
 			end
+			def.next
 		end
 	end
 
 	redef fun visit_icode(ic)
 	do
 		if _pass == 1 and ic isa ILoop then
-			var old_live = _live
-			var new_live = new HashSet[IRegister]
-			_live = new_live
+			var old_rank = _current_rank
+			_max_rank += 1
+			_current_rank = _max_rank
 			super
-			_live = old_live
-			deferred_free(new_live)
+			_current_rank = old_rank
+			deferred_free
 		else
 			super
 		end
@@ -119,12 +124,12 @@ special ICodeVisitor
 	redef fun visit_closure_defs(closdefs)
 	do
 		if _pass == 1 then
-			var old_live = _live
-			var new_live = new HashSet[IRegister]
-			_live = new_live
+			var old_rank = _current_rank
+			_max_rank += 1
+			_current_rank = _max_rank
 			super
-			_live = old_live
-			deferred_free(new_live)
+			_current_rank = old_rank
+			deferred_free
 		else
 			super
 		end
@@ -141,16 +146,18 @@ special ICodeVisitor
 			var old_ir = _current_ir
 			_current_ir = ir
 			for r in ir.params do
-				_firsts[r] = self
+				r._first = self
+				mark_locality(r)
 			end
 			super
 			if res != null then
-				_lasts[res] = self
+				res._last = self
+				mark_locality(res)
 			end
 			_current_ir = old_ir
 		else
-			var old_bool_slots = _bool_slots
-			_bool_slots = new SlotGroup
+			var old_tag_slots = _tag_slots
+			_tag_slots = new SlotGroup
 			var old_std_slots = _std_slots
 			if ir isa IClosureDef then
 				_std_slots = new SlotGroup
@@ -160,8 +167,8 @@ special ICodeVisitor
 			end
 			super
 			if res != null then free(res)
-			ir._bool_slots_nb = _bool_slots._next_index
-			_bool_slots = old_bool_slots
+			ir._tag_slots_nb = _tag_slots._next_index
+			_tag_slots = old_tag_slots
 			ir._std_slots_nb = _std_slots._next_index
 			_std_slots = old_std_slots
 		end
@@ -174,53 +181,45 @@ special ICodeVisitor
 	# In main iroutine, _global_slots == _std_slots
 	var _std_slots: SlotGroup
 
-	# Bool slots are used to store local boolean registers
-	var _bool_slots: SlotGroup = new SlotGroup
+	# Tag slots are used to store local tagged object registers
+	var _tag_slots: SlotGroup = new SlotGroup
 
 	# Assign a slot to a register according to its locality and its type
 	fun register(r: IRegister)
 	do
-		if not _lasts.has_key(r) then return
+		if r._last == null then return
 		assert r._slot_index == null
-		_live.add(r)
+		r._born_rank = _current_rank
 		if not r._is_local then
 			_global_slots.register(r)
-		else if (r.stype.local_class.name == once ("Bool".to_symbol)) then
-			r._in_bool_slots = true
-			_bool_slots.register(r)
+		else if r.stype.is_tagged then
+			r._in_tag_slots = true
+			_tag_slots.register(r)
 		else
 			_std_slots.register(r)
 		end
 	end
 
 	# Release a register, thus its slot can be reused
+	# If the register is not freable (born in a enclosing loop/closure), then the freeing is deferred
 	fun free(r: IRegister)
 	do
 		var i = r._slot_index
 		if i == null then return
-		if not _live.has(r) then
-			_deferred.add(r)
-		else if _lasts.has_key(r) then
-			if r._in_bool_slots then
-				_bool_slots.free(r)
+		if r._born_rank < _current_rank then
+			_deferred_list.add(r)
+		else if r._last != null then
+			if r._in_tag_slots then
+				_tag_slots.free(r)
 			else if r._is_local then
 				_std_slots.free(r)
 			else
 				_global_slots.free(r)
 			end
-			_lasts.remove_at(r) # Free a register only once
+			r._last = null # Free a register only once
 		end
 	end
 
-	# What is the first occurences of iregisters
-	# So that a slot is not needed before
-	var _firsts: HashMap[IRegister, Object] = new HashMap[IRegister, Object]
-
-	# What is the last occurences of iregisters
-	# So that a slot may be no more needed after
-	# ("may" because of loops/closure)
-	var _lasts: HashMap[IRegister, Object] = new HashMap[IRegister, Object]
-
 	# Run the slot allocation
 	fun iroutine_slot_allocation
 	do
@@ -228,6 +227,7 @@ special ICodeVisitor
 		visit_iroutine(ir)
 		_pass = 1
 		visit_iroutine(ir)
+		assert _deferred_list.is_empty
 	end
 
 	init(ir: IRoutine)
@@ -267,8 +267,8 @@ redef class IRoutine
 	# The number of standard slots (stored in an array)
 	readable var _std_slots_nb: Int = 0
 
-	# The number of bool slots
-	readable var _bool_slots_nb: Int = 0
+	# The number of tag slots
+	readable var _tag_slots_nb: Int = 0
 
 	fun allocate_iregister_slots
 	do
@@ -289,6 +289,20 @@ redef class IRegister
 	# If is_local, then what iroutine
 	readable writable var _local_iroutine: nullable IRoutine
 
-	# Is the register stored in the bool slot groups?
-	readable writable var _in_bool_slots: Bool = false
+	# Is the register stored in the tag slot group?
+	readable writable var _in_tag_slots: Bool = false
+
+	# What is the first occurences of the iregister
+	# So that a slot is not needed before
+	var _first: nullable Object = null
+
+	# What is the last occurences of the iregister
+	# So that a slot may be no more needed after
+	# ("may" because of loops/closure)
+	var _last: nullable Object = null
+
+	# Rank of the loop/closure where the iregister is born
+	# So it can die immediatly if this is the current loop/closure
+	# 0 means top-level
+	var _born_rank: Int = 0
 end