# * 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
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
mark_locality(r)
- _lasts[r] = ic
+ 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
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
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
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
# 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.is_tagged then
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._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
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
visit_iroutine(ir)
_pass = 1
visit_iroutine(ir)
+ assert _deferred_list.is_empty
end
init(ir: IRoutine)
# 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
nitlanguage / nit.git / blobdiff