DependenceAnalysis.h revision a39058aaed4540fc37681cad728b99546595b2e8
1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- C++ -*-===// 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// The LLVM Compiler Infrastructure 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// This file is distributed under the University of Illinois Open Source 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// License. See LICENSE.TXT for details. 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//===----------------------------------------------------------------------===// 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// DependenceAnalysis is an LLVM pass that analyses dependences between memory 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// accesses. Currently, it is an implementation of the approach described in 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Practical Dependence Testing 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Goff, Kennedy, Tseng 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// PLDI 1991 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// There's a single entry point that analyzes the dependence between a pair 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// of memory references in a function, returning either NULL, for no dependence, 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// or a more-or-less detailed description of the dependence between them. 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// This pass exists to support the DependenceGraph pass. There are two separate 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// passes because there's a useful separation of concerns. A dependence exists 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// if two conditions are met: 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 1) Two instructions reference the same memory location, and 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 2) There is a flow of control leading from one instruction to the other. 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// DependenceAnalysis attacks the first condition; DependenceGraph will attack 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// the second (it's not yet ready). 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Please note that this is work in progress and the interface is subject to 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// change. 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Plausible changes: 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Return a set of more precise dependences instead of just one dependence 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// summarizing all. 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//===----------------------------------------------------------------------===// 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "llvm/ADT/SmallBitVector.h" 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "llvm/IR/Instructions.h" 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "llvm/Pass.h" 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovnamespace llvm { 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class AliasAnalysis; 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class Loop; 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class LoopInfo; 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class ScalarEvolution; 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class SCEV; 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class SCEVConstant; 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class raw_ostream; 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Dependence - This class represents a dependence between two memory 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// memory references in a function. It contains minimal information and 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// is used in the very common situation where the compiler is unable to 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// determine anything beyond the existence of a dependence; that is, it 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// represents a confused dependence (see also FullDependence). In most 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// cases (for output, flow, and anti dependences), the dependence implies 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// an ordering, where the source must precede the destination; in contrast, 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// input dependences are unordered. 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class Dependence { 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov public: 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Dependence(Instruction *Source, 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Instruction *Destination) : 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Src(Source), Dst(Destination) {} 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual ~Dependence() {} 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Dependence::DVEntry - Each level in the distance/direction vector 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// has a direction (or perhaps a union of several directions), and 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// perhaps a distance. 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov struct DVEntry { 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov enum { NONE = 0, 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov LT = 1, 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov EQ = 2, 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov LE = 3, 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov GT = 4, 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov NE = 5, 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov GE = 6, 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ALL = 7 }; 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned char Direction : 3; // Init to ALL, then refine. 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool Scalar : 1; // Init to true. 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool PeelFirst : 1; // Peeling the first iteration will break dependence. 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool PeelLast : 1; // Peeling the last iteration will break the dependence. 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool Splitable : 1; // Splitting the loop will break dependence. 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Distance; // NULL implies no distance available. 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false), 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov PeelLast(false), Splitable(false), Distance(NULL) { } 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getSrc - Returns the source instruction for this dependence. 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Instruction *getSrc() const { return Src; } 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getDst - Returns the destination instruction for this dependence. 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Instruction *getDst() const { return Dst; } 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isInput - Returns true if this is an input dependence. 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isInput() const; 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isOutput - Returns true if this is an output dependence. 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isOutput() const; 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isFlow - Returns true if this is a flow (aka true) dependence. 110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isFlow() const; 112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isAnti - Returns true if this is an anti dependence. 114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isAnti() const; 116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isOrdered - Returns true if dependence is Output, Flow, or Anti 118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } 120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isUnordered - Returns true if dependence is Input 122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isUnordered() const { return isInput(); } 124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isLoopIndependent - Returns true if this is a loop-independent 126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dependence. 127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isLoopIndependent() const { return true; } 128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isConfused - Returns true if this dependence is confused 130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (the compiler understands nothing and makes worst-case 131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// assumptions). 132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isConfused() const { return true; } 133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isConsistent - Returns true if this dependence is consistent 135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (occurs every time the source and destination are executed). 136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isConsistent() const { return false; } 137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getLevels - Returns the number of common loops surrounding the 139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// source and destination of the dependence. 140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual unsigned getLevels() const { return 0; } 141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getDirection - Returns the direction associated with a particular 143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// level. 144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } 145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getDistance - Returns the distance (or NULL) associated with a 147ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// particular level. 148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual const SCEV *getDistance(unsigned Level) const { return NULL; } 149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isPeelFirst - Returns true if peeling the first iteration from 151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// this loop will break this dependence. 152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isPeelFirst(unsigned Level) const { return false; } 153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isPeelLast - Returns true if peeling the last iteration from 155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// this loop will break this dependence. 156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isPeelLast(unsigned Level) const { return false; } 157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isSplitable - Returns true if splitting this loop will break 159ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// the dependence. 160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isSplitable(unsigned Level) const { return false; } 161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isScalar - Returns true if a particular level is scalar; that is, 163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// if no subscript in the source or destination mention the induction 164ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// variable associated with the loop at this level. 165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov virtual bool isScalar(unsigned Level) const; 166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dump - For debugging purposes, dumps a dependence to OS. 168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void dump(raw_ostream &OS) const; 170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov private: 171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Instruction *Src, *Dst; 172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov friend class DependenceAnalysis; 173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// FullDependence - This class represents a dependence between two memory 177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// references in a function. It contains detailed information about the 178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dependence (direction vectors, etc) and is used when the compiler is 179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// able to accurately analyze the interaction of the references; that is, 180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// it is not a confused dependence (see Dependence). In most cases 181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (for output, flow, and anti dependences), the dependence implies an 182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ordering, where the source must precede the destination; in contrast, 183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// input dependences are unordered. 184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class FullDependence : public Dependence { 185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov public: 186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence(Instruction *Src, 187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Instruction *Dst, 188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool LoopIndependent, 189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Levels); 190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ~FullDependence() { 191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov delete[] DV; 192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isLoopIndependent - Returns true if this is a loop-independent 195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dependence. 196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isLoopIndependent() const { return LoopIndependent; } 197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isConfused - Returns true if this dependence is confused 199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (the compiler understands nothing and makes worst-case 200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// assumptions). 201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isConfused() const { return false; } 202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isConsistent - Returns true if this dependence is consistent 204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (occurs every time the source and destination are executed). 205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isConsistent() const { return Consistent; } 206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getLevels - Returns the number of common loops surrounding the 208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// source and destination of the dependence. 209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned getLevels() const { return Levels; } 210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getDirection - Returns the direction associated with a particular 212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// level. 213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned getDirection(unsigned Level) const; 214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getDistance - Returns the distance (or NULL) associated with a 216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// particular level. 217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getDistance(unsigned Level) const; 218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isPeelFirst - Returns true if peeling the first iteration from 220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// this loop will break this dependence. 221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isPeelFirst(unsigned Level) const; 222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isPeelLast - Returns true if peeling the last iteration from 224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// this loop will break this dependence. 225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isPeelLast(unsigned Level) const; 226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 227ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isSplitable - Returns true if splitting the loop will break 228ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// the dependence. 229ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isSplitable(unsigned Level) const; 230ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 231ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isScalar - Returns true if a particular level is scalar; that is, 232ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// if no subscript in the source or destination mention the induction 233ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// variable associated with the loop at this level. 234ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isScalar(unsigned Level) const; 235ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov private: 236ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned short Levels; 237ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool LoopIndependent; 238ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool Consistent; // Init to true, then refine. 239ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DVEntry *DV; 240ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov friend class DependenceAnalysis; 241ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 242ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 243ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 244ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// DependenceAnalysis - This class is the main dependence-analysis driver. 245ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 246ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class DependenceAnalysis : public FunctionPass { 247ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void operator=(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; 248ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DependenceAnalysis(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; 249ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov public: 250ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// depends - Tests for a dependence between the Src and Dst instructions. 251ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns NULL if no dependence; otherwise, returns a Dependence (or a 252ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// FullDependence) with as much information as can be gleaned. 253ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// The flag PossiblyLoopIndependent should be set by the caller 254ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// if it appears that control flow can reach from Src to Dst 255ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// without traversing a loop back edge. 256ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Dependence *depends(Instruction *Src, 257ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Instruction *Dst, 258ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool PossiblyLoopIndependent); 259ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 260ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getSplitIteration - Give a dependence that's splitable at some 261ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// particular level, return the iteration that should be used to split 262ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// the loop. 263ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 264ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Generally, the dependence analyzer will be used to build 265ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// a dependence graph for a function (basically a map from instructions 266ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// to dependences). Looking for cycles in the graph shows us loops 267ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// that cannot be trivially vectorized/parallelized. 268ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 269ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// We can try to improve the situation by examining all the dependences 270ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// that make up the cycle, looking for ones we can break. 271ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sometimes, peeling the first or last iteration of a loop will break 272ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dependences, and there are flags for those possibilities. 273ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sometimes, splitting a loop at some other iteration will do the trick, 274ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and we've got a flag for that case. Rather than waste the space to 275ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// record the exact iteration (since we rarely know), we provide 276ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// a method that calculates the iteration. It's a drag that it must work 277ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// from scratch, but wonderful in that it's possible. 278ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 279ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Here's an example: 280ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 281ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (i = 0; i < 10; i++) 282ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// A[i] = ... 283ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... = A[11 - i] 284ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 285ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// There's a loop-carried flow dependence from the store to the load, 286ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// found by the weak-crossing SIV test. The dependence will have a flag, 287ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// indicating that the dependence can be broken by splitting the loop. 288ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Calling getSplitIteration will return 5. 289ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Splitting the loop breaks the dependence, like so: 290ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 291ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (i = 0; i <= 5; i++) 292ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// A[i] = ... 293ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... = A[11 - i] 294ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (i = 6; i < 10; i++) 295ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// A[i] = ... 296ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... = A[11 - i] 297ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 298ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// breaks the dependence and allows us to vectorize/parallelize 299ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// both loops. 300ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level); 301ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 302ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov private: 303ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov AliasAnalysis *AA; 304ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ScalarEvolution *SE; 305ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov LoopInfo *LI; 306ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Function *F; 307ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 308ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Subscript - This private struct represents a pair of subscripts from 309ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// a pair of potentially multi-dimensional array references. We use a 310ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// vector of them to guide subscript partitioning. 311ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov struct Subscript { 312ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Src; 313ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst; 314ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification; 315ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector Loops; 316ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector GroupLoops; 317ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector Group; 318ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 319ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 320ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov struct CoefficientInfo { 321ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Coeff; 322ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *PosPart; 323ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *NegPart; 324ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Iterations; 325ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 326ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 327ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov struct BoundInfo { 328ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Iterations; 329ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Upper[8]; 330ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Lower[8]; 331ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned char Direction; 332ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned char DirSet; 333ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 334ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 335ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Constraint - This private class represents a constraint, as defined 336ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// in the paper 337ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 338ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Practical Dependence Testing 339ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Goff, Kennedy, Tseng 340ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// PLDI 1991 341ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 342ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// There are 5 kinds of constraint, in a hierarchy. 343ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 1) Any - indicates no constraint, any dependence is possible. 344ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 2) Line - A line ax + by = c, where a, b, and c are parameters, 345ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// representing the dependence equation. 346ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 3) Distance - The value d of the dependence distance; 347ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 4) Point - A point <x, y> representing the dependence from 348ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// iteration x to iteration y. 349ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 5) Empty - No dependence is possible. 350ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov class Constraint { 351ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov private: 352ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind; 353ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ScalarEvolution *SE; 354ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *A; 355ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *B; 356ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *C; 357ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *AssociatedLoop; 358ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov public: 359ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isEmpty - Return true if the constraint is of kind Empty. 360ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isEmpty() const { return Kind == Empty; } 361ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 362ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isPoint - Return true if the constraint is of kind Point. 363ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isPoint() const { return Kind == Point; } 364ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 365ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isDistance - Return true if the constraint is of kind Distance. 366ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isDistance() const { return Kind == Distance; } 367ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 368ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isLine - Return true if the constraint is of kind Line. 369ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Since Distance's can also be represented as Lines, we also return 370ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// true if the constraint is of kind Distance. 371ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isLine() const { return Kind == Line || Kind == Distance; } 372ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 373ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isAny - Return true if the constraint is of kind Any; 374ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isAny() const { return Kind == Any; } 375ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 376ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getX - If constraint is a point <X, Y>, returns X. 377ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Otherwise assert. 378ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getX() const; 379ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 380ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getY - If constraint is a point <X, Y>, returns Y. 381ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Otherwise assert. 382ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getY() const; 383ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 384ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getA - If constraint is a line AX + BY = C, returns A. 385ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Otherwise assert. 386ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getA() const; 387ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 388ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getB - If constraint is a line AX + BY = C, returns B. 389ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Otherwise assert. 390ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getB() const; 391ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 392ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getC - If constraint is a line AX + BY = C, returns C. 393ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Otherwise assert. 394ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getC() const; 395ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 396ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getD - If constraint is a distance, returns D. 397ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Otherwise assert. 398ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getD() const; 399ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 400ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getAssociatedLoop - Returns the loop associated with this constraint. 401ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *getAssociatedLoop() const; 402ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 403ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// setPoint - Change a constraint to Point. 404ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop); 405ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 406ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// setLine - Change a constraint to Line. 407ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void setLine(const SCEV *A, const SCEV *B, 408ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *C, const Loop *CurrentLoop); 409ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 410ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// setDistance - Change a constraint to Distance. 411ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void setDistance(const SCEV *D, const Loop *CurrentLoop); 412ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 413ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// setEmpty - Change a constraint to Empty. 414ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void setEmpty(); 415ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 416ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// setAny - Change a constraint to Any. 417ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void setAny(ScalarEvolution *SE); 418ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 419ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dump - For debugging purposes. Dumps the constraint 420ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// out to OS. 421ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void dump(raw_ostream &OS) const; 422ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 423ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 424ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 425ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// establishNestingLevels - Examines the loop nesting of the Src and Dst 426ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// instructions and establishes their shared loops. Sets the variables 427ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// CommonLevels, SrcLevels, and MaxLevels. 428ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// The source and destination instructions needn't be contained in the same 429ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// loop. The routine establishNestingLevels finds the level of most deeply 430ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// nested loop that contains them both, CommonLevels. An instruction that's 431ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// not contained in a loop is at level = 0. MaxLevels is equal to the level 432ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// of the source plus the level of the destination, minus CommonLevels. 433ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// This lets us allocate vectors MaxLevels in length, with room for every 434ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// distinct loop referenced in both the source and destination subscripts. 435ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// The variable SrcLevels is the nesting depth of the source instruction. 436ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// It's used to help calculate distinct loops referenced by the destination. 437ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Here's the map from loops to levels: 438ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 0 - unused 439ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 1 - outermost common loop 440ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... - other common loops 441ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// CommonLevels - innermost common loop 442ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... - loops containing Src but not Dst 443ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// SrcLevels - innermost loop containing Src but not Dst 444ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... - loops containing Dst but not Src 445ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// MaxLevels - innermost loop containing Dst but not Src 446ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Consider the follow code fragment: 447ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (a = ...) { 448ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (b = ...) { 449ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (c = ...) { 450ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (d = ...) { 451ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// A[] = ...; 452ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 453ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 454ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (e = ...) { 455ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (f = ...) { 456ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for (g = ...) { 457ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ... = A[]; 458ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 459ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 460ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 461ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 462ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// } 463ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If we're looking at the possibility of a dependence between the store 464ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// to A (the Src) and the load from A (the Dst), we'll note that they 465ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// have 2 loops in common, so CommonLevels will equal 2 and the direction 466ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. 467ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// A map from loop names to level indices would look like 468ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// a - 1 469ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// b - 2 = CommonLevels 470ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// c - 3 471ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// d - 4 = SrcLevels 472ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// e - 5 473ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// f - 6 474ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// g - 7 = MaxLevels 475ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void establishNestingLevels(const Instruction *Src, 476ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Instruction *Dst); 477ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 478ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned CommonLevels, SrcLevels, MaxLevels; 479ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 480ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// mapSrcLoop - Given one of the loops containing the source, return 481ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// its level index in our numbering scheme. 482ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned mapSrcLoop(const Loop *SrcLoop) const; 483ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 484ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// mapDstLoop - Given one of the loops containing the destination, 485ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// return its level index in our numbering scheme. 486ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned mapDstLoop(const Loop *DstLoop) const; 487ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 488ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isLoopInvariant - Returns true if Expression is loop invariant 489ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// in LoopNest. 490ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; 491ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 492ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// removeMatchingExtensions - Examines a subscript pair. 493ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If the source and destination are identically sign (or zero) 494ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// extended, it strips off the extension in an effort to 495ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// simplify the actual analysis. 496ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void removeMatchingExtensions(Subscript *Pair); 497ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 498ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// collectCommonLoops - Finds the set of loops from the LoopNest that 499ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// have a level <= CommonLevels and are referred to by the SCEV Expression. 500ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void collectCommonLoops(const SCEV *Expression, 501ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *LoopNest, 502ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector &Loops) const; 503ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 504ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's 505ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// linear. Collect the set of loops mentioned by Src. 506ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool checkSrcSubscript(const SCEV *Src, 507ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *LoopNest, 508ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector &Loops); 509ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 510ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's 511ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// linear. Collect the set of loops mentioned by Dst. 512ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool checkDstSubscript(const SCEV *Dst, 513ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *LoopNest, 514ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector &Loops); 515ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 516ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// isKnownPredicate - Compare X and Y using the predicate Pred. 517ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Basically a wrapper for SCEV::isKnownPredicate, 518ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// but tries harder, especially in the presence of sign and zero 519ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// extensions and symbolics. 520ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool isKnownPredicate(ICmpInst::Predicate Pred, 521ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *X, 522ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Y) const; 523ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 524ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// collectUpperBound - All subscripts are the same type (on my machine, 525ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// an i64). The loop bound may be a smaller type. collectUpperBound 526ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// find the bound, if available, and zero extends it to the Type T. 527ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (I zero extend since the bound should always be >= 0.) 528ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If no upper bound is available, return NULL. 529ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *collectUpperBound(const Loop *l, Type *T) const; 530ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 531ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// collectConstantUpperBound - Calls collectUpperBound(), then 532ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// attempts to cast it to SCEVConstant. If the cast fails, 533ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// returns NULL. 534ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; 535ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 536ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) 537ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. 538ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Collects the associated loops in a set. 539ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Subscript::ClassificationKind classifyPair(const SCEV *Src, 540ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *SrcLoopNest, 541ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 542ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *DstLoopNest, 543ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SmallBitVector &Loops); 544ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 545ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. 546ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 547ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 548ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If the dependence isn't proven to exist, 549ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// marks the Result as inconsistent. 550ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool testZIV(const SCEV *Src, 551ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 552ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result) const; 553ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 554ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. 555ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a1*i] and [c2 + a2*j], where 556ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// i and j are induction variables, c1 and c2 are loop invariant, 557ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a1 and a2 are constant. 558ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 559ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 560ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sets appropriate direction vector entry and, when possible, 561ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// the distance vector entry. 562ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If the dependence isn't proven to exist, 563ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// marks the Result as inconsistent. 564ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool testSIV(const SCEV *Src, 565ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 566ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned &Level, 567ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result, 568ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Constraint &NewConstraint, 569ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *&SplitIter) const; 570ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 571ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. 572ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a1*i] and [c2 + a2*j] 573ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i and j are induction variables, c1 and c2 are loop invariant, 574ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a1 and a2 are constant. 575ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// With minor algebra, this test can also be used for things like 576ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// [c1 + a1*i + a2*j][c2]. 577ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 578ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 579ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Marks the Result as inconsistent. 580ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool testRDIV(const SCEV *Src, 581ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 582ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result) const; 583ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 584ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. 585ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if dependence disproved. 586ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Can sometimes refine direction vectors. 587ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool testMIV(const SCEV *Src, 588ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 589ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SmallBitVector &Loops, 590ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result) const; 591ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 592ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) 593ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// for dependence. 594ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a*i] and [c2 + a*i], 595ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i is an induction variable, c1 and c2 are loop invariant, 596ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a is a constant 597ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 598ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 599ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sets appropriate direction and distance. 600ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool strongSIVtest(const SCEV *Coeff, 601ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 602ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 603ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *CurrentLoop, 604ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Level, 605ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result, 606ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Constraint &NewConstraint) const; 607ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 608ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair 609ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (Src and Dst) for dependence. 610ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a*i] and [c2 - a*i], 611ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i is an induction variable, c1 and c2 are loop invariant, 612ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a is a constant. 613ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 614ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 615ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sets appropriate direction entry. 616ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Set consistent to false. 617ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Marks the dependence as splitable. 618ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool weakCrossingSIVtest(const SCEV *SrcCoeff, 619ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 620ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 621ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *CurrentLoop, 622ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Level, 623ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result, 624ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Constraint &NewConstraint, 625ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *&SplitIter) const; 626ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 627ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ExactSIVtest - Tests the SIV subscript pair 628ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (Src and Dst) for dependence. 629ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a1*i] and [c2 + a2*i], 630ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i is an induction variable, c1 and c2 are loop invariant, 631ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a1 and a2 are constant. 632ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 633ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 634ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sets appropriate direction entry. 635ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Set consistent to false. 636ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool exactSIVtest(const SCEV *SrcCoeff, 637ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstCoeff, 638ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 639ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 640ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *CurrentLoop, 641ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Level, 642ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result, 643ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Constraint &NewConstraint) const; 644ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 645ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair 646ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (Src and Dst) for dependence. 647ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1] and [c2 + a*i], 648ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i is an induction variable, c1 and c2 are loop invariant, 649ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a is a constant. See also weakZeroDstSIVtest. 650ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 651ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 652ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sets appropriate direction entry. 653ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Set consistent to false. 654ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If loop peeling will break the dependence, mark appropriately. 655ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool weakZeroSrcSIVtest(const SCEV *DstCoeff, 656ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 657ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 658ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *CurrentLoop, 659ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Level, 660ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result, 661ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Constraint &NewConstraint) const; 662ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 663ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair 664ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// (Src and Dst) for dependence. 665ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a*i] and [c2], 666ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i is an induction variable, c1 and c2 are loop invariant, 667ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a is a constant. See also weakZeroSrcSIVtest. 668ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 669ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If there might be a dependence, returns false. 670ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Sets appropriate direction entry. 671ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Set consistent to false. 672ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// If loop peeling will break the dependence, mark appropriately. 673ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool weakZeroDstSIVtest(const SCEV *SrcCoeff, 674ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 675ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 676ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *CurrentLoop, 677ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Level, 678ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result, 679ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Constraint &NewConstraint) const; 680ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 681ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// exactRDIVtest - Tests the RDIV subscript pair for dependence. 682ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a*i] and [c2 + b*j], 683ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i and j are induction variable, c1 and c2 are loop invariant, 684ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a and b are constants. 685ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 686ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Marks the result as inconsistent. 687ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Works in some cases that symbolicRDIVtest doesn't, 688ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and vice versa. 689ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool exactRDIVtest(const SCEV *SrcCoeff, 690ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstCoeff, 691ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 692ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 693ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *SrcLoop, 694ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *DstLoop, 695ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result) const; 696ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 697ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. 698ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Things of the form [c1 + a*i] and [c2 + b*j], 699ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// where i and j are induction variable, c1 and c2 are loop invariant, 700ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and a and b are constants. 701ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 702ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Marks the result as inconsistent. 703ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Works in some cases that exactRDIVtest doesn't, 704ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and vice versa. Can also be used as a backup for 705ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// ordinary SIV tests. 706ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool symbolicRDIVtest(const SCEV *SrcCoeff, 707ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstCoeff, 708ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *SrcConst, 709ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *DstConst, 710ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *SrcLoop, 711ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const Loop *DstLoop) const; 712ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 713ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// gcdMIVtest - Tests an MIV subscript pair for dependence. 714ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 715ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Marks the result as inconsistent. 716ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Can sometimes disprove the equal direction for 1 or more loops. 717ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov // Can handle some symbolics that even the SIV tests don't get, 718ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// so we use it as a backup for everything. 719ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool gcdMIVtest(const SCEV *Src, 720ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 721ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result) const; 722ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 723ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// banerjeeMIVtest - Tests an MIV subscript pair for dependence. 724ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Returns true if any possible dependence is disproved. 725ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Marks the result as inconsistent. 726ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// Computes directions. 727ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool banerjeeMIVtest(const SCEV *Src, 728ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Dst, 729ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SmallBitVector &Loops, 730ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FullDependence &Result) const; 731ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 732ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// collectCoefficientInfo - Walks through the subscript, 733ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// collecting each coefficient, the associated loop bounds, 734ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// and recording its positive and negative parts for later use. 735ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, 736ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool SrcFlag, 737ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *&Constant) const; 738ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 739ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getPositivePart - X^+ = max(X, 0). 740ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 741ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getPositivePart(const SCEV *X) const; 742ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 743ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getNegativePart - X^- = min(X, 0). 744ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 745ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getNegativePart(const SCEV *X) const; 746ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 747ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getLowerBound - Looks through all the bounds info and 748ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// computes the lower bound given the current direction settings 749ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// at each level. 750ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getLowerBound(BoundInfo *Bound) const; 751ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 752ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// getUpperBound - Looks through all the bounds info and 753ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// computes the upper bound given the current direction settings 754ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// at each level. 755ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *getUpperBound(BoundInfo *Bound) const; 756ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 757ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// exploreDirections - Hierarchically expands the direction vector 758ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// search space, combining the directions of discovered dependences 759ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// in the DirSet field of Bound. Returns the number of distinct 760ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// dependences discovered. If the dependence is disproved, 761ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// it will return 0. 762ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned exploreDirections(unsigned Level, 763ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CoefficientInfo *A, 764ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CoefficientInfo *B, 765ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BoundInfo *Bound, 766ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SmallBitVector &Loops, 767ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned &DepthExpanded, 768ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Delta) const; 769ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 770ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// testBounds - Returns true iff the current bounds are plausible. 771ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// 772ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bool testBounds(unsigned char DirKind, 773ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned Level, 774ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BoundInfo *Bound, 775ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const SCEV *Delta) const; 776ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 777ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// findBoundsALL - Computes the upper and lower bounds for level K 778ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// using the * direction. Records them in Bound. 779ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void findBoundsALL(CoefficientInfo *A, 780ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CoefficientInfo *B, 781ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BoundInfo *Bound, 782ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned K) const; 783ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 784ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// findBoundsLT - Computes the upper and lower bounds for level K 785ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /// using the < direction. Records them in Bound. 786 void findBoundsLT(CoefficientInfo *A, 787 CoefficientInfo *B, 788 BoundInfo *Bound, 789 unsigned K) const; 790 791 /// findBoundsGT - Computes the upper and lower bounds for level K 792 /// using the > direction. Records them in Bound. 793 void findBoundsGT(CoefficientInfo *A, 794 CoefficientInfo *B, 795 BoundInfo *Bound, 796 unsigned K) const; 797 798 /// findBoundsEQ - Computes the upper and lower bounds for level K 799 /// using the = direction. Records them in Bound. 800 void findBoundsEQ(CoefficientInfo *A, 801 CoefficientInfo *B, 802 BoundInfo *Bound, 803 unsigned K) const; 804 805 /// intersectConstraints - Updates X with the intersection 806 /// of the Constraints X and Y. Returns true if X has changed. 807 bool intersectConstraints(Constraint *X, 808 const Constraint *Y); 809 810 /// propagate - Review the constraints, looking for opportunities 811 /// to simplify a subscript pair (Src and Dst). 812 /// Return true if some simplification occurs. 813 /// If the simplification isn't exact (that is, if it is conservative 814 /// in terms of dependence), set consistent to false. 815 bool propagate(const SCEV *&Src, 816 const SCEV *&Dst, 817 SmallBitVector &Loops, 818 SmallVector<Constraint, 4> &Constraints, 819 bool &Consistent); 820 821 /// propagateDistance - Attempt to propagate a distance 822 /// constraint into a subscript pair (Src and Dst). 823 /// Return true if some simplification occurs. 824 /// If the simplification isn't exact (that is, if it is conservative 825 /// in terms of dependence), set consistent to false. 826 bool propagateDistance(const SCEV *&Src, 827 const SCEV *&Dst, 828 Constraint &CurConstraint, 829 bool &Consistent); 830 831 /// propagatePoint - Attempt to propagate a point 832 /// constraint into a subscript pair (Src and Dst). 833 /// Return true if some simplification occurs. 834 bool propagatePoint(const SCEV *&Src, 835 const SCEV *&Dst, 836 Constraint &CurConstraint); 837 838 /// propagateLine - Attempt to propagate a line 839 /// constraint into a subscript pair (Src and Dst). 840 /// Return true if some simplification occurs. 841 /// If the simplification isn't exact (that is, if it is conservative 842 /// in terms of dependence), set consistent to false. 843 bool propagateLine(const SCEV *&Src, 844 const SCEV *&Dst, 845 Constraint &CurConstraint, 846 bool &Consistent); 847 848 /// findCoefficient - Given a linear SCEV, 849 /// return the coefficient corresponding to specified loop. 850 /// If there isn't one, return the SCEV constant 0. 851 /// For example, given a*i + b*j + c*k, returning the coefficient 852 /// corresponding to the j loop would yield b. 853 const SCEV *findCoefficient(const SCEV *Expr, 854 const Loop *TargetLoop) const; 855 856 /// zeroCoefficient - Given a linear SCEV, 857 /// return the SCEV given by zeroing out the coefficient 858 /// corresponding to the specified loop. 859 /// For example, given a*i + b*j + c*k, zeroing the coefficient 860 /// corresponding to the j loop would yield a*i + c*k. 861 const SCEV *zeroCoefficient(const SCEV *Expr, 862 const Loop *TargetLoop) const; 863 864 /// addToCoefficient - Given a linear SCEV Expr, 865 /// return the SCEV given by adding some Value to the 866 /// coefficient corresponding to the specified TargetLoop. 867 /// For example, given a*i + b*j + c*k, adding 1 to the coefficient 868 /// corresponding to the j loop would yield a*i + (b+1)*j + c*k. 869 const SCEV *addToCoefficient(const SCEV *Expr, 870 const Loop *TargetLoop, 871 const SCEV *Value) const; 872 873 /// updateDirection - Update direction vector entry 874 /// based on the current constraint. 875 void updateDirection(Dependence::DVEntry &Level, 876 const Constraint &CurConstraint) const; 877 public: 878 static char ID; // Class identification, replacement for typeinfo 879 DependenceAnalysis() : FunctionPass(ID) { 880 initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 881 } 882 883 bool runOnFunction(Function &F); 884 void releaseMemory(); 885 void getAnalysisUsage(AnalysisUsage &) const; 886 void print(raw_ostream &, const Module * = 0) const; 887 }; // class DependenceAnalysis 888 889 /// createDependenceAnalysisPass - This creates an instance of the 890 /// DependenceAnalysis pass. 891 FunctionPass *createDependenceAnalysisPass(); 892 893} // namespace llvm 894 895#endif 896