4648 u1->in(0) != u1_later && !u1->in(0)->is_Root()) {
4649 tty->print("n->out(%d)->in(0): ", i); u1->in(0)->dump();
4650 }
4651 for (uint j = 0; j < u1->outcnt(); j++) {
4652 Node* u2 = u1->raw_out(j);
4653 if (u2 == n || u2 == u1)
4654 continue;
4655 tty->print("n->out(%d)->out(%d): ", i, j); u2->dump();
4656 if (!u2->is_CFG()) {
4657 Node* u2_later = get_ctrl(u2);
4658 tty->print("later(n->out(%d)->out(%d)): ", i, j); u2_later->dump();
4659 if (u2->in(0) != NULL && !u2->in(0)->is_top() &&
4660 u2->in(0) != u2_later && !u2->in(0)->is_Root()) {
4661 tty->print("n->out(%d)->in(0): ", i); u2->in(0)->dump();
4662 }
4663 }
4664 }
4665 }
4666 }
4667 tty->cr();
4668 int ct = 0;
4669 Node *dbg_legal = LCA;
4670 while(!dbg_legal->is_Start() && ct < 100) {
4671 tty->print("idom[%d] ",ct); dbg_legal->dump();
4672 ct++;
4673 dbg_legal = idom(dbg_legal);
4674 }
4675 tty->cr();
4676 }
4677 #endif
4678
4679 #ifndef PRODUCT
4680 //------------------------------dump-------------------------------------------
4681 void PhaseIdealLoop::dump() const {
4682 ResourceMark rm;
4683 Node_Stack stack(C->live_nodes() >> 2);
4684 Node_List rpo_list;
4685 VectorSet visited;
4686 visited.set(C->top()->_idx);
4687 rpo(C->root(), stack, visited, rpo_list);
4688 // Dump root loop indexed by last element in PO order
4689 dump(_ltree_root, rpo_list.size(), rpo_list);
4690 }
4691
4692 void PhaseIdealLoop::dump(IdealLoopTree* loop, uint idx, Node_List &rpo_list) const {
4693 loop->dump_head();
4694
4695 // Now scan for CFG nodes in the same loop
4696 for (uint j = idx; j > 0; j--) {
4697 Node* n = rpo_list[j-1];
4727 computed_idom->_idx, cached_idom->_idx);
4728 }
4729 }
4730 // Dump nodes it controls
4731 for (uint k = 0; k < _nodes.Size(); k++) {
4732 // (k < C->unique() && get_ctrl(find(k)) == n)
4733 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4734 Node* m = C->root()->find(k);
4735 if (m && m->outcnt() > 0) {
4736 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4737 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p",
4738 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4739 }
4740 tty->sp(2 * loop->_nest + 1);
4741 m->dump();
4742 }
4743 }
4744 }
4745 }
4746 }
4747 #endif
4748
4749 // Collect a R-P-O for the whole CFG.
4750 // Result list is in post-order (scan backwards for RPO)
4751 void PhaseIdealLoop::rpo(Node* start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list) const {
4752 stk.push(start, 0);
4753 visited.set(start->_idx);
4754
4755 while (stk.is_nonempty()) {
4756 Node* m = stk.node();
4757 uint idx = stk.index();
4758 if (idx < m->outcnt()) {
4759 stk.set_index(idx + 1);
4760 Node* n = m->raw_out(idx);
4761 if (n->is_CFG() && !visited.test_set(n->_idx)) {
4762 stk.push(n, 0);
4763 }
4764 } else {
4765 rpo_list.push(m);
4766 stk.pop();
4767 }
|
4648 u1->in(0) != u1_later && !u1->in(0)->is_Root()) {
4649 tty->print("n->out(%d)->in(0): ", i); u1->in(0)->dump();
4650 }
4651 for (uint j = 0; j < u1->outcnt(); j++) {
4652 Node* u2 = u1->raw_out(j);
4653 if (u2 == n || u2 == u1)
4654 continue;
4655 tty->print("n->out(%d)->out(%d): ", i, j); u2->dump();
4656 if (!u2->is_CFG()) {
4657 Node* u2_later = get_ctrl(u2);
4658 tty->print("later(n->out(%d)->out(%d)): ", i, j); u2_later->dump();
4659 if (u2->in(0) != NULL && !u2->in(0)->is_top() &&
4660 u2->in(0) != u2_later && !u2->in(0)->is_Root()) {
4661 tty->print("n->out(%d)->in(0): ", i); u2->in(0)->dump();
4662 }
4663 }
4664 }
4665 }
4666 }
4667 tty->cr();
4668 tty->print_cr("idoms of early %d:", early->_idx);
4669 dump_idom(early);
4670 tty->cr();
4671 tty->print_cr("idoms of (wrong) LCA %d:", LCA->_idx);
4672 dump_idom(LCA);
4673 tty->cr();
4674 dump_real_LCA(early, LCA);
4675 tty->cr();
4676 }
4677
4678 // Find the real LCA of early and the wrongly assumed LCA.
4679 void PhaseIdealLoop::dump_real_LCA(Node* early, Node* wrong_lca) {
4680 assert(!is_dominator(early, wrong_lca) && !is_dominator(early, wrong_lca),
4681 "sanity check that one node does not dominate the other");
4682 assert(!has_ctrl(early) && !has_ctrl(wrong_lca), "sanity check, no data nodes");
4683
4684 ResourceMark rm;
4685 Node_List nodes_seen;
4686 Node* real_LCA = NULL;
4687 Node* n1 = wrong_lca;
4688 Node* n2 = early;
4689 uint count_1 = 0;
4690 uint count_2 = 0;
4691 // Add early and wrong_lca to simplify calculation of idom indices
4692 nodes_seen.push(n1);
4693 nodes_seen.push(n2);
4694
4695 // Walk the idom chain up from early and wrong_lca and stop when they intersect.
4696 while (!n1->is_Start() && !n2->is_Start()) {
4697 n1 = idom(n1);
4698 n2 = idom(n2);
4699 if (n1 == n2) {
4700 // Both idom chains intersect at the same index
4701 real_LCA = n1;
4702 count_1 = nodes_seen.size() / 2;
4703 count_2 = count_1;
4704 break;
4705 }
4706 if (check_idom_chains_intersection(n1, count_1, count_2, &nodes_seen)) {
4707 real_LCA = n1;
4708 break;
4709 }
4710 if (check_idom_chains_intersection(n2, count_2, count_1, &nodes_seen)) {
4711 real_LCA = n2;
4712 break;
4713 }
4714 nodes_seen.push(n1);
4715 nodes_seen.push(n2);
4716 }
4717
4718 assert(real_LCA != NULL, "must always find an LCA");
4719 tty->print_cr("Real LCA of early %d (idom[%d]) and (wrong) LCA %d (idom[%d]):", early->_idx, count_2, wrong_lca->_idx, count_1);
4720 real_LCA->dump();
4721 }
4722
4723 // Check if n is already on nodes_seen (i.e. idom chains of early and wrong_lca intersect at n). Determine the idom index of n
4724 // on both idom chains and return them in idom_idx_new and idom_idx_other, respectively.
4725 bool PhaseIdealLoop::check_idom_chains_intersection(const Node* n, uint& idom_idx_new, uint& idom_idx_other, const Node_List* nodes_seen) const {
4726 if (nodes_seen->contains(n)) {
4727 // The idom chain has just discovered n.
4728 // Divide by 2 because nodes_seen contains the same amount of nodes from both chains.
4729 idom_idx_new = nodes_seen->size() / 2;
4730
4731 // The other chain already contained n. Search the index.
4732 for (uint i = 0; i < nodes_seen->size(); i++) {
4733 if (nodes_seen->at(i) == n) {
4734 // Divide by 2 because nodes_seen contains the same amount of nodes from both chains.
4735 idom_idx_other = i / 2;
4736 }
4737 }
4738 return true;
4739 }
4740 return false;
4741 }
4742 #endif // ASSERT
4743
4744 #ifndef PRODUCT
4745 //------------------------------dump-------------------------------------------
4746 void PhaseIdealLoop::dump() const {
4747 ResourceMark rm;
4748 Node_Stack stack(C->live_nodes() >> 2);
4749 Node_List rpo_list;
4750 VectorSet visited;
4751 visited.set(C->top()->_idx);
4752 rpo(C->root(), stack, visited, rpo_list);
4753 // Dump root loop indexed by last element in PO order
4754 dump(_ltree_root, rpo_list.size(), rpo_list);
4755 }
4756
4757 void PhaseIdealLoop::dump(IdealLoopTree* loop, uint idx, Node_List &rpo_list) const {
4758 loop->dump_head();
4759
4760 // Now scan for CFG nodes in the same loop
4761 for (uint j = idx; j > 0; j--) {
4762 Node* n = rpo_list[j-1];
4792 computed_idom->_idx, cached_idom->_idx);
4793 }
4794 }
4795 // Dump nodes it controls
4796 for (uint k = 0; k < _nodes.Size(); k++) {
4797 // (k < C->unique() && get_ctrl(find(k)) == n)
4798 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4799 Node* m = C->root()->find(k);
4800 if (m && m->outcnt() > 0) {
4801 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4802 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p",
4803 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4804 }
4805 tty->sp(2 * loop->_nest + 1);
4806 m->dump();
4807 }
4808 }
4809 }
4810 }
4811 }
4812
4813 void PhaseIdealLoop::dump_idom(Node* n) const {
4814 if (has_ctrl(n)) {
4815 tty->print_cr("No idom for data nodes");
4816 } else {
4817 for (int i = 0; i < 100 && !n->is_Start(); i++) {
4818 tty->print("idom[%d] ", i);
4819 n->dump();
4820 n = idom(n);
4821 }
4822 }
4823 }
4824 #endif // NOT PRODUCT
4825
4826 // Collect a R-P-O for the whole CFG.
4827 // Result list is in post-order (scan backwards for RPO)
4828 void PhaseIdealLoop::rpo(Node* start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list) const {
4829 stk.push(start, 0);
4830 visited.set(start->_idx);
4831
4832 while (stk.is_nonempty()) {
4833 Node* m = stk.node();
4834 uint idx = stk.index();
4835 if (idx < m->outcnt()) {
4836 stk.set_index(idx + 1);
4837 Node* n = m->raw_out(idx);
4838 if (n->is_CFG() && !visited.test_set(n->_idx)) {
4839 stk.push(n, 0);
4840 }
4841 } else {
4842 rpo_list.push(m);
4843 stk.pop();
4844 }
|