js/src/jit/IonAnalysis.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_IonAnalysis_h
   8 #define jit_IonAnalysis_h
   9
  10 // This file declares various analysis passes that operate on MIR.
  11
  12 #include <stddef.h>
  13 #include <stdint.h>
  14
  15 #include "jit/IonTypes.h"
  16 #include "jit/JitAllocPolicy.h"
  17 #include "js/TypeDecls.h"
  18 #include "js/Utility.h"
  19 #include "js/Vector.h"
  20
  21 namespace js {
  22
  23 class JS_PUBLIC_API GenericPrinter;
  24 class PlainObject;
  25
  26 namespace jit {
  27
  28 class MBasicBlock;
  29 class MCompare;
  30 class MDefinition;
  31 class MIRGenerator;
  32 class MIRGraph;
  33 class MTest;
  34
  35 [[nodiscard]] bool PruneUnusedBranches(MIRGenerator* mir, MIRGraph& graph);
  36
  37 [[nodiscard]] bool FoldTests(MIRGraph& graph);
  38
  39 [[nodiscard]] bool FoldEmptyBlocks(MIRGraph& graph);
  40
  41 [[nodiscard]] bool SplitCriticalEdges(MIRGraph& graph);
  42
  43 [[nodiscard]] bool OptimizeIteratorIndices(MIRGenerator* mir, MIRGraph& graph);
  44
  45 bool IsUint32Type(const MDefinition* def);
  46
  47 enum Observability { ConservativeObservability, AggressiveObservability };
  48
  49 [[nodiscard]] bool EliminatePhis(MIRGenerator* mir, MIRGraph& graph,
  50                                  Observability observe);
  51
  52 size_t MarkLoopBlocks(MIRGraph& graph, MBasicBlock* header, bool* canOsr);
  53
  54 void UnmarkLoopBlocks(MIRGraph& graph, MBasicBlock* header);
  55
  56 [[nodiscard]] bool MakeLoopsContiguous(MIRGraph& graph);
  57
  58 [[nodiscard]] bool EliminateTriviallyDeadResumePointOperands(MIRGenerator* mir,
  59                                                              MIRGraph& graph);
  60
  61 [[nodiscard]] bool EliminateDeadResumePointOperands(MIRGenerator* mir,
  62                                                     MIRGraph& graph);
  63
  64 [[nodiscard]] bool EliminateDeadCode(MIRGenerator* mir, MIRGraph& graph);
  65
  66 [[nodiscard]] bool FoldLoadsWithUnbox(MIRGenerator* mir, MIRGraph& graph);
  67
  68 [[nodiscard]] bool ApplyTypeInformation(MIRGenerator* mir, MIRGraph& graph);
  69
  70 void RenumberBlocks(MIRGraph& graph);
  71
  72 [[nodiscard]] bool AccountForCFGChanges(MIRGenerator* mir, MIRGraph& graph,
  73                                         bool updateAliasAnalysis,
  74                                         bool underValueNumberer = false);
  75
  76 [[nodiscard]] bool RemoveUnmarkedBlocks(MIRGenerator* mir, MIRGraph& graph,
  77                                         uint32_t numMarkedBlocks);
  78
  79 void ClearDominatorTree(MIRGraph& graph);
  80
  81 [[nodiscard]] bool BuildDominatorTree(MIRGraph& graph);
  82
  83 [[nodiscard]] bool BuildPhiReverseMapping(MIRGraph& graph);
  84
  85 void AssertBasicGraphCoherency(MIRGraph& graph, bool force = false);
  86
  87 void AssertGraphCoherency(MIRGraph& graph, bool force = false);
  88
  89 void AssertExtendedGraphCoherency(MIRGraph& graph,
  90                                   bool underValueNumberer = false,
  91                                   bool force = false);
  92
  93 [[nodiscard]] bool EliminateRedundantChecks(MIRGraph& graph);
  94
  95 [[nodiscard]] bool EliminateRedundantShapeGuards(MIRGraph& graph);
  96
  97 [[nodiscard]] bool EliminateRedundantGCBarriers(MIRGraph& graph);
  98
  99 [[nodiscard]] bool AddKeepAliveInstructions(MIRGraph& graph);
 100
 101 [[nodiscard]] bool MarkLoadsUsedAsPropertyKeys(MIRGraph& graph);
 102
 103 // Simple linear sum of the form 'n' or 'x + n'.
 104 struct SimpleLinearSum {
 105   MDefinition* term;
 106   int32_t constant;
 107
 108   SimpleLinearSum(MDefinition* term, int32_t constant)
 109       : term(term), constant(constant) {}
 110 };
 111
 112 // Math done in a Linear sum can either be in a modulo space, in which case
 113 // overflow are wrapped around, or they can be computed in the integer-space in
 114 // which case we have to check that no overflow can happen when summing
 115 // constants.
 116 //
 117 // When the caller ignores which space it is, the definition would be used to
 118 // deduce it.
 119 enum class MathSpace { Modulo, Infinite, Unknown };
 120
 121 SimpleLinearSum ExtractLinearSum(MDefinition* ins,
 122                                  MathSpace space = MathSpace::Unknown,
 123                                  int32_t recursionDepth = 0);
 124
 125 [[nodiscard]] bool ExtractLinearInequality(MTest* test,
 126                                            BranchDirection direction,
 127                                            SimpleLinearSum* plhs,
 128                                            MDefinition** prhs,
 129                                            bool* plessEqual);
 130
 131 struct LinearTerm {
 132   MDefinition* term;
 133   int32_t scale;
 134
 135   LinearTerm(MDefinition* term, int32_t scale) : term(term), scale(scale) {}
 136 };
 137
 138 // General linear sum of the form 'x1*n1 + x2*n2 + ... + n'
 139 class LinearSum {
 140  public:
 141   explicit LinearSum(TempAllocator& alloc) : terms_(alloc), constant_(0) {}
 142
 143   LinearSum(const LinearSum& other)
 144       : terms_(other.terms_.allocPolicy()), constant_(other.constant_) {
 145     AutoEnterOOMUnsafeRegion oomUnsafe;
 146     if (!terms_.appendAll(other.terms_)) {
 147       oomUnsafe.crash("LinearSum::LinearSum");
 148     }
 149   }
 150
 151   // These return false on an integer overflow, and afterwards the sum must
 152   // not be used.
 153   [[nodiscard]] bool multiply(int32_t scale);
 154   [[nodiscard]] bool add(const LinearSum& other, int32_t scale = 1);
 155   [[nodiscard]] bool add(SimpleLinearSum other, int32_t scale = 1);
 156   [[nodiscard]] bool add(MDefinition* term, int32_t scale);
 157   [[nodiscard]] bool add(int32_t constant);
 158
 159   // Unlike the above function, on failure this leaves the sum unchanged and
 160   // it can still be used.
 161   [[nodiscard]] bool divide(uint32_t scale);
 162
 163   int32_t constant() const { return constant_; }
 164   size_t numTerms() const { return terms_.length(); }
 165   LinearTerm term(size_t i) const { return terms_[i]; }
 166   void replaceTerm(size_t i, MDefinition* def) { terms_[i].term = def; }
 167
 168   void dump(GenericPrinter& out) const;
 169   void dump() const;
 170
 171  private:
 172   Vector<LinearTerm, 2, JitAllocPolicy> terms_;
 173   int32_t constant_;
 174 };
 175
 176 // Convert all components of a linear sum (except the constant)
 177 // and add any new instructions to the end of block.
 178 MDefinition* ConvertLinearSum(TempAllocator& alloc, MBasicBlock* block,
 179                               const LinearSum& sum, BailoutKind bailoutKind);
 180
 181 bool DeadIfUnused(const MDefinition* def);
 182 bool DeadIfUnusedAllowEffectful(const MDefinition* def);
 183
 184 bool IsDiscardable(const MDefinition* def);
 185 bool IsDiscardableAllowEffectful(const MDefinition* def);
 186
 187 class CompileInfo;
 188 void DumpMIRExpressions(GenericPrinter& out, MIRGraph& graph,
 189                         const CompileInfo& info, const char* phase);
 190 void DumpMIRDefinition(GenericPrinter& out, MDefinition* def);
 191
 192 }  // namespace jit
 193 }  // namespace js
 194
 195 #endif /* jit_IonAnalysis_h */