text: // Copyright 2012 Google Inc. All Rights Reserved.
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  //     http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  
  #ifndef SYZYGY_REORDER_BASIC_BLOCK_OPTIMIZER_H_
  #define SYZYGY_REORDER_BASIC_BLOCK_OPTIMIZER_H_
  
  #include <string>
  
  #include "base/strings/string_piece.h"
  #include "syzygy/block_graph/basic_block.h"
  #include "syzygy/block_graph/basic_block_subgraph.h"
  #include "syzygy/block_graph/block_graph.h"
  #include "syzygy/grinder/basic_block_util.h"
  #include "syzygy/pe/image_layout.h"
  #include "syzygy/pe/pe_file.h"
  #include "syzygy/pe/pe_transform_policy.h"
  #include "syzygy/reorder/reorderer.h"
  
  namespace reorder {
  
  // A class to optimize the basic-block placement of a block ordering, given
  // basic-block entry count data.
  class BasicBlockOptimizer {
   public:
    typedef grinder::basic_block_util::IndexedFrequencyInformation
        IndexedFrequencyInformation;
    typedef pe::ImageLayout ImageLayout;
    typedef Reorderer::Order Order;
  
    // A helper class with utility functions used by the optimization functions.
    // Exposed as public to facilitate unit-testing.
    class BasicBlockOrderer;
  
    // Constructor.
    BasicBlockOptimizer();
  
    // @returns the name that will be assigned to the cold block section.
    const std::string& cold_section_name() const { return cold_section_name_; }
  
    // Set the name that will be assigned to the cold block section.
    void set_cold_section_name(const base::StringPiece& value) {
      DCHECK(!value.empty());
      value.CopyToString(&cold_section_name_);
    }
  
    // Basic-block optimize the given @p order.
    bool Optimize(const ImageLayout& image_layout,
                  const IndexedFrequencyInformation& entry_counts,
                  Order* order);
  
   protected:
    typedef block_graph::BlockGraph BlockGraph;
    typedef block_graph::ConstBlockVector ConstBlockVector;
  
    // Optimize the layout of all basic-blocks in a block.
    static bool OptimizeBlock(const pe::PETransformPolicy& policy,
                              const BlockGraph::Block* block,
                              const ImageLayout& image_layout,
                              const IndexedFrequencyInformation& entry_counts,
                              Order::BlockSpecVector* warm_block_specs,
                              Order::BlockSpecVector* cold_block_specs);
  
    // Optimize the layout of all basic-blocks in a section, as defined by the
    // given @p section_spec and the original @p image_layout.
    static bool OptimizeSection(const pe::PETransformPolicy& policy,
                                const ImageLayout& image_layout,
                                const IndexedFrequencyInformation& entry_counts,
                                const ConstBlockVector& explicit_blocks,
                                Order::SectionSpec* orig_section_spec,
                                Order::BlockSpecVector* warm_block_specs,
                                Order::BlockSpecVector* cold_block_specs);
  
    // The name of the (new) section in which to place cold blocks and
    // basic-blocks.
    std::string cold_section_name_;
  
   private:
    DISALLOW_COPY_AND_ASSIGN(BasicBlockOptimizer);
  };
  
  // A helper class which generates warm and cold basic-block orderings for
  // a given basic-block subgraph.
  class BasicBlockOptimizer::BasicBlockOrderer {
   public:
    typedef block_graph::BasicBlock BasicBlock;
    typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
    typedef block_graph::BasicCodeBlock BasicCodeBlock;
    typedef block_graph::BasicDataBlock BasicDataBlock;
    typedef std::set<const BasicBlock*> BasicBlockSet;
    typedef BlockGraph::Offset Offset;
    typedef BlockGraph::Size Size;
    typedef grinder::basic_block_util::EntryCountType EntryCountType;
    typedef grinder::basic_block_util::IndexedFrequencyInformation
        IndexedFrequencyInformation;
    typedef grinder::basic_block_util::RelativeAddress RelativeAddress;
  
    BasicBlockOrderer(const BasicBlockSubGraph& subgraph,
                      const RelativeAddress& addr,
                      Size size,
                      const IndexedFrequencyInformation& entry_counts);
  
    // Get the number of times the block itself was entered. This assumes that
    // the entry point of the block is its first basic block.
    bool GetBlockEntryCount(EntryCountType* entry_count) const;
  
    // Generate an ordered list or warm and cold basic blocks. The warm basic-
    // blocks are ordered such that branches are straightened for the most common
    // successor. The cold basic-blocks are maintained in their original ordering
    // in the block.
    bool GetBasicBlockOrderings(Order::OffsetVector* warm_basic_blocks,
                                Order::OffsetVector* cold_basic_blocks) const;
  
   protected:
    // Get the number of times a given code basic-block was entered.
    bool GetBasicBlockEntryCount(const BasicCodeBlock* code_bb,
                                 EntryCountType* entry_count) const;
  
    // Get the warmest not-yet-placed successor to the given code basic-block.
    // This may yield a NULL pointer, denoting either no successor, or no not-
    // yet-placed successor.
    bool GetWarmestSuccessor(const BasicCodeBlock* code_bb,
                             const BasicBlockSet& placed_bbs,
                             const BasicBlock** succ_bb) const;
  
    // Get the collection of the targets referenced from a given jmp instruction
    // sorted in order of decreasing entry count (i.e., highest entry count
    // first). Note that the sort is stable, targets having the same entry counts
    // are returned in the same relative order as originally in the jump table.
    bool GetSortedJumpTargets(const block_graph::Instruction& jmp_inst,
                              std::vector<const BasicCodeBlock*>* targets) const;
  
    // Add all data basic-blocks referenced from @p code_bb to @p warm_references.
    bool AddWarmDataReferences(const BasicCodeBlock* code_bb,
                               BasicBlockSet* warm_references) const;
  
    // Recursively add @p data_bb and all data basic-blocks referenced by
    // @p data_bb to @p warm references.
    void AddRecursiveDataReferences(const BasicDataBlock* data_bb,
                                    BasicBlockSet* warm_references) const;
  
   protected:
    const BasicBlockSubGraph& subgraph_;
    const RelativeAddress& addr_;
    const Size size_;
    const IndexedFrequencyInformation& entry_counts_;
  
   private:
    DISALLOW_COPY_AND_ASSIGN(BasicBlockOrderer);
  };
  
  }  // namespace reorder
  
  #endif  // SYZYGY_REORDER_BASIC_BLOCK_OPTIMIZER_H_
  