Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceSwitchLowering.h - Switch lowering --------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 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 Helpers for switch lowering. |
| 12 | /// |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef SUBZERO_SRC_ICESWITCHLOWERING_H |
| 16 | #define SUBZERO_SRC_ICESWITCHLOWERING_H |
| 17 | |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 18 | #include "IceDefs.h" |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 19 | #include "IceStringPool.h" |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 20 | |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 21 | #include <string> |
| 22 | |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 23 | namespace Ice { |
| 24 | |
| 25 | class CaseCluster; |
| 26 | |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 27 | using CaseClusterArray = CfgVector<CaseCluster>; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 28 | |
| 29 | /// A cluster of cases can be tested by a common method during switch lowering. |
| 30 | class CaseCluster { |
| 31 | CaseCluster() = delete; |
| 32 | |
| 33 | public: |
| 34 | enum CaseClusterKind { |
| 35 | Range, /// Numerically adjacent case values with same target. |
| 36 | JumpTable, /// Different targets and possibly sparse. |
| 37 | }; |
| 38 | |
| 39 | CaseCluster(const CaseCluster &) = default; |
| 40 | CaseCluster &operator=(const CaseCluster &) = default; |
| 41 | |
| 42 | /// Create a cluster of a single case represented by a unitary range. |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 43 | CaseCluster(uint64_t Value, CfgNode *Target) |
| 44 | : Kind(Range), Low(Value), High(Value), Target(Target) {} |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 45 | /// Create a case consisting of a jump table. |
| 46 | CaseCluster(uint64_t Low, uint64_t High, InstJumpTable *JT) |
| 47 | : Kind(JumpTable), Low(Low), High(High), JT(JT) {} |
| 48 | |
| 49 | CaseClusterKind getKind() const { return Kind; } |
| 50 | uint64_t getLow() const { return Low; } |
| 51 | uint64_t getHigh() const { return High; } |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 52 | CfgNode *getTarget() const { |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 53 | assert(Kind == Range); |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 54 | return Target; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 55 | } |
| 56 | InstJumpTable *getJumpTable() const { |
| 57 | assert(Kind == JumpTable); |
| 58 | return JT; |
| 59 | } |
| 60 | |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 61 | bool isUnitRange() const { return Low == High; } |
| 62 | bool isPairRange() const { return Low == High - 1; } |
| 63 | |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 64 | /// Discover cases which can be clustered together and return the clusters |
| 65 | /// ordered by case value. |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 66 | static CaseClusterArray clusterizeSwitch(Cfg *Func, const InstSwitch *Instr); |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 67 | |
| 68 | private: |
| 69 | CaseClusterKind Kind; |
| 70 | uint64_t Low; |
| 71 | uint64_t High; |
| 72 | union { |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 73 | CfgNode *Target; /// Target for a range. |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 74 | InstJumpTable *JT; /// Jump table targets. |
| 75 | }; |
| 76 | |
| 77 | /// Try and append a cluster returning whether or not it was successful. |
| 78 | bool tryAppend(const CaseCluster &New); |
| 79 | }; |
| 80 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 81 | /// Store the jump table data so that it can be emitted later in the correct ELF |
| 82 | /// section once the offsets from the start of the function are known. |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 83 | class JumpTableData { |
| 84 | JumpTableData() = delete; |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 85 | JumpTableData &operator=(const JumpTableData &) = delete; |
| 86 | |
| 87 | public: |
David Sehr | 0fe6b54 | 2015-11-19 21:47:15 -0800 | [diff] [blame] | 88 | using TargetList = std::vector<intptr_t>; |
| 89 | |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 90 | JumpTableData(GlobalString Name, GlobalString FuncName, SizeT Id, |
David Sehr | 0fe6b54 | 2015-11-19 21:47:15 -0800 | [diff] [blame] | 91 | const TargetList &TargetOffsets) |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 92 | : Name(Name), FuncName(FuncName), Id(Id), TargetOffsets(TargetOffsets) {} |
Andrew Scull | 1eda90a | 2015-08-04 17:03:19 -0700 | [diff] [blame] | 93 | JumpTableData(const JumpTableData &) = default; |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 94 | JumpTableData(JumpTableData &&) = default; |
Andrew Scull | 1eda90a | 2015-08-04 17:03:19 -0700 | [diff] [blame] | 95 | JumpTableData &operator=(JumpTableData &&) = default; |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 96 | |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 97 | GlobalString getName() const { return Name; } |
| 98 | GlobalString getFunctionName() const { return FuncName; } |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 99 | SizeT getId() const { return Id; } |
David Sehr | 0fe6b54 | 2015-11-19 21:47:15 -0800 | [diff] [blame] | 100 | const TargetList &getTargetOffsets() const { return TargetOffsets; } |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 101 | static std::string createSectionName(const GlobalString Name) { |
| 102 | if (Name.hasStdString()) { |
| 103 | return Name.toString() + "$jumptable"; |
| 104 | } |
| 105 | return std::to_string(Name.getID()) + "$jumptable"; |
| 106 | } |
| 107 | std::string getSectionName() const { return createSectionName(FuncName); } |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 108 | |
| 109 | private: |
John Porto | 0307721 | 2016-04-05 06:30:21 -0700 | [diff] [blame] | 110 | GlobalString Name; |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 111 | GlobalString FuncName; |
Andrew Scull | 1eda90a | 2015-08-04 17:03:19 -0700 | [diff] [blame] | 112 | SizeT Id; |
David Sehr | 0fe6b54 | 2015-11-19 21:47:15 -0800 | [diff] [blame] | 113 | TargetList TargetOffsets; |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 114 | }; |
| 115 | |
| 116 | using JumpTableDataList = std::vector<JumpTableData>; |
| 117 | |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 118 | } // end of namespace Ice |
| 119 | |
| 120 | #endif // SUBZERO_SRC_ICESWITCHLOWERING_H |