Home | History | Annotate | Download | only in src 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #ifndef V8_HYDROGEN_GVN_H_
      6 #define V8_HYDROGEN_GVN_H_
      7 
      8 #include "src/hydrogen.h"
      9 #include "src/hydrogen-instructions.h"
     10 #include "src/compiler.h"
     11 #include "src/zone.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 
     16 // This class extends GVNFlagSet with additional "special" dynamic side effects,
     17 // which can be used to represent side effects that cannot be expressed using
     18 // the GVNFlags of an HInstruction. These special side effects are tracked by a
     19 // SideEffectsTracker (see below).
     20 class SideEffects V8_FINAL {
     21  public:
     22   static const int kNumberOfSpecials = 64 - kNumberOfFlags;
     23 
     24   SideEffects() : bits_(0) {
     25     ASSERT(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
     26   }
     27   explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {}
     28   bool IsEmpty() const { return bits_ == 0; }
     29   bool ContainsFlag(GVNFlag flag) const {
     30     return (bits_ & MaskFlag(flag)) != 0;
     31   }
     32   bool ContainsSpecial(int special) const {
     33     return (bits_ & MaskSpecial(special)) != 0;
     34   }
     35   bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; }
     36   void Add(SideEffects set) { bits_ |= set.bits_; }
     37   void AddSpecial(int special) { bits_ |= MaskSpecial(special); }
     38   void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); }
     39   void RemoveAll() { bits_ = 0; }
     40   uint64_t ToIntegral() const { return bits_; }
     41   void PrintTo(StringStream* stream) const;
     42 
     43  private:
     44   uint64_t MaskFlag(GVNFlag flag) const {
     45     return static_cast<uint64_t>(1) << static_cast<unsigned>(flag);
     46   }
     47   uint64_t MaskSpecial(int special) const {
     48     ASSERT(special >= 0);
     49     ASSERT(special < kNumberOfSpecials);
     50     return static_cast<uint64_t>(1) << static_cast<unsigned>(
     51         special + kNumberOfFlags);
     52   }
     53 
     54   uint64_t bits_;
     55 };
     56 
     57 
     58 // Tracks global variable and inobject field loads/stores in a fine grained
     59 // fashion, and represents them using the "special" dynamic side effects of the
     60 // SideEffects class (see above). This way unrelated global variable/inobject
     61 // field stores don't prevent hoisting and merging of global variable/inobject
     62 // field loads.
     63 class SideEffectsTracker V8_FINAL BASE_EMBEDDED {
     64  public:
     65   SideEffectsTracker() : num_global_vars_(0), num_inobject_fields_(0) {}
     66   SideEffects ComputeChanges(HInstruction* instr);
     67   SideEffects ComputeDependsOn(HInstruction* instr);
     68   void PrintSideEffectsTo(StringStream* stream, SideEffects side_effects) const;
     69 
     70  private:
     71   bool ComputeGlobalVar(Unique<Cell> cell, int* index);
     72   bool ComputeInobjectField(HObjectAccess access, int* index);
     73 
     74   static int GlobalVar(int index) {
     75     ASSERT(index >= 0);
     76     ASSERT(index < kNumberOfGlobalVars);
     77     return index;
     78   }
     79   static int InobjectField(int index) {
     80     ASSERT(index >= 0);
     81     ASSERT(index < kNumberOfInobjectFields);
     82     return index + kNumberOfGlobalVars;
     83   }
     84 
     85   // Track up to four global vars.
     86   static const int kNumberOfGlobalVars = 4;
     87   Unique<Cell> global_vars_[kNumberOfGlobalVars];
     88   int num_global_vars_;
     89 
     90   // Track up to n inobject fields.
     91   static const int kNumberOfInobjectFields =
     92       SideEffects::kNumberOfSpecials - kNumberOfGlobalVars;
     93   HObjectAccess inobject_fields_[kNumberOfInobjectFields];
     94   int num_inobject_fields_;
     95 };
     96 
     97 
     98 // Perform common subexpression elimination and loop-invariant code motion.
     99 class HGlobalValueNumberingPhase V8_FINAL : public HPhase {
    100  public:
    101   explicit HGlobalValueNumberingPhase(HGraph* graph);
    102 
    103   void Run();
    104 
    105  private:
    106   SideEffects CollectSideEffectsOnPathsToDominatedBlock(
    107       HBasicBlock* dominator,
    108       HBasicBlock* dominated);
    109   void AnalyzeGraph();
    110   void ComputeBlockSideEffects();
    111   void LoopInvariantCodeMotion();
    112   void ProcessLoopBlock(HBasicBlock* block,
    113                         HBasicBlock* before_loop,
    114                         SideEffects loop_kills);
    115   bool AllowCodeMotion();
    116   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
    117 
    118   SideEffectsTracker side_effects_tracker_;
    119   bool removed_side_effects_;
    120 
    121   // A map of block IDs to their side effects.
    122   ZoneList<SideEffects> block_side_effects_;
    123 
    124   // A map of loop header block IDs to their loop's side effects.
    125   ZoneList<SideEffects> loop_side_effects_;
    126 
    127   // Used when collecting side effects on paths from dominator to
    128   // dominated.
    129   BitVector visited_on_paths_;
    130 
    131   DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
    132 };
    133 
    134 } }  // namespace v8::internal
    135 
    136 #endif  // V8_HYDROGEN_GVN_H_
    137