1243789Sdim//===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===// 2243789Sdim// 3243789Sdim// The LLVM Compiler Infrastructure 4243789Sdim// 5243789Sdim// This file is distributed under the University of Illinois Open Source 6243789Sdim// License. See LICENSE.TXT for details. 7243789Sdim// 8243789Sdim//===----------------------------------------------------------------------===// 9243789Sdim// 10243789Sdim// DependenceAnalysis is an LLVM pass that analyses dependences between memory 11243789Sdim// accesses. Currently, it is an (incomplete) implementation of the approach 12243789Sdim// described in 13243789Sdim// 14243789Sdim// Practical Dependence Testing 15243789Sdim// Goff, Kennedy, Tseng 16243789Sdim// PLDI 1991 17243789Sdim// 18243789Sdim// There's a single entry point that analyzes the dependence between a pair 19243789Sdim// of memory references in a function, returning either NULL, for no dependence, 20243789Sdim// or a more-or-less detailed description of the dependence between them. 21243789Sdim// 22243789Sdim// Currently, the implementation cannot propagate constraints between 23243789Sdim// coupled RDIV subscripts and lacks a multi-subscript MIV test. 24243789Sdim// Both of these are conservative weaknesses; 25243789Sdim// that is, not a source of correctness problems. 26243789Sdim// 27243789Sdim// The implementation depends on the GEP instruction to 28243789Sdim// differentiate subscripts. Since Clang linearizes subscripts 29243789Sdim// for most arrays, we give up some precision (though the existing MIV tests 30243789Sdim// will help). We trust that the GEP instruction will eventually be extended. 31243789Sdim// In the meantime, we should explore Maslov's ideas about delinearization. 32243789Sdim// 33243789Sdim// We should pay some careful attention to the possibility of integer overflow 34243789Sdim// in the implementation of the various tests. This could happen with Add, 35243789Sdim// Subtract, or Multiply, with both APInt's and SCEV's. 36243789Sdim// 37243789Sdim// Some non-linear subscript pairs can be handled by the GCD test 38243789Sdim// (and perhaps other tests). 39243789Sdim// Should explore how often these things occur. 40243789Sdim// 41243789Sdim// Finally, it seems like certain test cases expose weaknesses in the SCEV 42243789Sdim// simplification, especially in the handling of sign and zero extensions. 43243789Sdim// It could be useful to spend time exploring these. 44243789Sdim// 45243789Sdim// Please note that this is work in progress and the interface is subject to 46243789Sdim// change. 47243789Sdim// 48243789Sdim//===----------------------------------------------------------------------===// 49243789Sdim// // 50243789Sdim// In memory of Ken Kennedy, 1945 - 2007 // 51243789Sdim// // 52243789Sdim//===----------------------------------------------------------------------===// 53243789Sdim 54243789Sdim#define DEBUG_TYPE "da" 55243789Sdim 56243789Sdim#include "llvm/Analysis/DependenceAnalysis.h" 57243789Sdim#include "llvm/ADT/Statistic.h" 58243789Sdim#include "llvm/Analysis/AliasAnalysis.h" 59243789Sdim#include "llvm/Analysis/LoopInfo.h" 60243789Sdim#include "llvm/Analysis/ScalarEvolution.h" 61243789Sdim#include "llvm/Analysis/ScalarEvolutionExpressions.h" 62249423Sdim#include "llvm/Analysis/ValueTracking.h" 63249423Sdim#include "llvm/IR/Operator.h" 64243789Sdim#include "llvm/Support/Debug.h" 65243789Sdim#include "llvm/Support/ErrorHandling.h" 66243789Sdim#include "llvm/Support/InstIterator.h" 67243789Sdim#include "llvm/Support/raw_ostream.h" 68243789Sdim 69243789Sdimusing namespace llvm; 70243789Sdim 71243789Sdim//===----------------------------------------------------------------------===// 72243789Sdim// statistics 73243789Sdim 74243789SdimSTATISTIC(TotalArrayPairs, "Array pairs tested"); 75243789SdimSTATISTIC(SeparableSubscriptPairs, "Separable subscript pairs"); 76243789SdimSTATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs"); 77243789SdimSTATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs"); 78243789SdimSTATISTIC(ZIVapplications, "ZIV applications"); 79243789SdimSTATISTIC(ZIVindependence, "ZIV independence"); 80243789SdimSTATISTIC(StrongSIVapplications, "Strong SIV applications"); 81243789SdimSTATISTIC(StrongSIVsuccesses, "Strong SIV successes"); 82243789SdimSTATISTIC(StrongSIVindependence, "Strong SIV independence"); 83243789SdimSTATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications"); 84243789SdimSTATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes"); 85243789SdimSTATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence"); 86243789SdimSTATISTIC(ExactSIVapplications, "Exact SIV applications"); 87243789SdimSTATISTIC(ExactSIVsuccesses, "Exact SIV successes"); 88243789SdimSTATISTIC(ExactSIVindependence, "Exact SIV independence"); 89243789SdimSTATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications"); 90243789SdimSTATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes"); 91243789SdimSTATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence"); 92243789SdimSTATISTIC(ExactRDIVapplications, "Exact RDIV applications"); 93243789SdimSTATISTIC(ExactRDIVindependence, "Exact RDIV independence"); 94243789SdimSTATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications"); 95243789SdimSTATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence"); 96243789SdimSTATISTIC(DeltaApplications, "Delta applications"); 97243789SdimSTATISTIC(DeltaSuccesses, "Delta successes"); 98243789SdimSTATISTIC(DeltaIndependence, "Delta independence"); 99243789SdimSTATISTIC(DeltaPropagations, "Delta propagations"); 100243789SdimSTATISTIC(GCDapplications, "GCD applications"); 101243789SdimSTATISTIC(GCDsuccesses, "GCD successes"); 102243789SdimSTATISTIC(GCDindependence, "GCD independence"); 103243789SdimSTATISTIC(BanerjeeApplications, "Banerjee applications"); 104243789SdimSTATISTIC(BanerjeeIndependence, "Banerjee independence"); 105243789SdimSTATISTIC(BanerjeeSuccesses, "Banerjee successes"); 106243789Sdim 107243789Sdim//===----------------------------------------------------------------------===// 108243789Sdim// basics 109243789Sdim 110243789SdimINITIALIZE_PASS_BEGIN(DependenceAnalysis, "da", 111243789Sdim "Dependence Analysis", true, true) 112243789SdimINITIALIZE_PASS_DEPENDENCY(LoopInfo) 113243789SdimINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 114243789SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 115243789SdimINITIALIZE_PASS_END(DependenceAnalysis, "da", 116243789Sdim "Dependence Analysis", true, true) 117243789Sdim 118243789Sdimchar DependenceAnalysis::ID = 0; 119243789Sdim 120243789Sdim 121243789SdimFunctionPass *llvm::createDependenceAnalysisPass() { 122243789Sdim return new DependenceAnalysis(); 123243789Sdim} 124243789Sdim 125243789Sdim 126243789Sdimbool DependenceAnalysis::runOnFunction(Function &F) { 127243789Sdim this->F = &F; 128243789Sdim AA = &getAnalysis<AliasAnalysis>(); 129243789Sdim SE = &getAnalysis<ScalarEvolution>(); 130243789Sdim LI = &getAnalysis<LoopInfo>(); 131243789Sdim return false; 132243789Sdim} 133243789Sdim 134243789Sdim 135243789Sdimvoid DependenceAnalysis::releaseMemory() { 136243789Sdim} 137243789Sdim 138243789Sdim 139243789Sdimvoid DependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 140243789Sdim AU.setPreservesAll(); 141243789Sdim AU.addRequiredTransitive<AliasAnalysis>(); 142243789Sdim AU.addRequiredTransitive<ScalarEvolution>(); 143243789Sdim AU.addRequiredTransitive<LoopInfo>(); 144243789Sdim} 145243789Sdim 146243789Sdim 147243789Sdim// Used to test the dependence analyzer. 148249423Sdim// Looks through the function, noting loads and stores. 149249423Sdim// Calls depends() on every possible pair and prints out the result. 150243789Sdim// Ignores all other instructions. 151243789Sdimstatic 152243789Sdimvoid dumpExampleDependence(raw_ostream &OS, Function *F, 153243789Sdim DependenceAnalysis *DA) { 154243789Sdim for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); 155243789Sdim SrcI != SrcE; ++SrcI) { 156249423Sdim if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) { 157243789Sdim for (inst_iterator DstI = SrcI, DstE = inst_end(F); 158243789Sdim DstI != DstE; ++DstI) { 159249423Sdim if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) { 160243789Sdim OS << "da analyze - "; 161249423Sdim if (Dependence *D = DA->depends(&*SrcI, &*DstI, true)) { 162243789Sdim D->dump(OS); 163243789Sdim for (unsigned Level = 1; Level <= D->getLevels(); Level++) { 164243789Sdim if (D->isSplitable(Level)) { 165243789Sdim OS << "da analyze - split level = " << Level; 166243789Sdim OS << ", iteration = " << *DA->getSplitIteration(D, Level); 167243789Sdim OS << "!\n"; 168243789Sdim } 169243789Sdim } 170243789Sdim delete D; 171243789Sdim } 172243789Sdim else 173243789Sdim OS << "none!\n"; 174243789Sdim } 175243789Sdim } 176243789Sdim } 177243789Sdim } 178243789Sdim} 179243789Sdim 180243789Sdim 181243789Sdimvoid DependenceAnalysis::print(raw_ostream &OS, const Module*) const { 182243789Sdim dumpExampleDependence(OS, F, const_cast<DependenceAnalysis *>(this)); 183243789Sdim} 184243789Sdim 185243789Sdim//===----------------------------------------------------------------------===// 186243789Sdim// Dependence methods 187243789Sdim 188243789Sdim// Returns true if this is an input dependence. 189243789Sdimbool Dependence::isInput() const { 190243789Sdim return Src->mayReadFromMemory() && Dst->mayReadFromMemory(); 191243789Sdim} 192243789Sdim 193243789Sdim 194243789Sdim// Returns true if this is an output dependence. 195243789Sdimbool Dependence::isOutput() const { 196243789Sdim return Src->mayWriteToMemory() && Dst->mayWriteToMemory(); 197243789Sdim} 198243789Sdim 199243789Sdim 200243789Sdim// Returns true if this is an flow (aka true) dependence. 201243789Sdimbool Dependence::isFlow() const { 202243789Sdim return Src->mayWriteToMemory() && Dst->mayReadFromMemory(); 203243789Sdim} 204243789Sdim 205243789Sdim 206243789Sdim// Returns true if this is an anti dependence. 207243789Sdimbool Dependence::isAnti() const { 208243789Sdim return Src->mayReadFromMemory() && Dst->mayWriteToMemory(); 209243789Sdim} 210243789Sdim 211243789Sdim 212243789Sdim// Returns true if a particular level is scalar; that is, 213243789Sdim// if no subscript in the source or destination mention the induction 214243789Sdim// variable associated with the loop at this level. 215243789Sdim// Leave this out of line, so it will serve as a virtual method anchor 216243789Sdimbool Dependence::isScalar(unsigned level) const { 217243789Sdim return false; 218243789Sdim} 219243789Sdim 220243789Sdim 221243789Sdim//===----------------------------------------------------------------------===// 222243789Sdim// FullDependence methods 223243789Sdim 224249423SdimFullDependence::FullDependence(Instruction *Source, 225249423Sdim Instruction *Destination, 226243789Sdim bool PossiblyLoopIndependent, 227243789Sdim unsigned CommonLevels) : 228243789Sdim Dependence(Source, Destination), 229243789Sdim Levels(CommonLevels), 230243789Sdim LoopIndependent(PossiblyLoopIndependent) { 231243789Sdim Consistent = true; 232243789Sdim DV = CommonLevels ? new DVEntry[CommonLevels] : NULL; 233243789Sdim} 234243789Sdim 235243789Sdim// The rest are simple getters that hide the implementation. 236243789Sdim 237243789Sdim// getDirection - Returns the direction associated with a particular level. 238243789Sdimunsigned FullDependence::getDirection(unsigned Level) const { 239243789Sdim assert(0 < Level && Level <= Levels && "Level out of range"); 240243789Sdim return DV[Level - 1].Direction; 241243789Sdim} 242243789Sdim 243243789Sdim 244243789Sdim// Returns the distance (or NULL) associated with a particular level. 245243789Sdimconst SCEV *FullDependence::getDistance(unsigned Level) const { 246243789Sdim assert(0 < Level && Level <= Levels && "Level out of range"); 247243789Sdim return DV[Level - 1].Distance; 248243789Sdim} 249243789Sdim 250243789Sdim 251243789Sdim// Returns true if a particular level is scalar; that is, 252243789Sdim// if no subscript in the source or destination mention the induction 253243789Sdim// variable associated with the loop at this level. 254243789Sdimbool FullDependence::isScalar(unsigned Level) const { 255243789Sdim assert(0 < Level && Level <= Levels && "Level out of range"); 256243789Sdim return DV[Level - 1].Scalar; 257243789Sdim} 258243789Sdim 259243789Sdim 260243789Sdim// Returns true if peeling the first iteration from this loop 261243789Sdim// will break this dependence. 262243789Sdimbool FullDependence::isPeelFirst(unsigned Level) const { 263243789Sdim assert(0 < Level && Level <= Levels && "Level out of range"); 264243789Sdim return DV[Level - 1].PeelFirst; 265243789Sdim} 266243789Sdim 267243789Sdim 268243789Sdim// Returns true if peeling the last iteration from this loop 269243789Sdim// will break this dependence. 270243789Sdimbool FullDependence::isPeelLast(unsigned Level) const { 271243789Sdim assert(0 < Level && Level <= Levels && "Level out of range"); 272243789Sdim return DV[Level - 1].PeelLast; 273243789Sdim} 274243789Sdim 275243789Sdim 276243789Sdim// Returns true if splitting this loop will break the dependence. 277243789Sdimbool FullDependence::isSplitable(unsigned Level) const { 278243789Sdim assert(0 < Level && Level <= Levels && "Level out of range"); 279243789Sdim return DV[Level - 1].Splitable; 280243789Sdim} 281243789Sdim 282243789Sdim 283243789Sdim//===----------------------------------------------------------------------===// 284243789Sdim// DependenceAnalysis::Constraint methods 285243789Sdim 286243789Sdim// If constraint is a point <X, Y>, returns X. 287243789Sdim// Otherwise assert. 288243789Sdimconst SCEV *DependenceAnalysis::Constraint::getX() const { 289243789Sdim assert(Kind == Point && "Kind should be Point"); 290243789Sdim return A; 291243789Sdim} 292243789Sdim 293243789Sdim 294243789Sdim// If constraint is a point <X, Y>, returns Y. 295243789Sdim// Otherwise assert. 296243789Sdimconst SCEV *DependenceAnalysis::Constraint::getY() const { 297243789Sdim assert(Kind == Point && "Kind should be Point"); 298243789Sdim return B; 299243789Sdim} 300243789Sdim 301243789Sdim 302243789Sdim// If constraint is a line AX + BY = C, returns A. 303243789Sdim// Otherwise assert. 304243789Sdimconst SCEV *DependenceAnalysis::Constraint::getA() const { 305243789Sdim assert((Kind == Line || Kind == Distance) && 306243789Sdim "Kind should be Line (or Distance)"); 307243789Sdim return A; 308243789Sdim} 309243789Sdim 310243789Sdim 311243789Sdim// If constraint is a line AX + BY = C, returns B. 312243789Sdim// Otherwise assert. 313243789Sdimconst SCEV *DependenceAnalysis::Constraint::getB() const { 314243789Sdim assert((Kind == Line || Kind == Distance) && 315243789Sdim "Kind should be Line (or Distance)"); 316243789Sdim return B; 317243789Sdim} 318243789Sdim 319243789Sdim 320243789Sdim// If constraint is a line AX + BY = C, returns C. 321243789Sdim// Otherwise assert. 322243789Sdimconst SCEV *DependenceAnalysis::Constraint::getC() const { 323243789Sdim assert((Kind == Line || Kind == Distance) && 324243789Sdim "Kind should be Line (or Distance)"); 325243789Sdim return C; 326243789Sdim} 327243789Sdim 328243789Sdim 329243789Sdim// If constraint is a distance, returns D. 330243789Sdim// Otherwise assert. 331243789Sdimconst SCEV *DependenceAnalysis::Constraint::getD() const { 332243789Sdim assert(Kind == Distance && "Kind should be Distance"); 333243789Sdim return SE->getNegativeSCEV(C); 334243789Sdim} 335243789Sdim 336243789Sdim 337243789Sdim// Returns the loop associated with this constraint. 338243789Sdimconst Loop *DependenceAnalysis::Constraint::getAssociatedLoop() const { 339243789Sdim assert((Kind == Distance || Kind == Line || Kind == Point) && 340243789Sdim "Kind should be Distance, Line, or Point"); 341243789Sdim return AssociatedLoop; 342243789Sdim} 343243789Sdim 344243789Sdim 345243789Sdimvoid DependenceAnalysis::Constraint::setPoint(const SCEV *X, 346243789Sdim const SCEV *Y, 347243789Sdim const Loop *CurLoop) { 348243789Sdim Kind = Point; 349243789Sdim A = X; 350243789Sdim B = Y; 351243789Sdim AssociatedLoop = CurLoop; 352243789Sdim} 353243789Sdim 354243789Sdim 355243789Sdimvoid DependenceAnalysis::Constraint::setLine(const SCEV *AA, 356243789Sdim const SCEV *BB, 357243789Sdim const SCEV *CC, 358243789Sdim const Loop *CurLoop) { 359243789Sdim Kind = Line; 360243789Sdim A = AA; 361243789Sdim B = BB; 362243789Sdim C = CC; 363243789Sdim AssociatedLoop = CurLoop; 364243789Sdim} 365243789Sdim 366243789Sdim 367243789Sdimvoid DependenceAnalysis::Constraint::setDistance(const SCEV *D, 368243789Sdim const Loop *CurLoop) { 369243789Sdim Kind = Distance; 370243789Sdim A = SE->getConstant(D->getType(), 1); 371243789Sdim B = SE->getNegativeSCEV(A); 372243789Sdim C = SE->getNegativeSCEV(D); 373243789Sdim AssociatedLoop = CurLoop; 374243789Sdim} 375243789Sdim 376243789Sdim 377243789Sdimvoid DependenceAnalysis::Constraint::setEmpty() { 378243789Sdim Kind = Empty; 379243789Sdim} 380243789Sdim 381243789Sdim 382243789Sdimvoid DependenceAnalysis::Constraint::setAny(ScalarEvolution *NewSE) { 383243789Sdim SE = NewSE; 384243789Sdim Kind = Any; 385243789Sdim} 386243789Sdim 387243789Sdim 388243789Sdim// For debugging purposes. Dumps the constraint out to OS. 389243789Sdimvoid DependenceAnalysis::Constraint::dump(raw_ostream &OS) const { 390243789Sdim if (isEmpty()) 391243789Sdim OS << " Empty\n"; 392243789Sdim else if (isAny()) 393243789Sdim OS << " Any\n"; 394243789Sdim else if (isPoint()) 395243789Sdim OS << " Point is <" << *getX() << ", " << *getY() << ">\n"; 396243789Sdim else if (isDistance()) 397243789Sdim OS << " Distance is " << *getD() << 398243789Sdim " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n"; 399243789Sdim else if (isLine()) 400243789Sdim OS << " Line is " << *getA() << "*X + " << 401243789Sdim *getB() << "*Y = " << *getC() << "\n"; 402243789Sdim else 403243789Sdim llvm_unreachable("unknown constraint type in Constraint::dump"); 404243789Sdim} 405243789Sdim 406243789Sdim 407243789Sdim// Updates X with the intersection 408243789Sdim// of the Constraints X and Y. Returns true if X has changed. 409243789Sdim// Corresponds to Figure 4 from the paper 410243789Sdim// 411243789Sdim// Practical Dependence Testing 412243789Sdim// Goff, Kennedy, Tseng 413243789Sdim// PLDI 1991 414243789Sdimbool DependenceAnalysis::intersectConstraints(Constraint *X, 415243789Sdim const Constraint *Y) { 416243789Sdim ++DeltaApplications; 417243789Sdim DEBUG(dbgs() << "\tintersect constraints\n"); 418243789Sdim DEBUG(dbgs() << "\t X ="; X->dump(dbgs())); 419243789Sdim DEBUG(dbgs() << "\t Y ="; Y->dump(dbgs())); 420243789Sdim assert(!Y->isPoint() && "Y must not be a Point"); 421243789Sdim if (X->isAny()) { 422243789Sdim if (Y->isAny()) 423243789Sdim return false; 424243789Sdim *X = *Y; 425243789Sdim return true; 426243789Sdim } 427243789Sdim if (X->isEmpty()) 428243789Sdim return false; 429243789Sdim if (Y->isEmpty()) { 430243789Sdim X->setEmpty(); 431243789Sdim return true; 432243789Sdim } 433243789Sdim 434243789Sdim if (X->isDistance() && Y->isDistance()) { 435243789Sdim DEBUG(dbgs() << "\t intersect 2 distances\n"); 436243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD())) 437243789Sdim return false; 438243789Sdim if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) { 439243789Sdim X->setEmpty(); 440243789Sdim ++DeltaSuccesses; 441243789Sdim return true; 442243789Sdim } 443243789Sdim // Hmmm, interesting situation. 444243789Sdim // I guess if either is constant, keep it and ignore the other. 445243789Sdim if (isa<SCEVConstant>(Y->getD())) { 446243789Sdim *X = *Y; 447243789Sdim return true; 448243789Sdim } 449243789Sdim return false; 450243789Sdim } 451243789Sdim 452243789Sdim // At this point, the pseudo-code in Figure 4 of the paper 453243789Sdim // checks if (X->isPoint() && Y->isPoint()). 454243789Sdim // This case can't occur in our implementation, 455243789Sdim // since a Point can only arise as the result of intersecting 456243789Sdim // two Line constraints, and the right-hand value, Y, is never 457243789Sdim // the result of an intersection. 458243789Sdim assert(!(X->isPoint() && Y->isPoint()) && 459243789Sdim "We shouldn't ever see X->isPoint() && Y->isPoint()"); 460243789Sdim 461243789Sdim if (X->isLine() && Y->isLine()) { 462243789Sdim DEBUG(dbgs() << "\t intersect 2 lines\n"); 463243789Sdim const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB()); 464243789Sdim const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA()); 465243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) { 466243789Sdim // slopes are equal, so lines are parallel 467243789Sdim DEBUG(dbgs() << "\t\tsame slope\n"); 468243789Sdim Prod1 = SE->getMulExpr(X->getC(), Y->getB()); 469243789Sdim Prod2 = SE->getMulExpr(X->getB(), Y->getC()); 470243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) 471243789Sdim return false; 472243789Sdim if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) { 473243789Sdim X->setEmpty(); 474243789Sdim ++DeltaSuccesses; 475243789Sdim return true; 476243789Sdim } 477243789Sdim return false; 478243789Sdim } 479243789Sdim if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) { 480243789Sdim // slopes differ, so lines intersect 481243789Sdim DEBUG(dbgs() << "\t\tdifferent slopes\n"); 482243789Sdim const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB()); 483243789Sdim const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA()); 484243789Sdim const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB()); 485243789Sdim const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA()); 486243789Sdim const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB()); 487243789Sdim const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB()); 488243789Sdim const SCEVConstant *C1A2_C2A1 = 489243789Sdim dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1)); 490243789Sdim const SCEVConstant *C1B2_C2B1 = 491243789Sdim dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1)); 492243789Sdim const SCEVConstant *A1B2_A2B1 = 493243789Sdim dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1)); 494243789Sdim const SCEVConstant *A2B1_A1B2 = 495243789Sdim dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2)); 496243789Sdim if (!C1B2_C2B1 || !C1A2_C2A1 || 497243789Sdim !A1B2_A2B1 || !A2B1_A1B2) 498243789Sdim return false; 499243789Sdim APInt Xtop = C1B2_C2B1->getValue()->getValue(); 500243789Sdim APInt Xbot = A1B2_A2B1->getValue()->getValue(); 501243789Sdim APInt Ytop = C1A2_C2A1->getValue()->getValue(); 502243789Sdim APInt Ybot = A2B1_A1B2->getValue()->getValue(); 503243789Sdim DEBUG(dbgs() << "\t\tXtop = " << Xtop << "\n"); 504243789Sdim DEBUG(dbgs() << "\t\tXbot = " << Xbot << "\n"); 505243789Sdim DEBUG(dbgs() << "\t\tYtop = " << Ytop << "\n"); 506243789Sdim DEBUG(dbgs() << "\t\tYbot = " << Ybot << "\n"); 507243789Sdim APInt Xq = Xtop; // these need to be initialized, even 508243789Sdim APInt Xr = Xtop; // though they're just going to be overwritten 509243789Sdim APInt::sdivrem(Xtop, Xbot, Xq, Xr); 510243789Sdim APInt Yq = Ytop; 511243789Sdim APInt Yr = Ytop;; 512243789Sdim APInt::sdivrem(Ytop, Ybot, Yq, Yr); 513243789Sdim if (Xr != 0 || Yr != 0) { 514243789Sdim X->setEmpty(); 515243789Sdim ++DeltaSuccesses; 516243789Sdim return true; 517243789Sdim } 518243789Sdim DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n"); 519243789Sdim if (Xq.slt(0) || Yq.slt(0)) { 520243789Sdim X->setEmpty(); 521243789Sdim ++DeltaSuccesses; 522243789Sdim return true; 523243789Sdim } 524243789Sdim if (const SCEVConstant *CUB = 525243789Sdim collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) { 526243789Sdim APInt UpperBound = CUB->getValue()->getValue(); 527243789Sdim DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n"); 528243789Sdim if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) { 529243789Sdim X->setEmpty(); 530243789Sdim ++DeltaSuccesses; 531243789Sdim return true; 532243789Sdim } 533243789Sdim } 534243789Sdim X->setPoint(SE->getConstant(Xq), 535243789Sdim SE->getConstant(Yq), 536243789Sdim X->getAssociatedLoop()); 537243789Sdim ++DeltaSuccesses; 538243789Sdim return true; 539243789Sdim } 540243789Sdim return false; 541243789Sdim } 542243789Sdim 543243789Sdim // if (X->isLine() && Y->isPoint()) This case can't occur. 544243789Sdim assert(!(X->isLine() && Y->isPoint()) && "This case should never occur"); 545243789Sdim 546243789Sdim if (X->isPoint() && Y->isLine()) { 547243789Sdim DEBUG(dbgs() << "\t intersect Point and Line\n"); 548243789Sdim const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX()); 549243789Sdim const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY()); 550243789Sdim const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1); 551243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC())) 552243789Sdim return false; 553243789Sdim if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) { 554243789Sdim X->setEmpty(); 555243789Sdim ++DeltaSuccesses; 556243789Sdim return true; 557243789Sdim } 558243789Sdim return false; 559243789Sdim } 560243789Sdim 561243789Sdim llvm_unreachable("shouldn't reach the end of Constraint intersection"); 562243789Sdim return false; 563243789Sdim} 564243789Sdim 565243789Sdim 566243789Sdim//===----------------------------------------------------------------------===// 567243789Sdim// DependenceAnalysis methods 568243789Sdim 569243789Sdim// For debugging purposes. Dumps a dependence to OS. 570243789Sdimvoid Dependence::dump(raw_ostream &OS) const { 571243789Sdim bool Splitable = false; 572243789Sdim if (isConfused()) 573243789Sdim OS << "confused"; 574243789Sdim else { 575243789Sdim if (isConsistent()) 576243789Sdim OS << "consistent "; 577243789Sdim if (isFlow()) 578243789Sdim OS << "flow"; 579243789Sdim else if (isOutput()) 580243789Sdim OS << "output"; 581243789Sdim else if (isAnti()) 582243789Sdim OS << "anti"; 583243789Sdim else if (isInput()) 584243789Sdim OS << "input"; 585243789Sdim unsigned Levels = getLevels(); 586249423Sdim OS << " ["; 587249423Sdim for (unsigned II = 1; II <= Levels; ++II) { 588249423Sdim if (isSplitable(II)) 589249423Sdim Splitable = true; 590249423Sdim if (isPeelFirst(II)) 591249423Sdim OS << 'p'; 592249423Sdim const SCEV *Distance = getDistance(II); 593249423Sdim if (Distance) 594249423Sdim OS << *Distance; 595249423Sdim else if (isScalar(II)) 596249423Sdim OS << "S"; 597249423Sdim else { 598249423Sdim unsigned Direction = getDirection(II); 599249423Sdim if (Direction == DVEntry::ALL) 600249423Sdim OS << "*"; 601243789Sdim else { 602249423Sdim if (Direction & DVEntry::LT) 603249423Sdim OS << "<"; 604249423Sdim if (Direction & DVEntry::EQ) 605249423Sdim OS << "="; 606249423Sdim if (Direction & DVEntry::GT) 607249423Sdim OS << ">"; 608243789Sdim } 609243789Sdim } 610249423Sdim if (isPeelLast(II)) 611249423Sdim OS << 'p'; 612249423Sdim if (II < Levels) 613249423Sdim OS << " "; 614243789Sdim } 615249423Sdim if (isLoopIndependent()) 616249423Sdim OS << "|<"; 617249423Sdim OS << "]"; 618249423Sdim if (Splitable) 619249423Sdim OS << " splitable"; 620243789Sdim } 621243789Sdim OS << "!\n"; 622243789Sdim} 623243789Sdim 624243789Sdim 625243789Sdim 626243789Sdimstatic 627243789SdimAliasAnalysis::AliasResult underlyingObjectsAlias(AliasAnalysis *AA, 628243789Sdim const Value *A, 629243789Sdim const Value *B) { 630243789Sdim const Value *AObj = GetUnderlyingObject(A); 631243789Sdim const Value *BObj = GetUnderlyingObject(B); 632243789Sdim return AA->alias(AObj, AA->getTypeStoreSize(AObj->getType()), 633243789Sdim BObj, AA->getTypeStoreSize(BObj->getType())); 634243789Sdim} 635243789Sdim 636243789Sdim 637243789Sdim// Returns true if the load or store can be analyzed. Atomic and volatile 638243789Sdim// operations have properties which this analysis does not understand. 639243789Sdimstatic 640243789Sdimbool isLoadOrStore(const Instruction *I) { 641243789Sdim if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 642243789Sdim return LI->isUnordered(); 643243789Sdim else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) 644243789Sdim return SI->isUnordered(); 645243789Sdim return false; 646243789Sdim} 647243789Sdim 648243789Sdim 649243789Sdimstatic 650249423SdimValue *getPointerOperand(Instruction *I) { 651249423Sdim if (LoadInst *LI = dyn_cast<LoadInst>(I)) 652243789Sdim return LI->getPointerOperand(); 653249423Sdim if (StoreInst *SI = dyn_cast<StoreInst>(I)) 654243789Sdim return SI->getPointerOperand(); 655243789Sdim llvm_unreachable("Value is not load or store instruction"); 656243789Sdim return 0; 657243789Sdim} 658243789Sdim 659243789Sdim 660243789Sdim// Examines the loop nesting of the Src and Dst 661243789Sdim// instructions and establishes their shared loops. Sets the variables 662243789Sdim// CommonLevels, SrcLevels, and MaxLevels. 663243789Sdim// The source and destination instructions needn't be contained in the same 664243789Sdim// loop. The routine establishNestingLevels finds the level of most deeply 665243789Sdim// nested loop that contains them both, CommonLevels. An instruction that's 666243789Sdim// not contained in a loop is at level = 0. MaxLevels is equal to the level 667243789Sdim// of the source plus the level of the destination, minus CommonLevels. 668243789Sdim// This lets us allocate vectors MaxLevels in length, with room for every 669243789Sdim// distinct loop referenced in both the source and destination subscripts. 670243789Sdim// The variable SrcLevels is the nesting depth of the source instruction. 671243789Sdim// It's used to help calculate distinct loops referenced by the destination. 672243789Sdim// Here's the map from loops to levels: 673243789Sdim// 0 - unused 674243789Sdim// 1 - outermost common loop 675243789Sdim// ... - other common loops 676243789Sdim// CommonLevels - innermost common loop 677243789Sdim// ... - loops containing Src but not Dst 678243789Sdim// SrcLevels - innermost loop containing Src but not Dst 679243789Sdim// ... - loops containing Dst but not Src 680243789Sdim// MaxLevels - innermost loops containing Dst but not Src 681243789Sdim// Consider the follow code fragment: 682243789Sdim// for (a = ...) { 683243789Sdim// for (b = ...) { 684243789Sdim// for (c = ...) { 685243789Sdim// for (d = ...) { 686243789Sdim// A[] = ...; 687243789Sdim// } 688243789Sdim// } 689243789Sdim// for (e = ...) { 690243789Sdim// for (f = ...) { 691243789Sdim// for (g = ...) { 692243789Sdim// ... = A[]; 693243789Sdim// } 694243789Sdim// } 695243789Sdim// } 696243789Sdim// } 697243789Sdim// } 698243789Sdim// If we're looking at the possibility of a dependence between the store 699243789Sdim// to A (the Src) and the load from A (the Dst), we'll note that they 700243789Sdim// have 2 loops in common, so CommonLevels will equal 2 and the direction 701243789Sdim// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. 702243789Sdim// A map from loop names to loop numbers would look like 703243789Sdim// a - 1 704243789Sdim// b - 2 = CommonLevels 705243789Sdim// c - 3 706243789Sdim// d - 4 = SrcLevels 707243789Sdim// e - 5 708243789Sdim// f - 6 709243789Sdim// g - 7 = MaxLevels 710243789Sdimvoid DependenceAnalysis::establishNestingLevels(const Instruction *Src, 711243789Sdim const Instruction *Dst) { 712243789Sdim const BasicBlock *SrcBlock = Src->getParent(); 713243789Sdim const BasicBlock *DstBlock = Dst->getParent(); 714243789Sdim unsigned SrcLevel = LI->getLoopDepth(SrcBlock); 715243789Sdim unsigned DstLevel = LI->getLoopDepth(DstBlock); 716243789Sdim const Loop *SrcLoop = LI->getLoopFor(SrcBlock); 717243789Sdim const Loop *DstLoop = LI->getLoopFor(DstBlock); 718243789Sdim SrcLevels = SrcLevel; 719243789Sdim MaxLevels = SrcLevel + DstLevel; 720243789Sdim while (SrcLevel > DstLevel) { 721243789Sdim SrcLoop = SrcLoop->getParentLoop(); 722243789Sdim SrcLevel--; 723243789Sdim } 724243789Sdim while (DstLevel > SrcLevel) { 725243789Sdim DstLoop = DstLoop->getParentLoop(); 726243789Sdim DstLevel--; 727243789Sdim } 728243789Sdim while (SrcLoop != DstLoop) { 729243789Sdim SrcLoop = SrcLoop->getParentLoop(); 730243789Sdim DstLoop = DstLoop->getParentLoop(); 731243789Sdim SrcLevel--; 732243789Sdim } 733243789Sdim CommonLevels = SrcLevel; 734243789Sdim MaxLevels -= CommonLevels; 735243789Sdim} 736243789Sdim 737243789Sdim 738243789Sdim// Given one of the loops containing the source, return 739243789Sdim// its level index in our numbering scheme. 740243789Sdimunsigned DependenceAnalysis::mapSrcLoop(const Loop *SrcLoop) const { 741243789Sdim return SrcLoop->getLoopDepth(); 742243789Sdim} 743243789Sdim 744243789Sdim 745243789Sdim// Given one of the loops containing the destination, 746243789Sdim// return its level index in our numbering scheme. 747243789Sdimunsigned DependenceAnalysis::mapDstLoop(const Loop *DstLoop) const { 748243789Sdim unsigned D = DstLoop->getLoopDepth(); 749243789Sdim if (D > CommonLevels) 750243789Sdim return D - CommonLevels + SrcLevels; 751243789Sdim else 752243789Sdim return D; 753243789Sdim} 754243789Sdim 755243789Sdim 756243789Sdim// Returns true if Expression is loop invariant in LoopNest. 757243789Sdimbool DependenceAnalysis::isLoopInvariant(const SCEV *Expression, 758243789Sdim const Loop *LoopNest) const { 759243789Sdim if (!LoopNest) 760243789Sdim return true; 761243789Sdim return SE->isLoopInvariant(Expression, LoopNest) && 762243789Sdim isLoopInvariant(Expression, LoopNest->getParentLoop()); 763243789Sdim} 764243789Sdim 765243789Sdim 766243789Sdim 767243789Sdim// Finds the set of loops from the LoopNest that 768243789Sdim// have a level <= CommonLevels and are referred to by the SCEV Expression. 769243789Sdimvoid DependenceAnalysis::collectCommonLoops(const SCEV *Expression, 770243789Sdim const Loop *LoopNest, 771243789Sdim SmallBitVector &Loops) const { 772243789Sdim while (LoopNest) { 773243789Sdim unsigned Level = LoopNest->getLoopDepth(); 774243789Sdim if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest)) 775243789Sdim Loops.set(Level); 776243789Sdim LoopNest = LoopNest->getParentLoop(); 777243789Sdim } 778243789Sdim} 779243789Sdim 780243789Sdim 781243789Sdim// removeMatchingExtensions - Examines a subscript pair. 782243789Sdim// If the source and destination are identically sign (or zero) 783243789Sdim// extended, it strips off the extension in an effect to simplify 784243789Sdim// the actual analysis. 785243789Sdimvoid DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) { 786243789Sdim const SCEV *Src = Pair->Src; 787243789Sdim const SCEV *Dst = Pair->Dst; 788243789Sdim if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) || 789243789Sdim (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) { 790243789Sdim const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src); 791243789Sdim const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst); 792243789Sdim if (SrcCast->getType() == DstCast->getType()) { 793243789Sdim Pair->Src = SrcCast->getOperand(); 794243789Sdim Pair->Dst = DstCast->getOperand(); 795243789Sdim } 796243789Sdim } 797243789Sdim} 798243789Sdim 799243789Sdim 800243789Sdim// Examine the scev and return true iff it's linear. 801243789Sdim// Collect any loops mentioned in the set of "Loops". 802243789Sdimbool DependenceAnalysis::checkSrcSubscript(const SCEV *Src, 803243789Sdim const Loop *LoopNest, 804243789Sdim SmallBitVector &Loops) { 805243789Sdim const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src); 806243789Sdim if (!AddRec) 807243789Sdim return isLoopInvariant(Src, LoopNest); 808243789Sdim const SCEV *Start = AddRec->getStart(); 809243789Sdim const SCEV *Step = AddRec->getStepRecurrence(*SE); 810243789Sdim if (!isLoopInvariant(Step, LoopNest)) 811243789Sdim return false; 812243789Sdim Loops.set(mapSrcLoop(AddRec->getLoop())); 813243789Sdim return checkSrcSubscript(Start, LoopNest, Loops); 814243789Sdim} 815243789Sdim 816243789Sdim 817243789Sdim 818243789Sdim// Examine the scev and return true iff it's linear. 819243789Sdim// Collect any loops mentioned in the set of "Loops". 820243789Sdimbool DependenceAnalysis::checkDstSubscript(const SCEV *Dst, 821243789Sdim const Loop *LoopNest, 822243789Sdim SmallBitVector &Loops) { 823243789Sdim const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst); 824243789Sdim if (!AddRec) 825243789Sdim return isLoopInvariant(Dst, LoopNest); 826243789Sdim const SCEV *Start = AddRec->getStart(); 827243789Sdim const SCEV *Step = AddRec->getStepRecurrence(*SE); 828243789Sdim if (!isLoopInvariant(Step, LoopNest)) 829243789Sdim return false; 830243789Sdim Loops.set(mapDstLoop(AddRec->getLoop())); 831243789Sdim return checkDstSubscript(Start, LoopNest, Loops); 832243789Sdim} 833243789Sdim 834243789Sdim 835243789Sdim// Examines the subscript pair (the Src and Dst SCEVs) 836243789Sdim// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. 837243789Sdim// Collects the associated loops in a set. 838243789SdimDependenceAnalysis::Subscript::ClassificationKind 839243789SdimDependenceAnalysis::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, 840243789Sdim const SCEV *Dst, const Loop *DstLoopNest, 841243789Sdim SmallBitVector &Loops) { 842243789Sdim SmallBitVector SrcLoops(MaxLevels + 1); 843243789Sdim SmallBitVector DstLoops(MaxLevels + 1); 844243789Sdim if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops)) 845243789Sdim return Subscript::NonLinear; 846243789Sdim if (!checkDstSubscript(Dst, DstLoopNest, DstLoops)) 847243789Sdim return Subscript::NonLinear; 848243789Sdim Loops = SrcLoops; 849243789Sdim Loops |= DstLoops; 850243789Sdim unsigned N = Loops.count(); 851243789Sdim if (N == 0) 852243789Sdim return Subscript::ZIV; 853243789Sdim if (N == 1) 854243789Sdim return Subscript::SIV; 855243789Sdim if (N == 2 && (SrcLoops.count() == 0 || 856243789Sdim DstLoops.count() == 0 || 857243789Sdim (SrcLoops.count() == 1 && DstLoops.count() == 1))) 858243789Sdim return Subscript::RDIV; 859243789Sdim return Subscript::MIV; 860243789Sdim} 861243789Sdim 862243789Sdim 863243789Sdim// A wrapper around SCEV::isKnownPredicate. 864243789Sdim// Looks for cases where we're interested in comparing for equality. 865243789Sdim// If both X and Y have been identically sign or zero extended, 866243789Sdim// it strips off the (confusing) extensions before invoking 867243789Sdim// SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package 868243789Sdim// will be similarly updated. 869243789Sdim// 870243789Sdim// If SCEV::isKnownPredicate can't prove the predicate, 871243789Sdim// we try simple subtraction, which seems to help in some cases 872243789Sdim// involving symbolics. 873243789Sdimbool DependenceAnalysis::isKnownPredicate(ICmpInst::Predicate Pred, 874243789Sdim const SCEV *X, 875243789Sdim const SCEV *Y) const { 876243789Sdim if (Pred == CmpInst::ICMP_EQ || 877243789Sdim Pred == CmpInst::ICMP_NE) { 878243789Sdim if ((isa<SCEVSignExtendExpr>(X) && 879243789Sdim isa<SCEVSignExtendExpr>(Y)) || 880243789Sdim (isa<SCEVZeroExtendExpr>(X) && 881243789Sdim isa<SCEVZeroExtendExpr>(Y))) { 882243789Sdim const SCEVCastExpr *CX = cast<SCEVCastExpr>(X); 883243789Sdim const SCEVCastExpr *CY = cast<SCEVCastExpr>(Y); 884243789Sdim const SCEV *Xop = CX->getOperand(); 885243789Sdim const SCEV *Yop = CY->getOperand(); 886243789Sdim if (Xop->getType() == Yop->getType()) { 887243789Sdim X = Xop; 888243789Sdim Y = Yop; 889243789Sdim } 890243789Sdim } 891243789Sdim } 892243789Sdim if (SE->isKnownPredicate(Pred, X, Y)) 893243789Sdim return true; 894243789Sdim // If SE->isKnownPredicate can't prove the condition, 895243789Sdim // we try the brute-force approach of subtracting 896243789Sdim // and testing the difference. 897243789Sdim // By testing with SE->isKnownPredicate first, we avoid 898243789Sdim // the possibility of overflow when the arguments are constants. 899243789Sdim const SCEV *Delta = SE->getMinusSCEV(X, Y); 900243789Sdim switch (Pred) { 901243789Sdim case CmpInst::ICMP_EQ: 902243789Sdim return Delta->isZero(); 903243789Sdim case CmpInst::ICMP_NE: 904243789Sdim return SE->isKnownNonZero(Delta); 905243789Sdim case CmpInst::ICMP_SGE: 906243789Sdim return SE->isKnownNonNegative(Delta); 907243789Sdim case CmpInst::ICMP_SLE: 908243789Sdim return SE->isKnownNonPositive(Delta); 909243789Sdim case CmpInst::ICMP_SGT: 910243789Sdim return SE->isKnownPositive(Delta); 911243789Sdim case CmpInst::ICMP_SLT: 912243789Sdim return SE->isKnownNegative(Delta); 913243789Sdim default: 914243789Sdim llvm_unreachable("unexpected predicate in isKnownPredicate"); 915243789Sdim } 916243789Sdim} 917243789Sdim 918243789Sdim 919243789Sdim// All subscripts are all the same type. 920243789Sdim// Loop bound may be smaller (e.g., a char). 921243789Sdim// Should zero extend loop bound, since it's always >= 0. 922243789Sdim// This routine collects upper bound and extends if needed. 923243789Sdim// Return null if no bound available. 924243789Sdimconst SCEV *DependenceAnalysis::collectUpperBound(const Loop *L, 925243789Sdim Type *T) const { 926243789Sdim if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 927243789Sdim const SCEV *UB = SE->getBackedgeTakenCount(L); 928243789Sdim return SE->getNoopOrZeroExtend(UB, T); 929243789Sdim } 930243789Sdim return NULL; 931243789Sdim} 932243789Sdim 933243789Sdim 934243789Sdim// Calls collectUpperBound(), then attempts to cast it to SCEVConstant. 935243789Sdim// If the cast fails, returns NULL. 936243789Sdimconst SCEVConstant *DependenceAnalysis::collectConstantUpperBound(const Loop *L, 937243789Sdim Type *T 938243789Sdim ) const { 939243789Sdim if (const SCEV *UB = collectUpperBound(L, T)) 940243789Sdim return dyn_cast<SCEVConstant>(UB); 941243789Sdim return NULL; 942243789Sdim} 943243789Sdim 944243789Sdim 945243789Sdim// testZIV - 946243789Sdim// When we have a pair of subscripts of the form [c1] and [c2], 947243789Sdim// where c1 and c2 are both loop invariant, we attack it using 948243789Sdim// the ZIV test. Basically, we test by comparing the two values, 949243789Sdim// but there are actually three possible results: 950243789Sdim// 1) the values are equal, so there's a dependence 951243789Sdim// 2) the values are different, so there's no dependence 952243789Sdim// 3) the values might be equal, so we have to assume a dependence. 953243789Sdim// 954243789Sdim// Return true if dependence disproved. 955243789Sdimbool DependenceAnalysis::testZIV(const SCEV *Src, 956243789Sdim const SCEV *Dst, 957243789Sdim FullDependence &Result) const { 958243789Sdim DEBUG(dbgs() << " src = " << *Src << "\n"); 959243789Sdim DEBUG(dbgs() << " dst = " << *Dst << "\n"); 960243789Sdim ++ZIVapplications; 961243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) { 962243789Sdim DEBUG(dbgs() << " provably dependent\n"); 963243789Sdim return false; // provably dependent 964243789Sdim } 965243789Sdim if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) { 966243789Sdim DEBUG(dbgs() << " provably independent\n"); 967243789Sdim ++ZIVindependence; 968243789Sdim return true; // provably independent 969243789Sdim } 970243789Sdim DEBUG(dbgs() << " possibly dependent\n"); 971243789Sdim Result.Consistent = false; 972243789Sdim return false; // possibly dependent 973243789Sdim} 974243789Sdim 975243789Sdim 976243789Sdim// strongSIVtest - 977243789Sdim// From the paper, Practical Dependence Testing, Section 4.2.1 978243789Sdim// 979243789Sdim// When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i], 980243789Sdim// where i is an induction variable, c1 and c2 are loop invariant, 981243789Sdim// and a is a constant, we can solve it exactly using the Strong SIV test. 982243789Sdim// 983243789Sdim// Can prove independence. Failing that, can compute distance (and direction). 984243789Sdim// In the presence of symbolic terms, we can sometimes make progress. 985243789Sdim// 986243789Sdim// If there's a dependence, 987243789Sdim// 988243789Sdim// c1 + a*i = c2 + a*i' 989243789Sdim// 990243789Sdim// The dependence distance is 991243789Sdim// 992243789Sdim// d = i' - i = (c1 - c2)/a 993243789Sdim// 994243789Sdim// A dependence only exists if d is an integer and abs(d) <= U, where U is the 995243789Sdim// loop's upper bound. If a dependence exists, the dependence direction is 996243789Sdim// defined as 997243789Sdim// 998243789Sdim// { < if d > 0 999243789Sdim// direction = { = if d = 0 1000243789Sdim// { > if d < 0 1001243789Sdim// 1002243789Sdim// Return true if dependence disproved. 1003243789Sdimbool DependenceAnalysis::strongSIVtest(const SCEV *Coeff, 1004243789Sdim const SCEV *SrcConst, 1005243789Sdim const SCEV *DstConst, 1006243789Sdim const Loop *CurLoop, 1007243789Sdim unsigned Level, 1008243789Sdim FullDependence &Result, 1009243789Sdim Constraint &NewConstraint) const { 1010243789Sdim DEBUG(dbgs() << "\tStrong SIV test\n"); 1011243789Sdim DEBUG(dbgs() << "\t Coeff = " << *Coeff); 1012243789Sdim DEBUG(dbgs() << ", " << *Coeff->getType() << "\n"); 1013243789Sdim DEBUG(dbgs() << "\t SrcConst = " << *SrcConst); 1014243789Sdim DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n"); 1015243789Sdim DEBUG(dbgs() << "\t DstConst = " << *DstConst); 1016243789Sdim DEBUG(dbgs() << ", " << *DstConst->getType() << "\n"); 1017243789Sdim ++StrongSIVapplications; 1018243789Sdim assert(0 < Level && Level <= CommonLevels && "level out of range"); 1019243789Sdim Level--; 1020243789Sdim 1021243789Sdim const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); 1022243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta); 1023243789Sdim DEBUG(dbgs() << ", " << *Delta->getType() << "\n"); 1024243789Sdim 1025243789Sdim // check that |Delta| < iteration count 1026243789Sdim if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1027243789Sdim DEBUG(dbgs() << "\t UpperBound = " << *UpperBound); 1028243789Sdim DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n"); 1029243789Sdim const SCEV *AbsDelta = 1030243789Sdim SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta); 1031243789Sdim const SCEV *AbsCoeff = 1032243789Sdim SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff); 1033243789Sdim const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff); 1034243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product)) { 1035243789Sdim // Distance greater than trip count - no dependence 1036243789Sdim ++StrongSIVindependence; 1037243789Sdim ++StrongSIVsuccesses; 1038243789Sdim return true; 1039243789Sdim } 1040243789Sdim } 1041243789Sdim 1042243789Sdim // Can we compute distance? 1043243789Sdim if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) { 1044243789Sdim APInt ConstDelta = cast<SCEVConstant>(Delta)->getValue()->getValue(); 1045243789Sdim APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getValue()->getValue(); 1046243789Sdim APInt Distance = ConstDelta; // these need to be initialized 1047243789Sdim APInt Remainder = ConstDelta; 1048243789Sdim APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder); 1049243789Sdim DEBUG(dbgs() << "\t Distance = " << Distance << "\n"); 1050243789Sdim DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n"); 1051243789Sdim // Make sure Coeff divides Delta exactly 1052243789Sdim if (Remainder != 0) { 1053243789Sdim // Coeff doesn't divide Distance, no dependence 1054243789Sdim ++StrongSIVindependence; 1055243789Sdim ++StrongSIVsuccesses; 1056243789Sdim return true; 1057243789Sdim } 1058243789Sdim Result.DV[Level].Distance = SE->getConstant(Distance); 1059243789Sdim NewConstraint.setDistance(SE->getConstant(Distance), CurLoop); 1060243789Sdim if (Distance.sgt(0)) 1061243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::LT; 1062243789Sdim else if (Distance.slt(0)) 1063243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::GT; 1064243789Sdim else 1065243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::EQ; 1066243789Sdim ++StrongSIVsuccesses; 1067243789Sdim } 1068243789Sdim else if (Delta->isZero()) { 1069243789Sdim // since 0/X == 0 1070243789Sdim Result.DV[Level].Distance = Delta; 1071243789Sdim NewConstraint.setDistance(Delta, CurLoop); 1072243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::EQ; 1073243789Sdim ++StrongSIVsuccesses; 1074243789Sdim } 1075243789Sdim else { 1076243789Sdim if (Coeff->isOne()) { 1077243789Sdim DEBUG(dbgs() << "\t Distance = " << *Delta << "\n"); 1078243789Sdim Result.DV[Level].Distance = Delta; // since X/1 == X 1079243789Sdim NewConstraint.setDistance(Delta, CurLoop); 1080243789Sdim } 1081243789Sdim else { 1082243789Sdim Result.Consistent = false; 1083243789Sdim NewConstraint.setLine(Coeff, 1084243789Sdim SE->getNegativeSCEV(Coeff), 1085243789Sdim SE->getNegativeSCEV(Delta), CurLoop); 1086243789Sdim } 1087243789Sdim 1088243789Sdim // maybe we can get a useful direction 1089243789Sdim bool DeltaMaybeZero = !SE->isKnownNonZero(Delta); 1090243789Sdim bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta); 1091243789Sdim bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta); 1092243789Sdim bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff); 1093243789Sdim bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff); 1094243789Sdim // The double negatives above are confusing. 1095243789Sdim // It helps to read !SE->isKnownNonZero(Delta) 1096243789Sdim // as "Delta might be Zero" 1097243789Sdim unsigned NewDirection = Dependence::DVEntry::NONE; 1098243789Sdim if ((DeltaMaybePositive && CoeffMaybePositive) || 1099243789Sdim (DeltaMaybeNegative && CoeffMaybeNegative)) 1100243789Sdim NewDirection = Dependence::DVEntry::LT; 1101243789Sdim if (DeltaMaybeZero) 1102243789Sdim NewDirection |= Dependence::DVEntry::EQ; 1103243789Sdim if ((DeltaMaybeNegative && CoeffMaybePositive) || 1104243789Sdim (DeltaMaybePositive && CoeffMaybeNegative)) 1105243789Sdim NewDirection |= Dependence::DVEntry::GT; 1106243789Sdim if (NewDirection < Result.DV[Level].Direction) 1107243789Sdim ++StrongSIVsuccesses; 1108243789Sdim Result.DV[Level].Direction &= NewDirection; 1109243789Sdim } 1110243789Sdim return false; 1111243789Sdim} 1112243789Sdim 1113243789Sdim 1114243789Sdim// weakCrossingSIVtest - 1115243789Sdim// From the paper, Practical Dependence Testing, Section 4.2.2 1116243789Sdim// 1117243789Sdim// When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i], 1118243789Sdim// where i is an induction variable, c1 and c2 are loop invariant, 1119243789Sdim// and a is a constant, we can solve it exactly using the 1120243789Sdim// Weak-Crossing SIV test. 1121243789Sdim// 1122243789Sdim// Given c1 + a*i = c2 - a*i', we can look for the intersection of 1123243789Sdim// the two lines, where i = i', yielding 1124243789Sdim// 1125243789Sdim// c1 + a*i = c2 - a*i 1126243789Sdim// 2a*i = c2 - c1 1127243789Sdim// i = (c2 - c1)/2a 1128243789Sdim// 1129243789Sdim// If i < 0, there is no dependence. 1130243789Sdim// If i > upperbound, there is no dependence. 1131243789Sdim// If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0. 1132243789Sdim// If i = upperbound, there's a dependence with distance = 0. 1133243789Sdim// If i is integral, there's a dependence (all directions). 1134243789Sdim// If the non-integer part = 1/2, there's a dependence (<> directions). 1135243789Sdim// Otherwise, there's no dependence. 1136243789Sdim// 1137243789Sdim// Can prove independence. Failing that, 1138243789Sdim// can sometimes refine the directions. 1139243789Sdim// Can determine iteration for splitting. 1140243789Sdim// 1141243789Sdim// Return true if dependence disproved. 1142243789Sdimbool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff, 1143243789Sdim const SCEV *SrcConst, 1144243789Sdim const SCEV *DstConst, 1145243789Sdim const Loop *CurLoop, 1146243789Sdim unsigned Level, 1147243789Sdim FullDependence &Result, 1148243789Sdim Constraint &NewConstraint, 1149243789Sdim const SCEV *&SplitIter) const { 1150243789Sdim DEBUG(dbgs() << "\tWeak-Crossing SIV test\n"); 1151243789Sdim DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n"); 1152243789Sdim DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1153243789Sdim DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1154243789Sdim ++WeakCrossingSIVapplications; 1155243789Sdim assert(0 < Level && Level <= CommonLevels && "Level out of range"); 1156243789Sdim Level--; 1157243789Sdim Result.Consistent = false; 1158243789Sdim const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1159243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1160243789Sdim NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop); 1161243789Sdim if (Delta->isZero()) { 1162243789Sdim Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT); 1163243789Sdim Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT); 1164243789Sdim ++WeakCrossingSIVsuccesses; 1165243789Sdim if (!Result.DV[Level].Direction) { 1166243789Sdim ++WeakCrossingSIVindependence; 1167243789Sdim return true; 1168243789Sdim } 1169243789Sdim Result.DV[Level].Distance = Delta; // = 0 1170243789Sdim return false; 1171243789Sdim } 1172243789Sdim const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff); 1173243789Sdim if (!ConstCoeff) 1174243789Sdim return false; 1175243789Sdim 1176243789Sdim Result.DV[Level].Splitable = true; 1177243789Sdim if (SE->isKnownNegative(ConstCoeff)) { 1178243789Sdim ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff)); 1179243789Sdim assert(ConstCoeff && 1180243789Sdim "dynamic cast of negative of ConstCoeff should yield constant"); 1181243789Sdim Delta = SE->getNegativeSCEV(Delta); 1182243789Sdim } 1183243789Sdim assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"); 1184243789Sdim 1185243789Sdim // compute SplitIter for use by DependenceAnalysis::getSplitIteration() 1186243789Sdim SplitIter = 1187243789Sdim SE->getUDivExpr(SE->getSMaxExpr(SE->getConstant(Delta->getType(), 0), 1188243789Sdim Delta), 1189243789Sdim SE->getMulExpr(SE->getConstant(Delta->getType(), 2), 1190243789Sdim ConstCoeff)); 1191243789Sdim DEBUG(dbgs() << "\t Split iter = " << *SplitIter << "\n"); 1192243789Sdim 1193243789Sdim const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta); 1194243789Sdim if (!ConstDelta) 1195243789Sdim return false; 1196243789Sdim 1197243789Sdim // We're certain that ConstCoeff > 0; therefore, 1198243789Sdim // if Delta < 0, then no dependence. 1199243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1200243789Sdim DEBUG(dbgs() << "\t ConstCoeff = " << *ConstCoeff << "\n"); 1201243789Sdim if (SE->isKnownNegative(Delta)) { 1202243789Sdim // No dependence, Delta < 0 1203243789Sdim ++WeakCrossingSIVindependence; 1204243789Sdim ++WeakCrossingSIVsuccesses; 1205243789Sdim return true; 1206243789Sdim } 1207243789Sdim 1208243789Sdim // We're certain that Delta > 0 and ConstCoeff > 0. 1209243789Sdim // Check Delta/(2*ConstCoeff) against upper loop bound 1210243789Sdim if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1211243789Sdim DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); 1212243789Sdim const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2); 1213243789Sdim const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), 1214243789Sdim ConstantTwo); 1215243789Sdim DEBUG(dbgs() << "\t ML = " << *ML << "\n"); 1216243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) { 1217243789Sdim // Delta too big, no dependence 1218243789Sdim ++WeakCrossingSIVindependence; 1219243789Sdim ++WeakCrossingSIVsuccesses; 1220243789Sdim return true; 1221243789Sdim } 1222243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) { 1223243789Sdim // i = i' = UB 1224243789Sdim Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT); 1225243789Sdim Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT); 1226243789Sdim ++WeakCrossingSIVsuccesses; 1227243789Sdim if (!Result.DV[Level].Direction) { 1228243789Sdim ++WeakCrossingSIVindependence; 1229243789Sdim return true; 1230243789Sdim } 1231243789Sdim Result.DV[Level].Splitable = false; 1232243789Sdim Result.DV[Level].Distance = SE->getConstant(Delta->getType(), 0); 1233243789Sdim return false; 1234243789Sdim } 1235243789Sdim } 1236243789Sdim 1237243789Sdim // check that Coeff divides Delta 1238243789Sdim APInt APDelta = ConstDelta->getValue()->getValue(); 1239243789Sdim APInt APCoeff = ConstCoeff->getValue()->getValue(); 1240243789Sdim APInt Distance = APDelta; // these need to be initialzed 1241243789Sdim APInt Remainder = APDelta; 1242243789Sdim APInt::sdivrem(APDelta, APCoeff, Distance, Remainder); 1243243789Sdim DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n"); 1244243789Sdim if (Remainder != 0) { 1245243789Sdim // Coeff doesn't divide Delta, no dependence 1246243789Sdim ++WeakCrossingSIVindependence; 1247243789Sdim ++WeakCrossingSIVsuccesses; 1248243789Sdim return true; 1249243789Sdim } 1250243789Sdim DEBUG(dbgs() << "\t Distance = " << Distance << "\n"); 1251243789Sdim 1252243789Sdim // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible 1253243789Sdim APInt Two = APInt(Distance.getBitWidth(), 2, true); 1254243789Sdim Remainder = Distance.srem(Two); 1255243789Sdim DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n"); 1256243789Sdim if (Remainder != 0) { 1257243789Sdim // Equal direction isn't possible 1258243789Sdim Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ); 1259243789Sdim ++WeakCrossingSIVsuccesses; 1260243789Sdim } 1261243789Sdim return false; 1262243789Sdim} 1263243789Sdim 1264243789Sdim 1265243789Sdim// Kirch's algorithm, from 1266243789Sdim// 1267243789Sdim// Optimizing Supercompilers for Supercomputers 1268243789Sdim// Michael Wolfe 1269243789Sdim// MIT Press, 1989 1270243789Sdim// 1271243789Sdim// Program 2.1, page 29. 1272243789Sdim// Computes the GCD of AM and BM. 1273243789Sdim// Also finds a solution to the equation ax - by = gdc(a, b). 1274243789Sdim// Returns true iff the gcd divides Delta. 1275243789Sdimstatic 1276243789Sdimbool findGCD(unsigned Bits, APInt AM, APInt BM, APInt Delta, 1277243789Sdim APInt &G, APInt &X, APInt &Y) { 1278243789Sdim APInt A0(Bits, 1, true), A1(Bits, 0, true); 1279243789Sdim APInt B0(Bits, 0, true), B1(Bits, 1, true); 1280243789Sdim APInt G0 = AM.abs(); 1281243789Sdim APInt G1 = BM.abs(); 1282243789Sdim APInt Q = G0; // these need to be initialized 1283243789Sdim APInt R = G0; 1284243789Sdim APInt::sdivrem(G0, G1, Q, R); 1285243789Sdim while (R != 0) { 1286243789Sdim APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2; 1287243789Sdim APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2; 1288243789Sdim G0 = G1; G1 = R; 1289243789Sdim APInt::sdivrem(G0, G1, Q, R); 1290243789Sdim } 1291243789Sdim G = G1; 1292243789Sdim DEBUG(dbgs() << "\t GCD = " << G << "\n"); 1293243789Sdim X = AM.slt(0) ? -A1 : A1; 1294243789Sdim Y = BM.slt(0) ? B1 : -B1; 1295243789Sdim 1296243789Sdim // make sure gcd divides Delta 1297243789Sdim R = Delta.srem(G); 1298243789Sdim if (R != 0) 1299243789Sdim return true; // gcd doesn't divide Delta, no dependence 1300243789Sdim Q = Delta.sdiv(G); 1301243789Sdim X *= Q; 1302243789Sdim Y *= Q; 1303243789Sdim return false; 1304243789Sdim} 1305243789Sdim 1306243789Sdim 1307243789Sdimstatic 1308243789SdimAPInt floorOfQuotient(APInt A, APInt B) { 1309243789Sdim APInt Q = A; // these need to be initialized 1310243789Sdim APInt R = A; 1311243789Sdim APInt::sdivrem(A, B, Q, R); 1312243789Sdim if (R == 0) 1313243789Sdim return Q; 1314243789Sdim if ((A.sgt(0) && B.sgt(0)) || 1315243789Sdim (A.slt(0) && B.slt(0))) 1316243789Sdim return Q; 1317243789Sdim else 1318243789Sdim return Q - 1; 1319243789Sdim} 1320243789Sdim 1321243789Sdim 1322243789Sdimstatic 1323243789SdimAPInt ceilingOfQuotient(APInt A, APInt B) { 1324243789Sdim APInt Q = A; // these need to be initialized 1325243789Sdim APInt R = A; 1326243789Sdim APInt::sdivrem(A, B, Q, R); 1327243789Sdim if (R == 0) 1328243789Sdim return Q; 1329243789Sdim if ((A.sgt(0) && B.sgt(0)) || 1330243789Sdim (A.slt(0) && B.slt(0))) 1331243789Sdim return Q + 1; 1332243789Sdim else 1333243789Sdim return Q; 1334243789Sdim} 1335243789Sdim 1336243789Sdim 1337243789Sdimstatic 1338243789SdimAPInt maxAPInt(APInt A, APInt B) { 1339243789Sdim return A.sgt(B) ? A : B; 1340243789Sdim} 1341243789Sdim 1342243789Sdim 1343243789Sdimstatic 1344243789SdimAPInt minAPInt(APInt A, APInt B) { 1345243789Sdim return A.slt(B) ? A : B; 1346243789Sdim} 1347243789Sdim 1348243789Sdim 1349243789Sdim// exactSIVtest - 1350243789Sdim// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i], 1351243789Sdim// where i is an induction variable, c1 and c2 are loop invariant, and a1 1352243789Sdim// and a2 are constant, we can solve it exactly using an algorithm developed 1353243789Sdim// by Banerjee and Wolfe. See Section 2.5.3 in 1354243789Sdim// 1355243789Sdim// Optimizing Supercompilers for Supercomputers 1356243789Sdim// Michael Wolfe 1357243789Sdim// MIT Press, 1989 1358243789Sdim// 1359243789Sdim// It's slower than the specialized tests (strong SIV, weak-zero SIV, etc), 1360243789Sdim// so use them if possible. They're also a bit better with symbolics and, 1361243789Sdim// in the case of the strong SIV test, can compute Distances. 1362243789Sdim// 1363243789Sdim// Return true if dependence disproved. 1364243789Sdimbool DependenceAnalysis::exactSIVtest(const SCEV *SrcCoeff, 1365243789Sdim const SCEV *DstCoeff, 1366243789Sdim const SCEV *SrcConst, 1367243789Sdim const SCEV *DstConst, 1368243789Sdim const Loop *CurLoop, 1369243789Sdim unsigned Level, 1370243789Sdim FullDependence &Result, 1371243789Sdim Constraint &NewConstraint) const { 1372243789Sdim DEBUG(dbgs() << "\tExact SIV test\n"); 1373243789Sdim DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n"); 1374243789Sdim DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n"); 1375243789Sdim DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1376243789Sdim DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1377243789Sdim ++ExactSIVapplications; 1378243789Sdim assert(0 < Level && Level <= CommonLevels && "Level out of range"); 1379243789Sdim Level--; 1380243789Sdim Result.Consistent = false; 1381243789Sdim const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1382243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1383243789Sdim NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), 1384243789Sdim Delta, CurLoop); 1385243789Sdim const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta); 1386243789Sdim const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff); 1387243789Sdim const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff); 1388243789Sdim if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff) 1389243789Sdim return false; 1390243789Sdim 1391243789Sdim // find gcd 1392243789Sdim APInt G, X, Y; 1393243789Sdim APInt AM = ConstSrcCoeff->getValue()->getValue(); 1394243789Sdim APInt BM = ConstDstCoeff->getValue()->getValue(); 1395243789Sdim unsigned Bits = AM.getBitWidth(); 1396243789Sdim if (findGCD(Bits, AM, BM, ConstDelta->getValue()->getValue(), G, X, Y)) { 1397243789Sdim // gcd doesn't divide Delta, no dependence 1398243789Sdim ++ExactSIVindependence; 1399243789Sdim ++ExactSIVsuccesses; 1400243789Sdim return true; 1401243789Sdim } 1402243789Sdim 1403243789Sdim DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n"); 1404243789Sdim 1405243789Sdim // since SCEV construction normalizes, LM = 0 1406243789Sdim APInt UM(Bits, 1, true); 1407243789Sdim bool UMvalid = false; 1408243789Sdim // UM is perhaps unavailable, let's check 1409243789Sdim if (const SCEVConstant *CUB = 1410243789Sdim collectConstantUpperBound(CurLoop, Delta->getType())) { 1411243789Sdim UM = CUB->getValue()->getValue(); 1412243789Sdim DEBUG(dbgs() << "\t UM = " << UM << "\n"); 1413243789Sdim UMvalid = true; 1414243789Sdim } 1415243789Sdim 1416243789Sdim APInt TU(APInt::getSignedMaxValue(Bits)); 1417243789Sdim APInt TL(APInt::getSignedMinValue(Bits)); 1418243789Sdim 1419243789Sdim // test(BM/G, LM-X) and test(-BM/G, X-UM) 1420243789Sdim APInt TMUL = BM.sdiv(G); 1421243789Sdim if (TMUL.sgt(0)) { 1422243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL)); 1423243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1424243789Sdim if (UMvalid) { 1425243789Sdim TU = minAPInt(TU, floorOfQuotient(UM - X, TMUL)); 1426243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1427243789Sdim } 1428243789Sdim } 1429243789Sdim else { 1430243789Sdim TU = minAPInt(TU, floorOfQuotient(-X, TMUL)); 1431243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1432243789Sdim if (UMvalid) { 1433243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(UM - X, TMUL)); 1434243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1435243789Sdim } 1436243789Sdim } 1437243789Sdim 1438243789Sdim // test(AM/G, LM-Y) and test(-AM/G, Y-UM) 1439243789Sdim TMUL = AM.sdiv(G); 1440243789Sdim if (TMUL.sgt(0)) { 1441243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL)); 1442243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1443243789Sdim if (UMvalid) { 1444243789Sdim TU = minAPInt(TU, floorOfQuotient(UM - Y, TMUL)); 1445243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1446243789Sdim } 1447243789Sdim } 1448243789Sdim else { 1449243789Sdim TU = minAPInt(TU, floorOfQuotient(-Y, TMUL)); 1450243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1451243789Sdim if (UMvalid) { 1452243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(UM - Y, TMUL)); 1453243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1454243789Sdim } 1455243789Sdim } 1456243789Sdim if (TL.sgt(TU)) { 1457243789Sdim ++ExactSIVindependence; 1458243789Sdim ++ExactSIVsuccesses; 1459243789Sdim return true; 1460243789Sdim } 1461243789Sdim 1462243789Sdim // explore directions 1463243789Sdim unsigned NewDirection = Dependence::DVEntry::NONE; 1464243789Sdim 1465243789Sdim // less than 1466243789Sdim APInt SaveTU(TU); // save these 1467243789Sdim APInt SaveTL(TL); 1468243789Sdim DEBUG(dbgs() << "\t exploring LT direction\n"); 1469243789Sdim TMUL = AM - BM; 1470243789Sdim if (TMUL.sgt(0)) { 1471243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(X - Y + 1, TMUL)); 1472243789Sdim DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1473243789Sdim } 1474243789Sdim else { 1475243789Sdim TU = minAPInt(TU, floorOfQuotient(X - Y + 1, TMUL)); 1476243789Sdim DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1477243789Sdim } 1478243789Sdim if (TL.sle(TU)) { 1479243789Sdim NewDirection |= Dependence::DVEntry::LT; 1480243789Sdim ++ExactSIVsuccesses; 1481243789Sdim } 1482243789Sdim 1483243789Sdim // equal 1484243789Sdim TU = SaveTU; // restore 1485243789Sdim TL = SaveTL; 1486243789Sdim DEBUG(dbgs() << "\t exploring EQ direction\n"); 1487243789Sdim if (TMUL.sgt(0)) { 1488243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(X - Y, TMUL)); 1489243789Sdim DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1490243789Sdim } 1491243789Sdim else { 1492243789Sdim TU = minAPInt(TU, floorOfQuotient(X - Y, TMUL)); 1493243789Sdim DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1494243789Sdim } 1495243789Sdim TMUL = BM - AM; 1496243789Sdim if (TMUL.sgt(0)) { 1497243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(Y - X, TMUL)); 1498243789Sdim DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1499243789Sdim } 1500243789Sdim else { 1501243789Sdim TU = minAPInt(TU, floorOfQuotient(Y - X, TMUL)); 1502243789Sdim DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1503243789Sdim } 1504243789Sdim if (TL.sle(TU)) { 1505243789Sdim NewDirection |= Dependence::DVEntry::EQ; 1506243789Sdim ++ExactSIVsuccesses; 1507243789Sdim } 1508243789Sdim 1509243789Sdim // greater than 1510243789Sdim TU = SaveTU; // restore 1511243789Sdim TL = SaveTL; 1512243789Sdim DEBUG(dbgs() << "\t exploring GT direction\n"); 1513243789Sdim if (TMUL.sgt(0)) { 1514243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(Y - X + 1, TMUL)); 1515243789Sdim DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1516243789Sdim } 1517243789Sdim else { 1518243789Sdim TU = minAPInt(TU, floorOfQuotient(Y - X + 1, TMUL)); 1519243789Sdim DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1520243789Sdim } 1521243789Sdim if (TL.sle(TU)) { 1522243789Sdim NewDirection |= Dependence::DVEntry::GT; 1523243789Sdim ++ExactSIVsuccesses; 1524243789Sdim } 1525243789Sdim 1526243789Sdim // finished 1527243789Sdim Result.DV[Level].Direction &= NewDirection; 1528243789Sdim if (Result.DV[Level].Direction == Dependence::DVEntry::NONE) 1529243789Sdim ++ExactSIVindependence; 1530243789Sdim return Result.DV[Level].Direction == Dependence::DVEntry::NONE; 1531243789Sdim} 1532243789Sdim 1533243789Sdim 1534243789Sdim 1535243789Sdim// Return true if the divisor evenly divides the dividend. 1536243789Sdimstatic 1537243789Sdimbool isRemainderZero(const SCEVConstant *Dividend, 1538243789Sdim const SCEVConstant *Divisor) { 1539243789Sdim APInt ConstDividend = Dividend->getValue()->getValue(); 1540243789Sdim APInt ConstDivisor = Divisor->getValue()->getValue(); 1541243789Sdim return ConstDividend.srem(ConstDivisor) == 0; 1542243789Sdim} 1543243789Sdim 1544243789Sdim 1545243789Sdim// weakZeroSrcSIVtest - 1546243789Sdim// From the paper, Practical Dependence Testing, Section 4.2.2 1547243789Sdim// 1548243789Sdim// When we have a pair of subscripts of the form [c1] and [c2 + a*i], 1549243789Sdim// where i is an induction variable, c1 and c2 are loop invariant, 1550243789Sdim// and a is a constant, we can solve it exactly using the 1551243789Sdim// Weak-Zero SIV test. 1552243789Sdim// 1553243789Sdim// Given 1554243789Sdim// 1555243789Sdim// c1 = c2 + a*i 1556243789Sdim// 1557243789Sdim// we get 1558243789Sdim// 1559243789Sdim// (c1 - c2)/a = i 1560243789Sdim// 1561243789Sdim// If i is not an integer, there's no dependence. 1562243789Sdim// If i < 0 or > UB, there's no dependence. 1563243789Sdim// If i = 0, the direction is <= and peeling the 1564243789Sdim// 1st iteration will break the dependence. 1565243789Sdim// If i = UB, the direction is >= and peeling the 1566243789Sdim// last iteration will break the dependence. 1567243789Sdim// Otherwise, the direction is *. 1568243789Sdim// 1569243789Sdim// Can prove independence. Failing that, we can sometimes refine 1570243789Sdim// the directions. Can sometimes show that first or last 1571243789Sdim// iteration carries all the dependences (so worth peeling). 1572243789Sdim// 1573243789Sdim// (see also weakZeroDstSIVtest) 1574243789Sdim// 1575243789Sdim// Return true if dependence disproved. 1576243789Sdimbool DependenceAnalysis::weakZeroSrcSIVtest(const SCEV *DstCoeff, 1577243789Sdim const SCEV *SrcConst, 1578243789Sdim const SCEV *DstConst, 1579243789Sdim const Loop *CurLoop, 1580243789Sdim unsigned Level, 1581243789Sdim FullDependence &Result, 1582243789Sdim Constraint &NewConstraint) const { 1583243789Sdim // For the WeakSIV test, it's possible the loop isn't common to 1584243789Sdim // the Src and Dst loops. If it isn't, then there's no need to 1585243789Sdim // record a direction. 1586243789Sdim DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n"); 1587243789Sdim DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n"); 1588243789Sdim DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1589243789Sdim DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1590243789Sdim ++WeakZeroSIVapplications; 1591243789Sdim assert(0 < Level && Level <= MaxLevels && "Level out of range"); 1592243789Sdim Level--; 1593243789Sdim Result.Consistent = false; 1594243789Sdim const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); 1595243789Sdim NewConstraint.setLine(SE->getConstant(Delta->getType(), 0), 1596243789Sdim DstCoeff, Delta, CurLoop); 1597243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1598243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) { 1599243789Sdim if (Level < CommonLevels) { 1600243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::LE; 1601243789Sdim Result.DV[Level].PeelFirst = true; 1602243789Sdim ++WeakZeroSIVsuccesses; 1603243789Sdim } 1604243789Sdim return false; // dependences caused by first iteration 1605243789Sdim } 1606243789Sdim const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff); 1607243789Sdim if (!ConstCoeff) 1608243789Sdim return false; 1609243789Sdim const SCEV *AbsCoeff = 1610243789Sdim SE->isKnownNegative(ConstCoeff) ? 1611243789Sdim SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; 1612243789Sdim const SCEV *NewDelta = 1613243789Sdim SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; 1614243789Sdim 1615243789Sdim // check that Delta/SrcCoeff < iteration count 1616243789Sdim // really check NewDelta < count*AbsCoeff 1617243789Sdim if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1618243789Sdim DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); 1619243789Sdim const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); 1620243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) { 1621243789Sdim ++WeakZeroSIVindependence; 1622243789Sdim ++WeakZeroSIVsuccesses; 1623243789Sdim return true; 1624243789Sdim } 1625243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { 1626243789Sdim // dependences caused by last iteration 1627243789Sdim if (Level < CommonLevels) { 1628243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::GE; 1629243789Sdim Result.DV[Level].PeelLast = true; 1630243789Sdim ++WeakZeroSIVsuccesses; 1631243789Sdim } 1632243789Sdim return false; 1633243789Sdim } 1634243789Sdim } 1635243789Sdim 1636243789Sdim // check that Delta/SrcCoeff >= 0 1637243789Sdim // really check that NewDelta >= 0 1638243789Sdim if (SE->isKnownNegative(NewDelta)) { 1639243789Sdim // No dependence, newDelta < 0 1640243789Sdim ++WeakZeroSIVindependence; 1641243789Sdim ++WeakZeroSIVsuccesses; 1642243789Sdim return true; 1643243789Sdim } 1644243789Sdim 1645243789Sdim // if SrcCoeff doesn't divide Delta, then no dependence 1646243789Sdim if (isa<SCEVConstant>(Delta) && 1647243789Sdim !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) { 1648243789Sdim ++WeakZeroSIVindependence; 1649243789Sdim ++WeakZeroSIVsuccesses; 1650243789Sdim return true; 1651243789Sdim } 1652243789Sdim return false; 1653243789Sdim} 1654243789Sdim 1655243789Sdim 1656243789Sdim// weakZeroDstSIVtest - 1657243789Sdim// From the paper, Practical Dependence Testing, Section 4.2.2 1658243789Sdim// 1659243789Sdim// When we have a pair of subscripts of the form [c1 + a*i] and [c2], 1660243789Sdim// where i is an induction variable, c1 and c2 are loop invariant, 1661243789Sdim// and a is a constant, we can solve it exactly using the 1662243789Sdim// Weak-Zero SIV test. 1663243789Sdim// 1664243789Sdim// Given 1665243789Sdim// 1666243789Sdim// c1 + a*i = c2 1667243789Sdim// 1668243789Sdim// we get 1669243789Sdim// 1670243789Sdim// i = (c2 - c1)/a 1671243789Sdim// 1672243789Sdim// If i is not an integer, there's no dependence. 1673243789Sdim// If i < 0 or > UB, there's no dependence. 1674243789Sdim// If i = 0, the direction is <= and peeling the 1675243789Sdim// 1st iteration will break the dependence. 1676243789Sdim// If i = UB, the direction is >= and peeling the 1677243789Sdim// last iteration will break the dependence. 1678243789Sdim// Otherwise, the direction is *. 1679243789Sdim// 1680243789Sdim// Can prove independence. Failing that, we can sometimes refine 1681243789Sdim// the directions. Can sometimes show that first or last 1682243789Sdim// iteration carries all the dependences (so worth peeling). 1683243789Sdim// 1684243789Sdim// (see also weakZeroSrcSIVtest) 1685243789Sdim// 1686243789Sdim// Return true if dependence disproved. 1687243789Sdimbool DependenceAnalysis::weakZeroDstSIVtest(const SCEV *SrcCoeff, 1688243789Sdim const SCEV *SrcConst, 1689243789Sdim const SCEV *DstConst, 1690243789Sdim const Loop *CurLoop, 1691243789Sdim unsigned Level, 1692243789Sdim FullDependence &Result, 1693243789Sdim Constraint &NewConstraint) const { 1694243789Sdim // For the WeakSIV test, it's possible the loop isn't common to the 1695243789Sdim // Src and Dst loops. If it isn't, then there's no need to record a direction. 1696243789Sdim DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n"); 1697243789Sdim DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n"); 1698243789Sdim DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1699243789Sdim DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1700243789Sdim ++WeakZeroSIVapplications; 1701243789Sdim assert(0 < Level && Level <= SrcLevels && "Level out of range"); 1702243789Sdim Level--; 1703243789Sdim Result.Consistent = false; 1704243789Sdim const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1705243789Sdim NewConstraint.setLine(SrcCoeff, SE->getConstant(Delta->getType(), 0), 1706243789Sdim Delta, CurLoop); 1707243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1708243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) { 1709243789Sdim if (Level < CommonLevels) { 1710243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::LE; 1711243789Sdim Result.DV[Level].PeelFirst = true; 1712243789Sdim ++WeakZeroSIVsuccesses; 1713243789Sdim } 1714243789Sdim return false; // dependences caused by first iteration 1715243789Sdim } 1716243789Sdim const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff); 1717243789Sdim if (!ConstCoeff) 1718243789Sdim return false; 1719243789Sdim const SCEV *AbsCoeff = 1720243789Sdim SE->isKnownNegative(ConstCoeff) ? 1721243789Sdim SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; 1722243789Sdim const SCEV *NewDelta = 1723243789Sdim SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; 1724243789Sdim 1725243789Sdim // check that Delta/SrcCoeff < iteration count 1726243789Sdim // really check NewDelta < count*AbsCoeff 1727243789Sdim if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1728243789Sdim DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); 1729243789Sdim const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); 1730243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) { 1731243789Sdim ++WeakZeroSIVindependence; 1732243789Sdim ++WeakZeroSIVsuccesses; 1733243789Sdim return true; 1734243789Sdim } 1735243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { 1736243789Sdim // dependences caused by last iteration 1737243789Sdim if (Level < CommonLevels) { 1738243789Sdim Result.DV[Level].Direction &= Dependence::DVEntry::GE; 1739243789Sdim Result.DV[Level].PeelLast = true; 1740243789Sdim ++WeakZeroSIVsuccesses; 1741243789Sdim } 1742243789Sdim return false; 1743243789Sdim } 1744243789Sdim } 1745243789Sdim 1746243789Sdim // check that Delta/SrcCoeff >= 0 1747243789Sdim // really check that NewDelta >= 0 1748243789Sdim if (SE->isKnownNegative(NewDelta)) { 1749243789Sdim // No dependence, newDelta < 0 1750243789Sdim ++WeakZeroSIVindependence; 1751243789Sdim ++WeakZeroSIVsuccesses; 1752243789Sdim return true; 1753243789Sdim } 1754243789Sdim 1755243789Sdim // if SrcCoeff doesn't divide Delta, then no dependence 1756243789Sdim if (isa<SCEVConstant>(Delta) && 1757243789Sdim !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) { 1758243789Sdim ++WeakZeroSIVindependence; 1759243789Sdim ++WeakZeroSIVsuccesses; 1760243789Sdim return true; 1761243789Sdim } 1762243789Sdim return false; 1763243789Sdim} 1764243789Sdim 1765243789Sdim 1766243789Sdim// exactRDIVtest - Tests the RDIV subscript pair for dependence. 1767243789Sdim// Things of the form [c1 + a*i] and [c2 + b*j], 1768243789Sdim// where i and j are induction variable, c1 and c2 are loop invariant, 1769243789Sdim// and a and b are constants. 1770243789Sdim// Returns true if any possible dependence is disproved. 1771243789Sdim// Marks the result as inconsistent. 1772243789Sdim// Works in some cases that symbolicRDIVtest doesn't, and vice versa. 1773243789Sdimbool DependenceAnalysis::exactRDIVtest(const SCEV *SrcCoeff, 1774243789Sdim const SCEV *DstCoeff, 1775243789Sdim const SCEV *SrcConst, 1776243789Sdim const SCEV *DstConst, 1777243789Sdim const Loop *SrcLoop, 1778243789Sdim const Loop *DstLoop, 1779243789Sdim FullDependence &Result) const { 1780243789Sdim DEBUG(dbgs() << "\tExact RDIV test\n"); 1781243789Sdim DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n"); 1782243789Sdim DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n"); 1783243789Sdim DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1784243789Sdim DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1785243789Sdim ++ExactRDIVapplications; 1786243789Sdim Result.Consistent = false; 1787243789Sdim const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1788243789Sdim DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1789243789Sdim const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta); 1790243789Sdim const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff); 1791243789Sdim const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff); 1792243789Sdim if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff) 1793243789Sdim return false; 1794243789Sdim 1795243789Sdim // find gcd 1796243789Sdim APInt G, X, Y; 1797243789Sdim APInt AM = ConstSrcCoeff->getValue()->getValue(); 1798243789Sdim APInt BM = ConstDstCoeff->getValue()->getValue(); 1799243789Sdim unsigned Bits = AM.getBitWidth(); 1800243789Sdim if (findGCD(Bits, AM, BM, ConstDelta->getValue()->getValue(), G, X, Y)) { 1801243789Sdim // gcd doesn't divide Delta, no dependence 1802243789Sdim ++ExactRDIVindependence; 1803243789Sdim return true; 1804243789Sdim } 1805243789Sdim 1806243789Sdim DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n"); 1807243789Sdim 1808243789Sdim // since SCEV construction seems to normalize, LM = 0 1809243789Sdim APInt SrcUM(Bits, 1, true); 1810243789Sdim bool SrcUMvalid = false; 1811243789Sdim // SrcUM is perhaps unavailable, let's check 1812243789Sdim if (const SCEVConstant *UpperBound = 1813243789Sdim collectConstantUpperBound(SrcLoop, Delta->getType())) { 1814243789Sdim SrcUM = UpperBound->getValue()->getValue(); 1815243789Sdim DEBUG(dbgs() << "\t SrcUM = " << SrcUM << "\n"); 1816243789Sdim SrcUMvalid = true; 1817243789Sdim } 1818243789Sdim 1819243789Sdim APInt DstUM(Bits, 1, true); 1820243789Sdim bool DstUMvalid = false; 1821243789Sdim // UM is perhaps unavailable, let's check 1822243789Sdim if (const SCEVConstant *UpperBound = 1823243789Sdim collectConstantUpperBound(DstLoop, Delta->getType())) { 1824243789Sdim DstUM = UpperBound->getValue()->getValue(); 1825243789Sdim DEBUG(dbgs() << "\t DstUM = " << DstUM << "\n"); 1826243789Sdim DstUMvalid = true; 1827243789Sdim } 1828243789Sdim 1829243789Sdim APInt TU(APInt::getSignedMaxValue(Bits)); 1830243789Sdim APInt TL(APInt::getSignedMinValue(Bits)); 1831243789Sdim 1832243789Sdim // test(BM/G, LM-X) and test(-BM/G, X-UM) 1833243789Sdim APInt TMUL = BM.sdiv(G); 1834243789Sdim if (TMUL.sgt(0)) { 1835243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL)); 1836243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1837243789Sdim if (SrcUMvalid) { 1838243789Sdim TU = minAPInt(TU, floorOfQuotient(SrcUM - X, TMUL)); 1839243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1840243789Sdim } 1841243789Sdim } 1842243789Sdim else { 1843243789Sdim TU = minAPInt(TU, floorOfQuotient(-X, TMUL)); 1844243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1845243789Sdim if (SrcUMvalid) { 1846243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(SrcUM - X, TMUL)); 1847243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1848243789Sdim } 1849243789Sdim } 1850243789Sdim 1851243789Sdim // test(AM/G, LM-Y) and test(-AM/G, Y-UM) 1852243789Sdim TMUL = AM.sdiv(G); 1853243789Sdim if (TMUL.sgt(0)) { 1854243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL)); 1855243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1856243789Sdim if (DstUMvalid) { 1857243789Sdim TU = minAPInt(TU, floorOfQuotient(DstUM - Y, TMUL)); 1858243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1859243789Sdim } 1860243789Sdim } 1861243789Sdim else { 1862243789Sdim TU = minAPInt(TU, floorOfQuotient(-Y, TMUL)); 1863243789Sdim DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1864243789Sdim if (DstUMvalid) { 1865243789Sdim TL = maxAPInt(TL, ceilingOfQuotient(DstUM - Y, TMUL)); 1866243789Sdim DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1867243789Sdim } 1868243789Sdim } 1869243789Sdim if (TL.sgt(TU)) 1870243789Sdim ++ExactRDIVindependence; 1871243789Sdim return TL.sgt(TU); 1872243789Sdim} 1873243789Sdim 1874243789Sdim 1875243789Sdim// symbolicRDIVtest - 1876243789Sdim// In Section 4.5 of the Practical Dependence Testing paper,the authors 1877243789Sdim// introduce a special case of Banerjee's Inequalities (also called the 1878243789Sdim// Extreme-Value Test) that can handle some of the SIV and RDIV cases, 1879243789Sdim// particularly cases with symbolics. Since it's only able to disprove 1880243789Sdim// dependence (not compute distances or directions), we'll use it as a 1881243789Sdim// fall back for the other tests. 1882243789Sdim// 1883243789Sdim// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j] 1884243789Sdim// where i and j are induction variables and c1 and c2 are loop invariants, 1885243789Sdim// we can use the symbolic tests to disprove some dependences, serving as a 1886243789Sdim// backup for the RDIV test. Note that i and j can be the same variable, 1887243789Sdim// letting this test serve as a backup for the various SIV tests. 1888243789Sdim// 1889243789Sdim// For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some 1890243789Sdim// 0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized) 1891243789Sdim// loop bounds for the i and j loops, respectively. So, ... 1892243789Sdim// 1893243789Sdim// c1 + a1*i = c2 + a2*j 1894243789Sdim// a1*i - a2*j = c2 - c1 1895243789Sdim// 1896243789Sdim// To test for a dependence, we compute c2 - c1 and make sure it's in the 1897243789Sdim// range of the maximum and minimum possible values of a1*i - a2*j. 1898243789Sdim// Considering the signs of a1 and a2, we have 4 possible cases: 1899243789Sdim// 1900243789Sdim// 1) If a1 >= 0 and a2 >= 0, then 1901243789Sdim// a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0 1902243789Sdim// -a2*N2 <= c2 - c1 <= a1*N1 1903243789Sdim// 1904243789Sdim// 2) If a1 >= 0 and a2 <= 0, then 1905243789Sdim// a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2 1906243789Sdim// 0 <= c2 - c1 <= a1*N1 - a2*N2 1907243789Sdim// 1908243789Sdim// 3) If a1 <= 0 and a2 >= 0, then 1909243789Sdim// a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0 1910243789Sdim// a1*N1 - a2*N2 <= c2 - c1 <= 0 1911243789Sdim// 1912243789Sdim// 4) If a1 <= 0 and a2 <= 0, then 1913243789Sdim// a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2 1914243789Sdim// a1*N1 <= c2 - c1 <= -a2*N2 1915243789Sdim// 1916243789Sdim// return true if dependence disproved 1917243789Sdimbool DependenceAnalysis::symbolicRDIVtest(const SCEV *A1, 1918243789Sdim const SCEV *A2, 1919243789Sdim const SCEV *C1, 1920243789Sdim const SCEV *C2, 1921243789Sdim const Loop *Loop1, 1922243789Sdim const Loop *Loop2) const { 1923243789Sdim ++SymbolicRDIVapplications; 1924243789Sdim DEBUG(dbgs() << "\ttry symbolic RDIV test\n"); 1925243789Sdim DEBUG(dbgs() << "\t A1 = " << *A1); 1926243789Sdim DEBUG(dbgs() << ", type = " << *A1->getType() << "\n"); 1927243789Sdim DEBUG(dbgs() << "\t A2 = " << *A2 << "\n"); 1928243789Sdim DEBUG(dbgs() << "\t C1 = " << *C1 << "\n"); 1929243789Sdim DEBUG(dbgs() << "\t C2 = " << *C2 << "\n"); 1930243789Sdim const SCEV *N1 = collectUpperBound(Loop1, A1->getType()); 1931243789Sdim const SCEV *N2 = collectUpperBound(Loop2, A1->getType()); 1932243789Sdim DEBUG(if (N1) dbgs() << "\t N1 = " << *N1 << "\n"); 1933243789Sdim DEBUG(if (N2) dbgs() << "\t N2 = " << *N2 << "\n"); 1934243789Sdim const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1); 1935243789Sdim const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2); 1936243789Sdim DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n"); 1937243789Sdim DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n"); 1938243789Sdim if (SE->isKnownNonNegative(A1)) { 1939243789Sdim if (SE->isKnownNonNegative(A2)) { 1940243789Sdim // A1 >= 0 && A2 >= 0 1941243789Sdim if (N1) { 1942243789Sdim // make sure that c2 - c1 <= a1*N1 1943243789Sdim const SCEV *A1N1 = SE->getMulExpr(A1, N1); 1944243789Sdim DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n"); 1945243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) { 1946243789Sdim ++SymbolicRDIVindependence; 1947243789Sdim return true; 1948243789Sdim } 1949243789Sdim } 1950243789Sdim if (N2) { 1951243789Sdim // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2 1952243789Sdim const SCEV *A2N2 = SE->getMulExpr(A2, N2); 1953243789Sdim DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n"); 1954243789Sdim if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) { 1955243789Sdim ++SymbolicRDIVindependence; 1956243789Sdim return true; 1957243789Sdim } 1958243789Sdim } 1959243789Sdim } 1960243789Sdim else if (SE->isKnownNonPositive(A2)) { 1961243789Sdim // a1 >= 0 && a2 <= 0 1962243789Sdim if (N1 && N2) { 1963243789Sdim // make sure that c2 - c1 <= a1*N1 - a2*N2 1964243789Sdim const SCEV *A1N1 = SE->getMulExpr(A1, N1); 1965243789Sdim const SCEV *A2N2 = SE->getMulExpr(A2, N2); 1966243789Sdim const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); 1967243789Sdim DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); 1968243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) { 1969243789Sdim ++SymbolicRDIVindependence; 1970243789Sdim return true; 1971243789Sdim } 1972243789Sdim } 1973243789Sdim // make sure that 0 <= c2 - c1 1974243789Sdim if (SE->isKnownNegative(C2_C1)) { 1975243789Sdim ++SymbolicRDIVindependence; 1976243789Sdim return true; 1977243789Sdim } 1978243789Sdim } 1979243789Sdim } 1980243789Sdim else if (SE->isKnownNonPositive(A1)) { 1981243789Sdim if (SE->isKnownNonNegative(A2)) { 1982243789Sdim // a1 <= 0 && a2 >= 0 1983243789Sdim if (N1 && N2) { 1984243789Sdim // make sure that a1*N1 - a2*N2 <= c2 - c1 1985243789Sdim const SCEV *A1N1 = SE->getMulExpr(A1, N1); 1986243789Sdim const SCEV *A2N2 = SE->getMulExpr(A2, N2); 1987243789Sdim const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); 1988243789Sdim DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); 1989243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) { 1990243789Sdim ++SymbolicRDIVindependence; 1991243789Sdim return true; 1992243789Sdim } 1993243789Sdim } 1994243789Sdim // make sure that c2 - c1 <= 0 1995243789Sdim if (SE->isKnownPositive(C2_C1)) { 1996243789Sdim ++SymbolicRDIVindependence; 1997243789Sdim return true; 1998243789Sdim } 1999243789Sdim } 2000243789Sdim else if (SE->isKnownNonPositive(A2)) { 2001243789Sdim // a1 <= 0 && a2 <= 0 2002243789Sdim if (N1) { 2003243789Sdim // make sure that a1*N1 <= c2 - c1 2004243789Sdim const SCEV *A1N1 = SE->getMulExpr(A1, N1); 2005243789Sdim DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n"); 2006243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) { 2007243789Sdim ++SymbolicRDIVindependence; 2008243789Sdim return true; 2009243789Sdim } 2010243789Sdim } 2011243789Sdim if (N2) { 2012243789Sdim // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2 2013243789Sdim const SCEV *A2N2 = SE->getMulExpr(A2, N2); 2014243789Sdim DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n"); 2015243789Sdim if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) { 2016243789Sdim ++SymbolicRDIVindependence; 2017243789Sdim return true; 2018243789Sdim } 2019243789Sdim } 2020243789Sdim } 2021243789Sdim } 2022243789Sdim return false; 2023243789Sdim} 2024243789Sdim 2025243789Sdim 2026243789Sdim// testSIV - 2027243789Sdim// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i] 2028243789Sdim// where i is an induction variable, c1 and c2 are loop invariant, and a1 and 2029243789Sdim// a2 are constant, we attack it with an SIV test. While they can all be 2030243789Sdim// solved with the Exact SIV test, it's worthwhile to use simpler tests when 2031243789Sdim// they apply; they're cheaper and sometimes more precise. 2032243789Sdim// 2033243789Sdim// Return true if dependence disproved. 2034243789Sdimbool DependenceAnalysis::testSIV(const SCEV *Src, 2035243789Sdim const SCEV *Dst, 2036243789Sdim unsigned &Level, 2037243789Sdim FullDependence &Result, 2038243789Sdim Constraint &NewConstraint, 2039243789Sdim const SCEV *&SplitIter) const { 2040243789Sdim DEBUG(dbgs() << " src = " << *Src << "\n"); 2041243789Sdim DEBUG(dbgs() << " dst = " << *Dst << "\n"); 2042243789Sdim const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src); 2043243789Sdim const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst); 2044243789Sdim if (SrcAddRec && DstAddRec) { 2045243789Sdim const SCEV *SrcConst = SrcAddRec->getStart(); 2046243789Sdim const SCEV *DstConst = DstAddRec->getStart(); 2047243789Sdim const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); 2048243789Sdim const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); 2049243789Sdim const Loop *CurLoop = SrcAddRec->getLoop(); 2050243789Sdim assert(CurLoop == DstAddRec->getLoop() && 2051243789Sdim "both loops in SIV should be same"); 2052243789Sdim Level = mapSrcLoop(CurLoop); 2053243789Sdim bool disproven; 2054243789Sdim if (SrcCoeff == DstCoeff) 2055243789Sdim disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop, 2056243789Sdim Level, Result, NewConstraint); 2057243789Sdim else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff)) 2058243789Sdim disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop, 2059243789Sdim Level, Result, NewConstraint, SplitIter); 2060243789Sdim else 2061243789Sdim disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, 2062243789Sdim Level, Result, NewConstraint); 2063243789Sdim return disproven || 2064243789Sdim gcdMIVtest(Src, Dst, Result) || 2065243789Sdim symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop); 2066243789Sdim } 2067243789Sdim if (SrcAddRec) { 2068243789Sdim const SCEV *SrcConst = SrcAddRec->getStart(); 2069243789Sdim const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); 2070243789Sdim const SCEV *DstConst = Dst; 2071243789Sdim const Loop *CurLoop = SrcAddRec->getLoop(); 2072243789Sdim Level = mapSrcLoop(CurLoop); 2073243789Sdim return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop, 2074243789Sdim Level, Result, NewConstraint) || 2075243789Sdim gcdMIVtest(Src, Dst, Result); 2076243789Sdim } 2077243789Sdim if (DstAddRec) { 2078243789Sdim const SCEV *DstConst = DstAddRec->getStart(); 2079243789Sdim const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); 2080243789Sdim const SCEV *SrcConst = Src; 2081243789Sdim const Loop *CurLoop = DstAddRec->getLoop(); 2082243789Sdim Level = mapDstLoop(CurLoop); 2083243789Sdim return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, 2084243789Sdim CurLoop, Level, Result, NewConstraint) || 2085243789Sdim gcdMIVtest(Src, Dst, Result); 2086243789Sdim } 2087243789Sdim llvm_unreachable("SIV test expected at least one AddRec"); 2088243789Sdim return false; 2089243789Sdim} 2090243789Sdim 2091243789Sdim 2092243789Sdim// testRDIV - 2093243789Sdim// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j] 2094243789Sdim// where i and j are induction variables, c1 and c2 are loop invariant, 2095243789Sdim// and a1 and a2 are constant, we can solve it exactly with an easy adaptation 2096243789Sdim// of the Exact SIV test, the Restricted Double Index Variable (RDIV) test. 2097243789Sdim// It doesn't make sense to talk about distance or direction in this case, 2098243789Sdim// so there's no point in making special versions of the Strong SIV test or 2099243789Sdim// the Weak-crossing SIV test. 2100243789Sdim// 2101243789Sdim// With minor algebra, this test can also be used for things like 2102243789Sdim// [c1 + a1*i + a2*j][c2]. 2103243789Sdim// 2104243789Sdim// Return true if dependence disproved. 2105243789Sdimbool DependenceAnalysis::testRDIV(const SCEV *Src, 2106243789Sdim const SCEV *Dst, 2107243789Sdim FullDependence &Result) const { 2108243789Sdim // we have 3 possible situations here: 2109243789Sdim // 1) [a*i + b] and [c*j + d] 2110243789Sdim // 2) [a*i + c*j + b] and [d] 2111243789Sdim // 3) [b] and [a*i + c*j + d] 2112243789Sdim // We need to find what we've got and get organized 2113243789Sdim 2114243789Sdim const SCEV *SrcConst, *DstConst; 2115243789Sdim const SCEV *SrcCoeff, *DstCoeff; 2116243789Sdim const Loop *SrcLoop, *DstLoop; 2117243789Sdim 2118243789Sdim DEBUG(dbgs() << " src = " << *Src << "\n"); 2119243789Sdim DEBUG(dbgs() << " dst = " << *Dst << "\n"); 2120243789Sdim const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src); 2121243789Sdim const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst); 2122243789Sdim if (SrcAddRec && DstAddRec) { 2123243789Sdim SrcConst = SrcAddRec->getStart(); 2124243789Sdim SrcCoeff = SrcAddRec->getStepRecurrence(*SE); 2125243789Sdim SrcLoop = SrcAddRec->getLoop(); 2126243789Sdim DstConst = DstAddRec->getStart(); 2127243789Sdim DstCoeff = DstAddRec->getStepRecurrence(*SE); 2128243789Sdim DstLoop = DstAddRec->getLoop(); 2129243789Sdim } 2130243789Sdim else if (SrcAddRec) { 2131243789Sdim if (const SCEVAddRecExpr *tmpAddRec = 2132243789Sdim dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) { 2133243789Sdim SrcConst = tmpAddRec->getStart(); 2134243789Sdim SrcCoeff = tmpAddRec->getStepRecurrence(*SE); 2135243789Sdim SrcLoop = tmpAddRec->getLoop(); 2136243789Sdim DstConst = Dst; 2137243789Sdim DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE)); 2138243789Sdim DstLoop = SrcAddRec->getLoop(); 2139243789Sdim } 2140243789Sdim else 2141243789Sdim llvm_unreachable("RDIV reached by surprising SCEVs"); 2142243789Sdim } 2143243789Sdim else if (DstAddRec) { 2144243789Sdim if (const SCEVAddRecExpr *tmpAddRec = 2145243789Sdim dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) { 2146243789Sdim DstConst = tmpAddRec->getStart(); 2147243789Sdim DstCoeff = tmpAddRec->getStepRecurrence(*SE); 2148243789Sdim DstLoop = tmpAddRec->getLoop(); 2149243789Sdim SrcConst = Src; 2150243789Sdim SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE)); 2151243789Sdim SrcLoop = DstAddRec->getLoop(); 2152243789Sdim } 2153243789Sdim else 2154243789Sdim llvm_unreachable("RDIV reached by surprising SCEVs"); 2155243789Sdim } 2156243789Sdim else 2157243789Sdim llvm_unreachable("RDIV expected at least one AddRec"); 2158243789Sdim return exactRDIVtest(SrcCoeff, DstCoeff, 2159243789Sdim SrcConst, DstConst, 2160243789Sdim SrcLoop, DstLoop, 2161243789Sdim Result) || 2162243789Sdim gcdMIVtest(Src, Dst, Result) || 2163243789Sdim symbolicRDIVtest(SrcCoeff, DstCoeff, 2164243789Sdim SrcConst, DstConst, 2165243789Sdim SrcLoop, DstLoop); 2166243789Sdim} 2167243789Sdim 2168243789Sdim 2169243789Sdim// Tests the single-subscript MIV pair (Src and Dst) for dependence. 2170243789Sdim// Return true if dependence disproved. 2171243789Sdim// Can sometimes refine direction vectors. 2172243789Sdimbool DependenceAnalysis::testMIV(const SCEV *Src, 2173243789Sdim const SCEV *Dst, 2174243789Sdim const SmallBitVector &Loops, 2175243789Sdim FullDependence &Result) const { 2176243789Sdim DEBUG(dbgs() << " src = " << *Src << "\n"); 2177243789Sdim DEBUG(dbgs() << " dst = " << *Dst << "\n"); 2178243789Sdim Result.Consistent = false; 2179243789Sdim return gcdMIVtest(Src, Dst, Result) || 2180243789Sdim banerjeeMIVtest(Src, Dst, Loops, Result); 2181243789Sdim} 2182243789Sdim 2183243789Sdim 2184243789Sdim// Given a product, e.g., 10*X*Y, returns the first constant operand, 2185243789Sdim// in this case 10. If there is no constant part, returns NULL. 2186243789Sdimstatic 2187243789Sdimconst SCEVConstant *getConstantPart(const SCEVMulExpr *Product) { 2188243789Sdim for (unsigned Op = 0, Ops = Product->getNumOperands(); Op < Ops; Op++) { 2189243789Sdim if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Product->getOperand(Op))) 2190243789Sdim return Constant; 2191243789Sdim } 2192243789Sdim return NULL; 2193243789Sdim} 2194243789Sdim 2195243789Sdim 2196243789Sdim//===----------------------------------------------------------------------===// 2197243789Sdim// gcdMIVtest - 2198243789Sdim// Tests an MIV subscript pair for dependence. 2199243789Sdim// Returns true if any possible dependence is disproved. 2200243789Sdim// Marks the result as inconsistent. 2201243789Sdim// Can sometimes disprove the equal direction for 1 or more loops, 2202243789Sdim// as discussed in Michael Wolfe's book, 2203243789Sdim// High Performance Compilers for Parallel Computing, page 235. 2204243789Sdim// 2205243789Sdim// We spend some effort (code!) to handle cases like 2206243789Sdim// [10*i + 5*N*j + 15*M + 6], where i and j are induction variables, 2207243789Sdim// but M and N are just loop-invariant variables. 2208243789Sdim// This should help us handle linearized subscripts; 2209243789Sdim// also makes this test a useful backup to the various SIV tests. 2210243789Sdim// 2211243789Sdim// It occurs to me that the presence of loop-invariant variables 2212243789Sdim// changes the nature of the test from "greatest common divisor" 2213249423Sdim// to "a common divisor". 2214243789Sdimbool DependenceAnalysis::gcdMIVtest(const SCEV *Src, 2215243789Sdim const SCEV *Dst, 2216243789Sdim FullDependence &Result) const { 2217243789Sdim DEBUG(dbgs() << "starting gcd\n"); 2218243789Sdim ++GCDapplications; 2219249423Sdim unsigned BitWidth = SE->getTypeSizeInBits(Src->getType()); 2220243789Sdim APInt RunningGCD = APInt::getNullValue(BitWidth); 2221243789Sdim 2222243789Sdim // Examine Src coefficients. 2223243789Sdim // Compute running GCD and record source constant. 2224243789Sdim // Because we're looking for the constant at the end of the chain, 2225243789Sdim // we can't quit the loop just because the GCD == 1. 2226243789Sdim const SCEV *Coefficients = Src; 2227243789Sdim while (const SCEVAddRecExpr *AddRec = 2228243789Sdim dyn_cast<SCEVAddRecExpr>(Coefficients)) { 2229243789Sdim const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2230243789Sdim const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Coeff); 2231243789Sdim if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff)) 2232243789Sdim // If the coefficient is the product of a constant and other stuff, 2233243789Sdim // we can use the constant in the GCD computation. 2234243789Sdim Constant = getConstantPart(Product); 2235243789Sdim if (!Constant) 2236243789Sdim return false; 2237243789Sdim APInt ConstCoeff = Constant->getValue()->getValue(); 2238243789Sdim RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2239243789Sdim Coefficients = AddRec->getStart(); 2240243789Sdim } 2241243789Sdim const SCEV *SrcConst = Coefficients; 2242243789Sdim 2243243789Sdim // Examine Dst coefficients. 2244243789Sdim // Compute running GCD and record destination constant. 2245243789Sdim // Because we're looking for the constant at the end of the chain, 2246243789Sdim // we can't quit the loop just because the GCD == 1. 2247243789Sdim Coefficients = Dst; 2248243789Sdim while (const SCEVAddRecExpr *AddRec = 2249243789Sdim dyn_cast<SCEVAddRecExpr>(Coefficients)) { 2250243789Sdim const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2251243789Sdim const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Coeff); 2252243789Sdim if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff)) 2253243789Sdim // If the coefficient is the product of a constant and other stuff, 2254243789Sdim // we can use the constant in the GCD computation. 2255243789Sdim Constant = getConstantPart(Product); 2256243789Sdim if (!Constant) 2257243789Sdim return false; 2258243789Sdim APInt ConstCoeff = Constant->getValue()->getValue(); 2259243789Sdim RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2260243789Sdim Coefficients = AddRec->getStart(); 2261243789Sdim } 2262243789Sdim const SCEV *DstConst = Coefficients; 2263243789Sdim 2264243789Sdim APInt ExtraGCD = APInt::getNullValue(BitWidth); 2265243789Sdim const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 2266243789Sdim DEBUG(dbgs() << " Delta = " << *Delta << "\n"); 2267243789Sdim const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta); 2268243789Sdim if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) { 2269243789Sdim // If Delta is a sum of products, we may be able to make further progress. 2270243789Sdim for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) { 2271243789Sdim const SCEV *Operand = Sum->getOperand(Op); 2272243789Sdim if (isa<SCEVConstant>(Operand)) { 2273243789Sdim assert(!Constant && "Surprised to find multiple constants"); 2274243789Sdim Constant = cast<SCEVConstant>(Operand); 2275243789Sdim } 2276243789Sdim else if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) { 2277243789Sdim // Search for constant operand to participate in GCD; 2278243789Sdim // If none found; return false. 2279243789Sdim const SCEVConstant *ConstOp = getConstantPart(Product); 2280243789Sdim if (!ConstOp) 2281243789Sdim return false; 2282243789Sdim APInt ConstOpValue = ConstOp->getValue()->getValue(); 2283243789Sdim ExtraGCD = APIntOps::GreatestCommonDivisor(ExtraGCD, 2284243789Sdim ConstOpValue.abs()); 2285243789Sdim } 2286243789Sdim else 2287243789Sdim return false; 2288243789Sdim } 2289243789Sdim } 2290243789Sdim if (!Constant) 2291243789Sdim return false; 2292243789Sdim APInt ConstDelta = cast<SCEVConstant>(Constant)->getValue()->getValue(); 2293243789Sdim DEBUG(dbgs() << " ConstDelta = " << ConstDelta << "\n"); 2294243789Sdim if (ConstDelta == 0) 2295243789Sdim return false; 2296243789Sdim RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ExtraGCD); 2297243789Sdim DEBUG(dbgs() << " RunningGCD = " << RunningGCD << "\n"); 2298243789Sdim APInt Remainder = ConstDelta.srem(RunningGCD); 2299243789Sdim if (Remainder != 0) { 2300243789Sdim ++GCDindependence; 2301243789Sdim return true; 2302243789Sdim } 2303243789Sdim 2304243789Sdim // Try to disprove equal directions. 2305243789Sdim // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1], 2306243789Sdim // the code above can't disprove the dependence because the GCD = 1. 2307243789Sdim // So we consider what happen if i = i' and what happens if j = j'. 2308243789Sdim // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1], 2309243789Sdim // which is infeasible, so we can disallow the = direction for the i level. 2310243789Sdim // Setting j = j' doesn't help matters, so we end up with a direction vector 2311243789Sdim // of [<>, *] 2312243789Sdim // 2313243789Sdim // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5], 2314243789Sdim // we need to remember that the constant part is 5 and the RunningGCD should 2315243789Sdim // be initialized to ExtraGCD = 30. 2316243789Sdim DEBUG(dbgs() << " ExtraGCD = " << ExtraGCD << '\n'); 2317243789Sdim 2318243789Sdim bool Improved = false; 2319243789Sdim Coefficients = Src; 2320243789Sdim while (const SCEVAddRecExpr *AddRec = 2321243789Sdim dyn_cast<SCEVAddRecExpr>(Coefficients)) { 2322243789Sdim Coefficients = AddRec->getStart(); 2323243789Sdim const Loop *CurLoop = AddRec->getLoop(); 2324243789Sdim RunningGCD = ExtraGCD; 2325243789Sdim const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE); 2326243789Sdim const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff); 2327243789Sdim const SCEV *Inner = Src; 2328243789Sdim while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) { 2329243789Sdim AddRec = cast<SCEVAddRecExpr>(Inner); 2330243789Sdim const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2331243789Sdim if (CurLoop == AddRec->getLoop()) 2332243789Sdim ; // SrcCoeff == Coeff 2333243789Sdim else { 2334243789Sdim if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff)) 2335243789Sdim // If the coefficient is the product of a constant and other stuff, 2336243789Sdim // we can use the constant in the GCD computation. 2337243789Sdim Constant = getConstantPart(Product); 2338243789Sdim else 2339243789Sdim Constant = cast<SCEVConstant>(Coeff); 2340243789Sdim APInt ConstCoeff = Constant->getValue()->getValue(); 2341243789Sdim RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2342243789Sdim } 2343243789Sdim Inner = AddRec->getStart(); 2344243789Sdim } 2345243789Sdim Inner = Dst; 2346243789Sdim while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) { 2347243789Sdim AddRec = cast<SCEVAddRecExpr>(Inner); 2348243789Sdim const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2349243789Sdim if (CurLoop == AddRec->getLoop()) 2350243789Sdim DstCoeff = Coeff; 2351243789Sdim else { 2352243789Sdim if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff)) 2353243789Sdim // If the coefficient is the product of a constant and other stuff, 2354243789Sdim // we can use the constant in the GCD computation. 2355243789Sdim Constant = getConstantPart(Product); 2356243789Sdim else 2357243789Sdim Constant = cast<SCEVConstant>(Coeff); 2358243789Sdim APInt ConstCoeff = Constant->getValue()->getValue(); 2359243789Sdim RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2360243789Sdim } 2361243789Sdim Inner = AddRec->getStart(); 2362243789Sdim } 2363243789Sdim Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff); 2364243789Sdim if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Delta)) 2365243789Sdim // If the coefficient is the product of a constant and other stuff, 2366243789Sdim // we can use the constant in the GCD computation. 2367243789Sdim Constant = getConstantPart(Product); 2368243789Sdim else if (isa<SCEVConstant>(Delta)) 2369243789Sdim Constant = cast<SCEVConstant>(Delta); 2370243789Sdim else { 2371243789Sdim // The difference of the two coefficients might not be a product 2372243789Sdim // or constant, in which case we give up on this direction. 2373243789Sdim continue; 2374243789Sdim } 2375243789Sdim APInt ConstCoeff = Constant->getValue()->getValue(); 2376243789Sdim RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2377243789Sdim DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n"); 2378243789Sdim if (RunningGCD != 0) { 2379243789Sdim Remainder = ConstDelta.srem(RunningGCD); 2380243789Sdim DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n"); 2381243789Sdim if (Remainder != 0) { 2382243789Sdim unsigned Level = mapSrcLoop(CurLoop); 2383243789Sdim Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ); 2384243789Sdim Improved = true; 2385243789Sdim } 2386243789Sdim } 2387243789Sdim } 2388243789Sdim if (Improved) 2389243789Sdim ++GCDsuccesses; 2390243789Sdim DEBUG(dbgs() << "all done\n"); 2391243789Sdim return false; 2392243789Sdim} 2393243789Sdim 2394243789Sdim 2395243789Sdim//===----------------------------------------------------------------------===// 2396243789Sdim// banerjeeMIVtest - 2397243789Sdim// Use Banerjee's Inequalities to test an MIV subscript pair. 2398243789Sdim// (Wolfe, in the race-car book, calls this the Extreme Value Test.) 2399243789Sdim// Generally follows the discussion in Section 2.5.2 of 2400243789Sdim// 2401243789Sdim// Optimizing Supercompilers for Supercomputers 2402243789Sdim// Michael Wolfe 2403243789Sdim// 2404243789Sdim// The inequalities given on page 25 are simplified in that loops are 2405243789Sdim// normalized so that the lower bound is always 0 and the stride is always 1. 2406243789Sdim// For example, Wolfe gives 2407243789Sdim// 2408243789Sdim// LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k 2409243789Sdim// 2410243789Sdim// where A_k is the coefficient of the kth index in the source subscript, 2411243789Sdim// B_k is the coefficient of the kth index in the destination subscript, 2412243789Sdim// U_k is the upper bound of the kth index, L_k is the lower bound of the Kth 2413243789Sdim// index, and N_k is the stride of the kth index. Since all loops are normalized 2414243789Sdim// by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the 2415243789Sdim// equation to 2416243789Sdim// 2417243789Sdim// LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1 2418243789Sdim// = (A^-_k - B_k)^- (U_k - 1) - B_k 2419243789Sdim// 2420243789Sdim// Similar simplifications are possible for the other equations. 2421243789Sdim// 2422243789Sdim// When we can't determine the number of iterations for a loop, 2423243789Sdim// we use NULL as an indicator for the worst case, infinity. 2424243789Sdim// When computing the upper bound, NULL denotes +inf; 2425243789Sdim// for the lower bound, NULL denotes -inf. 2426243789Sdim// 2427243789Sdim// Return true if dependence disproved. 2428243789Sdimbool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src, 2429243789Sdim const SCEV *Dst, 2430243789Sdim const SmallBitVector &Loops, 2431243789Sdim FullDependence &Result) const { 2432243789Sdim DEBUG(dbgs() << "starting Banerjee\n"); 2433243789Sdim ++BanerjeeApplications; 2434243789Sdim DEBUG(dbgs() << " Src = " << *Src << '\n'); 2435243789Sdim const SCEV *A0; 2436243789Sdim CoefficientInfo *A = collectCoeffInfo(Src, true, A0); 2437243789Sdim DEBUG(dbgs() << " Dst = " << *Dst << '\n'); 2438243789Sdim const SCEV *B0; 2439243789Sdim CoefficientInfo *B = collectCoeffInfo(Dst, false, B0); 2440243789Sdim BoundInfo *Bound = new BoundInfo[MaxLevels + 1]; 2441243789Sdim const SCEV *Delta = SE->getMinusSCEV(B0, A0); 2442243789Sdim DEBUG(dbgs() << "\tDelta = " << *Delta << '\n'); 2443243789Sdim 2444243789Sdim // Compute bounds for all the * directions. 2445243789Sdim DEBUG(dbgs() << "\tBounds[*]\n"); 2446243789Sdim for (unsigned K = 1; K <= MaxLevels; ++K) { 2447243789Sdim Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations; 2448243789Sdim Bound[K].Direction = Dependence::DVEntry::ALL; 2449243789Sdim Bound[K].DirSet = Dependence::DVEntry::NONE; 2450243789Sdim findBoundsALL(A, B, Bound, K); 2451243789Sdim#ifndef NDEBUG 2452243789Sdim DEBUG(dbgs() << "\t " << K << '\t'); 2453243789Sdim if (Bound[K].Lower[Dependence::DVEntry::ALL]) 2454243789Sdim DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t'); 2455243789Sdim else 2456243789Sdim DEBUG(dbgs() << "-inf\t"); 2457243789Sdim if (Bound[K].Upper[Dependence::DVEntry::ALL]) 2458243789Sdim DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n'); 2459243789Sdim else 2460243789Sdim DEBUG(dbgs() << "+inf\n"); 2461243789Sdim#endif 2462243789Sdim } 2463243789Sdim 2464243789Sdim // Test the *, *, *, ... case. 2465243789Sdim bool Disproved = false; 2466243789Sdim if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) { 2467243789Sdim // Explore the direction vector hierarchy. 2468243789Sdim unsigned DepthExpanded = 0; 2469243789Sdim unsigned NewDeps = exploreDirections(1, A, B, Bound, 2470243789Sdim Loops, DepthExpanded, Delta); 2471243789Sdim if (NewDeps > 0) { 2472243789Sdim bool Improved = false; 2473243789Sdim for (unsigned K = 1; K <= CommonLevels; ++K) { 2474243789Sdim if (Loops[K]) { 2475243789Sdim unsigned Old = Result.DV[K - 1].Direction; 2476243789Sdim Result.DV[K - 1].Direction = Old & Bound[K].DirSet; 2477243789Sdim Improved |= Old != Result.DV[K - 1].Direction; 2478243789Sdim if (!Result.DV[K - 1].Direction) { 2479243789Sdim Improved = false; 2480243789Sdim Disproved = true; 2481243789Sdim break; 2482243789Sdim } 2483243789Sdim } 2484243789Sdim } 2485243789Sdim if (Improved) 2486243789Sdim ++BanerjeeSuccesses; 2487243789Sdim } 2488243789Sdim else { 2489243789Sdim ++BanerjeeIndependence; 2490243789Sdim Disproved = true; 2491243789Sdim } 2492243789Sdim } 2493243789Sdim else { 2494243789Sdim ++BanerjeeIndependence; 2495243789Sdim Disproved = true; 2496243789Sdim } 2497243789Sdim delete [] Bound; 2498243789Sdim delete [] A; 2499243789Sdim delete [] B; 2500243789Sdim return Disproved; 2501243789Sdim} 2502243789Sdim 2503243789Sdim 2504243789Sdim// Hierarchically expands the direction vector 2505243789Sdim// search space, combining the directions of discovered dependences 2506243789Sdim// in the DirSet field of Bound. Returns the number of distinct 2507243789Sdim// dependences discovered. If the dependence is disproved, 2508243789Sdim// it will return 0. 2509243789Sdimunsigned DependenceAnalysis::exploreDirections(unsigned Level, 2510243789Sdim CoefficientInfo *A, 2511243789Sdim CoefficientInfo *B, 2512243789Sdim BoundInfo *Bound, 2513243789Sdim const SmallBitVector &Loops, 2514243789Sdim unsigned &DepthExpanded, 2515243789Sdim const SCEV *Delta) const { 2516243789Sdim if (Level > CommonLevels) { 2517243789Sdim // record result 2518243789Sdim DEBUG(dbgs() << "\t["); 2519243789Sdim for (unsigned K = 1; K <= CommonLevels; ++K) { 2520243789Sdim if (Loops[K]) { 2521243789Sdim Bound[K].DirSet |= Bound[K].Direction; 2522243789Sdim#ifndef NDEBUG 2523243789Sdim switch (Bound[K].Direction) { 2524243789Sdim case Dependence::DVEntry::LT: 2525243789Sdim DEBUG(dbgs() << " <"); 2526243789Sdim break; 2527243789Sdim case Dependence::DVEntry::EQ: 2528243789Sdim DEBUG(dbgs() << " ="); 2529243789Sdim break; 2530243789Sdim case Dependence::DVEntry::GT: 2531243789Sdim DEBUG(dbgs() << " >"); 2532243789Sdim break; 2533243789Sdim case Dependence::DVEntry::ALL: 2534243789Sdim DEBUG(dbgs() << " *"); 2535243789Sdim break; 2536243789Sdim default: 2537243789Sdim llvm_unreachable("unexpected Bound[K].Direction"); 2538243789Sdim } 2539243789Sdim#endif 2540243789Sdim } 2541243789Sdim } 2542243789Sdim DEBUG(dbgs() << " ]\n"); 2543243789Sdim return 1; 2544243789Sdim } 2545243789Sdim if (Loops[Level]) { 2546243789Sdim if (Level > DepthExpanded) { 2547243789Sdim DepthExpanded = Level; 2548243789Sdim // compute bounds for <, =, > at current level 2549243789Sdim findBoundsLT(A, B, Bound, Level); 2550243789Sdim findBoundsGT(A, B, Bound, Level); 2551243789Sdim findBoundsEQ(A, B, Bound, Level); 2552243789Sdim#ifndef NDEBUG 2553243789Sdim DEBUG(dbgs() << "\tBound for level = " << Level << '\n'); 2554243789Sdim DEBUG(dbgs() << "\t <\t"); 2555243789Sdim if (Bound[Level].Lower[Dependence::DVEntry::LT]) 2556243789Sdim DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] << '\t'); 2557243789Sdim else 2558243789Sdim DEBUG(dbgs() << "-inf\t"); 2559243789Sdim if (Bound[Level].Upper[Dependence::DVEntry::LT]) 2560243789Sdim DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] << '\n'); 2561243789Sdim else 2562243789Sdim DEBUG(dbgs() << "+inf\n"); 2563243789Sdim DEBUG(dbgs() << "\t =\t"); 2564243789Sdim if (Bound[Level].Lower[Dependence::DVEntry::EQ]) 2565243789Sdim DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] << '\t'); 2566243789Sdim else 2567243789Sdim DEBUG(dbgs() << "-inf\t"); 2568243789Sdim if (Bound[Level].Upper[Dependence::DVEntry::EQ]) 2569243789Sdim DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] << '\n'); 2570243789Sdim else 2571243789Sdim DEBUG(dbgs() << "+inf\n"); 2572243789Sdim DEBUG(dbgs() << "\t >\t"); 2573243789Sdim if (Bound[Level].Lower[Dependence::DVEntry::GT]) 2574243789Sdim DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] << '\t'); 2575243789Sdim else 2576243789Sdim DEBUG(dbgs() << "-inf\t"); 2577243789Sdim if (Bound[Level].Upper[Dependence::DVEntry::GT]) 2578243789Sdim DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] << '\n'); 2579243789Sdim else 2580243789Sdim DEBUG(dbgs() << "+inf\n"); 2581243789Sdim#endif 2582243789Sdim } 2583243789Sdim 2584243789Sdim unsigned NewDeps = 0; 2585243789Sdim 2586243789Sdim // test bounds for <, *, *, ... 2587243789Sdim if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta)) 2588243789Sdim NewDeps += exploreDirections(Level + 1, A, B, Bound, 2589243789Sdim Loops, DepthExpanded, Delta); 2590243789Sdim 2591243789Sdim // Test bounds for =, *, *, ... 2592243789Sdim if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta)) 2593243789Sdim NewDeps += exploreDirections(Level + 1, A, B, Bound, 2594243789Sdim Loops, DepthExpanded, Delta); 2595243789Sdim 2596243789Sdim // test bounds for >, *, *, ... 2597243789Sdim if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta)) 2598243789Sdim NewDeps += exploreDirections(Level + 1, A, B, Bound, 2599243789Sdim Loops, DepthExpanded, Delta); 2600243789Sdim 2601243789Sdim Bound[Level].Direction = Dependence::DVEntry::ALL; 2602243789Sdim return NewDeps; 2603243789Sdim } 2604243789Sdim else 2605243789Sdim return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta); 2606243789Sdim} 2607243789Sdim 2608243789Sdim 2609243789Sdim// Returns true iff the current bounds are plausible. 2610243789Sdimbool DependenceAnalysis::testBounds(unsigned char DirKind, 2611243789Sdim unsigned Level, 2612243789Sdim BoundInfo *Bound, 2613243789Sdim const SCEV *Delta) const { 2614243789Sdim Bound[Level].Direction = DirKind; 2615243789Sdim if (const SCEV *LowerBound = getLowerBound(Bound)) 2616243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta)) 2617243789Sdim return false; 2618243789Sdim if (const SCEV *UpperBound = getUpperBound(Bound)) 2619243789Sdim if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound)) 2620243789Sdim return false; 2621243789Sdim return true; 2622243789Sdim} 2623243789Sdim 2624243789Sdim 2625243789Sdim// Computes the upper and lower bounds for level K 2626243789Sdim// using the * direction. Records them in Bound. 2627243789Sdim// Wolfe gives the equations 2628243789Sdim// 2629243789Sdim// LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k 2630243789Sdim// UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k 2631243789Sdim// 2632243789Sdim// Since we normalize loops, we can simplify these equations to 2633243789Sdim// 2634243789Sdim// LB^*_k = (A^-_k - B^+_k)U_k 2635243789Sdim// UB^*_k = (A^+_k - B^-_k)U_k 2636243789Sdim// 2637243789Sdim// We must be careful to handle the case where the upper bound is unknown. 2638243789Sdim// Note that the lower bound is always <= 0 2639243789Sdim// and the upper bound is always >= 0. 2640243789Sdimvoid DependenceAnalysis::findBoundsALL(CoefficientInfo *A, 2641243789Sdim CoefficientInfo *B, 2642243789Sdim BoundInfo *Bound, 2643243789Sdim unsigned K) const { 2644243789Sdim Bound[K].Lower[Dependence::DVEntry::ALL] = NULL; // Default value = -infinity. 2645243789Sdim Bound[K].Upper[Dependence::DVEntry::ALL] = NULL; // Default value = +infinity. 2646243789Sdim if (Bound[K].Iterations) { 2647243789Sdim Bound[K].Lower[Dependence::DVEntry::ALL] = 2648243789Sdim SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), 2649243789Sdim Bound[K].Iterations); 2650243789Sdim Bound[K].Upper[Dependence::DVEntry::ALL] = 2651243789Sdim SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), 2652243789Sdim Bound[K].Iterations); 2653243789Sdim } 2654243789Sdim else { 2655243789Sdim // If the difference is 0, we won't need to know the number of iterations. 2656243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart)) 2657243789Sdim Bound[K].Lower[Dependence::DVEntry::ALL] = 2658243789Sdim SE->getConstant(A[K].Coeff->getType(), 0); 2659243789Sdim if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart)) 2660243789Sdim Bound[K].Upper[Dependence::DVEntry::ALL] = 2661243789Sdim SE->getConstant(A[K].Coeff->getType(), 0); 2662243789Sdim } 2663243789Sdim} 2664243789Sdim 2665243789Sdim 2666243789Sdim// Computes the upper and lower bounds for level K 2667243789Sdim// using the = direction. Records them in Bound. 2668243789Sdim// Wolfe gives the equations 2669243789Sdim// 2670243789Sdim// LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k 2671243789Sdim// UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k 2672243789Sdim// 2673243789Sdim// Since we normalize loops, we can simplify these equations to 2674243789Sdim// 2675243789Sdim// LB^=_k = (A_k - B_k)^- U_k 2676243789Sdim// UB^=_k = (A_k - B_k)^+ U_k 2677243789Sdim// 2678243789Sdim// We must be careful to handle the case where the upper bound is unknown. 2679243789Sdim// Note that the lower bound is always <= 0 2680243789Sdim// and the upper bound is always >= 0. 2681243789Sdimvoid DependenceAnalysis::findBoundsEQ(CoefficientInfo *A, 2682243789Sdim CoefficientInfo *B, 2683243789Sdim BoundInfo *Bound, 2684243789Sdim unsigned K) const { 2685243789Sdim Bound[K].Lower[Dependence::DVEntry::EQ] = NULL; // Default value = -infinity. 2686243789Sdim Bound[K].Upper[Dependence::DVEntry::EQ] = NULL; // Default value = +infinity. 2687243789Sdim if (Bound[K].Iterations) { 2688243789Sdim const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); 2689243789Sdim const SCEV *NegativePart = getNegativePart(Delta); 2690243789Sdim Bound[K].Lower[Dependence::DVEntry::EQ] = 2691243789Sdim SE->getMulExpr(NegativePart, Bound[K].Iterations); 2692243789Sdim const SCEV *PositivePart = getPositivePart(Delta); 2693243789Sdim Bound[K].Upper[Dependence::DVEntry::EQ] = 2694243789Sdim SE->getMulExpr(PositivePart, Bound[K].Iterations); 2695243789Sdim } 2696243789Sdim else { 2697243789Sdim // If the positive/negative part of the difference is 0, 2698243789Sdim // we won't need to know the number of iterations. 2699243789Sdim const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); 2700243789Sdim const SCEV *NegativePart = getNegativePart(Delta); 2701243789Sdim if (NegativePart->isZero()) 2702243789Sdim Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero 2703243789Sdim const SCEV *PositivePart = getPositivePart(Delta); 2704243789Sdim if (PositivePart->isZero()) 2705243789Sdim Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero 2706243789Sdim } 2707243789Sdim} 2708243789Sdim 2709243789Sdim 2710243789Sdim// Computes the upper and lower bounds for level K 2711243789Sdim// using the < direction. Records them in Bound. 2712243789Sdim// Wolfe gives the equations 2713243789Sdim// 2714243789Sdim// LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k 2715243789Sdim// UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k 2716243789Sdim// 2717243789Sdim// Since we normalize loops, we can simplify these equations to 2718243789Sdim// 2719243789Sdim// LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k 2720243789Sdim// UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k 2721243789Sdim// 2722243789Sdim// We must be careful to handle the case where the upper bound is unknown. 2723243789Sdimvoid DependenceAnalysis::findBoundsLT(CoefficientInfo *A, 2724243789Sdim CoefficientInfo *B, 2725243789Sdim BoundInfo *Bound, 2726243789Sdim unsigned K) const { 2727243789Sdim Bound[K].Lower[Dependence::DVEntry::LT] = NULL; // Default value = -infinity. 2728243789Sdim Bound[K].Upper[Dependence::DVEntry::LT] = NULL; // Default value = +infinity. 2729243789Sdim if (Bound[K].Iterations) { 2730243789Sdim const SCEV *Iter_1 = 2731243789Sdim SE->getMinusSCEV(Bound[K].Iterations, 2732243789Sdim SE->getConstant(Bound[K].Iterations->getType(), 1)); 2733243789Sdim const SCEV *NegPart = 2734243789Sdim getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); 2735243789Sdim Bound[K].Lower[Dependence::DVEntry::LT] = 2736243789Sdim SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff); 2737243789Sdim const SCEV *PosPart = 2738243789Sdim getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); 2739243789Sdim Bound[K].Upper[Dependence::DVEntry::LT] = 2740243789Sdim SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff); 2741243789Sdim } 2742243789Sdim else { 2743243789Sdim // If the positive/negative part of the difference is 0, 2744243789Sdim // we won't need to know the number of iterations. 2745243789Sdim const SCEV *NegPart = 2746243789Sdim getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); 2747243789Sdim if (NegPart->isZero()) 2748243789Sdim Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); 2749243789Sdim const SCEV *PosPart = 2750243789Sdim getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); 2751243789Sdim if (PosPart->isZero()) 2752243789Sdim Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); 2753243789Sdim } 2754243789Sdim} 2755243789Sdim 2756243789Sdim 2757243789Sdim// Computes the upper and lower bounds for level K 2758243789Sdim// using the > direction. Records them in Bound. 2759243789Sdim// Wolfe gives the equations 2760243789Sdim// 2761243789Sdim// LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k 2762243789Sdim// UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k 2763243789Sdim// 2764243789Sdim// Since we normalize loops, we can simplify these equations to 2765243789Sdim// 2766243789Sdim// LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k 2767243789Sdim// UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k 2768243789Sdim// 2769243789Sdim// We must be careful to handle the case where the upper bound is unknown. 2770243789Sdimvoid DependenceAnalysis::findBoundsGT(CoefficientInfo *A, 2771243789Sdim CoefficientInfo *B, 2772243789Sdim BoundInfo *Bound, 2773243789Sdim unsigned K) const { 2774243789Sdim Bound[K].Lower[Dependence::DVEntry::GT] = NULL; // Default value = -infinity. 2775243789Sdim Bound[K].Upper[Dependence::DVEntry::GT] = NULL; // Default value = +infinity. 2776243789Sdim if (Bound[K].Iterations) { 2777243789Sdim const SCEV *Iter_1 = 2778243789Sdim SE->getMinusSCEV(Bound[K].Iterations, 2779243789Sdim SE->getConstant(Bound[K].Iterations->getType(), 1)); 2780243789Sdim const SCEV *NegPart = 2781243789Sdim getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); 2782243789Sdim Bound[K].Lower[Dependence::DVEntry::GT] = 2783243789Sdim SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff); 2784243789Sdim const SCEV *PosPart = 2785243789Sdim getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); 2786243789Sdim Bound[K].Upper[Dependence::DVEntry::GT] = 2787243789Sdim SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff); 2788243789Sdim } 2789243789Sdim else { 2790243789Sdim // If the positive/negative part of the difference is 0, 2791243789Sdim // we won't need to know the number of iterations. 2792243789Sdim const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); 2793243789Sdim if (NegPart->isZero()) 2794243789Sdim Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff; 2795243789Sdim const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); 2796243789Sdim if (PosPart->isZero()) 2797243789Sdim Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff; 2798243789Sdim } 2799243789Sdim} 2800243789Sdim 2801243789Sdim 2802243789Sdim// X^+ = max(X, 0) 2803243789Sdimconst SCEV *DependenceAnalysis::getPositivePart(const SCEV *X) const { 2804243789Sdim return SE->getSMaxExpr(X, SE->getConstant(X->getType(), 0)); 2805243789Sdim} 2806243789Sdim 2807243789Sdim 2808243789Sdim// X^- = min(X, 0) 2809243789Sdimconst SCEV *DependenceAnalysis::getNegativePart(const SCEV *X) const { 2810243789Sdim return SE->getSMinExpr(X, SE->getConstant(X->getType(), 0)); 2811243789Sdim} 2812243789Sdim 2813243789Sdim 2814243789Sdim// Walks through the subscript, 2815243789Sdim// collecting each coefficient, the associated loop bounds, 2816243789Sdim// and recording its positive and negative parts for later use. 2817243789SdimDependenceAnalysis::CoefficientInfo * 2818243789SdimDependenceAnalysis::collectCoeffInfo(const SCEV *Subscript, 2819243789Sdim bool SrcFlag, 2820243789Sdim const SCEV *&Constant) const { 2821243789Sdim const SCEV *Zero = SE->getConstant(Subscript->getType(), 0); 2822243789Sdim CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1]; 2823243789Sdim for (unsigned K = 1; K <= MaxLevels; ++K) { 2824243789Sdim CI[K].Coeff = Zero; 2825243789Sdim CI[K].PosPart = Zero; 2826243789Sdim CI[K].NegPart = Zero; 2827243789Sdim CI[K].Iterations = NULL; 2828243789Sdim } 2829243789Sdim while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) { 2830243789Sdim const Loop *L = AddRec->getLoop(); 2831243789Sdim unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L); 2832243789Sdim CI[K].Coeff = AddRec->getStepRecurrence(*SE); 2833243789Sdim CI[K].PosPart = getPositivePart(CI[K].Coeff); 2834243789Sdim CI[K].NegPart = getNegativePart(CI[K].Coeff); 2835243789Sdim CI[K].Iterations = collectUpperBound(L, Subscript->getType()); 2836243789Sdim Subscript = AddRec->getStart(); 2837243789Sdim } 2838243789Sdim Constant = Subscript; 2839243789Sdim#ifndef NDEBUG 2840243789Sdim DEBUG(dbgs() << "\tCoefficient Info\n"); 2841243789Sdim for (unsigned K = 1; K <= MaxLevels; ++K) { 2842243789Sdim DEBUG(dbgs() << "\t " << K << "\t" << *CI[K].Coeff); 2843243789Sdim DEBUG(dbgs() << "\tPos Part = "); 2844243789Sdim DEBUG(dbgs() << *CI[K].PosPart); 2845243789Sdim DEBUG(dbgs() << "\tNeg Part = "); 2846243789Sdim DEBUG(dbgs() << *CI[K].NegPart); 2847243789Sdim DEBUG(dbgs() << "\tUpper Bound = "); 2848243789Sdim if (CI[K].Iterations) 2849243789Sdim DEBUG(dbgs() << *CI[K].Iterations); 2850243789Sdim else 2851243789Sdim DEBUG(dbgs() << "+inf"); 2852243789Sdim DEBUG(dbgs() << '\n'); 2853243789Sdim } 2854243789Sdim DEBUG(dbgs() << "\t Constant = " << *Subscript << '\n'); 2855243789Sdim#endif 2856243789Sdim return CI; 2857243789Sdim} 2858243789Sdim 2859243789Sdim 2860243789Sdim// Looks through all the bounds info and 2861243789Sdim// computes the lower bound given the current direction settings 2862243789Sdim// at each level. If the lower bound for any level is -inf, 2863243789Sdim// the result is -inf. 2864243789Sdimconst SCEV *DependenceAnalysis::getLowerBound(BoundInfo *Bound) const { 2865243789Sdim const SCEV *Sum = Bound[1].Lower[Bound[1].Direction]; 2866243789Sdim for (unsigned K = 2; Sum && K <= MaxLevels; ++K) { 2867243789Sdim if (Bound[K].Lower[Bound[K].Direction]) 2868243789Sdim Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]); 2869243789Sdim else 2870243789Sdim Sum = NULL; 2871243789Sdim } 2872243789Sdim return Sum; 2873243789Sdim} 2874243789Sdim 2875243789Sdim 2876243789Sdim// Looks through all the bounds info and 2877243789Sdim// computes the upper bound given the current direction settings 2878243789Sdim// at each level. If the upper bound at any level is +inf, 2879243789Sdim// the result is +inf. 2880243789Sdimconst SCEV *DependenceAnalysis::getUpperBound(BoundInfo *Bound) const { 2881243789Sdim const SCEV *Sum = Bound[1].Upper[Bound[1].Direction]; 2882243789Sdim for (unsigned K = 2; Sum && K <= MaxLevels; ++K) { 2883243789Sdim if (Bound[K].Upper[Bound[K].Direction]) 2884243789Sdim Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]); 2885243789Sdim else 2886243789Sdim Sum = NULL; 2887243789Sdim } 2888243789Sdim return Sum; 2889243789Sdim} 2890243789Sdim 2891243789Sdim 2892243789Sdim//===----------------------------------------------------------------------===// 2893243789Sdim// Constraint manipulation for Delta test. 2894243789Sdim 2895243789Sdim// Given a linear SCEV, 2896243789Sdim// return the coefficient (the step) 2897243789Sdim// corresponding to the specified loop. 2898243789Sdim// If there isn't one, return 0. 2899243789Sdim// For example, given a*i + b*j + c*k, zeroing the coefficient 2900243789Sdim// corresponding to the j loop would yield b. 2901243789Sdimconst SCEV *DependenceAnalysis::findCoefficient(const SCEV *Expr, 2902243789Sdim const Loop *TargetLoop) const { 2903243789Sdim const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); 2904243789Sdim if (!AddRec) 2905243789Sdim return SE->getConstant(Expr->getType(), 0); 2906243789Sdim if (AddRec->getLoop() == TargetLoop) 2907243789Sdim return AddRec->getStepRecurrence(*SE); 2908243789Sdim return findCoefficient(AddRec->getStart(), TargetLoop); 2909243789Sdim} 2910243789Sdim 2911243789Sdim 2912243789Sdim// Given a linear SCEV, 2913243789Sdim// return the SCEV given by zeroing out the coefficient 2914243789Sdim// corresponding to the specified loop. 2915243789Sdim// For example, given a*i + b*j + c*k, zeroing the coefficient 2916243789Sdim// corresponding to the j loop would yield a*i + c*k. 2917243789Sdimconst SCEV *DependenceAnalysis::zeroCoefficient(const SCEV *Expr, 2918243789Sdim const Loop *TargetLoop) const { 2919243789Sdim const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); 2920243789Sdim if (!AddRec) 2921243789Sdim return Expr; // ignore 2922243789Sdim if (AddRec->getLoop() == TargetLoop) 2923243789Sdim return AddRec->getStart(); 2924243789Sdim return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop), 2925243789Sdim AddRec->getStepRecurrence(*SE), 2926243789Sdim AddRec->getLoop(), 2927243789Sdim AddRec->getNoWrapFlags()); 2928243789Sdim} 2929243789Sdim 2930243789Sdim 2931243789Sdim// Given a linear SCEV Expr, 2932243789Sdim// return the SCEV given by adding some Value to the 2933243789Sdim// coefficient corresponding to the specified TargetLoop. 2934243789Sdim// For example, given a*i + b*j + c*k, adding 1 to the coefficient 2935243789Sdim// corresponding to the j loop would yield a*i + (b+1)*j + c*k. 2936243789Sdimconst SCEV *DependenceAnalysis::addToCoefficient(const SCEV *Expr, 2937243789Sdim const Loop *TargetLoop, 2938243789Sdim const SCEV *Value) const { 2939243789Sdim const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); 2940243789Sdim if (!AddRec) // create a new addRec 2941243789Sdim return SE->getAddRecExpr(Expr, 2942243789Sdim Value, 2943243789Sdim TargetLoop, 2944243789Sdim SCEV::FlagAnyWrap); // Worst case, with no info. 2945243789Sdim if (AddRec->getLoop() == TargetLoop) { 2946243789Sdim const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value); 2947243789Sdim if (Sum->isZero()) 2948243789Sdim return AddRec->getStart(); 2949243789Sdim return SE->getAddRecExpr(AddRec->getStart(), 2950243789Sdim Sum, 2951243789Sdim AddRec->getLoop(), 2952243789Sdim AddRec->getNoWrapFlags()); 2953243789Sdim } 2954243789Sdim return SE->getAddRecExpr(addToCoefficient(AddRec->getStart(), 2955243789Sdim TargetLoop, Value), 2956243789Sdim AddRec->getStepRecurrence(*SE), 2957243789Sdim AddRec->getLoop(), 2958243789Sdim AddRec->getNoWrapFlags()); 2959243789Sdim} 2960243789Sdim 2961243789Sdim 2962243789Sdim// Review the constraints, looking for opportunities 2963243789Sdim// to simplify a subscript pair (Src and Dst). 2964243789Sdim// Return true if some simplification occurs. 2965243789Sdim// If the simplification isn't exact (that is, if it is conservative 2966243789Sdim// in terms of dependence), set consistent to false. 2967243789Sdim// Corresponds to Figure 5 from the paper 2968243789Sdim// 2969243789Sdim// Practical Dependence Testing 2970243789Sdim// Goff, Kennedy, Tseng 2971243789Sdim// PLDI 1991 2972243789Sdimbool DependenceAnalysis::propagate(const SCEV *&Src, 2973243789Sdim const SCEV *&Dst, 2974243789Sdim SmallBitVector &Loops, 2975243789Sdim SmallVector<Constraint, 4> &Constraints, 2976243789Sdim bool &Consistent) { 2977243789Sdim bool Result = false; 2978243789Sdim for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) { 2979243789Sdim DEBUG(dbgs() << "\t Constraint[" << LI << "] is"); 2980243789Sdim DEBUG(Constraints[LI].dump(dbgs())); 2981243789Sdim if (Constraints[LI].isDistance()) 2982243789Sdim Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent); 2983243789Sdim else if (Constraints[LI].isLine()) 2984243789Sdim Result |= propagateLine(Src, Dst, Constraints[LI], Consistent); 2985243789Sdim else if (Constraints[LI].isPoint()) 2986243789Sdim Result |= propagatePoint(Src, Dst, Constraints[LI]); 2987243789Sdim } 2988243789Sdim return Result; 2989243789Sdim} 2990243789Sdim 2991243789Sdim 2992243789Sdim// Attempt to propagate a distance 2993243789Sdim// constraint into a subscript pair (Src and Dst). 2994243789Sdim// Return true if some simplification occurs. 2995243789Sdim// If the simplification isn't exact (that is, if it is conservative 2996243789Sdim// in terms of dependence), set consistent to false. 2997243789Sdimbool DependenceAnalysis::propagateDistance(const SCEV *&Src, 2998243789Sdim const SCEV *&Dst, 2999243789Sdim Constraint &CurConstraint, 3000243789Sdim bool &Consistent) { 3001243789Sdim const Loop *CurLoop = CurConstraint.getAssociatedLoop(); 3002243789Sdim DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n"); 3003243789Sdim const SCEV *A_K = findCoefficient(Src, CurLoop); 3004243789Sdim if (A_K->isZero()) 3005243789Sdim return false; 3006243789Sdim const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD()); 3007243789Sdim Src = SE->getMinusSCEV(Src, DA_K); 3008243789Sdim Src = zeroCoefficient(Src, CurLoop); 3009243789Sdim DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n"); 3010243789Sdim DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n"); 3011243789Sdim Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K)); 3012243789Sdim DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n"); 3013243789Sdim if (!findCoefficient(Dst, CurLoop)->isZero()) 3014243789Sdim Consistent = false; 3015243789Sdim return true; 3016243789Sdim} 3017243789Sdim 3018243789Sdim 3019243789Sdim// Attempt to propagate a line 3020243789Sdim// constraint into a subscript pair (Src and Dst). 3021243789Sdim// Return true if some simplification occurs. 3022243789Sdim// If the simplification isn't exact (that is, if it is conservative 3023243789Sdim// in terms of dependence), set consistent to false. 3024243789Sdimbool DependenceAnalysis::propagateLine(const SCEV *&Src, 3025243789Sdim const SCEV *&Dst, 3026243789Sdim Constraint &CurConstraint, 3027243789Sdim bool &Consistent) { 3028243789Sdim const Loop *CurLoop = CurConstraint.getAssociatedLoop(); 3029243789Sdim const SCEV *A = CurConstraint.getA(); 3030243789Sdim const SCEV *B = CurConstraint.getB(); 3031243789Sdim const SCEV *C = CurConstraint.getC(); 3032243789Sdim DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C << "\n"); 3033243789Sdim DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n"); 3034243789Sdim DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n"); 3035243789Sdim if (A->isZero()) { 3036243789Sdim const SCEVConstant *Bconst = dyn_cast<SCEVConstant>(B); 3037243789Sdim const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C); 3038243789Sdim if (!Bconst || !Cconst) return false; 3039243789Sdim APInt Beta = Bconst->getValue()->getValue(); 3040243789Sdim APInt Charlie = Cconst->getValue()->getValue(); 3041243789Sdim APInt CdivB = Charlie.sdiv(Beta); 3042243789Sdim assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B"); 3043243789Sdim const SCEV *AP_K = findCoefficient(Dst, CurLoop); 3044243789Sdim // Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); 3045243789Sdim Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); 3046243789Sdim Dst = zeroCoefficient(Dst, CurLoop); 3047243789Sdim if (!findCoefficient(Src, CurLoop)->isZero()) 3048243789Sdim Consistent = false; 3049243789Sdim } 3050243789Sdim else if (B->isZero()) { 3051243789Sdim const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A); 3052243789Sdim const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C); 3053243789Sdim if (!Aconst || !Cconst) return false; 3054243789Sdim APInt Alpha = Aconst->getValue()->getValue(); 3055243789Sdim APInt Charlie = Cconst->getValue()->getValue(); 3056243789Sdim APInt CdivA = Charlie.sdiv(Alpha); 3057243789Sdim assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A"); 3058243789Sdim const SCEV *A_K = findCoefficient(Src, CurLoop); 3059243789Sdim Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); 3060243789Sdim Src = zeroCoefficient(Src, CurLoop); 3061243789Sdim if (!findCoefficient(Dst, CurLoop)->isZero()) 3062243789Sdim Consistent = false; 3063243789Sdim } 3064243789Sdim else if (isKnownPredicate(CmpInst::ICMP_EQ, A, B)) { 3065243789Sdim const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A); 3066243789Sdim const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C); 3067243789Sdim if (!Aconst || !Cconst) return false; 3068243789Sdim APInt Alpha = Aconst->getValue()->getValue(); 3069243789Sdim APInt Charlie = Cconst->getValue()->getValue(); 3070243789Sdim APInt CdivA = Charlie.sdiv(Alpha); 3071243789Sdim assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A"); 3072243789Sdim const SCEV *A_K = findCoefficient(Src, CurLoop); 3073243789Sdim Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); 3074243789Sdim Src = zeroCoefficient(Src, CurLoop); 3075243789Sdim Dst = addToCoefficient(Dst, CurLoop, A_K); 3076243789Sdim if (!findCoefficient(Dst, CurLoop)->isZero()) 3077243789Sdim Consistent = false; 3078243789Sdim } 3079243789Sdim else { 3080243789Sdim // paper is incorrect here, or perhaps just misleading 3081243789Sdim const SCEV *A_K = findCoefficient(Src, CurLoop); 3082243789Sdim Src = SE->getMulExpr(Src, A); 3083243789Sdim Dst = SE->getMulExpr(Dst, A); 3084243789Sdim Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C)); 3085243789Sdim Src = zeroCoefficient(Src, CurLoop); 3086243789Sdim Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B)); 3087243789Sdim if (!findCoefficient(Dst, CurLoop)->isZero()) 3088243789Sdim Consistent = false; 3089243789Sdim } 3090243789Sdim DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n"); 3091243789Sdim DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n"); 3092243789Sdim return true; 3093243789Sdim} 3094243789Sdim 3095243789Sdim 3096243789Sdim// Attempt to propagate a point 3097243789Sdim// constraint into a subscript pair (Src and Dst). 3098243789Sdim// Return true if some simplification occurs. 3099243789Sdimbool DependenceAnalysis::propagatePoint(const SCEV *&Src, 3100243789Sdim const SCEV *&Dst, 3101243789Sdim Constraint &CurConstraint) { 3102243789Sdim const Loop *CurLoop = CurConstraint.getAssociatedLoop(); 3103243789Sdim const SCEV *A_K = findCoefficient(Src, CurLoop); 3104243789Sdim const SCEV *AP_K = findCoefficient(Dst, CurLoop); 3105243789Sdim const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX()); 3106243789Sdim const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY()); 3107243789Sdim DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n"); 3108243789Sdim Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K)); 3109243789Sdim Src = zeroCoefficient(Src, CurLoop); 3110243789Sdim DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n"); 3111243789Sdim DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n"); 3112243789Sdim Dst = zeroCoefficient(Dst, CurLoop); 3113243789Sdim DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n"); 3114243789Sdim return true; 3115243789Sdim} 3116243789Sdim 3117243789Sdim 3118243789Sdim// Update direction vector entry based on the current constraint. 3119243789Sdimvoid DependenceAnalysis::updateDirection(Dependence::DVEntry &Level, 3120243789Sdim const Constraint &CurConstraint 3121243789Sdim ) const { 3122243789Sdim DEBUG(dbgs() << "\tUpdate direction, constraint ="); 3123243789Sdim DEBUG(CurConstraint.dump(dbgs())); 3124243789Sdim if (CurConstraint.isAny()) 3125243789Sdim ; // use defaults 3126243789Sdim else if (CurConstraint.isDistance()) { 3127243789Sdim // this one is consistent, the others aren't 3128243789Sdim Level.Scalar = false; 3129243789Sdim Level.Distance = CurConstraint.getD(); 3130243789Sdim unsigned NewDirection = Dependence::DVEntry::NONE; 3131243789Sdim if (!SE->isKnownNonZero(Level.Distance)) // if may be zero 3132243789Sdim NewDirection = Dependence::DVEntry::EQ; 3133243789Sdim if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive 3134243789Sdim NewDirection |= Dependence::DVEntry::LT; 3135243789Sdim if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative 3136243789Sdim NewDirection |= Dependence::DVEntry::GT; 3137243789Sdim Level.Direction &= NewDirection; 3138243789Sdim } 3139243789Sdim else if (CurConstraint.isLine()) { 3140243789Sdim Level.Scalar = false; 3141243789Sdim Level.Distance = NULL; 3142243789Sdim // direction should be accurate 3143243789Sdim } 3144243789Sdim else if (CurConstraint.isPoint()) { 3145243789Sdim Level.Scalar = false; 3146243789Sdim Level.Distance = NULL; 3147243789Sdim unsigned NewDirection = Dependence::DVEntry::NONE; 3148243789Sdim if (!isKnownPredicate(CmpInst::ICMP_NE, 3149243789Sdim CurConstraint.getY(), 3150243789Sdim CurConstraint.getX())) 3151243789Sdim // if X may be = Y 3152243789Sdim NewDirection |= Dependence::DVEntry::EQ; 3153243789Sdim if (!isKnownPredicate(CmpInst::ICMP_SLE, 3154243789Sdim CurConstraint.getY(), 3155243789Sdim CurConstraint.getX())) 3156243789Sdim // if Y may be > X 3157243789Sdim NewDirection |= Dependence::DVEntry::LT; 3158243789Sdim if (!isKnownPredicate(CmpInst::ICMP_SGE, 3159243789Sdim CurConstraint.getY(), 3160243789Sdim CurConstraint.getX())) 3161243789Sdim // if Y may be < X 3162243789Sdim NewDirection |= Dependence::DVEntry::GT; 3163243789Sdim Level.Direction &= NewDirection; 3164243789Sdim } 3165243789Sdim else 3166243789Sdim llvm_unreachable("constraint has unexpected kind"); 3167243789Sdim} 3168243789Sdim 3169243789Sdim 3170243789Sdim//===----------------------------------------------------------------------===// 3171243789Sdim 3172243789Sdim#ifndef NDEBUG 3173243789Sdim// For debugging purposes, dump a small bit vector to dbgs(). 3174243789Sdimstatic void dumpSmallBitVector(SmallBitVector &BV) { 3175243789Sdim dbgs() << "{"; 3176243789Sdim for (int VI = BV.find_first(); VI >= 0; VI = BV.find_next(VI)) { 3177243789Sdim dbgs() << VI; 3178243789Sdim if (BV.find_next(VI) >= 0) 3179243789Sdim dbgs() << ' '; 3180243789Sdim } 3181243789Sdim dbgs() << "}\n"; 3182243789Sdim} 3183243789Sdim#endif 3184243789Sdim 3185243789Sdim 3186243789Sdim// depends - 3187243789Sdim// Returns NULL if there is no dependence. 3188243789Sdim// Otherwise, return a Dependence with as many details as possible. 3189243789Sdim// Corresponds to Section 3.1 in the paper 3190243789Sdim// 3191243789Sdim// Practical Dependence Testing 3192243789Sdim// Goff, Kennedy, Tseng 3193243789Sdim// PLDI 1991 3194243789Sdim// 3195249423Sdim// Care is required to keep the routine below, getSplitIteration(), 3196249423Sdim// up to date with respect to this routine. 3197249423SdimDependence *DependenceAnalysis::depends(Instruction *Src, 3198249423Sdim Instruction *Dst, 3199243789Sdim bool PossiblyLoopIndependent) { 3200249423Sdim if (Src == Dst) 3201249423Sdim PossiblyLoopIndependent = false; 3202249423Sdim 3203243789Sdim if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) || 3204243789Sdim (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory())) 3205243789Sdim // if both instructions don't reference memory, there's no dependence 3206243789Sdim return NULL; 3207243789Sdim 3208249423Sdim if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) { 3209243789Sdim // can only analyze simple loads and stores, i.e., no calls, invokes, etc. 3210249423Sdim DEBUG(dbgs() << "can only handle simple loads and stores\n"); 3211243789Sdim return new Dependence(Src, Dst); 3212249423Sdim } 3213243789Sdim 3214249423Sdim Value *SrcPtr = getPointerOperand(Src); 3215249423Sdim Value *DstPtr = getPointerOperand(Dst); 3216243789Sdim 3217243789Sdim switch (underlyingObjectsAlias(AA, DstPtr, SrcPtr)) { 3218243789Sdim case AliasAnalysis::MayAlias: 3219243789Sdim case AliasAnalysis::PartialAlias: 3220243789Sdim // cannot analyse objects if we don't understand their aliasing. 3221249423Sdim DEBUG(dbgs() << "can't analyze may or partial alias\n"); 3222243789Sdim return new Dependence(Src, Dst); 3223243789Sdim case AliasAnalysis::NoAlias: 3224243789Sdim // If the objects noalias, they are distinct, accesses are independent. 3225249423Sdim DEBUG(dbgs() << "no alias\n"); 3226243789Sdim return NULL; 3227243789Sdim case AliasAnalysis::MustAlias: 3228243789Sdim break; // The underlying objects alias; test accesses for dependence. 3229243789Sdim } 3230243789Sdim 3231243789Sdim // establish loop nesting levels 3232243789Sdim establishNestingLevels(Src, Dst); 3233243789Sdim DEBUG(dbgs() << " common nesting levels = " << CommonLevels << "\n"); 3234243789Sdim DEBUG(dbgs() << " maximum nesting levels = " << MaxLevels << "\n"); 3235243789Sdim 3236243789Sdim FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels); 3237243789Sdim ++TotalArrayPairs; 3238243789Sdim 3239249423Sdim // See if there are GEPs we can use. 3240249423Sdim bool UsefulGEP = false; 3241249423Sdim GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr); 3242249423Sdim GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr); 3243249423Sdim if (SrcGEP && DstGEP && 3244249423Sdim SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) { 3245249423Sdim const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand()); 3246249423Sdim const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand()); 3247249423Sdim DEBUG(dbgs() << " SrcPtrSCEV = " << *SrcPtrSCEV << "\n"); 3248249423Sdim DEBUG(dbgs() << " DstPtrSCEV = " << *DstPtrSCEV << "\n"); 3249249423Sdim 3250249423Sdim UsefulGEP = 3251249423Sdim isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && 3252249423Sdim isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())); 3253249423Sdim } 3254249423Sdim unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1; 3255243789Sdim SmallVector<Subscript, 4> Pair(Pairs); 3256249423Sdim if (UsefulGEP) { 3257249423Sdim DEBUG(dbgs() << " using GEPs\n"); 3258249423Sdim unsigned P = 0; 3259249423Sdim for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(), 3260249423Sdim SrcEnd = SrcGEP->idx_end(), 3261249423Sdim DstIdx = DstGEP->idx_begin(); 3262249423Sdim SrcIdx != SrcEnd; 3263249423Sdim ++SrcIdx, ++DstIdx, ++P) { 3264249423Sdim Pair[P].Src = SE->getSCEV(*SrcIdx); 3265249423Sdim Pair[P].Dst = SE->getSCEV(*DstIdx); 3266249423Sdim } 3267243789Sdim } 3268249423Sdim else { 3269249423Sdim DEBUG(dbgs() << " ignoring GEPs\n"); 3270249423Sdim const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); 3271249423Sdim const SCEV *DstSCEV = SE->getSCEV(DstPtr); 3272249423Sdim DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n"); 3273249423Sdim DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n"); 3274249423Sdim Pair[0].Src = SrcSCEV; 3275249423Sdim Pair[0].Dst = DstSCEV; 3276249423Sdim } 3277249423Sdim 3278249423Sdim for (unsigned P = 0; P < Pairs; ++P) { 3279249423Sdim Pair[P].Loops.resize(MaxLevels + 1); 3280249423Sdim Pair[P].GroupLoops.resize(MaxLevels + 1); 3281249423Sdim Pair[P].Group.resize(Pairs); 3282249423Sdim removeMatchingExtensions(&Pair[P]); 3283249423Sdim Pair[P].Classification = 3284249423Sdim classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), 3285249423Sdim Pair[P].Dst, LI->getLoopFor(Dst->getParent()), 3286249423Sdim Pair[P].Loops); 3287249423Sdim Pair[P].GroupLoops = Pair[P].Loops; 3288249423Sdim Pair[P].Group.set(P); 3289249423Sdim DEBUG(dbgs() << " subscript " << P << "\n"); 3290249423Sdim DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n"); 3291249423Sdim DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n"); 3292249423Sdim DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n"); 3293243789Sdim DEBUG(dbgs() << "\tloops = "); 3294249423Sdim DEBUG(dumpSmallBitVector(Pair[P].Loops)); 3295243789Sdim } 3296243789Sdim 3297243789Sdim SmallBitVector Separable(Pairs); 3298243789Sdim SmallBitVector Coupled(Pairs); 3299243789Sdim 3300243789Sdim // Partition subscripts into separable and minimally-coupled groups 3301243789Sdim // Algorithm in paper is algorithmically better; 3302243789Sdim // this may be faster in practice. Check someday. 3303243789Sdim // 3304243789Sdim // Here's an example of how it works. Consider this code: 3305243789Sdim // 3306243789Sdim // for (i = ...) { 3307243789Sdim // for (j = ...) { 3308243789Sdim // for (k = ...) { 3309243789Sdim // for (l = ...) { 3310243789Sdim // for (m = ...) { 3311243789Sdim // A[i][j][k][m] = ...; 3312243789Sdim // ... = A[0][j][l][i + j]; 3313243789Sdim // } 3314243789Sdim // } 3315243789Sdim // } 3316243789Sdim // } 3317243789Sdim // } 3318243789Sdim // 3319243789Sdim // There are 4 subscripts here: 3320243789Sdim // 0 [i] and [0] 3321243789Sdim // 1 [j] and [j] 3322243789Sdim // 2 [k] and [l] 3323243789Sdim // 3 [m] and [i + j] 3324243789Sdim // 3325243789Sdim // We've already classified each subscript pair as ZIV, SIV, etc., 3326243789Sdim // and collected all the loops mentioned by pair P in Pair[P].Loops. 3327243789Sdim // In addition, we've initialized Pair[P].GroupLoops to Pair[P].Loops 3328243789Sdim // and set Pair[P].Group = {P}. 3329243789Sdim // 3330243789Sdim // Src Dst Classification Loops GroupLoops Group 3331243789Sdim // 0 [i] [0] SIV {1} {1} {0} 3332243789Sdim // 1 [j] [j] SIV {2} {2} {1} 3333243789Sdim // 2 [k] [l] RDIV {3,4} {3,4} {2} 3334243789Sdim // 3 [m] [i + j] MIV {1,2,5} {1,2,5} {3} 3335243789Sdim // 3336243789Sdim // For each subscript SI 0 .. 3, we consider each remaining subscript, SJ. 3337243789Sdim // So, 0 is compared against 1, 2, and 3; 1 is compared against 2 and 3, etc. 3338243789Sdim // 3339243789Sdim // We begin by comparing 0 and 1. The intersection of the GroupLoops is empty. 3340243789Sdim // Next, 0 and 2. Again, the intersection of their GroupLoops is empty. 3341243789Sdim // Next 0 and 3. The intersection of their GroupLoop = {1}, not empty, 3342243789Sdim // so Pair[3].Group = {0,3} and Done = false (that is, 0 will not be added 3343243789Sdim // to either Separable or Coupled). 3344243789Sdim // 3345243789Sdim // Next, we consider 1 and 2. The intersection of the GroupLoops is empty. 3346243789Sdim // Next, 1 and 3. The intersectionof their GroupLoops = {2}, not empty, 3347243789Sdim // so Pair[3].Group = {0, 1, 3} and Done = false. 3348243789Sdim // 3349243789Sdim // Next, we compare 2 against 3. The intersection of the GroupLoops is empty. 3350243789Sdim // Since Done remains true, we add 2 to the set of Separable pairs. 3351243789Sdim // 3352243789Sdim // Finally, we consider 3. There's nothing to compare it with, 3353243789Sdim // so Done remains true and we add it to the Coupled set. 3354243789Sdim // Pair[3].Group = {0, 1, 3} and GroupLoops = {1, 2, 5}. 3355243789Sdim // 3356243789Sdim // In the end, we've got 1 separable subscript and 1 coupled group. 3357243789Sdim for (unsigned SI = 0; SI < Pairs; ++SI) { 3358243789Sdim if (Pair[SI].Classification == Subscript::NonLinear) { 3359243789Sdim // ignore these, but collect loops for later 3360243789Sdim ++NonlinearSubscriptPairs; 3361243789Sdim collectCommonLoops(Pair[SI].Src, 3362243789Sdim LI->getLoopFor(Src->getParent()), 3363243789Sdim Pair[SI].Loops); 3364243789Sdim collectCommonLoops(Pair[SI].Dst, 3365243789Sdim LI->getLoopFor(Dst->getParent()), 3366243789Sdim Pair[SI].Loops); 3367243789Sdim Result.Consistent = false; 3368243789Sdim } 3369243789Sdim else if (Pair[SI].Classification == Subscript::ZIV) { 3370243789Sdim // always separable 3371243789Sdim Separable.set(SI); 3372243789Sdim } 3373243789Sdim else { 3374243789Sdim // SIV, RDIV, or MIV, so check for coupled group 3375243789Sdim bool Done = true; 3376243789Sdim for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) { 3377243789Sdim SmallBitVector Intersection = Pair[SI].GroupLoops; 3378243789Sdim Intersection &= Pair[SJ].GroupLoops; 3379243789Sdim if (Intersection.any()) { 3380243789Sdim // accumulate set of all the loops in group 3381243789Sdim Pair[SJ].GroupLoops |= Pair[SI].GroupLoops; 3382243789Sdim // accumulate set of all subscripts in group 3383243789Sdim Pair[SJ].Group |= Pair[SI].Group; 3384243789Sdim Done = false; 3385243789Sdim } 3386243789Sdim } 3387243789Sdim if (Done) { 3388243789Sdim if (Pair[SI].Group.count() == 1) { 3389243789Sdim Separable.set(SI); 3390243789Sdim ++SeparableSubscriptPairs; 3391243789Sdim } 3392243789Sdim else { 3393243789Sdim Coupled.set(SI); 3394243789Sdim ++CoupledSubscriptPairs; 3395243789Sdim } 3396243789Sdim } 3397243789Sdim } 3398243789Sdim } 3399243789Sdim 3400243789Sdim DEBUG(dbgs() << " Separable = "); 3401243789Sdim DEBUG(dumpSmallBitVector(Separable)); 3402243789Sdim DEBUG(dbgs() << " Coupled = "); 3403243789Sdim DEBUG(dumpSmallBitVector(Coupled)); 3404243789Sdim 3405243789Sdim Constraint NewConstraint; 3406243789Sdim NewConstraint.setAny(SE); 3407243789Sdim 3408243789Sdim // test separable subscripts 3409243789Sdim for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) { 3410243789Sdim DEBUG(dbgs() << "testing subscript " << SI); 3411243789Sdim switch (Pair[SI].Classification) { 3412243789Sdim case Subscript::ZIV: 3413243789Sdim DEBUG(dbgs() << ", ZIV\n"); 3414243789Sdim if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result)) 3415243789Sdim return NULL; 3416243789Sdim break; 3417243789Sdim case Subscript::SIV: { 3418243789Sdim DEBUG(dbgs() << ", SIV\n"); 3419243789Sdim unsigned Level; 3420243789Sdim const SCEV *SplitIter = NULL; 3421243789Sdim if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, 3422243789Sdim Result, NewConstraint, SplitIter)) 3423243789Sdim return NULL; 3424243789Sdim break; 3425243789Sdim } 3426243789Sdim case Subscript::RDIV: 3427243789Sdim DEBUG(dbgs() << ", RDIV\n"); 3428243789Sdim if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result)) 3429243789Sdim return NULL; 3430243789Sdim break; 3431243789Sdim case Subscript::MIV: 3432243789Sdim DEBUG(dbgs() << ", MIV\n"); 3433243789Sdim if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result)) 3434243789Sdim return NULL; 3435243789Sdim break; 3436243789Sdim default: 3437243789Sdim llvm_unreachable("subscript has unexpected classification"); 3438243789Sdim } 3439243789Sdim } 3440243789Sdim 3441243789Sdim if (Coupled.count()) { 3442243789Sdim // test coupled subscript groups 3443243789Sdim DEBUG(dbgs() << "starting on coupled subscripts\n"); 3444243789Sdim DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n"); 3445243789Sdim SmallVector<Constraint, 4> Constraints(MaxLevels + 1); 3446243789Sdim for (unsigned II = 0; II <= MaxLevels; ++II) 3447243789Sdim Constraints[II].setAny(SE); 3448243789Sdim for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) { 3449243789Sdim DEBUG(dbgs() << "testing subscript group " << SI << " { "); 3450243789Sdim SmallBitVector Group(Pair[SI].Group); 3451243789Sdim SmallBitVector Sivs(Pairs); 3452243789Sdim SmallBitVector Mivs(Pairs); 3453243789Sdim SmallBitVector ConstrainedLevels(MaxLevels + 1); 3454243789Sdim for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) { 3455243789Sdim DEBUG(dbgs() << SJ << " "); 3456243789Sdim if (Pair[SJ].Classification == Subscript::SIV) 3457243789Sdim Sivs.set(SJ); 3458243789Sdim else 3459243789Sdim Mivs.set(SJ); 3460243789Sdim } 3461243789Sdim DEBUG(dbgs() << "}\n"); 3462243789Sdim while (Sivs.any()) { 3463243789Sdim bool Changed = false; 3464243789Sdim for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) { 3465243789Sdim DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n"); 3466243789Sdim // SJ is an SIV subscript that's part of the current coupled group 3467243789Sdim unsigned Level; 3468243789Sdim const SCEV *SplitIter = NULL; 3469243789Sdim DEBUG(dbgs() << "SIV\n"); 3470243789Sdim if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, 3471243789Sdim Result, NewConstraint, SplitIter)) 3472243789Sdim return NULL; 3473243789Sdim ConstrainedLevels.set(Level); 3474243789Sdim if (intersectConstraints(&Constraints[Level], &NewConstraint)) { 3475243789Sdim if (Constraints[Level].isEmpty()) { 3476243789Sdim ++DeltaIndependence; 3477243789Sdim return NULL; 3478243789Sdim } 3479243789Sdim Changed = true; 3480243789Sdim } 3481243789Sdim Sivs.reset(SJ); 3482243789Sdim } 3483243789Sdim if (Changed) { 3484243789Sdim // propagate, possibly creating new SIVs and ZIVs 3485243789Sdim DEBUG(dbgs() << " propagating\n"); 3486243789Sdim DEBUG(dbgs() << "\tMivs = "); 3487243789Sdim DEBUG(dumpSmallBitVector(Mivs)); 3488243789Sdim for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { 3489243789Sdim // SJ is an MIV subscript that's part of the current coupled group 3490243789Sdim DEBUG(dbgs() << "\tSJ = " << SJ << "\n"); 3491243789Sdim if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, 3492243789Sdim Constraints, Result.Consistent)) { 3493243789Sdim DEBUG(dbgs() << "\t Changed\n"); 3494243789Sdim ++DeltaPropagations; 3495243789Sdim Pair[SJ].Classification = 3496243789Sdim classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), 3497243789Sdim Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), 3498243789Sdim Pair[SJ].Loops); 3499243789Sdim switch (Pair[SJ].Classification) { 3500243789Sdim case Subscript::ZIV: 3501243789Sdim DEBUG(dbgs() << "ZIV\n"); 3502243789Sdim if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) 3503243789Sdim return NULL; 3504243789Sdim Mivs.reset(SJ); 3505243789Sdim break; 3506243789Sdim case Subscript::SIV: 3507243789Sdim Sivs.set(SJ); 3508243789Sdim Mivs.reset(SJ); 3509243789Sdim break; 3510243789Sdim case Subscript::RDIV: 3511243789Sdim case Subscript::MIV: 3512243789Sdim break; 3513243789Sdim default: 3514243789Sdim llvm_unreachable("bad subscript classification"); 3515243789Sdim } 3516243789Sdim } 3517243789Sdim } 3518243789Sdim } 3519243789Sdim } 3520243789Sdim 3521243789Sdim // test & propagate remaining RDIVs 3522243789Sdim for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { 3523243789Sdim if (Pair[SJ].Classification == Subscript::RDIV) { 3524243789Sdim DEBUG(dbgs() << "RDIV test\n"); 3525243789Sdim if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) 3526243789Sdim return NULL; 3527243789Sdim // I don't yet understand how to propagate RDIV results 3528243789Sdim Mivs.reset(SJ); 3529243789Sdim } 3530243789Sdim } 3531243789Sdim 3532243789Sdim // test remaining MIVs 3533243789Sdim // This code is temporary. 3534243789Sdim // Better to somehow test all remaining subscripts simultaneously. 3535243789Sdim for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { 3536243789Sdim if (Pair[SJ].Classification == Subscript::MIV) { 3537243789Sdim DEBUG(dbgs() << "MIV test\n"); 3538243789Sdim if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result)) 3539243789Sdim return NULL; 3540243789Sdim } 3541243789Sdim else 3542243789Sdim llvm_unreachable("expected only MIV subscripts at this point"); 3543243789Sdim } 3544243789Sdim 3545243789Sdim // update Result.DV from constraint vector 3546243789Sdim DEBUG(dbgs() << " updating\n"); 3547243789Sdim for (int SJ = ConstrainedLevels.find_first(); 3548243789Sdim SJ >= 0; SJ = ConstrainedLevels.find_next(SJ)) { 3549243789Sdim updateDirection(Result.DV[SJ - 1], Constraints[SJ]); 3550243789Sdim if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) 3551243789Sdim return NULL; 3552243789Sdim } 3553243789Sdim } 3554243789Sdim } 3555243789Sdim 3556249423Sdim // Make sure the Scalar flags are set correctly. 3557243789Sdim SmallBitVector CompleteLoops(MaxLevels + 1); 3558243789Sdim for (unsigned SI = 0; SI < Pairs; ++SI) 3559243789Sdim CompleteLoops |= Pair[SI].Loops; 3560243789Sdim for (unsigned II = 1; II <= CommonLevels; ++II) 3561243789Sdim if (CompleteLoops[II]) 3562243789Sdim Result.DV[II - 1].Scalar = false; 3563243789Sdim 3564243789Sdim if (PossiblyLoopIndependent) { 3565249423Sdim // Make sure the LoopIndependent flag is set correctly. 3566249423Sdim // All directions must include equal, otherwise no 3567249423Sdim // loop-independent dependence is possible. 3568243789Sdim for (unsigned II = 1; II <= CommonLevels; ++II) { 3569243789Sdim if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) { 3570243789Sdim Result.LoopIndependent = false; 3571243789Sdim break; 3572243789Sdim } 3573243789Sdim } 3574243789Sdim } 3575249423Sdim else { 3576249423Sdim // On the other hand, if all directions are equal and there's no 3577249423Sdim // loop-independent dependence possible, then no dependence exists. 3578249423Sdim bool AllEqual = true; 3579249423Sdim for (unsigned II = 1; II <= CommonLevels; ++II) { 3580249423Sdim if (Result.getDirection(II) != Dependence::DVEntry::EQ) { 3581249423Sdim AllEqual = false; 3582249423Sdim break; 3583249423Sdim } 3584249423Sdim } 3585249423Sdim if (AllEqual) 3586249423Sdim return NULL; 3587249423Sdim } 3588243789Sdim 3589243789Sdim FullDependence *Final = new FullDependence(Result); 3590243789Sdim Result.DV = NULL; 3591243789Sdim return Final; 3592243789Sdim} 3593243789Sdim 3594243789Sdim 3595243789Sdim 3596243789Sdim//===----------------------------------------------------------------------===// 3597243789Sdim// getSplitIteration - 3598243789Sdim// Rather than spend rarely-used space recording the splitting iteration 3599243789Sdim// during the Weak-Crossing SIV test, we re-compute it on demand. 3600243789Sdim// The re-computation is basically a repeat of the entire dependence test, 3601243789Sdim// though simplified since we know that the dependence exists. 3602243789Sdim// It's tedious, since we must go through all propagations, etc. 3603243789Sdim// 3604249423Sdim// Care is required to keep this code up to date with respect to the routine 3605249423Sdim// above, depends(). 3606243789Sdim// 3607243789Sdim// Generally, the dependence analyzer will be used to build 3608243789Sdim// a dependence graph for a function (basically a map from instructions 3609243789Sdim// to dependences). Looking for cycles in the graph shows us loops 3610243789Sdim// that cannot be trivially vectorized/parallelized. 3611243789Sdim// 3612243789Sdim// We can try to improve the situation by examining all the dependences 3613243789Sdim// that make up the cycle, looking for ones we can break. 3614243789Sdim// Sometimes, peeling the first or last iteration of a loop will break 3615243789Sdim// dependences, and we've got flags for those possibilities. 3616243789Sdim// Sometimes, splitting a loop at some other iteration will do the trick, 3617243789Sdim// and we've got a flag for that case. Rather than waste the space to 3618243789Sdim// record the exact iteration (since we rarely know), we provide 3619243789Sdim// a method that calculates the iteration. It's a drag that it must work 3620243789Sdim// from scratch, but wonderful in that it's possible. 3621243789Sdim// 3622243789Sdim// Here's an example: 3623243789Sdim// 3624243789Sdim// for (i = 0; i < 10; i++) 3625243789Sdim// A[i] = ... 3626243789Sdim// ... = A[11 - i] 3627243789Sdim// 3628243789Sdim// There's a loop-carried flow dependence from the store to the load, 3629243789Sdim// found by the weak-crossing SIV test. The dependence will have a flag, 3630243789Sdim// indicating that the dependence can be broken by splitting the loop. 3631243789Sdim// Calling getSplitIteration will return 5. 3632243789Sdim// Splitting the loop breaks the dependence, like so: 3633243789Sdim// 3634243789Sdim// for (i = 0; i <= 5; i++) 3635243789Sdim// A[i] = ... 3636243789Sdim// ... = A[11 - i] 3637243789Sdim// for (i = 6; i < 10; i++) 3638243789Sdim// A[i] = ... 3639243789Sdim// ... = A[11 - i] 3640243789Sdim// 3641243789Sdim// breaks the dependence and allows us to vectorize/parallelize 3642243789Sdim// both loops. 3643243789Sdimconst SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, 3644243789Sdim unsigned SplitLevel) { 3645243789Sdim assert(Dep && "expected a pointer to a Dependence"); 3646243789Sdim assert(Dep->isSplitable(SplitLevel) && 3647243789Sdim "Dep should be splitable at SplitLevel"); 3648249423Sdim Instruction *Src = Dep->getSrc(); 3649249423Sdim Instruction *Dst = Dep->getDst(); 3650243789Sdim assert(Src->mayReadFromMemory() || Src->mayWriteToMemory()); 3651243789Sdim assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory()); 3652243789Sdim assert(isLoadOrStore(Src)); 3653243789Sdim assert(isLoadOrStore(Dst)); 3654249423Sdim Value *SrcPtr = getPointerOperand(Src); 3655249423Sdim Value *DstPtr = getPointerOperand(Dst); 3656243789Sdim assert(underlyingObjectsAlias(AA, DstPtr, SrcPtr) == 3657243789Sdim AliasAnalysis::MustAlias); 3658243789Sdim 3659243789Sdim // establish loop nesting levels 3660243789Sdim establishNestingLevels(Src, Dst); 3661243789Sdim 3662243789Sdim FullDependence Result(Src, Dst, false, CommonLevels); 3663243789Sdim 3664249423Sdim // See if there are GEPs we can use. 3665249423Sdim bool UsefulGEP = false; 3666249423Sdim GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr); 3667249423Sdim GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr); 3668249423Sdim if (SrcGEP && DstGEP && 3669249423Sdim SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) { 3670249423Sdim const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand()); 3671249423Sdim const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand()); 3672249423Sdim UsefulGEP = 3673249423Sdim isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && 3674249423Sdim isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())); 3675249423Sdim } 3676249423Sdim unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1; 3677243789Sdim SmallVector<Subscript, 4> Pair(Pairs); 3678249423Sdim if (UsefulGEP) { 3679249423Sdim unsigned P = 0; 3680249423Sdim for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(), 3681249423Sdim SrcEnd = SrcGEP->idx_end(), 3682249423Sdim DstIdx = DstGEP->idx_begin(); 3683249423Sdim SrcIdx != SrcEnd; 3684249423Sdim ++SrcIdx, ++DstIdx, ++P) { 3685249423Sdim Pair[P].Src = SE->getSCEV(*SrcIdx); 3686249423Sdim Pair[P].Dst = SE->getSCEV(*DstIdx); 3687249423Sdim } 3688243789Sdim } 3689249423Sdim else { 3690249423Sdim const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); 3691249423Sdim const SCEV *DstSCEV = SE->getSCEV(DstPtr); 3692249423Sdim Pair[0].Src = SrcSCEV; 3693249423Sdim Pair[0].Dst = DstSCEV; 3694243789Sdim } 3695243789Sdim 3696249423Sdim for (unsigned P = 0; P < Pairs; ++P) { 3697249423Sdim Pair[P].Loops.resize(MaxLevels + 1); 3698249423Sdim Pair[P].GroupLoops.resize(MaxLevels + 1); 3699249423Sdim Pair[P].Group.resize(Pairs); 3700249423Sdim removeMatchingExtensions(&Pair[P]); 3701249423Sdim Pair[P].Classification = 3702249423Sdim classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), 3703249423Sdim Pair[P].Dst, LI->getLoopFor(Dst->getParent()), 3704249423Sdim Pair[P].Loops); 3705249423Sdim Pair[P].GroupLoops = Pair[P].Loops; 3706249423Sdim Pair[P].Group.set(P); 3707249423Sdim } 3708249423Sdim 3709243789Sdim SmallBitVector Separable(Pairs); 3710243789Sdim SmallBitVector Coupled(Pairs); 3711243789Sdim 3712243789Sdim // partition subscripts into separable and minimally-coupled groups 3713243789Sdim for (unsigned SI = 0; SI < Pairs; ++SI) { 3714243789Sdim if (Pair[SI].Classification == Subscript::NonLinear) { 3715243789Sdim // ignore these, but collect loops for later 3716243789Sdim collectCommonLoops(Pair[SI].Src, 3717243789Sdim LI->getLoopFor(Src->getParent()), 3718243789Sdim Pair[SI].Loops); 3719243789Sdim collectCommonLoops(Pair[SI].Dst, 3720243789Sdim LI->getLoopFor(Dst->getParent()), 3721243789Sdim Pair[SI].Loops); 3722243789Sdim Result.Consistent = false; 3723243789Sdim } 3724243789Sdim else if (Pair[SI].Classification == Subscript::ZIV) 3725243789Sdim Separable.set(SI); 3726243789Sdim else { 3727243789Sdim // SIV, RDIV, or MIV, so check for coupled group 3728243789Sdim bool Done = true; 3729243789Sdim for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) { 3730243789Sdim SmallBitVector Intersection = Pair[SI].GroupLoops; 3731243789Sdim Intersection &= Pair[SJ].GroupLoops; 3732243789Sdim if (Intersection.any()) { 3733243789Sdim // accumulate set of all the loops in group 3734243789Sdim Pair[SJ].GroupLoops |= Pair[SI].GroupLoops; 3735243789Sdim // accumulate set of all subscripts in group 3736243789Sdim Pair[SJ].Group |= Pair[SI].Group; 3737243789Sdim Done = false; 3738243789Sdim } 3739243789Sdim } 3740243789Sdim if (Done) { 3741243789Sdim if (Pair[SI].Group.count() == 1) 3742243789Sdim Separable.set(SI); 3743243789Sdim else 3744243789Sdim Coupled.set(SI); 3745243789Sdim } 3746243789Sdim } 3747243789Sdim } 3748243789Sdim 3749243789Sdim Constraint NewConstraint; 3750243789Sdim NewConstraint.setAny(SE); 3751243789Sdim 3752243789Sdim // test separable subscripts 3753243789Sdim for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) { 3754243789Sdim switch (Pair[SI].Classification) { 3755243789Sdim case Subscript::SIV: { 3756243789Sdim unsigned Level; 3757243789Sdim const SCEV *SplitIter = NULL; 3758243789Sdim (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level, 3759243789Sdim Result, NewConstraint, SplitIter); 3760243789Sdim if (Level == SplitLevel) { 3761243789Sdim assert(SplitIter != NULL); 3762243789Sdim return SplitIter; 3763243789Sdim } 3764243789Sdim break; 3765243789Sdim } 3766243789Sdim case Subscript::ZIV: 3767243789Sdim case Subscript::RDIV: 3768243789Sdim case Subscript::MIV: 3769243789Sdim break; 3770243789Sdim default: 3771243789Sdim llvm_unreachable("subscript has unexpected classification"); 3772243789Sdim } 3773243789Sdim } 3774243789Sdim 3775243789Sdim if (Coupled.count()) { 3776243789Sdim // test coupled subscript groups 3777243789Sdim SmallVector<Constraint, 4> Constraints(MaxLevels + 1); 3778243789Sdim for (unsigned II = 0; II <= MaxLevels; ++II) 3779243789Sdim Constraints[II].setAny(SE); 3780243789Sdim for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) { 3781243789Sdim SmallBitVector Group(Pair[SI].Group); 3782243789Sdim SmallBitVector Sivs(Pairs); 3783243789Sdim SmallBitVector Mivs(Pairs); 3784243789Sdim SmallBitVector ConstrainedLevels(MaxLevels + 1); 3785243789Sdim for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) { 3786243789Sdim if (Pair[SJ].Classification == Subscript::SIV) 3787243789Sdim Sivs.set(SJ); 3788243789Sdim else 3789243789Sdim Mivs.set(SJ); 3790243789Sdim } 3791243789Sdim while (Sivs.any()) { 3792243789Sdim bool Changed = false; 3793243789Sdim for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) { 3794243789Sdim // SJ is an SIV subscript that's part of the current coupled group 3795243789Sdim unsigned Level; 3796243789Sdim const SCEV *SplitIter = NULL; 3797243789Sdim (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, 3798243789Sdim Result, NewConstraint, SplitIter); 3799243789Sdim if (Level == SplitLevel && SplitIter) 3800243789Sdim return SplitIter; 3801243789Sdim ConstrainedLevels.set(Level); 3802243789Sdim if (intersectConstraints(&Constraints[Level], &NewConstraint)) 3803243789Sdim Changed = true; 3804243789Sdim Sivs.reset(SJ); 3805243789Sdim } 3806243789Sdim if (Changed) { 3807243789Sdim // propagate, possibly creating new SIVs and ZIVs 3808243789Sdim for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { 3809243789Sdim // SJ is an MIV subscript that's part of the current coupled group 3810243789Sdim if (propagate(Pair[SJ].Src, Pair[SJ].Dst, 3811243789Sdim Pair[SJ].Loops, Constraints, Result.Consistent)) { 3812243789Sdim Pair[SJ].Classification = 3813243789Sdim classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), 3814243789Sdim Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), 3815243789Sdim Pair[SJ].Loops); 3816243789Sdim switch (Pair[SJ].Classification) { 3817243789Sdim case Subscript::ZIV: 3818243789Sdim Mivs.reset(SJ); 3819243789Sdim break; 3820243789Sdim case Subscript::SIV: 3821243789Sdim Sivs.set(SJ); 3822243789Sdim Mivs.reset(SJ); 3823243789Sdim break; 3824243789Sdim case Subscript::RDIV: 3825243789Sdim case Subscript::MIV: 3826243789Sdim break; 3827243789Sdim default: 3828243789Sdim llvm_unreachable("bad subscript classification"); 3829243789Sdim } 3830243789Sdim } 3831243789Sdim } 3832243789Sdim } 3833243789Sdim } 3834243789Sdim } 3835243789Sdim } 3836243789Sdim llvm_unreachable("somehow reached end of routine"); 3837243789Sdim return NULL; 3838243789Sdim} 3839