1# Copyright 2013 The ChromiumOS Authors 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__ = "[email protected] (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( 156 _DecreaseFlag(work_flags_set, spec).values() 157 ) 158 new_task = task.Task(flag_set) 159 if new_task not in cache: 160 results.add(new_task) 161 162 return [IterativeEliminationGeneration(results, worst_task)] 163 164 165class IterativeEliminationFirstGeneration(IterativeEliminationGeneration): 166 """The first iteration of the iterative elimination algorithm. 167 168 The first iteration also evaluates the base line task. The base line tasks in 169 the subsequent iterations have been evaluated. Therefore, 170 IterativeEliminationGeneration does not include the base line task in the 171 execution set. 172 """ 173 174 def IsImproved(self): 175 # Find out the base line task in the execution set. 176 parent = next(task for task in self.Pool() if task == self._parent_task) 177 self._parent_task = parent 178 179 return IterativeEliminationGeneration.IsImproved(self) 180