Home | History | Annotate | Download | only in bestflags 
      1 # Copyright (c) 2013 The Chromium OS 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 """Iterative flags elimination.
      5 
      6 Part of the Chrome build flags optimization.
      7 
      8 This module implements the flag iterative elimination algorithm (IE) adopted
      9 from the paper
     10 Z. Pan et al. Fast and Effective Orchestration of Compiler Optimizations for
     11 Automatic Performance Tuning.
     12 
     13 IE begins with the base line that turns on all the optimizations flags and
     14 setting the numeric flags to their highest values. IE turns off the one boolean
     15 flag or lower the value of a numeric flag with the most negative effect from the
     16 baseline. This process repeats with all remaining flags, until none of them
     17 causes performance degradation. The complexity of IE is O(n^2).
     18 
     19 For example, -fstrict-aliasing and -ftree-vectorize. The base line is
     20 b=[-fstrict-aliasing, -ftree-vectorize]. The two tasks in the first iteration
     21 are t0=[-fstrict-aliasing] and t1=[-ftree-vectorize]. The algorithm compares b
     22 with t0 and t1, respectively, and see whether setting the numeric flag with a
     23 lower value or removing the boolean flag -fstrict-aliasing produce a better
     24 fitness value.
     25 """
     26 
     27 __author__ = 'yuhenglong (at] google.com (Yuheng Long)'
     28 
     29 import flags
     30 from generation import Generation
     31 import task
     32 
     33 
     34 def _DecreaseFlag(flags_dict, spec):
     35   """Decrease the value of the flag that has the specification spec.
     36 
     37   If the flag that contains the spec is a boolean flag, it is eliminated.
     38   Otherwise the flag is a numeric flag, its value will be reduced by one.
     39 
     40   Args:
     41     flags_dict: The dictionary containing the original flags whose neighbors are
     42       to be explored.
     43     spec: The spec in the flags_dict is to be changed.
     44 
     45   Returns:
     46     Dictionary of neighbor flag that is only different from the original
     47     dictionary by the spec.
     48   """
     49 
     50   # The specification must be held by one of the flags.
     51   assert spec in flags_dict
     52 
     53   # The results this method returns.
     54   results = flags_dict.copy()
     55 
     56   # This method searches for a pattern [start-end] in the spec. If the spec
     57   # contains this pattern, it is a numeric flag. Otherwise it is a boolean flag.
     58   # For example, -finline-limit=[1-1000] is a numeric flag and -falign-jumps is
     59   # a boolean flag.
     60   numeric_flag_match = flags.Search(spec)
     61 
     62   if numeric_flag_match:
     63     # numeric flag
     64     val = results[spec].GetValue()
     65 
     66     # If the value of the flag is the lower boundary of the specification, this
     67     # flag will be turned off. Because it already contains the lowest value and
     68     # can not be decreased any more.
     69     if val == int(numeric_flag_match.group('start')):
     70       # Turn off the flag. A flag is turned off if it is not presented in the
     71       # flags_dict.
     72       del results[spec]
     73     else:
     74       results[spec] = flags.Flag(spec, val - 1)
     75   else:
     76     # Turn off the flag. A flag is turned off if it is not presented in the
     77     # flags_dict.
     78     del results[spec]
     79 
     80   return results
     81 
     82 
     83 class IterativeEliminationGeneration(Generation):
     84   """The negative flag iterative elimination algorithm."""
     85 
     86   def __init__(self, exe_set, parent_task):
     87     """Set up the base line parent task.
     88 
     89     The parent task is the base line against which the new tasks are compared.
     90     The new tasks are only different from the base line from one flag f by
     91     either turning this flag f off, or lower the flag value by 1.
     92     If a new task is better than the base line, one flag is identified that
     93     gives degradation. The flag that give the worst degradation will be removed
     94     or lower the value by 1 in the base in each iteration.
     95 
     96     Args:
     97       exe_set: A set of tasks to be run. Each one only differs from the
     98         parent_task by one flag.
     99       parent_task: The base line task, against which the new tasks in exe_set
    100         are compared.
    101     """
    102 
    103     Generation.__init__(self, exe_set, None)
    104     self._parent_task = parent_task
    105 
    106   def IsImproved(self):
    107     """Whether any new task has improvement upon the parent task."""
    108 
    109     parent = self._parent_task
    110     # Whether there is any new task that has improvement over the parent base
    111     # line task.
    112     for curr in [curr for curr in self.Pool() if curr != parent]:
    113       if curr.IsImproved(parent):
    114         return True
    115 
    116     return False
    117 
    118   def Next(self, cache):
    119     """Find out the flag that gives the worst degradation.
    120 
    121     Found out the flag that gives the worst degradation. Turn that flag off from
    122     the base line and use the new base line for the new generation.
    123 
    124     Args:
    125       cache: A set of tasks that have been generated before.
    126 
    127     Returns:
    128       A set of new generations.
    129     """
    130     parent_task = self._parent_task
    131 
    132     # Find out the task that gives the worst degradation.
    133     worst_task = parent_task
    134 
    135     for curr in [curr for curr in self.Pool() if curr != parent_task]:
    136       # The method IsImproved, which is supposed to be called before, ensures
    137       # that there is at least a task that improves upon the parent_task.
    138       if curr.IsImproved(worst_task):
    139         worst_task = curr
    140 
    141     assert worst_task != parent_task
    142 
    143     # The flags_set of the worst task.
    144     work_flags_set = worst_task.GetFlags().GetFlags()
    145 
    146     results = set([])
    147 
    148     # If the flags_set contains no flag, i.e., all the flags have been
    149     # eliminated, the algorithm stops.
    150     if not work_flags_set:
    151       return []
    152 
    153     # Turn of the remaining flags one by one for the next generation.
    154     for spec in work_flags_set:
    155       flag_set = flags.FlagSet(_DecreaseFlag(work_flags_set, spec).values())
    156       new_task = task.Task(flag_set)
    157       if new_task not in cache:
    158         results.add(new_task)
    159 
    160     return [IterativeEliminationGeneration(results, worst_task)]
    161 
    162 
    163 class IterativeEliminationFirstGeneration(IterativeEliminationGeneration):
    164   """The first iteration of the iterative elimination algorithm.
    165 
    166   The first iteration also evaluates the base line task. The base line tasks in
    167   the subsequent iterations have been evaluated. Therefore,
    168   IterativeEliminationGeneration does not include the base line task in the
    169   execution set.
    170   """
    171 
    172   def IsImproved(self):
    173     # Find out the base line task in the execution set.
    174     parent = next(task for task in self.Pool() if task == self._parent_task)
    175     self._parent_task = parent
    176 
    177     return IterativeEliminationGeneration.IsImproved(self)
    178