diff options
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp')
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 80 |
1 files changed, 2 insertions, 78 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 78ebd2d3..1ae682e 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -11639,92 +11639,16 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, } } -unsigned SelectionDAGBuilder::caseClusterRank(const CaseCluster &CC, - CaseClusterIt First, - CaseClusterIt Last) { - return std::count_if(First, Last + 1, [&](const CaseCluster &X) { - if (X.Prob != CC.Prob) - return X.Prob > CC.Prob; - - // Ties are broken by comparing the case value. - return X.Low->getValue().slt(CC.Low->getValue()); - }); -} - void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList, const SwitchWorkListItem &W, Value *Cond, MachineBasicBlock *SwitchMBB) { assert(W.FirstCluster->Low->getValue().slt(W.LastCluster->Low->getValue()) && "Clusters not sorted?"); - assert(W.LastCluster - W.FirstCluster + 1 >= 2 && "Too small to split!"); - // Balance the tree based on branch probabilities to create a near-optimal (in - // terms of search time given key frequency) binary search tree. See e.g. Kurt - // Mehlhorn "Nearly Optimal Binary Search Trees" (1975). - CaseClusterIt LastLeft = W.FirstCluster; - CaseClusterIt FirstRight = W.LastCluster; - auto LeftProb = LastLeft->Prob + W.DefaultProb / 2; - auto RightProb = FirstRight->Prob + W.DefaultProb / 2; - - // Move LastLeft and FirstRight towards each other from opposite directions to - // find a partitioning of the clusters which balances the probability on both - // sides. If LeftProb and RightProb are equal, alternate which side is - // taken to ensure 0-probability nodes are distributed evenly. - unsigned I = 0; - while (LastLeft + 1 < FirstRight) { - if (LeftProb < RightProb || (LeftProb == RightProb && (I & 1))) - LeftProb += (++LastLeft)->Prob; - else - RightProb += (--FirstRight)->Prob; - I++; - } - - while (true) { - // Our binary search tree differs from a typical BST in that ours can have up - // to three values in each leaf. The pivot selection above doesn't take that - // into account, which means the tree might require more nodes and be less - // efficient. We compensate for this here. - - unsigned NumLeft = LastLeft - W.FirstCluster + 1; - unsigned NumRight = W.LastCluster - FirstRight + 1; - - if (std::min(NumLeft, NumRight) < 3 && std::max(NumLeft, NumRight) > 3) { - // If one side has less than 3 clusters, and the other has more than 3, - // consider taking a cluster from the other side. - - if (NumLeft < NumRight) { - // Consider moving the first cluster on the right to the left side. - CaseCluster &CC = *FirstRight; - unsigned RightSideRank = caseClusterRank(CC, FirstRight, W.LastCluster); - unsigned LeftSideRank = caseClusterRank(CC, W.FirstCluster, LastLeft); - if (LeftSideRank <= RightSideRank) { - // Moving the cluster to the left does not demote it. - ++LastLeft; - ++FirstRight; - continue; - } - } else { - assert(NumRight < NumLeft); - // Consider moving the last element on the left to the right side. - CaseCluster &CC = *LastLeft; - unsigned LeftSideRank = caseClusterRank(CC, W.FirstCluster, LastLeft); - unsigned RightSideRank = caseClusterRank(CC, FirstRight, W.LastCluster); - if (RightSideRank <= LeftSideRank) { - // Moving the cluster to the right does not demot it. - --LastLeft; - --FirstRight; - continue; - } - } - } - break; - } - - assert(LastLeft + 1 == FirstRight); - assert(LastLeft >= W.FirstCluster); - assert(FirstRight <= W.LastCluster); + auto [LastLeft, FirstRight, LeftProb, RightProb] = + SL->computeSplitWorkItemInfo(W); // Use the first element on the right as pivot since we will make less-than // comparisons against it. |