llvm/SandboxIR/Region.h

0001 //===- Region.h -------------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_SANDBOXIR_REGION_H
0010 #define LLVM_SANDBOXIR_REGION_H
0011
0012 #include <memory>
0013
0014 #include "llvm/ADT/SetVector.h"
0015 #include "llvm/ADT/iterator_range.h"
0016 #include "llvm/Analysis/TargetTransformInfo.h"
0017 #include "llvm/SandboxIR/Instruction.h"
0018 #include "llvm/Support/raw_ostream.h"
0019
0020 namespace llvm::sandboxir {
0021
0022 class Region;
0023
0024 class ScoreBoard {
0025   const Region &Rgn;
0026   TargetTransformInfo &TTI;
0027   constexpr static TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
0028   /// The cost of all instructions added to the region.
0029   InstructionCost AfterCost = 0;
0030   /// The cost of all instructions that got removed and replaced by new ones.
0031   InstructionCost BeforeCost = 0;
0032   /// Helper for both add() and remove(). \Returns the TTI cost of \p I.
0033   InstructionCost getCost(Instruction *I) const;
0034   /// No need to allow copies.
0035   ScoreBoard(const ScoreBoard &) = delete;
0036   const ScoreBoard &operator=(const ScoreBoard &) = delete;
0037
0038 public:
0039   ScoreBoard(Region &Rgn, TargetTransformInfo &TTI) : Rgn(Rgn), TTI(TTI) {}
0040   /// Mark \p I as a newly added instruction to the region.
0041   void add(Instruction *I) { AfterCost += getCost(I); }
0042   /// Mark \p I as a deleted instruction from the region.
0043   void remove(Instruction *I);
0044   /// \Returns the cost of the newly added instructions.
0045   InstructionCost getAfterCost() const { return AfterCost; }
0046   /// \Returns the cost of the Removed instructions.
0047   InstructionCost getBeforeCost() const { return BeforeCost; }
0048
0049 #ifndef NDEBUG
0050   void dump(raw_ostream &OS) const {
0051     OS << "BeforeCost: " << BeforeCost << "\n";
0052     OS << "AfterCost:  " << AfterCost << "\n";
0053   }
0054   LLVM_DUMP_METHOD void dump() const;
0055 #endif // NDEBUG
0056 };
0057
0058 /// The main job of the Region is to point to new instructions generated by
0059 /// vectorization passes. It is the unit that RegionPasses operate on with their
0060 /// runOnRegion() function.
0061 ///
0062 /// The region allows us to stack transformations horizontally, meaning that
0063 /// each transformation operates on a single region and the resulting region is
0064 /// the input to the next transformation, as opposed to vertically, which is the
0065 /// common way of applying a transformation across the whole function. This
0066 /// enables us to check for profitability and decide whether we accept or
0067 /// rollback at a region granularity, which is much better than doing this at
0068 /// the function level.
0069 ///
0070 //  Traditional approach: transformations applied vertically for the whole
0071 //  function
0072 //    F
0073 //  +----+
0074 //  |    |
0075 //  |    |
0076 //  |    | -> Transform1 ->  ... -> TransformN -> Check Cost
0077 //  |    |
0078 //  |    |
0079 //  +----+
0080 //
0081 //  Region-based approach: transformations applied horizontally, for each Region
0082 //    F
0083 //  +----+
0084 //  |Rgn1| -> Transform1 ->  ... -> TransformN -> Check Cost
0085 //  |    |
0086 //  |Rgn2| -> Transform1 ->  ... -> TransformN -> Check Cost
0087 //  |    |
0088 //  |Rgn3| -> Transform1 ->  ... -> TransformN -> Check Cost
0089 //  +----+
0090
0091 class Region {
0092   /// All the instructions in the Region. Only new instructions generated during
0093   /// vectorization are part of the Region.
0094   SetVector<Instruction *> Insts;
0095
0096   /// MDNode that we'll use to mark instructions as being part of the region.
0097   MDNode *RegionMDN;
0098   static constexpr const char *MDKind = "sandboxvec";
0099   static constexpr const char *RegionStr = "sandboxregion";
0100
0101   Context &Ctx;
0102   /// Keeps track of cost of instructions added and removed.
0103   ScoreBoard Scoreboard;
0104
0105   /// ID (for later deregistration) of the "create instruction" callback.
0106   Context::CallbackID CreateInstCB;
0107   /// ID (for later deregistration) of the "erase instruction" callback.
0108   Context::CallbackID EraseInstCB;
0109
0110   // TODO: Add cost modeling.
0111   // TODO: Add a way to encode/decode region info to/from metadata.
0112
0113 public:
0114   Region(Context &Ctx, TargetTransformInfo &TTI);
0115   ~Region();
0116
0117   Context &getContext() const { return Ctx; }
0118
0119   /// Adds I to the set.
0120   void add(Instruction *I);
0121   /// Removes I from the set.
0122   void remove(Instruction *I);
0123   /// Returns true if I is in the Region.
0124   bool contains(Instruction *I) const { return Insts.contains(I); }
0125   /// Returns true if the Region has no instructions.
0126   bool empty() const { return Insts.empty(); }
0127
0128   using iterator = decltype(Insts.begin());
0129   iterator begin() { return Insts.begin(); }
0130   iterator end() { return Insts.end(); }
0131   iterator_range<iterator> insts() { return make_range(begin(), end()); }
0132
0133   static SmallVector<std::unique_ptr<Region>>
0134   createRegionsFromMD(Function &F, TargetTransformInfo &TTI);
0135   /// \Returns the ScoreBoard data structure that keeps track of instr costs.
0136   const ScoreBoard &getScoreboard() const { return Scoreboard; }
0137
0138 #ifndef NDEBUG
0139   /// This is an expensive check, meant for testing.
0140   bool operator==(const Region &Other) const;
0141   bool operator!=(const Region &other) const { return !(*this == other); }
0142
0143   void dump(raw_ostream &OS) const;
0144   void dump() const;
0145   friend raw_ostream &operator<<(raw_ostream &OS, const Region &Rgn) {
0146     Rgn.dump(OS);
0147     return OS;
0148   }
0149 #endif
0150 };
0151
0152 } // namespace llvm::sandboxir
0153
0154 #endif // LLVM_SANDBOXIR_REGION_H