transitiveClosure.scala 15.5 KB
Newer Older
Kunshan Wang's avatar
Kunshan Wang committed
1
2
3
4
5
6
7
8
9
10
package uvm.refimpl.bootimg

import scala.collection.immutable.TreeMap
import scala.collection.mutable.{ Set, Queue }

import org.slf4j.LoggerFactory

import com.typesafe.scalalogging.Logger

import uvm._
Kunshan Wang's avatar
Kunshan Wang committed
11
import uvm.ir.irbuilder.IRBuilder
Kunshan Wang's avatar
Kunshan Wang committed
12
13
14
15
16
17
import uvm.refimpl._
import uvm.refimpl.itpr._
import uvm.refimpl.mem.HeaderUtils
import uvm.refimpl.mem.Space
import uvm.refimpl.mem.TypeSizes
import uvm.refimpl.mem.scanning.MemoryDataScanner
Kunshan Wang's avatar
Kunshan Wang committed
18
import uvm.refimpl.mem.scanning.MemoryFieldHandler
Kunshan Wang's avatar
Kunshan Wang committed
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import uvm.ssavariables._
import uvm.types._

object TransitiveClosure {
  def apply[T](initialElems: T*) = new TransitiveClosure(initialElems)
}

class TransitiveClosure[T](initialElems: Seq[T]) {
  val set = Set[T](initialElems: _*)
  val queue = Queue[T](initialElems: _*)

  def hasPending = !queue.isEmpty
  def dequeue() = queue.dequeue()
  def maybeEnqueue(elem: T): Boolean = {
    if (set.contains(elem)) {
      false
    } else {
      set += elem
      queue += elem
      true
    }
  }
  def +=(elem: T): TransitiveClosure[T] = { maybeEnqueue(elem); this }
  def ++=(elems: Seq[T]): TransitiveClosure[T] = { elems.foreach(this +=); this }
}

object TransitiveClosureBuilder {
  val logger = Logger(LoggerFactory.getLogger(getClass.getName))

  implicit class RichTransitiveClosure[T <: Identified](val tc: TransitiveClosure[T]) extends AnyVal {
49
    def ?=(elem: SSAVariable): TransitiveClosure[T] = {
Kunshan Wang's avatar
Kunshan Wang committed
50
51
52
53
54
      if (elem.isInstanceOf[GlobalVariable]) {
        tc += elem.asInstanceOf[T]
      }
      tc
    }
55
    def ??=(elems: Seq[SSAVariable]): TransitiveClosure[T] = {
Kunshan Wang's avatar
Kunshan Wang committed
56
57
58
59
60
      for (elem <- elems) {
        this ?= elem
      }
      tc
    }
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
    def ??=(dest: DestClause): TransitiveClosure[T] = {
      this ??= dest.args
      tc
    }
    def ??=(maybeExcClause: Option[ExcClause]): TransitiveClosure[T] = {
      maybeExcClause foreach { excClause =>
        this ??= excClause.nor.args ??= excClause.exc.args
      }
      tc
    }
    def ???=(maybeElem: Option[SSAVariable]): TransitiveClosure[T] = { // More ? to work around type erasure
      for (elem <- maybeElem) {
        this ?= elem
      }
      tc
    }
    def ????=(maybeDest: Option[DestClause]): TransitiveClosure[T] = {
      for (dest <- maybeDest) {
        this ??= dest.args
      }
      tc
    }
Kunshan Wang's avatar
Kunshan Wang committed
83
84
85
86
87
  }

  case class GlobalCellRec(begin: Word, end: Word, g: GlobalCell)
}

Kunshan Wang's avatar
Kunshan Wang committed
88
89
class TransitiveClosureBuilder(initialSet: Seq[TopLevel], val primordial: PrimordialInfo)(
    implicit microVM: MicroVM) extends MemoryFieldHandler {
Kunshan Wang's avatar
Kunshan Wang committed
90
  import TransitiveClosureBuilder._
91

Kunshan Wang's avatar
Kunshan Wang committed
92
93
94
  private val globalMemory: Space = microVM.memoryManager.globalMemory
  private val smallObjectSpace: Space = microVM.memoryManager.heap.space
  private val largeObjectSpace: Space = microVM.memoryManager.heap.los
95
  private implicit val memorySupport = microVM.memoryManager.memorySupport
Kunshan Wang's avatar
Kunshan Wang committed
96
97
98
99
100

  /**
   * Top-level definitions in the closure. Function versions are not considered top-level here. A function may have at
   * most one function version. Only that version is serialised into the boot image.
   */
101
  val tls = TransitiveClosure[TopLevel](initialSet: _*)
Kunshan Wang's avatar
Kunshan Wang committed
102
103
104
105
106

  /**
   * Global cells + heap objects.
   */
  val allocs = TransitiveClosure[Word]()
Kunshan Wang's avatar
Kunshan Wang committed
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
  
  // Put the primordial function/stack and the thread-local into the set
  {
    val PrimordialInfo(pf, ps, ptl) = primordial
    
    if (ps.isDefined) {
      throw new BootImageBuilderException("Building boot image using a stack is not implemented. The current way is to specify the stack-bottom function.")
    }
    
    pf foreach { func =>
      // If the primordial function/stack is specified, add it.
      tls += func
      
      ptl foreach { addr =>
        // Also add the thread-local if specified.
        allocs += addr
      }
    }
  }
Kunshan Wang's avatar
Kunshan Wang committed
126

Kunshan Wang's avatar
Kunshan Wang committed
127
  private def getGlobalCellAddr(g: GlobalCell): Word = {
Kunshan Wang's avatar
Kunshan Wang committed
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
    microVM.constantPool.getGlobalVarBox(g).asInstanceOf[BoxIRef].addr
  }

  /**
   * Map the global cell's starting address to the global cell itself.
   */
  val globalCellMap = {
    val elems = microVM.globalBundle.globalCellNs.all.toSeq.map { g =>
      val begin = getGlobalCellAddr(g)
      val ty = g.cellTy
      assert(!ty.isInstanceOf[TypeHybrid])
      val size = TypeSizes.sizeOf(ty)
      val end = begin + size
      (begin, GlobalCellRec(begin, end, g))
    }
    TreeMap[Word, GlobalCellRec](elems: _*)
  }
145
146
147
148
149
150
151
152
153
154

  def getGlobalCellRecExact(begin: Word): GlobalCellRec = {
    require(microVM.memoryManager.globalMemory.isInSpace(begin),
      "Address %d 0x%x is not in the global space".format(begin, begin))

    val gcr = globalCellMap(begin)

    gcr
  }

Kunshan Wang's avatar
Kunshan Wang committed
155
156
  def getGlobalCellRec(iref: Word): GlobalCellRec = {
    require(microVM.memoryManager.globalMemory.isInSpace(iref),
157
158
      "Address %d 0x%x is not in the global space".format(iref, iref))

Kunshan Wang's avatar
Kunshan Wang committed
159
160
    val (begin, gcr) = globalCellMap.to(iref).last
    assert(begin <= iref && iref < gcr.end,
161
162
      "Address %d 0x%x is in the global space, but the previous global cell's address range is %d 0x%x - %d 0x%x".format(
        iref, iref, begin, begin, gcr.end, gcr.end))
Kunshan Wang's avatar
Kunshan Wang committed
163
164
165
166

    gcr
  }

167
  def maybeGetGlobalCellRec(iref: Word): Option[GlobalCellRec] = {
Kunshan Wang's avatar
Kunshan Wang committed
168
169
170
171
172
    if (microVM.memoryManager.globalMemory.isInSpace(iref)) {
      for ((begin, gcr) <- globalCellMap.to(iref).lastOption) yield {
        assert(begin <= iref && iref < gcr.end,
          "Address %d 0x%x is in the global space, but the previous global cell's address range is %d 0x%x - %d 0x%x".format(
            iref, iref, begin, begin, gcr.end, gcr.end))
173

Kunshan Wang's avatar
Kunshan Wang committed
174
175
176
177
        gcr
      }
    } else { 
      None
178
179
180
    }
  }

Kunshan Wang's avatar
Kunshan Wang committed
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
  def doTransitiveClosure(): Unit = {
    while (tls.hasPending || allocs.hasPending) {
      while (tls.hasPending) {
        visitTopLevel(tls.dequeue())
      }
      while (allocs.hasPending) {
        visitAllocUnit(allocs.dequeue())
      }
    }
  }

  private def visitTopLevel(tl: Identified): Unit = {
    tl match {
      case t: Type        => visitType(t)
      case s: FuncSig     => visitFuncSig(s)
      case c: Constant    => visitConstant(c)
      case g: GlobalCell  => visitGlobalCell(g)
      case f: Function    => visitFunction(f)
      case e: ExposedFunc => visitExpFunc(e)
    }
  }

  private def visitType(ty: Type): Unit = ty match {
    case TypeUPtr(t)       => tls += t
    case TypeUFuncPtr(s)   => tls += s
    case TypeStruct(ts)    => tls ++= ts
    case TypeHybrid(fs, v) => tls ++= fs += v
    case TypeArray(t, _)   => tls += t
    case TypeVector(t, _)  => tls += t
    case TypeRef(t)        => tls += t
    case TypeIRef(t)       => tls += t
    case TypeWeakRef(t)    => tls += t
    case TypeFuncRef(s)    => tls += s
    case _                 => // Not nested or recursive. Do nothing.
  }

  private def visitFuncSig(s: FuncSig): Unit = {
    tls ++= s.paramTys ++= s.retTys
  }

  private def visitConstant(c: Constant): Unit = {
    tls += c.constTy

    c match {
      case ConstSeq(_, elems) => tls ++= elems
      case _                  => // Not nested. Do nothing.
    }
  }

  private def visitGlobalCell(g: GlobalCell): Unit = {
    tls += g.cellTy

    allocs += getGlobalCellAddr(g)
  }

  private def visitFunction(f: Function): Unit = {
    tls += f.sig

    microVM.globalBundle.funcToVers(f).headOption match {
      case None => // Undefined. Do nothing
      case Some(mostRecent) => {
        // Visit all TOP-LEVELS (mostly types sigs and SSA variables).
        // This version, including all of its basic blocks and instructions, will be in the boot image. 
        for (bb <- mostRecent.bbs) {
          tls ++= bb.norParams.map(_.ty)

          for (inst <- bb.insts) {
            visitInstruction(inst)
          }
        }
      }
    }
  }

  private def visitExpFunc(e: ExposedFunc): Unit = {
    tls += e.func
    tls += e.cookie
  }

  private def visitInstruction(inst: Instruction): Unit = inst match {
261
    case InstBinOp(op, opndTy, op1, op2, excClause)              => tls += opndTy ?= op1 ?= op2 ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
262
263
264
    case InstCmp(op, opndTy, op1, op2)                           => tls += opndTy ?= op1 ?= op2
    case InstConv(op, fromTy, toTy, opnd)                        => tls += fromTy += toTy ?= opnd
    case InstSelect(condTy, opndTy, cond, ifTrue, ifFalse)       => tls += condTy += opndTy ?= cond ?= ifTrue ?= ifFalse
265
266
267
268
    case InstBranch(dest)                                        => tls ??= dest
    case InstBranch2(cond, ifTrue, ifFalse)                      => tls ?= cond ??= ifTrue ??= ifFalse
    case i @ InstSwitch(opndTy, opnd, defDest, cases)            => tls += opndTy ?= opnd ??= defDest ??= cases.map(_._1)
    case InstCall(sig, callee, argList, excClause, keepalives)   => tls += sig ?= callee ??= argList ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
269
270
271
272
273
274
275
276
    case InstTailCall(sig, callee, argList)                      => tls += sig ?= callee ??= argList
    case InstRet(funcVer, retVals)                               => tls ??= retVals
    case InstThrow(excVal)                                       => tls ?= excVal
    case InstExtractValue(strTy, index, opnd)                    => tls += strTy ?= opnd
    case InstInsertValue(strTy, index, opnd, newVal)             => tls += strTy ?= opnd ?= newVal
    case InstExtractElement(seqTy, indTy, opnd, index)           => tls += seqTy += indTy ?= opnd ?= index
    case InstInsertElement(seqTy, indTy, opnd, index, newVal)    => tls += seqTy += indTy ?= opnd ?= index ?= newVal
    case InstShuffleVector(vecTy, maskTy, vec1, vec2, mask)      => tls += vecTy += maskTy ?= vec1 ?= vec2 ?= mask
277
278
279
280
    case InstNew(allocTy, excClause)                             => tls += allocTy ??= excClause
    case InstNewHybrid(allocTy, lenTy, length, excClause)        => tls += allocTy += lenTy ?= length ??= excClause
    case InstAlloca(allocTy, excClause)                          => tls += allocTy ??= excClause
    case InstAllocaHybrid(allocTy, lenTy, length, excClause)     => tls += allocTy += lenTy ?= length ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
281
282
283
284
285
    case InstGetIRef(referentTy, opnd)                           => tls += referentTy ?= opnd
    case InstGetFieldIRef(ptr, referentTy, index, opnd)          => tls += referentTy ?= opnd
    case InstGetElemIRef(ptr, referentTy, indTy, opnd, index)    => tls += referentTy += indTy ?= opnd ?= index
    case InstShiftIRef(ptr, referentTy, offTy, opnd, offset)     => tls += referentTy += offTy ?= opnd ?= offset
    case InstGetVarPartIRef(ptr, referentTy, opnd)               => tls += referentTy ?= opnd
286
287
    case InstLoad(ptr, ord, referentTy, loc, excClause)          => tls += referentTy ?= loc ??= excClause
    case InstStore(ptr, ord, referentTy, loc, newVal, excClause) => tls += referentTy ?= loc ?= newVal ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
288
    case InstCmpXchg(ptr, weak, ordSucc, ordFail, referentTy, loc, expected, desired, excClause) // This line is long ...
289
290
    => tls += referentTy ?= loc ?= expected ?= desired ??= excClause
    case InstAtomicRMW(ptr, ord, op, referentTy, loc, opnd, excClause) => tls += referentTy ?= loc ?= opnd ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
291
    case InstFence(ord) =>
292
293
294
    case InstTrap(retTys, excClause, keepalives) => tls ++= retTys ??= excClause
    case InstWatchPoint(wpID, retTys, dis, ena, exc, keepalives) => tls ++= retTys ??= dis ??= ena ????= exc
    case InstWPBranch(wpID, dis, ena) => tls ??= dis ??= ena
Kunshan Wang's avatar
Kunshan Wang committed
295
    case InstCCall(callConv, funcTy, sig, callee, argList, excClause, keepalives) // This line is long, too...
296
    => tls += funcTy += sig ?= callee ??= argList ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
297
    case InstNewThread(stack, threadLocal, newStackAction, excClause) => {
298
      tls ?= stack ???= threadLocal ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
299
300
301
      visitNewStackAction(newStackAction)
    }
    case InstSwapStack(swappee, curStackAction, newStackAction, excClause, keepalives) => {
302
      tls ?= swappee ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
303
304
305
306
307
308
309
      curStackAction match {
        case RetWith(ts) => tls ++= ts
        case KillOld()   =>
      }
      visitNewStackAction(newStackAction)
    }
    case InstCommInst(ci, flagList, typeList, funcSigList, argList, excClause, keepalives) =>
310
      tls ++= typeList ++= funcSigList ??= argList ??= excClause
Kunshan Wang's avatar
Kunshan Wang committed
311
312
313
314
315
316
317
318
319

    case _ => throw new BootImageBuilderException("Unknown instruction: " + inst.getClass.getName)
  }

  private def visitNewStackAction(nsa: NewStackAction): Unit = nsa match {
    case PassValues(ts, vs) => tls ++= ts ??= vs
    case ThrowExc(e)        =>
  }

320
321
322
323
324
325
326
327
328
329
330
  /**
   * Visit an allocation unit (global cell or heap object). As a pre-condition, begin must refer to the beginning of
   * the unit.
   *
   * @param begin The beginning of the object.
   */
  private def visitAllocUnit(begin: Word): Unit = {
    logger.debug("Visiting allocation unit 0x%x".format(begin))
    if (globalMemory.isInSpace(begin)) {
      val GlobalCellRec(begin2, end, g) = getGlobalCellRecExact(begin)
      assert(begin2 == begin)
Kunshan Wang's avatar
Kunshan Wang committed
331
332
333
      logger.debug("  It's global cell. begin=0x%x, end=0x%x, type=%s".format(begin, end, g.cellTy))
      tls += g
      visitAllocUnitFields(begin, g.cellTy)
334
335
    } else if (smallObjectSpace.isInSpace(begin) || largeObjectSpace.isInSpace(begin)) {
      val objRef = begin
Kunshan Wang's avatar
Kunshan Wang committed
336
337
338
339
340
      val tag = HeaderUtils.getTag(objRef)
      val ty = HeaderUtils.getType(microVM, tag)
      tls += ty
      visitAllocUnitFields(objRef, ty)
    } else {
341
      throw new BootImageBuilderException("Address %d 0x%x is not in the heap or global space".format(begin, begin))
Kunshan Wang's avatar
Kunshan Wang committed
342
343
    }
  }
344

Kunshan Wang's avatar
Kunshan Wang committed
345
346
347
348
  private def visitAllocUnitFields(begin: Word, ty: Type): Unit = {
    MemoryDataScanner.scanAllocUnit(begin, this)
  }

349
  override def visitRefField(objRef: Word, iRef: Word, toObj: Word, isWeak: Boolean): Unit = {
Kunshan Wang's avatar
Kunshan Wang committed
350
351
352
353
354
    if (toObj != 0L) {
      allocs += toObj
    }
  }

355
356
357
358
359
360
361
362
363
  override def visitIRefField(objRef: Word, iRef: Word, toObj: Word, toOffset: Word): Unit = {
    if (toObj == 0L) {
      if (globalMemory.isInSpace(toOffset)) {
        val gr = getGlobalCellRec(toOffset)
        tls += gr.g
      } else {
        if (largeObjectSpace.isInSpace(toOffset)) {
          throw new BootImageBuilderException(("Error: non-object iref to LOS found. This is probably a reference to " +
            "a stack cell (ALLOCA). It should not exist during boot image building. source: [0x%x + 0x%x] -> dest 0x%x").format(
364
              objRef, iRef, toOffset))
365
366
        } else {
          throw new BootImageBuilderException(("Error: non-object iref not referring to global. source: [0x%x + 0x%x] -> dest 0x%x").format(
367
            objRef, iRef, toOffset))
368
369
370
371
372
373
374
        }
      }
    } else {
      if (toObj != 0L) {
        allocs += toObj
      }
    }
375
  }
376

377
378
379
  override def visitTagRefField(objRef: Word, iRef: Word, toObj: Word): Unit = {
    if (toObj != 0L) {
      allocs += toObj
Kunshan Wang's avatar
Kunshan Wang committed
380
381
382
    }
  }

383
384
385
  override def visitFuncRefField(objRef: Word, iRef: Word, toFunc: Option[Function]): Unit = {
    toFunc.foreach(tls+=)
  }
386

Kunshan Wang's avatar
Kunshan Wang committed
387
388
389
390
391
392
  override def visitUPtrField(objRef: Word, iRef: Word, toAddr: Word): Unit = {
    maybeGetGlobalCellRec(toAddr).foreach{ gcr => 
      tls += gcr.g
    }
  }
  override def visitUFPField(objRef: Word, iRef: Word, toAddr: Word): Unit = {}
393
  override def visitStackRefField(objRef: Word, iRef: Word, toStack: Option[InterpreterStack]): Unit =
394
    toStack.foreach(o => throw noReach("stack", objRef, iRef, o))
395
  override def visitThreadRefField(objRef: Word, iRef: Word, toThread: Option[InterpreterThread]): Unit =
396
    toThread.foreach(o => throw noReach("thread", objRef, iRef, o))
397
  override def visitFCRefField(objRef: Word, iRef: Word, toFCRef: Option[FrameCursor]): Unit =
398
    toFCRef.foreach(o => throw noReach("frame cursor", objRef, iRef, o))
Kunshan Wang's avatar
Kunshan Wang committed
399
400
  override def visitIRBuilderRefField(objRef: Word, iRef: Word, toIRNode: Option[IRBuilder]): Unit =
    toIRNode.foreach(o => throw noReach("IR builder", objRef, iRef, o))
401

402
403
  private def noReach(kind: String, objRef: Word, iRef: Word, obj: AnyRef) =
    new BootImageBuilderException(
404
405
      "Error: Non-null %s field is not allowed in boot image. From: obj 0x%x, iref 0x%x. To stack id: %s".format(
        objRef, iRef, obj))
Kunshan Wang's avatar
Kunshan Wang committed
406
}