Compute liveness of instructions to get better and fewer variable names.

lib/compiler/implementation/ssa/variable_allocator.dart

+/**

[floitsch, 2012/05/30 18:45:03]

copyright.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+ * The [LiveRange] class covers a range where an instruction is live.
+ */
+class LiveRange {
+  final int start;
+  // [end] is not final because it can be udpated due to loops.

[kasperl, 2012/05/31 05:26:03]

udpated -> updated

[ngeoffray, 2012/05/31 08:12:46]

Done.

+  int end;
+  LiveRange(this.start, this.end) {
+    assert(start <= end);
+  }
+
+  String toString() {

[kasperl, 2012/05/31 05:26:03]

=>

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    return '[$start $end[';
+  }
+}
+
+/**
+ * The [LiveInterval] class contains the list of ranges where an
+ * instruction is live.
+ */
+class LiveInterval {
+  /**
+   * The id where there instruction is defined.
+   */
+  int start;
+  final List<LiveRange> ranges;
+  LiveInterval() : ranges = <LiveRange>[];
+
+  /**
+   * Update all ranges that are contained in [start, end[ to have

[floitsch, 2012/05/30 18:45:03]

This will probably confuse the doc-generator, and I think US uses a different
way of denoting inclusive/exclusive.
Personally I'm fine with this notation, though ;)

[kasperl, 2012/05/31 05:26:03]

to have die? to have died? to die?

[ngeoffray, 2012/05/31 08:12:46]

to die.

[ngeoffray, 2012/05/31 08:12:46]

Let's see how it complains :)

+   * die at [end].

[floitsch, 2012/05/30 18:45:03]

"have die"?
either have "end", or just "to die"

[ngeoffray, 2012/05/31 08:12:46]

Done.

+   */
+  void loopUpdate(int start, int end) {
+    for (LiveRange range in ranges) {
+      if (range.start >= start && range.end < end) {

[floitsch, 2012/05/30 18:45:03]

minor, but personally I prefer start <= range.start && range.end < end.
For me it makes it more obvious that range.start..end is enclosed.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+        range.end = end;
+      }
+    }
+  }
+
+  /**
+   * Add a new range to this interval.
+   */
+  void add(LiveRange interval) {
+    ranges.add(interval);
+  }
+
+  /**
+   * Returns true if one of the ranges of this interval dies at [at].
+   */
+  bool diesAt(int at) {
+    for (LiveRange range in ranges) {

[floitsch, 2012/05/30 18:45:03]

Haven't yet looked at the use-sites, but this looks like an O(n^2) thingy...

[ngeoffray, 2012/05/31 08:12:46]

An instruction doesn't have that many live ranges. It is not one live range per
block. For example if it survives an if/else, it has one live range.

+      if (range.end == at) return true;
+    }
+    return false;
+  }
+
+  String toString() {
+    List<String> res = new List<String>();
+    for (final interval in ranges) res.add(interval.toString());
+    return '(${Strings.join(res, ', ')})';
+  }
+}
+
+/**
+ * The [LiveEnvironment] class contains the live-ins of a basic block.

[floitsch, 2012/05/30 18:45:03]

please rename all "live-in"s with "live-interval"s in the comments.

[ngeoffray, 2012/05/31 08:12:46]

It's not containing the live-intervals, it's containing the liveIns set. Changed
the comment.

+ */
+class LiveEnvironment {
+  /**

[kasperl, 2012/05/31 05:26:03]

It would be nice with some better explanations of what these ids are used for.
It looks like it's a completely artificial id based on the counter in the
interval builder, but it would be nice to know what it's used for here -- and
what the significance of the integer value is.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+   * The id where the basic block starts.
+   */
+  int startId;
+
+  /**
+   * The id where the basic block ends.
+   */
+  final int endId;
+
+  /**
+   * List of loop markers that will be updated once the loop header is

[kasperl, 2012/05/31 05:26:03]

Maybe explain what it marks (what's the int value used for)? Marker is a very
generic term.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+   * visited. All live-ins of the loop header will be merged into this
+   * environment.
+   */
+  final Map<HBasicBlock, int> loopMarkers;
+
+  /**
+   * The instructions that are live in this basic block. The values of
+   * the map contains the ids where the instructions die.

[floitsch, 2012/05/30 18:45:03]

contain

[ngeoffray, 2012/05/31 08:12:46]

Done.

+   */
+  final Map<HInstruction, int> lives;

[floitsch, 2012/05/30 18:45:03]

could we rename this to "lastUsedAt" ?

[kasperl, 2012/05/31 05:26:03]

lives -> liveUntil? How does this relate to the last end position of the ranges
in the liveIntervals?

[ngeoffray, 2012/05/31 08:12:46]

It's really a map of live instructions with the information of where they are
last used. I'd prefer using liveInstructions instead.

[ngeoffray, 2012/05/31 08:12:46]

It will be used when adding a range to the live interval of an instruction.
Added a comment.

+
+  /**
+   * Map containing the live intervals of instructions.
+   */
+  final Map<HInstruction, LiveInterval> liveIntervals;
+
+  LiveEnvironment(this.liveIntervals, this.endId)
+    : lives = new Map<HInstruction, int>(),
+      loopMarkers = new Map<HBasicBlock, int>();
+
+  /**
+   * Remove an instruction from the liveIn set. This method also
+   * updates the live interval of [instruction] to contain the new
+   * range: [id, / id contained in [lives] /].
+   */
+  void remove(HInstruction instruction, int id) {
+    // Special case the HCheck instruction to have the same live
+    // interval as the instruction it is checking.
+    if (instruction is HCheck) {
+      HInstruction input = instruction.checkedInput;
+      while (input is HCheck) input = input.checkedInput;
+      liveIntervals.putIfAbsent(input, () => new LiveInterval());
+      liveIntervals.putIfAbsent(instruction, () => liveIntervals[input]);
+      return;
+    }
+    LiveInterval range = liveIntervals.putIfAbsent(
+        instruction, () => new LiveInterval());
+    int lastId = lives[instruction];
+    // If [lastId] is null, then this instruction is bot being used.

[floitsch, 2012/05/30 18:45:03]

not

[kasperl, 2012/05/31 05:26:03]

is bot -> is not

[ngeoffray, 2012/05/31 08:12:46]

Done.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    range.add(new LiveRange(id, lastId == null ? id : lastId));
+    // The instruction is defined at [id].
+    range.start = id;
+    lives.remove(instruction);
+  }
+
+  /**
+   * Add [instruction] to the liveIn set. If the instruction is not
+   * already in the set, we save the id where it dies.
+   */
+  void add(HInstruction instruction, int userId) {
+    // Special case the HCheck instruction to use the actual checked
+    // instruction.
+    while (instruction is HCheck) instruction = instruction.checkedInput;
+    lives.putIfAbsent(instruction, () => userId);

[floitsch, 2012/05/30 18:45:03]

Add comment that reminds that we are visiting the graph in post-order, and that
we see a variable first when it dies.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+  }
+
+  /**
+   * Merge this environment with [other]. Update the end id of
+   * instructions in case they are different between this and [other].
+   */
+  void mergeWith(LiveEnvironment other) {
+    other.lives.forEach((HInstruction instruction, int existingId) {
+      if (existingId == endId) return;

[floitsch, 2012/05/30 18:45:03]

Add comment when this can happen.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+      LiveInterval range = liveIntervals.putIfAbsent(
+          instruction, () => new LiveInterval());
+      range.add(new LiveRange(other.startId, existingId));
+      lives[instruction] = endId;
+    });
+    other.loopMarkers.forEach((k, v) { loopMarkers[k] = v; });
+  }
+
+  void addLoopMarker(HBasicBlock header, int id) {
+    assert(!loopMarkers.containsKey(header));
+    loopMarkers[header] = id;
+  }
+
+  void removeLoopMarker(HBasicBlock header) {
+    assert(loopMarkers.containsKey(header));
+    loopMarkers.remove(header);
+  }
+
+  bool isEmpty() => lives.isEmpty() && loopMarkers.isEmpty();
+  bool contains(HInstruction instruction) => lives.containsKey(instruction);
+  String toString() => lives.toString();
+}
+
+/**
+ * Builds the live intervals of each instruction. The algorithm visits
+ * the graph post-dominator tree to find the last uses of an
+ * instruction, and computes the liveIns of each basic block.
+ */
+class SsaLiveIntervalBuilder extends HBaseVisitor {
+  final Compiler compiler;
+
+  /**
+   * A counter to assign start and end ids to live ranges. The initial
+   * value is not relevant.
+   */
+  int counter = 0;
+
+  /**
+   * The liveIns of basic blocks.
+   */
+  final Map<HBasicBlock, LiveEnvironment> liveInstructions;
+
+  /**
+   * The live intervals of instructions.
+   */
+  final Map<HInstruction, LiveInterval> liveIntervals;
+
+  SsaLiveIntervalBuilder(this.compiler)
+    : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(),
+      liveIntervals = new Map<HInstruction, LiveInterval>();
+
+  void visitGraph(HGraph graph) {
+    visitPostDominatorTree(graph);
+    if (!liveInstructions[graph.entry].isEmpty()) {
+      compiler.internalError('LiveIntervalBuilder',
+          node: compiler.currentElement.parseNode(compiler));
+    }
+  }
+
+  void visitBasicBlock(HBasicBlock block) {
+    LiveEnvironment environment = new LiveEnvironment(liveIntervals, counter);
+
+    // Add to the environment the live instructions of its successor, as well as
+    // the inputs of the phis of the successor that flow from this block.
+    for (int i = 0; i < block.successors.length; i++) {
+      HBasicBlock successor = block.successors[i];
+      LiveEnvironment successorEnv = liveInstructions[successor];
+      if (successorEnv !== null) {
+        environment.mergeWith(successorEnv);
+      } else {
+        environment.addLoopMarker(successor, counter);
+      }
+
+      int index = successor.predecessors.indexOf(block);
+      for (HPhi phi = successor.phis.first; phi != null; phi = phi.next) {
+        environment.add(phi.inputs[index], counter);
+      }
+    }
+
+    // Iterate over all instructions to remove an instruction from the
+    // environment and add its inputs.
+    HInstruction instruction = block.last;
+    while (instruction != null) {
+      environment.remove(instruction, counter);
+      for (int i = 0, len = instruction.inputs.length; i < len; i++) {
+        environment.add(instruction.inputs[i], counter);
+      }
+      instruction = instruction.previous;
+      counter--;

[kasperl, 2012/05/31 05:26:03]

This is the only place you change counter? Hmm. This looks fishy. If it is
intentional to let counter go negative it deserves a comment.

[ngeoffray, 2012/05/31 08:12:46]

Changed the name to instructionId, and added a comment at the declaration of the
field.

+    }
+
+    // We just remove the phis from the environment. The inputs of the
+    // phis will be put in the environment of the predecessors.
+    for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
+      environment.remove(phi, counter);
+    }
+
+    // Save the liveInstructions of that block.
+    environment.startId = counter + 1;
+    liveInstructions[block] = environment;
+
+    // If the block is a loop header, we can remove the loop marker,
+    // because it will just recompute the loop phis.
+    if (block.isLoopHeader()) {
+      updateLoopMarker(block);
+    }
+  }
+
+  void updateLoopMarker(HBasicBlock header) {
+    LiveEnvironment env = liveInstructions[header];
+    int lastId = env.loopMarkers[header];
+    // Update all instructions that are liveIns in [header] to have a
+    // range that covers the loop.
+    env.lives.forEach((HInstruction instruction, int id) {
+      LiveInterval range = env.liveIntervals.putIfAbsent(
+          instruction, () => new LiveInterval());
+      range.loopUpdate(env.startId, lastId);
+      env.lives[instruction] = lastId;
+    });
+
+    env.removeLoopMarker(header);
+   
+    // Update all liveIns set to contain the liveIns of [header]. 
+    liveInstructions.forEach((HBasicBlock block, LiveEnvironment other) {
+      if (other.loopMarkers.containsKey(header)) {
+        env.lives.forEach((HInstruction instruction, int id) {
+          other.lives[instruction] = id;
+        });
+        other.removeLoopMarker(header);
+        env.loopMarkers.forEach((k, v) { other.loopMarkers[k] = v; });
+      }
+    });
+  }
+}
+
+/**
+ * Represents a copy from one instruction to another. The codegen
+ * also uses this class to represent a copy from one variable to
+ * another.
+ */
+class Copy {

[Lasse Reichstein Nielsen, 2012/05/31 08:24:56]

Rename to "Copying" (or "Assignment" if that isn't taken).
This represents an act of copying, not the resulting copy.

[ngeoffray, 2012/05/31 08:48:22]

As discussed, kept the name :)

+  var source;

[floitsch, 2012/05/30 18:45:03]

final HInstruction ?

[kasperl, 2012/05/31 05:26:03]

Types on source and destination? I'm pretty sure they are instructions.

[ngeoffray, 2012/05/31 08:12:46]

They are here, but will be String in codegen :) This class is really a std::pair
equivalent.

[ngeoffray, 2012/05/31 08:12:46]

Made it final, but not typed, as they can also be String (see
sequentializeParallelCopies in codegen).

+  var destination;
+  Copy(this.source, this.destination);
+  String toString() => '$destination <- $source';
+}
+
+/**
+ * A copy handler contains the copies that a basic block needs to do
+ * after executing all its instructions.
+ */
+class CopyHandler {
+  /**
+   * The copies from an instruction to a phi of the successor.
+   */
+  final List<Copy> copies;
+
+  /**
+   * Trivial assignments from a constant to the phi of a successor.

[Lasse Reichstein Nielsen, 2012/05/31 08:24:56]

How is this different from a copying? I.e., what makes them trivial?

[ngeoffray, 2012/05/31 08:48:22]

Because the source does not need a name. Added a comment.

+   */
+  final List<Copy> assignments;
+
+  CopyHandler()
+    : copies = new List<Copy>(),
+      assignments = new List<Copy>();
+
+  void addCopy(HInstruction source, HInstruction destination) {
+    copies.add(new Copy(source, destination));
+  }
+
+  void addAssignment(HInstruction source, HInstruction destination) {
+    assignments.add(new Copy(source, destination));
+  }
+
+  String toString() {

[kasperl, 2012/05/31 05:26:03]

=>

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    return 'Copies: $copies, assignments: $assignments';
+  }
+}
+
+/**
+ * Contains the mapping between instructions and their names for code
+ * generation, as well as the [CopyHandler] for each basic block.
+ */
+class VariableNames {
+  final Map<HInstruction, String> ownName;
+  final Map<HBasicBlock, CopyHandler> copies;

[kasperl, 2012/05/31 05:26:03]

This really don't hold copies -- it holds handlers. I would rename it to avoid
confusion.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+  static final String SWAP_TEMP = 't0';

[Lasse Reichstein Nielsen, 2012/05/31 08:24:56]

How do we know this doesn't collide with anything?
(If we do, write it here).

[ngeoffray, 2012/05/31 08:48:22]

Done. And added a TODO to deal with parameters.

+
+  VariableNames()
+    : ownName = new Map<HInstruction, String>(),
+      copies = new Map<HBasicBlock, CopyHandler>();
+
+  String getName(HInstruction instruction) {
+    return ownName[instruction];
+  }
+
+  CopyHandler getCopies(HBasicBlock block) {

[kasperl, 2012/05/31 05:26:03]

I would probably call this getCopyHandler.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    return copies[block];
+  }
+
+  bool hasName(HInstruction instruction) => ownName.containsKey(instruction);
+
+  void addCopy(HBasicBlock block, HInstruction source, HPhi destination) {
+    CopyHandler handler =
+        copies.putIfAbsent(block, () => new CopyHandler());
+    handler.addCopy(source, destination);
+  }
+
+  void addAssignment(HBasicBlock block, HInstruction source, HPhi destination) {
+    CopyHandler handler =
+        copies.putIfAbsent(block, () => new CopyHandler());
+    handler.addAssignment(source, destination);
+  }
+}
+
+/**
+ * Allocates variable names for instructions, making sure they don't
+ * collide.

[floitsch, 2012/05/30 18:45:03]

Not that it matters, but this should fit on one line.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+ */
+class VariableNamer {
+  final VariableNames names;
+  final Set<String> usedNames;
+
+  VariableNamer(LiveEnvironment environment, this.names)
+    : usedNames = new Set<String>() {
+    // [VariableNames.SWAP_TEMP] is being used when there is a cycle
+    // in a copy handler. Therefore we make sure no one will use it.
+    usedNames.add(VariableNames.SWAP_TEMP);
+
+    // All liveIns instructions must have a name at this point, so we
+    // add them to the list of used names.
+    environment.lives.forEach((HInstruction instruction, int index) {
+      String name = names.getName(instruction);
+      if (name !== null) {
+        usedNames.add(name);
+      }
+    });
+  }
+
+  String allocateWithHint(String originalName) {
+    int i = 0;
+    String name = JsNames.getValid(originalName);
+    while (usedNames.contains(name)) {
+      name = JsNames.getValid('$originalName${i++}');
+    }
+    return name;
+  }
+
+  String allocateTemporary() {
+    int i = 1;

[kasperl, 2012/05/31 05:26:03]

Add comment about not using t0 because it's SWAP_TEMP.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    String name = 't${i++}';
+    while (usedNames.contains(name)) name = 't${i++}';
+    return name;
+  }
+
+  HPhi firstPhiUserWithElement(HInstruction instruction) {
+    for (HInstruction user in instruction.usedBy) {
+      if (user is HPhi && user.sourceElement !== null) {
+        return user;
+      }
+    }
+    return null;
+  }
+
+  String allocateName(HInstruction instruction) {
+    String name;
+    if (instruction is HCheck) {
+      // Special case the check instruction to use the name of its
+      // checked instruction.
+      HCheck check = instruction;
+      name = names.ownName[check.checkedInput];
+      // If the name is null, then the checked input is being
+      // generated at use site, and we don't need a name for the check
+      // instruction.
+      if (name == null) return;
+    } else if (instruction is HParameterValue) {
+      HParameterValue parameter = instruction;
+      name = allocateWithHint(parameter.element.name.slowToString());
+    } else if (instruction.sourceElement !== null) {
+      name = allocateWithHint(instruction.sourceElement.name.slowToString());
+    } else {
+      // We could not find an element for the instruction. If the
+      // instruction is used by a phi, try to use the name of the phi.
+      // Otherwise, just allocate a temporary name.
+      HPhi phi = firstPhiUserWithElement(instruction);
+      if (phi !== null) {
+        name = allocateWithHint(phi.sourceElement.name.slowToString());
+      } else {
+        name = allocateTemporary();
+      }
+    }
+    usedNames.add(name);
+    names.ownName[instruction] = name;
+    return name;
+  }
+
+  void freeName(HInstruction instruction) {

[floitsch, 2012/05/30 18:45:03]

Add comment: "Frees the [instruction]'s name so it can be used for other
instructions".

(Just to make sure nobody reads the method as "getNextFreeName")

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    String ownName = names.ownName[instruction];
+    if (ownName != null) {
+      usedNames.remove(ownName);
+    }
+  }
+}
+
+/**
+ * Visits all blocks in the graph, sets names to instructions, and
+ * creates the [CopyHandler] for each block. This class needs to have
+ * the liveIns set as well as all the live intervals of instructions.
+ * It visits the graph in dominator order, so that at each entry of a
+ * block, the instructions in its liveIns set have names.
+ *
+ * When visiting a block, it goes through all instructions. For each
+ * instruction, it frees the names of the inputs that die at that
+ * instruction, and allocates a name to the instruction. For each phi,
+ * it adds a copy to the CopyHandler of the corresponding predecessor.
+ */
+class SsaVariableAllocator extends HBaseVisitor {
+
+  final Compiler compiler;
+  final Map<HBasicBlock, LiveEnvironment> liveInstructions;
+  final Map<HInstruction, LiveInterval> liveIntervals;
+  final Set<HInstruction> generateAtUseSite;
+
+  final VariableNames names;
+
+  SsaVariableAllocator(this.compiler,
+                       this.liveInstructions,
+                       this.liveIntervals,
+                       this.generateAtUseSite)
+    : names = new VariableNames();
+
+  void visitGraph(HGraph graph) {
+    visitDominatorTree(graph);
+  }
+
+  void visitBasicBlock(HBasicBlock block) {
+    VariableNamer namer = new VariableNamer(liveInstructions[block], names);
+
+    block.forEachPhi((HPhi phi) {
+      handlePhi(phi, namer);
+    });
+
+    block.forEachInstruction((HInstruction instruction) {
+      handleInstruction(instruction, namer);
+    });
+  }
+
+  /**
+   * Returns whether [instruction] needs a name. Instructions that
+   * have no users or that are generated at use site does not need a name.

[kasperl, 2012/05/31 05:26:03]

use site does -> use site do. Maybe change method name to needsName to make it
fit better with allocateName and freeName?

[ngeoffray, 2012/05/31 08:12:46]

Done.

+   */
+  bool needsVariable(HInstruction instruction) {
+    if (instruction.usedBy.isEmpty()) return false;
+    // TODO(ngeoffray): We need a name for parameters, but we could

[kasperl, 2012/05/31 05:26:03]

The TODO comment isn't easy to understand. The "we need a name for parameters"
part I get, but is the TODO about allocating such names before getting to this
point (and then return false from needsVariable in the future)?

[ngeoffray, 2012/05/31 08:12:46]

The problem is that we're making parameters generate at use site, and I would
like to avoid that to not special case parameters. I improved the TODO comment.

+    // allocate it before.
+    if (instruction is HParameterValue && instruction is !HThis) return true;
+    if (generateAtUseSite.contains(instruction)) return false;
+    return true;
+  }
+

[kasperl, 2012/05/31 05:26:03]

Too many newlines.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+  
+  /**
+   * Retrurns whether [instruction] dies at the instruction [at].

[floitsch, 2012/05/30 18:45:03]

Returns

[kasperl, 2012/05/31 05:26:03]

Retrurns -> Returns

[ngeoffray, 2012/05/31 08:12:46]

Done.

[ngeoffray, 2012/05/31 08:12:46]

Done.

+   */
+  bool diesAt(HInstruction instruction, HInstruction at) {
+    LiveInterval atRange = liveIntervals[at];

[kasperl, 2012/05/31 05:26:03]

You call them ranges in a few places, but the type calls the concept intervals.
Maybe call them atInterval and instructionInterval?

[ngeoffray, 2012/05/31 08:12:46]

Done.

+    LiveInterval instructionRange = liveIntervals[instruction];
+    int start = atRange.start;
+    return instructionRange.diesAt(start);
+  }
+
+  void handleInstruction(HInstruction instruction, VariableNamer namer) {
+    for (int i = 0, len = instruction.inputs.length; i < len; i++) {
+      HInstruction input = instruction.inputs[i];
+      if (needsVariable(input) && diesAt(input, instruction)) {

[kasperl, 2012/05/31 05:26:03]

Add a comment here. If we're the last use of something that has needs a
variable, we free it?

[ngeoffray, 2012/05/31 08:12:46]

Done.

+        namer.freeName(input);
+      }
+    }
+
+    if (needsVariable(instruction)) {
+      namer.allocateName(instruction);
+    }
+  }
+
+  void handlePhi(HPhi phi, VariableNamer namer) {
+    if (!needsVariable(phi)) return;
+
+    for (int i = 0; i < phi.inputs.length; i++) {
+      HInstruction input = phi.inputs[i];
+      HBasicBlock predecessor = phi.block.predecessors[i];
+      if (!needsVariable(input)) {
+        names.addAssignment(predecessor, input, phi);

[Lasse Reichstein Nielsen, 2012/05/31 08:24:56]

If it doesn't need a variable, what are we assigning to?

[ngeoffray, 2012/05/31 08:48:22]

The instruction (eg a constant, or a generate at use site instruction).

+      } else {
+        names.addCopy(predecessor, input, phi);
+      }
+    }
+
+    namer.allocateName(phi);
+  }
+}