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/optimize/application_profile.h"
  30    :  #include "syzygy/optimize/transforms/subgraph_transform.h"
  31    :  
  32    :  namespace optimize {
  33    :  namespace transforms {
  34    :    typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
  35    :    typedef block_graph::BlockGraph BlockGraph;
  36    :    typedef block_graph::TransformPolicyInterface TransformPolicyInterface;
  37    :  
  38    :  // This transformation uses the Pettis algorithm to reorder basic blocks.
  39    :  class BasicBlockReorderingTransform : public SubGraphTransformInterface {
  40    :   public:
  41    :    // Constructor.
  42  i :    BasicBlockReorderingTransform() { }
  43    :  
  44    :    // @name SubGraphTransformInterface implementation.
  45    :    // @{
  46    :    virtual bool TransformBasicBlockSubGraph(
  47    :        const TransformPolicyInterface* policy,
  48    :        BlockGraph* block_graph,
  49    :        BasicBlockSubGraph* subgraph,
  50    :        ApplicationProfile* profile,
  51    :        SubGraphProfile* subgraph_profile) OVERRIDE;
  52    :    // @}
  53    :  
  54    :   private:
  55    :    DISALLOW_COPY_AND_ASSIGN(BasicBlockReorderingTransform);
  56    :  };
  57    :  
  58    :  }  // namespace transforms
  59    :  }  // namespace optimize
  60    :  
  61    :  #endif  // SYZYGY_OPTIMIZE_TRANSFORMS_BASIC_BLOCK_REORDERING_TRANSFORM_H_