src/hydrogen-gvn.h

   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 <iosfwd>
   9
  10 #include "src/hydrogen.h"
  11 #include "src/hydrogen-instructions.h"
  12 #include "src/zone.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16
  17 // This class extends GVNFlagSet with additional "special" dynamic side effects,
  18 // which can be used to represent side effects that cannot be expressed using
  19 // the GVNFlags of an HInstruction. These special side effects are tracked by a
  20 // SideEffectsTracker (see below).
  21 class SideEffects final {
  22  public:
  23   static const int kNumberOfSpecials = 64 - kNumberOfFlags;
  24
  25   SideEffects() : bits_(0) {
  26     DCHECK(kNumberOfFlags + kNumberOfSpecials == sizeof(bits_) * CHAR_BIT);
  27   }
  28   explicit SideEffects(GVNFlagSet flags) : bits_(flags.ToIntegral()) {}
  29   bool IsEmpty() const { return bits_ == 0; }
  30   bool ContainsFlag(GVNFlag flag) const {
  31     return (bits_ & MaskFlag(flag)) != 0;
  32   }
  33   bool ContainsSpecial(int special) const {
  34     return (bits_ & MaskSpecial(special)) != 0;
  35   }
  36   bool ContainsAnyOf(SideEffects set) const { return (bits_ & set.bits_) != 0; }
  37   void Add(SideEffects set) { bits_ |= set.bits_; }
  38   void AddSpecial(int special) { bits_ |= MaskSpecial(special); }
  39   void RemoveFlag(GVNFlag flag) { bits_ &= ~MaskFlag(flag); }
  40   void RemoveAll() { bits_ = 0; }
  41   uint64_t ToIntegral() const { return bits_; }
  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     DCHECK(special >= 0);
  49     DCHECK(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 struct TrackedEffects;
  59
  60 // Tracks global variable and inobject field loads/stores in a fine grained
  61 // fashion, and represents them using the "special" dynamic side effects of the
  62 // SideEffects class (see above). This way unrelated global variable/inobject
  63 // field stores don't prevent hoisting and merging of global variable/inobject
  64 // field loads.
  65 class SideEffectsTracker final BASE_EMBEDDED {
  66  public:
  67   SideEffectsTracker() : num_global_vars_(0), num_inobject_fields_(0) {}
  68   SideEffects ComputeChanges(HInstruction* instr);
  69   SideEffects ComputeDependsOn(HInstruction* instr);
  70
  71  private:
  72   friend std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
  73   bool ComputeGlobalVar(Unique<PropertyCell> cell, int* index);
  74   bool ComputeInobjectField(HObjectAccess access, int* index);
  75
  76   static int GlobalVar(int index) {
  77     DCHECK(index >= 0);
  78     DCHECK(index < kNumberOfGlobalVars);
  79     return index;
  80   }
  81   static int InobjectField(int index) {
  82     DCHECK(index >= 0);
  83     DCHECK(index < kNumberOfInobjectFields);
  84     return index + kNumberOfGlobalVars;
  85   }
  86
  87   // Track up to four global vars.
  88   static const int kNumberOfGlobalVars = 4;
  89   Unique<PropertyCell> global_vars_[kNumberOfGlobalVars];
  90   int num_global_vars_;
  91
  92   // Track up to n inobject fields.
  93   static const int kNumberOfInobjectFields =
  94       SideEffects::kNumberOfSpecials - kNumberOfGlobalVars;
  95   HObjectAccess inobject_fields_[kNumberOfInobjectFields];
  96   int num_inobject_fields_;
  97 };
  98
  99
 100 // Helper class for printing, because the effects don't know their tracker.
 101 struct TrackedEffects {
 102   TrackedEffects(SideEffectsTracker* t, SideEffects e)
 103       : tracker(t), effects(e) {}
 104   SideEffectsTracker* tracker;
 105   SideEffects effects;
 106 };
 107
 108
 109 std::ostream& operator<<(std::ostream& os, const TrackedEffects& f);
 110
 111
 112 // Perform common subexpression elimination and loop-invariant code motion.
 113 class HGlobalValueNumberingPhase final : public HPhase {
 114  public:
 115   explicit HGlobalValueNumberingPhase(HGraph* graph);
 116
 117   void Run();
 118
 119  private:
 120   SideEffects CollectSideEffectsOnPathsToDominatedBlock(
 121       HBasicBlock* dominator,
 122       HBasicBlock* dominated);
 123   void AnalyzeGraph();
 124   void ComputeBlockSideEffects();
 125   void LoopInvariantCodeMotion();
 126   void ProcessLoopBlock(HBasicBlock* block,
 127                         HBasicBlock* before_loop,
 128                         SideEffects loop_kills);
 129   bool AllowCodeMotion();
 130   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
 131   TrackedEffects Print(SideEffects side_effects) {
 132     return TrackedEffects(&side_effects_tracker_, side_effects);
 133   }
 134
 135   SideEffectsTracker side_effects_tracker_;
 136   bool removed_side_effects_;
 137
 138   // A map of block IDs to their side effects.
 139   ZoneList<SideEffects> block_side_effects_;
 140
 141   // A map of loop header block IDs to their loop's side effects.
 142   ZoneList<SideEffects> loop_side_effects_;
 143
 144   // Used when collecting side effects on paths from dominator to
 145   // dominated.
 146   BitVector visited_on_paths_;
 147
 148   DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
 149 };
 150
 151 }  // namespace internal
 152 }  // namespace v8
 153
 154 #endif  // V8_HYDROGEN_GVN_H_