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