You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by hi...@apache.org on 2010/06/07 00:47:41 UTC
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...
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;