Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceSwitchLowering.cpp - Switch lowering ----------------===// |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 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 |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Implements platform independent analysis of switch cases to improve |
| 12 | /// the generated code. |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 13 | /// |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | #include "IceSwitchLowering.h" |
| 16 | |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 17 | #include "IceCfgNode.h" |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 18 | #include "IceTargetLowering.h" |
| 19 | |
| 20 | #include <algorithm> |
| 21 | |
| 22 | namespace Ice { |
| 23 | |
| 24 | CaseClusterArray CaseCluster::clusterizeSwitch(Cfg *Func, |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 25 | const InstSwitch *Instr) { |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 26 | const SizeT NumCases = Instr->getNumCases(); |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 27 | CaseClusterArray CaseClusters; |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 28 | CaseClusters.reserve(NumCases); |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 29 | |
| 30 | // Load the cases |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 31 | CaseClusters.reserve(NumCases); |
| 32 | for (SizeT I = 0; I < NumCases; ++I) |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 33 | CaseClusters.emplace_back(Instr->getValue(I), Instr->getLabel(I)); |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 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 |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 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 |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 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. |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 64 | const uint64_t MaxValue = CaseClusters.back().High; |
| 65 | const uint64_t MinValue = CaseClusters.front().Low; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 66 | // Don't +1 yet to avoid (INT64_MAX-0)+1 overflow |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 67 | const uint64_t Range = MaxValue - MinValue; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 68 | |
| 69 | // Might be too sparse for the jump table |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 70 | if (NumCases * 2 <= Range) |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 71 | return CaseClusters; |
| 72 | // Unlikely. Would mean can't store size of jump table. |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 73 | if (Range == UINT64_MAX) |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 74 | return CaseClusters; |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 75 | const uint64_t TotalRange = Range + 1; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 76 | |
| 77 | // Replace everything with a jump table |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 78 | auto *JumpTable = |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 79 | InstJumpTable::create(Func, TotalRange, Instr->getLabelDefault()); |
Andrew Scull | 016c56d | 2015-07-23 14:31:12 -0700 | [diff] [blame] | 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) |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 84 | JumpTable->addTarget(I - MinValue, Case.Target); |
| 85 | JumpTable->addTarget(Case.High - MinValue, Case.Target); |
| 86 | Case.Target->setNeedsAlignment(); |
Andrew Scull | 016c56d | 2015-07-23 14:31:12 -0700 | [diff] [blame] | 87 | } |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 88 | Func->addJumpTable(JumpTable); |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 89 | |
| 90 | CaseClusters.clear(); |
| 91 | CaseClusters.emplace_back(MinValue, MaxValue, JumpTable); |
| 92 | |
| 93 | return CaseClusters; |
| 94 | } |
| 95 | |
| 96 | bool CaseCluster::tryAppend(const CaseCluster &New) { |
| 97 | // Can only append ranges with the same target and are adjacent |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 98 | const bool CanAppend = |
| 99 | this->Target == New.Target && this->High + 1 == New.Low; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 100 | if (CanAppend) |
| 101 | this->High = New.High; |
| 102 | return CanAppend; |
| 103 | } |
| 104 | |
| 105 | } // end of namespace Ice |