Home | History | Annotate | Download | only in src 
      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
     11 /// \brief Helpers for switch lowering.
     12 ///
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef SUBZERO_SRC_ICESWITCHLOWERING_H
     16 #define SUBZERO_SRC_ICESWITCHLOWERING_H
     17 
     18 #include "IceDefs.h"
     19 #include "IceStringPool.h"
     20 
     21 #include <string>
     22 
     23 namespace Ice {
     24 
     25 class CaseCluster;
     26 
     27 using CaseClusterArray = CfgVector<CaseCluster>;
     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.
     43   CaseCluster(uint64_t Value, CfgNode *Target)
     44       : Kind(Range), Low(Value), High(Value), Target(Target) {}
     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; }
     52   CfgNode *getTarget() const {
     53     assert(Kind == Range);
     54     return Target;
     55   }
     56   InstJumpTable *getJumpTable() const {
     57     assert(Kind == JumpTable);
     58     return JT;
     59   }
     60 
     61   bool isUnitRange() const { return Low == High; }
     62   bool isPairRange() const { return Low == High - 1; }
     63 
     64   /// Discover cases which can be clustered together and return the clusters
     65   /// ordered by case value.
     66   static CaseClusterArray clusterizeSwitch(Cfg *Func, const InstSwitch *Instr);
     67 
     68 private:
     69   CaseClusterKind Kind;
     70   uint64_t Low;
     71   uint64_t High;
     72   union {
     73     CfgNode *Target;   /// Target for a range.
     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 
     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.
     83 class JumpTableData {
     84   JumpTableData() = delete;
     85   JumpTableData &operator=(const JumpTableData &) = delete;
     86 
     87 public:
     88   using TargetList = std::vector<intptr_t>;
     89 
     90   JumpTableData(GlobalString Name, GlobalString FuncName, SizeT Id,
     91                 const TargetList &TargetOffsets)
     92       : Name(Name), FuncName(FuncName), Id(Id), TargetOffsets(TargetOffsets) {}
     93   JumpTableData(const JumpTableData &) = default;
     94   JumpTableData(JumpTableData &&) = default;
     95   JumpTableData &operator=(JumpTableData &&) = default;
     96 
     97   GlobalString getName() const { return Name; }
     98   GlobalString getFunctionName() const { return FuncName; }
     99   SizeT getId() const { return Id; }
    100   const TargetList &getTargetOffsets() const { return TargetOffsets; }
    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); }
    108 
    109 private:
    110   GlobalString Name;
    111   GlobalString FuncName;
    112   SizeT Id;
    113   TargetList TargetOffsets;
    114 };
    115 
    116 using JumpTableDataList = std::vector<JumpTableData>;
    117 
    118 } // end of namespace Ice
    119 
    120 #endif //  SUBZERO_SRC_ICESWITCHLOWERING_H
    121