Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       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             : 
      13             : namespace js {
      14             : namespace jit {
      15             : 
      16             : class MDefinition;
      17             : class MBasicBlock;
      18             : class MIRGraph;
      19             : class MPhi;
      20             : class MIRGenerator;
      21             : class MResumePoint;
      22             : 
      23           8 : class ValueNumberer
      24             : {
      25             :     // Value numbering data.
      26           8 :     class VisibleValues
      27             :     {
      28             :         // Hash policy for ValueSet.
      29             :         struct ValueHasher
      30             :         {
      31             :             typedef const MDefinition* Lookup;
      32             :             typedef MDefinition* Key;
      33             :             static HashNumber hash(Lookup ins);
      34             :             static bool match(Key k, Lookup l);
      35             :             static void rekey(Key& k, Key newKey);
      36             :         };
      37             : 
      38             :         typedef HashSet<MDefinition*, ValueHasher, JitAllocPolicy> ValueSet;
      39             : 
      40             :         ValueSet set_;        // Set of visible values
      41             : 
      42             :       public:
      43             :         explicit VisibleValues(TempAllocator& alloc);
      44             :         MOZ_MUST_USE bool init();
      45             : 
      46             :         typedef ValueSet::Ptr Ptr;
      47             :         typedef ValueSet::AddPtr AddPtr;
      48             : 
      49             :         Ptr findLeader(const MDefinition* def) const;
      50             :         AddPtr findLeaderForAdd(MDefinition* def);
      51             :         MOZ_MUST_USE bool add(AddPtr p, MDefinition* def);
      52             :         void overwrite(AddPtr p, MDefinition* def);
      53             :         void forget(const MDefinition* def);
      54             :         void clear();
      55             : #ifdef DEBUG
      56             :         bool has(const MDefinition* def) const;
      57             : #endif
      58             :     };
      59             : 
      60             :     typedef Vector<MBasicBlock*, 4, JitAllocPolicy> BlockWorklist;
      61             :     typedef Vector<MDefinition*, 4, JitAllocPolicy> DefWorklist;
      62             : 
      63             :     MIRGenerator* const mir_;
      64             :     MIRGraph& graph_;
      65             :     VisibleValues values_;            // Numbered values
      66             :     DefWorklist deadDefs_;            // Worklist for deleting values
      67             :     BlockWorklist remainingBlocks_;   // Blocks remaining with fewer preds
      68             :     MDefinition* nextDef_;            // The next definition; don't discard
      69             :     size_t totalNumVisited_;          // The number of blocks visited
      70             :     bool rerun_;                      // Should we run another GVN iteration?
      71             :     bool blocksRemoved_;              // Have any blocks been removed?
      72             :     bool updateAliasAnalysis_;        // Do we care about AliasAnalysis?
      73             :     bool dependenciesBroken_;         // Have we broken AliasAnalysis?
      74             :     bool hasOSRFixups_;               // Have we created any OSR fixup blocks?
      75             : 
      76             :     enum UseRemovedOption {
      77             :         DontSetUseRemoved,
      78             :         SetUseRemoved
      79             :     };
      80             : 
      81             :     MOZ_MUST_USE bool handleUseReleased(MDefinition* def, UseRemovedOption useRemovedOption);
      82             :     MOZ_MUST_USE bool discardDefsRecursively(MDefinition* def);
      83             :     MOZ_MUST_USE bool releaseResumePointOperands(MResumePoint* resume);
      84             :     MOZ_MUST_USE bool releaseAndRemovePhiOperands(MPhi* phi);
      85             :     MOZ_MUST_USE bool releaseOperands(MDefinition* def);
      86             :     MOZ_MUST_USE bool discardDef(MDefinition* def);
      87             :     MOZ_MUST_USE bool processDeadDefs();
      88             : 
      89             :     MOZ_MUST_USE bool fixupOSROnlyLoop(MBasicBlock* block, MBasicBlock* backedge);
      90             :     MOZ_MUST_USE bool removePredecessorAndDoDCE(MBasicBlock* block, MBasicBlock* pred,
      91             :                                                 size_t predIndex);
      92             :     MOZ_MUST_USE bool removePredecessorAndCleanUp(MBasicBlock* block, 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             :     MOZ_MUST_USE bool visitDefinition(MDefinition* def);
     100             :     MOZ_MUST_USE bool visitControlInstruction(MBasicBlock* block, const MBasicBlock* root);
     101             :     MOZ_MUST_USE bool visitUnreachableBlock(MBasicBlock* block);
     102             :     MOZ_MUST_USE bool visitBlock(MBasicBlock* block, const MBasicBlock* root);
     103             :     MOZ_MUST_USE bool visitDominatorTree(MBasicBlock* root);
     104             :     MOZ_MUST_USE bool visitGraph();
     105             : 
     106             :     MOZ_MUST_USE bool insertOSRFixups();
     107             :     MOZ_MUST_USE bool cleanupOSRFixups();
     108             : 
     109             :   public:
     110             :     ValueNumberer(MIRGenerator* mir, MIRGraph& graph);
     111             :     MOZ_MUST_USE bool init();
     112             : 
     113             :     enum UpdateAliasAnalysisFlag {
     114             :         DontUpdateAliasAnalysis,
     115             :         UpdateAliasAnalysis
     116             :     };
     117             : 
     118             :     // Optimize the graph, performing expression simplification and
     119             :     // canonicalization, eliminating statically fully-redundant expressions,
     120             :     // deleting dead instructions, and removing unreachable blocks.
     121             :     MOZ_MUST_USE bool run(UpdateAliasAnalysisFlag updateAliasAnalysis);
     122             : };
     123             : 
     124             : } // namespace jit
     125             : } // namespace js
     126             : 
     127             : #endif /* jit_ValueNumbering_h */