iterative_elimination.py revision f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbe 
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
6Part of the Chrome build flags optimization.
7
8This module implements the flag iterative elimination algorithm (IE) adopted
9from the paper
10Z. Pan et al. Fast and Effective Orchestration of Compiler Optimizations for
11Automatic Performance Tuning.
12
13IE begins with the base line that turns on all the optimizations flags and
14setting the numeric flags to their highest values. IE turns off the one boolean
15flag or lower the value of a numeric flag with the most negative effect from the
16baseline. This process repeats with all remaining flags, until none of them
17causes performance degradation. The complexity of IE is O(n^2).
18
19For example, -fstrict-aliasing and -ftree-vectorize. The base line is
20b=[-fstrict-aliasing, -ftree-vectorize]. The two tasks in the first iteration
21are t0=[-fstrict-aliasing] and t1=[-ftree-vectorize]. The algorithm compares b
22with t0 and t1, respectively, and see whether setting the numeric flag with a
23lower value or removing the boolean flag -fstrict-aliasing produce a better
24fitness value.
25"""
26
27__author__ = 'yuhenglong@google.com (Yuheng Long)'
28
29import flags
30from generation import Generation
31import task
32
33
34def _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
83class 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
163class 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