diff options
Diffstat (limited to 'bestflags/iterative_elimination.py')
| -rw-r--r-- | bestflags/iterative_elimination.py | 232 |
1 files changed, 117 insertions, 115 deletions
diff --git a/bestflags/iterative_elimination.py b/bestflags/iterative_elimination.py index 2f4c41d1..8d548606 100644 --- a/bestflags/iterative_elimination.py +++ b/bestflags/iterative_elimination.py @@ -1,4 +1,4 @@ -# Copyright (c) 2013 The Chromium OS Authors. All rights reserved. +# Copyright 2013 The ChromiumOS Authors # Use of this source code is governed by a BSD-style license that can be # found in the LICENSE file. """Iterative flags elimination. @@ -24,7 +24,7 @@ lower value or removing the boolean flag -fstrict-aliasing produce a better fitness value. """ -__author__ = 'yuhenglong@google.com (Yuheng Long)' +__author__ = "yuhenglong@google.com (Yuheng Long)" import flags from generation import Generation @@ -32,146 +32,148 @@ 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] + """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: - 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] + # Turn off the flag. A flag is turned off if it is not presented in the + # flags_dict. + del results[spec] - return results + return results class IterativeEliminationGeneration(Generation): - """The negative flag iterative elimination algorithm.""" + """The negative flag iterative elimination algorithm.""" - def __init__(self, exe_set, parent_task): - """Set up the base line parent task. + 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. + 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. - """ + 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 + Generation.__init__(self, exe_set, None) + self._parent_task = parent_task - def IsImproved(self): - """Whether any new task has improvement upon the 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 + 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 + return False - def Next(self, cache): - """Find out the flag that gives the worst degradation. + 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. + 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. + Args: + cache: A set of tasks that have been generated before. - Returns: - A set of new generations. - """ - parent_task = self._parent_task + Returns: + A set of new generations. + """ + parent_task = self._parent_task - # Find out the task that gives the worst degradation. - worst_task = 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 + 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 + assert worst_task != parent_task - # The flags_set of the worst task. - work_flags_set = worst_task.GetFlags().GetFlags() + # The flags_set of the worst task. + work_flags_set = worst_task.GetFlags().GetFlags() - results = set([]) + 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 [] + # 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) + # 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)] + return [IterativeEliminationGeneration(results, worst_task)] class IterativeEliminationFirstGeneration(IterativeEliminationGeneration): - """The first iteration of the iterative elimination algorithm. + """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. - """ + 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 + 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) + return IterativeEliminationGeneration.IsImproved(self) |