alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Scala example source code file (BasicBlocks.scala)

This example Scala source code file (BasicBlocks.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Java - Scala tags/keywords

basicblock, boolean, boolean, dirtypreds, instruction, instruction, instructions, int, int, list, list, nil, position, string

The Scala BasicBlocks.scala source code

/* NSC -- new Scala compiler
 * Copyright 2005-2011 LAMP/EPFL
 * @author  Martin Odersky
 */


package scala.tools.nsc
package backend
package icode

import scala.collection.{ mutable, immutable }
import mutable.{ ArrayBuffer }
import util.{ Position, NoPosition }
import backend.icode.analysis.ProgramPoint

trait BasicBlocks {
  self: ICodes =>
  
  import opcodes._
  import global.{ settings, log, nme }
  import nme.isExceptionResultName

  /** This class represents a basic block. Each
   *  basic block contains a list of instructions that are
   *  either executed all, or none. No jumps
   *  to/from the "middle" of the basic block are allowed (modulo exceptions).
   */
  class BasicBlock(val label: Int, val method: IMethod)
        extends AnyRef
        with ProgramPoint[BasicBlock]
        with Seq[Instruction] {

    import BBFlags._
    
    def code = method.code
    
    /** Flags of this basic block. */
    private var flags: Int = 0

    /** Does this block have the given flag? */
    def hasFlag(flag: Int): Boolean = (flags & flag) != 0
    
    /** Set the given flag. */
    private def setFlag(flag: Int): Unit = flags |= flag
    private def resetFlag(flag: Int) {
      flags &= ~flag
    }
    
    /** Is this block closed? */
    def closed: Boolean = hasFlag(CLOSED)
    def closed_=(b: Boolean) = if (b) setFlag(CLOSED) else resetFlag(CLOSED)
    
    /** When set, the <code>emit methods will be ignored. */
    def ignore: Boolean = hasFlag(IGNORING)
    def ignore_=(b: Boolean) = if (b) setFlag(IGNORING) else resetFlag(IGNORING)

    /** Is this block the head of a while? */
    def loopHeader = hasFlag(LOOP_HEADER)
    def loopHeader_=(b: Boolean) = 
      if (b) setFlag(LOOP_HEADER) else resetFlag(LOOP_HEADER)
    
    /** Is this block the start block of an exception handler? */
    def exceptionHandlerStart = hasFlag(EX_HEADER)
    def exceptionHandlerStart_=(b: Boolean) = 
      if (b) setFlag(EX_HEADER) else resetFlag(EX_HEADER)

    /** Has this basic block been modified since the last call to 'successors'? */
    def touched = hasFlag(DIRTYSUCCS)
    def touched_=(b: Boolean) = if (b) {
      setFlag(DIRTYSUCCS | DIRTYPREDS)
    } else {
      resetFlag(DIRTYSUCCS | DIRTYPREDS)
    }

    // basic blocks start in a dirty state
    setFlag(DIRTYSUCCS | DIRTYPREDS)

    /** Cached predecessors. */
    var preds: List[BasicBlock] = null
    
    /** Local variables that are in scope at entry of this basic block. Used
     *  for debugging information.
     */
    var varsInScope: mutable.Set[Local] = new mutable.LinkedHashSet()
    
    /** ICode instructions, used as temporary storage while emitting code.
     * Once closed is called, only the `instrs' array should be used.
     */
    private var instructionList: List[Instruction] = Nil

    private var instrs: Array[Instruction] = _

    override def toList: List[Instruction] =
      if (closed) instrs.toList else instructionList.reverse
    
    /** Return an iterator over the instructions in this basic block. */
    def iterator: Iterator[Instruction] =
      if (closed) instrs.iterator else instructionList.reverse.iterator
    
    /** return the underlying array of instructions */
    def getArray: Array[Instruction] = {
      assert(closed)
      instrs
    }

    def fromList(is: List[Instruction]) {
      code.touched = true
      instrs = is.toArray
      closed = true
    }

    /** Return the index of inst. Uses reference equality.
     *  Returns -1 if not found.
     */
    def indexOf(inst: Instruction): Int = {
      assert(closed)
      instrs indexWhere (_ eq inst)
    }

    /** Apply a function to all the instructions of the block. */
    override def foreach[U](f: Instruction => U) = {
      if (!closed) {
        method.dump
        global.abort("Traversing an open block!: " + label + " in " + method)
      }
      instrs foreach f
    }

    /** The number of instructions in this basic block so far. */
    def length = if (closed) instrs.length else instructionList.length

    /** Return the n-th instruction. */
    def apply(n: Int): Instruction =
      if (closed) instrs(n) else instructionList.reverse(n)

    ///////////////////// Substitutions ///////////////////////

    /**
     * Replace the instruction at the given position. Used by labels when
     * they are anchored. It retains the position of the previous instruction.
     */
    def replaceInstruction(pos: Int, instr: Instruction): Boolean = {
      assert(closed, "Instructions can be replaced only after the basic block is closed")
      instr.setPos(instrs(pos).pos)
      instrs(pos) = instr
      code.touched = true
      true
    }

    /**
     * Replace the given instruction with the new one. 
     * Returns `true' if it actually changed something. 
     * It retains the position of the previous instruction.
     */
    def replaceInstruction(oldInstr: Instruction, newInstr: Instruction): Boolean = {
      assert(closed, "Instructions can be replaced only after the basic block is closed")
      
      indexOf(oldInstr) match {
        case -1   => false
        case idx  =>
          newInstr setPos oldInstr.pos
          instrs(idx) = newInstr
          code.touched = true
          true
      }
    }

    /** Replaces <code>oldInstr with is. It does not update
     *  the position field in the newly inserted instructions, so it behaves
     *  differently than the one-instruction versions of this function.
     *
     *  @param iold ..
     *  @param is   ..
     *  @return     ..
     */
    def replaceInstruction(oldInstr: Instruction, is: List[Instruction]): Boolean = {
      assert(closed, "Instructions can be replaced only after the basic block is closed")
      
      indexOf(oldInstr) match {
        case -1   => false
        case idx  =>
          instrs = instrs.patch(idx, is, 1)
          code.touched = true
          true
      }
    }
    
    /** Insert instructions in 'is' immediately after index 'idx'. */
    def insertAfter(idx: Int, is: List[Instruction]) {
      assert(closed, "Instructions can be replaced only after the basic block is closed")
      
      instrs = instrs.patch(idx + 1, is, 0)
      code.touched = true
    }

    /** Removes instructions found at the given positions.
     *
     *  @param positions ...
     */
    def removeInstructionsAt(positions: Int*) {
      assert(closed)
      instrs = instrs.indices.toArray filterNot positions.toSet map instrs
      code.touched = true
    }
    
    /** Remove the last instruction of this basic block. It is
     *  fast for an open block, but slower when the block is closed.
     */
    def removeLastInstruction() {
      if (closed) 
        removeInstructionsAt(size)
      else {
        instructionList = instructionList.tail
        code.touched = true
      }
    }

    /** Replaces all instructions found in the map.
     *
     *  @param map ...
     */
    def subst(map: Map[Instruction, Instruction]): Unit =
      if (!closed)
        instructionList = instructionList map (x => map.getOrElse(x, x))
      else
        instrs.zipWithIndex collect {
          case (oldInstr, i) if map contains oldInstr =>
            code.touched |= replaceInstruction(i, map(oldInstr))
        }

    ////////////////////// Emit //////////////////////


    /** Add a new instruction at the end of the block,
     *  using the same source position as the last emitted instruction
     */
    def emit(instr: Instruction) {
      val pos = if (instructionList.isEmpty) NoPosition else instructionList.head.pos
      emit(instr, pos)
    }

    /** Emitting does not set touched to true. During code generation this is a hotspot and
     *  setting the flag for each emit is a waste. Caching should happen only after a block
     *  is closed, which sets the DIRTYSUCCS flag.
     */
    def emit(instr: Instruction, pos: Position) {
/*      if (closed) {
        print()
        Console.println("trying to emit: " + instr)
      } */
      assert(!closed || ignore, "BasicBlock closed")

      if (ignore) {
        if (settings.debug.value) {
          /** Trying to pin down what it's likely to see after a block has been
           *  put into ignore mode so we hear about it if there's a problem.
           */
          instr match {
            case JUMP(_) | RETURN(_) | THROW(_) | SCOPE_EXIT(_)               => // ok
            case STORE_LOCAL(local) if isExceptionResultName(local.sym.name)  => // ok
            case x => log("Ignoring instruction, possibly at our peril, at " + pos + ": " + x)
          }
        }
      }
      else {
        instr.setPos(pos)
        instructionList ::= instr
      }
    }
    
    def emit(instrs: Seq[Instruction]) {
      instrs foreach (i => emit(i, i.pos))
    }
    
    /** The semantics of this are a little odd but it's designed to work
     *  seamlessly with the existing code.  It emits each supplied instruction,
     *  then closes the block.  The odd part is that if the instruction has
     *  pos == NoPosition, it calls the 1-arg emit, but otherwise it calls
     *  the 2-arg emit.  This way I could retain existing behavior exactly by
     *  calling setPos on any instruction using the two arg version which
     *  I wanted to include in a call to emitOnly.
     */
    def emitOnly(instrs: Instruction*) {
      instrs foreach (i => if (i.pos == NoPosition) emit(i) else emit(i, i.pos))
      this.close
    }

    /** do nothing if block is already closed */
    def closeWith(instr: Instruction) {
      if (closed) () else {
        emit(instr)
        close
      }
    }

    def closeWith(instr: Instruction, pos: Position) {
      if (closed) () else {
        emit(instr, pos)
        close
      }
    }

    /** Close the block */
    def close() {
      assert(!closed || ignore)
      assert(instructionList.nonEmpty, "Empty block.")
      closed = true
      setFlag(DIRTYSUCCS)
      instructionList = instructionList.reverse
      instrs = instructionList.toArray
    }

    def open() {
      assert(closed)
      closed = false
      ignore = false
      touched = true
      instructionList = instructionList.reverse  // prepare for appending to the head
    }

    def clear() {
      instructionList = Nil
      instrs = null
      preds  = null
    }

    override def isEmpty: Boolean = instructionList.isEmpty

    /** Enter ignore mode: new 'emit'ted instructions will not be
     *  added to this basic block. It makes the generation of THROW
     *  and RETURNs easier.
     */
    def enterIgnoreMode() = {
      ignore = true
    }

    def exitIgnoreMode() {
      assert(ignore, "Exit ignore mode when not in ignore mode.")
      ignore = false
    }

    /** Return the last instruction of this basic block. */
    def lastInstruction =
      if (closed) instrs.last
      else instructionList.head

    def firstInstruction =
      if (closed) instrs(0)
      else instructionList.last
    
    def exceptionSuccessorsForBlock(block: BasicBlock): List[BasicBlock] =
      method.exh collect { case x if x covers block => x.startBlock }

    /** Cached value of successors. Must be recomputed whenever a block in the current method is changed. */
    private var succs: List[BasicBlock] = Nil
    private def updateSuccs() {
      resetFlag(DIRTYSUCCS)      
      succs =
        if (isEmpty) Nil
        else exceptionSuccessors ++ directSuccessors ++ indirectExceptionSuccessors
    }

    def successors : List[BasicBlock] = {    
      if (touched) updateSuccs()
      succs
    }

    def directSuccessors: List[BasicBlock] =
      if (isEmpty) Nil else lastInstruction match {
        case JUMP(whereto)              => List(whereto)
        case CJUMP(succ, fail, _, _)    => fail :: succ :: Nil
        case CZJUMP(succ, fail, _, _)   => fail :: succ :: Nil
        case SWITCH(_, labels)          => labels
        case RETURN(_)                  => Nil
        case THROW(_)                   => Nil
        case _ =>
          if (closed) {
            dump
            global.abort("The last instruction is not a control flow instruction: " + lastInstruction)
          }
          else Nil
      }
    
    def exceptionSuccessors: List[BasicBlock] =
      exceptionSuccessorsForBlock(this)

    /** Return a list of successors for 'b' that come from exception handlers
     *  covering b's (non-exceptional) successors. These exception handlers 
     *  might not cover 'b' itself. This situation corresponds to an 
     *  exception being thrown as the first thing of one of b's successors.
     */
    def indirectExceptionSuccessors: List[BasicBlock] =
      directSuccessors flatMap exceptionSuccessorsForBlock distinct

    /** Returns the predecessors of this block.     */
    def predecessors: List[BasicBlock] = {
      if (hasFlag(DIRTYPREDS)) {
        resetFlag(DIRTYPREDS)
        preds = code.blocks.iterator filter (_.successors contains this) toList
      }
      preds
    }

    override def equals(other: Any): Boolean = other match {
      case that: BasicBlock => (that.label == label) && (that.code == code)
      case _ => false
    }

    override def hashCode = label * 41 + code.hashCode
    
    // Instead of it, rather use a printer
    def print() { print(java.lang.System.out) }

    def print(out: java.io.PrintStream) {
      out.println("block #"+label+" :")
      foreach(i => out.println("  " + i))
      out.print("Successors: ")
      successors.foreach((x: BasicBlock) => out.print(" "+x.label.toString()))
      out.println()
    }

    private def succString = if (successors.isEmpty) "[S: N/A]" else successors.distinct.mkString("[S: ", ", ", "]")
    private def predString = if (predecessors.isEmpty) "[P: N/A]" else predecessors.distinct.mkString("[P: ", ", ", "]")

    override def toString(): String = "" + label

    def blockContents = {
      def posStr(p: Position) = if (p.isDefined) p.line.toString else "<??>"
      val xs = this.toList map (instr => posStr(instr.pos) + "\t" + instr)
      xs.mkString(fullString + " {\n  ", "\n  ", "\n}")
    }
    def predContents = predecessors.map(_.blockContents).mkString(predecessors.size + " preds:\n", "\n", "\n")
    def succContents = successors.map(_.blockContents).mkString(successors.size + " succs:\n", "\n", "\n")

    def fullString: String = List("Block", label, succString, predString, flagsString) mkString " "    
    def flagsString: String = BBFlags.flagsToString(flags)
  }
}

object BBFlags {
  val flagMap = Map[Int, String](
    LOOP_HEADER -> "loopheader",
    IGNORING -> "ignore",
    EX_HEADER -> "exheader",
    CLOSED -> "closed",
    DIRTYSUCCS -> "dirtysuccs",
    DIRTYPREDS -> "dirtypreds"
  )
  def flagsToString(flags: Int) = {
    flagMap collect { case (bit, name) if (bit & flags) != 0 => "<" + name + ">" } mkString " "
  }

  /** This block is a loop header (was translated from a while). */
  final val LOOP_HEADER = (1 << 0)
  
  /** Ignoring mode: emit instructions are dropped. */
  final val IGNORING    = (1 << 1)
  
  /** This block is the header of an exception handler. */
  final val EX_HEADER   = (1 << 2)
  
  /** This block is closed. No new instructions can be added. */
  final val CLOSED      = (1 << 3)

  /** Code has been changed, recompute successors. */
  final val DIRTYSUCCS  = (1 << 4)

  /** Code has been changed, recompute predecessors. */
  final val DIRTYPREDS  = (1 << 5)
}

Other Scala examples (source code examples)

Here is a short list of links related to this Scala BasicBlocks.scala source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.