1    :  // Copyright 2013 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  //
  15    :  // This class implements the basic block reordering transformation.
  16    :  //
  17    :  // The transformation reorders basic blocks to decrease the amount of taken and
  18    :  // mispredicted jumps.
  19    :  //
  20    :  // see: K.Pettis, R.C.Hansen, Profile Guided Code Positioning,
  21    :  //     Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language
  22    :  //     Design and Implementation, Vol. 25, No. 6, June 1990, pp. 16-27.
  23    :  
  24    :  #ifndef SYZYGY_OPTIMIZE_TRANSFORMS_BASIC_BLOCK_REORDERING_TRANSFORM_H_
  25    :  #define SYZYGY_OPTIMIZE_TRANSFORMS_BASIC_BLOCK_REORDERING_TRANSFORM_H_
  26    :  
  27    :  #include "syzygy/block_graph/filterable.h"
  28    :  #include "syzygy/block_graph/transform_policy.h"
  29    :  #include "syzygy/block_graph/analysis/control_flow_analysis.h"
  30    :  #include "syzygy/optimize/application_profile.h"
  31    :  #include "syzygy/optimize/transforms/subgraph_transform.h"
  32    :  
  33    :  namespace optimize {
  34    :  namespace transforms {
  35    :  
  36    :  // This transformation uses the Pettis algorithm to reorder basic blocks.
  37    :  class BasicBlockReorderingTransform : public SubGraphTransformInterface {
  38    :   public:
  39    :    typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
  40    :    typedef block_graph::BlockGraph BlockGraph;
  41    :    typedef block_graph::TransformPolicyInterface TransformPolicyInterface;
  42    :    typedef block_graph::analysis::ControlFlowAnalysis::BasicBlockOrdering
  43    :        BasicBlockOrdering;
  44    :  
  45    :    // Constructor.
  46  E :    BasicBlockReorderingTransform() { }
  47    :  
  48    :    // @name SubGraphTransformInterface implementation.
  49    :    // @{
  50    :    virtual bool TransformBasicBlockSubGraph(
  51    :        const TransformPolicyInterface* policy,
  52    :        BlockGraph* block_graph,
  53    :        BasicBlockSubGraph* subgraph,
  54    :        ApplicationProfile* profile,
  55    :        SubGraphProfile* subgraph_profile) override;
  56    :    // @}
  57    :  
  58    :   protected:
  59    :    // Exposed for unittesting.
  60    :    // @{
  61    :    static bool FlattenStructuralTreeToAnOrder(
  62    :        const BasicBlockSubGraph* subgraph,
  63    :        const SubGraphProfile* subgraph_profile,
  64    :        BasicBlockOrdering* order);
  65    :  
  66    :    static uint64 EvaluateCost(const BasicBlockOrdering& order,
  67    :                               const SubGraphProfile& profile);
  68    :  
  69    :    static void CommitOrdering(
  70    :        const BasicBlockOrdering& order,
  71    :        block_graph::BasicEndBlock* basic_end_block,
  72    :        BasicBlockSubGraph::BasicBlockOrdering* target);
  73    :    // @}
  74    :  
  75    :   private:
  76    :    DISALLOW_COPY_AND_ASSIGN(BasicBlockReorderingTransform);
  77    :  };
  78    :  
  79    :  }  // namespace transforms
  80    :  }  // namespace optimize
  81    :  
  82    :  #endif  // SYZYGY_OPTIMIZE_TRANSFORMS_BASIC_BLOCK_REORDERING_TRANSFORM_H_