1 (* Copyright (C) 2017 Matthew Fluet.
2 * Copyright (C) 1999-2007 Henry Cejtin, Matthew Fluet, Suresh
3 * Jagannathan, and Stephen Weeks.
4 * Copyright (C) 1997-2000 NEC Research Institute.
6 * MLton is released under a BSD-style license.
7 * See the file MLton-LICENSE for details.
10 functor AllocateRegisters (S: ALLOCATE_REGISTERS_STRUCTS): ALLOCATE_REGISTERS =
21 structure Function = Function
23 structure Label = Label
31 structure CType = CType
32 structure Operand = Operand
33 structure Register = Register
34 structure Runtime = Runtime
35 structure StackOffset = StackOffset
38 structure Live = Live (Rssa)
46 val get: t * Type.t -> t * {offset: Bytes.t}
47 val layout: t -> Layout.t
48 val new: StackOffset.t list -> t
49 val size: t -> Bytes.t
54 val getRegister: t * Type.t -> Register.t
55 val getStack: t * Type.t -> {offset: Bytes.t}
56 val layout: t -> Layout.t
57 val new: StackOffset.t list * Register.t list -> t
58 val stack: t -> Stack.t
59 val stackSize: t -> Bytes.t
64 (* Keep a list of allocated slots sorted in increasing order of offset.
66 datatype t = T of {offset: Bytes.t, size: Bytes.t} list
68 fun layout (T alloc) =
69 List.layout (fn {offset, size} =>
70 Layout.record [("offset", Bytes.layout offset),
71 ("size", Bytes.layout size)])
78 val {offset, size} = List.last alloc
80 Bytes.+ (offset, size)
86 Array.fromListMap (alloc, fn StackOffset.T {offset, ty} =>
88 size = Type.bytes ty})
91 (a, fn (r, r') => Bytes.<= (#offset r, #offset r'))
92 fun loop (alloc, ac) =
95 | [a] => List.rev (a::ac)
96 | (a1 as {offset = offset1, size = size1})::(a2 as {offset = offset2, size = size2})::alloc =>
97 if Bytes.equals (Bytes.+ (offset1, size1), offset2)
98 then loop ({offset = offset1, size = Bytes.+ (size1, size2)}::alloc, ac)
99 else loop (a2::alloc, a1::ac)
101 T (loop (Array.toList a, []))
104 fun get (T alloc, ty) =
106 val slotSize = Type.bytes ty
107 fun loop (alloc, a as {offset, size}, ac) =
109 val prevEnd = Bytes.+ (offset, size)
110 val begin = Type.align (ty, prevEnd)
112 if Bytes.equals (prevEnd, begin)
113 then ({offset = offset, size = Bytes.+ (size, slotSize)}, ac)
114 else ({offset = begin, size = slotSize}, a :: ac)
119 val (a, ac) = coalesce ()
121 (T (rev (a :: ac)), {offset = begin})
123 | (a' as {offset, size}) :: alloc =>
124 if Bytes.> (Bytes.+ (begin, slotSize), offset)
125 then loop (alloc, a',
126 if Bytes.isZero offset andalso Bytes.isZero size
130 val (a'' as {offset = o', size = s'}, ac) =
135 if Bytes.equals (Bytes.+ (o', s'), offset)
136 then {offset = o', size = Bytes.+ (size, s')} :: alloc
137 else a'' :: a' :: alloc)
139 (T alloc, {offset = begin})
143 loop (alloc, {offset = Bytes.zero, size = Bytes.zero}, [])
147 ("AllocateRegisters.Allocation.Stack.get",
149 Layout.tuple2 (layout, fn {offset} =>
150 Layout.record [("offset", Bytes.layout offset)]))
153 structure Registers =
155 (* A register allocation keeps track of the registers that have
156 * already been allocated, for each runtime type. The reason that
157 * we associate them with runtime types rather than Rssa types is
158 * that the register indices that the codegens use are based on
161 datatype t = T of CType.t -> {alloc: Register.t list,
168 val {alloc, next} = ! (f t)
170 Layout.record [("ty", CType.layout t),
171 ("next", Int.layout next),
172 ("alloc", List.layout Register.layout alloc)]
176 fun compress {next, alloc} =
178 fun loop (next, alloc) =
180 fun done () = {alloc = alloc,
186 if next = Register.index r
187 then loop (next + 1, alloc)
194 fun new (rs: Register.t list): t =
196 fun sameType (r, r') =
198 (Type.toCType (Register.ty r),
199 Type.toCType (Register.ty r'))
200 val rss = List.equivalence (rs, sameType)
204 case List.peek (rss, fn rs =>
209 (t, Type.toCType (Register.ty r))) of
210 NONE => ref {alloc = [], next = 0}
218 Register.index r <= Register.index r')})))
221 fun get (T f, ty: Type.t) =
223 val t = Type.toCType ty
225 val {alloc, next} = !r
226 val reg = Register.new (ty, SOME next)
228 r := compress {alloc = alloc,
235 datatype t = T of {registers: Registers.t,
239 fun make s (T x) = s x
241 val stack = ! o (make #stack)
242 val stackSize = Stack.size o stack
245 fun layout (T {registers, stack}) =
247 [("stack", Stack.layout (!stack)),
248 ("registers", Registers.layout registers)]
250 fun getStack (T {stack, ...}, ty) =
252 val (s, offset) = Stack.get (!stack, ty)
258 fun getRegister (T {registers, ...}, ty) =
259 Registers.get (registers, ty)
261 fun new (stack, registers) =
262 T {registers = Registers.new registers,
263 stack = ref (Stack.new stack)}
268 type t = {live: Operand.t vector,
269 liveNoFormals: Operand.t vector,
272 fun layout ({live, liveNoFormals, size, ...}: t) =
274 [("live", Vector.layout Operand.layout live),
275 ("liveNoFormals", Vector.layout Operand.layout liveNoFormals),
276 ("size", Bytes.layout size)]
279 (* ------------------------------------------------- *)
281 (* ------------------------------------------------- *)
283 fun allocate {formalsStackOffsets,
284 function = f: Rssa.Function.t,
285 varInfo: Var.t -> {operand: Machine.Operand.t option ref option,
293 fun diagVar (x: Var.t): unit =
295 [Var.layout x, str " ",
297 (fn r => Option.layout Operand.layout (!r))
298 (#operand (varInfo x))])
299 fun diagStatement (s: R.Statement.t): unit =
300 R.Statement.foreachDef (s, diagVar o #1)
302 f (display, diagVar, diagStatement)
305 Control.diagnostic (fn () =>
307 in seq [str "Function allocs for ",
308 Func.layout (Function.name f)]
310 val {labelLive, remLabelLive} =
311 Live.live (f, {shouldConsider = isSome o #operand o varInfo})
312 val {args, blocks, name, ...} = Function.dest f
314 * Decide which variables will live in stack slots and which
315 * will live in registers.
317 * - all formals are put in stack slots
318 * - everything else is put in a register.
319 * Variables get moved to the stack if they are
320 * - live at the beginning of a Cont block; such variables are
321 * live while the frame is suspended during a non-tail call
322 * and must be stack allocated to be traced during a GC
323 * - live at the beginning of a CReturn block that mayGC; such
324 * variables are live while the frame is suspended during a
325 * C call and must be stack allocated to be traced during
327 * Both of the above are indiced by Kind.frameStyle kind =
328 * Kind.OffsetsAndSize
330 datatype place = Stack | Register
331 val {get = place: Var.t -> place ref, rem = removePlace, ...} =
332 Property.get (Var.plist, Property.initFun (fn _ => ref Register))
333 (* !hasHandler = true iff handlers are installed in this function. *)
334 val hasHandler: bool ref = ref false
335 fun forceStack (x: Var.t): unit = place x := Stack
336 val _ = Vector.foreach (args, forceStack o #1)
340 fn R.Block.T {kind, label, statements, ...} =>
342 val {beginNoFormals, ...} = labelLive label
344 case Kind.frameStyle kind of
346 | Kind.OffsetsAndSize =>
347 Vector.foreach (beginNoFormals, forceStack)
348 | Kind.SizeOnly => ()
351 andalso (Vector.exists
354 datatype z = datatype R.Statement.t
358 | SetExnStackLocal => true
359 | SetExnStackSlot => true
360 | SetSlotExnStack => true
363 then hasHandler := true
368 fun allocateVar (x: Var.t, a: Allocation.t): unit =
370 val {operand, ty} = varInfo x
378 val {offset} = Allocation.getStack (a, ty)
381 (StackOffset.T {offset = offset, ty = ty})
385 (Allocation.getRegister (a, ty))
386 val () = removePlace x
390 | SOME r => r := SOME oper
398 ("AllocateRegisters.allocateVar", Var.layout, Allocation.layout, Unit.layout)
400 (* Set the stack slots for the formals.
401 * Also, create a stack allocation that includes all formals; if
402 * link and handler stack slots are required, then they will be
403 * allocated against this stack.
408 (args, formalsStackOffsets args, [],
409 fn ((x, _), so, stack) =>
410 (valOf (#operand (varInfo x)) := SOME (Operand.StackOffset so)
412 (* Allocate stack slots for the link and handler, if necessary. *)
413 val handlerLinkOffset =
417 (* Choose fixed and permanently allocated stack
418 * slots that do not conflict with formals.
420 val (stack, {offset = handler, ...}) =
421 Allocation.Stack.get (stack, Type.label (Label.newNoname ()))
422 val (_, {offset = link, ...}) =
423 Allocation.Stack.get (stack, Type.exnStack ())
425 SOME {handler = handler, link = link}
428 fun getOperands (xs: Var.t vector): Operand.t vector =
429 Vector.map (xs, fn x => valOf (! (valOf (#operand (varInfo x)))))
432 ("AllocateRegisters.getOperands",
433 Vector.layout Var.layout, Vector.layout Operand.layout)
435 val {get = labelInfo: R.Label.t -> Info.t, set = setLabelInfo, ...} =
436 Property.getSetOnce (R.Label.plist,
437 Property.initRaise ("labelInfo", R.Label.layout))
440 ("AllocateRegisters.setLabelInfo",
441 R.Label.layout, Info.layout, Unit.layout)
443 (* Do a DFS of the control-flow graph. *)
446 (f, fn R.Block.T {args, label, kind, statements, transfer, ...} =>
448 val {begin, beginNoFormals, handler = handlerLive,
449 link = linkLive} = labelLive label
450 val () = remLabelLive label
451 fun addHS (ops: Operand.t vector): Operand.t vector =
452 case handlerLinkOffset of
454 | SOME {handler, link} =>
461 Operand.stackOffset {offset = handler,
467 Operand.stackOffset {offset = link,
468 ty = Type.exnStack ()}
472 Vector.concat [Vector.fromList extra, ops]
474 val liveNoFormals = getOperands beginNoFormals
475 val (stackInit, registersInit) =
477 (liveNoFormals, ([],[]), fn (oper, (stack, registers)) =>
479 Operand.StackOffset s => (s::stack, registers)
480 | Operand.Register r => (stack, r::registers)
481 | _ => (stack, registers))
483 case handlerLinkOffset of
485 | SOME {handler, link} =>
486 StackOffset.T {offset = handler,
487 ty = Type.label (Label.newNoname ())}
488 :: StackOffset.T {offset = link,
489 ty = Type.exnStack ()}
491 val a = Allocation.new (stackInit, registersInit)
495 (case handlerLinkOffset of
496 NONE => Error.bug "AllocateRegisters.allocate: Handler with no handler offset"
497 | SOME {handler, ...} =>
498 Bytes.+ (Runtime.labelSize (), handler))
503 (Runtime.labelSize (),
504 Bytes.alignWord32 (Allocation.stackSize a))
506 case !Control.align of
507 Control.Align4 => size
508 | Control.Align8 => Bytes.alignWord64 size
511 if Bytes.isWord32Aligned size
513 else Error.bug (concat ["AllocateRegisters.allocate: ",
516 " in ", Label.toString label])
517 val _ = Vector.foreach (args, fn (x, _) => allocateVar (x, a))
518 (* Must compute live after allocateVar'ing the args, since that
519 * sets the operands for the args.
521 val live = getOperands begin
522 fun one (var, _) = allocateVar (var, a)
524 Vector.foreach (statements, fn statement =>
525 R.Statement.foreachDef (statement, one))
526 val _ = R.Transfer.foreachDef (transfer, one)
528 setLabelInfo (label, {live = addHS live,
529 liveNoFormals = addHS liveNoFormals,
536 (fn (display, diagVar, diagStatement) =>
540 display (seq [str "function ", Func.layout name,
541 str " handlerLinkOffset ",
543 (fn {handler, link} =>
544 record [("handler", Bytes.layout handler),
545 ("link", Bytes.layout link)])
547 val _ = Vector.foreach (args, diagVar o #1)
550 (blocks, fn R.Block.T {label, args, statements, ...} =>
552 val {live, ...} = labelInfo label
553 val () = display (R.Label.layout label)
556 (seq [str "live: ", Vector.layout Operand.layout live])
557 val () = Vector.foreach (args, diagVar o #1)
558 val () = Vector.foreach (statements, diagStatement)
565 {handlerLinkOffset = handlerLinkOffset,
566 labelInfo = labelInfo}
571 ("AllocateRegisters.allocate",
572 fn {function, ...} => Func.layout (Function.name function),