001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.ssa;
014
015import static org.jikesrvm.compilers.opt.driver.OptConstants.SSA_SYNTH_BCI;
016import static org.jikesrvm.compilers.opt.ir.Operators.FENCE;
017import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
018import static org.jikesrvm.compilers.opt.ir.Operators.READ_CEILING;
019import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN_opcode;
020import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END_opcode;
021import static org.jikesrvm.compilers.opt.ir.Operators.WRITE_FLOOR;
022
023import java.lang.reflect.Constructor;
024import java.util.Enumeration;
025import java.util.HashMap;
026import java.util.HashSet;
027import java.util.Iterator;
028import java.util.Map;
029import java.util.Set;
030import java.util.Stack;
031
032import org.jikesrvm.VM;
033import org.jikesrvm.classloader.TypeReference;
034import org.jikesrvm.compilers.opt.ClassLoaderProxy;
035import org.jikesrvm.compilers.opt.DefUse;
036import org.jikesrvm.compilers.opt.OptOptions;
037import org.jikesrvm.compilers.opt.OptimizingCompilerException;
038import org.jikesrvm.compilers.opt.controlflow.DominanceFrontier;
039import org.jikesrvm.compilers.opt.controlflow.DominatorTreeNode;
040import org.jikesrvm.compilers.opt.driver.CompilerPhase;
041import org.jikesrvm.compilers.opt.ir.Athrow;
042import org.jikesrvm.compilers.opt.ir.Attempt;
043import org.jikesrvm.compilers.opt.ir.BBend;
044import org.jikesrvm.compilers.opt.ir.BasicBlock;
045import org.jikesrvm.compilers.opt.ir.CacheOp;
046import org.jikesrvm.compilers.opt.ir.Call;
047import org.jikesrvm.compilers.opt.ir.IR;
048import org.jikesrvm.compilers.opt.ir.Instruction;
049import org.jikesrvm.compilers.opt.ir.Label;
050import org.jikesrvm.compilers.opt.ir.MonitorOp;
051import org.jikesrvm.compilers.opt.ir.Phi;
052import org.jikesrvm.compilers.opt.ir.Prepare;
053import org.jikesrvm.compilers.opt.ir.Register;
054import org.jikesrvm.compilers.opt.ir.ResultCarrier;
055import org.jikesrvm.compilers.opt.ir.Return;
056import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
057import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
058import org.jikesrvm.compilers.opt.ir.operand.Operand;
059import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
060import org.jikesrvm.compilers.opt.ir.operand.UnreachableOperand;
061import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
062import org.jikesrvm.compilers.opt.liveness.LiveSet;
063import org.jikesrvm.compilers.opt.util.TreeNode;
064import org.jikesrvm.util.BitVector;
065import org.jikesrvm.util.Pair;
066
067/**
068 * This compiler phase constructs SSA form.
069 *
070 * <p> This module constructs SSA according to the SSA properties defined
071 * in <code> IR.desiredSSAOptions </code>.  See <code> SSAOptions
072 * </code> for more details on supported options for SSA construction.
073 *
074 * <p>The SSA construction algorithm is the classic dominance frontier
075 * based algorithm from Cytron et al.'s 1991 TOPLAS paper.
076 *
077 * <p> See our SAS 2000 paper
078 * <a href="http://www.research.ibm.com/jalapeno/publication.html#sas00">
079 *  Unified Analysis of Arrays and Object References in Strongly Typed
080 *  Languages </a> for an overview of Array SSA form.  More implementation
081 *  details are documented in {@link SSA}.
082 *
083 * @see SSA
084 * @see SSAOptions
085 * @see org.jikesrvm.compilers.opt.controlflow.LTDominators
086 */
087public class EnterSSA extends CompilerPhase {
088  /**
089   * flag to optionally print verbose debugging messages
090   */
091  static final boolean DEBUG = false;
092
093  /**
094   * The governing IR
095   */
096  private IR ir;
097
098  /**
099   * Cached results of liveness analysis
100   */
101  private LiveAnalysis live;
102
103  /**
104   * A set of registers determined to span basic blocks
105   */
106  private HashSet<Register> nonLocalRegisters;
107
108  /**
109   * The set of scalar phi functions inserted
110   */
111  private final HashSet<Instruction> scalarPhis = new HashSet<Instruction>();
112
113  /**
114   * For each basic block, the number of predecessors that have been
115   * processed.
116   */
117  private int[] numPredProcessed;
118
119  /**
120   * Should this phase be performed under a guiding set of compiler
121   * options?
122   *
123   * @param options the controlling compiler options
124   * @return true iff SSA is enabled under the options
125   */
126  @Override
127  public final boolean shouldPerform(OptOptions options) {
128    return options.SSA;
129  }
130
131  /**
132   * Constructor for this compiler phase
133   */
134  private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(EnterSSA.class);
135
136  /**
137   * Get a constructor object for this compiler phase
138   * @return compiler phase constructor
139   */
140  @Override
141  public Constructor<CompilerPhase> getClassConstructor() {
142    return constructor;
143  }
144
145  /**
146   * Return a string identifying this compiler phase.
147   * @return "Enter SSA"
148   */
149  @Override
150  public final String getName() {
151    return "Enter SSA";
152  }
153
154  /**
155   * Should the IR be printed either before or after performing this phase?
156   *
157   * @param options controlling compiler options
158   * @param before true iff querying before the phase
159   * @return true or false
160   */
161  @Override
162  public final boolean printingEnabled(OptOptions options, boolean before) {
163    return false;
164  }
165
166  /**
167   * Construct SSA form to satisfy the desired options in ir.desiredSSAOptions.
168   * This module is lazy; if the actual SSA options satisfy the desired options,
169   * then do nothing.
170   */
171  @Override
172  public final void perform(IR ir) {
173
174    // Exit if we don't have to recompute SSA.
175    if (ir.desiredSSAOptions.getAbort()) return;
176    if (ir.actualSSAOptions != null) {
177      if (ir.actualSSAOptions.satisfies(ir.desiredSSAOptions)) {
178        return;
179      }
180    }
181    this.ir = ir;
182    boolean scalarsOnly = ir.desiredSSAOptions.getScalarsOnly();
183    boolean backwards = ir.desiredSSAOptions.getBackwards();
184    Set<Object> heapTypes = ir.desiredSSAOptions.getHeapTypes();
185    boolean insertUsePhis = ir.desiredSSAOptions.getInsertUsePhis();
186    boolean insertPEIDeps = ir.desiredSSAOptions.getInsertPEIDeps();
187    boolean excludeGuards = ir.desiredSSAOptions.getExcludeGuards();
188
189    // make sure the dominator computation completed successfully
190    if (!ir.HIRInfo.dominatorsAreComputed) {
191      throw new OptimizingCompilerException("Need dominators for SSA");
192    }
193    // reset SSA dictionary information
194    ir.HIRInfo.dictionary = new SSADictionary(null, true, false, ir);
195    // initialize as needed for SSA options
196    prepare();
197    // work around problem with PEI-generated values and handlers
198    if (true /* ir.options.UNFACTOR_FOR_SSA */) {
199      patchPEIgeneratedValues();
200    }
201    if (ir.options.PRINT_SSA) {
202      SSA.printInstructions(ir);
203    }
204    computeSSA(ir, scalarsOnly, backwards, heapTypes, insertUsePhis, insertPEIDeps, excludeGuards);
205    // reset the SSAOptions
206    ir.actualSSAOptions = new SSAOptions();
207    ir.actualSSAOptions.setScalarsOnly(scalarsOnly);
208    ir.actualSSAOptions.setBackwards(backwards);
209    ir.actualSSAOptions.setHeapTypes(heapTypes);
210    ir.actualSSAOptions.setInsertUsePhis(insertUsePhis);
211    ir.actualSSAOptions.setInsertPEIDeps(insertPEIDeps);
212    ir.actualSSAOptions.setExcludeGuards(excludeGuards);
213    ir.actualSSAOptions.setScalarValid(true);
214    ir.actualSSAOptions.setHeapValid(!scalarsOnly);
215  }
216
217  /**
218   * Perform some calculations to prepare for SSA construction.
219   * <ul>
220   * <li> If using pruned SSA, compute liveness.
221   * <li> If using semi-pruned SSA, compute non-local registers
222   * </ul>
223   */
224  private void prepare() {
225    live = new LiveAnalysis(false, // don't create GC maps
226                                true,  // skip (final) local propagation step
227                                // of live analysis
228                                false, // don't store live at handlers
229                                ir.desiredSSAOptions.getExcludeGuards());
230    // don't skip guards
231    live.perform(ir);
232  }
233
234  /**
235   * Pass through the IR and calculate which registers are not
236   * local to a basic block.  Store the result in the <code> nonLocalRegisters
237   * </code> field.
238   */
239  @SuppressWarnings("unused")
240  private void computeNonLocals() {
241    nonLocalRegisters = new HashSet<Register>(20);
242    Enumeration<BasicBlock> blocks = ir.getBasicBlocks();
243    while (blocks.hasMoreElements()) {
244      HashSet<Register> killed = new HashSet<Register>(5);
245      BasicBlock block = blocks.nextElement();
246      Enumeration<Instruction> instrs = block.forwardRealInstrEnumerator();
247      while (instrs.hasMoreElements()) {
248        Instruction instr = instrs.nextElement();
249        Enumeration<Operand> uses = instr.getUses();
250        while (uses.hasMoreElements()) {
251          Operand op = uses.nextElement();
252          if (op instanceof RegisterOperand) {
253            if (!killed.contains(op.asRegister().getRegister())) {
254              nonLocalRegisters.add(op.asRegister().getRegister());
255            }
256          }
257        }
258        Enumeration<Operand> defs = instr.getDefs();
259        while (defs.hasMoreElements()) {
260          Operand op = defs.nextElement();
261          if (op instanceof RegisterOperand) {
262            killed.add(op.asRegister().getRegister());
263          }
264        }
265      }
266    }
267  }
268
269  /**
270   * Work around some problems with PEI-generated values and
271   * handlers.  Namely, if a PEI has a return value, rename the
272   * result register before and after the PEI in order to reflect the fact
273   * that the PEI may not actually assign the result register.
274   */
275  private void patchPEIgeneratedValues() {
276    // this only applies if there are exception handlers
277    if (!ir.hasReachableExceptionHandlers()) return;
278
279    HashSet<Pair<BasicBlock, RegisterOperand>> needed = new HashSet<Pair<BasicBlock,RegisterOperand>>(4);
280    Enumeration<BasicBlock> blocks = ir.getBasicBlocks();
281    while (blocks.hasMoreElements()) {
282      BasicBlock block = blocks.nextElement();
283      if (block.getExceptionalOut().hasMoreElements()) {
284        Instruction pei = block.lastRealInstruction();
285        if (pei != null && pei.isPEI() && ResultCarrier.conforms(pei)) {
286          boolean copyNeeded = false;
287          RegisterOperand v = ResultCarrier.getResult(pei);
288          // void calls and the like... :(
289          if (v != null) {
290            Register orig = v.getRegister();
291            {
292              Enumeration<BasicBlock> out = block.getApplicableExceptionalOut(pei);
293              while (out.hasMoreElements()) {
294                BasicBlock exp = out.nextElement();
295                LiveSet explive = live.getLiveInfo(exp).getIn();
296                if (explive.contains(orig)) {
297                  copyNeeded = true;
298                  break;
299                }
300              }
301            }
302            if (copyNeeded) {
303              Enumeration<BasicBlock> out = block.getApplicableExceptionalOut(pei);
304              while (out.hasMoreElements()) {
305                BasicBlock exp = out.nextElement();
306                needed.add(new Pair<BasicBlock, RegisterOperand>(exp, v));
307              }
308            }
309          }
310        }
311      }
312    }
313    // having determine where copies should be inserted, now insert them.
314    if (!needed.isEmpty()) {
315      for (Pair<BasicBlock, RegisterOperand> copy : needed) {
316        BasicBlock inBlock = copy.first;
317        RegisterOperand registerOp = copy.second;
318        TypeReference type = registerOp.getType();
319        Register register = registerOp.getRegister();
320        Register temp = ir.regpool.getReg(register);
321        inBlock.prependInstruction(SSA.makeMoveInstruction(ir, register, temp, type));
322        Enumeration<BasicBlock> outBlocks = inBlock.getIn();
323        while (outBlocks.hasMoreElements()) {
324          BasicBlock outBlock = outBlocks.nextElement();
325          Instruction x = SSA.makeMoveInstruction(ir, temp, register, type);
326          SSA.addAtEnd(ir, outBlock, x, true);
327        }
328      }
329      // Recompute liveness information.  You might be tempted to incrementally
330      // update it, but it's tricky, so resist.....do the obvious, but easy thing!
331      prepare();
332    }
333  }
334
335  /**
336   * Calculate SSA form for an IR.  This routine holds the guts of the
337   * transformation.
338   *
339   * @param ir the governing IR
340   * @param scalarsOnly should we compute SSA only for scalar variables?
341   * @param backwards If this is true, then every statement that
342   * can leave the procedure is considered to <em> use </em> every heap
343   * variable.  This option is useful for backwards analyses such as dead
344   * store elimination.
345   * @param heapTypes If this variable is non-null, then heap array SSA
346   * form will restrict itself to this set of types. If this is null, build
347   * heap array SSA for all types.
348   * @param insertUsePhis Should we insert uphi functions for heap array
349   * SSA? ie., should we create a new name for each heap array at every use
350   * of the heap array? This option is useful for some analyses, such as
351   * our redundant load elimination algorithm.
352   * @param insertPEIDeps Should we model exceptions with an explicit
353   * heap variable for exception state? This option is useful for global
354   * code placement algorithms.
355   * @param excludeGuards Should we exclude guard registers from SSA?
356   */
357  private void computeSSA(IR ir, boolean scalarsOnly, boolean backwards, Set<Object> heapTypes,
358                          boolean insertUsePhis, boolean insertPEIDeps, boolean excludeGuards) {
359    // if reads Kill.  model this with uphis.
360    if (ir.options.READS_KILL) insertUsePhis = true;
361
362    // reset Array SSA information
363    if (!scalarsOnly) {
364      ir.HIRInfo.dictionary = new SSADictionary(heapTypes, insertUsePhis, insertPEIDeps, ir);
365    } else {
366      ir.HIRInfo.dictionary = new SSADictionary(null, insertUsePhis, insertPEIDeps, ir);
367    }
368    if (DEBUG) System.out.println("Computing register lists...");
369
370    // 1. re-compute the flow-insensitive isSSA flag for each register
371    DefUse.computeDU(ir);
372    DefUse.recomputeSSA(ir);
373
374    // 2. set up a mapping from symbolic register number to the
375    //  register.  !!TODO: factor this out and make it more
376    //  useful.
377    Register[] symbolicRegisters = getSymbolicRegisters();
378
379    // 3. walk through the IR, and set up BitVectors representing the defs
380    //    for each symbolic register (more efficient than using register
381    //  lists)
382    if (DEBUG) System.out.println("Find defs for each register...");
383    BitVector[] defSets = getDefSets();
384
385    // 4. Insert phi functions for scalars
386    if (DEBUG) System.out.println("Insert phi functions...");
387    insertPhiFunctions(ir, defSets, symbolicRegisters, excludeGuards);
388
389    // 5. Insert heap variables into the Array SSA form
390    if (!scalarsOnly) {
391      insertHeapVariables(ir, backwards);
392    }
393    if (DEBUG) System.out.println("Before renaming...");
394    if (DEBUG) SSA.printInstructions(ir);
395    if (DEBUG) System.out.println("Renaming...");
396    renameSymbolicRegisters(symbolicRegisters);
397
398    if (!scalarsOnly) {
399      renameHeapVariables(ir);
400    }
401    if (DEBUG) System.out.println("SSA done.");
402    if (ir.options.PRINT_SSA) SSA.printInstructions(ir);
403  }
404
405  /**
406   * Insert heap variables needed for Array SSA form.
407   *
408   * @param ir the governing IR
409   * @param backwards if this is true, every statement that can leave the
410   *                   procedure <em> uses </em> every heap variable.
411   *                   This option is useful for backwards analyses
412   */
413  private void insertHeapVariables(IR ir, boolean backwards) {
414    // insert dphi functions where needed
415    registerHeapVariables(ir);
416
417    // insert heap defs and uses for CALL instructions
418    registerCalls(ir);
419
420    // register heap uses for instructions that can leave the procedure
421    if (backwards) {
422      registerExits(ir);
423    }
424
425    // insert phi funcions where needed
426    insertHeapPhiFunctions(ir);
427  }
428
429  /**
430   * Register every instruction that can leave this method with the
431   * implicit heap array SSA look aside structure.
432   *
433   * @param ir the governing IR
434   */
435  private void registerExits(IR ir) {
436    SSADictionary dictionary = ir.HIRInfo.dictionary;
437    for (Enumeration<BasicBlock> bbe = ir.getBasicBlocks(); bbe.hasMoreElements();) {
438      BasicBlock b = bbe.nextElement();
439      for (Enumeration<Instruction> e = b.forwardInstrEnumerator(); e.hasMoreElements();) {
440        Instruction s = e.nextElement();
441        // we already handled calls in a previous pass.
442        if (Call.conforms(s)) {
443          continue;
444        }
445        if (Return.conforms(s) || Athrow.conforms(s) || s.isPEI()) {
446          dictionary.registerExit(s, b);
447        }
448      }
449    }
450  }
451
452  /**
453   * Register every CALL instruction in this method with the
454   * implicit heap array SSA look aside structure.
455   * Namely, mark that this instruction defs and uses <em> every </em>
456   * type of heap variable in the IR's SSA dictionary.
457   *
458   * @param ir the governing IR
459   */
460  private void registerCalls(IR ir) {
461    SSADictionary dictionary = ir.HIRInfo.dictionary;
462    for (Enumeration<BasicBlock> bbe = ir.getBasicBlocks(); bbe.hasMoreElements();) {
463      BasicBlock b = bbe.nextElement();
464      for (Enumeration<Instruction> e = b.forwardInstrEnumerator(); e.hasMoreElements();) {
465        Instruction s = e.nextElement();
466        boolean isSynch = (s.operator() == READ_CEILING) || (s.operator() == WRITE_FLOOR) || (s.operator() == FENCE);
467        if (isSynch ||
468            Call.conforms(s) ||
469            MonitorOp.conforms(s) ||
470            Prepare.conforms(s) ||
471            Attempt.conforms(s) ||
472            CacheOp.conforms(s) ||
473            s.isDynamicLinkingPoint()) {
474          dictionary.registerUnknown(s, b);
475        }
476      }
477    }
478  }
479
480  /**
481   * Register every instruction in this method with the
482   * implicit heap array SSA lookaside structure.
483   *
484   * @param ir the governing IR
485   */
486  private void registerHeapVariables(IR ir) {
487    SSADictionary dictionary = ir.HIRInfo.dictionary;
488    for (Enumeration<BasicBlock> bbe = ir.getBasicBlocks(); bbe.hasMoreElements();) {
489      BasicBlock b = bbe.nextElement();
490      for (Enumeration<Instruction> e = b.forwardInstrEnumerator(); e.hasMoreElements();) {
491        Instruction s = e.nextElement();
492        if (s.isImplicitLoad() ||
493            s.isImplicitStore() ||
494            s.isAllocation() ||
495            Phi.conforms(s) ||
496            s.isPEI() ||
497            Label.conforms(s) ||
498            BBend.conforms(s) ||
499            s.getOpcode() == UNINT_BEGIN_opcode ||
500            s.getOpcode() == UNINT_END_opcode) {
501          dictionary.registerInstruction(s, b);
502        }
503      }
504    }
505  }
506
507  /**
508   * Insert phi functions for heap array SSA heap variables.
509   *
510   * @param ir the governing IR
511   */
512  private void insertHeapPhiFunctions(IR ir) {
513    Iterator<HeapVariable<Object>> e = ir.HIRInfo.dictionary.getHeapVariables();
514    while (e.hasNext()) {
515      HeapVariable<Object> H = e.next();
516
517      if (DEBUG) System.out.println("Inserting phis for Heap " + H);
518      if (DEBUG) System.out.println("Start iterated frontier...");
519
520      BitVector defH = H.getDefBlocks();
521      if (DEBUG) System.out.println(H + " DEFINED IN " + defH);
522
523      BitVector needsPhi = DominanceFrontier.
524          getIteratedDominanceFrontier(ir, defH);
525      if (DEBUG) System.out.println(H + " NEEDS PHI " + needsPhi);
526
527      if (DEBUG) System.out.println("Done.");
528      for (int b = 0; b < needsPhi.length(); b++) {
529        if (needsPhi.get(b)) {
530          BasicBlock bb = ir.getBasicBlock(b);
531          ir.HIRInfo.dictionary.createHeapPhiInstruction(bb, H);
532        }
533      }
534    }
535  }
536
537  /**
538   * Calculate the set of blocks that contain defs for each
539   *    symbolic register in an IR.  <em> Note: </em> This routine skips
540   *    registers marked  already having a single static
541   *    definition, physical registers, and guard registeres.
542   *
543   * @return an array of BitVectors, where element <em>i</em> represents the
544   *    basic blocks that contain defs for symbolic register <em>i</em>
545   */
546  private BitVector[] getDefSets() {
547    int nBlocks = ir.getMaxBasicBlockNumber();
548    BitVector[] result = new BitVector[ir.getNumberOfSymbolicRegisters()];
549
550    for (int i = 0; i < result.length; i++) {
551      result[i] = new BitVector(nBlocks + 1);
552    }
553
554    // loop over each basic block
555    for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
556      BasicBlock bb = e.nextElement();
557      int bbNumber = bb.getNumber();
558      // visit each instruction in the basic block
559      for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
560        Instruction s = ie.nextElement();
561        // record each def in the instruction
562        // skip SSA defs
563        for (int j = 0; j < s.getNumberOfDefs(); j++) {
564          Operand operand = s.getOperand(j);
565          if (operand == null) continue;
566          if (!operand.isRegister()) continue;
567          if (operand.asRegister().getRegister().isSSA()) continue;
568          if (operand.asRegister().getRegister().isPhysical()) continue;
569
570          int reg = operand.asRegister().getRegister().getNumber();
571          result[reg].set(bbNumber);
572        }
573      }
574    }
575    return result;
576  }
577
578  /**
579   * Insert the necessary phi functions into an IR.
580   * <p> Algorithm:
581   * <p>For register r, let S be the set of all blocks that
582   *    contain defs of r.  Let D be the iterated dominance frontier
583   *    of S.  Each block in D needs a phi-function for r.
584   *
585   * <p> Special Java case: if node N dominates all defs of r, then N
586   *                      does not need a phi-function for r
587   *
588   * @param ir the governing IR
589   * @param defs defs[i] represents the basic blocks that define
590   *            symbolic register i.
591   * @param symbolics symbolics[i] is symbolic register number i
592   * @param excludeGuards whether guard registers should be excluded
593   *  from SSA
594   */
595  private void insertPhiFunctions(IR ir, BitVector[] defs, Register[] symbolics, boolean excludeGuards) {
596    for (int r = 0; r < defs.length; r++) {
597      if (symbolics[r] == null) continue;
598      if (symbolics[r].isSSA()) continue;
599      if (symbolics[r].isPhysical()) continue;
600      if (excludeGuards && symbolics[r].isValidation()) continue;
601      if (DEBUG) System.out.println("Inserting phis for register " + r);
602      if (DEBUG) System.out.println("Start iterated frontier...");
603      BitVector needsPhi = DominanceFrontier.getIteratedDominanceFrontier(ir, defs[r]);
604      removePhisThatDominateAllDefs(needsPhi, ir, defs[r]);
605      if (DEBUG) System.out.println("Done.");
606
607      for (int b = 0; b < needsPhi.length(); b++) {
608        if (needsPhi.get(b)) {
609          BasicBlock bb = ir.getBasicBlock(b);
610          if (live.getLiveInfo(bb).getIn().contains(symbolics[r])) {
611            insertPhi(bb, symbolics[r]);
612          }
613        }
614      }
615    }
616  }
617
618  /**
619   * If node N dominates all defs of a register r, then N does
620   * not need a phi function for r; this function removes such
621   * nodes N from a Bit Set.
622   *
623   * @param needsPhi representation of set of nodes that
624   *                need phi functions for a register r
625   * @param ir the governing IR
626   * @param defs set of nodes that define register r
627   */
628  private void removePhisThatDominateAllDefs(BitVector needsPhi, IR ir, BitVector defs) {
629    for (int i = 0; i < needsPhi.length(); i++) {
630      if (!needsPhi.get(i)) {
631        continue;
632      }
633      if (ir.HIRInfo.dominatorTree.dominates(i, defs)) {
634        needsPhi.clear(i);
635      }
636    }
637  }
638
639  /**
640   * Insert a phi function for a symbolic register at the head
641   * of a basic block.
642   *
643   * @param bb the basic block
644   * @param r the symbolic register that needs a phi function
645   */
646  private void insertPhi(BasicBlock bb, Register r) {
647    Instruction s = makePhiInstruction(r, bb);
648    bb.firstInstruction().insertAfter(s);
649    scalarPhis.add(s);
650  }
651
652  /**
653   * Create a phi-function instruction
654   *
655   * @param r the symbolic register
656   * @param bb the basic block holding the new phi function
657   * @return the instruction r = PHI null,null,..,null
658   */
659  private Instruction makePhiInstruction(Register r, BasicBlock bb) {
660    int n = bb.getNumberOfIn();
661    Enumeration<BasicBlock> in = bb.getIn();
662    TypeReference type = null;
663    Instruction s = Phi.create(PHI, new RegisterOperand(r, type), n);
664    for (int i = 0; i < n; i++) {
665      RegisterOperand junk = new RegisterOperand(r, type);
666      Phi.setValue(s, i, junk);
667      BasicBlock pred = in.nextElement();
668      Phi.setPred(s, i, new BasicBlockOperand(pred));
669    }
670    s.position = ir.gc.getInlineSequence();
671    s.bcIndex = SSA_SYNTH_BCI;
672    return s;
673  }
674
675  /**
676   * Set up a mapping from symbolic register number to the register.
677   * <p> TODO: put this functionality elsewhere.
678   *
679   * @return a mapping
680   */
681  private Register[] getSymbolicRegisters() {
682    Register[] map = new Register[ir.getNumberOfSymbolicRegisters()];
683    for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
684      int number = reg.getNumber();
685      map[number] = reg;
686    }
687    return map;
688  }
689
690  /**
691   * Rename the symbolic registers so that each register has only one
692   * definition.
693   *
694   * <p><em> Note </em>: call this after phi functions have been inserted.
695   * <p> <b> Algorithm:</b> from Cytron et. al 91
696   * <pre>
697   *  call search(entry)
698   *
699   *  search(X):
700   *  for each statement A in X do
701   *     if A is not-phi
702   *       for each r in RHS(A) do
703   *            if !r.isSSA, replace r with TOP(S(r))
704   *       done
705   *     fi
706   *    for each r in LHS(A) do
707   *            if !r.isSSA
708   *                r2 = new temp register
709   *                push r2 onto S(r)
710   *                replace r in A by r2
711   *            fi
712   *    done
713   *  done (end of first loop)
714   *  for each Y in succ(X) do
715   *      j &lt;- whichPred(Y,X)
716   *      for each phi-function F in Y do
717   *       replace the j-th operand (r) in RHS(F) with TOP(S(r))
718   *     done
719   *  done (end of second loop)
720   *  for each Y in Children(X) do
721   *    call search(Y)
722   *  done (end of third loop)
723   *  for each assignment A in X do
724   *     for each r in LHS(A) do
725   *      pop(S(r))
726   *   done
727   *  done (end of fourth loop)
728   *  end
729   * </pre>
730   *
731   * @param symbolicRegisters mapping from integer to symbolic registers
732   */
733  private void renameSymbolicRegisters(Register[] symbolicRegisters) {
734    int n = ir.getNumberOfSymbolicRegisters();
735    @SuppressWarnings("unchecked") // the old covariant array-type problem
736        Stack<RegisterOperand>[] S = new Stack[n + 1];
737    for (int i = 0; i < S.length; i++) {
738      S[i] = new Stack<RegisterOperand>();
739      // populate the Stacks with initial names for
740      // each parameter, and push "null" for other symbolic registers
741      if (i >= symbolicRegisters.length) continue;
742      //Register r = symbolicRegisters[i];
743      // If a register's name is "null", that means the
744      // register has not yet been defined.
745      S[i].push(null);
746    }
747    BasicBlock entry = ir.cfg.entry();
748    DefUse.clearDU(ir);
749    numPredProcessed = new int[ir.getMaxBasicBlockNumber()];
750    search(entry, S);
751    DefUse.recomputeSSA(ir);
752    rectifyPhiTypes();
753  }
754
755  /**
756   * This routine is the guts of the SSA construction phase for scalars.  See
757   * renameSymbolicRegisters for more details.
758   *
759   * @param X basic block to search dominator tree from
760   * @param S stack of names for each register
761   */
762  private void search(BasicBlock X, Stack<RegisterOperand>[] S) {
763    if (DEBUG) System.out.println("SEARCH " + X);
764
765    HashMap<Register, Register> pushedRegs = new HashMap<Register, Register>();
766
767    for (Enumeration<Instruction> ie = X.forwardInstrEnumerator(); ie.hasMoreElements();) {
768      Instruction A = ie.nextElement();
769      if (A.operator() != PHI) {
770        // replace each use
771        for (int u = A.getNumberOfDefs(); u < A.getNumberOfOperands(); u++) {
772          Operand op = A.getOperand(u);
773          if (op instanceof RegisterOperand) {
774            RegisterOperand rop = (RegisterOperand) op;
775            Register r1 = rop.getRegister();
776            if (r1.isSSA()) continue;
777            if (r1.isPhysical()) continue;
778            RegisterOperand r2 = S[r1.getNumber()].peek();
779            if (DEBUG) System.out.println("REPLACE NORMAL USE " + r1 + " with " + r2);
780            if (r2 != null) {
781              rop.setRegister(r2.getRegister());
782              DefUse.recordUse(rop);
783            }
784          }
785        }
786      }
787      // replace each def
788      for (int d = 0; d < A.getNumberOfDefs(); d++) {
789        Operand op = A.getOperand(d);
790        if (op instanceof RegisterOperand) {
791          RegisterOperand rop = (RegisterOperand) op;
792          Register r1 = rop.getRegister();
793          if (r1.isSSA()) continue;
794          if (r1.isPhysical()) continue;
795          Register r2 = ir.regpool.getReg(r1);
796          if (DEBUG) System.out.println("PUSH " + r2 + " FOR " + r1 + " BECAUSE " + A);
797          S[r1.getNumber()].push(new RegisterOperand(r2, rop.getType()));
798          rop.setRegister(r2);
799          pushedRegs.put(r2, r1);
800        }
801      }
802    } // end of first loop
803
804    if (DEBUG) System.out.println("SEARCH (second loop) " + X);
805    for (Enumeration<BasicBlock> y = X.getOut(); y.hasMoreElements();) {
806      BasicBlock Y = y.nextElement();
807      if (DEBUG) System.out.println(" Successor: " + Y);
808      int j = numPredProcessed[Y.getNumber()]++;
809      if (Y.isExit()) continue;
810      Instruction s = Y.firstRealInstruction();
811      if (s == null) continue;
812      // replace use USE in each PHI instruction
813      if (DEBUG) System.out.println(" Predecessor: " + j);
814      while (s.operator() == PHI) {
815        Operand val = Phi.getValue(s, j);
816        if (val.isRegister()) {
817          Register r1 = ((RegisterOperand) Phi.getValue(s, j)).getRegister();
818          // ignore registers already marked SSA by a previous pass
819          if (!r1.isSSA()) {
820            RegisterOperand r2 = S[r1.getNumber()].peek();
821            if (r2 == null) {
822              // in this case, the register is never defined along
823              // this particular control flow path into the basic
824              // block.
825              Phi.setValue(s, j, new UnreachableOperand());
826            } else {
827              RegisterOperand rop = r2.copyRO();
828              Phi.setValue(s, j, rop);
829              DefUse.recordUse(rop);
830            }
831            Phi.setPred(s, j, new BasicBlockOperand(X));
832          }
833        }
834        s = s.nextInstructionInCodeOrder();
835      }
836    } // end of second loop
837
838    if (DEBUG) System.out.println("SEARCH (third loop) " + X);
839    for (Enumeration<TreeNode> c = ir.HIRInfo.dominatorTree.getChildren(X); c.hasMoreElements();) {
840      DominatorTreeNode v = (DominatorTreeNode) c.nextElement();
841      search(v.getBlock(), S);
842    } // end of third loop
843
844    if (DEBUG) System.out.println("SEARCH (fourth loop) " + X);
845    for (Enumeration<Instruction> a = X.forwardInstrEnumerator(); a.hasMoreElements();) {
846      Instruction A = a.nextElement();
847      // loop over each def
848      for (int d = 0; d < A.getNumberOfDefs(); d++) {
849        Operand newOp = A.getOperand(d);
850        if (newOp == null) continue;
851        if (!newOp.isRegister()) continue;
852        Register newReg = newOp.asRegister().getRegister();
853        if (newReg.isSSA()) continue;
854        if (newReg.isPhysical()) continue;
855        Register r1 = pushedRegs.get(newReg);
856        S[r1.getNumber()].pop();
857        if (DEBUG) System.out.println("POP " + r1);
858      }
859    } // end of fourth loop
860    if (DEBUG) System.out.println("FINISHED SEARCH " + X);
861  }
862
863  /**
864   * Rename the implicit heap variables in the SSA form so that
865   * each heap variable has only one definition.
866   *
867   * <p> Algorithm: Cytron et. al 91  (see renameSymbolicRegisters)
868   *
869   * @param ir the governing IR
870   */
871  private void renameHeapVariables(IR ir) {
872    int n = ir.HIRInfo.dictionary.getNumberOfHeapVariables();
873    if (n == 0) {
874      return;
875    }
876    // we maintain a stack of names for each type of heap variable
877    // stacks implements a mapping from type to Stack.
878    // Example: to get the stack of names for HEAP<int> variables,
879    // use stacks.get(ClassLoaderProxy.IntType);
880    HashMap<Object, Stack<HeapOperand<Object>>> stacks = new HashMap<Object, Stack<HeapOperand<Object>>>(n);
881    // populate the stacks variable with the initial heap variable
882    // names, currently stored in the SSADictionary
883    for (Iterator<HeapVariable<Object>> e = ir.HIRInfo.dictionary.getHeapVariables(); e.hasNext();) {
884      HeapVariable<Object> H = e.next();
885      Stack<HeapOperand<Object>> S = new Stack<HeapOperand<Object>>();
886      S.push(new HeapOperand<Object>(H));
887      Object heapType = H.getHeapType();
888      stacks.put(heapType, S);
889    }
890    BasicBlock entry = ir.cfg.entry();
891    numPredProcessed = new int[ir.getMaxBasicBlockNumber()];
892    search2(entry, stacks);
893    // registerRenamedHeapPhis(ir);
894  }
895
896  /**
897   * This routine is the guts of the SSA construction phase for heap array
898   * SSA.  The renaming algorithm is analagous to the algorithm for
899   * scalars See <code> renameSymbolicRegisters </code> for more details.
900   *
901   * @param X the current basic block being traversed
902   * @param stacks a structure holding the current names for each heap
903   * variable
904   * used and defined by each instruction.
905   */
906  private void search2(BasicBlock X, HashMap<Object, Stack<HeapOperand<Object>>> stacks) {
907    if (DEBUG) System.out.println("SEARCH2 " + X);
908    SSADictionary dictionary = ir.HIRInfo.dictionary;
909    for (Enumeration<Instruction> ie = dictionary.getAllInstructions(X); ie.hasMoreElements();) {
910      Instruction A = ie.nextElement();
911      if (!dictionary.usesHeapVariable(A) && !dictionary.defsHeapVariable(A)) continue;
912      if (A.operator() != PHI) {
913        // replace the Heap variables USED by this instruction
914        HeapOperand<Object>[] uses = dictionary.getHeapUses(A);
915        if (uses != null) {
916          @SuppressWarnings("unchecked")  // Generic array problem
917              HeapOperand<Object>[] newUses = new HeapOperand[uses.length];
918          for (int i = 0; i < uses.length; i++) {
919            Stack<HeapOperand<Object>> S = stacks.get(uses[i].getHeapType());
920            newUses[i] = S.peek().copy();
921            if (DEBUG) {
922              System.out.println("NORMAL USE PEEK " + newUses[i]);
923            }
924          }
925          dictionary.replaceUses(A, newUses);
926        }
927      }
928      // replace any Heap variable DEF
929      if (A.operator() != PHI) {
930        HeapOperand<Object>[] defs = dictionary.getHeapDefs(A);
931        if (defs != null) {
932          for (HeapOperand<Object> operand : dictionary.replaceDefs(A, X)) {
933            Stack<HeapOperand<Object>> S = stacks.get(operand.getHeapType());
934            S.push(operand);
935            if (DEBUG) System.out.println("PUSH " + operand + " FOR " + operand.getHeapType());
936          }
937        }
938      } else {
939        HeapOperand<Object>[] r = dictionary.replaceDefs(A, X);
940        Stack<HeapOperand<Object>> S = stacks.get(r[0].getHeapType());
941        S.push(r[0]);
942        if (DEBUG) System.out.println("PUSH " + r[0] + " FOR " + r[0].getHeapType());
943      }
944    } // end of first loop
945
946    for (Enumeration<BasicBlock> y = X.getOut(); y.hasMoreElements();) {
947      BasicBlock Y = y.nextElement();
948      if (Y.isExit()) continue;
949      int j = numPredProcessed[Y.getNumber()]++;
950      // replace each USE in each HEAP-PHI function for Y
951      for (Iterator<Instruction> hp = dictionary.getHeapPhiInstructions(Y); hp.hasNext();) {
952        Instruction s = hp.next();
953        @SuppressWarnings("unchecked") // Down-cast to a generic type
954            HeapOperand<Object> H1 = (HeapOperand) Phi.getResult(s);
955        Stack<HeapOperand<Object>> S = stacks.get(H1.getHeapType());
956        HeapOperand<Object> H2 = S.peek();
957        Phi.setValue(s, j, new HeapOperand<Object>(H2.getHeapVariable()));
958        Phi.setPred(s, j, new BasicBlockOperand(X));
959      }
960    } // end of second loop
961
962    for (Enumeration<TreeNode> c = ir.HIRInfo.dominatorTree.getChildren(X); c.hasMoreElements();) {
963      DominatorTreeNode v = (DominatorTreeNode) c.nextElement();
964      search2(v.getBlock(), stacks);
965    } // end of third loop
966
967    for (Enumeration<Instruction> a = dictionary.getAllInstructions(X); a.hasMoreElements();) {
968      Instruction A = a.nextElement();
969      if (!dictionary.usesHeapVariable(A) && !dictionary.defsHeapVariable(A)) continue;
970      // retrieve the Heap Variables defined by A
971      if (A.operator() != PHI) {
972        HeapOperand<Object>[] defs = dictionary.getHeapDefs(A);
973        if (defs != null) {
974          for (HeapOperand<Object> def : defs) {
975            Stack<HeapOperand<Object>> S = stacks.get(def.getHeapType());
976            S.pop();
977            if (DEBUG) System.out.println("POP " + def.getHeapType());
978          }
979        }
980      } else {
981        @SuppressWarnings("unchecked") // Down-cast to a generic type
982            HeapOperand<Object> H = (HeapOperand) Phi.getResult(A);
983        Stack<HeapOperand<Object>> S = stacks.get(H.getHeapType());
984        S.pop();
985        if (DEBUG) System.out.println("POP " + H.getHeapType());
986      }
987    } // end of fourth loop
988    if (DEBUG) System.out.println("END SEARCH2 " + X);
989  }
990
991  /**
992   * After performing renaming on heap phi functions, this
993   * routines notifies the SSA dictionary of the new names.
994   * <p>
995   * FIXME - this was commented out: delete it ??  RJG
996   *
997   * @param ir the governing IR
998   */
999  @SuppressWarnings({"unused", "unchecked"})
1000  // HeapOperand requires casts to a generic type
1001  private void registerRenamedHeapPhis(IR ir) {
1002    SSADictionary ssa = ir.HIRInfo.dictionary;
1003    for (Enumeration<BasicBlock> e1 = ir.getBasicBlocks(); e1.hasMoreElements();) {
1004      BasicBlock bb = e1.nextElement();
1005      for (Enumeration<Instruction> e2 = ssa.getAllInstructions(bb); e2.hasMoreElements();) {
1006        Instruction s = e2.nextElement();
1007        if (Phi.conforms(s)) {
1008          if (ssa.defsHeapVariable(s)) {
1009            int n = Phi.getNumberOfValues(s);
1010            HeapOperand<Object>[] uses = new HeapOperand[n];
1011            for (int i = 0; i < n; i++) {
1012              uses[i] = (HeapOperand) Phi.getValue(s, i);
1013            }
1014            ssa.replaceUses(s, uses);
1015          }
1016        }
1017      }
1018    }
1019  }
1020
1021  /**
1022   * Store a copy of the Heap variables each instruction defs.
1023   *
1024   * @param ir governing IR
1025   * @param store place to store copies
1026   */
1027  @SuppressWarnings("unused")
1028  private void copyHeapDefs(IR ir, HashMap<Instruction, HeapOperand<?>[]> store) {
1029    SSADictionary dictionary = ir.HIRInfo.dictionary;
1030    for (Enumeration<BasicBlock> be = ir.forwardBlockEnumerator(); be.hasMoreElements();) {
1031      BasicBlock bb = be.nextElement();
1032      for (Enumeration<Instruction> e = dictionary.getAllInstructions(bb); e.hasMoreElements();) {
1033        Instruction s = e.nextElement();
1034        store.put(s, ir.HIRInfo.dictionary.getHeapDefs(s));
1035      }
1036    }
1037  }
1038
1039  private enum PhiTypeInformation {
1040    NO_NULL_TYPE, FOUND_NULL_TYPE
1041  }
1042
1043  /*
1044   * Compute type information for operands in each phi instruction.
1045   *
1046   * PRECONDITION: Def-use chains computed.
1047   * SIDE EFFECT: empties the scalarPhis set
1048   */
1049  private void rectifyPhiTypes() {
1050    if (DEBUG) System.out.println("Rectify phi types.");
1051    removeAllUnreachablePhis(scalarPhis);
1052    int noRehashCapacity = (int) (scalarPhis.size() * 1.5f);
1053    HashMap<Instruction, PhiTypeInformation> phiTypes =
1054        new HashMap<Instruction, PhiTypeInformation>(noRehashCapacity) ;
1055    while (!scalarPhis.isEmpty()) {
1056      boolean didSomething = false;
1057      for (Iterator<Instruction> i = scalarPhis.iterator(); i.hasNext();) {
1058        Instruction phi = i.next();
1059        phiTypes.put(phi, PhiTypeInformation.NO_NULL_TYPE);
1060        if (DEBUG) System.out.println("PHI: " + phi);
1061        TypeReference meet = meetPhiType(phi, phiTypes);
1062        if (DEBUG) System.out.println("MEET: " + meet);
1063        if (meet != null) {
1064          didSomething = true;
1065          if (phiTypes.get(phi) == PhiTypeInformation.NO_NULL_TYPE) i.remove();
1066          RegisterOperand result = (RegisterOperand) Phi.getResult(phi);
1067          result.setType(meet);
1068          for (Enumeration<RegisterOperand> e = DefUse.uses(result.getRegister()); e.hasMoreElements();) {
1069            RegisterOperand rop = e.nextElement();
1070            if (rop.getType() != meet) {
1071              rop.clearPreciseType();
1072              rop.setType(meet);
1073            }
1074          }
1075        }
1076      }
1077      if (!didSomething) {
1078        // iteration has bottomed out.
1079        return;
1080      }
1081    }
1082  }
1083
1084  private void removeAllUnreachablePhis(HashSet<Instruction> scalarPhis) {
1085    boolean iterateAgain = false;
1086    do {
1087      iterateAgain = false;
1088      outer:
1089      for (Iterator<Instruction> i = scalarPhis.iterator(); i.hasNext();) {
1090        Instruction phi = i.next();
1091        for (int j = 0; j < Phi.getNumberOfValues(phi); j++) {
1092          Operand op = Phi.getValue(phi, j);
1093          if (!(op instanceof UnreachableOperand)) {
1094            continue outer;
1095          }
1096        }
1097        RegisterOperand result = Phi.getResult(phi).asRegister();
1098        i.remove();
1099        for (Enumeration<RegisterOperand> e = DefUse.uses(result.getRegister()); e.hasMoreElements();) {
1100          RegisterOperand use = e.nextElement();
1101          Instruction s = use.instruction;
1102          if (Phi.conforms(s)) {
1103            for (int k = 0; k < Phi.getNumberOfValues(phi); k++) {
1104              Operand op = Phi.getValue(phi, k);
1105              if (op != null && op.similar(result)) {
1106                Phi.setValue(phi, k, new UnreachableOperand());
1107                iterateAgain = true;
1108              }
1109            }
1110          }
1111        }
1112      }
1113    } while (iterateAgain);
1114  }
1115
1116  @SuppressWarnings("unused")
1117  private void removeUnreachableOperands(HashSet<Instruction> scalarPhis) {
1118    for (Instruction phi : scalarPhis) {
1119      boolean didSomething = true;
1120      while (didSomething) {
1121        didSomething = false;
1122        for (int j = 0; j < Phi.getNumberOfValues(phi); j++) {
1123          Operand v = Phi.getValue(phi, j);
1124          if (v instanceof UnreachableOperand) {
1125            // rewrite the phi instruction to remove the unreachable
1126            // operand
1127            didSomething = true;
1128            Instruction tmpPhi = phi.copyWithoutLinks();
1129            Phi.mutate(phi, PHI, Phi.getResult(tmpPhi), Phi.getNumberOfValues(phi) - 1);
1130            int m = 0;
1131            for (int k = 0; k < Phi.getNumberOfValues(phi); k++) {
1132              if (k == j) continue;
1133              Phi.setValue(phi, m, Phi.getValue(tmpPhi, k));
1134              Phi.setPred(phi, m, Phi.getPred(tmpPhi, k));
1135              m++;
1136            }
1137          }
1138        }
1139      }
1140    }
1141  }
1142
1143  /**
1144   * Return the meet of the types on the rhs of a phi instruction
1145   *
1146   * @param s phi instruction
1147   * @param phiTypes TODO
1148   * @return the meet of the types
1149   */
1150  private static TypeReference meetPhiType(Instruction s, Map<Instruction, PhiTypeInformation> phiTypes) {
1151    TypeReference result = null;
1152    for (int i = 0; i < Phi.getNumberOfValues(s); i++) {
1153      Operand val = Phi.getValue(s, i);
1154      if (val instanceof UnreachableOperand) continue;
1155      TypeReference t = val.getType();
1156      if (t == null) {
1157        phiTypes.put(s, PhiTypeInformation.FOUND_NULL_TYPE);
1158      } else if (result == null) {
1159        result = t;
1160      } else {
1161        TypeReference meet = ClassLoaderProxy.findCommonSuperclass(result, t);
1162        if (meet == null) {
1163          // TODO: This horrific kludge should go away once we get rid of Address.toInt()
1164          if ((result.isIntLikeType() && (t.isReferenceType() || t.isWordLikeType())) ||
1165              ((result.isReferenceType() || result.isWordLikeType()) && t.isIntLikeType())) {
1166            meet = TypeReference.Int;
1167          } else if (result.isReferenceType() && t.isWordLikeType()) {
1168            meet = t;
1169          } else if (result.isWordLikeType() && t.isReferenceType()) {
1170            meet = result;
1171          }
1172        }
1173        if (VM.VerifyAssertions && meet == null) {
1174          String msg = result + " and " + t + " meet to null";
1175          VM._assert(VM.NOT_REACHED, msg);
1176        }
1177        result = meet;
1178      }
1179    }
1180    return result;
1181  }
1182
1183  @SuppressWarnings("unused")
1184  private TypeReference findParameterType(Register p) {
1185    RegisterOperand firstUse = p.useList;
1186    if (firstUse == null) {
1187      return null;             // parameter has no uses
1188    }
1189    return firstUse.getType();
1190  }
1191}
1192
1193
1194