You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by va...@apache.org on 2007/06/04 14:12:04 UTC
svn commit: r544138 [3/3] - in /harmony/enhanced/drlvm/trunk:
src/test/regression/H1788/ vm/jitrino/config/em64t/ vm/jitrino/config/ia32/
vm/jitrino/src/codegenerator/ia32/ vm/jitrino/src/optimizer/
vm/jitrino/src/optimizer/abcd/ vm/jitrino/src/shared/
Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp?view=auto&rev=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp Mon Jun 4 05:12:02 2007
@@ -0,0 +1,1117 @@
+/*
+ * 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.
+ */
+
+#include "insertpi.h"
+#include "walkers.h"
+#include "abcdbounds.h"
+#include "constantfolder.h"
+
+namespace Jitrino {
+
+static ComparisonModifier
+negateComparison(ComparisonModifier mod)
+{
+ switch (mod) {
+ case Cmp_GT: return Cmp_GTE;
+ case Cmp_GT_Un: return Cmp_GTE_Un;
+ case Cmp_GTE: return Cmp_GT;
+ case Cmp_GTE_Un: return Cmp_GT_Un;
+ case Cmp_EQ: return Cmp_EQ;
+ case Cmp_NE_Un: return Cmp_NE_Un;
+ default:
+ assert(0); return mod;
+ }
+}
+
+static const char *
+printableComparison(ComparisonModifier mod)
+{
+ switch (mod) {
+ case Cmp_GT: return "Cmp_GT";
+ case Cmp_GT_Un: return "Cmp_GT_Un";
+ case Cmp_GTE: return "Cmp_GTE";
+ case Cmp_GTE_Un: return "Cmp_GTE_Un";
+ case Cmp_EQ: return "Cmp_EQ";
+ case Cmp_NE_Un: return "Cmp_NE_Un";
+ default:
+ assert(0); return "";
+ }
+}
+
+static Type::Tag
+unsignType(Type::Tag typetag)
+{
+ switch (typetag) {
+ case Type::IntPtr: return Type::UIntPtr;
+ case Type::Int8: return Type::UInt8;
+ case Type::Int16: return Type::UInt16;
+ case Type::Int32: return Type::UInt32;
+ case Type::Int64: return Type::UInt64;
+ default:
+ assert(0); return typetag;
+ }
+}
+
+// a DomWalker, to be applied in pre-order
+class InsertPiWalker {
+public:
+ InsertPiWalker(InsertPi* insert_pi) : _insertPi(insert_pi) {};
+
+ void applyToDominatorNode(DominatorNode *domNode)
+ {
+ _insertPi->insertPiToNode(domNode->getNode());
+ }
+
+ // is called before a node and its children are processed
+ void enterScope() {};
+
+ // is called after node and children are processed
+ void exitScope() {};
+
+private:
+ InsertPi* _insertPi;
+};
+//------------------------------------------------------------------------------
+
+// Add a Pi node in the node if it is after each test
+// which tells something about a variable
+//
+// WARNING: Pi var live ranges may overlap the original var live ranges
+// since we don't bother to add Phi nodes and rename subsequent uses of var.
+void InsertPi::insertPi()
+{
+ InsertPiWalker insert_pi_walker(this);
+
+ // dom-pre-order traversal
+ DomTreeWalk<true, InsertPiWalker>(_domTree, insert_pi_walker, _mm);
+ renamePiVariables();
+
+ if (Log::isEnabled()) {
+ Log::out() << "IR after Pi insertion" << std::endl;
+ FlowGraph::printHIR(Log::out(), _irManager.getFlowGraph(),
+ _irManager.getMethodDesc());
+ FlowGraph::printDotFile(_irManager.getFlowGraph(),
+ _irManager.getMethodDesc(), "withpi");
+ }
+}
+//------------------------------------------------------------------------------
+
+// add Pi in the node iff after a test which tells something about the var
+void InsertPi::insertPiToNode(Node* block)
+{
+ Edge *dom_edge = 0;
+
+ // see if there is a predecessor block idom such that
+ // (1) idom dominates this one
+ // (2) this block dominates all other predecessors
+ // (3) idom has multiple out-edges
+ // (4) idom has only 1 edge to this node
+
+ // (1a) if a predecessor dominates it must be idom
+ Node *idom = _domTree.getIdom(block);
+
+ // (3) must exist and have multiple out-edges
+ if ((idom == NULL) || (idom->hasOnlyOneSuccEdge())) {
+ return;
+ }
+
+ if (Log::isEnabled()) {
+ Log::out() << "Checking block " << (int)block->getId() << " with idom "
+ << (int) idom->getId() << std::endl;
+ }
+
+ if (block->hasOnlyOnePredEdge()) {
+ // must be from idom -- (1b)
+ // satisfies (2) trivially
+ dom_edge = *(block->getInEdges().begin());
+ } else {
+ // check (1b) and (2)
+ const Edges &inedges = block->getInEdges();
+ typedef Edges::const_iterator EdgeIter;
+ EdgeIter e_last = inedges.end();
+ for (EdgeIter e_iter = inedges.begin(); e_iter != e_last; e_iter++) {
+ Edge *in_edge = *e_iter;
+ Node *pred_block = in_edge->getSourceNode();
+ if (pred_block == idom) {
+ // (1b) found idom
+ if (dom_edge) {
+ // failed (4): idom found on more than one incoming edge
+ return;
+ }
+ dom_edge = in_edge;
+ } else if (! _domTree.dominates(block, pred_block)) {
+ // failed (2)
+ return;
+ }
+ }
+ }
+
+ if (dom_edge) {
+ Edge *in_edge = dom_edge;
+ Node *pred_block = idom;
+ if (Log::isEnabled()) {
+ Log::out() << "Checking branch for " << (int)block->getId()
+ << " with idom "
+ << (int) idom->getId() << std::endl;
+ }
+ if (!pred_block->hasOnlyOneSuccEdge()) {
+ Edge::Kind kind = in_edge->getKind();
+ switch (kind) {
+ case Edge::Kind_True:
+ case Edge::Kind_False:
+ {
+ Inst* branchi1 = (Inst*)pred_block->getLastInst();
+ assert(branchi1 != NULL);
+ BranchInst* branchi = branchi1->asBranchInst();
+ if (branchi && branchi->isConditionalBranch()) {
+ insertPiForBranch(block, branchi, kind);
+ } else {
+ return;
+ }
+ }
+ break;
+
+ case Edge::Kind_Dispatch:
+ return;
+
+ case Edge::Kind_Unconditional:
+ // Previous block must have a PEI
+ // since it had multiple out-edges.
+ // This is the unexceptional condition.
+ {
+ Inst* lasti = (Inst*)pred_block->getLastInst();
+ assert(lasti != NULL);
+ insertPiForUnexceptionalPEI(block, lasti);
+ }
+ // We could look for a bounds check in predecessor.
+
+ // But: since now all useful PEIs have explicit results,
+ // they imply a Pi-like action.
+ break;
+
+ case Edge::Kind_Catch:
+ break;
+ default:
+ break;
+ }
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+void InsertPi::insertPiForUnexceptionalPEI(Node *block, Inst *lasti)
+{
+ switch (lasti->getOpcode()) {
+ case Op_TauCheckBounds:
+ {
+ // the number of newarray elements must be >= 0.
+ assert(lasti->getNumSrcOperands() == 2);
+ Opnd *idxOp = lasti->getSrc(1);
+ Opnd *boundsOp = lasti->getSrc(0);
+
+ if (Log::isEnabled()) {
+ Log::out() << "Adding info about CheckBounds instruction ";
+ lasti->print(Log::out());
+ Log::out() << std::endl;
+ }
+ Type::Tag typetag = idxOp->getType()->tag;
+ PiBound lb(typetag, int64(0));
+ PiBound ub(typetag, 1, VarBound(boundsOp),int64(-1));
+ PiCondition bounds0(lb, ub);
+ Opnd *tauOpnd = lasti->getDst(); // use the checkbounds tau
+ insertPiForOpndAndAliases(block, idxOp, bounds0, tauOpnd);
+
+ PiBound idxBound(typetag, 1, VarBound(idxOp), int64(1));
+ PiCondition bounds1(idxBound, PiBound(typetag, false));
+ insertPiForOpndAndAliases(block, boundsOp, bounds1, tauOpnd);
+ }
+ break;
+ case Op_NewArray:
+ {
+ // the number of newarray elements must be in [0, MAXINT32]
+ assert(lasti->getNumSrcOperands() == 1);
+ Opnd *numElemOpnd = lasti->getSrc(0);
+ if (Log::isEnabled()) {
+ Log::out() << "Adding info about NewArray instruction ";
+ lasti->print(Log::out());
+ Log::out() << std::endl;
+ }
+ Opnd *tauOpnd = getBlockTauEdge(block); // need to use a TauEdge
+ PiCondition bounds0(PiBound(numElemOpnd->getType()->tag,
+ int64(0)),
+ PiBound(numElemOpnd->getType()->tag,
+ int64(0x7fffffff)));
+ insertPiForOpndAndAliases(block, numElemOpnd, bounds0, tauOpnd);
+ }
+ break;
+ case Op_NewMultiArray:
+ {
+ // the number of newarray dimensions must be >= 1.
+ uint32 numOpnds = lasti->getNumSrcOperands();
+ assert(numOpnds >= 1);
+ StlSet<Opnd *> done(_mm);
+ if (Log::isEnabled()) {
+ Log::out() << "Adding info about NewMultiArray instruction ";
+ lasti->print(Log::out());
+ Log::out() << std::endl;
+ }
+ Opnd *tauOpnd = 0;
+ // the number of newarray elements must be in [0, MAXINT32]
+ for (uint32 opndNum = 0; opndNum < numOpnds; opndNum++) {
+ Opnd *thisOpnd = lasti->getSrc(opndNum);
+ if (!done.has(thisOpnd)) {
+ done.insert(thisOpnd);
+ PiCondition bounds0(PiBound(thisOpnd->getType()->tag,
+ int64(0)),
+ PiBound(thisOpnd->getType()->tag,
+ int64(0x7fffffff)));
+ if ( !tauOpnd ) {
+ tauOpnd = getBlockTauEdge(block); // must use a tauEdge
+ }
+ insertPiForOpndAndAliases(block, thisOpnd, bounds0, tauOpnd);
+ }
+ }
+ }
+ break;
+ default:
+ break;
+ }
+}
+//------------------------------------------------------------------------------
+
+SsaTmpOpnd* InsertPi::getBlockTauEdge(Node *block) {
+ if ((_lastTauEdgeBlock == block) && _blockTauEdge) return _blockTauEdge;
+ Inst *firstInst = (Inst*)block->getFirstInst();
+ Inst *inst = firstInst->getNextInst();
+ for (; inst != NULL; inst = inst->getNextInst()) {
+ if (inst->getOpcode() == Op_TauEdge) {
+ _blockTauEdge = inst->getDst()->asSsaTmpOpnd();
+ assert(_blockTauEdge);
+ _lastTauEdgeBlock = block;
+ return _blockTauEdge;
+ }
+ }
+ for (inst = firstInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
+ if ((inst->getOpcode() != Op_Phi) && (inst->getOpcode() != Op_TauPoint)) {
+ break; // insert before inst.
+ }
+ }
+ // no non-phis, insert before inst;
+ TypeManager &tm = _irManager.getTypeManager();
+ SsaTmpOpnd *tauOpnd = _irManager.getOpndManager().createSsaTmpOpnd(tm.getTauType());
+ Inst* tauEdge = _irManager.getInstFactory().makeTauEdge(tauOpnd);
+ if(Log::isEnabled()) {
+ Log::out() << "Inserting tauEdge inst ";
+ tauEdge->print(Log::out());
+ if (inst!=NULL) {
+ Log::out() << " before inst ";
+ inst->print(Log::out());
+ }
+ Log::out() << std::endl;
+ }
+ if (inst != NULL) {
+ tauEdge->insertBefore(inst);
+ } else {
+ block->appendInst(tauEdge);
+ }
+ _blockTauEdge = tauOpnd;
+ _lastTauEdgeBlock = block;
+ return tauOpnd;
+}
+//------------------------------------------------------------------------------
+
+// Insert Pi Nodes for any variables occurring in the branch test
+//
+// Since we're examining the test anyway, let's figure out the conditions
+// here, too, so we don't have to duplicate any code. Note that this
+// condition may already be in terms of Pi variables from the predecessor
+// block, since
+// -- predecessor dominates this block
+// -- we are traversing blocks in a dominator-tree preorder
+// so we must have already visited the predecessor.
+//
+// We also must add the new Pi variable to our map.
+//
+void InsertPi::insertPiForBranch(Node* block,
+ BranchInst* branchi,
+ Edge::Kind kind) // True or False only
+{
+ Type::Tag instTypeTag = branchi->getType();
+ if (!Type::isInteger(instTypeTag))
+ return;
+ ComparisonModifier mod = branchi->getComparisonModifier();
+ if (branchi->getNumSrcOperands() == 1) {
+ Opnd *op0 = branchi->getSrc(0);
+ PiCondition zeroBounds(PiBound(instTypeTag, (int64)0),
+ PiBound(instTypeTag, (int64)0));
+ switch (mod) {
+ case Cmp_Zero:
+ insertPiForComparison(block,
+ Cmp_EQ,
+ zeroBounds,
+ op0,
+ false,
+ // negate if false edge
+ (kind == Edge::Kind_False));
+ break;
+ case Cmp_NonZero:
+ insertPiForComparison(block,
+ Cmp_EQ, // use EQ
+ zeroBounds,
+ op0,
+ false,
+ // but negate if true edge
+ (kind == Edge::Kind_True));
+ break;
+ default:
+ break;
+ }
+ } else {
+ Opnd *op0 = branchi->getSrc(0);
+ Opnd *op1 = branchi->getSrc(1);
+ assert(branchi->getNumSrcOperands() == 2);
+ PiCondition bounds0(op0->getType()->tag, op0);
+ PiCondition bounds1(op1->getType()->tag, op1);
+ if (!bounds0.isUnknown()) {
+ insertPiForComparison(block,
+ mod,
+ bounds0,
+ op1,
+ false,
+ // negate for false edge
+ (kind == Edge::Kind_False));
+ }
+ if (!bounds1.isUnknown()) {
+ insertPiForComparison(block,
+ mod,
+ bounds1,
+ op0,
+ true,
+ // negate for false edge
+ (kind == Edge::Kind_False));
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+void InsertPi::insertPiForComparison(Node* block,
+ ComparisonModifier mod,
+ const PiCondition &bounds,
+ Opnd* op,
+ bool swap_operands,
+ bool negate_comparison)
+{
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(..., ";
+ Log::out() << printableComparison(mod);
+ Log::out() << ", ";
+ bounds.print(Log::out());
+ Log::out() << ", ";
+ op->print(Log::out());
+ Log::out() << ", ";
+ Log::out() << (swap_operands ? "true" : "false");
+ Log::out() << (negate_comparison ? "true" : "false");
+ Log::out() << std::endl;
+ }
+
+ PiCondition bounds0 = bounds;
+ // add a Pi node for immediate value.
+ if (negate_comparison) {
+ mod = negateComparison(mod);
+ swap_operands = !swap_operands;
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison: negating comparison to " ;
+ Log::out() << printableComparison(mod);
+ Log::out() << std::endl;
+ }
+ }
+ switch (mod) {
+ case Cmp_EQ:
+ if (!negate_comparison)
+ insertPiForOpndAndAliases(block, op, bounds0, NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison: cannot represent ! Cmp_EQ" << std::endl;
+ }
+ }
+ // we can't represent the other case
+ break;
+ case Cmp_NE_Un:
+ if (negate_comparison)
+ insertPiForOpndAndAliases(block, op, bounds0, NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison: cannot represent Cmp_NE_Un" << std::endl;
+ }
+ }
+ // we can't represent the other case
+ break;
+ case Cmp_GT_Un:
+ if (swap_operands) { // op > bounds, only a lower bound on op
+ Type::Tag optag = op->getType()->tag;
+ if (!Type::isUnsignedInteger(optag)) {
+ // 1 is a lower bound on int op
+ PiCondition oneBounds(PiBound(optag, (int64)1),
+ PiBound(optag, (int64)1));
+ PiCondition oneLowerBound(oneBounds.only_lower_bound());
+ insertPiForOpndAndAliases(block, op, oneLowerBound, NULL);
+ } else {
+ // we can be more precise for an unsigned op
+ bounds0 = bounds0.cast(unsignType(bounds0.getType()));
+ PiCondition bounds1a(bounds0.only_lower_bound());
+ PiCondition bounds1(bounds1a.add((int64)1));
+ if (! bounds1.getLb().isUnknown())
+ insertPiForOpndAndAliases(block, op, bounds1, NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(1): bounds1 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << "\n\tbounds1a is ";
+ bounds1a.print(Log::out());
+ Log::out() << "\n\tbounds1 is ";
+ bounds1.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ } else { // bounds > op, only an upper bound on op
+ Type::Tag optag = op->getType()->tag;
+ if (Type::isUnsignedInteger(optag)) {
+ // for an unsigned upper bound, we're ok
+ bounds0 = bounds0.cast(unsignType(bounds0.getType()));
+ PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1));
+ if (! bounds1.getUb().isUnknown())
+ insertPiForOpndAndAliases(block, op, bounds1, NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(2): bounds1 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << "\n\tbounds1 is ";
+ bounds1.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ } else {
+ // otherwise, we know nothing unless bound is a small constant
+ PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1));
+ if (bounds0.getUb().isConstant()) {
+ int64 ubConst = bounds1.getUb().getConst();
+ if (((optag == Type::Int32) &&
+ ((ubConst&0xffffffff) <= 0x7ffffff) &&
+ ((ubConst&0xffffffff) >= 0)) ||
+ ((optag == Type::Int64) &&
+ ((ubConst <= 0x7ffffff) &&
+ (ubConst >= 0)))) {
+ insertPiForOpndAndAliases(block, op, bounds1, NULL);
+ } else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(2): bounds1 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << "\n\tbounds1 is ";
+ bounds1.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ }
+ }
+ break;
+ case Cmp_GT:
+ if (swap_operands) { // op > bounds, only a lower bound on op
+ PiCondition bounds1a(bounds0.only_lower_bound());
+ PiCondition bounds1(bounds1a.add((int64)1));
+ if (! bounds1.getLb().isUnknown())
+ insertPiForOpndAndAliases(block, op, bounds1, NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(1): bounds1 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << "\n\tbounds1a is ";
+ bounds1a.print(Log::out());
+ Log::out() << "\n\tbounds1 is ";
+ bounds1.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ } else { // bounds > op, only an upper bound on op
+ PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1));
+ if (! bounds1.getUb().isUnknown())
+ insertPiForOpndAndAliases(block, op, bounds1, NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(2): bounds1 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << "\n\tbounds1 is ";
+ bounds1.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ break;
+ case Cmp_GTE_Un:
+ if (swap_operands) { // op >= bounds, only lower bound on op
+ Type::Tag optag = op->getType()->tag;
+ if (!Type::isUnsignedInteger(optag)) {
+ // 0 is a lower bound on an int op
+ PiCondition zeroBounds(PiBound(optag, (int64)0),
+ PiBound(optag, (int64)0));
+ PiCondition zeroLowerBound(zeroBounds.only_lower_bound());
+ insertPiForOpndAndAliases(block, op, zeroLowerBound, NULL);
+ } else {
+ // we can be more precise for an unsigned op lb
+ bounds0 = bounds0.cast(unsignType(bounds0.getType()));
+ if (! bounds0.getLb().isUnknown()) {
+ insertPiForOpndAndAliases(block, op,
+ bounds0.only_lower_bound(), NULL);
+ } else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(3): bounds0 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ } else { // bounds >= op, only upper bound on op
+ Type::Tag optag = op->getType()->tag;
+ if (Type::isUnsignedInteger(optag)) {
+ // unsigned ub on unsigned op
+ bounds0 = bounds0.cast(unsignType(bounds0.getType()));
+ if (! bounds0.getUb().isUnknown())
+ insertPiForOpndAndAliases(block, op,
+ bounds0.only_upper_bound(), NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(4): bounds0 UB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ } else {
+ // otherwise, we know nothing unless bound is a small constant
+ if (bounds0.getUb().isConstant()) {
+ int64 ubConst = bounds0.getUb().getConst();
+ if (((optag == Type::Int32) &&
+ ((ubConst&0xffffffff) <= 0x7ffffff) &&
+ ((ubConst&0xffffffff) >= 0)) ||
+ ((optag == Type::Int64) &&
+ ((ubConst <= 0x7ffffff) &&
+ (ubConst >= 0)))) {
+ insertPiForOpndAndAliases(block, op, bounds0, NULL);
+ } else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(2): bounds0 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ }
+ }
+ break;
+ case Cmp_GTE:
+ if (swap_operands) { // op >= bounds, only lower bound on op
+ if (! bounds0.getLb().isUnknown()) {
+ insertPiForOpndAndAliases(block, op,
+ bounds0.only_lower_bound(), NULL);
+ } else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(3): bounds0 LB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ } else { // bounds >= op, only upper bound on op
+ if (! bounds0.getUb().isUnknown())
+ insertPiForOpndAndAliases(block, op,
+ bounds0.only_upper_bound(), NULL);
+ else {
+ if (Log::isEnabled()) {
+ Log::out() << "insertPiForComparison(4): bounds0 UB is Unknown;\n\tbounds is ";
+ bounds.print(Log::out());
+ Log::out() << "\n\tbounds0 is ";
+ bounds0.print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ break;
+ case Cmp_Zero:
+ case Cmp_NonZero:
+ case Cmp_Mask:
+ assert(0);
+ break;
+ default:
+ assert(false);
+ break;
+ }
+}
+//------------------------------------------------------------------------------
+
+void InsertPi::insertPiForOpnd(Node *block,
+ Opnd *org,
+ const PiCondition &cond,
+ Opnd *tauOpnd)
+{
+ if (ConstantFolder::isConstant(org)) {
+ if (Log::isEnabled()) {
+ Log::out() << "Skipping Pi Node for opnd ";
+ org->print(Log::out());
+ Log::out() << " under condition ";
+ cond.print(Log::out());
+ Log::out() << " since it is constant" << std::endl;
+ }
+ } else {
+ PiOpnd *piOpnd = _irManager.getOpndManager().createPiOpnd(org);
+ Inst *headInst = (Inst*)block->getFirstInst();
+ PiCondition *condPtr = new (_irManager.getMemoryManager()) PiCondition(cond);
+ if (tauOpnd == 0)
+ tauOpnd = getBlockTauEdge(block);
+ Inst *newInst = _irManager.getInstFactory().makeTauPi(piOpnd, org, tauOpnd, condPtr);
+ Inst *place = headInst->getNextInst();
+ while (place != NULL) {
+ Opcode opc = place->getOpcode();
+ if ((opc != Op_Phi) && (opc != Op_TauPoint) && (opc != Op_TauEdge))
+ break;
+ place = place->getNextInst();
+ }
+ if (Log::isEnabled()) {
+ Log::out() << "Inserting Pi Node for opnd ";
+ org->print(Log::out());
+ Log::out() << " under condition ";
+ cond.print(Log::out());
+ if (place!=NULL) {
+ Log::out() << " just before inst ";
+ place->print(Log::out());
+ }
+ Log::out() << std::endl;
+ }
+ if (place != NULL) {
+ newInst->insertBefore(place);
+ } else {
+ block->appendInst(newInst);
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+// dereferencing through Pis, 0 if not constant.
+Opnd* InsertPi::getConstantOpnd(Opnd *opnd)
+{
+ return ConstantFolder::isConstant(opnd) ? opnd : NULL;
+}
+//------------------------------------------------------------------------------
+
+bool InsertPi::getAliases(Opnd *opnd, AbcdAliases *aliases, int64 addend)
+{
+ Inst *inst = opnd->getInst();
+ switch (inst->getOpcode()) {
+ case Op_TauPi:
+ return getAliases(inst->getSrc(0), aliases, addend);
+
+ case Op_Add:
+ {
+ Opnd *op0 = inst->getSrc(0);
+ Opnd *op1 = inst->getSrc(1);
+ Opnd *constOpnd0 = getConstantOpnd(op0);
+ Opnd *constOpnd1 = getConstantOpnd(op1);
+ if ((constOpnd0 || constOpnd1) &&
+ (inst->getType() == Type::Int32)) {
+ // I assume we've done folding first
+ assert(!(constOpnd0 && constOpnd1));
+ if (constOpnd1) {
+ // swap the operands;
+ constOpnd0 = constOpnd1;
+ op1 = op0;
+ }
+ // now constOpnd0 should be constant
+ // op1 is the non-constant operand
+
+ Inst *inst0 = constOpnd0->getInst();
+ assert(inst0);
+ ConstInst *cinst0 = inst0->asConstInst();
+ assert(cinst0);
+ ConstInst::ConstValue cv = cinst0->getValue();
+ int32 c = cv.i4;
+ int64 sumc = c + addend;
+ if (add_overflowed<int64>(sumc, c, addend)) {
+ return false;
+ } else {
+ VarBound vb(op1);
+ aliases->theSet.insert(PiBound(inst->getType(), 1, vb, sumc));
+ getAliases(op1, aliases, sumc);
+ return true;
+ }
+ }
+ }
+ break;
+ case Op_Sub:
+ {
+ Opnd *constOpnd = getConstantOpnd(inst->getSrc(1));
+ if (constOpnd && (inst->getType() == Type::Int32)) {
+ Opnd *op0 = inst->getSrc(0);
+ Opnd *op1 = constOpnd;
+ // now op1 should be constant
+ // I assume we've done folding first
+ if( !(!getConstantOpnd(op0)) ) assert(0);
+
+ Inst *inst1 = op1->getInst();
+ assert(inst1);
+ ConstInst *cinst1 = inst1->asConstInst();
+ assert(cinst1);
+ ConstInst::ConstValue cv = cinst1->getValue();
+ int64 c = cv.i4;
+ int64 negc = -c;
+ int64 subres = addend + negc;
+ if (neg_overflowed<int64>(negc, c) ||
+ add_overflowed<int64>(subres, addend, negc)) {
+ return false;
+ } else {
+ VarBound vb(op1);
+ aliases->theSet.insert(PiBound(inst->getType(), 1, vb, subres));
+ getAliases(op1, aliases, subres);
+ return true;
+ }
+ }
+ }
+ break;
+ case Op_Copy:
+ assert(0); // do copy propagation first
+ break;
+ case Op_TauCheckZero:
+ return false;
+ default:
+ break;
+ }
+ return false;
+}
+//------------------------------------------------------------------------------
+
+// checks for aliases of opnd, inserts them.
+void InsertPi::insertPiForOpndAndAliases(Node *block,
+ Opnd *org,
+ const PiCondition &cond,
+ Opnd *tauOpnd)
+{
+ const PiBound &lb = cond.getLb();
+ const PiBound &ub = cond.getUb();
+
+ if((_problemType == Lower) && lb.isUndefined()) return;
+ else if((_problemType == Upper) && ub.isUndefined()) return;
+
+ if (_useAliases) {
+ if (Log::isEnabled()) {
+ Log::out() << "Inserting Pi Node for opnd ";
+ org->print(Log::out());
+ Log::out() << " and its aliases";
+ Log::out() << " under condition ";
+ cond.print(Log::out());
+ Log::out() << std::endl;
+ }
+ AbcdAliases aliases(_mm);
+ // check for aliases
+ insertPiForOpnd(block, org, cond, tauOpnd);
+ if (getAliases(org, &aliases, 0)) {
+ if (Log::isEnabled()) {
+ Log::out() << "Has aliases ";
+ AbcdAliasesSet::iterator iter = aliases.theSet.begin();
+ AbcdAliasesSet::iterator end = aliases.theSet.end();
+ for ( ; iter != end; iter++) {
+ PiBound alias = *iter;
+ alias.print(Log::out());
+ Log::out() << " ";
+ }
+ Log::out() << std::endl;
+ }
+ AbcdAliasesSet::iterator iter = aliases.theSet.begin();
+ AbcdAliasesSet::iterator end = aliases.theSet.end();
+ for ( ; iter != end; iter++) {
+ PiBound alias = *iter;
+ PiBound inverted = alias.invert(org); // org - c
+ // plug-in lb and ub into inverted, yields bounds:
+ // [ lb - c, ub - c ]
+ PiCondition renamedCondition(PiBound(inverted, org, lb),
+ PiBound(inverted, org, ub));
+ insertPiForOpnd(block, alias.getVar().the_var,
+ renamedCondition, tauOpnd);
+ }
+ }
+ } else {
+ insertPiForOpnd(block, org, cond, tauOpnd);
+ }
+}
+//------------------------------------------------------------------------------
+
+// a DomWalker, to be applied forwards/preorder
+class RenamePiWalker {
+public:
+
+ RenamePiWalker(InsertPi *insert_pi,
+ MemoryManager &localMM,
+ SparseOpndMap* &piMap0,
+ int sizeEstimate0) :
+ _insertPi(insert_pi),
+ localMemManager(localMM),
+ _piMap(piMap0),
+ sizeEstimate(sizeEstimate0)
+ {}
+
+ void applyToDominatorNode(DominatorNode *domNode)
+ {
+ _insertPi->renamePiVariablesInNode(domNode->getNode());
+ }
+
+ void enterScope()
+ {
+ if (!_piMap) _piMap =
+ new (localMemManager) SparseOpndMap(sizeEstimate,
+ localMemManager, 1, 4, 7);
+ _piMap->enter_scope();
+ }
+
+ void exitScope()
+ {
+ _piMap->exit_scope();
+ }
+private:
+ InsertPi* _insertPi;
+ MemoryManager &localMemManager;
+ SparseOpndMap* &_piMap;
+ int sizeEstimate;
+};
+//------------------------------------------------------------------------------
+
+void InsertPi::renamePiVariables()
+{
+ MethodDesc &methodDesc= _irManager.getMethodDesc();
+ uint32 byteCodeSize = methodDesc.getByteCodeSize();
+ MemoryManager localMemManager("Abcd::renamePiNodes");
+
+ RenamePiWalker theWalker(this, localMemManager, _piMap, byteCodeSize);
+ DomTreeWalk<true, RenamePiWalker>(_domTree, theWalker, localMemManager);
+}
+//------------------------------------------------------------------------------
+
+void InsertPi::renamePiVariablesInNode(Node *block)
+{
+ // For each variable use in the block, check for a Pi version in
+ // the piTable. Since we are visiting in preorder over dominator
+ // tree dominator order, any found version will dominate this node.
+
+ // we defer adding any new mappings for the Pi instructions here until
+ // we are past the Pi instructions
+
+ // first process any pi nodes, just the RHSs
+ Inst* headInst = (Inst*)block->getFirstInst();
+ for (int phase=0; phase < 2; ++phase) {
+ // phase 0: remap just Pi node source operands
+ // phase 1: add Pi remappings, remap source operands of other instructions
+
+ for (Inst* inst = headInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
+
+ if (inst->getOpcode() == Op_TauPi) {
+ if (phase == 1) {
+ // add any Pi node destination to the map.
+
+ Opnd *dstOpnd = inst->getDst();
+ assert(dstOpnd->isPiOpnd());
+ Opnd *orgOpnd = dstOpnd->asPiOpnd()->getOrg();
+ if (_useAliases) {
+ if (orgOpnd->isSsaVarOpnd()) {
+ orgOpnd = orgOpnd->asSsaVarOpnd()->getVar();
+ }
+ }
+ _piMap->insert(orgOpnd, dstOpnd);
+ if (Log::isEnabled()) {
+ Log::out() << "adding remap for Pi of ";
+ orgOpnd->print(Log::out());
+ Log::out() << " to ";
+ inst->getDst()->print(Log::out());
+ Log::out() << std::endl;
+ }
+
+ continue; // don't remap Pi sources;
+ }
+ } else {
+ if (phase == 0) {
+ // no more Pi instructions, we're done with phase 0.
+ break;
+ }
+ }
+
+ // now process source operands
+ uint32 numOpnds = inst->getNumSrcOperands();
+ for (uint32 i=0; i<numOpnds; i++) {
+ Opnd *opnd = inst->getSrc(i);
+ if (opnd->isPiOpnd())
+ opnd = opnd->asPiOpnd()->getOrg();
+ Opnd *foundOpnd = _piMap->lookup(opnd);
+ if (foundOpnd) {
+ inst->setSrc(i,foundOpnd);
+ }
+ }
+
+ if (inst->getOpcode() == Op_TauPi) {
+ // for a Pi, remap variables appearing in the condition as well
+ if (Log::isEnabled()) {
+ Log::out() << "remapping condition in ";
+ inst->print(Log::out());
+ Log::out() << std::endl;
+ }
+ TauPiInst *thePiInst = inst->asTauPiInst();
+ assert(thePiInst);
+ PiCondition *cond = thePiInst->cond;
+ if (Log::isEnabled()) {
+ Log::out() << " original condition is ";
+ cond->print(Log::out());
+ Log::out() << std::endl;
+ }
+ Opnd *lbRemap = cond->getLb().getVar().the_var;
+ if (lbRemap) {
+ if (Log::isEnabled()) {
+ Log::out() << " has lbRemap=";
+ lbRemap->print(Log::out());
+ Log::out() << std::endl;
+ }
+ if (lbRemap->isPiOpnd())
+ lbRemap = lbRemap->asPiOpnd()->getOrg();
+ Opnd *lbRemapTo = _piMap->lookup(lbRemap);
+ if (lbRemapTo) {
+ if (Log::isEnabled()) {
+ Log::out() << "adding remap of lbRemap=";
+ lbRemap->print(Log::out());
+ Log::out() << " to lbRemapTo=";
+ lbRemapTo->print(Log::out());
+ Log::out() << " to condition ";
+ cond->print(Log::out());
+ }
+ PiCondition remapped(*cond, lbRemap, lbRemapTo);
+ if (Log::isEnabled()) {
+ Log::out() << " YIELDS1 ";
+ remapped.print(Log::out());
+ }
+ *cond = remapped;
+ if (Log::isEnabled()) {
+ Log::out() << " YIELDS ";
+ cond->print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ Opnd *ubRemap = cond->getUb().getVar().the_var;
+ if (ubRemap && (lbRemap != ubRemap)) {
+ if (Log::isEnabled()) {
+ Log::out() << " has ubRemap=";
+ ubRemap->print(Log::out());
+ Log::out() << std::endl;
+ }
+ if (ubRemap->isPiOpnd())
+ ubRemap = ubRemap->asPiOpnd()->getOrg();
+ Opnd *ubRemapTo = _piMap->lookup(ubRemap);
+ if (ubRemapTo) {
+ if (Log::isEnabled()) {
+ Log::out() << "adding remap of ubRemap=";
+ ubRemap->print(Log::out());
+ Log::out() << " to ubRemapTo=";
+ ubRemapTo->print(Log::out());
+ Log::out() << " to condition ";
+ cond->print(Log::out());
+ }
+ PiCondition remapped(*cond, ubRemap, ubRemapTo);
+ if (Log::isEnabled()) {
+ Log::out() << " YIELDS1 ";
+ remapped.print(Log::out());
+ }
+ *cond = remapped;
+ if (Log::isEnabled()) {
+ Log::out() << " YIELDS ";
+ cond->print(Log::out());
+ Log::out() << std::endl;
+ }
+ }
+ }
+ }
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+// a ScopedDomNodeInstWalker, forward/preorder
+class RemovePiWalker {
+public:
+ RemovePiWalker(InsertPi* ins) : _insertPi(ins), block(0) // forward
+ {}
+
+ void startNode(DominatorNode *domNode) { block = domNode->getNode(); };
+ void applyToInst(Inst *i) { _insertPi->removePiOnInst(block, i); }
+ void finishNode(DominatorNode *domNode) {}
+
+ void enterScope() {}
+ void exitScope() {}
+private:
+ InsertPi* _insertPi;
+ Node* block;
+};
+//------------------------------------------------------------------------------
+
+void InsertPi::removePi()
+{
+ RemovePiWalker removePiWalker(this);
+ typedef ScopedDomNodeInst2DomWalker<true, RemovePiWalker>
+ RemovePiDomWalker;
+ RemovePiDomWalker removePiDomWalker(removePiWalker);
+ DomTreeWalk<true, RemovePiDomWalker>(_domTree, removePiDomWalker, _mm);
+}
+//------------------------------------------------------------------------------
+
+void InsertPi::removePiOnInst(Node* block, Inst *inst)
+{
+ if ( inst->getOpcode() == Op_TauPi ) {
+ inst->unlink();
+ }else{
+ // replace Pi operands with original ones
+ uint32 num_opnds = inst->getNumSrcOperands();
+ for (uint32 i = 0; i < num_opnds; i++) {
+ Opnd* pi_opnd = inst->getSrc(i);
+ while ( pi_opnd->isPiOpnd() ) {
+ pi_opnd = pi_opnd->asPiOpnd()->getOrg();
+ }
+ inst->setSrc(i, pi_opnd);
+ }
+ }
+}
+//------------------------------------------------------------------------------
+
+} //namespace Jitrino
+
Propchange: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp
------------------------------------------------------------------------------
svn:eol-style = native
Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h?view=auto&rev=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h Mon Jun 4 05:12:02 2007
@@ -0,0 +1,120 @@
+/*
+ * 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.
+ */
+
+#ifndef _INSERTPI_H
+#define _INSERTPI_H
+
+#include <iostream>
+#include "open/types.h"
+#include "Opcode.h"
+#include "FlowGraph.h"
+#include "abcd/AbcdFlags.h"
+#include "abcdbounds.h"
+#include "opndmap.h"
+
+namespace Jitrino {
+
+class InsertPi {
+public:
+ enum ProblemType {
+ Upper = 2,
+ Lower = 1,
+ Both = 0
+ };
+
+ InsertPi(MemoryManager& mm, DominatorTree& dom_tree, IRManager& irm,
+ bool use_aliases, ProblemType type = Both) :
+ _mm(mm),
+ _domTree(dom_tree),
+ _useAliases(use_aliases),
+ _problemType(type),
+ _irManager(irm),
+ _blockTauEdge(0),
+ _lastTauEdgeBlock(0),
+ _piMap(0)
+ {}
+
+ // Add a Pi node in the node if it is after each test
+ // which tells something about a variable
+ void insertPi();
+
+ void removePi();
+
+ void setUseAliases(bool use = true) { _useAliases = use; }
+ bool useAliases() const { return _useAliases; }
+private:
+ friend class InsertPiWalker;
+ friend class RenamePiWalker;
+ friend class RemovePiWalker;
+
+ // add Pi in the node iff after a test which tells something about the var
+ void insertPiToNode(Node* block);
+
+ // definition: PEI=Potentially Excepting Instruction
+ void insertPiForUnexceptionalPEI(Node *block, Inst *lasti);
+
+ SsaTmpOpnd* getBlockTauEdge(Node *block);
+
+ void insertPiForBranch(Node* block,
+ BranchInst* branchi,
+ Edge::Kind kind);
+
+ void insertPiForComparison(Node* block,
+ ComparisonModifier mod,
+ const PiCondition& bounds,
+ Opnd* op,
+ bool swap_operands,
+ bool negate_comparison);
+
+ void insertPiForOpnd(Node* block,
+ Opnd* org,
+ const PiCondition &cond,
+ Opnd* tauOpnd);
+
+ // checks for aliases of opnd, inserts them.
+ void insertPiForOpndAndAliases(Node* block,
+ Opnd* org,
+ const PiCondition& cond,
+ Opnd* tauOpnd);
+
+ bool getAliases(Opnd *opnd, AbcdAliases *aliases, int64 addend);
+
+ Opnd* getConstantOpnd(Opnd *opnd);
+
+ // Renames variables for which we have Pi nodes.
+ void renamePiVariables();
+
+ void renamePiVariablesInNode(Node *block);
+
+ void renamePiVariablesInDomNode(DominatorNode *block);
+
+ void removePiOnInst(Node* block, Inst *inst);
+
+ MemoryManager& _mm;
+ DominatorTree& _domTree;
+ bool _useAliases;
+ ProblemType _problemType;
+ IRManager& _irManager;
+
+ SsaTmpOpnd* _blockTauEdge;
+ Node* _lastTauEdgeBlock;
+ SparseOpndMap *_piMap;
+};
+
+} //namespace Jitrino
+
+#endif /* _INSERTPI_H */
Propchange: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h
------------------------------------------------------------------------------
svn:eol-style = native
Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/HashSet.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/HashSet.h?view=diff&rev=544138&r1=544137&r2=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/HashSet.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/HashSet.h Mon Jun 4 05:12:02 2007
@@ -112,7 +112,7 @@
// Find elements that are in this set but are not in 'set' and
// write them into 'removeList'.
//
- MemoryManager memManager(1024,"HashSet::intersect.memManager");
+ MemoryManager memManager("HashSet::intersect.memManager");
KEY * removeList = (KEY *)memManager.alloc(sizeof(KEY) * map.size());
uint32 removeListSize = 0;
const_iterator iter = map.begin(),
Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/MapSet.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/MapSet.h?view=diff&rev=544138&r1=544137&r2=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/MapSet.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/shared/MapSet.h Mon Jun 4 05:12:02 2007
@@ -120,7 +120,7 @@
// Find elements that are in this set bat are not in 'set' and
// write them into 'removeList'.
//
- MemoryManager memManager(1024,"MapSet::intersect.memManager");
+ MemoryManager memManager("MapSet::intersect.memManager");
KEY * removeList = (KEY *)memManager.alloc(sizeof(KEY) * size());
uint32 removeListSize = 0;
const_iterator iter = begin(),