178 lines
6.2 KiB
Python
178 lines
6.2 KiB
Python
|
# 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)
|