712 } |
712 } |
713 } |
713 } |
714 } |
714 } |
715 } |
715 } |
716 |
716 |
|
717 if (can_reshape) { |
|
718 modified |= optimize_trichotomy(phase->is_IterGVN()); |
|
719 } |
|
720 |
717 return modified ? this : NULL; |
721 return modified ? this : NULL; |
718 } |
722 } |
719 |
723 |
720 |
724 //------------------------------optimize_trichotomy-------------------------- |
|
725 // Optimize nested comparisons of the following kind: |
|
726 // |
|
727 // int compare(int a, int b) { |
|
728 // return (a < b) ? -1 : (a == b) ? 0 : 1; |
|
729 // } |
|
730 // |
|
731 // Shape 1: |
|
732 // if (compare(a, b) == 1) { ... } -> if (a > b) { ... } |
|
733 // |
|
734 // Shape 2: |
|
735 // if (compare(a, b) == 0) { ... } -> if (a == b) { ... } |
|
736 // |
|
737 // Above code leads to the following IR shapes where both Ifs compare the |
|
738 // same value and two out of three region inputs idx1 and idx2 map to |
|
739 // the same value and control flow. |
|
740 // |
|
741 // (1) If (2) If |
|
742 // / \ / \ |
|
743 // Proj Proj Proj Proj |
|
744 // | \ | \ |
|
745 // | If | If If |
|
746 // | / \ | / \ / \ |
|
747 // | Proj Proj | Proj Proj ==> Proj Proj |
|
748 // | / / \ | / | / |
|
749 // Region / \ | / | / |
|
750 // \ / \ | / | / |
|
751 // Region Region Region |
|
752 // |
|
753 // The method returns true if 'this' is modified and false otherwise. |
|
754 bool RegionNode::optimize_trichotomy(PhaseIterGVN* igvn) { |
|
755 int idx1 = 1, idx2 = 2; |
|
756 Node* region = NULL; |
|
757 if (req() == 3 && in(1) != NULL && in(2) != NULL) { |
|
758 // Shape 1: Check if one of the inputs is a region that merges two control |
|
759 // inputs and has no other users (especially no Phi users). |
|
760 region = in(1)->isa_Region() ? in(1) : in(2)->isa_Region(); |
|
761 if (region == NULL || region->outcnt() != 2 || region->req() != 3) { |
|
762 return false; // No suitable region input found |
|
763 } |
|
764 } else if (req() == 4) { |
|
765 // Shape 2: Check if two control inputs map to the same value of the unique phi |
|
766 // user and treat these as if they would come from another region (shape (1)). |
|
767 PhiNode* phi = has_unique_phi(); |
|
768 if (phi == NULL) { |
|
769 return false; // No unique phi user |
|
770 } |
|
771 if (phi->in(idx1) != phi->in(idx2)) { |
|
772 idx2 = 3; |
|
773 if (phi->in(idx1) != phi->in(idx2)) { |
|
774 idx1 = 2; |
|
775 if (phi->in(idx1) != phi->in(idx2)) { |
|
776 return false; // No equal phi inputs found |
|
777 } |
|
778 } |
|
779 } |
|
780 assert(phi->in(idx1) == phi->in(idx2), "must be"); // Region is merging same value |
|
781 region = this; |
|
782 } |
|
783 if (region == NULL || region->in(idx1) == NULL || region->in(idx2) == NULL) { |
|
784 return false; // Region does not merge two control inputs |
|
785 } |
|
786 // At this point we know that region->in(idx1) and region->(idx2) map to the same |
|
787 // value and control flow. Now search for ifs that feed into these region inputs. |
|
788 ProjNode* proj1 = region->in(idx1)->isa_Proj(); |
|
789 ProjNode* proj2 = region->in(idx2)->isa_Proj(); |
|
790 if (proj1 == NULL || proj1->outcnt() != 1 || |
|
791 proj2 == NULL || proj2->outcnt() != 1) { |
|
792 return false; // No projection inputs with region as unique user found |
|
793 } |
|
794 assert(proj1 != proj2, "should be different projections"); |
|
795 IfNode* iff1 = proj1->in(0)->isa_If(); |
|
796 IfNode* iff2 = proj2->in(0)->isa_If(); |
|
797 if (iff1 == NULL || iff1->outcnt() != 2 || |
|
798 iff2 == NULL || iff2->outcnt() != 2) { |
|
799 return false; // No ifs found |
|
800 } |
|
801 if (iff1 == iff2) { |
|
802 igvn->add_users_to_worklist(iff1); // Make sure dead if is eliminated |
|
803 igvn->replace_input_of(region, idx1, iff1->in(0)); |
|
804 igvn->replace_input_of(region, idx2, igvn->C->top()); |
|
805 return (region == this); // Remove useless if (both projections map to the same control/value) |
|
806 } |
|
807 BoolNode* bol1 = iff1->in(1)->isa_Bool(); |
|
808 BoolNode* bol2 = iff2->in(1)->isa_Bool(); |
|
809 if (bol1 == NULL || bol2 == NULL) { |
|
810 return false; // No bool inputs found |
|
811 } |
|
812 Node* cmp1 = bol1->in(1); |
|
813 Node* cmp2 = bol2->in(1); |
|
814 bool commute = false; |
|
815 if (!cmp1->is_Cmp() || !cmp2->is_Cmp()) { |
|
816 return false; // No comparison |
|
817 } else if (cmp1->Opcode() == Op_CmpF || cmp1->Opcode() == Op_CmpD || |
|
818 cmp2->Opcode() == Op_CmpF || cmp2->Opcode() == Op_CmpD || |
|
819 cmp1->Opcode() == Op_CmpP || cmp1->Opcode() == Op_CmpN || |
|
820 cmp2->Opcode() == Op_CmpP || cmp2->Opcode() == Op_CmpN) { |
|
821 // Floats and pointers don't exactly obey trichotomy. To be on the safe side, don't transform their tests. |
|
822 return false; |
|
823 } else if (cmp1 != cmp2) { |
|
824 if (cmp1->in(1) == cmp2->in(2) && |
|
825 cmp1->in(2) == cmp2->in(1)) { |
|
826 commute = true; // Same but swapped inputs, commute the test |
|
827 } else { |
|
828 return false; // Ifs are not comparing the same values |
|
829 } |
|
830 } |
|
831 proj1 = proj1->other_if_proj(); |
|
832 proj2 = proj2->other_if_proj(); |
|
833 if (!((proj1->unique_ctrl_out() == iff2 && |
|
834 proj2->unique_ctrl_out() == this) || |
|
835 (proj2->unique_ctrl_out() == iff1 && |
|
836 proj1->unique_ctrl_out() == this))) { |
|
837 return false; // Ifs are not connected through other projs |
|
838 } |
|
839 // Found 'iff -> proj -> iff -> proj -> this' shape where all other projs are merged |
|
840 // through 'region' and map to the same value. Merge the boolean tests and replace |
|
841 // the ifs by a single comparison. |
|
842 BoolTest test1 = (proj1->_con == 1) ? bol1->_test : bol1->_test.negate(); |
|
843 BoolTest test2 = (proj2->_con == 1) ? bol2->_test : bol2->_test.negate(); |
|
844 test1 = commute ? test1.commute() : test1; |
|
845 // After possibly commuting test1, if we can merge test1 & test2, then proj2/iff2/bol2 are the nodes to refine. |
|
846 BoolTest::mask res = test1.merge(test2); |
|
847 if (res == BoolTest::illegal) { |
|
848 return false; // Unable to merge tests |
|
849 } |
|
850 // Adjust iff1 to always pass (only iff2 will remain) |
|
851 igvn->replace_input_of(iff1, 1, igvn->intcon(proj1->_con)); |
|
852 if (res == BoolTest::never) { |
|
853 // Merged test is always false, adjust iff2 to always fail |
|
854 igvn->replace_input_of(iff2, 1, igvn->intcon(1 - proj2->_con)); |
|
855 } else { |
|
856 // Replace bool input of iff2 with merged test |
|
857 BoolNode* new_bol = new BoolNode(bol2->in(1), res); |
|
858 igvn->replace_input_of(iff2, 1, igvn->transform((proj2->_con == 1) ? new_bol : new_bol->negate(igvn))); |
|
859 } |
|
860 return false; |
|
861 } |
721 |
862 |
722 const RegMask &RegionNode::out_RegMask() const { |
863 const RegMask &RegionNode::out_RegMask() const { |
723 return RegMask::Empty; |
864 return RegMask::Empty; |
724 } |
865 } |
725 |
866 |