loop_dependence.h | Explore in Territory

// Copyright (c) 2018 Google LLC.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef SOURCE_OPT_LOOP_DEPENDENCE_H_
#define SOURCE_OPT_LOOP_DEPENDENCE_H_

#include <algorithm>
#include <cstdint>
#include <list>
#include <map>
#include <memory>
#include <ostream>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "source/opt/instruction.h"
#include "source/opt/ir_context.h"
#include "source/opt/loop_descriptor.h"
#include "source/opt/scalar_analysis.h"

namespace spvtools {
namespace opt {

// Stores information about dependence between a load and a store wrt a single
// loop in a loop nest.
// DependenceInformation
// * UNKNOWN if no dependence information can be gathered or is gathered
//   for it.
// * DIRECTION if a dependence direction could be found, but not a
//   distance.
// * DISTANCE if a dependence distance could be found.
// * PEEL if peeling either the first or last iteration will break
//   dependence between the given load and store.
// * IRRELEVANT if it has no effect on the dependence between the given
//   load and store.
//
// If peel_first == true, the analysis has found that peeling the first
// iteration of this loop will break dependence.
//
// If peel_last == true, the analysis has found that peeling the last iteration
// of this loop will break dependence.
class DistanceEntry { … };

// Stores a vector of DistanceEntrys, one per loop in the analysis.
// A DistanceVector holds all of the information gathered in a dependence
// analysis wrt the loops stored in the LoopDependenceAnalysis performing the
// analysis.
class DistanceVector { … };

class DependenceLine;
class DependenceDistance;
class DependencePoint;
class DependenceNone;
class DependenceEmpty;

class Constraint { … };
// clang-format on

class DependenceLine : public Constraint { … };

class DependenceDistance : public Constraint { … };

class DependencePoint : public Constraint { … };

class DependenceNone : public Constraint { … };

class DependenceEmpty : public Constraint { … };

// Provides dependence information between a store instruction and a load
// instruction inside the same loop in a loop nest.
//
// The analysis can only check dependence between stores and loads with regard
// to the loop nest it is created with.
//
// The analysis can output debugging information to a stream. The output
// describes the control flow of the analysis and what information it can deduce
// at each step.
// SetDebugStream and ClearDebugStream are provided for this functionality.
//
// The dependency algorithm is based on the 1990 Paper
//   Practical Dependence Testing
//   Gina Goff, Ken Kennedy, Chau-Wen Tseng
//
// The algorithm first identifies subscript pairs between the load and store.
// Each pair is tested until all have been tested or independence is found.
// The number of induction variables in a pair determines which test to perform
// on it;
// Zero Index Variable (ZIV) is used when no induction variables are present
// in the pair.
// Single Index Variable (SIV) is used when only one induction variable is
// present, but may occur multiple times in the pair.
// Multiple Index Variable (MIV) is used when more than one induction variable
// is present in the pair.
class LoopDependenceAnalysis { … };

}  // namespace opt
}  // namespace spvtools

#endif  // SOURCE_OPT_LOOP_DEPENDENCE_H_
chromium/third_party/spirv-tools/src/source/opt/loop_dependence.h
