Switch lowering: add heuristic for filling leaf nodes in the weight-balanced…

Description

Switch lowering: add heuristic for filling leaf nodes in the weight-balanced binary search tree

Sparse switches with profile info are lowered as weight-balanced BSTs. For
example, if the node weights are {1,1,1,1,1,1000}, the right-most node would
end up in a tree by itself, bringing it closer to the top.

However, a leaf in this BST can contain up to 3 cases, and having a single
case in a leaf node as in the example means the tree might become
unnecessarily high.

This patch adds a heauristic to the pivot selection algorithm that moves more
cases into leaf nodes unless that would lower their rank. It still doesn't
yield the optimal tree in every case, but I believe it's conservatibely correct.

Details

Committed
hansJun 20 2015, 10:14 AM
Parents
rL240223: [X86][SSE] Fix PerformSExtCombine bug that accessed the wrong return value of…
Branches
Unknown
Tags
Unknown