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;
014
015import static org.jikesrvm.compilers.opt.driver.OptConstants.YES;
016import static org.jikesrvm.compilers.opt.ir.Operators.ARRAYLENGTH_opcode;
017import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
018import static org.jikesrvm.compilers.opt.ir.Operators.GET_CAUGHT_EXCEPTION;
019import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
020import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE;
021import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY;
022import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY_UNRESOLVED;
023import static org.jikesrvm.compilers.opt.ir.Operators.NOP;
024import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
025import static org.jikesrvm.compilers.opt.ir.Operators.SET_CAUGHT_EXCEPTION;
026import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN;
027import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END;
028
029import java.lang.reflect.Constructor;
030import java.util.ArrayList;
031import java.util.Enumeration;
032
033import org.jikesrvm.VM;
034import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
035import org.jikesrvm.compilers.opt.controlflow.BranchSimplifier;
036import org.jikesrvm.compilers.opt.driver.CompilerPhase;
037import org.jikesrvm.compilers.opt.ir.BasicBlock;
038import org.jikesrvm.compilers.opt.ir.Binary;
039import org.jikesrvm.compilers.opt.ir.BoundsCheck;
040import org.jikesrvm.compilers.opt.ir.GuardedUnary;
041import org.jikesrvm.compilers.opt.ir.IR;
042import org.jikesrvm.compilers.opt.ir.Instruction;
043import org.jikesrvm.compilers.opt.ir.Move;
044import org.jikesrvm.compilers.opt.ir.NewArray;
045import org.jikesrvm.compilers.opt.ir.Operator;
046import org.jikesrvm.compilers.opt.ir.Phi;
047import org.jikesrvm.compilers.opt.ir.Register;
048import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
049import org.jikesrvm.compilers.opt.ir.operand.Operand;
050import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
051import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
052
053/**
054 * Simple flow-insensitive optimizations.
055 *
056 * <p> Except for the "CompilerPhase" methods, all fields and methods in
057 * this class are declared static.
058 */
059public final class Simple extends CompilerPhase {
060
061  private final BranchOptimizations branchOpts = new BranchOptimizations(-1, false, false, false);
062
063  /**
064   * At what optimization level should this phase be run?
065   */
066  private final int level;
067  /**
068   * Perform type propagation?
069   */
070  private final boolean typeProp;
071  /**
072   * Attempt to eliminate bounds and cast checks?
073   */
074  private final boolean foldChecks;
075  /**
076   * Fold conditional branches with constant operands?
077   */
078  private final boolean foldBranches;
079  /**
080   * Sort registers used by commutative operators
081   */
082  private final boolean sortRegisters;
083
084  @Override
085  public boolean shouldPerform(OptOptions options) {
086    return options.getOptLevel() >= level;
087  }
088
089  @Override
090  public String getName() {
091    return "Simple Opts";
092  }
093
094  @Override
095  public boolean printingEnabled(OptOptions options, boolean before) {
096    return false;
097  }
098
099  /**
100   * The constructor is used to specify what pieces of Simple will
101   * be enabled for this instance.  Some pieces are always enabled.
102   * Customizing can be useful because some of the optimizations are not
103   * valid/useful on LIR or even on "late stage" HIR.
104   *
105   * @param level at what optimization level should the phase be enabled?
106   * @param typeProp should type propagation be peformed?
107   * @param foldChecks should we attempt to eliminate boundscheck?
108   * @param foldBranches should we attempt to constant fold conditional
109   * @param sortRegisters should we sort use operands?
110   * branches?
111   */
112  public Simple(int level, boolean typeProp, boolean foldChecks, boolean foldBranches, boolean sortRegisters) {
113    super(new Object[]{level, typeProp, foldChecks, foldBranches, sortRegisters});
114    this.level = level;
115    this.typeProp = typeProp;
116    this.foldChecks = foldChecks;
117    this.foldBranches = foldBranches;
118    this.sortRegisters = sortRegisters;
119  }
120
121  /**
122   * Constructor for this compiler phase
123   */
124  private static final Constructor<CompilerPhase> constructor =
125      getCompilerPhaseConstructor(Simple.class,
126                                  new Class[]{Integer.TYPE, Boolean.TYPE, Boolean.TYPE, Boolean.TYPE, Boolean.TYPE});
127
128  /**
129   * Get a constructor object for this compiler phase
130   * @return compiler phase constructor
131   */
132  @Override
133  public Constructor<CompilerPhase> getClassConstructor() {
134    return constructor;
135  }
136
137  /**
138   * Main driver for the simple optimizations
139   *
140   * @param ir the IR to optimize
141   */
142  @Override
143  public void perform(IR ir) {
144    // Compute defList, useList, useCount fields for each register.
145    DefUse.computeDU(ir);
146    // Recompute isSSA flags
147    DefUse.recomputeSSA(ir);
148    // Simple copy propagation.
149    // This pass incrementally updates the register list.
150    copyPropagation(ir);
151    // Simple type propagation.
152    // This pass uses the register list, but doesn't modify it.
153    if (typeProp) {
154      typePropagation(ir);
155    }
156    // Perform simple bounds-check and arraylength elimination.
157    // This pass incrementally updates the register list
158    if (foldChecks) {
159      arrayPropagation(ir);
160    }
161    // Simple dead code elimination.
162    // This pass incrementally updates the register list
163    eliminateDeadInstructions(ir);
164    // constant folding
165    // This pass usually doesn't modify the DU, but
166    // if it does it will recompute it.
167    foldConstants(ir);
168    // Simple local expression folding respecting DU
169    if (ir.options.LOCAL_EXPRESSION_FOLDING && ExpressionFolding.performLocal(ir)) {
170      // constant folding again
171      foldConstants(ir);
172    }
173    // Try to remove conditional branches with constant operands
174    // If it actually constant folds a branch,
175    // this pass will recompute the DU
176    if (foldBranches) {
177      simplifyConstantBranches(ir);
178    }
179    // Should we sort commutative use operands
180    if (sortRegisters) {
181      sortCommutativeRegisterUses(ir);
182    }
183  }
184
185  /**
186   * Sort commutative use operands so that those defined most are on the lhs
187   *
188   * @param ir the IR to work on
189   */
190  private static void sortCommutativeRegisterUses(IR ir) {
191    // Pass over instructions
192    for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
193      Instruction s = e.nextElement();
194      // Sort most frequently defined operands onto lhs
195      if (Binary.conforms(s) && s.operator().isCommutative() &&
196          Binary.getVal1(s).isRegister() && Binary.getVal2(s).isRegister()) {
197        RegisterOperand rop1 = Binary.getVal1(s).asRegister();
198        RegisterOperand rop2 = Binary.getVal2(s).asRegister();
199        // Simple SSA based test
200        if (rop1.getRegister().isSSA()) {
201          if (rop2.getRegister().isSSA()) {
202            // ordering is arbitrary, ignore
203          } else {
204            // swap
205            Binary.setVal1(s, rop2);
206            Binary.setVal2(s, rop1);
207          }
208        } else if (rop2.getRegister().isSSA()) {
209          // already have prefered ordering
210        } else {
211          // neither registers are SSA so place registers used more on the RHS
212          // (we don't have easy access to a count of the number of definitions)
213          if (rop1.getRegister().useCount > rop2.getRegister().useCount) {
214            // swap
215            Binary.setVal1(s, rop2);
216            Binary.setVal2(s, rop1);
217          }
218        }
219      }
220    }
221  }
222
223  /**
224   * Perform flow-insensitive copy and constant propagation using
225   * register list information.
226   *
227   * <ul>
228   * <li> Note: register list MUST be initialized BEFORE calling this routine.
229   * <li> Note: this function incrementally maintains the register list.
230   * </ul>
231   *
232   * @param ir the IR in question
233   */
234  public static void copyPropagation(IR ir) {
235    // Use register list to enumerate register objects
236    Register elemNext;
237    boolean reiterate = true;
238    while (reiterate) {         // /MT/ better think about proper ordering.
239      reiterate = false;
240      for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = elemNext) {
241        elemNext = reg.getNext(); // we may remove reg, so get elemNext up front
242        if (reg.useList == null ||   // Copy propagation not possible if reg
243            // has no uses
244            reg.defList == null ||   // Copy propagation not possible if reg
245            // has no defs
246            !reg.isSSA()) {           // Flow-insensitive copy prop only possible
247          // for SSA registers.
248          continue;
249        }
250        // isSSA => reg has exactly one definition, reg.defList.
251        RegisterOperand lhs = reg.defList;
252        Instruction defInstr = lhs.instruction;
253        Operand rhs;
254        // Copy/constant propagation only possible when defInstr is a move
255        if (defInstr.isMove()) {
256          rhs = Move.getVal(defInstr);
257        } else if (defInstr.operator() == PHI) {
258          Operand phiVal = equivalentValforPHI(defInstr);
259          if (phiVal == null) continue;
260          rhs = phiVal;
261        } else {
262          continue;
263        }
264
265        if (rhs.isRegister()) {
266          Register rrhs = rhs.asRegister().getRegister();
267          // If rhs is a non-SSA register, then we can't propagate it
268          // because we can't be sure that the same definition reaches
269          // all uses.
270          if (!rrhs.isSSA()) continue;
271
272          // If rhs is a physical register, then we can't safely propagate
273          // it to uses of lhs because we don't understand the implicit
274          // uses/defs of physical registers well enough to do so safely.
275          if (rrhs.isPhysical()) continue;
276        }
277
278        reiterate = ir.options.getOptLevel() > 1;
279        // Now substitute rhs for all uses of lhs, updating the
280        // register list as we go.
281        if (rhs.isRegister()) {
282          RegisterOperand nextUse;
283          RegisterOperand rhsRegOp = rhs.asRegister();
284          for (RegisterOperand use = reg.useList; use != null; use = nextUse) {
285            nextUse = use.getNext(); // get early before reg's useList is updated.
286            if (VM.VerifyAssertions) VM._assert(rhsRegOp.getRegister().getType() == use.getRegister().getType());
287            DefUse.transferUse(use, rhsRegOp);
288          }
289        } else if (rhs.isConstant()) {
290          // NOTE: no need to incrementally update use's register list since we are going
291          //       to blow it all away as soon as this loop is done.
292          for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
293            int index = use.getIndexInInstruction();
294            use.instruction.putOperand(index, rhs.copy());
295          }
296        } else {
297          throw new OptimizingCompilerException("Simple.copyPropagation: unexpected operand type");
298        }
299        // defInstr is now dead. Remove it.
300        defInstr.remove();
301        if (rhs.isRegister()) {
302          DefUse.removeUse(rhs.asRegister());
303        }
304        ir.regpool.removeRegister(lhs.getRegister());
305      }
306    }
307  }
308
309  /**
310   * Try to find an operand that is equivalent to the result of a
311   * given phi instruction.
312   *
313   * @param phi the instruction to be simplified
314   * @return one of the phi's operands that is equivalent to the phi's result,
315   * or null if the phi can not be simplified.
316   */
317  static Operand equivalentValforPHI(Instruction phi) {
318    if (!Phi.conforms(phi)) return null;
319    // search for the first input that is different from the result
320    Operand result = Phi.getResult(phi), equiv = result;
321    int i = 0, n = Phi.getNumberOfValues(phi);
322    while (i < n) {
323      equiv = Phi.getValue(phi, i++);
324      if (!equiv.similar(result)) break;
325    }
326    // no luck if result and equiv aren't the only distinct inputs
327    while (i < n) {
328      Operand opi = Phi.getValue(phi, i++);
329      if (!opi.similar(equiv) && !opi.similar(result)) return null;
330    }
331    return equiv;
332  }
333
334  /**
335   * Perform flow-insensitive type propagation using register list
336   * information. Note: register list MUST be initialized BEFORE
337   * calling this routine.
338   *
339   * <p> Kept separate from copyPropagation loop to enable clients
340   * more flexibility.
341   *
342   * @param ir the IR in question
343   */
344  static void typePropagation(IR ir) {
345    // Use register list to enumerate register objects (FAST)
346    Register elemNext;
347    for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = elemNext) {
348      elemNext = reg.getNext();
349      // Type propagation not possible if reg has no uses
350      if (reg.useList == null) {
351        continue;
352      }
353      // Type propagation not possible if reg has no defs
354      if (reg.defList == null) {
355        continue;
356      }
357      // Do not attempt type propagation if reg has multiple defs
358      if (!reg.isSSA()) {
359        continue;
360      }
361      // Now reg has exactly one definition
362      RegisterOperand lhs = reg.defList;
363      Instruction instr = lhs.instruction;
364      Operator op = instr.operator();
365      // Type propagation not possible if lhs is not in a move instr
366      if (!op.isMove()) {
367        continue;
368      }
369      Operand rhsOp = Move.getVal(instr);
370      // Do not attempt type propagation if RHS is not a register
371      if (!(rhsOp instanceof RegisterOperand)) {
372        continue;
373      }
374      RegisterOperand rhs = (RegisterOperand) rhsOp;
375      // Propagate the type in the def
376      lhs.copyTypeFrom(rhs);
377
378      // Now propagate lhs into all uses; substitute rhs.type for lhs.type
379      for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
380        // if rhs.type is a supertype of use.type, don't do it
381        // because use.type has more detailed information
382        if (ClassLoaderProxy.includesType(rhs.getType(), use.getType()) == YES) {
383          continue;
384        }
385        // If Magic has been employed to convert an int to a reference,
386        // don't undo the effects!
387        if (rhs.getType().isPrimitiveType() && !use.getType().isPrimitiveType()) {
388          continue;
389        }
390        use.copyTypeFrom(rhs);
391      }
392    }
393  }
394
395  /**
396   * Perform flow-insensitive propagation to eliminate bounds checks
397   * and arraylength for arrays with static lengths. Only useful on the HIR
398   * (because BOUNDS_CHECK is expanded in LIR into multiple instrs)
399   *
400   * <p> Note: this function incrementally maintains the register list.
401   *
402   * @param ir the IR in question
403   */
404  static void arrayPropagation(IR ir) {
405    // Use register list to enumerate register objects (FAST)
406    Register elemNext;
407    for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = elemNext) {
408      elemNext = reg.getNext();
409      if (reg.useList == null) {
410        continue;
411      }
412      if (reg.defList == null) {
413        continue;
414      }
415      if (!reg.isSSA()) {
416        continue;
417      }
418      // Now reg has exactly one definition
419      RegisterOperand lhs = reg.defList;
420      Instruction instr = lhs.instruction;
421      Operator op = instr.operator();
422      if (!(op == NEWARRAY || op == NEWARRAY_UNRESOLVED)) {
423        continue;
424      }
425      Operand sizeOp = NewArray.getSize(instr);
426      // check for an array whose length is a compile-time constant
427      // or an SSA register
428      boolean boundsCheckOK = false;
429      boolean arraylengthOK = false;
430      int size = -1;
431      if (sizeOp instanceof IntConstantOperand) {
432        size = ((IntConstantOperand) sizeOp).value;
433        boundsCheckOK = true;
434        arraylengthOK = true;
435      } else if (sizeOp instanceof RegisterOperand) {
436        if (sizeOp.asRegister().getRegister().isSSA()) {
437          arraylengthOK = true;
438        }
439      }
440      // Now propagate
441      for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
442        Instruction i = use.instruction;
443        // bounds-check elimination
444        if (boundsCheckOK && i.getOpcode() == BOUNDS_CHECK_opcode) {
445          Operand indexOp = BoundsCheck.getIndex(i);
446          if (indexOp instanceof IntConstantOperand) {
447            if (((IntConstantOperand) indexOp).value <= size) {
448              Instruction s =
449                  Move.create(GUARD_MOVE, BoundsCheck.getGuardResult(i).copyD2D(), new TrueGuardOperand());
450              s.position = i.position;
451              s.bcIndex = i.bcIndex;
452              i.insertAfter(s);
453              DefUse.updateDUForNewInstruction(s);
454              DefUse.removeInstructionAndUpdateDU(i);
455            }
456          }
457        } else if (arraylengthOK && i.getOpcode() == ARRAYLENGTH_opcode) {
458          Operand newSizeOp = sizeOp.copy();
459          RegisterOperand result = (RegisterOperand) GuardedUnary.getResult(i).copy();
460          Instruction s = Move.create(INT_MOVE, result, newSizeOp);
461          s.position = i.position;
462          s.bcIndex = i.bcIndex;
463          i.insertAfter(s);
464          DefUse.updateDUForNewInstruction(s);
465          DefUse.removeInstructionAndUpdateDU(i);
466        }
467      }
468    }
469  }
470
471  /**
472   * Simple conservative dead code elimination.
473   * An instruction is eliminated if:
474   * <ul>
475   *  <li> 1. it is not a PEI, store or call
476   *  <li> 2. it DEFs only registers
477   *  <li> 3. all registers it DEFS are dead
478   * </ul>
479   *
480   * <p> Note: this function incrementally maintains the register list.
481   *
482   * @param ir the IR to optimize
483   */
484  static void eliminateDeadInstructions(IR ir) {
485    eliminateDeadInstructions(ir, false);
486  }
487
488  /**
489   * Simple conservative dead code elimination.
490   * An instruction is eliminated if:
491   * <ul>
492   *  <li> 1. it is not a PEI, store or non-pure call
493   *  <li> 2. it DEFs only registers
494   *  <li> 3. all registers it DEFS are dead
495   * </ul>
496   *
497   * <p> Note: this function incrementally maintains the register list.
498   *
499   * @param ir IR to optimize
500   * @param preserveImplicitSSA if this is true, do not eliminate dead
501   * instructions that have implicit operands for heap array SSA form
502   */
503  public static void eliminateDeadInstructions(IR ir, boolean preserveImplicitSSA) {
504    // (USE BACKWARDS PASS FOR INCREASED EFFECTIVENESS)
505    ArrayList<Instruction> setCaughtExceptionInstructions = null;
506    int getCaughtExceptionInstructions = 0;
507    for (Instruction instr = ir.lastInstructionInCodeOrder(),
508        prevInstr = null; instr != null; instr = prevInstr) {
509      prevInstr = instr.prevInstructionInCodeOrder(); // cache because
510      // remove nulls next/prev fields
511      // if instr is a PEI, store, branch, or call, then it's not dead ...
512      if (instr.isPEI() || instr.isImplicitStore() || instr.isBranch() || instr.isNonPureCall()) {
513        continue;
514      }
515      if (preserveImplicitSSA && (instr.isImplicitLoad() || instr.isAllocation() || instr.operator() == PHI)) {
516        continue;
517      }
518
519      if (instr.operator() == SET_CAUGHT_EXCEPTION) {
520        if (setCaughtExceptionInstructions == null) {
521          setCaughtExceptionInstructions = new ArrayList<Instruction>();
522        }
523        setCaughtExceptionInstructions.add(instr);
524      }
525
526      // remove NOPs
527      if (instr.operator() == NOP) {
528        DefUse.removeInstructionAndUpdateDU(instr);
529      }
530
531      // remove UNINT_BEGIN/UNINT_END with nothing in between them
532      if (instr.operator() == UNINT_BEGIN) {
533        Instruction s = instr.nextInstructionInCodeOrder();
534        if (s.operator() == UNINT_END) {
535          DefUse.removeInstructionAndUpdateDU(s);
536          DefUse.removeInstructionAndUpdateDU(instr);
537        }
538      }
539
540      // remove trivial assignments
541      if (Move.conforms(instr)) {
542        Register lhs = Move.getResult(instr).asRegister().getRegister();
543        if (Move.getVal(instr).isRegister()) {
544          Register rhs = Move.getVal(instr).asRegister().getRegister();
545          if (lhs == rhs) {
546            DefUse.removeInstructionAndUpdateDU(instr);
547            continue;
548          }
549        }
550      }
551      if (instr.operator() == GET_CAUGHT_EXCEPTION) {
552        getCaughtExceptionInstructions++;
553      }
554
555      // check that all defs are to dead registers and that
556      // there is at least 1 def.
557      boolean isDead = true;
558      boolean foundRegisterDef = false;
559      for (Enumeration<Operand> defs = instr.getDefs(); defs.hasMoreElements();) {
560        Operand def = defs.nextElement();
561        if (!def.isRegister()) {
562          isDead = false;
563          break;
564        }
565        foundRegisterDef = true;
566        RegisterOperand r = def.asRegister();
567        if (r.getRegister().useList != null) {
568          isDead = false;
569          break;
570        }
571        if (r.getRegister().isPhysical()) {
572          isDead = false;
573          break;
574        }
575      }
576      if (!isDead) {
577        continue;
578      }
579      if (!foundRegisterDef) {
580        continue;
581      }
582      if (instr.operator() == GET_CAUGHT_EXCEPTION) {
583        getCaughtExceptionInstructions--;
584      }
585      // There are 1 or more register defs, but all of them are dead.
586      // Remove instr.
587      DefUse.removeInstructionAndUpdateDU(instr);
588    }
589    if (false && // temporarily disabled - see RVM-410
590        (getCaughtExceptionInstructions == 0) &&
591        (setCaughtExceptionInstructions != null)) {
592      for (Instruction instr : setCaughtExceptionInstructions) {
593        DefUse.removeInstructionAndUpdateDU(instr);
594      }
595    }
596  }
597
598  /**
599   * Perform constant folding.
600   *
601   * @param ir the IR to optimize
602   */
603  void foldConstants(IR ir) {
604    boolean recomputeRegList = false;
605    for (Instruction s = ir.firstInstructionInCodeOrder(); s != null; s = s.nextInstructionInCodeOrder()) {
606      Simplifier.DefUseEffect code = Simplifier.simplify(ir.IRStage == IR.HIR, ir.regpool, ir.options, s);
607      // If something was reduced (as opposed to folded) then its uses may
608      // be different. This happens so infrequently that it's cheaper to
609      // handle it by  recomputing the DU from
610      // scratch rather than trying to do the incremental bookkeeping.
611      recomputeRegList |=
612          (code == Simplifier.DefUseEffect.MOVE_REDUCED ||
613           code == Simplifier.DefUseEffect.TRAP_REDUCED ||
614           code == Simplifier.DefUseEffect.REDUCED);
615    }
616    if (recomputeRegList) {
617      DefUse.computeDU(ir);
618      DefUse.recomputeSSA(ir);
619    }
620  }
621
622  /**
623   * Simplify branches whose operands are constants.
624   *
625   * <p> NOTE: This pass ensures that the register list is still valid after it
626   * is done.
627   *
628   * @param ir the IR to optimize
629   */
630  void simplifyConstantBranches(IR ir) {
631    boolean didSomething = false;
632    for (Enumeration<BasicBlock> e = ir.forwardBlockEnumerator(); e.hasMoreElements();) {
633      BasicBlock bb = e.nextElement();
634      didSomething |= BranchSimplifier.simplify(bb, ir);
635    }
636    if (didSomething) {
637      // killed at least one branch, cleanup the CFG removing dead code.
638      // Then recompute register list and isSSA info
639      branchOpts.perform(ir, true);
640      DefUse.computeDU(ir);
641      DefUse.recomputeSSA(ir);
642    }
643  }
644}