1 //===- subzero/src/IceSwitchLowering.cpp - Switch lowering ----------------===//
2 //
3 // The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Implements platform independent analysis of switch cases to improve
12 /// the generated code.
13 ///
14 //===----------------------------------------------------------------------===//
15 #include "IceSwitchLowering.h"
16
17 #include "IceCfgNode.h"
18 #include "IceTargetLowering.h"
19
20 #include <algorithm>
21
22 namespace Ice {
23
clusterizeSwitch(Cfg * Func,const InstSwitch * Instr)24 CaseClusterArray CaseCluster::clusterizeSwitch(Cfg *Func,
25 const InstSwitch *Instr) {
26 const SizeT NumCases = Instr->getNumCases();
27 CaseClusterArray CaseClusters;
28 CaseClusters.reserve(NumCases);
29
30 // Load the cases
31 CaseClusters.reserve(NumCases);
32 for (SizeT I = 0; I < NumCases; ++I)
33 CaseClusters.emplace_back(Instr->getValue(I), Instr->getLabel(I));
34
35 // Sort the cases
36 std::sort(CaseClusters.begin(), CaseClusters.end(),
37 [](const CaseCluster &x, const CaseCluster &y) {
38 return x.High < y.Low;
39 });
40
41 // Merge adjacent case ranges
42 auto Active = CaseClusters.begin();
43 std::for_each(Active + 1, CaseClusters.end(),
44 [&Active](const CaseCluster &x) {
45 if (!Active->tryAppend(x))
46 *(++Active) = x;
47 });
48 CaseClusters.erase(Active + 1, CaseClusters.end());
49
50 // TODO(ascull): Merge in a cycle i.e. -1(=UINTXX_MAX) to 0. This depends on
51 // the types for correct wrap around behavior.
52
53 // A small number of cases is more efficient without a jump table
54 if (CaseClusters.size() < Func->getTarget()->getMinJumpTableSize())
55 return CaseClusters;
56
57 // Test for a single jump table. This can be done in constant time whereas
58 // finding the best set of jump table would be quadratic, too slow(?). If
59 // jump tables were included in the search tree we'd first have to traverse
60 // to them. Ideally we would have an unbalanced tree which is biased towards
61 // frequently executed code but we can't do this well without profiling data.
62 // So, this single jump table is a good starting point where you can get to
63 // the jump table quickly without figuring out how to unbalance the tree.
64 const uint64_t MaxValue = CaseClusters.back().High;
65 const uint64_t MinValue = CaseClusters.front().Low;
66 // Don't +1 yet to avoid (INT64_MAX-0)+1 overflow
67 const uint64_t Range = MaxValue - MinValue;
68
69 // Might be too sparse for the jump table
70 if (NumCases * 2 <= Range)
71 return CaseClusters;
72 // Unlikely. Would mean can't store size of jump table.
73 if (Range == UINT64_MAX)
74 return CaseClusters;
75 const uint64_t TotalRange = Range + 1;
76
77 // Replace everything with a jump table
78 auto *JumpTable =
79 InstJumpTable::create(Func, TotalRange, Instr->getLabelDefault());
80 for (const CaseCluster &Case : CaseClusters) {
81 // Case.High could be UINT64_MAX which makes the loop awkward. Unwrap the
82 // last iteration to avoid wrap around problems.
83 for (uint64_t I = Case.Low; I < Case.High; ++I)
84 JumpTable->addTarget(I - MinValue, Case.Target);
85 JumpTable->addTarget(Case.High - MinValue, Case.Target);
86 Case.Target->setNeedsAlignment();
87 }
88 Func->addJumpTable(JumpTable);
89
90 CaseClusters.clear();
91 CaseClusters.emplace_back(MinValue, MaxValue, JumpTable);
92
93 return CaseClusters;
94 }
95
tryAppend(const CaseCluster & New)96 bool CaseCluster::tryAppend(const CaseCluster &New) {
97 // Can only append ranges with the same target and are adjacent
98 const bool CanAppend =
99 this->Target == New.Target && this->High + 1 == New.Low;
100 if (CanAppend)
101 this->High = New.High;
102 return CanAppend;
103 }
104
105 } // end of namespace Ice
106