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 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 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
