Add the negative flag elimination algorithm.

BUG=None
TEST=unit testings for the pipeline stage, pipeline workers, generation,
steering, task, flag, hill climbing, genetic algorithm and iterative flag
elimination algorithm.

Change-Id: I2d400e304570de8a15556529eff823d40c36b185
Reviewed-on: https://gerrit-int.chromium.org/42798
Reviewed-by: Luis Lozano <llozano@chromium.org>
Commit-Queue: Yuheng Long <yuhenglong@google.com>
Tested-by: Yuheng Long <yuhenglong@google.com>

2 files changed, 323 insertions, 8 deletions

diff --git a/bestflags/iterative_elimination.py b/bestflags/iterative_elimination.py
new file mode 100644
index 00000000..618917e2
--- /dev/null
+++ b/bestflags/iterative_elimination.py
@@ -0,0 +1,178 @@
+# 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)
diff --git a/bestflags/testing_batch.py b/bestflags/testing_batch.py
index 97ea450a..7bfda09b 100644
--- a/bestflags/testing_batch.py
+++ b/bestflags/testing_batch.py
@@ -6,7 +6,8 @@
 
 Part of the Chrome build flags optimization.
 
-Test the variations of the hill climbing algorithms.
+Test the best branching hill climbing algorithms, genetic algorithm and
+iterative elimination algorithm.
 """
 
 __author__ = 'yuhenglong@google.com (Yuheng Long)'
@@ -22,6 +23,7 @@ from flags import FlagSet
 from genetic_algorithm import GAGeneration
 from genetic_algorithm import GATask
 from hill_climb_best_neighbor import HillClimbingBestBranch
+from iterative_elimination import IterativeEliminationFirstGeneration
 import pipeline_process
 from steering import Steering
 from task import BUILD_STAGE
@@ -133,6 +135,102 @@ def GenerateRandomGATasks(specs, num_tasks, num_trials):
   return tasks
 
 
+def _GenerateInitialFlags(specs, spec):
+  """Generate the flag_set of a task in the flag elimination algorithm.
+
+  Set the value of all the flags to the largest value, except for the flag that
+  contains spec.
+
+  For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing] and
+  the spec is -finline-limit=[1-1000], then the result is
+  [-finline-limit=[1-1000]:-finline-limit=998,
+   -fstrict-aliasing:-fstrict-aliasing]
+
+  Args:
+    specs: an array of specifications from which the result flag_set is created.
+      The flag_set contains one and only one flag that contain the specification
+      spec.
+    spec: The flag containing this spec should have a value that is smaller than
+      the highest value the flag can have.
+
+  Returns:
+    An array of flags, each of which contains one spec in specs. All the values
+    of the flags are the largest values in specs, expect the one that contains
+    spec.
+  """
+
+  flag_set = []
+  for other_spec in specs:
+    numeric_flag_match = flags.Search(other_spec)
+    # Found the spec in the array specs.
+    if other_spec == spec:
+      # Numeric flag will have a value that is smaller than the largest value
+      # and Boolean flag will be deleted.
+      if numeric_flag_match:
+        end = int(numeric_flag_match.group('end'))
+        flag_set.append(flags.Flag(other_spec, end - 2))
+
+      continue
+
+    # other_spec != spec
+    if numeric_flag_match:
+      # numeric flag
+      end = int(numeric_flag_match.group('end'))
+      flag_set.append(flags.Flag(other_spec, end - 1))
+      continue
+
+    # boolean flag
+    flag_set.append(flags.Flag(other_spec))
+
+  return flag_set
+
+
+def _GenerateAllIterativeEliminationTasks(specs):
+  """Generate the initial tasks for the negative flag elimination algorithm.
+
+  Generate the base line task that turns on all the boolean flags and sets the
+  value to be the largest value for the numeric flag.
+
+  For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing],
+  the base line is [-finline-limit=[1-1000]:-finline-limit=999,
+  -fstrict-aliasing:-fstrict-aliasing]
+
+  Generate a set of task, each turns off one of the flag or sets a value that is
+  smaller than the largest value for the flag.
+
+  Args:
+    specs: an array of specifications from which the result flag_set is created.
+
+  Returns:
+    An array containing one generation of the initial tasks for the negative
+    flag elimination algorithm.
+  """
+
+  # The set of tasks to be generated.
+  results = set([])
+  flag_set = []
+
+  for spec in specs:
+    numeric_flag_match = flags.Search(spec)
+    if numeric_flag_match:
+      # Numeric flag.
+      end_value = int(numeric_flag_match.group('end'))
+      flag_set.append(flags.Flag(spec, end_value - 1))
+      continue
+
+    # Boolean flag.
+    flag_set.append(flags.Flag(spec))
+
+  # The base line task that set all the flags to their largest values.
+  parent_task = Task(flags.FlagSet(flag_set))
+  results.add(parent_task)
+
+  for spec in specs:
+    results.add(Task(flags.FlagSet(_GenerateInitialFlags(specs, spec))))
+
+  return [IterativeEliminationFirstGeneration(results, parent_task)]
+
+
 def _ComputeCost(cost_func, specs, flag_set):
   """Compute the mock cost of the flag_set using the input cost function.
 
@@ -242,6 +340,13 @@ class MockAlgorithmsTest(unittest.TestCase):
   build and test phases by letting the user define the fitness function.
   """
 
+  def _GenerateFlagSpecifications(self):
+    """Generate the testing specifications."""
+
+    mock_test_file = 'scale_mock_test'
+    _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file)
+    return flags.ReadConf(mock_test_file)
+
   def testBestHillClimb(self):
     """Test the best hill climb algorithm.
 
@@ -252,9 +357,7 @@ class MockAlgorithmsTest(unittest.TestCase):
     Task.InitLogCommand(None, None, 'output')
 
     # Generate the testing specs.
-    mock_test_file = 'scale_mock_test'
-    _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file)
-    specs = flags.ReadConf(mock_test_file)
+    specs = self._GenerateFlagSpecifications()
 
     # Generate the initial generations for a test whose cost function is the
     # summation of the values of all the flags.
@@ -292,10 +395,7 @@ class MockAlgorithmsTest(unittest.TestCase):
     Task.InitLogCommand(None, None, 'output')
 
     # Generate the testing specs.
-    mock_test_file = 'scale_mock_test'
-    _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file)
-    specs = flags.ReadConf(mock_test_file)
-
+    specs = self._GenerateFlagSpecifications()
     # Initiate the build/test command and the log directory.
     GAGeneration.InitMetaData(STOP_THRESHOLD, NUM_CHROMOSOMES, NUM_TRIALS,
                               specs, MUTATION_RATE)
@@ -310,6 +410,43 @@ class MockAlgorithmsTest(unittest.TestCase):
     cost_func = 'sys.maxint - sum(values[0:len(values)])'
     _TestAlgorithm(cost_func, specs, generations, -1)
 
+  def testIterativeElimination(self):
+    """Test the iterative elimination algorithm.
+
+    Test whether it finds the best results as expected.
+    """
+
+    # Initiate the build/test command and the log directory.
+    Task.InitLogCommand(None, None, 'output')
+
+    # Generate the testing specs.
+    specs = self._GenerateFlagSpecifications()
+
+    # Generate the initial generations. The generation contains the base line
+    # task that turns on all the flags and tasks that each turn off one of the
+    # flags.
+    generations = _GenerateAllIterativeEliminationTasks(specs)
+
+    # Test the algorithm. The cost function is the summation of all the values
+    # of all the flags. Therefore, the best value is supposed to be 0, i.e.,
+    # when all the flags are disabled.
+    _TestAlgorithm('sum(values[0:len(values)])', specs, generations, 0)
+
+    # This test uses a cost function that is the negative of the previous cost
+    # function. Therefore, the best result should be found in task with all the
+    # flags enabled.
+    all_flags_tasks = _GenerateAllFlagsTasks(specs)
+    cost_function = 'sys.maxint - sum(values[0:len(values)])'
+    # Compute the cost of the task that turns on all the flags.
+    all_flags = list(all_flags_tasks)[0].GetFlags()
+    cost = _ComputeCost(cost_function, specs, all_flags)
+
+    # Test the algorithm. The cost function is negative of the summation of all
+    # the values of all the flags. Therefore, the best value is supposed to be
+    # 0, i.e., when all the flags are disabled.
+    # The concrete type of the generation decides how the next generation will
+    # be generated.
+    _TestAlgorithm(cost_function, specs, generations, cost)
 
 if __name__ == '__main__':
   unittest.main()