Introduction of improved switch lowering.
This includes the high level analysis of switches, the x86 lowering,
the repointing of targets in jump tables and ASM emission of jump
tables.
The technique uses jump tables, range test and binary search with
worst case O(lg n) which improves the previous worst case of O(n)
from a sequential search.
Use is hidden by the --adv-switch flag as the IAS emission still
needs to be implemented.
BUG=None
R=jvoung@chromium.org, stichnot@chromium.org
Review URL: https://codereview.chromium.org/1234803007.
diff --git a/src/IceSwitchLowering.cpp b/src/IceSwitchLowering.cpp
new file mode 100644
index 0000000..06894e6
--- /dev/null
+++ b/src/IceSwitchLowering.cpp
@@ -0,0 +1,96 @@
+//===- subzero/src/IceSwitchLowering.cpp - Switch lowering -----------------==//
+//
+// The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file implements platform independent analysis of switch cases to
+/// improve the generated code.
+///
+//===----------------------------------------------------------------------===//
+#include "IceSwitchLowering.h"
+
+#include "IceTargetLowering.h"
+
+#include <algorithm>
+
+namespace Ice {
+
+CaseClusterArray CaseCluster::clusterizeSwitch(Cfg *Func,
+ const InstSwitch *Inst) {
+ CaseClusterArray CaseClusters;
+
+ // Load the cases
+ SizeT NumCases = Inst->getNumCases();
+ CaseClusters.reserve(NumCases);
+ for (SizeT I = 0; I < NumCases; ++I)
+ CaseClusters.emplace_back(Inst->getValue(I), Inst->getLabel(I));
+
+ // Sort the cases
+ std::sort(CaseClusters.begin(), CaseClusters.end(),
+ [](const CaseCluster &x, const CaseCluster &y) {
+ return x.High < y.Low;
+ });
+
+ // Merge adjacent case ranges
+ auto Active = CaseClusters.begin();
+ std::for_each(Active + 1, CaseClusters.end(),
+ [&Active](const CaseCluster &x) {
+ if (!Active->tryAppend(x))
+ *(++Active) = x;
+ });
+ CaseClusters.erase(Active + 1, CaseClusters.end());
+
+ // TODO(ascull): Merge in a cycle i.e. -1(=UINTXX_MAX) to 0. This depends on
+ // the types for correct wrap around behavior.
+
+ // A small number of cases is more efficient without a jump table
+ if (CaseClusters.size() < Func->getTarget()->getMinJumpTableSize())
+ return CaseClusters;
+
+ // Test for a single jump table. This can be done in constant time whereas
+ // finding the best set of jump table would be quadratic, too slow(?). If
+ // jump tables were included in the search tree we'd first have to traverse to
+ // them. Ideally we would have an unbalanced tree which is biased towards
+ // frequently executed code but we can't do this well without profiling data.
+ // So, this single jump table is a good starting point where you can get to
+ // the jump table quickly without figuring out how to unbalance the tree.
+ uint64_t MaxValue = CaseClusters.back().High;
+ uint64_t MinValue = CaseClusters.front().Low;
+ // Don't +1 yet to avoid (INT64_MAX-0)+1 overflow
+ uint64_t TotalRange = MaxValue - MinValue;
+
+ // Might be too sparse for the jump table
+ if (NumCases * 2 <= TotalRange)
+ return CaseClusters;
+ // Unlikely. Would mean can't store size of jump table.
+ if (TotalRange == UINT64_MAX)
+ return CaseClusters;
+ ++TotalRange;
+
+ // Replace everything with a jump table
+ InstJumpTable *JumpTable =
+ InstJumpTable::create(Func, TotalRange, Inst->getLabelDefault());
+ for (const CaseCluster &Case : CaseClusters)
+ for (uint64_t I = Case.Low; I <= Case.High; ++I)
+ JumpTable->addTarget(I - MinValue, Case.Label);
+
+ CaseClusters.clear();
+ CaseClusters.emplace_back(MinValue, MaxValue, JumpTable);
+
+ return CaseClusters;
+}
+
+bool CaseCluster::tryAppend(const CaseCluster &New) {
+ // Can only append ranges with the same target and are adjacent
+ bool CanAppend = this->Label == New.Label && this->High + 1 == New.Low;
+ if (CanAppend)
+ this->High = New.High;
+ return CanAppend;
+}
+
+} // end of namespace Ice
