Home | History | Annotate | Download | only in src 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_HYDROGEN_GVN_H_
     29 #define V8_HYDROGEN_GVN_H_
     30 
     31 #include "hydrogen.h"
     32 #include "hydrogen-instructions.h"
     33 #include "compiler.h"
     34 #include "zone.h"
     35 
     36 namespace v8 {
     37 namespace internal {
     38 
     39 // Perform common subexpression elimination and loop-invariant code motion.
     40 class HGlobalValueNumberingPhase : public HPhase {
     41  public:
     42   explicit HGlobalValueNumberingPhase(HGraph* graph);
     43 
     44   void Run() {
     45     Analyze();
     46     // Trigger a second analysis pass to further eliminate duplicate values
     47     // that could only be discovered by removing side-effect-generating
     48     // instructions during the first pass.
     49     if (FLAG_smi_only_arrays && removed_side_effects_) {
     50       Analyze();
     51       // TODO(danno): Turn this into a fixpoint iteration.
     52     }
     53   }
     54 
     55  private:
     56   void Analyze();
     57   GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock(
     58       HBasicBlock* dominator,
     59       HBasicBlock* dominated);
     60   void AnalyzeGraph();
     61   void ComputeBlockSideEffects();
     62   void LoopInvariantCodeMotion();
     63   void ProcessLoopBlock(HBasicBlock* block,
     64                         HBasicBlock* before_loop,
     65                         GVNFlagSet loop_kills,
     66                         GVNFlagSet* accumulated_first_time_depends,
     67                         GVNFlagSet* accumulated_first_time_changes);
     68   bool AllowCodeMotion();
     69   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
     70 
     71   bool removed_side_effects_;
     72 
     73   // A map of block IDs to their side effects.
     74   ZoneList<GVNFlagSet> block_side_effects_;
     75 
     76   // A map of loop header block IDs to their loop's side effects.
     77   ZoneList<GVNFlagSet> loop_side_effects_;
     78 
     79   // Used when collecting side effects on paths from dominator to
     80   // dominated.
     81   BitVector visited_on_paths_;
     82 
     83   DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
     84 };
     85 
     86 
     87 } }  // namespace v8::internal
     88 
     89 #endif  // V8_HYDROGEN_GVN_H_
     90