From 395f4f4b2a3db77755fb0a08669b268e74f458c1 Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Wed, 22 Apr 2015 23:14:56 +0000 Subject: Switch lowering: extract jump tables and bit tests before building binary tree (PR22262) This is a re-commit of r235101, which also fixes the problems with the previous patch: - Switches with only a default case and non-fallthrough were handled incorrectly - The previous patch tickled a bug in PowerPC Early-Return Creation which is fixed here. > This is a major rewrite of the SelectionDAG switch lowering. The previous code > would lower switches as a binary tre, discovering clusters of cases > suitable for lowering by jump tables or bit tests as it went along. To increase > the likelihood of finding jump tables, the binary tree pivot was selected to > maximize case density on both sides of the pivot. > > By not selecting the pivot in the middle, the binary trees would not always > be balanced, leading to performance problems in the generated code. > > This patch rewrites the lowering to search for clusters of cases > suitable for jump tables or bit tests first, and then builds the binary > tree around those clusters. This way, the binary tree will always be balanced. > > This has the added benefit of decoupling the different aspects of the lowering: > tree building and jump table or bit tests finding are now easier to tweak > separately. > > For example, this will enable us to balance the tree based on profile info > in the future. > > The algorithm for finding jump tables is quadratic, whereas the previous algorithm > was O(n log n) for common cases, and quadratic only in the worst-case. This > doesn't seem to be major problem in practice, e.g. compiling a file consisting > of a 10k-case switch was only 30% slower, and such large switches should be rare > in practice. Compiling e.g. gcc.c showed no compile-time difference. If this > does turn out to be a problem, we could limit the search space of the algorithm. > > This commit also disables all optimizations during switch lowering in -O0. > > Differential Revision: http://reviews.llvm.org/D8649 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@235560 91177308-0d34-0410-b5e6-96231b3b80d8 --- test/CodeGen/PowerPC/mcm-5.ll | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'test/CodeGen/PowerPC/mcm-5.ll') diff --git a/test/CodeGen/PowerPC/mcm-5.ll b/test/CodeGen/PowerPC/mcm-5.ll index 0c258459c91..19adbe5b7d9 100644 --- a/test/CodeGen/PowerPC/mcm-5.ll +++ b/test/CodeGen/PowerPC/mcm-5.ll @@ -1,5 +1,5 @@ -; RUN: llc -mcpu=pwr7 -O0 -code-model=medium <%s | FileCheck %s -; RUN: llc -mcpu=pwr7 -O0 -code-model=large <%s | FileCheck %s +; RUN: llc -mcpu=pwr7 -code-model=medium <%s | FileCheck %s +; RUN: llc -mcpu=pwr7 -code-model=large <%s | FileCheck %s ; Test correct code generation for medium and large code model ; for loading the address of a jump table from the TOC. -- cgit v1.2.3