740 return singleLength; |
740 return singleLength; |
741 } |
741 } |
742 |
742 |
743 /** |
743 /** |
744 * Tries to find an original value of the given node by traversing through proxies and |
744 * Tries to find an original value of the given node by traversing through proxies and |
745 * unambiguous phis. Note that this method will perform an exhaustive search through phis. It is |
745 * unambiguous phis. Note that this method will perform an exhaustive search through phis. |
746 * intended to be used during graph building, when phi nodes aren't yet canonicalized. |
746 * |
747 * |
747 * @param value the node whose original value should be determined |
748 * @param value The node whose original value should be determined. |
748 * @param abortOnLoopPhi specifies if the traversal through phis should stop and return |
749 * @return The original value (which might be the input value itself). |
749 * {@code value} if it hits a {@linkplain PhiNode#isLoopPhi loop phi}. This argument |
750 */ |
750 * must be {@code true} if used during graph building as loop phi nodes may not yet |
751 public static ValueNode originalValue(ValueNode value) { |
751 * have all their inputs computed. |
752 ValueNode result = originalValueSimple(value); |
752 * @return the original value (which might be {@code value} itself) |
|
753 */ |
|
754 public static ValueNode originalValue(ValueNode value, boolean abortOnLoopPhi) { |
|
755 ValueNode result = originalValueSimple(value, abortOnLoopPhi); |
753 assert result != null; |
756 assert result != null; |
754 return result; |
757 return result; |
755 } |
758 } |
756 |
759 |
757 private static ValueNode originalValueSimple(ValueNode value) { |
760 private static ValueNode originalValueSimple(ValueNode value, boolean abortOnLoopPhi) { |
758 /* The very simple case: look through proxies. */ |
761 /* The very simple case: look through proxies. */ |
759 ValueNode cur = originalValueForProxy(value); |
762 ValueNode cur = originalValueForProxy(value); |
760 |
763 |
761 while (cur instanceof PhiNode) { |
764 while (cur instanceof PhiNode) { |
762 /* |
765 /* |
763 * We found a phi function. Check if we can analyze it without allocating temporary data |
766 * We found a phi function. Check if we can analyze it without allocating temporary data |
764 * structures. |
767 * structures. |
765 */ |
768 */ |
766 PhiNode phi = (PhiNode) cur; |
769 PhiNode phi = (PhiNode) cur; |
|
770 |
|
771 if (abortOnLoopPhi && phi.isLoopPhi()) { |
|
772 return value; |
|
773 } |
767 |
774 |
768 ValueNode phiSingleValue = null; |
775 ValueNode phiSingleValue = null; |
769 int count = phi.valueCount(); |
776 int count = phi.valueCount(); |
770 for (int i = 0; i < count; ++i) { |
777 for (int i = 0; i < count; ++i) { |
771 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); |
778 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); |
781 /* |
788 /* |
782 * We have two different input values for the phi function, and at least one |
789 * We have two different input values for the phi function, and at least one |
783 * of the inputs is another phi function. We need to do a complicated |
790 * of the inputs is another phi function. We need to do a complicated |
784 * exhaustive check. |
791 * exhaustive check. |
785 */ |
792 */ |
786 return originalValueForComplicatedPhi(phi, new NodeBitMap(value.graph())); |
793 return originalValueForComplicatedPhi(value, phi, new NodeBitMap(value.graph()), abortOnLoopPhi); |
787 } else { |
794 } else { |
788 /* |
795 /* |
789 * We have two different input values for the phi function, but none of them |
796 * We have two different input values for the phi function, but none of them |
790 * is another phi function. This phi function cannot be reduce any further, |
797 * is another phi function. This phi function cannot be reduce any further, |
791 * so the phi function is the original value. |
798 * so the phi function is the original value. |
817 } |
824 } |
818 |
825 |
819 /** |
826 /** |
820 * Handling for complicated nestings of phi functions. We need to reduce phi functions |
827 * Handling for complicated nestings of phi functions. We need to reduce phi functions |
821 * recursively, and need a temporary map of visited nodes to avoid endless recursion of cycles. |
828 * recursively, and need a temporary map of visited nodes to avoid endless recursion of cycles. |
822 */ |
829 * |
823 private static ValueNode originalValueForComplicatedPhi(PhiNode phi, NodeBitMap visited) { |
830 * @param value the node whose original value is being determined |
|
831 * @param abortOnLoopPhi specifies if the traversal through phis should stop and return |
|
832 * {@code value} if it hits a {@linkplain PhiNode#isLoopPhi loop phi} |
|
833 */ |
|
834 private static ValueNode originalValueForComplicatedPhi(ValueNode value, PhiNode phi, NodeBitMap visited, boolean abortOnLoopPhi) { |
824 if (visited.isMarked(phi)) { |
835 if (visited.isMarked(phi)) { |
825 /* |
836 /* |
826 * Found a phi function that was already seen. Either a cycle, or just a second phi |
837 * Found a phi function that was already seen. Either a cycle, or just a second phi |
827 * input to a path we have already processed. |
838 * input to a path we have already processed. |
828 */ |
839 */ |
834 int count = phi.valueCount(); |
845 int count = phi.valueCount(); |
835 for (int i = 0; i < count; ++i) { |
846 for (int i = 0; i < count; ++i) { |
836 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); |
847 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); |
837 if (phiCurValue instanceof PhiNode) { |
848 if (phiCurValue instanceof PhiNode) { |
838 /* Recursively process a phi function input. */ |
849 /* Recursively process a phi function input. */ |
839 phiCurValue = originalValueForComplicatedPhi((PhiNode) phiCurValue, visited); |
850 PhiNode curPhi = (PhiNode) phiCurValue; |
|
851 if (abortOnLoopPhi && curPhi.isLoopPhi()) { |
|
852 return value; |
|
853 } |
|
854 phiCurValue = originalValueForComplicatedPhi(value, curPhi, visited, abortOnLoopPhi); |
|
855 if (phiCurValue == value) { |
|
856 // Hit a loop phi |
|
857 assert abortOnLoopPhi; |
|
858 return value; |
|
859 } |
840 } |
860 } |
841 |
861 |
842 if (phiCurValue == null) { |
862 if (phiCurValue == null) { |
843 /* Cycle to a phi function that was already seen. We can ignore this input. */ |
863 /* Cycle to a phi function that was already seen. We can ignore this input. */ |
844 } else if (phiSingleValue == null) { |
864 } else if (phiSingleValue == null) { |