js/src/jit/ValueNumbering.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef jit_ValueNumbering_h
   8 #define jit_ValueNumbering_h
   9
  10 #include "jit/JitAllocPolicy.h"
  11 #include "js/HashTable.h"
  12 #include "js/Vector.h"
  13
  14 namespace js {
  15 namespace jit {
  16
  17 class MDefinition;
  18 class MBasicBlock;
  19 class MIRGraph;
  20 class MPhi;
  21 class MIRGenerator;
  22 class MResumePoint;
  23
  24 class ValueNumberer {
  25   // Value numbering data.
  26   class VisibleValues {
  27     // Hash policy for ValueSet.
  28     struct ValueHasher {
  29       using Lookup = const MDefinition*;
  30       using Key = MDefinition*;
  31       static HashNumber hash(Lookup ins);
  32       static bool match(Key k, Lookup l);
  33       static void rekey(Key& k, Key newKey);
  34     };
  35
  36     typedef HashSet<MDefinition*, ValueHasher, JitAllocPolicy> ValueSet;
  37
  38     ValueSet set_;  // Set of visible values
  39
  40    public:
  41     explicit VisibleValues(TempAllocator& alloc);
  42
  43     using Ptr = ValueSet::Ptr;
  44     using AddPtr = ValueSet::AddPtr;
  45
  46     Ptr findLeader(const MDefinition* def) const;
  47     AddPtr findLeaderForAdd(MDefinition* def);
  48     [[nodiscard]] bool add(AddPtr p, MDefinition* def);
  49     void overwrite(AddPtr p, MDefinition* def);
  50     void forget(const MDefinition* def);
  51     void clear();
  52 #ifdef DEBUG
  53     bool has(const MDefinition* def) const;
  54 #endif
  55   };
  56
  57   typedef Vector<MBasicBlock*, 4, JitAllocPolicy> BlockWorklist;
  58   typedef Vector<MDefinition*, 4, JitAllocPolicy> DefWorklist;
  59
  60   MIRGenerator* const mir_;
  61   MIRGraph& graph_;
  62   VisibleValues values_;           // Numbered values
  63   DefWorklist deadDefs_;           // Worklist for deleting values
  64   BlockWorklist remainingBlocks_;  // Blocks remaining with fewer preds
  65   MDefinition* nextDef_;           // The next definition; don't discard
  66   size_t totalNumVisited_;         // The number of blocks visited
  67   bool rerun_;                     // Should we run another GVN iteration?
  68   bool blocksRemoved_;             // Have any blocks been removed?
  69   bool updateAliasAnalysis_;       // Do we care about AliasAnalysis?
  70   bool dependenciesBroken_;        // Have we broken AliasAnalysis?
  71   bool hasOSRFixups_;              // Have we created any OSR fixup blocks?
  72
  73   enum ImplicitUseOption { DontSetImplicitUse, SetImplicitUse };
  74   enum class AllowEffectful : bool { No, Yes };
  75
  76   [[nodiscard]] bool handleUseReleased(MDefinition* def,
  77                                        ImplicitUseOption implicitUseOption);
  78   [[nodiscard]] bool discardDefsRecursively(
  79       MDefinition* def, AllowEffectful allowEffectful = AllowEffectful::No);
  80   [[nodiscard]] bool releaseResumePointOperands(MResumePoint* resume);
  81   [[nodiscard]] bool releaseAndRemovePhiOperands(MPhi* phi);
  82   [[nodiscard]] bool releaseOperands(MDefinition* def);
  83   [[nodiscard]] bool discardDef(
  84       MDefinition* def, AllowEffectful allowEffectful = AllowEffectful::No);
  85   [[nodiscard]] bool processDeadDefs();
  86
  87   [[nodiscard]] bool fixupOSROnlyLoop(MBasicBlock* block);
  88   [[nodiscard]] bool removePredecessorAndDoDCE(MBasicBlock* block,
  89                                                MBasicBlock* pred,
  90                                                size_t predIndex);
  91   [[nodiscard]] bool removePredecessorAndCleanUp(MBasicBlock* block,
  92                                                  MBasicBlock* pred);
  93
  94   MDefinition* simplified(MDefinition* def) const;
  95   MDefinition* leader(MDefinition* def);
  96   bool hasLeader(const MPhi* phi, const MBasicBlock* phiBlock) const;
  97   bool loopHasOptimizablePhi(MBasicBlock* header) const;
  98
  99   [[nodiscard]] bool visitDefinition(MDefinition* def);
 100   [[nodiscard]] bool visitControlInstruction(MBasicBlock* block);
 101   [[nodiscard]] bool visitUnreachableBlock(MBasicBlock* block);
 102   [[nodiscard]] bool visitBlock(MBasicBlock* block);
 103   [[nodiscard]] bool visitDominatorTree(MBasicBlock* root);
 104   [[nodiscard]] bool visitGraph();
 105
 106   [[nodiscard]] bool insertOSRFixups();
 107   [[nodiscard]] bool cleanupOSRFixups();
 108
 109  public:
 110   ValueNumberer(MIRGenerator* mir, MIRGraph& graph);
 111
 112   enum UpdateAliasAnalysisFlag { DontUpdateAliasAnalysis, UpdateAliasAnalysis };
 113
 114   // Optimize the graph, performing expression simplification and
 115   // canonicalization, eliminating statically fully-redundant expressions,
 116   // deleting dead instructions, and removing unreachable blocks.
 117   [[nodiscard]] bool run(UpdateAliasAnalysisFlag updateAliasAnalysis);
 118 };
 119
 120 }  // namespace jit
 121 }  // namespace js
 122
 123 #endif /* jit_ValueNumbering_h */