harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hinde...@apache.org
Subject svn commit: r952017 [4/5] - in /harmony/enhanced/java/trunk/drlvm: make/vm/ vm/jitrino/config/em64t/ vm/jitrino/config/ia32/ vm/jitrino/src/codegenerator/ vm/jitrino/src/codegenerator/ia32/ vm/jitrino/src/jet/ vm/jitrino/src/optimizer/ vm/jitrino/src/o...
Date Sun, 06 Jun 2010 22:47:41 GMT
Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.cpp?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.cpp (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.cpp Sun Jun  6 22:47:40 2010
@@ -0,0 +1,221 @@
+/* -*- mode: c++; indent-tabs-mode: nil; -*- */
+
+#include "expr.h"
+
+namespace Jitrino {
+
+bool
+Expr::int_zero_p () const
+{
+  Integer *i = as_integer ();
+
+  return i && i->value == 0;
+}
+
+bool
+Expr::int_nonzero_p () const
+{
+  Integer *i = as_integer ();
+
+  return i && i->value != 0;
+}
+
+bool
+Expr::int_one_p () const
+{
+  Integer *i = as_integer ();
+
+  return i && i->value == 1;
+}
+
+SsaOpnd* Integer::gen_insts_before (Inst *inst, IRManager &irm)
+{
+  TypeManager &type_manager = irm.getTypeManager ();
+  OpndManager &opnd_manager = irm.getOpndManager ();
+  InstFactory &inst_factory = irm.getInstFactory ();
+
+  Type *type = type_manager.getInt32Type ();
+  SsaTmpOpnd *result = opnd_manager.createSsaTmpOpnd (type);
+  Inst *new_inst = inst_factory.makeLdConst (result, value);
+
+  new_inst->insertBefore (inst);
+
+  return result;
+}
+
+SsaOpnd* Variable::gen_insts_before (Inst *inst, IRManager &irm)
+{
+  SsaVarOpnd *ssa_var_opnd = opnd->asSsaVarOpnd ();
+
+  if (!ssa_var_opnd)
+    {
+      assert (opnd->asSsaTmpOpnd ());
+
+      return opnd;
+    }
+
+  OpndManager &opnd_manager = irm.getOpndManager ();
+  InstFactory &inst_factory = irm.getInstFactory ();
+
+  Type *type = opnd->getType ();
+  SsaTmpOpnd *result = opnd_manager.createSsaTmpOpnd (type);
+  Inst *new_inst = inst_factory.makeLdVar (result, ssa_var_opnd);
+
+  new_inst->insertBefore (inst);
+
+  return result;
+}
+
+SsaOpnd* OpExpr::gen_insts_before (Inst *inst, IRManager &irm)
+{
+  TypeManager &type_manager = irm.getTypeManager ();
+  OpndManager &opnd_manager = irm.getOpndManager ();
+  InstFactory &inst_factory = irm.getInstFactory ();
+
+  SsaOpnd *opnd0 = opnd[0]->gen_insts_before (inst, irm);
+  SsaOpnd *opnd1 = opnd[1]->gen_insts_before (inst, irm);
+
+  Type *type = opnd0->getType ();
+  SsaTmpOpnd *result = opnd_manager.createSsaTmpOpnd (type);
+  Opcode opcode = get_opcode ();
+
+  switch (opcode)
+    {
+    case Op_TauDiv:
+    case Op_TauRem:
+      {
+        Modifier mod = Modifier (SignedOp) | Modifier (Strict_No);
+        SsaTmpOpnd *tau_safe = opnd_manager.createSsaTmpOpnd (type_manager.getTauType ());
+        Inst *tau_safe_inst = inst_factory.makeTauSafe (tau_safe);
+        Inst *new_inst;
+
+        if (opcode == Op_TauDiv)
+          new_inst = inst_factory.makeTauDiv (mod, result,
+                                              opnd0, opnd1, tau_safe);
+        else
+          new_inst = inst_factory.makeTauRem (mod, result,
+                                              opnd0, opnd1, tau_safe);
+
+        tau_safe_inst->insertBefore (inst);
+        new_inst->insertBefore (inst);
+
+        break;
+      }
+
+    default:
+      {
+        Modifier mod = (Modifier (Overflow_None)
+                        | Modifier (Exception_Never)
+                        | Modifier (Strict_No));
+        Inst *new_inst = inst_factory.makeInst (get_opcode (), mod,
+                                                type->tag,
+                                                result, opnd0, opnd1);
+        new_inst->insertBefore (inst);
+      }
+    }
+
+  return result;
+}
+
+std::ostream&
+operator<< (std::ostream &out, const Expr *e)
+{
+  if (!e)
+    out << "NULL";
+  else if (Integer *i = e->as_integer ())
+    out << i->value;
+  else if (Variable *v = e->as_variable ())
+    v->opnd->print (out);
+  else if (OpExpr *o = e->as_op_expr ())
+    {
+      Opcode opcode = o->get_opcode ();
+      const char *op;
+
+      switch (opcode)
+        {
+        case Op_Add:
+          op = "+";
+          break;
+
+        case Op_Sub:
+          op = "-";
+          break;
+
+        case Op_Mul:
+          op = "*";
+          break;
+
+        case Op_TauDiv:
+          op = "/";
+          break;
+
+        default:
+          op = "??";
+        }
+
+      out << '(';
+      out << o->opnd[0];
+      out << ' ' << op << ' ';
+      out << o->opnd[1];
+      out << ')';
+    }
+  else if (PolyChrec *c = e->as_poly_chrec ())
+    {
+      out << '{';
+      out << c->left;
+      out << ", +, ";
+      out << c->right;
+      out << "}_";
+      out << c->loop->getPreNum ();
+    }
+
+  return out;
+}
+
+SsaOpnd*
+strip_copies (SsaOpnd *var)
+{
+  Inst *inst = var->getInst ();
+
+  switch (inst->getOpcode ())
+    {
+    case Op_StVar:
+    case Op_LdVar:
+    case Op_Copy:
+      return strip_copies (inst->getSrc(0)->asSsaOpnd ());
+
+    default:
+      return var;
+    }
+}
+
+bool
+extract_base_and_index (SsaOpnd *var, SsaOpnd *&base, SsaOpnd *&index)
+{
+  var = strip_copies (var);
+
+  Inst *inst = var->getInst ();
+  Opcode opcode = inst->getOpcode ();
+
+  if (opcode == Op_AddScaledIndex)
+    {
+      SsaOpnd *op0 = strip_copies (inst->getSrc(0)->asSsaOpnd ());
+      SsaOpnd *op1 = strip_copies (inst->getSrc(1)->asSsaOpnd ());
+
+      if (op0->getInst()->getOpcode () == Op_AddScaledIndex)
+        // We don't allow addresses like (base + index) + index
+        return false;
+
+      base = op0;
+      index = op1;
+    }
+  else
+    {
+      base = var;
+      index = NULL;
+    }
+
+  return true;
+}
+
+}

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.cpp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.h?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.h (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.h Sun Jun  6 22:47:40 2010
@@ -0,0 +1,149 @@
+/* -*- mode: c++; indent-tabs-mode: nil; -*- */
+
+#ifndef _EXPR_H_
+#define _EXPR_H_
+
+#include "irmanager.h"
+#include "LoopTree.h"
+
+namespace Jitrino {
+
+class Expr;
+class Integer;
+class Variable;
+class OpExpr;
+class PolyChrec;
+
+// General expression type.
+
+class Expr
+{
+public:
+  Type* get_type () const { return type; }
+
+  Opcode get_opcode () const { return opcode; }
+
+  Integer* as_integer () const { return opcode == Op_LdConstant ? (Integer*)this : NULL; }
+
+  Variable* as_variable () const { return opcode == Op_LdVar ? (Variable*)this : NULL; }
+
+  OpExpr* as_op_expr () const { return opcode >= Op_Add && opcode <= Op_Cmp3 ? (OpExpr*)this : NULL;}
+
+  PolyChrec* as_poly_chrec () const { return opcode == Op_Branch ? (PolyChrec*)this : NULL; }
+
+  // Return true iff this is an integer zero.
+  bool int_zero_p () const;
+
+  // Return true iff this is an integer nonzero.
+  bool int_nonzero_p () const;
+
+  // Return true iff this is an integer one.
+  bool int_one_p () const;
+
+  // Generate instructions for computing this expression before INST.
+  // Return the SSA variable containing the final result.
+  virtual SsaOpnd* gen_insts_before (Inst *inst, IRManager &irm) = 0;
+
+  virtual ~Expr () {}
+
+protected:
+  Expr (Type *t, Opcode o) : type (t), opcode (o) {}
+
+private:
+  Type *type;
+  const Opcode opcode;
+};
+
+// Integer constants of an expression tree (leaf nodes).
+// Reuse the opcode Op_LdConstant to represent this class.
+
+class Integer : public Expr
+{
+public:
+  Integer (Type *t, I_32 v) : Expr (t, Op_LdConstant), value (v) {}
+
+  virtual SsaOpnd* gen_insts_before (Inst *inst, IRManager &irm);
+
+public:
+  I_32 value;
+};
+
+// Variable of an expression tree (leaf nodes).
+// Reuse the opcode Op_LdVar to represent this class.
+
+class Variable : public Expr
+{
+public:
+  Variable (Type *t, SsaOpnd *o) : Expr (t, Op_LdVar), opnd (o) {}
+
+  virtual SsaOpnd* gen_insts_before (Inst *inst, IRManager &irm);
+
+public:
+  SsaOpnd *opnd;
+};
+
+// Expression with an operator (internal nodes of an expression tree).
+// Reuse the opcodes from Op_Add through Op_Cmp3 to represent this class.
+
+class OpExpr : public Expr
+{
+public:
+  OpExpr (Type *t, Opcode op, Expr *e0, Expr *e1 = NULL) : Expr (t, op)
+  {
+    assert (op >= Op_Add && op <= Op_Cmp3);
+
+    opnd[0] = e0; opnd[1] = e1;
+  }
+
+  virtual SsaOpnd* gen_insts_before (Inst *inst, IRManager &irm);
+
+public:
+  Expr *opnd[2];
+};
+
+// Polynomial chain of recurrences.
+// Reuse the opcode Op_Branch to represent this class.
+
+class PolyChrec : public Expr
+{
+public:
+  PolyChrec (Type *t, Expr *l, Expr *r, LoopNode *p)
+    : Expr (t, Op_Branch), left (l), right (r), loop (p)
+  {
+  }
+
+  virtual SsaOpnd* gen_insts_before (Inst *inst, IRManager &irm)
+  {
+    assert (0);
+    return NULL;
+  }
+
+public:
+  Expr *left;
+  Expr *right;
+  // The loop this chrec is with respect to.
+  LoopNode *loop;
+};
+
+std::ostream& operator<< (std::ostream &out, const Expr *e);
+
+//====================================================================
+//       The following are some frequently used utilities.
+//====================================================================
+
+// Strip copy instructions starting from VAR's definition instruction.
+
+extern SsaOpnd* strip_copies (SsaOpnd *var);
+
+// Extract base and index parts from array address (operand of ld/stind) VAR.
+// Return false if the address is not in the normal form: base or base + index.
+// For example, (base + index) + index is not normal.  The reason for checking
+// this is that we want to try to ensure a property:
+// base1 + index1 != base2 + index2 if base1 != base2.  With this,
+// base1[i] will never alias to base2[j] as long as i != j.
+
+extern bool extract_base_and_index (SsaOpnd *var, SsaOpnd *&base, SsaOpnd *&index);
+
+}
+
+#endif

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/expr.h
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.cpp?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.cpp (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.cpp Sun Jun  6 22:47:40 2010
@@ -0,0 +1,109 @@
+/* -*- mode: c++; indent-tabs-mode: nil; -*- */
+
+#include "loop-info.h"
+#include "scalar-evolution.h"
+
+namespace Jitrino {
+
+Edge*
+LoopInfo::find_single_exit ()
+{
+  Edge *exit_edge = single_exit (loop);
+
+  if (!exit_edge)
+    return NULL;
+
+  single_exit_edge = exit_edge;
+
+  Node *exit_node = exit_edge->getSourceNode();
+  Inst *cond_inst = (Inst*)exit_node->getLastInst ();
+
+  while (cond_inst->getOpcode () != Op_Branch)
+    {
+      cond_inst = cond_inst->getPrevInst ();
+
+      if (!cond_inst)
+        return NULL;
+    }
+
+  exit_branch_inst = cond_inst->asBranchInst ();
+
+  const Edges &out_edges = exit_node->getOutEdges ();
+  assert (out_edges.size () == 2);
+  continue_edge = (out_edges[0] == exit_edge ? out_edges[1] : out_edges[0]);
+
+  return exit_edge;
+}
+
+Expr*
+LoopInfo::set_iteration_number (ScalarEvolution &scev_analyzer)
+{
+  return iteration_number = scev_analyzer.number_of_iterations (*this);
+}
+
+Edge*
+LoopInfo::get_single_latch_edge () const
+{
+  Node *header = loop->getHeader ();
+  const Edges &in_edges = header->getInEdges ();
+
+  assert (in_edges.size () == 2);
+
+  return in_edges[(loop->inLoop (in_edges[0]->getSourceNode ())
+                   ? 0 : 1)];
+}
+
+Edge*
+LoopInfo::get_single_preheader_edge () const
+{
+  Node *header = loop->getHeader ();
+  const Edges &in_edges = header->getInEdges ();
+
+  assert (in_edges.size () == 2);
+
+  return in_edges[(loop->inLoop (in_edges[0]->getSourceNode ())
+                   ? 1 : 0)];
+}
+
+Node*
+LoopInfo::get_single_latch_node () const
+{
+  return get_single_latch_edge()->getSourceNode ();
+}
+
+Node*
+LoopInfo::get_single_preheader_node () const
+{
+  return get_single_preheader_edge()->getSourceNode ();
+}
+
+// Return the exit edge of LOOP if it's the only exit edge of LOOP.
+// Otherwise, return NULL.  This static method should probably be
+// defined in the LoopNode class.
+
+Edge*
+LoopInfo::single_exit (LoopNode *loop)
+{
+  const Nodes &nodes = loop->getNodesInLoop ();
+  Edge *exit_edge = NULL;
+
+  for (unsigned i = 0; i < nodes.size (); i++)
+    {
+      const Edges &edges = nodes[i]->getOutEdges ();
+
+      for (unsigned j = 0; j < edges.size (); j++)
+        if (!edges[j]->getTargetNode()->isDispatchNode ()
+            && loop->isLoopExit (edges[j]))
+          {
+            if (exit_edge)
+              // There is more than one exit edge of LOOP.
+              return NULL;
+
+            exit_edge = edges[j];
+          }
+    }
+
+  return exit_edge;
+}
+
+}

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.cpp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.h?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.h (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.h Sun Jun  6 22:47:40 2010
@@ -0,0 +1,76 @@
+/* -*- mode: c++; indent-tabs-mode: nil; -*- */
+
+#ifndef _LOOP_INFO_H_
+#define _LOOP_INFO_H_
+
+#include "Loop.h"
+#include "expr.h"
+
+namespace Jitrino {
+
+class ScalarEvolution;
+
+// Information of a loop in loop nest.
+
+class LoopInfo
+{
+public:
+  LoopInfo (LoopNode *l)
+    : loop (l), single_exit_edge (NULL), continue_edge (NULL),
+      exit_branch_inst (NULL), iteration_number (NULL) {}
+
+  LoopNode* get_loop () const { return loop; }
+
+  Edge* get_single_exit_edge () const { return single_exit_edge; }
+
+  Edge* get_continue_edge () const { return continue_edge; }
+
+  BranchInst* get_exit_branch_inst () const { return exit_branch_inst; }
+
+  Expr* get_iteration_number () const { return iteration_number; }
+
+  // Set SINGLE_EXIT_EDGE and EXIT_BRANCH_INST for LOOP and return the
+  // SINGLE_EXIT_EDGE.
+  Edge* find_single_exit ();
+
+  // Compute iteration number of LOOP with SCEV_ANALYZER and save the
+  // result to ITERATION_NUMBER and return it.
+  Expr* set_iteration_number (ScalarEvolution &scev_analyzer);
+
+  // Return the edge from the single latch to the header of LOOP.
+  Edge* get_single_latch_edge () const;
+
+  // Return the edge from the single preheader to the header of LOOP.
+  Edge* get_single_preheader_edge () const;
+
+  // Return the single latch node, i.e. the only node in LOOP that is
+  // the predecessor of header of LOOP.
+  Node* get_single_latch_node () const;
+
+  // Return the single preheader node of LOOP.
+  Node* get_single_preheader_node () const;
+
+private:
+  static Edge* single_exit (LoopNode *);
+
+private:
+  LoopNode *loop;
+
+  // The single exit edge of LOOP.
+  Edge *single_exit_edge;
+
+  // The edge of the continue branch from the exit node.
+  Edge *continue_edge;
+
+  // The single exit branch instruction of LOOP.
+  BranchInst *exit_branch_inst;
+
+  // The number of iterations of LOOP.
+  Expr *iteration_number;
+};
+
+typedef std::vector<LoopInfo> LoopInfos;
+
+}
+
+#endif

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/loop-info.h
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.cpp?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.cpp (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.cpp Sun Jun  6 22:47:40 2010
@@ -0,0 +1,1143 @@
+/* -*- mode: c++; indent-tabs-mode: nil; -*- */
+
+#include <algorithm>
+#include "scalar-evolution.h"
+
+namespace Jitrino {
+
+Expr*
+ScalarEvolution::analyze_scev (SsaOpnd *var, LoopNode *loop)
+{
+  VarLoop var_loop (var, loop);
+  Expr *result = cached_scev.lookup (&var_loop);
+
+  if (!result)
+    // The <VAR, LOOP> pair has not bee analyzed, do it now.
+    {
+      result = analyze_scev_1 (var, loop);
+      cached_scev.insert (new (memory) VarLoop (var, loop), result);
+    }
+
+  return result;
+}
+
+// Helper function for analyze_scev
+
+Expr*
+ScalarEvolution::analyze_scev_1 (SsaOpnd *var, LoopNode *loop)
+{
+  if (!var->getType()->isInteger ())
+    return NULL;
+
+  var = strip_copies (var);
+
+  Inst* inst = var->getInst ();
+  Opcode opcode = inst->getOpcode ();
+
+  // Return the constant in spite of whether it's defined in LOOP.
+  if (opcode == Op_LdConstant)
+    return new (memory) Integer (var->getType (), inst->asConstInst()->getValue().i4);
+
+  // If VAR is defined outside LOOP and is not a result of multiply
+  // instruction, return the symbolic form (parameter).  Allowing
+  // expansion of multiply instructions may make GCD more accurate.
+  if (!loop->inLoop (inst->getNode ()) && !is_mul_inst (inst))
+    return new (memory) Variable (var->getType (), var);
+
+  switch (opcode)
+    {
+    case Op_Phi:
+      if (loop->getHeader () == inst->getNode ())
+        return analyze_scev_for_loop_phi (inst, loop);
+
+      // TODO: Ignore other complex cases for now.
+      return NULL;
+
+    case Op_Add:
+    case Op_Sub:
+    case Op_Mul:
+    case Op_Shl:
+      {
+        SsaOpnd *op1 = inst->getSrc(0)->asSsaOpnd ();
+        SsaOpnd *op2 = inst->getSrc(1)->asSsaOpnd ();
+        Expr *ev1 = analyze_scev (op1, loop);
+        Expr *ev2 = ev1 ? analyze_scev (op2, loop) : NULL;
+
+        if (!ev2)
+          return NULL;
+
+        if (opcode == Op_Shl)
+          {
+            if (Integer *itmp = ev2->as_integer ())
+              // Convert constant left-shift to multiply.
+              {
+                opcode = Op_Mul;
+                ev2 = new (memory) Integer (ev2->get_type (), 1 << itmp->value);
+              }
+            else
+              // We don't support non-constant shifts.
+              return NULL;
+          }
+
+        return fold_build (opcode, ev1, ev2);
+      }
+
+    case Op_Shladd:
+      {
+        SsaOpnd *op1 = inst->getSrc(0)->asSsaOpnd ();
+        SsaOpnd *op2 = inst->getSrc(1)->asSsaOpnd ();
+        SsaOpnd *op3 = inst->getSrc(2)->asSsaOpnd ();
+        Expr *ev1 = analyze_scev (op1, loop);
+        Expr *ev2 = ev1 ? analyze_scev (op2, loop) : NULL;
+        Integer *itmp = ev2 ? ev2->as_integer () : NULL;
+        Expr *ev3 = itmp ? analyze_scev (op3, loop) : NULL;
+
+        if (!ev3)
+          return NULL;
+
+        return fold_build (Op_Add,
+                           fold_build (Op_Mul, ev1,
+                                       new (memory) Integer (itmp->get_type (),
+                                                             1 << itmp->value)),
+                           ev3);
+      }
+
+    default:
+      return NULL;
+    }
+}
+
+Expr*
+ScalarEvolution::number_of_iterations (LoopInfo &loop_info)
+{
+  LoopNode *loop = loop_info.get_loop ();
+  Edge *exit_edge = loop_info.find_single_exit ();
+  BranchInst *cond_inst = loop_info.get_exit_branch_inst ();
+
+  if (!cond_inst)
+    return NULL;
+
+  SsaOpnd *op0 = cond_inst->getSrc(0)->asSsaOpnd ();
+  Expr *scev0 = analyze_scev (op0, loop);
+  Expr *scev1;
+  ComparisonModifier cond_code = cond_inst->getComparisonModifier ();
+
+  // Convert the two unary operations to standard binary operations.
+  // Why use these two unary operations in IR?  They're not convenient.
+  switch (cond_code)
+    {
+    case Cmp_Zero:
+      cond_code = Cmp_EQ;
+      scev1 = int_zero;
+      break;
+
+    case Cmp_NonZero:
+      cond_code = Cmp_NE_Un;
+      scev1 = int_zero;
+      break;
+
+    default:
+      {
+        SsaOpnd *op1 = cond_inst->getSrc(1)->asSsaOpnd ();
+        scev1 = analyze_scev (op1, loop);
+      }
+    }
+
+  if (!scev0 || !scev1
+      || (bool)scev0->as_poly_chrec () == (bool)scev1->as_poly_chrec ())
+    // It's too complex, just give up.
+    return NULL;
+
+  PolyChrec *chrec = (scev0->as_poly_chrec () ? scev0 : scev1)->as_poly_chrec ();
+  Expr *first_exit_value;
+
+  if (cond_inst->getTargetLabel ()
+      != exit_edge->getTargetNode()->getFirstInst ())
+    // When condition is true, continue to run the loop.
+    switch (cond_code)
+      {
+      case Cmp_NE_Un:
+      case Cmp_GT:
+      case Cmp_GT_Un:
+        first_exit_value = scev0->as_poly_chrec () ? scev1 : scev0;
+        break;
+
+      case Cmp_GTE:
+      case Cmp_GTE_Un:
+        first_exit_value = (scev0->as_poly_chrec ()
+                            ? fold_build (Op_Sub, scev1, int_one)
+                            : fold_build (Op_Add, scev0, int_one));
+        break;
+
+      default:
+        return NULL;
+      }
+  else
+    // When condition is true, exit the loop.
+    switch (cond_code)
+      {
+      case Cmp_GT:
+      case Cmp_GT_Un:
+        first_exit_value = (scev0->as_poly_chrec ()
+                            ? fold_build (Op_Add, scev1, int_one)
+                            : fold_build (Op_Sub, scev0, int_one));
+        break;
+
+      case Cmp_EQ:
+      case Cmp_GTE:
+      case Cmp_GTE_Un:
+        first_exit_value = scev0->as_poly_chrec () ? scev1 : scev0;
+        break;
+
+      default:
+        return NULL;
+      }
+
+  // TODO: The Op_TauDiv should be something like Op_CeilDiv, which
+  // denotes a ceiling division, i.e. the division for integer result
+  // that rounds the quotient toward infinity.
+  return fold_build (Op_TauDiv,
+                     fold_build (Op_Sub, first_exit_value, chrec->left),
+                     chrec->right);
+}
+
+bool
+ScalarEvolution::is_mul_inst (Inst *inst)
+{
+  switch (inst->getOpcode ())
+    {
+    case Op_Mul:
+      return true;
+
+    case Op_Shl:
+      {
+        SsaOpnd *op1 = strip_copies (inst->getSrc(1)->asSsaOpnd ());
+
+        return op1->getInst()->getOpcode () == Op_LdConstant;
+      }
+
+    case Op_Shladd:
+      {
+        SsaOpnd *op1 = strip_copies (inst->getSrc(1)->asSsaOpnd ());
+        SsaOpnd *op2 = strip_copies (inst->getSrc(2)->asSsaOpnd ());
+
+        return (op1->getInst()->getOpcode () == Op_LdConstant
+                && op2->getInst()->getOpcode () == Op_LdConstant
+                && op2->getInst()->asConstInst()->getValue().i4 == 0);
+      }
+
+    default:
+      return false;
+    }
+}
+
+Expr*
+ScalarEvolution::instantiate_scev (Expr *scev, LoopNode *use_loop, LoopNode *wrto_loop)
+{
+  if (!scev)
+    return scev;
+
+  Opcode opcode = scev->get_opcode ();
+
+  switch (opcode)
+    {
+    case Op_LdConstant:
+      return scev;
+
+    case Op_LdVar:
+      {
+        Variable *var = scev->as_variable ();
+        Inst* inst = var->opnd->getInst ();
+
+        // If VAR is defined outside WRTO_LOOP, leave it as symbolic form.
+        if (!wrto_loop->inLoop (inst->getNode ()))
+          return var;
+
+        LoopNode *def_loop = loop_tree->getLoopNode (inst->getNode (), false);
+        LoopNode *common_loop = loop_tree->findCommonLoop (use_loop, def_loop);
+
+        scev = analyze_scev (var->opnd, common_loop);
+
+        if (scev)
+          scev = instantiate_scev (scev, use_loop, wrto_loop);
+
+        return scev;
+      }
+
+    case Op_Branch:
+      {
+        PolyChrec *chrec = scev->as_poly_chrec ();
+        Expr *left = instantiate_scev (chrec->left, use_loop, wrto_loop);
+        Expr *right = left ? instantiate_scev (chrec->right, use_loop, wrto_loop) : NULL;
+
+        return (!right ? NULL
+                : (left == chrec->left && right == chrec->right ? chrec
+                   : fold_build_poly_chrec (chrec->get_type (), left, right, chrec->loop)));
+      }
+
+    case Op_Add:
+    case Op_Sub:
+    case Op_Mul:
+      {
+        OpExpr *expr = scev->as_op_expr ();
+        Expr *op0 = instantiate_scev (expr->opnd[0], use_loop, wrto_loop);
+        Expr *op1 = op0 ? instantiate_scev (expr->opnd[1], use_loop, wrto_loop) : NULL;
+
+        return (!op1 ? NULL
+                : (op0 == expr->opnd[0] && op1 == expr->opnd[1] ? expr
+                   : fold_build (opcode, op0, op1)));
+      }
+
+    default:
+      return NULL;
+    }
+}
+
+// Return true if PHI is a loop phi node.
+
+bool
+ScalarEvolution::loop_phi_node_p (Inst *phi)
+{
+  assert (phi->getOpcode () == Op_Phi);
+
+  return loop_tree->isLoopHeader (phi->getNode ());
+}
+
+// INST must be a loop-phi node of LOOP.
+
+Expr*
+ScalarEvolution::analyze_scev_for_loop_phi (Inst *phi, LoopNode *loop)
+{
+  assert (loop_phi_node_p (phi));
+
+  Expr *init = NULL;
+
+  // Find the initial value of PHI in LOOP.
+  for (unsigned i = 0; i < phi->getNumSrcOperands (); i++)
+    {
+      SsaOpnd *arg = strip_copies (phi->getSrc(i)->asSsaOpnd ());
+      Inst *inst = arg->getInst ();
+
+      if (loop->inLoop (inst->getNode ()))
+        continue;
+
+      if (init)
+        // TODO: We don't support multi-entries for now.
+        return NULL;
+      else
+        // The ARG must be loop-invariant.  compute_step certainly
+        // can handle this simple case, so we just use it.
+        init = compute_step (arg, phi, loop);
+    }
+
+  // Every loop must have at least one entry.
+  assert (init);
+
+  Expr *ev_fn = NULL;
+
+  // Compute step part of the evolution of PHI in LOOP.
+  for (unsigned i = 0; i < phi->getNumSrcOperands (); i++)
+    {
+      SsaOpnd *arg = phi->getSrc(i)->asSsaOpnd ();
+
+      if (!loop->inLoop (arg->getInst()->getNode ()))
+        continue;
+
+      if (ev_fn)
+        // TODO: We don't support multi-backedges for now.
+        return NULL;
+      else
+        {
+          ev_fn = compute_step (arg, phi, loop);
+
+          if (!ev_fn || !ev_fn->as_poly_chrec ())
+            // Return dont-know since step is not a polynomial chrec.
+            return NULL;
+          else
+            ev_fn->as_poly_chrec()->left = init;
+        }
+    }
+
+  return ev_fn;
+}
+
+// Compute step part for loop-phi node PHI of LOOP by tracing SSA flows
+// starting from one of its argument ARG to itself.  It may be another
+// polynomial chrec of LOOP, but currently we don't support higher degree
+// polynomial, i.e. only loop-invariant steps are allowed for now.
+
+Expr*
+ScalarEvolution::compute_step (SsaOpnd *arg, Inst *start_phi, LoopNode *loop)
+{
+  arg = strip_copies (arg);
+
+  Inst* inst = arg->getInst ();
+  Opcode opcode = inst->getOpcode ();
+
+  // Return the constant in spite of whether it's defined in LOOP.
+  if (opcode == Op_LdConstant)
+    return new (memory) Integer (arg->getType (), inst->asConstInst()->getValue().i4);
+
+  // If ARG is defined outside LOOP and is not a result of multiply
+  // instruction, return the symbolic form (parameter).  Allowing
+  // expansion of multiply instructions may make GCD more accurate.
+  if (!loop->inLoop (inst->getNode ()) && !is_mul_inst (inst))
+    return new (memory) Variable (arg->getType (), arg);
+
+  switch (opcode)
+    {
+    case Op_Phi:
+      if (inst == start_phi)
+        // Reach the start phi, return the chrec with step zero.
+        // Don't use fold_build_poly_chrec here as we need the PolyChrec
+        // object to denote that we have reached the start phi.
+        return new (memory) PolyChrec (arg->getType (), NULL, int_zero, loop);
+
+      if (!loop_phi_node_p (inst))
+        // TODO: Ignore conditional phi nodes for now.
+        return NULL;
+
+      // TODO: Ignore all complex cases for now, including when INST is
+      // a loop-phi-node of LOOP and of inner loop of LOOP.
+      return NULL;
+
+    case Op_Add:
+    case Op_Sub:
+    case Op_Mul:
+    case Op_Shl:
+    case Op_Shladd:
+      {
+        SsaOpnd *op1 = inst->getSrc(0)->asSsaOpnd ();
+        SsaOpnd *op2 = inst->getSrc(1)->asSsaOpnd ();
+        Expr *ev1 = compute_step (op1, start_phi, loop);
+        Expr *ev2 = ev1 ? compute_step (op2, start_phi, loop) : NULL;
+
+        if (!ev2)
+          return NULL;
+
+        // Is it necessary to use the trinary instruction Op_Shladd?
+        // It complicates problems and leads to ugly code as follows.
+        if (opcode == Op_Shl || opcode == Op_Shladd)
+          {
+            Integer *i2 = ev2->as_integer ();
+
+            if (!i2)
+              return NULL;
+
+            if (opcode == Op_Shl)
+              // If shift a constant, convert it to multiply.
+              {
+                ev2 = new (memory) Integer (i2->get_type (), 1 << i2->value);
+                opcode = Op_Mul;
+              }
+            else
+              {
+                SsaOpnd *op3 = inst->getSrc(2)->asSsaOpnd ();
+                Expr *ev3 = compute_step (op3, start_phi, loop);
+                Integer *i3 = ev3 ? ev3->as_integer () : NULL;
+
+                if (!i3)
+                  return NULL;
+
+                if (i2->value == 0)
+                  // Shift zero bit, convert the shift-add to add.
+                  {
+                    ev2 = ev3;
+                    opcode = Op_Add;
+                  }
+                else if (i3->value == 0)
+                  // Add zero, convert the shift-add to multiply.
+                  {
+                    ev2 = new (memory) Integer (i2->get_type (), 1 << i2->value);
+                    opcode = Op_Mul;
+                  }
+                else
+                  // We don't support non-trivial trinary operations.
+                  return NULL;
+              }
+          }
+
+        switch (((bool)ev1->as_poly_chrec () << 1) + (bool)ev2->as_poly_chrec ())
+          {
+          case 0:
+            return fold_build (opcode, ev1, ev2);
+
+          case 1:
+            if (opcode == Op_Sub)
+              return NULL;
+
+            std::swap (ev1, ev2);
+
+          case 2:
+            {
+              if (opcode == Op_Mul)
+                return NULL;
+
+              PolyChrec *chrec = ev1->as_poly_chrec();
+              chrec->right = fold_build (opcode, chrec->right, ev2);
+              return chrec;
+            }
+
+          case 3:
+            // Can't be represented by a polynomial chrec.
+            return NULL;
+          }
+      }
+
+    default:
+      return NULL;
+    }
+}
+
+Expr*
+ScalarEvolution::fold (Opcode opcode, Expr *e1, Expr *e2)
+{
+  if (PolyChrec *chrec1 = e1->as_poly_chrec ())
+    {
+      if (PolyChrec *chrec2 = e2->as_poly_chrec ())
+        {
+          if (chrec1->loop == chrec2->loop)
+            switch (opcode)
+              {
+              case Op_Add:
+              case Op_Sub:
+                return fold_build_poly_chrec (e1->get_type (),
+                                              fold_build (opcode, chrec1->left, chrec2->left),
+                                              fold_build (opcode, chrec1->right, chrec2->right),
+                                              chrec1->loop);
+              default:
+                ;
+              }
+          else if (loop_tree->isAncestor (chrec1->loop, chrec2->loop))
+            return fold_build_poly_chrec (e1->get_type (),
+                                          fold_build (opcode, chrec1, chrec2->left),
+                                          chrec2->right,
+                                          chrec2->loop);
+          else if (loop_tree->isAncestor (chrec2->loop, chrec1->loop))
+            return fold_build_poly_chrec (e1->get_type (),
+                                          fold_build (opcode, chrec1->left, chrec2),
+                                          chrec1->right,
+                                          chrec1->loop);
+        }
+      else
+        switch (opcode)
+          {
+          case Op_Add:
+          case Op_Sub:
+            return fold_build_poly_chrec (e1->get_type (),
+                                          fold_build (opcode, chrec1->left, e2),
+                                          chrec1->right, chrec1->loop);
+
+          case Op_Mul:
+            return fold_build_poly_chrec (e1->get_type (),
+                                          fold_build (opcode, chrec1->left, e2),
+                                          fold_build (opcode, chrec1->right, e2),
+                                          chrec1->loop);
+
+          default:
+            ;
+          }
+
+      return NULL;
+    }
+  else if (PolyChrec *chrec2 = e2->as_poly_chrec ())
+    {
+      switch (opcode)
+        {
+        case Op_Add:
+          return fold_build_poly_chrec (e1->get_type (),
+                                        fold_build (opcode, e1, chrec2->left),
+                                        chrec2->right, chrec2->loop);
+
+        case Op_Mul:
+          return fold_build_poly_chrec (e1->get_type (),
+                                        fold_build (opcode, e1, chrec2->left),
+                                        fold_build (opcode, e1, chrec2->right),
+                                        chrec2->loop);
+
+        case Op_Sub:
+          return fold_build_poly_chrec (e1->get_type (),
+                                        fold_build (opcode, e1, chrec2->left),
+                                        fold_build (opcode, int_zero, chrec2->right),
+                                        chrec2->loop);
+
+        default:
+          ;
+        }
+
+      return NULL;
+    }
+  else if (Integer *i1 = e1->as_integer ())
+    {
+      // 0 + e2 => e2, 1 * e2 => e2
+      if ((opcode == Op_Add && i1->value == 0)
+          || (opcode == Op_Mul && i1->value == 1))
+        return e2;
+
+      // 0 * e2 => 0
+      if (opcode == Op_Mul && i1->value == 0)
+        return i1;
+
+      if (Integer *i2 = e2->as_integer ())
+        switch (opcode)
+          {
+          case Op_Add:
+            return new (memory) Integer (i1->get_type (), i1->value + i2->value);
+
+          case Op_Sub:
+            return new (memory) Integer (i1->get_type (), i1->value - i2->value);
+
+          case Op_Mul:
+            return new (memory) Integer (i1->get_type (), i1->value * i2->value);
+
+          case Op_TauDiv:
+            // TODO: We don't handle the floor and ceiling problem for now.
+            // Rather, we only process their common case and leave other cases
+            // unchanged.
+            if (i1->value % i2->value == 0)
+              return new (memory) Integer (i1->get_type (), i1->value / i2->value);
+            else
+              return NULL;
+
+          default:
+            ;
+          }
+    }
+  else if (Integer *i2 = e2->as_integer ())
+    {
+      // e1 + 0 => e1, e1 * 1 => e1, e1 / 1 => e1
+      if (((opcode == Op_Add || opcode == Op_Sub) && i2->value == 0)
+          || ((opcode == Op_Mul || opcode == Op_TauDiv) && i2->value == 1))
+        return e1;
+
+      // e1 * 0 => 0
+      if (opcode == Op_Mul && i2->value == 0)
+        return i2;
+    }
+
+  return fold_polynomial (opcode, e1, e2);
+}
+
+// Fold two polynomials into such form c + a * b + d * e + ...
+// Return the folded expression if successful, otherwise return NULL.
+
+Expr*
+ScalarEvolution::fold_polynomial (Opcode opcode, Expr *e1, Expr *e2)
+{
+  Opcode code1 = e1->get_opcode ();
+  Opcode code2 = e2->get_opcode ();
+
+  switch (opcode)
+    {
+    case Op_Add:
+    case Op_Sub:
+      // If the latter is an add or sub, the folding always succeeds.
+      if (code2 == Op_Add || code2 == Op_Sub)
+        {
+          OpExpr *oe2 = e2->as_op_expr ();
+
+          // p1 + (p2 + t) => (p1 + p2) + t
+          return fold_build (code2 == opcode ? Op_Add : Op_Sub,
+                             fold_build (opcode, e1, oe2->opnd[0]),
+                             oe2->opnd[1]);
+        }
+
+      // Now, the latter is a single term.
+      if (code1 == Op_Add || code1 == Op_Sub)
+        {
+          OpExpr *oe1 = e1->as_op_expr ();
+
+          // If folding (p1 + t2) succeeds, (p1 + t1) + t2 => (p1 + t2) + t1
+          if (Expr *left = fold (opcode, oe1->opnd[0], e2))
+            return fold_build (code1, left, oe1->opnd[1]);
+          // If folding (t1 + t2) succeeds, (p1 + t1) + t2 => p1 + (t1 + t2)
+          else if (Expr *right = fold (code1 == opcode ? Op_Add : Op_Sub,
+                                       oe1->opnd[1], e2))
+            return fold_build (code1, oe1->opnd[0], right);
+          // Otherwise, t2 cannot be folded into e1 and the folding fails.
+          else
+            return NULL;
+        }
+
+      // Now, both e1 and e2 are terms.
+      return term_add (opcode, e1, e2);
+
+    case Op_Mul:
+      // If the latter is an add or sub, folding always succeeds.
+      if (code2 == Op_Add || code2 == Op_Sub)
+        {
+          OpExpr *oe2 = e2->as_op_expr ();
+
+          // p1 * (p2 + t) => (p1 * p2) + (p1 * t)
+          return fold_build (code2,
+                             fold_build (Op_Mul, e1, oe2->opnd[0]),
+                             fold_build (Op_Mul, e1, oe2->opnd[1]));
+        }
+
+      // Now, the latter is a term.
+      if (code1 == Op_Add || code1 == Op_Sub)
+        {
+          OpExpr *oe1 = e1->as_op_expr ();
+
+          // (p1 + t1) * t2 => p1 * t2 + t1 * t2
+          return fold_build (code1,
+                             fold_build (Op_Mul, oe1->opnd[0], e2),
+                             fold_build (Op_Mul, oe1->opnd[1], e2));
+        }
+
+      // Now, both are terms.
+      return term_mul (e1, e2);
+
+    case Op_TauDiv:
+      if (!e2->as_integer ())
+        // TODO: We only support constant divisor for now.
+        return NULL;
+
+      if (code1 == Op_Add || code1 == Op_Sub)
+        {
+          OpExpr *oe1 = e1->as_op_expr ();
+
+          // (p1 + t1) / c => p1 / c + t1 / c
+          Expr *opnd0 = fold (Op_TauDiv, oe1->opnd[0], e2);
+          Expr *opnd1 = opnd0 ? fold (Op_TauDiv, oe1->opnd[1], e2) : NULL;
+
+          // Succeeds only when both sub foldings succeed.
+          return opnd1 ? build (code1, opnd0, opnd1) : NULL;
+        }
+
+      // Now, e1 is a term.
+      return term_div (e1, e2);
+
+    default:
+      return NULL;
+    }
+}
+
+// Return true iff E1 and E2 are both Variable and have the same opnd.
+
+bool
+ScalarEvolution::same_opnd_p (Expr *e1, Expr *e2)
+{
+  Variable *v1, *v2;
+
+  return ((v1 = e1->as_variable ()) && (v2 = e2->as_variable ())
+          && v1->opnd == v2->opnd);
+}
+
+// Try to add or sub two terms T1 and T2 into one term.  If the result
+// is one term, return it, otherwise return NULL.  For example,
+// term_add (Op_add, a * b, 2 * a * b) returns 3 * a * b,
+// but term_add (Op_Add, 2 * a * b, 3 * a * c) returns NULL.
+// We assume factors in terms have been sorted.
+
+Expr*
+ScalarEvolution::term_add (Opcode opcode, Expr *t1, Expr *t2)
+{
+  assert (opcode == Op_Add || opcode == Op_Sub);
+
+  if (OpExpr *mul1 = t1->as_op_expr ())
+    {
+      if (t1->get_opcode () != Op_Mul)
+        // Only fold multiply operations
+        return NULL;
+
+      if (OpExpr *mul2 = t2->as_op_expr ())
+        {
+          if (t2->get_opcode () != Op_Mul)
+            // Only fold multiply operations
+            return NULL;
+
+          if (!same_opnd_p (mul1->opnd[1], mul2->opnd[1]))
+            return NULL;
+
+          // If folding (t1 + t2) succeeds, (t1 * a) + (t2 * a) => (t1 + t2) * a.
+          if (Expr *left = fold (opcode, mul1->opnd[0], mul2->opnd[0]))
+            return fold_build (Op_Mul, left, mul1->opnd[1]);
+        }
+      else if (same_opnd_p (mul1->opnd[1], t2))
+        {
+          // If folding (t1 + 1) succeeds, (t1 * a) + a => (t1 + 1) * a.
+          if (Expr *left = fold (opcode, mul1->opnd[0], int_one))
+            return fold_build (Op_Mul, left, mul1->opnd[1]);
+        }
+    }
+  else if (OpExpr *mul2 = t2->as_op_expr ())
+    {
+      if (t2->get_opcode () != Op_Mul)
+        // Only fold multiply operations
+        return NULL;
+
+      if (same_opnd_p (t1, mul2->opnd[1]))
+        {
+          // If folding (1 + t2) succeeds, a + (t2 * a) => (1 + t2) * a.
+          if (Expr *left = fold (opcode, int_one, mul2->opnd[0]))
+            return fold_build (Op_Mul, left, mul2->opnd[1]);
+        }
+    }
+  else if (same_opnd_p (t1, t2))
+    return fold_build (Op_Mul, fold (opcode, int_one, int_one), t1);
+
+  return NULL;
+}
+
+// Return true iff factor F1 should appear befor factor F2 in a
+// normalized term.
+
+bool
+ScalarEvolution::factor_precede_p (Expr *f1, Expr *f2)
+{
+  if (f1->as_integer () && !f2->as_integer ())
+    // Constant should be in the front of a term.
+    return true;
+
+  if (Variable *v1 = f1->as_variable ())
+    if (Variable *v2 = f2->as_variable ())
+      if (v1->opnd->getId () < v2->opnd->getId ())
+        // Sort variables by their ID order.
+        return true;
+
+  return false;
+}
+
+// Multiply two terms into one term and return it.  Non-one constant
+// always appears in the front of the result term, and variables are
+// sorted in the order of their operand ID.
+
+Expr*
+ScalarEvolution::term_mul (Expr *t1, Expr *t2)
+{
+  if (t1->get_opcode () == Op_TauDiv)
+    {
+      OpExpr *div1 = t1->as_op_expr();
+
+      if (div1->opnd[1] == t2)
+        // t11 / t12 * t12 => t11
+        return div1->opnd[0];
+    }
+
+  if (t2->get_opcode () == Op_TauDiv)
+    {
+      OpExpr *div2 = t2->as_op_expr();
+
+      if (div2->opnd[1] == t1)
+        // t22 * (t21 / t22) => t21
+        return div2->opnd[0];
+    }
+
+  // If t2 is a multiply expression, always perform the folding
+  // t1 * (t21 * t22) => (t1 * t21) * t22
+  if (OpExpr *mul2 = t2->as_op_expr ())
+    {
+      if (t2->get_opcode () != Op_Mul)
+        // Only fold multiply operations
+        return NULL;
+
+      return fold_build (Op_Mul,
+                         fold_build (Op_Mul, t1, mul2->opnd[0]),
+                         mul2->opnd[1]);
+    }
+
+  // Now t2 is a single integer or variable.
+  if (OpExpr *mul1 = t1->as_op_expr ())
+    {
+      if (t1->get_opcode () != Op_Mul)
+        // Only fold multiply operations
+        return NULL;
+
+      if (!factor_precede_p (t2, mul1->opnd[1]))
+        // It has been in the ordered form, nothing needs to change.
+        return NULL;
+      else
+        // Otherwise, t2 shoud precede mul1->opnd[1].  Perform
+        // the folding (t11 * v1) * t2 => (t11 * t2) * v1
+        return build (Op_Mul, fold_build (Op_Mul, mul1->opnd[0], t2),
+                      mul1->opnd[1]);
+    }
+
+  // Now, t1 and t2 are either an integer or a variable.
+  if (!factor_precede_p (t2, t1))
+    // t2 shouldn't precede t1, the folding fails.
+    return NULL;
+  else
+    // Otherwise, exchange them.
+    return build (Op_Mul, t2, t1);
+}
+
+// Fold t1 / t2.
+
+Expr*
+ScalarEvolution::term_div (Expr *t1, Expr *t2)
+{
+  Integer *i2 = t2->as_integer ();
+
+  // For now, t2 must be a constant integer.
+  if (!i2)
+    return NULL;
+
+  // It should be catched before.
+  assert (i2->value != 1);
+
+  if (OpExpr *mul1 = t1->as_op_expr ())
+    {
+      assert (t1->get_opcode () == Op_Mul);
+
+      Expr *opnd0 = fold (Op_TauDiv, mul1->opnd[0], t2);
+
+      return opnd0 ? build (Op_Mul, opnd0, mul1->opnd[1]) : NULL;
+    }
+
+  return NULL;
+}
+
+Expr*
+ScalarEvolution::fold_build (Opcode opcode, Expr *e1, Expr *e2)
+{
+  if (Expr *folded = fold (opcode, e1, e2))
+    return folded;
+
+  return build (opcode, e1, e2);
+}
+
+Expr*
+ScalarEvolution::build (Opcode opcode, Expr *e1, Expr *e2)
+{
+  return new (memory) OpExpr (e1->get_type (), opcode, e1, e2);
+}
+
+// Create a new polynomial chrec if RIGHT is not zero, otherwise
+// return LEFT, i.e. do the folding {left, +, 0}_l => left.
+
+Expr*
+ScalarEvolution::fold_build_poly_chrec (Type *type, Expr *left,
+                                        Expr *right, LoopNode *loop)
+{
+  Integer *itmp = right->as_integer ();
+
+  return (itmp && itmp->value == 0 ? left
+          : new (memory) PolyChrec (type, left, right, loop));
+}
+
+int
+ScalarEvolution::number_gcd (int a, int b)
+{
+  if (a > b)
+    return number_gcd (b, a);
+
+  for (;;)
+    {
+      int c = b % a;
+
+      if (c == 0)
+        return a;
+
+      b = a;
+      a = c;
+    }
+}
+
+Expr*
+ScalarEvolution::term_gcd (Expr *t1, Expr *t2)
+{
+  if (t1->int_zero_p ())
+    {
+      if (!t2->int_zero_p ())
+        // gcd (0, t2) => t2
+        return t2;
+      else
+        // gcd (0, 0) => 1
+        return int_one;
+    }
+
+  if (t2->int_zero_p ())
+    // gcd (t1, 0) => t1
+    return t1;
+
+  if (OpExpr *mul1 = t1->as_op_expr ())
+    {
+      if (mul1->get_opcode () != Op_Mul)
+        // Only process terms.
+        return int_one;
+
+      if (OpExpr *mul2 = t2->as_op_expr ())
+        {
+          if (mul2->get_opcode () != Op_Mul)
+            // Only process terms.
+            return int_one;
+
+          if (same_opnd_p (mul1->opnd[1], mul2->opnd[1]))
+            // Found a common factor, perform the conversion
+            // gcd (t1 * a, t2 * a) => gcd (t1, t2) * a
+            return fold_build (Op_Mul,
+                               term_gcd (mul1->opnd[0], mul2->opnd[0]),
+                               mul1->opnd[1]);
+          else if (factor_precede_p (mul1->opnd[1], mul2->opnd[1]))
+            // a precedes b, gcd (t1 * a, t2 * b) => gcd (t1 * a, t2)
+            return term_gcd (mul1, mul2->opnd[0]);
+          else
+            // Otherwise, gcd (t1 * a, t2 * b) => gcd (t1, t2 * b)
+            return term_gcd (mul1->opnd[0], mul2);
+        }
+      else
+        // gcd (t1 * a, b) => gcd (b, t1 * a).  See the following code.
+        return term_gcd (t2, t1);
+    }
+
+  // Now, t1 is a single factor.
+  if (OpExpr *mul2 = t2->as_op_expr ())
+    {
+      if (mul2->get_opcode () != Op_Mul)
+        // Only process terms.
+        return int_one;
+
+      if (same_opnd_p (t1, mul2->opnd[1]))
+        // gcd (a, t2 * a) => a
+        return t1;
+      else if (factor_precede_p (t1, mul2->opnd[1]))
+        // a precedes b, gcd (a, t2 * b) => gcd (a, t2)
+        return term_gcd (t1, mul2->opnd[0]);
+      else
+        // Otherwise, gcd (a, t2 * b) => 1
+        return int_one;
+    }
+
+  // Now, t1 and t2 are either an integer or a variable.
+  if (same_opnd_p (t1, t2))
+    // gcd (a, a) => a
+    return t1;
+
+  if (Integer *i1 = t1->as_integer ())
+    if (Integer *i2 = t2->as_integer ())
+      return new (memory) Integer (i1->get_type (),
+                                   number_gcd (i1->value, i2->value));
+
+  return int_one;
+}
+
+// Return false only when DIVIDEND and DIVISOR are both terms, and we
+// are sure that DIVIDEND cannot be exactly divided by DIVISOR.
+
+bool
+ScalarEvolution::term_may_divided_by_p (Expr *dividend, Expr *divisor)
+{
+  if (OpExpr *mul1 = dividend->as_op_expr ())
+    {
+      if (mul1->get_opcode () != Op_Mul)
+        // Only process terms.  Make conservative assumption for others.
+        return true;
+
+      if (OpExpr *mul2 = divisor->as_op_expr ())
+        {
+          if (mul2->get_opcode () != Op_Mul)
+            // Only process terms.  Make conservative assumption for others.
+            return true;
+
+          if (same_opnd_p (mul1->opnd[1], mul2->opnd[1]))
+            // Common divisor can be safely removed.
+            return term_may_divided_by_p (mul1->opnd[0], mul2->opnd[0]);
+          else if (factor_precede_p (mul1->opnd[1], mul2->opnd[1]))
+            // There is a variable of divisor not in dividend, ignore
+            // the last variable of divisor since it may equal 1 (the
+            // most conservative assumption).  This is safe because
+            // (a * b) % c != 0 implies (a * b) % (c * d) != 0.
+            return term_may_divided_by_p (mul1, mul2->opnd[0]);
+          else
+            // There is a variable of dividend not in divisor.  We can
+            // only make this conservative assumption without information
+            // of values of variables, since that variable may equal
+            // any value even the whole divisor.
+            return true;
+        }
+      else
+        // See the comments of the last case above.
+        return true;
+    }
+
+  // Now, dividend is a single factor.
+  if (OpExpr *mul2 = divisor->as_op_expr ())
+    {
+      if (mul2->get_opcode () != Op_Mul)
+        // Only process terms.  Make conservative assumption for others.
+        return true;
+
+      if (same_opnd_p (dividend, mul2->opnd[1]))
+        // Common divisor can be safely removed.
+        return term_may_divided_by_p (int_one, mul2->opnd[0]);
+      else if (factor_precede_p (dividend, mul2->opnd[1]))
+        // There is a variable of divisor not in dividend.  See above.
+        return term_may_divided_by_p (dividend, mul2->opnd[0]);
+      else
+        // There is a variable of dividend not in divisor.  See above.
+        return true;
+    }
+
+  // Now, dividend and divisor are either an integer or a variable.
+
+  if (Integer *i1 = dividend->as_integer ())
+    if (Integer *i2 = divisor->as_integer ())
+      return i1->value % i2->value == 0;
+
+  return true;
+}
+
+bool
+ScalarEvolution::may_divided_by_p (Expr *dividend, Expr *divisor)
+{
+  assert (!divisor->int_zero_p ());
+
+  if (OpExpr *opexpr = dividend->as_op_expr ())
+    {
+      switch (opexpr->get_opcode ())
+        {
+        case Op_Add:
+        case Op_Sub:
+          // Return false only when one part can be divided and the
+          // other part cannot.  Note that even when two parts can
+          // neither be divided, the whole may.  For example, 5x + 1
+          // and 2 when x may equal 1 during runtime.
+          return (may_divided_by_p (opexpr->opnd[0], divisor)
+                  == may_divided_by_p (opexpr->opnd[1], divisor));
+
+        default:
+          ;
+        }
+    }
+
+  return term_may_divided_by_p (dividend, divisor);
+}
+
+void
+ScalarEvolution::debug_scev_for_all (LoopNode *loop)
+{
+  // Process all inter loops first.
+  for (LoopNode *child = loop->getChild (); child; child = child->getSiblings ())
+    debug_scev_for_all (child);
+
+  const Nodes &nodes = loop->getNodesInLoop ();
+
+  for (Nodes::const_iterator i = nodes.begin (); i != nodes.end (); i++)
+    {
+      Node *node = *i;
+      Inst *label = (Inst*)node->getLabelInst ();
+
+      for (Inst *inst = label->getNextInst ();
+           inst && inst != label;
+           inst = inst->getNextInst ())
+        {
+          SsaOpnd *var = inst->getDst()->asSsaOpnd ();
+
+          if (var)
+            {
+              Expr *scev = analyze_scev (var, loop);
+
+              if (Log::isEnabled () && scev)
+                {
+                  Log::out() << "SCEV of ";
+                  var->print (Log::out ());
+                  Log::out() << ": " << scev << "\n";
+                }
+            }
+        }
+    }
+}
+
+}

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.cpp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.h?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.h (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.h Sun Jun  6 22:47:40 2010
@@ -0,0 +1,136 @@
+/* -*- mode: c++; indent-tabs-mode: nil; -*- */
+
+#ifndef _SCALAR_EVOLUTION_H_
+#define _SCALAR_EVOLUTION_H_
+
+#include "loop-info.h"
+
+namespace Jitrino {
+
+class ScalarEvolution
+{
+public:
+  ScalarEvolution (LoopTree *t)
+    : memory ("ScalarEvolution"), loop_tree (t), cached_scev (memory, 97)
+  {
+    int_zero = new (memory) Integer (NULL, 0);
+    int_one = new (memory) Integer (NULL, 1);
+  }
+
+  // Return the evolution function of VAR with respect to LOOP, which
+  // can be represented by the polynomial chain of recurrences (chrec).
+  // At all program points that exactly belong to LOOP (not to sub-loops),
+  // and where VAR is available, the value of VAR always equals to the
+  // result of applying the evolution function on the iteration number
+  // of LOOP, say i.  The evolution function can only contain variables
+  // defined outside LOOP, because a variable defined in LOOP can either
+  // be represented by a polynomial chrec that don't contain variables
+  // defined in LOOP, or be a function of i that cannot be represented
+  // by a polynomial chrec.  The variables defined outside LOOP are
+  // parameters of the evolution function and can be instantiated.
+  Expr* analyze_scev (SsaOpnd *var, LoopNode *loop);
+
+  // Compute and return the number of iterations of LOOP_INFO.  Return
+  // NULL if it cannot be computed (e.g. it has multiple latches).
+  Expr* number_of_iterations (LoopInfo &loop_info);
+
+  // Instantiate parameters of SCEV used in USE_LOOP with respect to
+  // WRTO_LOOP.  Returned function is an evolution function of iteration
+  // numbers of loops in [WRTO_LOOP, USE_LOOP].
+  Expr* instantiate_scev (Expr *scev, LoopNode *use_loop, LoopNode *wrto_loop);
+
+  Integer* get_int_zero () const { return int_zero; }
+
+  // Fold the expression (E1 OPCODE E2).  Return the folded expression
+  // if successful, otherwise return NULL.
+  Expr* fold (Opcode opcode, Expr *e1, Expr *e2);
+
+  // Build the folded expression (E1 OPCODE E2).
+  Expr* fold_build (Opcode opcode, Expr *e1, Expr *e2);
+
+  // Build the expression (E1 OPCODE E2).
+  Expr* build (Opcode opcode, Expr *e1, Expr *e2);
+
+  // Return the GCD of two integer.
+  static int number_gcd (int a, int b);
+
+  // Return the GCD of two terms.
+  Expr* term_gcd (Expr *t1, Expr *t2);
+
+  // Return false only when DIVIDEND is a polynomial and DIVISOR is a
+  // single term, and we are sure that DIVIDEND cannot be exactly
+  // divided by DIVISOR.  For all other cases, simply return true.
+  bool may_divided_by_p (Expr *dividend, Expr *divisor);
+
+  // For debugging:
+
+  void debug_scev_for_all (LoopNode *loop);
+
+private:
+  // A pair of <var, loop>.
+  class VarLoop
+  {
+  public:
+    VarLoop (SsaOpnd *v, LoopNode *l) : var (v), loop (l) {}
+
+  public:
+    SsaOpnd *var;
+    LoopNode *loop;
+  };
+
+  // The hash table for mapping pairs of <var, loop> to expressions.
+  class MapVarLoopToExpr : public HashTable<VarLoop, Expr>
+  {
+  public:
+    MapVarLoopToExpr (MemoryManager &m, U_32 s)
+      : HashTable<VarLoop, Expr> (m, s) {}
+
+  protected:
+    virtual bool keyEquals (VarLoop *key1, VarLoop *key2) const
+    {
+      return key1->var == key2->var && key1->loop == key2->loop;
+    }
+
+    virtual U_32 getKeyHashCode (VarLoop *key) const
+    {
+      return (U_32)(((long)key->var ^ (long)key->loop) >> 2);
+    }
+  };
+
+private:
+  Expr* analyze_scev_1 (SsaOpnd *, LoopNode *);
+  bool loop_phi_node_p (Inst *);
+  Expr* analyze_scev_for_loop_phi (Inst *, LoopNode *);
+  Expr* compute_step (SsaOpnd *, Inst *, LoopNode *);
+
+  static bool is_mul_inst (Inst *);
+
+  Expr* fold_polynomial (Opcode, Expr *, Expr *);
+
+  static bool same_opnd_p (Expr *, Expr *);
+  Expr* term_add (Opcode, Expr *, Expr *);
+
+  static bool factor_precede_p (Expr *, Expr *);
+  Expr* term_mul (Expr *, Expr *);
+  Expr* term_div (Expr *, Expr *);
+
+  bool term_may_divided_by_p (Expr *, Expr *);
+
+  Expr* fold_build_poly_chrec (Type *, Expr *, Expr *, LoopNode *);
+
+private:
+  MemoryManager memory;
+
+  LoopTree *loop_tree;
+
+  // Hash set of <KEY:(var, loop), VALUE:evolution_function> pairs for
+  // caching analyzed results.
+  MapVarLoopToExpr cached_scev;
+
+  Integer *int_zero;
+  Integer *int_one;
+};
+
+}
+
+#endif

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/autovect/scalar-evolution.h
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/codelowerer.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/codelowerer.h?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/codelowerer.h (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/codelowerer.h Sun Jun  6 22:47:40 2010
@@ -94,6 +94,8 @@ private:
 
     Inst* caseXor(Inst* inst) {return caseDefault(inst);}
 
+    Inst* caseAndNot(Inst* inst) {return caseDefault(inst);}
+
     Inst* caseNot(Inst* inst) {return caseDefault(inst);}
 
     // selection
@@ -304,6 +306,24 @@ private:
 
     Inst* caseAddOffsetPlusHeapbase(Inst* inst) {return caseDefault(inst);}
 
+    Inst* caseVecAddSub(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecHadd(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecHsub(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecShuffle(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecExtract(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecPackScalars(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecInterleaveHigh(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecInterleaveLow(Inst* inst) {return caseDefault(inst);}
+
+    Inst* caseVecCmpStr(Inst* inst) {return caseDefault(inst);}
+
     // new tau methods
     Inst* caseTauPoint(Inst* inst) {return caseDefault(inst);}
 

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.cpp?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.cpp (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.cpp Sun Jun  6 22:47:40 2010
@@ -752,6 +752,23 @@ void DynamicABCE::findArrayAccesses() {
     }
 }
 
+Inst *DynamicABCE::getLdBaseInst(Inst* checkInst) {
+
+    if (checkInst->getOpcode() == Op_LdArrayBaseAddr) {
+        return checkInst;
+    } else if (checkInst->getOpcode() == Op_LdVar) {
+        return getLdBaseInst(checkInst->getSrc(0)->asSsaOpnd()->getInst()); 
+    } else if (checkInst->getOpcode() == Op_StVar) {
+        return getLdBaseInst(checkInst->getSrc(0)->asSsaOpnd()->getInst());
+    } else if (checkInst->getOpcode() == Op_Phi) {
+        return getLdBaseInst(checkInst->getSrc(0)->asSsaOpnd()->getInst());
+    }
+
+    assert(0);
+
+    return NULL;
+}
+
 void DynamicABCE::fillTemplate(ArrayAccessTemplate* arrayAccess, Inst* checkInst) {
     Inst* ldBaseInst = NULL;
 
@@ -778,7 +795,7 @@ void DynamicABCE::fillTemplate(ArrayAcce
         } else if (opcode == Op_AddScaledIndex &&
             arrayAccess->index == inst->getSrc(1) && arrayAccess->array == NULL) {
             assert(ldBaseInst == NULL);
-            ldBaseInst = inst->getSrc(0)->asSsaOpnd()->getInst();
+            ldBaseInst = getLdBaseInst(inst->getSrc(0)->asSsaOpnd()->getInst());
             assert((ldBaseInst->getOpcode() == Op_LdArrayBaseAddr)||(ldBaseInst->getOpcode() == Op_LdVar));
             arrayAccess->array = ldBaseInst->getSrc(0)->asSsaOpnd();
             break;

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.h?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.h (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/dabce.h Sun Jun  6 22:47:40 2010
@@ -109,6 +109,7 @@ private:
                             InvariantOpndLoopInfo* stride,
                             SsaOpnd* arrayLength,
                             bool canReachBound);
+    Inst *getLdBaseInst(Inst* checkInst);
     void fillTemplate(ArrayAccessTemplate* arrayAccesses, Inst* checkInst);    
     Edge* findUnconditionalInEdge(Node* targetNode);
     Node* getClonedLoop();

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/hashvaluenumberer.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/hashvaluenumberer.cpp?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/hashvaluenumberer.cpp (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/hashvaluenumberer.cpp Sun Jun  6 22:47:40 2010
@@ -159,6 +159,7 @@ public:
     Inst* caseAnd(Inst* inst)               { return hashInst(inst); }
     Inst* caseOr(Inst* inst)                { return hashInst(inst); }
     Inst* caseXor(Inst* inst)               { return hashInst(inst); }
+    Inst* caseAndNot(Inst* inst)            { return hashInst(inst); }
     Inst* caseNot(Inst* inst)               { return hashInst(inst); }
     
     // selection
@@ -899,6 +900,33 @@ public:
     virtual Inst*
     caseAddOffsetPlusHeapbase(Inst* inst) { return hashInst(inst); }
 
+    virtual Inst*
+    caseVecAddSub(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecHadd(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecHsub(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecShuffle(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecExtract(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecPackScalars(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecInterleaveHigh(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecInterleaveLow(Inst* inst) { return caseDefault(inst); }
+
+    virtual Inst*
+    caseVecCmpStr(Inst* inst) { return caseDefault(inst); }
+
     // new tau methods
     virtual Inst*
     caseTauPoint(Inst* inst) { return caseDefault(inst); }

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/memoryopt.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/memoryopt.cpp?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/memoryopt.cpp (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/memoryopt.cpp Sun Jun  6 22:47:40 2010
@@ -898,7 +898,7 @@ MemoryOptInitWalker::applyToInst(Inst *i
 
     case Op_Add: case Op_Mul: case Op_Sub: case Op_TauDiv: case Op_TauRem: 
     case Op_Neg: case Op_MulHi: case Op_Min: case Op_Max: case Op_Abs:
-    case Op_And: case Op_Or: case Op_Xor: 
+    case Op_And: case Op_Or: case Op_Xor: case Op_AndNot:
     case Op_Not: case Op_Select: case Op_Conv: case Op_ConvZE: case Op_ConvUnmanaged: case Op_Shladd: case Op_Shl: 
     case Op_Shr: case Op_Cmp: case Op_Cmp3: 
     case Op_Branch: case Op_Jump: case Op_Switch:
@@ -920,6 +920,15 @@ MemoryOptInitWalker::applyToInst(Inst *i
     case Op_Label:
     case Op_Phi:
     case Op_TauPi:
+    case Op_VecAddSub:
+    case Op_VecHadd:
+    case Op_VecHsub:
+    case Op_VecShuffle:
+    case Op_VecExtract:
+    case Op_VecPackScalars:
+    case Op_VecInterleaveHigh:
+    case Op_VecInterleaveLow:
+    case Op_VecCmpStr:
     case Op_TauPoint:
     case Op_TauEdge:
     case Op_TauAnd:

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.cpp?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.cpp (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.cpp Sun Jun  6 22:47:40 2010
@@ -1661,6 +1661,12 @@ Simplifier::simplifyTauRem(Type* dstType
                 //
                 return genLdConstant((I_32)0)->getDst();
             }
+            else if (denom > 0 && ((denom & (denom - 1)) == 0)) {
+                // convert rem by powers of 2 into bitwise "and" --njt--
+                // src1 % src2 -> src1 & (src2 - 1)
+                return genAnd(dstType, src1,
+                              genLdConstant(denom - 1)->getDst ())->getDst ();
+            }
         } else if (ConstantFolder::isConstant(src2inst, cv.i8)) {
             int64 denom = cv.i8;
             if ((denom == -1) || (denom == 1)) {

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.h?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.h (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/optimizer/simplifier.h Sun Jun  6 22:47:40 2010
@@ -385,6 +385,9 @@ public:
             return opnd->getInst();
         return inst;
     }
+    Inst* caseAndNot(Inst* inst) {
+        return inst;
+    }
     Inst* caseNot(Inst* inst) {
         Opnd* opnd = simplifyNot(inst->getDst()->getType(),
                                  inst->getSrc(0));
@@ -876,6 +879,42 @@ public:
         return inst;
     }
 
+    Inst* caseVecAddSub(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecHadd(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecHsub(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecShuffle(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecExtract(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecPackScalars(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecInterleaveHigh(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecInterleaveLow(Inst* inst) {
+        return inst;
+    }
+
+    Inst* caseVecCmpStr(Inst* inst) {
+        return inst;
+    }
+
     Inst* caseTauPoint(Inst* inst) {
         return inst;
     }

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.cpp?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.cpp (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.cpp Sun Jun  6 22:47:40 2010
@@ -313,6 +313,33 @@ bool LoopTree::isBackEdge(const Edge* ed
     return fg->getDominatorTree()->dominates(edge->getTargetNode(), edge->getSourceNode());
 }
 
+LoopNode*
+LoopTree::findCommonLoop (LoopNode *loop1, LoopNode *loop2) const
+{
+  int depth1 = loop1->getDepth ();
+  int depth2 = loop2->getDepth ();
+
+  while (depth1 < depth2)
+    {
+      loop2 = loop2->getParent ();
+      depth2--;
+    }
+
+  while (depth2 < depth1)
+    {
+      loop1 = loop1->getParent ();
+      depth1--;
+    }
+
+  while (loop1 != loop2)
+    {
+      loop1 = loop1->getParent ();
+      loop2 = loop2->getParent ();
+    }
+
+  return loop1;
+}
+
 
 bool LoopNode::inLoop(const Node* node) const  {
     assert(this!=loopTree->getRoot());

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.h?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.h (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/LoopTree.h Sun Jun  6 22:47:40 2010
@@ -105,6 +105,10 @@ public:
     bool isNormalized() const { return normalized;}
 
     U_32 getMaxLoopDepth() const {return getHeight()-1;}
+
+    // Return common ancestor of LOOP1 and LOOP2.
+    LoopNode* findCommonLoop (LoopNode *loop1, LoopNode *loop2) const;
+
 private:
 
     void findLoopHeaders(Nodes& headers);

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.cpp?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.cpp (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.cpp Sun Jun  6 22:47:40 2010
@@ -0,0 +1,78 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, ersion 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+/**
+ * @author Intel, Buqi Cheng$
+ *
+ */
+
+#include <string.h>
+#include "SIMD.h"
+
+namespace Jitrino {
+
+bool
+SIMDUtils::isSIMDClass(const char* kname)
+{
+  return !strncmp (kname + (*kname == 'L'), SIMD_HELPER_PACKAGE_NAME,
+                   sizeof (SIMD_HELPER_PACKAGE_NAME) - 1);
+}
+
+bool
+SIMDUtils::matchType (const char* candidate, const char* typeName)
+{
+  if (candidate[0] == 'L')
+    {
+      size_t typeLen = strlen (typeName);
+      size_t candLen = strlen (candidate);
+      return typeLen + 2 == candLen && !strncmp (typeName, candidate + 1, typeLen);
+    }
+
+  return !strcmp (typeName, candidate);
+}
+
+Type*
+SIMDUtils::convertSIMDType2HIR (TypeManager &tm, const char *name)
+{
+  if (matchType (name, "com/intel/jvi/I8vec16"))
+    return tm.getVectorType (tm.getInt8Type (), 16);
+  else if (matchType (name, "com/intel/jvi/I16vec8"))
+    return tm.getVectorType (tm.getInt16Type (), 8);
+  else if (matchType (name, "com/intel/jvi/I32vec4"))
+    return tm.getVectorType (tm.getInt32Type (), 4);
+  else if (matchType (name, "com/intel/jvi/I64vec2"))
+    return tm.getVectorType (tm.getInt64Type (), 2);
+  else if (matchType(name, "com/intel/jvi/F32vec4"))
+    return tm.getVectorType (tm.getSingleType (), 4);
+  else if (matchType (name, "com/intel/jvi/F64vec2"))
+    return tm.getVectorType (tm.getDoubleType (), 2);
+
+  assert (0);
+
+  return NULL;
+}
+
+Type*
+SIMDUtils::convertSIMDType2HIR (TypeManager &tm, Type *type)
+{
+  const char *name = type->getName ();
+  assert (isSIMDClass (name));
+
+  return convertSIMDType2HIR (tm, name);
+}
+
+}//namespace Jitirno

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.cpp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.h?rev=952017&view=auto
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.h (added)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.h Sun Jun  6 22:47:40 2010
@@ -0,0 +1,55 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+/**
+ * @author Intel, Mikhail Y. Fursov
+ *
+ */
+
+#ifndef _SIMD_JITRINO_H_
+#define _SIMD_JITRINO_H_
+
+#include "Opcode.h"
+
+namespace Jitrino {
+
+#ifndef VECTOR_WIDTH
+#define VECTOR_WIDTH 16
+#endif
+
+#define SIMD_HELPER_PACKAGE_NAME  "com/intel/jvi"
+
+class TypeManager;
+class Type;
+
+class SIMDUtils
+{
+public:
+  // checks of class nams is vmmagic class
+  // both typenames and descriptor names are supported
+  static bool isSIMDClass(const char* kname);
+
+  static Type* convertSIMDType2HIR (TypeManager &tm, const char *name);
+
+  static Type* convertSIMDType2HIR (TypeManager &tm, Type *type);
+
+private:
+  static bool matchType (const char* candidate, const char* typeName);
+};
+
+} //namespace Jitirno
+#endif

Propchange: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/SIMD.h
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.cpp?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.cpp (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.cpp Sun Jun  6 22:47:40 2010
@@ -131,6 +131,7 @@ Type* TypeManager::toInternalType(Type* 
     case Type::Single:
     case Type::Double:
     case Type::Float:
+    case Type::Vector:
     case Type::SystemObject:
     case Type::SystemClass:
     case Type::SystemString:
@@ -341,6 +342,7 @@ TypeManager::TypeManager(MemoryManager& 
     userObjectTypes(mm,32), 
     managedPtrTypes(mm,32), 
     unmanagedPtrTypes(mm,32), 
+    vectorTypes(mm,32), 
     arrayTypes(mm,32), 
     methodPtrTypes(mm,32),
     vtablePtrTypes(mm,32),
@@ -430,6 +432,26 @@ TypeManager::init() {
     floatType = initBuiltinType(Type::Float);
 }
 
+VectorType*    
+TypeManager::getVectorType(NamedType *elemType, int length)
+{
+    assert (elemType->isBuiltinValue ());
+
+    VectorType *type = vectorTypes.lookup (elemType);
+
+    if (!type) {
+        type = new (memManager) VectorType(elemType, length);
+	vectorTypes.insert(elemType, type);
+    } else {
+        // For now, we only support single length vector types for a
+        // given element type since it's enough for all existing
+        // machines that supports SIMD.
+        assert (type->getLength () == length);
+    }
+
+    return type;
+}
+
 ArrayType*    
 TypeManager::getArrayType(Type* elemType, bool isCompressed, void* arrayVMTypeHandle) {
     PtrHashTable<ArrayType> &lookupTable = 
@@ -951,6 +973,11 @@ void    EnumType::print(::std::ostream& 
 
 extern const char *messageStr(const char *);
 
+void    VectorType::print(::std::ostream& os) {
+    elemType->print(os);
+    os << "<" << length << ">";
+}
+
 void    ObjectType::print(::std::ostream& os) {
     if (isCompressedReference()) {
         os << "clsc:" << getName();
@@ -1055,6 +1082,7 @@ Type::getPrintString(Tag t) {
     case Single:          s = "r4 "; break;
     case Double:          s = "r8 "; break;
     case Float:           s = "r  "; break;
+    case Vector:          s = "<> "; break;
     case TypedReference:  s = "trf"; break;
     case Value:           s = "val"; break;
     case SystemObject:    s = "obj"; break;

Modified: harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.h?rev=952017&r1=952016&r2=952017&view=diff
==============================================================================
--- harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.h (original)
+++ harmony/enhanced/java/trunk/drlvm/vm/jitrino/src/shared/Type.h Sun Jun  6 22:47:40 2010
@@ -40,6 +40,7 @@ class SsaOpnd;
 class PtrType;
 class FunctionPtrType;
 class NamedType;
+class VectorType;
 class ArrayType;
 class MethodPtrType;
 class UnresolvedMethodPtrType;
@@ -75,6 +76,7 @@ public:
         Single,
         Double,
         Float, // machine-specific float
+	Vector, // vector types
         TypedReference, // typed reference
         
         //     (1.2) User-defined un-boxed value type
@@ -173,6 +175,7 @@ public:
     bool    isSingle()         {return (tag == Type::Single);      }
     bool    isDouble()         {return (tag == Type::Double);      }
     bool    isFloat()          {return (tag == Type::Float);       }
+    bool    isVector()         {return (tag == Type::Vector);       }
     bool    isOffset()         {return (tag == Type::Offset);       }
     bool    isOffsetPlusHeapbase()         {return (tag == Type::OffsetPlusHeapbase);       }
     bool    isSystemObject()   {return isSystemObject(tag); }
@@ -209,6 +212,7 @@ public:
     bool    isArrayLength()    {return (tag == Type::ArrayLength);  }
     bool    isArrayElement()   {return (tag == Type::ArrayElementType);  }
     virtual void print(::std::ostream& os);
+    virtual VectorType*       asVectorType()         {return NULL;}
     virtual ObjectType*       asObjectType()         {return NULL;}
     virtual PtrType*          asPtrType()            {return NULL;}
     virtual FunctionPtrType*  asFunctionPtrType()    {return NULL;}
@@ -540,6 +544,24 @@ public:
     virtual ~ValueType() {}
 };
 
+class VectorType : public ValueType {
+public:
+    VectorType (NamedType *t, int l)
+      : ValueType (Vector), elemType (t), length (l) {}
+
+    VectorType* asVectorType () { return this; }
+
+    NamedType* getElemType () {return elemType;}
+
+    int getLength () { return length; }
+
+    void print (::std::ostream& os);
+
+private:
+    NamedType *elemType;
+    int length;
+};
+
 class UserValueType : public NamedType {
 public:
     UserValueType(void* td,TypeManager& tm) : NamedType(Value,td,tm) {}
@@ -733,6 +755,7 @@ public:
 
     NamedType*    getValueType(void* vmTypeHandle);
     ObjectType*   getObjectType(void* vmTypeHandle, bool isCompressed=false);
+    VectorType*   getVectorType(NamedType *elemType, int length);
     ArrayType*    getArrayType(Type* elemType, bool isCompressed=false, void* arrayVMTypeHandle=NULL);
     void          initArrayType(Type* elemType, bool isCompressed, void* arrayVMTypeHandle);
     Type*         getCommonType(Type* type1, Type *type2);
@@ -828,6 +851,7 @@ private:
     PtrHashTable<ObjectType>       userObjectTypes;
     PtrHashTable<PtrType>          managedPtrTypes;
     PtrHashTable<PtrType>          unmanagedPtrTypes;
+    PtrHashTable<VectorType>       vectorTypes;
     PtrHashTable<ArrayType>        arrayTypes;
     PtrHashTable<MethodPtrType>    methodPtrTypes;
     PtrHashTable<VTablePtrType>    vtablePtrTypes;



Mime
View raw message