diff options
Diffstat (limited to 'bestflags/iterative_elimination.py')
| -rw-r--r-- | bestflags/iterative_elimination.py | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/bestflags/iterative_elimination.py b/bestflags/iterative_elimination.py new file mode 100644 index 00000000..2f4c41d1 --- /dev/null +++ b/bestflags/iterative_elimination.py @@ -0,0 +1,177 @@ +# Copyright (c) 2013 The Chromium OS Authors. All rights reserved. +# Use of this source code is governed by a BSD-style license that can be +# found in the LICENSE file. +"""Iterative flags elimination. + +Part of the Chrome build flags optimization. + +This module implements the flag iterative elimination algorithm (IE) adopted +from the paper +Z. Pan et al. Fast and Effective Orchestration of Compiler Optimizations for +Automatic Performance Tuning. + +IE begins with the base line that turns on all the optimizations flags and +setting the numeric flags to their highest values. IE turns off the one boolean +flag or lower the value of a numeric flag with the most negative effect from the +baseline. This process repeats with all remaining flags, until none of them +causes performance degradation. The complexity of IE is O(n^2). + +For example, -fstrict-aliasing and -ftree-vectorize. The base line is +b=[-fstrict-aliasing, -ftree-vectorize]. The two tasks in the first iteration +are t0=[-fstrict-aliasing] and t1=[-ftree-vectorize]. The algorithm compares b +with t0 and t1, respectively, and see whether setting the numeric flag with a +lower value or removing the boolean flag -fstrict-aliasing produce a better +fitness value. +""" + +__author__ = 'yuhenglong@google.com (Yuheng Long)' + +import flags +from generation import Generation +import task + + +def _DecreaseFlag(flags_dict, spec): + """Decrease the value of the flag that has the specification spec. + + If the flag that contains the spec is a boolean flag, it is eliminated. + Otherwise the flag is a numeric flag, its value will be reduced by one. + + Args: + flags_dict: The dictionary containing the original flags whose neighbors are + to be explored. + spec: The spec in the flags_dict is to be changed. + + Returns: + Dictionary of neighbor flag that is only different from the original + dictionary by the spec. + """ + + # The specification must be held by one of the flags. + assert spec in flags_dict + + # The results this method returns. + results = flags_dict.copy() + + # This method searches for a pattern [start-end] in the spec. If the spec + # contains this pattern, it is a numeric flag. Otherwise it is a boolean flag. + # For example, -finline-limit=[1-1000] is a numeric flag and -falign-jumps is + # a boolean flag. + numeric_flag_match = flags.Search(spec) + + if numeric_flag_match: + # numeric flag + val = results[spec].GetValue() + + # If the value of the flag is the lower boundary of the specification, this + # flag will be turned off. Because it already contains the lowest value and + # can not be decreased any more. + if val == int(numeric_flag_match.group('start')): + # Turn off the flag. A flag is turned off if it is not presented in the + # flags_dict. + del results[spec] + else: + results[spec] = flags.Flag(spec, val - 1) + else: + # Turn off the flag. A flag is turned off if it is not presented in the + # flags_dict. + del results[spec] + + return results + + +class IterativeEliminationGeneration(Generation): + """The negative flag iterative elimination algorithm.""" + + def __init__(self, exe_set, parent_task): + """Set up the base line parent task. + + The parent task is the base line against which the new tasks are compared. + The new tasks are only different from the base line from one flag f by + either turning this flag f off, or lower the flag value by 1. + If a new task is better than the base line, one flag is identified that + gives degradation. The flag that give the worst degradation will be removed + or lower the value by 1 in the base in each iteration. + + Args: + exe_set: A set of tasks to be run. Each one only differs from the + parent_task by one flag. + parent_task: The base line task, against which the new tasks in exe_set + are compared. + """ + + Generation.__init__(self, exe_set, None) + self._parent_task = parent_task + + def IsImproved(self): + """Whether any new task has improvement upon the parent task.""" + + parent = self._parent_task + # Whether there is any new task that has improvement over the parent base + # line task. + for curr in [curr for curr in self.Pool() if curr != parent]: + if curr.IsImproved(parent): + return True + + return False + + def Next(self, cache): + """Find out the flag that gives the worst degradation. + + Found out the flag that gives the worst degradation. Turn that flag off from + the base line and use the new base line for the new generation. + + Args: + cache: A set of tasks that have been generated before. + + Returns: + A set of new generations. + """ + parent_task = self._parent_task + + # Find out the task that gives the worst degradation. + worst_task = parent_task + + for curr in [curr for curr in self.Pool() if curr != parent_task]: + # The method IsImproved, which is supposed to be called before, ensures + # that there is at least a task that improves upon the parent_task. + if curr.IsImproved(worst_task): + worst_task = curr + + assert worst_task != parent_task + + # The flags_set of the worst task. + work_flags_set = worst_task.GetFlags().GetFlags() + + results = set([]) + + # If the flags_set contains no flag, i.e., all the flags have been + # eliminated, the algorithm stops. + if not work_flags_set: + return [] + + # Turn of the remaining flags one by one for the next generation. + for spec in work_flags_set: + flag_set = flags.FlagSet(_DecreaseFlag(work_flags_set, spec).values()) + new_task = task.Task(flag_set) + if new_task not in cache: + results.add(new_task) + + return [IterativeEliminationGeneration(results, worst_task)] + + +class IterativeEliminationFirstGeneration(IterativeEliminationGeneration): + """The first iteration of the iterative elimination algorithm. + + The first iteration also evaluates the base line task. The base line tasks in + the subsequent iterations have been evaluated. Therefore, + IterativeEliminationGeneration does not include the base line task in the + execution set. + """ + + def IsImproved(self): + # Find out the base line task in the execution set. + parent = next(task for task in self.Pool() if task == self._parent_task) + self._parent_task = parent + + return IterativeEliminationGeneration.IsImproved(self) |