| OLD | NEW |
| 1 //===- subzero/src/IceSwitchLowering.cpp - Switch lowering ----------------===// | 1 //===- subzero/src/IceSwitchLowering.cpp - Switch lowering ----------------===// |
| 2 // | 2 // |
| 3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
| 4 // | 4 // |
| 5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
| 6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
| 7 // | 7 // |
| 8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
| 9 /// | 9 /// |
| 10 /// \file | 10 /// \file |
| 11 /// \brief Implements platform independent analysis of switch cases to improve | 11 /// \brief Implements platform independent analysis of switch cases to improve |
| 12 /// the generated code. | 12 /// the generated code. |
| 13 /// | 13 /// |
| 14 //===----------------------------------------------------------------------===// | 14 //===----------------------------------------------------------------------===// |
| 15 #include "IceSwitchLowering.h" | 15 #include "IceSwitchLowering.h" |
| 16 | 16 |
| 17 #include "IceCfgNode.h" | 17 #include "IceCfgNode.h" |
| 18 #include "IceTargetLowering.h" | 18 #include "IceTargetLowering.h" |
| 19 | 19 |
| 20 #include <algorithm> | 20 #include <algorithm> |
| 21 | 21 |
| 22 namespace Ice { | 22 namespace Ice { |
| 23 | 23 |
| 24 CaseClusterArray CaseCluster::clusterizeSwitch(Cfg *Func, | 24 CaseClusterArray CaseCluster::clusterizeSwitch(Cfg *Func, |
| 25 const InstSwitch *Inst) { | 25 const InstSwitch *Instr) { |
| 26 CaseClusterArray CaseClusters; | 26 CaseClusterArray CaseClusters; |
| 27 | 27 |
| 28 // Load the cases | 28 // Load the cases |
| 29 SizeT NumCases = Inst->getNumCases(); | 29 SizeT NumCases = Instr->getNumCases(); |
| 30 CaseClusters.reserve(NumCases); | 30 CaseClusters.reserve(NumCases); |
| 31 for (SizeT I = 0; I < NumCases; ++I) | 31 for (SizeT I = 0; I < NumCases; ++I) |
| 32 CaseClusters.emplace_back(Inst->getValue(I), Inst->getLabel(I)); | 32 CaseClusters.emplace_back(Instr->getValue(I), Instr->getLabel(I)); |
| 33 | 33 |
| 34 // Sort the cases | 34 // Sort the cases |
| 35 std::sort(CaseClusters.begin(), CaseClusters.end(), | 35 std::sort(CaseClusters.begin(), CaseClusters.end(), |
| 36 [](const CaseCluster &x, const CaseCluster &y) { | 36 [](const CaseCluster &x, const CaseCluster &y) { |
| 37 return x.High < y.Low; | 37 return x.High < y.Low; |
| 38 }); | 38 }); |
| 39 | 39 |
| 40 // Merge adjacent case ranges | 40 // Merge adjacent case ranges |
| 41 auto Active = CaseClusters.begin(); | 41 auto Active = CaseClusters.begin(); |
| 42 std::for_each(Active + 1, CaseClusters.end(), | 42 std::for_each(Active + 1, CaseClusters.end(), |
| (...skipping 25 matching lines...) Expand all Loading... |
| 68 // Might be too sparse for the jump table | 68 // Might be too sparse for the jump table |
| 69 if (NumCases * 2 <= TotalRange) | 69 if (NumCases * 2 <= TotalRange) |
| 70 return CaseClusters; | 70 return CaseClusters; |
| 71 // Unlikely. Would mean can't store size of jump table. | 71 // Unlikely. Would mean can't store size of jump table. |
| 72 if (TotalRange == UINT64_MAX) | 72 if (TotalRange == UINT64_MAX) |
| 73 return CaseClusters; | 73 return CaseClusters; |
| 74 ++TotalRange; | 74 ++TotalRange; |
| 75 | 75 |
| 76 // Replace everything with a jump table | 76 // Replace everything with a jump table |
| 77 InstJumpTable *JumpTable = | 77 InstJumpTable *JumpTable = |
| 78 InstJumpTable::create(Func, TotalRange, Inst->getLabelDefault()); | 78 InstJumpTable::create(Func, TotalRange, Instr->getLabelDefault()); |
| 79 for (const CaseCluster &Case : CaseClusters) { | 79 for (const CaseCluster &Case : CaseClusters) { |
| 80 // Case.High could be UINT64_MAX which makes the loop awkward. Unwrap the | 80 // Case.High could be UINT64_MAX which makes the loop awkward. Unwrap the |
| 81 // last iteration to avoid wrap around problems. | 81 // last iteration to avoid wrap around problems. |
| 82 for (uint64_t I = Case.Low; I < Case.High; ++I) | 82 for (uint64_t I = Case.Low; I < Case.High; ++I) |
| 83 JumpTable->addTarget(I - MinValue, Case.Target); | 83 JumpTable->addTarget(I - MinValue, Case.Target); |
| 84 JumpTable->addTarget(Case.High - MinValue, Case.Target); | 84 JumpTable->addTarget(Case.High - MinValue, Case.Target); |
| 85 Case.Target->setNeedsAlignment(); | 85 Case.Target->setNeedsAlignment(); |
| 86 } | 86 } |
| 87 Func->addJumpTable(JumpTable); | 87 Func->addJumpTable(JumpTable); |
| 88 | 88 |
| 89 CaseClusters.clear(); | 89 CaseClusters.clear(); |
| 90 CaseClusters.emplace_back(MinValue, MaxValue, JumpTable); | 90 CaseClusters.emplace_back(MinValue, MaxValue, JumpTable); |
| 91 | 91 |
| 92 return CaseClusters; | 92 return CaseClusters; |
| 93 } | 93 } |
| 94 | 94 |
| 95 bool CaseCluster::tryAppend(const CaseCluster &New) { | 95 bool CaseCluster::tryAppend(const CaseCluster &New) { |
| 96 // Can only append ranges with the same target and are adjacent | 96 // Can only append ranges with the same target and are adjacent |
| 97 bool CanAppend = this->Target == New.Target && this->High + 1 == New.Low; | 97 bool CanAppend = this->Target == New.Target && this->High + 1 == New.Low; |
| 98 if (CanAppend) | 98 if (CanAppend) |
| 99 this->High = New.High; | 99 this->High = New.High; |
| 100 return CanAppend; | 100 return CanAppend; |
| 101 } | 101 } |
| 102 | 102 |
| 103 } // end of namespace Ice | 103 } // end of namespace Ice |
| OLD | NEW |