1 //===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // DependenceAnalysis is an LLVM pass that analyses dependences between memory 11 // accesses. Currently, it is an (incomplete) implementation of the approach 12 // described in 13 // 14 // Practical Dependence Testing 15 // Goff, Kennedy, Tseng 16 // PLDI 1991 17 // 18 // There's a single entry point that analyzes the dependence between a pair 19 // of memory references in a function, returning either NULL, for no dependence, 20 // or a more-or-less detailed description of the dependence between them. 21 // 22 // Currently, the implementation cannot propagate constraints between 23 // coupled RDIV subscripts and lacks a multi-subscript MIV test. 24 // Both of these are conservative weaknesses; 25 // that is, not a source of correctness problems. 26 // 27 // Since Clang linearizes some array subscripts, the dependence 28 // analysis is using SCEV->delinearize to recover the representation of multiple 29 // subscripts, and thus avoid the more expensive and less precise MIV tests. The 30 // delinearization is controlled by the flag -da-delinearize. 31 // 32 // We should pay some careful attention to the possibility of integer overflow 33 // in the implementation of the various tests. This could happen with Add, 34 // Subtract, or Multiply, with both APInt's and SCEV's. 35 // 36 // Some non-linear subscript pairs can be handled by the GCD test 37 // (and perhaps other tests). 38 // Should explore how often these things occur. 39 // 40 // Finally, it seems like certain test cases expose weaknesses in the SCEV 41 // simplification, especially in the handling of sign and zero extensions. 42 // It could be useful to spend time exploring these. 43 // 44 // Please note that this is work in progress and the interface is subject to 45 // change. 46 // 47 //===----------------------------------------------------------------------===// 48 // // 49 // In memory of Ken Kennedy, 1945 - 2007 // 50 // // 51 //===----------------------------------------------------------------------===// 52 53 #include "llvm/Analysis/DependenceAnalysis.h" 54 #include "llvm/ADT/STLExtras.h" 55 #include "llvm/ADT/Statistic.h" 56 #include "llvm/Analysis/AliasAnalysis.h" 57 #include "llvm/Analysis/LoopInfo.h" 58 #include "llvm/Analysis/ScalarEvolution.h" 59 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 60 #include "llvm/Analysis/ValueTracking.h" 61 #include "llvm/Config/llvm-config.h" 62 #include "llvm/IR/InstIterator.h" 63 #include "llvm/IR/Module.h" 64 #include "llvm/IR/Operator.h" 65 #include "llvm/Support/CommandLine.h" 66 #include "llvm/Support/Debug.h" 67 #include "llvm/Support/ErrorHandling.h" 68 #include "llvm/Support/raw_ostream.h" 69 70 using namespace llvm; 71 72 #define DEBUG_TYPE "da" 73 74 //===----------------------------------------------------------------------===// 75 // statistics 76 77 STATISTIC(TotalArrayPairs, "Array pairs tested"); 78 STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs"); 79 STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs"); 80 STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs"); 81 STATISTIC(ZIVapplications, "ZIV applications"); 82 STATISTIC(ZIVindependence, "ZIV independence"); 83 STATISTIC(StrongSIVapplications, "Strong SIV applications"); 84 STATISTIC(StrongSIVsuccesses, "Strong SIV successes"); 85 STATISTIC(StrongSIVindependence, "Strong SIV independence"); 86 STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications"); 87 STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes"); 88 STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence"); 89 STATISTIC(ExactSIVapplications, "Exact SIV applications"); 90 STATISTIC(ExactSIVsuccesses, "Exact SIV successes"); 91 STATISTIC(ExactSIVindependence, "Exact SIV independence"); 92 STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications"); 93 STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes"); 94 STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence"); 95 STATISTIC(ExactRDIVapplications, "Exact RDIV applications"); 96 STATISTIC(ExactRDIVindependence, "Exact RDIV independence"); 97 STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications"); 98 STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence"); 99 STATISTIC(DeltaApplications, "Delta applications"); 100 STATISTIC(DeltaSuccesses, "Delta successes"); 101 STATISTIC(DeltaIndependence, "Delta independence"); 102 STATISTIC(DeltaPropagations, "Delta propagations"); 103 STATISTIC(GCDapplications, "GCD applications"); 104 STATISTIC(GCDsuccesses, "GCD successes"); 105 STATISTIC(GCDindependence, "GCD independence"); 106 STATISTIC(BanerjeeApplications, "Banerjee applications"); 107 STATISTIC(BanerjeeIndependence, "Banerjee independence"); 108 STATISTIC(BanerjeeSuccesses, "Banerjee successes"); 109 110 static cl::opt<bool> 111 Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, 112 cl::desc("Try to delinearize array references.")); 113 114 //===----------------------------------------------------------------------===// 115 // basics 116 117 DependenceAnalysis::Result 118 DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { 119 auto &AA = FAM.getResult<AAManager>(F); 120 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F); 121 auto &LI = FAM.getResult<LoopAnalysis>(F); 122 return DependenceInfo(&F, &AA, &SE, &LI); 123 } 124 125 AnalysisKey DependenceAnalysis::Key; 126 127 INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da", 128 "Dependence Analysis", true, true) 129 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 130 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 131 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 132 INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", 133 true, true) 134 135 char DependenceAnalysisWrapperPass::ID = 0; 136 137 FunctionPass *llvm::createDependenceAnalysisWrapperPass() { 138 return new DependenceAnalysisWrapperPass(); 139 } 140 141 bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) { 142 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 143 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 144 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 145 info.reset(new DependenceInfo(&F, &AA, &SE, &LI)); 146 return false; 147 } 148 149 DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; } 150 151 void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); } 152 153 void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 154 AU.setPreservesAll(); 155 AU.addRequiredTransitive<AAResultsWrapperPass>(); 156 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>(); 157 AU.addRequiredTransitive<LoopInfoWrapperPass>(); 158 } 159 160 161 // Used to test the dependence analyzer. 162 // Looks through the function, noting loads and stores. 163 // Calls depends() on every possible pair and prints out the result. 164 // Ignores all other instructions. 165 static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) { 166 auto *F = DA->getFunction(); 167 for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE; 168 ++SrcI) { 169 if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) { 170 for (inst_iterator DstI = SrcI, DstE = inst_end(F); 171 DstI != DstE; ++DstI) { 172 if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) { 173 OS << "da analyze - "; 174 if (auto D = DA->depends(&*SrcI, &*DstI, true)) { 175 D->dump(OS); 176 for (unsigned Level = 1; Level <= D->getLevels(); Level++) { 177 if (D->isSplitable(Level)) { 178 OS << "da analyze - split level = " << Level; 179 OS << ", iteration = " << *DA->getSplitIteration(*D, Level); 180 OS << "!\n"; 181 } 182 } 183 } 184 else 185 OS << "none!\n"; 186 } 187 } 188 } 189 } 190 } 191 192 void DependenceAnalysisWrapperPass::print(raw_ostream &OS, 193 const Module *) const { 194 dumpExampleDependence(OS, info.get()); 195 } 196 197 //===----------------------------------------------------------------------===// 198 // Dependence methods 199 200 // Returns true if this is an input dependence. 201 bool Dependence::isInput() const { 202 return Src->mayReadFromMemory() && Dst->mayReadFromMemory(); 203 } 204 205 206 // Returns true if this is an output dependence. 207 bool Dependence::isOutput() const { 208 return Src->mayWriteToMemory() && Dst->mayWriteToMemory(); 209 } 210 211 212 // Returns true if this is an flow (aka true) dependence. 213 bool Dependence::isFlow() const { 214 return Src->mayWriteToMemory() && Dst->mayReadFromMemory(); 215 } 216 217 218 // Returns true if this is an anti dependence. 219 bool Dependence::isAnti() const { 220 return Src->mayReadFromMemory() && Dst->mayWriteToMemory(); 221 } 222 223 224 // Returns true if a particular level is scalar; that is, 225 // if no subscript in the source or destination mention the induction 226 // variable associated with the loop at this level. 227 // Leave this out of line, so it will serve as a virtual method anchor 228 bool Dependence::isScalar(unsigned level) const { 229 return false; 230 } 231 232 233 //===----------------------------------------------------------------------===// 234 // FullDependence methods 235 236 FullDependence::FullDependence(Instruction *Source, Instruction *Destination, 237 bool PossiblyLoopIndependent, 238 unsigned CommonLevels) 239 : Dependence(Source, Destination), Levels(CommonLevels), 240 LoopIndependent(PossiblyLoopIndependent) { 241 Consistent = true; 242 if (CommonLevels) 243 DV = make_unique<DVEntry[]>(CommonLevels); 244 } 245 246 // The rest are simple getters that hide the implementation. 247 248 // getDirection - Returns the direction associated with a particular level. 249 unsigned FullDependence::getDirection(unsigned Level) const { 250 assert(0 < Level && Level <= Levels && "Level out of range"); 251 return DV[Level - 1].Direction; 252 } 253 254 255 // Returns the distance (or NULL) associated with a particular level. 256 const SCEV *FullDependence::getDistance(unsigned Level) const { 257 assert(0 < Level && Level <= Levels && "Level out of range"); 258 return DV[Level - 1].Distance; 259 } 260 261 262 // Returns true if a particular level is scalar; that is, 263 // if no subscript in the source or destination mention the induction 264 // variable associated with the loop at this level. 265 bool FullDependence::isScalar(unsigned Level) const { 266 assert(0 < Level && Level <= Levels && "Level out of range"); 267 return DV[Level - 1].Scalar; 268 } 269 270 271 // Returns true if peeling the first iteration from this loop 272 // will break this dependence. 273 bool FullDependence::isPeelFirst(unsigned Level) const { 274 assert(0 < Level && Level <= Levels && "Level out of range"); 275 return DV[Level - 1].PeelFirst; 276 } 277 278 279 // Returns true if peeling the last iteration from this loop 280 // will break this dependence. 281 bool FullDependence::isPeelLast(unsigned Level) const { 282 assert(0 < Level && Level <= Levels && "Level out of range"); 283 return DV[Level - 1].PeelLast; 284 } 285 286 287 // Returns true if splitting this loop will break the dependence. 288 bool FullDependence::isSplitable(unsigned Level) const { 289 assert(0 < Level && Level <= Levels && "Level out of range"); 290 return DV[Level - 1].Splitable; 291 } 292 293 294 //===----------------------------------------------------------------------===// 295 // DependenceInfo::Constraint methods 296 297 // If constraint is a point <X, Y>, returns X. 298 // Otherwise assert. 299 const SCEV *DependenceInfo::Constraint::getX() const { 300 assert(Kind == Point && "Kind should be Point"); 301 return A; 302 } 303 304 305 // If constraint is a point <X, Y>, returns Y. 306 // Otherwise assert. 307 const SCEV *DependenceInfo::Constraint::getY() const { 308 assert(Kind == Point && "Kind should be Point"); 309 return B; 310 } 311 312 313 // If constraint is a line AX + BY = C, returns A. 314 // Otherwise assert. 315 const SCEV *DependenceInfo::Constraint::getA() const { 316 assert((Kind == Line || Kind == Distance) && 317 "Kind should be Line (or Distance)"); 318 return A; 319 } 320 321 322 // If constraint is a line AX + BY = C, returns B. 323 // Otherwise assert. 324 const SCEV *DependenceInfo::Constraint::getB() const { 325 assert((Kind == Line || Kind == Distance) && 326 "Kind should be Line (or Distance)"); 327 return B; 328 } 329 330 331 // If constraint is a line AX + BY = C, returns C. 332 // Otherwise assert. 333 const SCEV *DependenceInfo::Constraint::getC() const { 334 assert((Kind == Line || Kind == Distance) && 335 "Kind should be Line (or Distance)"); 336 return C; 337 } 338 339 340 // If constraint is a distance, returns D. 341 // Otherwise assert. 342 const SCEV *DependenceInfo::Constraint::getD() const { 343 assert(Kind == Distance && "Kind should be Distance"); 344 return SE->getNegativeSCEV(C); 345 } 346 347 348 // Returns the loop associated with this constraint. 349 const Loop *DependenceInfo::Constraint::getAssociatedLoop() const { 350 assert((Kind == Distance || Kind == Line || Kind == Point) && 351 "Kind should be Distance, Line, or Point"); 352 return AssociatedLoop; 353 } 354 355 void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y, 356 const Loop *CurLoop) { 357 Kind = Point; 358 A = X; 359 B = Y; 360 AssociatedLoop = CurLoop; 361 } 362 363 void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB, 364 const SCEV *CC, const Loop *CurLoop) { 365 Kind = Line; 366 A = AA; 367 B = BB; 368 C = CC; 369 AssociatedLoop = CurLoop; 370 } 371 372 void DependenceInfo::Constraint::setDistance(const SCEV *D, 373 const Loop *CurLoop) { 374 Kind = Distance; 375 A = SE->getOne(D->getType()); 376 B = SE->getNegativeSCEV(A); 377 C = SE->getNegativeSCEV(D); 378 AssociatedLoop = CurLoop; 379 } 380 381 void DependenceInfo::Constraint::setEmpty() { Kind = Empty; } 382 383 void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) { 384 SE = NewSE; 385 Kind = Any; 386 } 387 388 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 389 // For debugging purposes. Dumps the constraint out to OS. 390 LLVM_DUMP_METHOD void DependenceInfo::Constraint::dump(raw_ostream &OS) const { 391 if (isEmpty()) 392 OS << " Empty\n"; 393 else if (isAny()) 394 OS << " Any\n"; 395 else if (isPoint()) 396 OS << " Point is <" << *getX() << ", " << *getY() << ">\n"; 397 else if (isDistance()) 398 OS << " Distance is " << *getD() << 399 " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n"; 400 else if (isLine()) 401 OS << " Line is " << *getA() << "*X + " << 402 *getB() << "*Y = " << *getC() << "\n"; 403 else 404 llvm_unreachable("unknown constraint type in Constraint::dump"); 405 } 406 #endif 407 408 409 // Updates X with the intersection 410 // of the Constraints X and Y. Returns true if X has changed. 411 // Corresponds to Figure 4 from the paper 412 // 413 // Practical Dependence Testing 414 // Goff, Kennedy, Tseng 415 // PLDI 1991 416 bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) { 417 ++DeltaApplications; 418 LLVM_DEBUG(dbgs() << "\tintersect constraints\n"); 419 LLVM_DEBUG(dbgs() << "\t X ="; X->dump(dbgs())); 420 LLVM_DEBUG(dbgs() << "\t Y ="; Y->dump(dbgs())); 421 assert(!Y->isPoint() && "Y must not be a Point"); 422 if (X->isAny()) { 423 if (Y->isAny()) 424 return false; 425 *X = *Y; 426 return true; 427 } 428 if (X->isEmpty()) 429 return false; 430 if (Y->isEmpty()) { 431 X->setEmpty(); 432 return true; 433 } 434 435 if (X->isDistance() && Y->isDistance()) { 436 LLVM_DEBUG(dbgs() << "\t intersect 2 distances\n"); 437 if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD())) 438 return false; 439 if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) { 440 X->setEmpty(); 441 ++DeltaSuccesses; 442 return true; 443 } 444 // Hmmm, interesting situation. 445 // I guess if either is constant, keep it and ignore the other. 446 if (isa<SCEVConstant>(Y->getD())) { 447 *X = *Y; 448 return true; 449 } 450 return false; 451 } 452 453 // At this point, the pseudo-code in Figure 4 of the paper 454 // checks if (X->isPoint() && Y->isPoint()). 455 // This case can't occur in our implementation, 456 // since a Point can only arise as the result of intersecting 457 // two Line constraints, and the right-hand value, Y, is never 458 // the result of an intersection. 459 assert(!(X->isPoint() && Y->isPoint()) && 460 "We shouldn't ever see X->isPoint() && Y->isPoint()"); 461 462 if (X->isLine() && Y->isLine()) { 463 LLVM_DEBUG(dbgs() << "\t intersect 2 lines\n"); 464 const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB()); 465 const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA()); 466 if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) { 467 // slopes are equal, so lines are parallel 468 LLVM_DEBUG(dbgs() << "\t\tsame slope\n"); 469 Prod1 = SE->getMulExpr(X->getC(), Y->getB()); 470 Prod2 = SE->getMulExpr(X->getB(), Y->getC()); 471 if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) 472 return false; 473 if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) { 474 X->setEmpty(); 475 ++DeltaSuccesses; 476 return true; 477 } 478 return false; 479 } 480 if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) { 481 // slopes differ, so lines intersect 482 LLVM_DEBUG(dbgs() << "\t\tdifferent slopes\n"); 483 const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB()); 484 const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA()); 485 const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB()); 486 const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA()); 487 const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB()); 488 const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB()); 489 const SCEVConstant *C1A2_C2A1 = 490 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1)); 491 const SCEVConstant *C1B2_C2B1 = 492 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1)); 493 const SCEVConstant *A1B2_A2B1 = 494 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1)); 495 const SCEVConstant *A2B1_A1B2 = 496 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2)); 497 if (!C1B2_C2B1 || !C1A2_C2A1 || 498 !A1B2_A2B1 || !A2B1_A1B2) 499 return false; 500 APInt Xtop = C1B2_C2B1->getAPInt(); 501 APInt Xbot = A1B2_A2B1->getAPInt(); 502 APInt Ytop = C1A2_C2A1->getAPInt(); 503 APInt Ybot = A2B1_A1B2->getAPInt(); 504 LLVM_DEBUG(dbgs() << "\t\tXtop = " << Xtop << "\n"); 505 LLVM_DEBUG(dbgs() << "\t\tXbot = " << Xbot << "\n"); 506 LLVM_DEBUG(dbgs() << "\t\tYtop = " << Ytop << "\n"); 507 LLVM_DEBUG(dbgs() << "\t\tYbot = " << Ybot << "\n"); 508 APInt Xq = Xtop; // these need to be initialized, even 509 APInt Xr = Xtop; // though they're just going to be overwritten 510 APInt::sdivrem(Xtop, Xbot, Xq, Xr); 511 APInt Yq = Ytop; 512 APInt Yr = Ytop; 513 APInt::sdivrem(Ytop, Ybot, Yq, Yr); 514 if (Xr != 0 || Yr != 0) { 515 X->setEmpty(); 516 ++DeltaSuccesses; 517 return true; 518 } 519 LLVM_DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n"); 520 if (Xq.slt(0) || Yq.slt(0)) { 521 X->setEmpty(); 522 ++DeltaSuccesses; 523 return true; 524 } 525 if (const SCEVConstant *CUB = 526 collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) { 527 const APInt &UpperBound = CUB->getAPInt(); 528 LLVM_DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n"); 529 if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) { 530 X->setEmpty(); 531 ++DeltaSuccesses; 532 return true; 533 } 534 } 535 X->setPoint(SE->getConstant(Xq), 536 SE->getConstant(Yq), 537 X->getAssociatedLoop()); 538 ++DeltaSuccesses; 539 return true; 540 } 541 return false; 542 } 543 544 // if (X->isLine() && Y->isPoint()) This case can't occur. 545 assert(!(X->isLine() && Y->isPoint()) && "This case should never occur"); 546 547 if (X->isPoint() && Y->isLine()) { 548 LLVM_DEBUG(dbgs() << "\t intersect Point and Line\n"); 549 const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX()); 550 const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY()); 551 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1); 552 if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC())) 553 return false; 554 if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) { 555 X->setEmpty(); 556 ++DeltaSuccesses; 557 return true; 558 } 559 return false; 560 } 561 562 llvm_unreachable("shouldn't reach the end of Constraint intersection"); 563 return false; 564 } 565 566 567 //===----------------------------------------------------------------------===// 568 // DependenceInfo methods 569 570 // For debugging purposes. Dumps a dependence to OS. 571 void Dependence::dump(raw_ostream &OS) const { 572 bool Splitable = false; 573 if (isConfused()) 574 OS << "confused"; 575 else { 576 if (isConsistent()) 577 OS << "consistent "; 578 if (isFlow()) 579 OS << "flow"; 580 else if (isOutput()) 581 OS << "output"; 582 else if (isAnti()) 583 OS << "anti"; 584 else if (isInput()) 585 OS << "input"; 586 unsigned Levels = getLevels(); 587 OS << " ["; 588 for (unsigned II = 1; II <= Levels; ++II) { 589 if (isSplitable(II)) 590 Splitable = true; 591 if (isPeelFirst(II)) 592 OS << 'p'; 593 const SCEV *Distance = getDistance(II); 594 if (Distance) 595 OS << *Distance; 596 else if (isScalar(II)) 597 OS << "S"; 598 else { 599 unsigned Direction = getDirection(II); 600 if (Direction == DVEntry::ALL) 601 OS << "*"; 602 else { 603 if (Direction & DVEntry::LT) 604 OS << "<"; 605 if (Direction & DVEntry::EQ) 606 OS << "="; 607 if (Direction & DVEntry::GT) 608 OS << ">"; 609 } 610 } 611 if (isPeelLast(II)) 612 OS << 'p'; 613 if (II < Levels) 614 OS << " "; 615 } 616 if (isLoopIndependent()) 617 OS << "|<"; 618 OS << "]"; 619 if (Splitable) 620 OS << " splitable"; 621 } 622 OS << "!\n"; 623 } 624 625 // Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their 626 // underlaying objects. If LocA and LocB are known to not alias (for any reason: 627 // tbaa, non-overlapping regions etc), then it is known there is no dependecy. 628 // Otherwise the underlying objects are checked to see if they point to 629 // different identifiable objects. 630 static AliasResult underlyingObjectsAlias(AliasAnalysis *AA, 631 const DataLayout &DL, 632 const MemoryLocation &LocA, 633 const MemoryLocation &LocB) { 634 // Check the original locations (minus size) for noalias, which can happen for 635 // tbaa, incompatible underlying object locations, etc. 636 MemoryLocation LocAS(LocA.Ptr, MemoryLocation::UnknownSize, LocA.AATags); 637 MemoryLocation LocBS(LocB.Ptr, MemoryLocation::UnknownSize, LocB.AATags); 638 if (AA->alias(LocAS, LocBS) == NoAlias) 639 return NoAlias; 640 641 // Check the underlying objects are the same 642 const Value *AObj = GetUnderlyingObject(LocA.Ptr, DL); 643 const Value *BObj = GetUnderlyingObject(LocB.Ptr, DL); 644 645 // If the underlying objects are the same, they must alias 646 if (AObj == BObj) 647 return MustAlias; 648 649 // We may have hit the recursion limit for underlying objects, or have 650 // underlying objects where we don't know they will alias. 651 if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj)) 652 return MayAlias; 653 654 // Otherwise we know the objects are different and both identified objects so 655 // must not alias. 656 return NoAlias; 657 } 658 659 660 // Returns true if the load or store can be analyzed. Atomic and volatile 661 // operations have properties which this analysis does not understand. 662 static 663 bool isLoadOrStore(const Instruction *I) { 664 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 665 return LI->isUnordered(); 666 else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) 667 return SI->isUnordered(); 668 return false; 669 } 670 671 672 // Examines the loop nesting of the Src and Dst 673 // instructions and establishes their shared loops. Sets the variables 674 // CommonLevels, SrcLevels, and MaxLevels. 675 // The source and destination instructions needn't be contained in the same 676 // loop. The routine establishNestingLevels finds the level of most deeply 677 // nested loop that contains them both, CommonLevels. An instruction that's 678 // not contained in a loop is at level = 0. MaxLevels is equal to the level 679 // of the source plus the level of the destination, minus CommonLevels. 680 // This lets us allocate vectors MaxLevels in length, with room for every 681 // distinct loop referenced in both the source and destination subscripts. 682 // The variable SrcLevels is the nesting depth of the source instruction. 683 // It's used to help calculate distinct loops referenced by the destination. 684 // Here's the map from loops to levels: 685 // 0 - unused 686 // 1 - outermost common loop 687 // ... - other common loops 688 // CommonLevels - innermost common loop 689 // ... - loops containing Src but not Dst 690 // SrcLevels - innermost loop containing Src but not Dst 691 // ... - loops containing Dst but not Src 692 // MaxLevels - innermost loops containing Dst but not Src 693 // Consider the follow code fragment: 694 // for (a = ...) { 695 // for (b = ...) { 696 // for (c = ...) { 697 // for (d = ...) { 698 // A[] = ...; 699 // } 700 // } 701 // for (e = ...) { 702 // for (f = ...) { 703 // for (g = ...) { 704 // ... = A[]; 705 // } 706 // } 707 // } 708 // } 709 // } 710 // If we're looking at the possibility of a dependence between the store 711 // to A (the Src) and the load from A (the Dst), we'll note that they 712 // have 2 loops in common, so CommonLevels will equal 2 and the direction 713 // vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. 714 // A map from loop names to loop numbers would look like 715 // a - 1 716 // b - 2 = CommonLevels 717 // c - 3 718 // d - 4 = SrcLevels 719 // e - 5 720 // f - 6 721 // g - 7 = MaxLevels 722 void DependenceInfo::establishNestingLevels(const Instruction *Src, 723 const Instruction *Dst) { 724 const BasicBlock *SrcBlock = Src->getParent(); 725 const BasicBlock *DstBlock = Dst->getParent(); 726 unsigned SrcLevel = LI->getLoopDepth(SrcBlock); 727 unsigned DstLevel = LI->getLoopDepth(DstBlock); 728 const Loop *SrcLoop = LI->getLoopFor(SrcBlock); 729 const Loop *DstLoop = LI->getLoopFor(DstBlock); 730 SrcLevels = SrcLevel; 731 MaxLevels = SrcLevel + DstLevel; 732 while (SrcLevel > DstLevel) { 733 SrcLoop = SrcLoop->getParentLoop(); 734 SrcLevel--; 735 } 736 while (DstLevel > SrcLevel) { 737 DstLoop = DstLoop->getParentLoop(); 738 DstLevel--; 739 } 740 while (SrcLoop != DstLoop) { 741 SrcLoop = SrcLoop->getParentLoop(); 742 DstLoop = DstLoop->getParentLoop(); 743 SrcLevel--; 744 } 745 CommonLevels = SrcLevel; 746 MaxLevels -= CommonLevels; 747 } 748 749 750 // Given one of the loops containing the source, return 751 // its level index in our numbering scheme. 752 unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const { 753 return SrcLoop->getLoopDepth(); 754 } 755 756 757 // Given one of the loops containing the destination, 758 // return its level index in our numbering scheme. 759 unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const { 760 unsigned D = DstLoop->getLoopDepth(); 761 if (D > CommonLevels) 762 return D - CommonLevels + SrcLevels; 763 else 764 return D; 765 } 766 767 768 // Returns true if Expression is loop invariant in LoopNest. 769 bool DependenceInfo::isLoopInvariant(const SCEV *Expression, 770 const Loop *LoopNest) const { 771 if (!LoopNest) 772 return true; 773 return SE->isLoopInvariant(Expression, LoopNest) && 774 isLoopInvariant(Expression, LoopNest->getParentLoop()); 775 } 776 777 778 779 // Finds the set of loops from the LoopNest that 780 // have a level <= CommonLevels and are referred to by the SCEV Expression. 781 void DependenceInfo::collectCommonLoops(const SCEV *Expression, 782 const Loop *LoopNest, 783 SmallBitVector &Loops) const { 784 while (LoopNest) { 785 unsigned Level = LoopNest->getLoopDepth(); 786 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest)) 787 Loops.set(Level); 788 LoopNest = LoopNest->getParentLoop(); 789 } 790 } 791 792 void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) { 793 794 unsigned widestWidthSeen = 0; 795 Type *widestType; 796 797 // Go through each pair and find the widest bit to which we need 798 // to extend all of them. 799 for (Subscript *Pair : Pairs) { 800 const SCEV *Src = Pair->Src; 801 const SCEV *Dst = Pair->Dst; 802 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType()); 803 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType()); 804 if (SrcTy == nullptr || DstTy == nullptr) { 805 assert(SrcTy == DstTy && "This function only unify integer types and " 806 "expect Src and Dst share the same type " 807 "otherwise."); 808 continue; 809 } 810 if (SrcTy->getBitWidth() > widestWidthSeen) { 811 widestWidthSeen = SrcTy->getBitWidth(); 812 widestType = SrcTy; 813 } 814 if (DstTy->getBitWidth() > widestWidthSeen) { 815 widestWidthSeen = DstTy->getBitWidth(); 816 widestType = DstTy; 817 } 818 } 819 820 821 assert(widestWidthSeen > 0); 822 823 // Now extend each pair to the widest seen. 824 for (Subscript *Pair : Pairs) { 825 const SCEV *Src = Pair->Src; 826 const SCEV *Dst = Pair->Dst; 827 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType()); 828 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType()); 829 if (SrcTy == nullptr || DstTy == nullptr) { 830 assert(SrcTy == DstTy && "This function only unify integer types and " 831 "expect Src and Dst share the same type " 832 "otherwise."); 833 continue; 834 } 835 if (SrcTy->getBitWidth() < widestWidthSeen) 836 // Sign-extend Src to widestType 837 Pair->Src = SE->getSignExtendExpr(Src, widestType); 838 if (DstTy->getBitWidth() < widestWidthSeen) { 839 // Sign-extend Dst to widestType 840 Pair->Dst = SE->getSignExtendExpr(Dst, widestType); 841 } 842 } 843 } 844 845 // removeMatchingExtensions - Examines a subscript pair. 846 // If the source and destination are identically sign (or zero) 847 // extended, it strips off the extension in an effect to simplify 848 // the actual analysis. 849 void DependenceInfo::removeMatchingExtensions(Subscript *Pair) { 850 const SCEV *Src = Pair->Src; 851 const SCEV *Dst = Pair->Dst; 852 if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) || 853 (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) { 854 const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src); 855 const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst); 856 const SCEV *SrcCastOp = SrcCast->getOperand(); 857 const SCEV *DstCastOp = DstCast->getOperand(); 858 if (SrcCastOp->getType() == DstCastOp->getType()) { 859 Pair->Src = SrcCastOp; 860 Pair->Dst = DstCastOp; 861 } 862 } 863 } 864 865 866 // Examine the scev and return true iff it's linear. 867 // Collect any loops mentioned in the set of "Loops". 868 bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, 869 SmallBitVector &Loops) { 870 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src); 871 if (!AddRec) 872 return isLoopInvariant(Src, LoopNest); 873 const SCEV *Start = AddRec->getStart(); 874 const SCEV *Step = AddRec->getStepRecurrence(*SE); 875 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); 876 if (!isa<SCEVCouldNotCompute>(UB)) { 877 if (SE->getTypeSizeInBits(Start->getType()) < 878 SE->getTypeSizeInBits(UB->getType())) { 879 if (!AddRec->getNoWrapFlags()) 880 return false; 881 } 882 } 883 if (!isLoopInvariant(Step, LoopNest)) 884 return false; 885 Loops.set(mapSrcLoop(AddRec->getLoop())); 886 return checkSrcSubscript(Start, LoopNest, Loops); 887 } 888 889 890 891 // Examine the scev and return true iff it's linear. 892 // Collect any loops mentioned in the set of "Loops". 893 bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest, 894 SmallBitVector &Loops) { 895 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst); 896 if (!AddRec) 897 return isLoopInvariant(Dst, LoopNest); 898 const SCEV *Start = AddRec->getStart(); 899 const SCEV *Step = AddRec->getStepRecurrence(*SE); 900 const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); 901 if (!isa<SCEVCouldNotCompute>(UB)) { 902 if (SE->getTypeSizeInBits(Start->getType()) < 903 SE->getTypeSizeInBits(UB->getType())) { 904 if (!AddRec->getNoWrapFlags()) 905 return false; 906 } 907 } 908 if (!isLoopInvariant(Step, LoopNest)) 909 return false; 910 Loops.set(mapDstLoop(AddRec->getLoop())); 911 return checkDstSubscript(Start, LoopNest, Loops); 912 } 913 914 915 // Examines the subscript pair (the Src and Dst SCEVs) 916 // and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. 917 // Collects the associated loops in a set. 918 DependenceInfo::Subscript::ClassificationKind 919 DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, 920 const SCEV *Dst, const Loop *DstLoopNest, 921 SmallBitVector &Loops) { 922 SmallBitVector SrcLoops(MaxLevels + 1); 923 SmallBitVector DstLoops(MaxLevels + 1); 924 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops)) 925 return Subscript::NonLinear; 926 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops)) 927 return Subscript::NonLinear; 928 Loops = SrcLoops; 929 Loops |= DstLoops; 930 unsigned N = Loops.count(); 931 if (N == 0) 932 return Subscript::ZIV; 933 if (N == 1) 934 return Subscript::SIV; 935 if (N == 2 && (SrcLoops.count() == 0 || 936 DstLoops.count() == 0 || 937 (SrcLoops.count() == 1 && DstLoops.count() == 1))) 938 return Subscript::RDIV; 939 return Subscript::MIV; 940 } 941 942 943 // A wrapper around SCEV::isKnownPredicate. 944 // Looks for cases where we're interested in comparing for equality. 945 // If both X and Y have been identically sign or zero extended, 946 // it strips off the (confusing) extensions before invoking 947 // SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package 948 // will be similarly updated. 949 // 950 // If SCEV::isKnownPredicate can't prove the predicate, 951 // we try simple subtraction, which seems to help in some cases 952 // involving symbolics. 953 bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X, 954 const SCEV *Y) const { 955 if (Pred == CmpInst::ICMP_EQ || 956 Pred == CmpInst::ICMP_NE) { 957 if ((isa<SCEVSignExtendExpr>(X) && 958 isa<SCEVSignExtendExpr>(Y)) || 959 (isa<SCEVZeroExtendExpr>(X) && 960 isa<SCEVZeroExtendExpr>(Y))) { 961 const SCEVCastExpr *CX = cast<SCEVCastExpr>(X); 962 const SCEVCastExpr *CY = cast<SCEVCastExpr>(Y); 963 const SCEV *Xop = CX->getOperand(); 964 const SCEV *Yop = CY->getOperand(); 965 if (Xop->getType() == Yop->getType()) { 966 X = Xop; 967 Y = Yop; 968 } 969 } 970 } 971 if (SE->isKnownPredicate(Pred, X, Y)) 972 return true; 973 // If SE->isKnownPredicate can't prove the condition, 974 // we try the brute-force approach of subtracting 975 // and testing the difference. 976 // By testing with SE->isKnownPredicate first, we avoid 977 // the possibility of overflow when the arguments are constants. 978 const SCEV *Delta = SE->getMinusSCEV(X, Y); 979 switch (Pred) { 980 case CmpInst::ICMP_EQ: 981 return Delta->isZero(); 982 case CmpInst::ICMP_NE: 983 return SE->isKnownNonZero(Delta); 984 case CmpInst::ICMP_SGE: 985 return SE->isKnownNonNegative(Delta); 986 case CmpInst::ICMP_SLE: 987 return SE->isKnownNonPositive(Delta); 988 case CmpInst::ICMP_SGT: 989 return SE->isKnownPositive(Delta); 990 case CmpInst::ICMP_SLT: 991 return SE->isKnownNegative(Delta); 992 default: 993 llvm_unreachable("unexpected predicate in isKnownPredicate"); 994 } 995 } 996 997 /// Compare to see if S is less than Size, using isKnownNegative(S - max(Size, 1)) 998 /// with some extra checking if S is an AddRec and we can prove less-than using 999 /// the loop bounds. 1000 bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const { 1001 // First unify to the same type 1002 auto *SType = dyn_cast<IntegerType>(S->getType()); 1003 auto *SizeType = dyn_cast<IntegerType>(Size->getType()); 1004 if (!SType || !SizeType) 1005 return false; 1006 Type *MaxType = 1007 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType; 1008 S = SE->getTruncateOrZeroExtend(S, MaxType); 1009 Size = SE->getTruncateOrZeroExtend(Size, MaxType); 1010 1011 // Special check for addrecs using BE taken count 1012 const SCEV *Bound = SE->getMinusSCEV(S, Size); 1013 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) { 1014 if (AddRec->isAffine()) { 1015 const SCEV *BECount = SE->getBackedgeTakenCount(AddRec->getLoop()); 1016 if (!isa<SCEVCouldNotCompute>(BECount)) { 1017 const SCEV *Limit = AddRec->evaluateAtIteration(BECount, *SE); 1018 if (SE->isKnownNegative(Limit)) 1019 return true; 1020 } 1021 } 1022 } 1023 1024 // Check using normal isKnownNegative 1025 const SCEV *LimitedBound = 1026 SE->getMinusSCEV(S, SE->getSMaxExpr(Size, SE->getOne(Size->getType()))); 1027 return SE->isKnownNegative(LimitedBound); 1028 } 1029 1030 bool DependenceInfo::isKnownNonNegative(const SCEV *S, const Value *Ptr) const { 1031 bool Inbounds = false; 1032 if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr)) 1033 Inbounds = SrcGEP->isInBounds(); 1034 if (Inbounds) { 1035 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { 1036 if (AddRec->isAffine()) { 1037 // We know S is for Ptr, the operand on a load/store, so doesn't wrap. 1038 // If both parts are NonNegative, the end result will be NonNegative 1039 if (SE->isKnownNonNegative(AddRec->getStart()) && 1040 SE->isKnownNonNegative(AddRec->getOperand(1))) 1041 return true; 1042 } 1043 } 1044 } 1045 1046 return SE->isKnownNonNegative(S); 1047 } 1048 1049 // All subscripts are all the same type. 1050 // Loop bound may be smaller (e.g., a char). 1051 // Should zero extend loop bound, since it's always >= 0. 1052 // This routine collects upper bound and extends or truncates if needed. 1053 // Truncating is safe when subscripts are known not to wrap. Cases without 1054 // nowrap flags should have been rejected earlier. 1055 // Return null if no bound available. 1056 const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const { 1057 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 1058 const SCEV *UB = SE->getBackedgeTakenCount(L); 1059 return SE->getTruncateOrZeroExtend(UB, T); 1060 } 1061 return nullptr; 1062 } 1063 1064 1065 // Calls collectUpperBound(), then attempts to cast it to SCEVConstant. 1066 // If the cast fails, returns NULL. 1067 const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L, 1068 Type *T) const { 1069 if (const SCEV *UB = collectUpperBound(L, T)) 1070 return dyn_cast<SCEVConstant>(UB); 1071 return nullptr; 1072 } 1073 1074 1075 // testZIV - 1076 // When we have a pair of subscripts of the form [c1] and [c2], 1077 // where c1 and c2 are both loop invariant, we attack it using 1078 // the ZIV test. Basically, we test by comparing the two values, 1079 // but there are actually three possible results: 1080 // 1) the values are equal, so there's a dependence 1081 // 2) the values are different, so there's no dependence 1082 // 3) the values might be equal, so we have to assume a dependence. 1083 // 1084 // Return true if dependence disproved. 1085 bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst, 1086 FullDependence &Result) const { 1087 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n"); 1088 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n"); 1089 ++ZIVapplications; 1090 if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) { 1091 LLVM_DEBUG(dbgs() << " provably dependent\n"); 1092 return false; // provably dependent 1093 } 1094 if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) { 1095 LLVM_DEBUG(dbgs() << " provably independent\n"); 1096 ++ZIVindependence; 1097 return true; // provably independent 1098 } 1099 LLVM_DEBUG(dbgs() << " possibly dependent\n"); 1100 Result.Consistent = false; 1101 return false; // possibly dependent 1102 } 1103 1104 1105 // strongSIVtest - 1106 // From the paper, Practical Dependence Testing, Section 4.2.1 1107 // 1108 // When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i], 1109 // where i is an induction variable, c1 and c2 are loop invariant, 1110 // and a is a constant, we can solve it exactly using the Strong SIV test. 1111 // 1112 // Can prove independence. Failing that, can compute distance (and direction). 1113 // In the presence of symbolic terms, we can sometimes make progress. 1114 // 1115 // If there's a dependence, 1116 // 1117 // c1 + a*i = c2 + a*i' 1118 // 1119 // The dependence distance is 1120 // 1121 // d = i' - i = (c1 - c2)/a 1122 // 1123 // A dependence only exists if d is an integer and abs(d) <= U, where U is the 1124 // loop's upper bound. If a dependence exists, the dependence direction is 1125 // defined as 1126 // 1127 // { < if d > 0 1128 // direction = { = if d = 0 1129 // { > if d < 0 1130 // 1131 // Return true if dependence disproved. 1132 bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, 1133 const SCEV *DstConst, const Loop *CurLoop, 1134 unsigned Level, FullDependence &Result, 1135 Constraint &NewConstraint) const { 1136 LLVM_DEBUG(dbgs() << "\tStrong SIV test\n"); 1137 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff); 1138 LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n"); 1139 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst); 1140 LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n"); 1141 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst); 1142 LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n"); 1143 ++StrongSIVapplications; 1144 assert(0 < Level && Level <= CommonLevels && "level out of range"); 1145 Level--; 1146 1147 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); 1148 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta); 1149 LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n"); 1150 1151 // check that |Delta| < iteration count 1152 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1153 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound); 1154 LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n"); 1155 const SCEV *AbsDelta = 1156 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta); 1157 const SCEV *AbsCoeff = 1158 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff); 1159 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff); 1160 if (isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product)) { 1161 // Distance greater than trip count - no dependence 1162 ++StrongSIVindependence; 1163 ++StrongSIVsuccesses; 1164 return true; 1165 } 1166 } 1167 1168 // Can we compute distance? 1169 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) { 1170 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt(); 1171 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt(); 1172 APInt Distance = ConstDelta; // these need to be initialized 1173 APInt Remainder = ConstDelta; 1174 APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder); 1175 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n"); 1176 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n"); 1177 // Make sure Coeff divides Delta exactly 1178 if (Remainder != 0) { 1179 // Coeff doesn't divide Distance, no dependence 1180 ++StrongSIVindependence; 1181 ++StrongSIVsuccesses; 1182 return true; 1183 } 1184 Result.DV[Level].Distance = SE->getConstant(Distance); 1185 NewConstraint.setDistance(SE->getConstant(Distance), CurLoop); 1186 if (Distance.sgt(0)) 1187 Result.DV[Level].Direction &= Dependence::DVEntry::LT; 1188 else if (Distance.slt(0)) 1189 Result.DV[Level].Direction &= Dependence::DVEntry::GT; 1190 else 1191 Result.DV[Level].Direction &= Dependence::DVEntry::EQ; 1192 ++StrongSIVsuccesses; 1193 } 1194 else if (Delta->isZero()) { 1195 // since 0/X == 0 1196 Result.DV[Level].Distance = Delta; 1197 NewConstraint.setDistance(Delta, CurLoop); 1198 Result.DV[Level].Direction &= Dependence::DVEntry::EQ; 1199 ++StrongSIVsuccesses; 1200 } 1201 else { 1202 if (Coeff->isOne()) { 1203 LLVM_DEBUG(dbgs() << "\t Distance = " << *Delta << "\n"); 1204 Result.DV[Level].Distance = Delta; // since X/1 == X 1205 NewConstraint.setDistance(Delta, CurLoop); 1206 } 1207 else { 1208 Result.Consistent = false; 1209 NewConstraint.setLine(Coeff, 1210 SE->getNegativeSCEV(Coeff), 1211 SE->getNegativeSCEV(Delta), CurLoop); 1212 } 1213 1214 // maybe we can get a useful direction 1215 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta); 1216 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta); 1217 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta); 1218 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff); 1219 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff); 1220 // The double negatives above are confusing. 1221 // It helps to read !SE->isKnownNonZero(Delta) 1222 // as "Delta might be Zero" 1223 unsigned NewDirection = Dependence::DVEntry::NONE; 1224 if ((DeltaMaybePositive && CoeffMaybePositive) || 1225 (DeltaMaybeNegative && CoeffMaybeNegative)) 1226 NewDirection = Dependence::DVEntry::LT; 1227 if (DeltaMaybeZero) 1228 NewDirection |= Dependence::DVEntry::EQ; 1229 if ((DeltaMaybeNegative && CoeffMaybePositive) || 1230 (DeltaMaybePositive && CoeffMaybeNegative)) 1231 NewDirection |= Dependence::DVEntry::GT; 1232 if (NewDirection < Result.DV[Level].Direction) 1233 ++StrongSIVsuccesses; 1234 Result.DV[Level].Direction &= NewDirection; 1235 } 1236 return false; 1237 } 1238 1239 1240 // weakCrossingSIVtest - 1241 // From the paper, Practical Dependence Testing, Section 4.2.2 1242 // 1243 // When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i], 1244 // where i is an induction variable, c1 and c2 are loop invariant, 1245 // and a is a constant, we can solve it exactly using the 1246 // Weak-Crossing SIV test. 1247 // 1248 // Given c1 + a*i = c2 - a*i', we can look for the intersection of 1249 // the two lines, where i = i', yielding 1250 // 1251 // c1 + a*i = c2 - a*i 1252 // 2a*i = c2 - c1 1253 // i = (c2 - c1)/2a 1254 // 1255 // If i < 0, there is no dependence. 1256 // If i > upperbound, there is no dependence. 1257 // If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0. 1258 // If i = upperbound, there's a dependence with distance = 0. 1259 // If i is integral, there's a dependence (all directions). 1260 // If the non-integer part = 1/2, there's a dependence (<> directions). 1261 // Otherwise, there's no dependence. 1262 // 1263 // Can prove independence. Failing that, 1264 // can sometimes refine the directions. 1265 // Can determine iteration for splitting. 1266 // 1267 // Return true if dependence disproved. 1268 bool DependenceInfo::weakCrossingSIVtest( 1269 const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst, 1270 const Loop *CurLoop, unsigned Level, FullDependence &Result, 1271 Constraint &NewConstraint, const SCEV *&SplitIter) const { 1272 LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n"); 1273 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n"); 1274 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1275 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1276 ++WeakCrossingSIVapplications; 1277 assert(0 < Level && Level <= CommonLevels && "Level out of range"); 1278 Level--; 1279 Result.Consistent = false; 1280 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1281 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1282 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop); 1283 if (Delta->isZero()) { 1284 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT); 1285 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT); 1286 ++WeakCrossingSIVsuccesses; 1287 if (!Result.DV[Level].Direction) { 1288 ++WeakCrossingSIVindependence; 1289 return true; 1290 } 1291 Result.DV[Level].Distance = Delta; // = 0 1292 return false; 1293 } 1294 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff); 1295 if (!ConstCoeff) 1296 return false; 1297 1298 Result.DV[Level].Splitable = true; 1299 if (SE->isKnownNegative(ConstCoeff)) { 1300 ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff)); 1301 assert(ConstCoeff && 1302 "dynamic cast of negative of ConstCoeff should yield constant"); 1303 Delta = SE->getNegativeSCEV(Delta); 1304 } 1305 assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"); 1306 1307 // compute SplitIter for use by DependenceInfo::getSplitIteration() 1308 SplitIter = SE->getUDivExpr( 1309 SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta), 1310 SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff)); 1311 LLVM_DEBUG(dbgs() << "\t Split iter = " << *SplitIter << "\n"); 1312 1313 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta); 1314 if (!ConstDelta) 1315 return false; 1316 1317 // We're certain that ConstCoeff > 0; therefore, 1318 // if Delta < 0, then no dependence. 1319 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1320 LLVM_DEBUG(dbgs() << "\t ConstCoeff = " << *ConstCoeff << "\n"); 1321 if (SE->isKnownNegative(Delta)) { 1322 // No dependence, Delta < 0 1323 ++WeakCrossingSIVindependence; 1324 ++WeakCrossingSIVsuccesses; 1325 return true; 1326 } 1327 1328 // We're certain that Delta > 0 and ConstCoeff > 0. 1329 // Check Delta/(2*ConstCoeff) against upper loop bound 1330 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1331 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); 1332 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2); 1333 const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), 1334 ConstantTwo); 1335 LLVM_DEBUG(dbgs() << "\t ML = " << *ML << "\n"); 1336 if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) { 1337 // Delta too big, no dependence 1338 ++WeakCrossingSIVindependence; 1339 ++WeakCrossingSIVsuccesses; 1340 return true; 1341 } 1342 if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) { 1343 // i = i' = UB 1344 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT); 1345 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT); 1346 ++WeakCrossingSIVsuccesses; 1347 if (!Result.DV[Level].Direction) { 1348 ++WeakCrossingSIVindependence; 1349 return true; 1350 } 1351 Result.DV[Level].Splitable = false; 1352 Result.DV[Level].Distance = SE->getZero(Delta->getType()); 1353 return false; 1354 } 1355 } 1356 1357 // check that Coeff divides Delta 1358 APInt APDelta = ConstDelta->getAPInt(); 1359 APInt APCoeff = ConstCoeff->getAPInt(); 1360 APInt Distance = APDelta; // these need to be initialzed 1361 APInt Remainder = APDelta; 1362 APInt::sdivrem(APDelta, APCoeff, Distance, Remainder); 1363 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n"); 1364 if (Remainder != 0) { 1365 // Coeff doesn't divide Delta, no dependence 1366 ++WeakCrossingSIVindependence; 1367 ++WeakCrossingSIVsuccesses; 1368 return true; 1369 } 1370 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n"); 1371 1372 // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible 1373 APInt Two = APInt(Distance.getBitWidth(), 2, true); 1374 Remainder = Distance.srem(Two); 1375 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n"); 1376 if (Remainder != 0) { 1377 // Equal direction isn't possible 1378 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ); 1379 ++WeakCrossingSIVsuccesses; 1380 } 1381 return false; 1382 } 1383 1384 1385 // Kirch's algorithm, from 1386 // 1387 // Optimizing Supercompilers for Supercomputers 1388 // Michael Wolfe 1389 // MIT Press, 1989 1390 // 1391 // Program 2.1, page 29. 1392 // Computes the GCD of AM and BM. 1393 // Also finds a solution to the equation ax - by = gcd(a, b). 1394 // Returns true if dependence disproved; i.e., gcd does not divide Delta. 1395 static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, 1396 const APInt &Delta, APInt &G, APInt &X, APInt &Y) { 1397 APInt A0(Bits, 1, true), A1(Bits, 0, true); 1398 APInt B0(Bits, 0, true), B1(Bits, 1, true); 1399 APInt G0 = AM.abs(); 1400 APInt G1 = BM.abs(); 1401 APInt Q = G0; // these need to be initialized 1402 APInt R = G0; 1403 APInt::sdivrem(G0, G1, Q, R); 1404 while (R != 0) { 1405 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2; 1406 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2; 1407 G0 = G1; G1 = R; 1408 APInt::sdivrem(G0, G1, Q, R); 1409 } 1410 G = G1; 1411 LLVM_DEBUG(dbgs() << "\t GCD = " << G << "\n"); 1412 X = AM.slt(0) ? -A1 : A1; 1413 Y = BM.slt(0) ? B1 : -B1; 1414 1415 // make sure gcd divides Delta 1416 R = Delta.srem(G); 1417 if (R != 0) 1418 return true; // gcd doesn't divide Delta, no dependence 1419 Q = Delta.sdiv(G); 1420 X *= Q; 1421 Y *= Q; 1422 return false; 1423 } 1424 1425 static APInt floorOfQuotient(const APInt &A, const APInt &B) { 1426 APInt Q = A; // these need to be initialized 1427 APInt R = A; 1428 APInt::sdivrem(A, B, Q, R); 1429 if (R == 0) 1430 return Q; 1431 if ((A.sgt(0) && B.sgt(0)) || 1432 (A.slt(0) && B.slt(0))) 1433 return Q; 1434 else 1435 return Q - 1; 1436 } 1437 1438 static APInt ceilingOfQuotient(const APInt &A, const APInt &B) { 1439 APInt Q = A; // these need to be initialized 1440 APInt R = A; 1441 APInt::sdivrem(A, B, Q, R); 1442 if (R == 0) 1443 return Q; 1444 if ((A.sgt(0) && B.sgt(0)) || 1445 (A.slt(0) && B.slt(0))) 1446 return Q + 1; 1447 else 1448 return Q; 1449 } 1450 1451 1452 static 1453 APInt maxAPInt(APInt A, APInt B) { 1454 return A.sgt(B) ? A : B; 1455 } 1456 1457 1458 static 1459 APInt minAPInt(APInt A, APInt B) { 1460 return A.slt(B) ? A : B; 1461 } 1462 1463 1464 // exactSIVtest - 1465 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i], 1466 // where i is an induction variable, c1 and c2 are loop invariant, and a1 1467 // and a2 are constant, we can solve it exactly using an algorithm developed 1468 // by Banerjee and Wolfe. See Section 2.5.3 in 1469 // 1470 // Optimizing Supercompilers for Supercomputers 1471 // Michael Wolfe 1472 // MIT Press, 1989 1473 // 1474 // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc), 1475 // so use them if possible. They're also a bit better with symbolics and, 1476 // in the case of the strong SIV test, can compute Distances. 1477 // 1478 // Return true if dependence disproved. 1479 bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, 1480 const SCEV *SrcConst, const SCEV *DstConst, 1481 const Loop *CurLoop, unsigned Level, 1482 FullDependence &Result, 1483 Constraint &NewConstraint) const { 1484 LLVM_DEBUG(dbgs() << "\tExact SIV test\n"); 1485 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n"); 1486 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n"); 1487 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1488 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1489 ++ExactSIVapplications; 1490 assert(0 < Level && Level <= CommonLevels && "Level out of range"); 1491 Level--; 1492 Result.Consistent = false; 1493 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1494 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1495 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), 1496 Delta, CurLoop); 1497 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta); 1498 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff); 1499 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff); 1500 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff) 1501 return false; 1502 1503 // find gcd 1504 APInt G, X, Y; 1505 APInt AM = ConstSrcCoeff->getAPInt(); 1506 APInt BM = ConstDstCoeff->getAPInt(); 1507 unsigned Bits = AM.getBitWidth(); 1508 if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) { 1509 // gcd doesn't divide Delta, no dependence 1510 ++ExactSIVindependence; 1511 ++ExactSIVsuccesses; 1512 return true; 1513 } 1514 1515 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n"); 1516 1517 // since SCEV construction normalizes, LM = 0 1518 APInt UM(Bits, 1, true); 1519 bool UMvalid = false; 1520 // UM is perhaps unavailable, let's check 1521 if (const SCEVConstant *CUB = 1522 collectConstantUpperBound(CurLoop, Delta->getType())) { 1523 UM = CUB->getAPInt(); 1524 LLVM_DEBUG(dbgs() << "\t UM = " << UM << "\n"); 1525 UMvalid = true; 1526 } 1527 1528 APInt TU(APInt::getSignedMaxValue(Bits)); 1529 APInt TL(APInt::getSignedMinValue(Bits)); 1530 1531 // test(BM/G, LM-X) and test(-BM/G, X-UM) 1532 APInt TMUL = BM.sdiv(G); 1533 if (TMUL.sgt(0)) { 1534 TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL)); 1535 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1536 if (UMvalid) { 1537 TU = minAPInt(TU, floorOfQuotient(UM - X, TMUL)); 1538 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1539 } 1540 } 1541 else { 1542 TU = minAPInt(TU, floorOfQuotient(-X, TMUL)); 1543 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1544 if (UMvalid) { 1545 TL = maxAPInt(TL, ceilingOfQuotient(UM - X, TMUL)); 1546 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1547 } 1548 } 1549 1550 // test(AM/G, LM-Y) and test(-AM/G, Y-UM) 1551 TMUL = AM.sdiv(G); 1552 if (TMUL.sgt(0)) { 1553 TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL)); 1554 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1555 if (UMvalid) { 1556 TU = minAPInt(TU, floorOfQuotient(UM - Y, TMUL)); 1557 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1558 } 1559 } 1560 else { 1561 TU = minAPInt(TU, floorOfQuotient(-Y, TMUL)); 1562 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1563 if (UMvalid) { 1564 TL = maxAPInt(TL, ceilingOfQuotient(UM - Y, TMUL)); 1565 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1566 } 1567 } 1568 if (TL.sgt(TU)) { 1569 ++ExactSIVindependence; 1570 ++ExactSIVsuccesses; 1571 return true; 1572 } 1573 1574 // explore directions 1575 unsigned NewDirection = Dependence::DVEntry::NONE; 1576 1577 // less than 1578 APInt SaveTU(TU); // save these 1579 APInt SaveTL(TL); 1580 LLVM_DEBUG(dbgs() << "\t exploring LT direction\n"); 1581 TMUL = AM - BM; 1582 if (TMUL.sgt(0)) { 1583 TL = maxAPInt(TL, ceilingOfQuotient(X - Y + 1, TMUL)); 1584 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1585 } 1586 else { 1587 TU = minAPInt(TU, floorOfQuotient(X - Y + 1, TMUL)); 1588 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1589 } 1590 if (TL.sle(TU)) { 1591 NewDirection |= Dependence::DVEntry::LT; 1592 ++ExactSIVsuccesses; 1593 } 1594 1595 // equal 1596 TU = SaveTU; // restore 1597 TL = SaveTL; 1598 LLVM_DEBUG(dbgs() << "\t exploring EQ direction\n"); 1599 if (TMUL.sgt(0)) { 1600 TL = maxAPInt(TL, ceilingOfQuotient(X - Y, TMUL)); 1601 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1602 } 1603 else { 1604 TU = minAPInt(TU, floorOfQuotient(X - Y, TMUL)); 1605 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1606 } 1607 TMUL = BM - AM; 1608 if (TMUL.sgt(0)) { 1609 TL = maxAPInt(TL, ceilingOfQuotient(Y - X, TMUL)); 1610 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1611 } 1612 else { 1613 TU = minAPInt(TU, floorOfQuotient(Y - X, TMUL)); 1614 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1615 } 1616 if (TL.sle(TU)) { 1617 NewDirection |= Dependence::DVEntry::EQ; 1618 ++ExactSIVsuccesses; 1619 } 1620 1621 // greater than 1622 TU = SaveTU; // restore 1623 TL = SaveTL; 1624 LLVM_DEBUG(dbgs() << "\t exploring GT direction\n"); 1625 if (TMUL.sgt(0)) { 1626 TL = maxAPInt(TL, ceilingOfQuotient(Y - X + 1, TMUL)); 1627 LLVM_DEBUG(dbgs() << "\t\t TL = " << TL << "\n"); 1628 } 1629 else { 1630 TU = minAPInt(TU, floorOfQuotient(Y - X + 1, TMUL)); 1631 LLVM_DEBUG(dbgs() << "\t\t TU = " << TU << "\n"); 1632 } 1633 if (TL.sle(TU)) { 1634 NewDirection |= Dependence::DVEntry::GT; 1635 ++ExactSIVsuccesses; 1636 } 1637 1638 // finished 1639 Result.DV[Level].Direction &= NewDirection; 1640 if (Result.DV[Level].Direction == Dependence::DVEntry::NONE) 1641 ++ExactSIVindependence; 1642 return Result.DV[Level].Direction == Dependence::DVEntry::NONE; 1643 } 1644 1645 1646 1647 // Return true if the divisor evenly divides the dividend. 1648 static 1649 bool isRemainderZero(const SCEVConstant *Dividend, 1650 const SCEVConstant *Divisor) { 1651 const APInt &ConstDividend = Dividend->getAPInt(); 1652 const APInt &ConstDivisor = Divisor->getAPInt(); 1653 return ConstDividend.srem(ConstDivisor) == 0; 1654 } 1655 1656 1657 // weakZeroSrcSIVtest - 1658 // From the paper, Practical Dependence Testing, Section 4.2.2 1659 // 1660 // When we have a pair of subscripts of the form [c1] and [c2 + a*i], 1661 // where i is an induction variable, c1 and c2 are loop invariant, 1662 // and a is a constant, we can solve it exactly using the 1663 // Weak-Zero SIV test. 1664 // 1665 // Given 1666 // 1667 // c1 = c2 + a*i 1668 // 1669 // we get 1670 // 1671 // (c1 - c2)/a = i 1672 // 1673 // If i is not an integer, there's no dependence. 1674 // If i < 0 or > UB, there's no dependence. 1675 // If i = 0, the direction is >= and peeling the 1676 // 1st iteration will break the dependence. 1677 // If i = UB, the direction is <= and peeling the 1678 // last iteration will break the dependence. 1679 // Otherwise, the direction is *. 1680 // 1681 // Can prove independence. Failing that, we can sometimes refine 1682 // the directions. Can sometimes show that first or last 1683 // iteration carries all the dependences (so worth peeling). 1684 // 1685 // (see also weakZeroDstSIVtest) 1686 // 1687 // Return true if dependence disproved. 1688 bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, 1689 const SCEV *SrcConst, 1690 const SCEV *DstConst, 1691 const Loop *CurLoop, unsigned Level, 1692 FullDependence &Result, 1693 Constraint &NewConstraint) const { 1694 // For the WeakSIV test, it's possible the loop isn't common to 1695 // the Src and Dst loops. If it isn't, then there's no need to 1696 // record a direction. 1697 LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n"); 1698 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n"); 1699 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1700 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1701 ++WeakZeroSIVapplications; 1702 assert(0 < Level && Level <= MaxLevels && "Level out of range"); 1703 Level--; 1704 Result.Consistent = false; 1705 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); 1706 NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta, 1707 CurLoop); 1708 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1709 if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) { 1710 if (Level < CommonLevels) { 1711 Result.DV[Level].Direction &= Dependence::DVEntry::GE; 1712 Result.DV[Level].PeelFirst = true; 1713 ++WeakZeroSIVsuccesses; 1714 } 1715 return false; // dependences caused by first iteration 1716 } 1717 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff); 1718 if (!ConstCoeff) 1719 return false; 1720 const SCEV *AbsCoeff = 1721 SE->isKnownNegative(ConstCoeff) ? 1722 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; 1723 const SCEV *NewDelta = 1724 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; 1725 1726 // check that Delta/SrcCoeff < iteration count 1727 // really check NewDelta < count*AbsCoeff 1728 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1729 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); 1730 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); 1731 if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) { 1732 ++WeakZeroSIVindependence; 1733 ++WeakZeroSIVsuccesses; 1734 return true; 1735 } 1736 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { 1737 // dependences caused by last iteration 1738 if (Level < CommonLevels) { 1739 Result.DV[Level].Direction &= Dependence::DVEntry::LE; 1740 Result.DV[Level].PeelLast = true; 1741 ++WeakZeroSIVsuccesses; 1742 } 1743 return false; 1744 } 1745 } 1746 1747 // check that Delta/SrcCoeff >= 0 1748 // really check that NewDelta >= 0 1749 if (SE->isKnownNegative(NewDelta)) { 1750 // No dependence, newDelta < 0 1751 ++WeakZeroSIVindependence; 1752 ++WeakZeroSIVsuccesses; 1753 return true; 1754 } 1755 1756 // if SrcCoeff doesn't divide Delta, then no dependence 1757 if (isa<SCEVConstant>(Delta) && 1758 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) { 1759 ++WeakZeroSIVindependence; 1760 ++WeakZeroSIVsuccesses; 1761 return true; 1762 } 1763 return false; 1764 } 1765 1766 1767 // weakZeroDstSIVtest - 1768 // From the paper, Practical Dependence Testing, Section 4.2.2 1769 // 1770 // When we have a pair of subscripts of the form [c1 + a*i] and [c2], 1771 // where i is an induction variable, c1 and c2 are loop invariant, 1772 // and a is a constant, we can solve it exactly using the 1773 // Weak-Zero SIV test. 1774 // 1775 // Given 1776 // 1777 // c1 + a*i = c2 1778 // 1779 // we get 1780 // 1781 // i = (c2 - c1)/a 1782 // 1783 // If i is not an integer, there's no dependence. 1784 // If i < 0 or > UB, there's no dependence. 1785 // If i = 0, the direction is <= and peeling the 1786 // 1st iteration will break the dependence. 1787 // If i = UB, the direction is >= and peeling the 1788 // last iteration will break the dependence. 1789 // Otherwise, the direction is *. 1790 // 1791 // Can prove independence. Failing that, we can sometimes refine 1792 // the directions. Can sometimes show that first or last 1793 // iteration carries all the dependences (so worth peeling). 1794 // 1795 // (see also weakZeroSrcSIVtest) 1796 // 1797 // Return true if dependence disproved. 1798 bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, 1799 const SCEV *SrcConst, 1800 const SCEV *DstConst, 1801 const Loop *CurLoop, unsigned Level, 1802 FullDependence &Result, 1803 Constraint &NewConstraint) const { 1804 // For the WeakSIV test, it's possible the loop isn't common to the 1805 // Src and Dst loops. If it isn't, then there's no need to record a direction. 1806 LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n"); 1807 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n"); 1808 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1809 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1810 ++WeakZeroSIVapplications; 1811 assert(0 < Level && Level <= SrcLevels && "Level out of range"); 1812 Level--; 1813 Result.Consistent = false; 1814 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1815 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta, 1816 CurLoop); 1817 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1818 if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) { 1819 if (Level < CommonLevels) { 1820 Result.DV[Level].Direction &= Dependence::DVEntry::LE; 1821 Result.DV[Level].PeelFirst = true; 1822 ++WeakZeroSIVsuccesses; 1823 } 1824 return false; // dependences caused by first iteration 1825 } 1826 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff); 1827 if (!ConstCoeff) 1828 return false; 1829 const SCEV *AbsCoeff = 1830 SE->isKnownNegative(ConstCoeff) ? 1831 SE->getNegativeSCEV(ConstCoeff) : ConstCoeff; 1832 const SCEV *NewDelta = 1833 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; 1834 1835 // check that Delta/SrcCoeff < iteration count 1836 // really check NewDelta < count*AbsCoeff 1837 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) { 1838 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); 1839 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); 1840 if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) { 1841 ++WeakZeroSIVindependence; 1842 ++WeakZeroSIVsuccesses; 1843 return true; 1844 } 1845 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { 1846 // dependences caused by last iteration 1847 if (Level < CommonLevels) { 1848 Result.DV[Level].Direction &= Dependence::DVEntry::GE; 1849 Result.DV[Level].PeelLast = true; 1850 ++WeakZeroSIVsuccesses; 1851 } 1852 return false; 1853 } 1854 } 1855 1856 // check that Delta/SrcCoeff >= 0 1857 // really check that NewDelta >= 0 1858 if (SE->isKnownNegative(NewDelta)) { 1859 // No dependence, newDelta < 0 1860 ++WeakZeroSIVindependence; 1861 ++WeakZeroSIVsuccesses; 1862 return true; 1863 } 1864 1865 // if SrcCoeff doesn't divide Delta, then no dependence 1866 if (isa<SCEVConstant>(Delta) && 1867 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) { 1868 ++WeakZeroSIVindependence; 1869 ++WeakZeroSIVsuccesses; 1870 return true; 1871 } 1872 return false; 1873 } 1874 1875 1876 // exactRDIVtest - Tests the RDIV subscript pair for dependence. 1877 // Things of the form [c1 + a*i] and [c2 + b*j], 1878 // where i and j are induction variable, c1 and c2 are loop invariant, 1879 // and a and b are constants. 1880 // Returns true if any possible dependence is disproved. 1881 // Marks the result as inconsistent. 1882 // Works in some cases that symbolicRDIVtest doesn't, and vice versa. 1883 bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, 1884 const SCEV *SrcConst, const SCEV *DstConst, 1885 const Loop *SrcLoop, const Loop *DstLoop, 1886 FullDependence &Result) const { 1887 LLVM_DEBUG(dbgs() << "\tExact RDIV test\n"); 1888 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n"); 1889 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n"); 1890 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); 1891 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); 1892 ++ExactRDIVapplications; 1893 Result.Consistent = false; 1894 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 1895 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); 1896 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta); 1897 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff); 1898 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff); 1899 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff) 1900 return false; 1901 1902 // find gcd 1903 APInt G, X, Y; 1904 APInt AM = ConstSrcCoeff->getAPInt(); 1905 APInt BM = ConstDstCoeff->getAPInt(); 1906 unsigned Bits = AM.getBitWidth(); 1907 if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) { 1908 // gcd doesn't divide Delta, no dependence 1909 ++ExactRDIVindependence; 1910 return true; 1911 } 1912 1913 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n"); 1914 1915 // since SCEV construction seems to normalize, LM = 0 1916 APInt SrcUM(Bits, 1, true); 1917 bool SrcUMvalid = false; 1918 // SrcUM is perhaps unavailable, let's check 1919 if (const SCEVConstant *UpperBound = 1920 collectConstantUpperBound(SrcLoop, Delta->getType())) { 1921 SrcUM = UpperBound->getAPInt(); 1922 LLVM_DEBUG(dbgs() << "\t SrcUM = " << SrcUM << "\n"); 1923 SrcUMvalid = true; 1924 } 1925 1926 APInt DstUM(Bits, 1, true); 1927 bool DstUMvalid = false; 1928 // UM is perhaps unavailable, let's check 1929 if (const SCEVConstant *UpperBound = 1930 collectConstantUpperBound(DstLoop, Delta->getType())) { 1931 DstUM = UpperBound->getAPInt(); 1932 LLVM_DEBUG(dbgs() << "\t DstUM = " << DstUM << "\n"); 1933 DstUMvalid = true; 1934 } 1935 1936 APInt TU(APInt::getSignedMaxValue(Bits)); 1937 APInt TL(APInt::getSignedMinValue(Bits)); 1938 1939 // test(BM/G, LM-X) and test(-BM/G, X-UM) 1940 APInt TMUL = BM.sdiv(G); 1941 if (TMUL.sgt(0)) { 1942 TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL)); 1943 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1944 if (SrcUMvalid) { 1945 TU = minAPInt(TU, floorOfQuotient(SrcUM - X, TMUL)); 1946 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1947 } 1948 } 1949 else { 1950 TU = minAPInt(TU, floorOfQuotient(-X, TMUL)); 1951 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1952 if (SrcUMvalid) { 1953 TL = maxAPInt(TL, ceilingOfQuotient(SrcUM - X, TMUL)); 1954 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1955 } 1956 } 1957 1958 // test(AM/G, LM-Y) and test(-AM/G, Y-UM) 1959 TMUL = AM.sdiv(G); 1960 if (TMUL.sgt(0)) { 1961 TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL)); 1962 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1963 if (DstUMvalid) { 1964 TU = minAPInt(TU, floorOfQuotient(DstUM - Y, TMUL)); 1965 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1966 } 1967 } 1968 else { 1969 TU = minAPInt(TU, floorOfQuotient(-Y, TMUL)); 1970 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n"); 1971 if (DstUMvalid) { 1972 TL = maxAPInt(TL, ceilingOfQuotient(DstUM - Y, TMUL)); 1973 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n"); 1974 } 1975 } 1976 if (TL.sgt(TU)) 1977 ++ExactRDIVindependence; 1978 return TL.sgt(TU); 1979 } 1980 1981 1982 // symbolicRDIVtest - 1983 // In Section 4.5 of the Practical Dependence Testing paper,the authors 1984 // introduce a special case of Banerjee's Inequalities (also called the 1985 // Extreme-Value Test) that can handle some of the SIV and RDIV cases, 1986 // particularly cases with symbolics. Since it's only able to disprove 1987 // dependence (not compute distances or directions), we'll use it as a 1988 // fall back for the other tests. 1989 // 1990 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j] 1991 // where i and j are induction variables and c1 and c2 are loop invariants, 1992 // we can use the symbolic tests to disprove some dependences, serving as a 1993 // backup for the RDIV test. Note that i and j can be the same variable, 1994 // letting this test serve as a backup for the various SIV tests. 1995 // 1996 // For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some 1997 // 0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized) 1998 // loop bounds for the i and j loops, respectively. So, ... 1999 // 2000 // c1 + a1*i = c2 + a2*j 2001 // a1*i - a2*j = c2 - c1 2002 // 2003 // To test for a dependence, we compute c2 - c1 and make sure it's in the 2004 // range of the maximum and minimum possible values of a1*i - a2*j. 2005 // Considering the signs of a1 and a2, we have 4 possible cases: 2006 // 2007 // 1) If a1 >= 0 and a2 >= 0, then 2008 // a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0 2009 // -a2*N2 <= c2 - c1 <= a1*N1 2010 // 2011 // 2) If a1 >= 0 and a2 <= 0, then 2012 // a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2 2013 // 0 <= c2 - c1 <= a1*N1 - a2*N2 2014 // 2015 // 3) If a1 <= 0 and a2 >= 0, then 2016 // a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0 2017 // a1*N1 - a2*N2 <= c2 - c1 <= 0 2018 // 2019 // 4) If a1 <= 0 and a2 <= 0, then 2020 // a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2 2021 // a1*N1 <= c2 - c1 <= -a2*N2 2022 // 2023 // return true if dependence disproved 2024 bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2, 2025 const SCEV *C1, const SCEV *C2, 2026 const Loop *Loop1, 2027 const Loop *Loop2) const { 2028 ++SymbolicRDIVapplications; 2029 LLVM_DEBUG(dbgs() << "\ttry symbolic RDIV test\n"); 2030 LLVM_DEBUG(dbgs() << "\t A1 = " << *A1); 2031 LLVM_DEBUG(dbgs() << ", type = " << *A1->getType() << "\n"); 2032 LLVM_DEBUG(dbgs() << "\t A2 = " << *A2 << "\n"); 2033 LLVM_DEBUG(dbgs() << "\t C1 = " << *C1 << "\n"); 2034 LLVM_DEBUG(dbgs() << "\t C2 = " << *C2 << "\n"); 2035 const SCEV *N1 = collectUpperBound(Loop1, A1->getType()); 2036 const SCEV *N2 = collectUpperBound(Loop2, A1->getType()); 2037 LLVM_DEBUG(if (N1) dbgs() << "\t N1 = " << *N1 << "\n"); 2038 LLVM_DEBUG(if (N2) dbgs() << "\t N2 = " << *N2 << "\n"); 2039 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1); 2040 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2); 2041 LLVM_DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n"); 2042 LLVM_DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n"); 2043 if (SE->isKnownNonNegative(A1)) { 2044 if (SE->isKnownNonNegative(A2)) { 2045 // A1 >= 0 && A2 >= 0 2046 if (N1) { 2047 // make sure that c2 - c1 <= a1*N1 2048 const SCEV *A1N1 = SE->getMulExpr(A1, N1); 2049 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n"); 2050 if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) { 2051 ++SymbolicRDIVindependence; 2052 return true; 2053 } 2054 } 2055 if (N2) { 2056 // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2 2057 const SCEV *A2N2 = SE->getMulExpr(A2, N2); 2058 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n"); 2059 if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) { 2060 ++SymbolicRDIVindependence; 2061 return true; 2062 } 2063 } 2064 } 2065 else if (SE->isKnownNonPositive(A2)) { 2066 // a1 >= 0 && a2 <= 0 2067 if (N1 && N2) { 2068 // make sure that c2 - c1 <= a1*N1 - a2*N2 2069 const SCEV *A1N1 = SE->getMulExpr(A1, N1); 2070 const SCEV *A2N2 = SE->getMulExpr(A2, N2); 2071 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); 2072 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); 2073 if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) { 2074 ++SymbolicRDIVindependence; 2075 return true; 2076 } 2077 } 2078 // make sure that 0 <= c2 - c1 2079 if (SE->isKnownNegative(C2_C1)) { 2080 ++SymbolicRDIVindependence; 2081 return true; 2082 } 2083 } 2084 } 2085 else if (SE->isKnownNonPositive(A1)) { 2086 if (SE->isKnownNonNegative(A2)) { 2087 // a1 <= 0 && a2 >= 0 2088 if (N1 && N2) { 2089 // make sure that a1*N1 - a2*N2 <= c2 - c1 2090 const SCEV *A1N1 = SE->getMulExpr(A1, N1); 2091 const SCEV *A2N2 = SE->getMulExpr(A2, N2); 2092 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2); 2093 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n"); 2094 if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) { 2095 ++SymbolicRDIVindependence; 2096 return true; 2097 } 2098 } 2099 // make sure that c2 - c1 <= 0 2100 if (SE->isKnownPositive(C2_C1)) { 2101 ++SymbolicRDIVindependence; 2102 return true; 2103 } 2104 } 2105 else if (SE->isKnownNonPositive(A2)) { 2106 // a1 <= 0 && a2 <= 0 2107 if (N1) { 2108 // make sure that a1*N1 <= c2 - c1 2109 const SCEV *A1N1 = SE->getMulExpr(A1, N1); 2110 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n"); 2111 if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) { 2112 ++SymbolicRDIVindependence; 2113 return true; 2114 } 2115 } 2116 if (N2) { 2117 // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2 2118 const SCEV *A2N2 = SE->getMulExpr(A2, N2); 2119 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n"); 2120 if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) { 2121 ++SymbolicRDIVindependence; 2122 return true; 2123 } 2124 } 2125 } 2126 } 2127 return false; 2128 } 2129 2130 2131 // testSIV - 2132 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i] 2133 // where i is an induction variable, c1 and c2 are loop invariant, and a1 and 2134 // a2 are constant, we attack it with an SIV test. While they can all be 2135 // solved with the Exact SIV test, it's worthwhile to use simpler tests when 2136 // they apply; they're cheaper and sometimes more precise. 2137 // 2138 // Return true if dependence disproved. 2139 bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, 2140 FullDependence &Result, Constraint &NewConstraint, 2141 const SCEV *&SplitIter) const { 2142 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n"); 2143 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n"); 2144 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src); 2145 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst); 2146 if (SrcAddRec && DstAddRec) { 2147 const SCEV *SrcConst = SrcAddRec->getStart(); 2148 const SCEV *DstConst = DstAddRec->getStart(); 2149 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); 2150 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); 2151 const Loop *CurLoop = SrcAddRec->getLoop(); 2152 assert(CurLoop == DstAddRec->getLoop() && 2153 "both loops in SIV should be same"); 2154 Level = mapSrcLoop(CurLoop); 2155 bool disproven; 2156 if (SrcCoeff == DstCoeff) 2157 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop, 2158 Level, Result, NewConstraint); 2159 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff)) 2160 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop, 2161 Level, Result, NewConstraint, SplitIter); 2162 else 2163 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, 2164 Level, Result, NewConstraint); 2165 return disproven || 2166 gcdMIVtest(Src, Dst, Result) || 2167 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop); 2168 } 2169 if (SrcAddRec) { 2170 const SCEV *SrcConst = SrcAddRec->getStart(); 2171 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); 2172 const SCEV *DstConst = Dst; 2173 const Loop *CurLoop = SrcAddRec->getLoop(); 2174 Level = mapSrcLoop(CurLoop); 2175 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop, 2176 Level, Result, NewConstraint) || 2177 gcdMIVtest(Src, Dst, Result); 2178 } 2179 if (DstAddRec) { 2180 const SCEV *DstConst = DstAddRec->getStart(); 2181 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); 2182 const SCEV *SrcConst = Src; 2183 const Loop *CurLoop = DstAddRec->getLoop(); 2184 Level = mapDstLoop(CurLoop); 2185 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, 2186 CurLoop, Level, Result, NewConstraint) || 2187 gcdMIVtest(Src, Dst, Result); 2188 } 2189 llvm_unreachable("SIV test expected at least one AddRec"); 2190 return false; 2191 } 2192 2193 2194 // testRDIV - 2195 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j] 2196 // where i and j are induction variables, c1 and c2 are loop invariant, 2197 // and a1 and a2 are constant, we can solve it exactly with an easy adaptation 2198 // of the Exact SIV test, the Restricted Double Index Variable (RDIV) test. 2199 // It doesn't make sense to talk about distance or direction in this case, 2200 // so there's no point in making special versions of the Strong SIV test or 2201 // the Weak-crossing SIV test. 2202 // 2203 // With minor algebra, this test can also be used for things like 2204 // [c1 + a1*i + a2*j][c2]. 2205 // 2206 // Return true if dependence disproved. 2207 bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst, 2208 FullDependence &Result) const { 2209 // we have 3 possible situations here: 2210 // 1) [a*i + b] and [c*j + d] 2211 // 2) [a*i + c*j + b] and [d] 2212 // 3) [b] and [a*i + c*j + d] 2213 // We need to find what we've got and get organized 2214 2215 const SCEV *SrcConst, *DstConst; 2216 const SCEV *SrcCoeff, *DstCoeff; 2217 const Loop *SrcLoop, *DstLoop; 2218 2219 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n"); 2220 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n"); 2221 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src); 2222 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst); 2223 if (SrcAddRec && DstAddRec) { 2224 SrcConst = SrcAddRec->getStart(); 2225 SrcCoeff = SrcAddRec->getStepRecurrence(*SE); 2226 SrcLoop = SrcAddRec->getLoop(); 2227 DstConst = DstAddRec->getStart(); 2228 DstCoeff = DstAddRec->getStepRecurrence(*SE); 2229 DstLoop = DstAddRec->getLoop(); 2230 } 2231 else if (SrcAddRec) { 2232 if (const SCEVAddRecExpr *tmpAddRec = 2233 dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) { 2234 SrcConst = tmpAddRec->getStart(); 2235 SrcCoeff = tmpAddRec->getStepRecurrence(*SE); 2236 SrcLoop = tmpAddRec->getLoop(); 2237 DstConst = Dst; 2238 DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE)); 2239 DstLoop = SrcAddRec->getLoop(); 2240 } 2241 else 2242 llvm_unreachable("RDIV reached by surprising SCEVs"); 2243 } 2244 else if (DstAddRec) { 2245 if (const SCEVAddRecExpr *tmpAddRec = 2246 dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) { 2247 DstConst = tmpAddRec->getStart(); 2248 DstCoeff = tmpAddRec->getStepRecurrence(*SE); 2249 DstLoop = tmpAddRec->getLoop(); 2250 SrcConst = Src; 2251 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE)); 2252 SrcLoop = DstAddRec->getLoop(); 2253 } 2254 else 2255 llvm_unreachable("RDIV reached by surprising SCEVs"); 2256 } 2257 else 2258 llvm_unreachable("RDIV expected at least one AddRec"); 2259 return exactRDIVtest(SrcCoeff, DstCoeff, 2260 SrcConst, DstConst, 2261 SrcLoop, DstLoop, 2262 Result) || 2263 gcdMIVtest(Src, Dst, Result) || 2264 symbolicRDIVtest(SrcCoeff, DstCoeff, 2265 SrcConst, DstConst, 2266 SrcLoop, DstLoop); 2267 } 2268 2269 2270 // Tests the single-subscript MIV pair (Src and Dst) for dependence. 2271 // Return true if dependence disproved. 2272 // Can sometimes refine direction vectors. 2273 bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst, 2274 const SmallBitVector &Loops, 2275 FullDependence &Result) const { 2276 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n"); 2277 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n"); 2278 Result.Consistent = false; 2279 return gcdMIVtest(Src, Dst, Result) || 2280 banerjeeMIVtest(Src, Dst, Loops, Result); 2281 } 2282 2283 2284 // Given a product, e.g., 10*X*Y, returns the first constant operand, 2285 // in this case 10. If there is no constant part, returns NULL. 2286 static 2287 const SCEVConstant *getConstantPart(const SCEV *Expr) { 2288 if (const auto *Constant = dyn_cast<SCEVConstant>(Expr)) 2289 return Constant; 2290 else if (const auto *Product = dyn_cast<SCEVMulExpr>(Expr)) 2291 if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0))) 2292 return Constant; 2293 return nullptr; 2294 } 2295 2296 2297 //===----------------------------------------------------------------------===// 2298 // gcdMIVtest - 2299 // Tests an MIV subscript pair for dependence. 2300 // Returns true if any possible dependence is disproved. 2301 // Marks the result as inconsistent. 2302 // Can sometimes disprove the equal direction for 1 or more loops, 2303 // as discussed in Michael Wolfe's book, 2304 // High Performance Compilers for Parallel Computing, page 235. 2305 // 2306 // We spend some effort (code!) to handle cases like 2307 // [10*i + 5*N*j + 15*M + 6], where i and j are induction variables, 2308 // but M and N are just loop-invariant variables. 2309 // This should help us handle linearized subscripts; 2310 // also makes this test a useful backup to the various SIV tests. 2311 // 2312 // It occurs to me that the presence of loop-invariant variables 2313 // changes the nature of the test from "greatest common divisor" 2314 // to "a common divisor". 2315 bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst, 2316 FullDependence &Result) const { 2317 LLVM_DEBUG(dbgs() << "starting gcd\n"); 2318 ++GCDapplications; 2319 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType()); 2320 APInt RunningGCD = APInt::getNullValue(BitWidth); 2321 2322 // Examine Src coefficients. 2323 // Compute running GCD and record source constant. 2324 // Because we're looking for the constant at the end of the chain, 2325 // we can't quit the loop just because the GCD == 1. 2326 const SCEV *Coefficients = Src; 2327 while (const SCEVAddRecExpr *AddRec = 2328 dyn_cast<SCEVAddRecExpr>(Coefficients)) { 2329 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2330 // If the coefficient is the product of a constant and other stuff, 2331 // we can use the constant in the GCD computation. 2332 const auto *Constant = getConstantPart(Coeff); 2333 if (!Constant) 2334 return false; 2335 APInt ConstCoeff = Constant->getAPInt(); 2336 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2337 Coefficients = AddRec->getStart(); 2338 } 2339 const SCEV *SrcConst = Coefficients; 2340 2341 // Examine Dst coefficients. 2342 // Compute running GCD and record destination constant. 2343 // Because we're looking for the constant at the end of the chain, 2344 // we can't quit the loop just because the GCD == 1. 2345 Coefficients = Dst; 2346 while (const SCEVAddRecExpr *AddRec = 2347 dyn_cast<SCEVAddRecExpr>(Coefficients)) { 2348 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2349 // If the coefficient is the product of a constant and other stuff, 2350 // we can use the constant in the GCD computation. 2351 const auto *Constant = getConstantPart(Coeff); 2352 if (!Constant) 2353 return false; 2354 APInt ConstCoeff = Constant->getAPInt(); 2355 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2356 Coefficients = AddRec->getStart(); 2357 } 2358 const SCEV *DstConst = Coefficients; 2359 2360 APInt ExtraGCD = APInt::getNullValue(BitWidth); 2361 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); 2362 LLVM_DEBUG(dbgs() << " Delta = " << *Delta << "\n"); 2363 const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta); 2364 if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) { 2365 // If Delta is a sum of products, we may be able to make further progress. 2366 for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) { 2367 const SCEV *Operand = Sum->getOperand(Op); 2368 if (isa<SCEVConstant>(Operand)) { 2369 assert(!Constant && "Surprised to find multiple constants"); 2370 Constant = cast<SCEVConstant>(Operand); 2371 } 2372 else if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) { 2373 // Search for constant operand to participate in GCD; 2374 // If none found; return false. 2375 const SCEVConstant *ConstOp = getConstantPart(Product); 2376 if (!ConstOp) 2377 return false; 2378 APInt ConstOpValue = ConstOp->getAPInt(); 2379 ExtraGCD = APIntOps::GreatestCommonDivisor(ExtraGCD, 2380 ConstOpValue.abs()); 2381 } 2382 else 2383 return false; 2384 } 2385 } 2386 if (!Constant) 2387 return false; 2388 APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt(); 2389 LLVM_DEBUG(dbgs() << " ConstDelta = " << ConstDelta << "\n"); 2390 if (ConstDelta == 0) 2391 return false; 2392 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ExtraGCD); 2393 LLVM_DEBUG(dbgs() << " RunningGCD = " << RunningGCD << "\n"); 2394 APInt Remainder = ConstDelta.srem(RunningGCD); 2395 if (Remainder != 0) { 2396 ++GCDindependence; 2397 return true; 2398 } 2399 2400 // Try to disprove equal directions. 2401 // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1], 2402 // the code above can't disprove the dependence because the GCD = 1. 2403 // So we consider what happen if i = i' and what happens if j = j'. 2404 // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1], 2405 // which is infeasible, so we can disallow the = direction for the i level. 2406 // Setting j = j' doesn't help matters, so we end up with a direction vector 2407 // of [<>, *] 2408 // 2409 // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5], 2410 // we need to remember that the constant part is 5 and the RunningGCD should 2411 // be initialized to ExtraGCD = 30. 2412 LLVM_DEBUG(dbgs() << " ExtraGCD = " << ExtraGCD << '\n'); 2413 2414 bool Improved = false; 2415 Coefficients = Src; 2416 while (const SCEVAddRecExpr *AddRec = 2417 dyn_cast<SCEVAddRecExpr>(Coefficients)) { 2418 Coefficients = AddRec->getStart(); 2419 const Loop *CurLoop = AddRec->getLoop(); 2420 RunningGCD = ExtraGCD; 2421 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE); 2422 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff); 2423 const SCEV *Inner = Src; 2424 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) { 2425 AddRec = cast<SCEVAddRecExpr>(Inner); 2426 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2427 if (CurLoop == AddRec->getLoop()) 2428 ; // SrcCoeff == Coeff 2429 else { 2430 // If the coefficient is the product of a constant and other stuff, 2431 // we can use the constant in the GCD computation. 2432 Constant = getConstantPart(Coeff); 2433 if (!Constant) 2434 return false; 2435 APInt ConstCoeff = Constant->getAPInt(); 2436 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2437 } 2438 Inner = AddRec->getStart(); 2439 } 2440 Inner = Dst; 2441 while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) { 2442 AddRec = cast<SCEVAddRecExpr>(Inner); 2443 const SCEV *Coeff = AddRec->getStepRecurrence(*SE); 2444 if (CurLoop == AddRec->getLoop()) 2445 DstCoeff = Coeff; 2446 else { 2447 // If the coefficient is the product of a constant and other stuff, 2448 // we can use the constant in the GCD computation. 2449 Constant = getConstantPart(Coeff); 2450 if (!Constant) 2451 return false; 2452 APInt ConstCoeff = Constant->getAPInt(); 2453 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2454 } 2455 Inner = AddRec->getStart(); 2456 } 2457 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff); 2458 // If the coefficient is the product of a constant and other stuff, 2459 // we can use the constant in the GCD computation. 2460 Constant = getConstantPart(Delta); 2461 if (!Constant) 2462 // The difference of the two coefficients might not be a product 2463 // or constant, in which case we give up on this direction. 2464 continue; 2465 APInt ConstCoeff = Constant->getAPInt(); 2466 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs()); 2467 LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n"); 2468 if (RunningGCD != 0) { 2469 Remainder = ConstDelta.srem(RunningGCD); 2470 LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n"); 2471 if (Remainder != 0) { 2472 unsigned Level = mapSrcLoop(CurLoop); 2473 Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ); 2474 Improved = true; 2475 } 2476 } 2477 } 2478 if (Improved) 2479 ++GCDsuccesses; 2480 LLVM_DEBUG(dbgs() << "all done\n"); 2481 return false; 2482 } 2483 2484 2485 //===----------------------------------------------------------------------===// 2486 // banerjeeMIVtest - 2487 // Use Banerjee's Inequalities to test an MIV subscript pair. 2488 // (Wolfe, in the race-car book, calls this the Extreme Value Test.) 2489 // Generally follows the discussion in Section 2.5.2 of 2490 // 2491 // Optimizing Supercompilers for Supercomputers 2492 // Michael Wolfe 2493 // 2494 // The inequalities given on page 25 are simplified in that loops are 2495 // normalized so that the lower bound is always 0 and the stride is always 1. 2496 // For example, Wolfe gives 2497 // 2498 // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k 2499 // 2500 // where A_k is the coefficient of the kth index in the source subscript, 2501 // B_k is the coefficient of the kth index in the destination subscript, 2502 // U_k is the upper bound of the kth index, L_k is the lower bound of the Kth 2503 // index, and N_k is the stride of the kth index. Since all loops are normalized 2504 // by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the 2505 // equation to 2506 // 2507 // LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1 2508 // = (A^-_k - B_k)^- (U_k - 1) - B_k 2509 // 2510 // Similar simplifications are possible for the other equations. 2511 // 2512 // When we can't determine the number of iterations for a loop, 2513 // we use NULL as an indicator for the worst case, infinity. 2514 // When computing the upper bound, NULL denotes +inf; 2515 // for the lower bound, NULL denotes -inf. 2516 // 2517 // Return true if dependence disproved. 2518 bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst, 2519 const SmallBitVector &Loops, 2520 FullDependence &Result) const { 2521 LLVM_DEBUG(dbgs() << "starting Banerjee\n"); 2522 ++BanerjeeApplications; 2523 LLVM_DEBUG(dbgs() << " Src = " << *Src << '\n'); 2524 const SCEV *A0; 2525 CoefficientInfo *A = collectCoeffInfo(Src, true, A0); 2526 LLVM_DEBUG(dbgs() << " Dst = " << *Dst << '\n'); 2527 const SCEV *B0; 2528 CoefficientInfo *B = collectCoeffInfo(Dst, false, B0); 2529 BoundInfo *Bound = new BoundInfo[MaxLevels + 1]; 2530 const SCEV *Delta = SE->getMinusSCEV(B0, A0); 2531 LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n'); 2532 2533 // Compute bounds for all the * directions. 2534 LLVM_DEBUG(dbgs() << "\tBounds[*]\n"); 2535 for (unsigned K = 1; K <= MaxLevels; ++K) { 2536 Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations; 2537 Bound[K].Direction = Dependence::DVEntry::ALL; 2538 Bound[K].DirSet = Dependence::DVEntry::NONE; 2539 findBoundsALL(A, B, Bound, K); 2540 #ifndef NDEBUG 2541 LLVM_DEBUG(dbgs() << "\t " << K << '\t'); 2542 if (Bound[K].Lower[Dependence::DVEntry::ALL]) 2543 LLVM_DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t'); 2544 else 2545 LLVM_DEBUG(dbgs() << "-inf\t"); 2546 if (Bound[K].Upper[Dependence::DVEntry::ALL]) 2547 LLVM_DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n'); 2548 else 2549 LLVM_DEBUG(dbgs() << "+inf\n"); 2550 #endif 2551 } 2552 2553 // Test the *, *, *, ... case. 2554 bool Disproved = false; 2555 if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) { 2556 // Explore the direction vector hierarchy. 2557 unsigned DepthExpanded = 0; 2558 unsigned NewDeps = exploreDirections(1, A, B, Bound, 2559 Loops, DepthExpanded, Delta); 2560 if (NewDeps > 0) { 2561 bool Improved = false; 2562 for (unsigned K = 1; K <= CommonLevels; ++K) { 2563 if (Loops[K]) { 2564 unsigned Old = Result.DV[K - 1].Direction; 2565 Result.DV[K - 1].Direction = Old & Bound[K].DirSet; 2566 Improved |= Old != Result.DV[K - 1].Direction; 2567 if (!Result.DV[K - 1].Direction) { 2568 Improved = false; 2569 Disproved = true; 2570 break; 2571 } 2572 } 2573 } 2574 if (Improved) 2575 ++BanerjeeSuccesses; 2576 } 2577 else { 2578 ++BanerjeeIndependence; 2579 Disproved = true; 2580 } 2581 } 2582 else { 2583 ++BanerjeeIndependence; 2584 Disproved = true; 2585 } 2586 delete [] Bound; 2587 delete [] A; 2588 delete [] B; 2589 return Disproved; 2590 } 2591 2592 2593 // Hierarchically expands the direction vector 2594 // search space, combining the directions of discovered dependences 2595 // in the DirSet field of Bound. Returns the number of distinct 2596 // dependences discovered. If the dependence is disproved, 2597 // it will return 0. 2598 unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A, 2599 CoefficientInfo *B, BoundInfo *Bound, 2600 const SmallBitVector &Loops, 2601 unsigned &DepthExpanded, 2602 const SCEV *Delta) const { 2603 if (Level > CommonLevels) { 2604 // record result 2605 LLVM_DEBUG(dbgs() << "\t["); 2606 for (unsigned K = 1; K <= CommonLevels; ++K) { 2607 if (Loops[K]) { 2608 Bound[K].DirSet |= Bound[K].Direction; 2609 #ifndef NDEBUG 2610 switch (Bound[K].Direction) { 2611 case Dependence::DVEntry::LT: 2612 LLVM_DEBUG(dbgs() << " <"); 2613 break; 2614 case Dependence::DVEntry::EQ: 2615 LLVM_DEBUG(dbgs() << " ="); 2616 break; 2617 case Dependence::DVEntry::GT: 2618 LLVM_DEBUG(dbgs() << " >"); 2619 break; 2620 case Dependence::DVEntry::ALL: 2621 LLVM_DEBUG(dbgs() << " *"); 2622 break; 2623 default: 2624 llvm_unreachable("unexpected Bound[K].Direction"); 2625 } 2626 #endif 2627 } 2628 } 2629 LLVM_DEBUG(dbgs() << " ]\n"); 2630 return 1; 2631 } 2632 if (Loops[Level]) { 2633 if (Level > DepthExpanded) { 2634 DepthExpanded = Level; 2635 // compute bounds for <, =, > at current level 2636 findBoundsLT(A, B, Bound, Level); 2637 findBoundsGT(A, B, Bound, Level); 2638 findBoundsEQ(A, B, Bound, Level); 2639 #ifndef NDEBUG 2640 LLVM_DEBUG(dbgs() << "\tBound for level = " << Level << '\n'); 2641 LLVM_DEBUG(dbgs() << "\t <\t"); 2642 if (Bound[Level].Lower[Dependence::DVEntry::LT]) 2643 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] 2644 << '\t'); 2645 else 2646 LLVM_DEBUG(dbgs() << "-inf\t"); 2647 if (Bound[Level].Upper[Dependence::DVEntry::LT]) 2648 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] 2649 << '\n'); 2650 else 2651 LLVM_DEBUG(dbgs() << "+inf\n"); 2652 LLVM_DEBUG(dbgs() << "\t =\t"); 2653 if (Bound[Level].Lower[Dependence::DVEntry::EQ]) 2654 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] 2655 << '\t'); 2656 else 2657 LLVM_DEBUG(dbgs() << "-inf\t"); 2658 if (Bound[Level].Upper[Dependence::DVEntry::EQ]) 2659 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] 2660 << '\n'); 2661 else 2662 LLVM_DEBUG(dbgs() << "+inf\n"); 2663 LLVM_DEBUG(dbgs() << "\t >\t"); 2664 if (Bound[Level].Lower[Dependence::DVEntry::GT]) 2665 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] 2666 << '\t'); 2667 else 2668 LLVM_DEBUG(dbgs() << "-inf\t"); 2669 if (Bound[Level].Upper[Dependence::DVEntry::GT]) 2670 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] 2671 << '\n'); 2672 else 2673 LLVM_DEBUG(dbgs() << "+inf\n"); 2674 #endif 2675 } 2676 2677 unsigned NewDeps = 0; 2678 2679 // test bounds for <, *, *, ... 2680 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta)) 2681 NewDeps += exploreDirections(Level + 1, A, B, Bound, 2682 Loops, DepthExpanded, Delta); 2683 2684 // Test bounds for =, *, *, ... 2685 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta)) 2686 NewDeps += exploreDirections(Level + 1, A, B, Bound, 2687 Loops, DepthExpanded, Delta); 2688 2689 // test bounds for >, *, *, ... 2690 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta)) 2691 NewDeps += exploreDirections(Level + 1, A, B, Bound, 2692 Loops, DepthExpanded, Delta); 2693 2694 Bound[Level].Direction = Dependence::DVEntry::ALL; 2695 return NewDeps; 2696 } 2697 else 2698 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta); 2699 } 2700 2701 2702 // Returns true iff the current bounds are plausible. 2703 bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level, 2704 BoundInfo *Bound, const SCEV *Delta) const { 2705 Bound[Level].Direction = DirKind; 2706 if (const SCEV *LowerBound = getLowerBound(Bound)) 2707 if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta)) 2708 return false; 2709 if (const SCEV *UpperBound = getUpperBound(Bound)) 2710 if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound)) 2711 return false; 2712 return true; 2713 } 2714 2715 2716 // Computes the upper and lower bounds for level K 2717 // using the * direction. Records them in Bound. 2718 // Wolfe gives the equations 2719 // 2720 // LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k 2721 // UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k 2722 // 2723 // Since we normalize loops, we can simplify these equations to 2724 // 2725 // LB^*_k = (A^-_k - B^+_k)U_k 2726 // UB^*_k = (A^+_k - B^-_k)U_k 2727 // 2728 // We must be careful to handle the case where the upper bound is unknown. 2729 // Note that the lower bound is always <= 0 2730 // and the upper bound is always >= 0. 2731 void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B, 2732 BoundInfo *Bound, unsigned K) const { 2733 Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity. 2734 Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity. 2735 if (Bound[K].Iterations) { 2736 Bound[K].Lower[Dependence::DVEntry::ALL] = 2737 SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), 2738 Bound[K].Iterations); 2739 Bound[K].Upper[Dependence::DVEntry::ALL] = 2740 SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), 2741 Bound[K].Iterations); 2742 } 2743 else { 2744 // If the difference is 0, we won't need to know the number of iterations. 2745 if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart)) 2746 Bound[K].Lower[Dependence::DVEntry::ALL] = 2747 SE->getZero(A[K].Coeff->getType()); 2748 if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart)) 2749 Bound[K].Upper[Dependence::DVEntry::ALL] = 2750 SE->getZero(A[K].Coeff->getType()); 2751 } 2752 } 2753 2754 2755 // Computes the upper and lower bounds for level K 2756 // using the = direction. Records them in Bound. 2757 // Wolfe gives the equations 2758 // 2759 // LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k 2760 // UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k 2761 // 2762 // Since we normalize loops, we can simplify these equations to 2763 // 2764 // LB^=_k = (A_k - B_k)^- U_k 2765 // UB^=_k = (A_k - B_k)^+ U_k 2766 // 2767 // We must be careful to handle the case where the upper bound is unknown. 2768 // Note that the lower bound is always <= 0 2769 // and the upper bound is always >= 0. 2770 void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B, 2771 BoundInfo *Bound, unsigned K) const { 2772 Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity. 2773 Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity. 2774 if (Bound[K].Iterations) { 2775 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); 2776 const SCEV *NegativePart = getNegativePart(Delta); 2777 Bound[K].Lower[Dependence::DVEntry::EQ] = 2778 SE->getMulExpr(NegativePart, Bound[K].Iterations); 2779 const SCEV *PositivePart = getPositivePart(Delta); 2780 Bound[K].Upper[Dependence::DVEntry::EQ] = 2781 SE->getMulExpr(PositivePart, Bound[K].Iterations); 2782 } 2783 else { 2784 // If the positive/negative part of the difference is 0, 2785 // we won't need to know the number of iterations. 2786 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); 2787 const SCEV *NegativePart = getNegativePart(Delta); 2788 if (NegativePart->isZero()) 2789 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero 2790 const SCEV *PositivePart = getPositivePart(Delta); 2791 if (PositivePart->isZero()) 2792 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero 2793 } 2794 } 2795 2796 2797 // Computes the upper and lower bounds for level K 2798 // using the < direction. Records them in Bound. 2799 // Wolfe gives the equations 2800 // 2801 // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k 2802 // UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k 2803 // 2804 // Since we normalize loops, we can simplify these equations to 2805 // 2806 // LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k 2807 // UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k 2808 // 2809 // We must be careful to handle the case where the upper bound is unknown. 2810 void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B, 2811 BoundInfo *Bound, unsigned K) const { 2812 Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity. 2813 Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity. 2814 if (Bound[K].Iterations) { 2815 const SCEV *Iter_1 = SE->getMinusSCEV( 2816 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); 2817 const SCEV *NegPart = 2818 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); 2819 Bound[K].Lower[Dependence::DVEntry::LT] = 2820 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff); 2821 const SCEV *PosPart = 2822 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); 2823 Bound[K].Upper[Dependence::DVEntry::LT] = 2824 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff); 2825 } 2826 else { 2827 // If the positive/negative part of the difference is 0, 2828 // we won't need to know the number of iterations. 2829 const SCEV *NegPart = 2830 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); 2831 if (NegPart->isZero()) 2832 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); 2833 const SCEV *PosPart = 2834 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff)); 2835 if (PosPart->isZero()) 2836 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff); 2837 } 2838 } 2839 2840 2841 // Computes the upper and lower bounds for level K 2842 // using the > direction. Records them in Bound. 2843 // Wolfe gives the equations 2844 // 2845 // LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k 2846 // UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k 2847 // 2848 // Since we normalize loops, we can simplify these equations to 2849 // 2850 // LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k 2851 // UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k 2852 // 2853 // We must be careful to handle the case where the upper bound is unknown. 2854 void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B, 2855 BoundInfo *Bound, unsigned K) const { 2856 Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity. 2857 Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity. 2858 if (Bound[K].Iterations) { 2859 const SCEV *Iter_1 = SE->getMinusSCEV( 2860 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); 2861 const SCEV *NegPart = 2862 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); 2863 Bound[K].Lower[Dependence::DVEntry::GT] = 2864 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff); 2865 const SCEV *PosPart = 2866 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); 2867 Bound[K].Upper[Dependence::DVEntry::GT] = 2868 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff); 2869 } 2870 else { 2871 // If the positive/negative part of the difference is 0, 2872 // we won't need to know the number of iterations. 2873 const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); 2874 if (NegPart->isZero()) 2875 Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff; 2876 const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart)); 2877 if (PosPart->isZero()) 2878 Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff; 2879 } 2880 } 2881 2882 2883 // X^+ = max(X, 0) 2884 const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const { 2885 return SE->getSMaxExpr(X, SE->getZero(X->getType())); 2886 } 2887 2888 2889 // X^- = min(X, 0) 2890 const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const { 2891 return SE->getSMinExpr(X, SE->getZero(X->getType())); 2892 } 2893 2894 2895 // Walks through the subscript, 2896 // collecting each coefficient, the associated loop bounds, 2897 // and recording its positive and negative parts for later use. 2898 DependenceInfo::CoefficientInfo * 2899 DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag, 2900 const SCEV *&Constant) const { 2901 const SCEV *Zero = SE->getZero(Subscript->getType()); 2902 CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1]; 2903 for (unsigned K = 1; K <= MaxLevels; ++K) { 2904 CI[K].Coeff = Zero; 2905 CI[K].PosPart = Zero; 2906 CI[K].NegPart = Zero; 2907 CI[K].Iterations = nullptr; 2908 } 2909 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) { 2910 const Loop *L = AddRec->getLoop(); 2911 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L); 2912 CI[K].Coeff = AddRec->getStepRecurrence(*SE); 2913 CI[K].PosPart = getPositivePart(CI[K].Coeff); 2914 CI[K].NegPart = getNegativePart(CI[K].Coeff); 2915 CI[K].Iterations = collectUpperBound(L, Subscript->getType()); 2916 Subscript = AddRec->getStart(); 2917 } 2918 Constant = Subscript; 2919 #ifndef NDEBUG 2920 LLVM_DEBUG(dbgs() << "\tCoefficient Info\n"); 2921 for (unsigned K = 1; K <= MaxLevels; ++K) { 2922 LLVM_DEBUG(dbgs() << "\t " << K << "\t" << *CI[K].Coeff); 2923 LLVM_DEBUG(dbgs() << "\tPos Part = "); 2924 LLVM_DEBUG(dbgs() << *CI[K].PosPart); 2925 LLVM_DEBUG(dbgs() << "\tNeg Part = "); 2926 LLVM_DEBUG(dbgs() << *CI[K].NegPart); 2927 LLVM_DEBUG(dbgs() << "\tUpper Bound = "); 2928 if (CI[K].Iterations) 2929 LLVM_DEBUG(dbgs() << *CI[K].Iterations); 2930 else 2931 LLVM_DEBUG(dbgs() << "+inf"); 2932 LLVM_DEBUG(dbgs() << '\n'); 2933 } 2934 LLVM_DEBUG(dbgs() << "\t Constant = " << *Subscript << '\n'); 2935 #endif 2936 return CI; 2937 } 2938 2939 2940 // Looks through all the bounds info and 2941 // computes the lower bound given the current direction settings 2942 // at each level. If the lower bound for any level is -inf, 2943 // the result is -inf. 2944 const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const { 2945 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction]; 2946 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) { 2947 if (Bound[K].Lower[Bound[K].Direction]) 2948 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]); 2949 else 2950 Sum = nullptr; 2951 } 2952 return Sum; 2953 } 2954 2955 2956 // Looks through all the bounds info and 2957 // computes the upper bound given the current direction settings 2958 // at each level. If the upper bound at any level is +inf, 2959 // the result is +inf. 2960 const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const { 2961 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction]; 2962 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) { 2963 if (Bound[K].Upper[Bound[K].Direction]) 2964 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]); 2965 else 2966 Sum = nullptr; 2967 } 2968 return Sum; 2969 } 2970 2971 2972 //===----------------------------------------------------------------------===// 2973 // Constraint manipulation for Delta test. 2974 2975 // Given a linear SCEV, 2976 // return the coefficient (the step) 2977 // corresponding to the specified loop. 2978 // If there isn't one, return 0. 2979 // For example, given a*i + b*j + c*k, finding the coefficient 2980 // corresponding to the j loop would yield b. 2981 const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr, 2982 const Loop *TargetLoop) const { 2983 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); 2984 if (!AddRec) 2985 return SE->getZero(Expr->getType()); 2986 if (AddRec->getLoop() == TargetLoop) 2987 return AddRec->getStepRecurrence(*SE); 2988 return findCoefficient(AddRec->getStart(), TargetLoop); 2989 } 2990 2991 2992 // Given a linear SCEV, 2993 // return the SCEV given by zeroing out the coefficient 2994 // corresponding to the specified loop. 2995 // For example, given a*i + b*j + c*k, zeroing the coefficient 2996 // corresponding to the j loop would yield a*i + c*k. 2997 const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr, 2998 const Loop *TargetLoop) const { 2999 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); 3000 if (!AddRec) 3001 return Expr; // ignore 3002 if (AddRec->getLoop() == TargetLoop) 3003 return AddRec->getStart(); 3004 return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop), 3005 AddRec->getStepRecurrence(*SE), 3006 AddRec->getLoop(), 3007 AddRec->getNoWrapFlags()); 3008 } 3009 3010 3011 // Given a linear SCEV Expr, 3012 // return the SCEV given by adding some Value to the 3013 // coefficient corresponding to the specified TargetLoop. 3014 // For example, given a*i + b*j + c*k, adding 1 to the coefficient 3015 // corresponding to the j loop would yield a*i + (b+1)*j + c*k. 3016 const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr, 3017 const Loop *TargetLoop, 3018 const SCEV *Value) const { 3019 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); 3020 if (!AddRec) // create a new addRec 3021 return SE->getAddRecExpr(Expr, 3022 Value, 3023 TargetLoop, 3024 SCEV::FlagAnyWrap); // Worst case, with no info. 3025 if (AddRec->getLoop() == TargetLoop) { 3026 const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value); 3027 if (Sum->isZero()) 3028 return AddRec->getStart(); 3029 return SE->getAddRecExpr(AddRec->getStart(), 3030 Sum, 3031 AddRec->getLoop(), 3032 AddRec->getNoWrapFlags()); 3033 } 3034 if (SE->isLoopInvariant(AddRec, TargetLoop)) 3035 return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap); 3036 return SE->getAddRecExpr( 3037 addToCoefficient(AddRec->getStart(), TargetLoop, Value), 3038 AddRec->getStepRecurrence(*SE), AddRec->getLoop(), 3039 AddRec->getNoWrapFlags()); 3040 } 3041 3042 3043 // Review the constraints, looking for opportunities 3044 // to simplify a subscript pair (Src and Dst). 3045 // Return true if some simplification occurs. 3046 // If the simplification isn't exact (that is, if it is conservative 3047 // in terms of dependence), set consistent to false. 3048 // Corresponds to Figure 5 from the paper 3049 // 3050 // Practical Dependence Testing 3051 // Goff, Kennedy, Tseng 3052 // PLDI 1991 3053 bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst, 3054 SmallBitVector &Loops, 3055 SmallVectorImpl<Constraint> &Constraints, 3056 bool &Consistent) { 3057 bool Result = false; 3058 for (unsigned LI : Loops.set_bits()) { 3059 LLVM_DEBUG(dbgs() << "\t Constraint[" << LI << "] is"); 3060 LLVM_DEBUG(Constraints[LI].dump(dbgs())); 3061 if (Constraints[LI].isDistance()) 3062 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent); 3063 else if (Constraints[LI].isLine()) 3064 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent); 3065 else if (Constraints[LI].isPoint()) 3066 Result |= propagatePoint(Src, Dst, Constraints[LI]); 3067 } 3068 return Result; 3069 } 3070 3071 3072 // Attempt to propagate a distance 3073 // constraint into a subscript pair (Src and Dst). 3074 // Return true if some simplification occurs. 3075 // If the simplification isn't exact (that is, if it is conservative 3076 // in terms of dependence), set consistent to false. 3077 bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst, 3078 Constraint &CurConstraint, 3079 bool &Consistent) { 3080 const Loop *CurLoop = CurConstraint.getAssociatedLoop(); 3081 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n"); 3082 const SCEV *A_K = findCoefficient(Src, CurLoop); 3083 if (A_K->isZero()) 3084 return false; 3085 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD()); 3086 Src = SE->getMinusSCEV(Src, DA_K); 3087 Src = zeroCoefficient(Src, CurLoop); 3088 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n"); 3089 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n"); 3090 Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K)); 3091 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n"); 3092 if (!findCoefficient(Dst, CurLoop)->isZero()) 3093 Consistent = false; 3094 return true; 3095 } 3096 3097 3098 // Attempt to propagate a line 3099 // constraint into a subscript pair (Src and Dst). 3100 // Return true if some simplification occurs. 3101 // If the simplification isn't exact (that is, if it is conservative 3102 // in terms of dependence), set consistent to false. 3103 bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst, 3104 Constraint &CurConstraint, 3105 bool &Consistent) { 3106 const Loop *CurLoop = CurConstraint.getAssociatedLoop(); 3107 const SCEV *A = CurConstraint.getA(); 3108 const SCEV *B = CurConstraint.getB(); 3109 const SCEV *C = CurConstraint.getC(); 3110 LLVM_DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C 3111 << "\n"); 3112 LLVM_DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n"); 3113 LLVM_DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n"); 3114 if (A->isZero()) { 3115 const SCEVConstant *Bconst = dyn_cast<SCEVConstant>(B); 3116 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C); 3117 if (!Bconst || !Cconst) return false; 3118 APInt Beta = Bconst->getAPInt(); 3119 APInt Charlie = Cconst->getAPInt(); 3120 APInt CdivB = Charlie.sdiv(Beta); 3121 assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B"); 3122 const SCEV *AP_K = findCoefficient(Dst, CurLoop); 3123 // Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); 3124 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB))); 3125 Dst = zeroCoefficient(Dst, CurLoop); 3126 if (!findCoefficient(Src, CurLoop)->isZero()) 3127 Consistent = false; 3128 } 3129 else if (B->isZero()) { 3130 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A); 3131 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C); 3132 if (!Aconst || !Cconst) return false; 3133 APInt Alpha = Aconst->getAPInt(); 3134 APInt Charlie = Cconst->getAPInt(); 3135 APInt CdivA = Charlie.sdiv(Alpha); 3136 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A"); 3137 const SCEV *A_K = findCoefficient(Src, CurLoop); 3138 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); 3139 Src = zeroCoefficient(Src, CurLoop); 3140 if (!findCoefficient(Dst, CurLoop)->isZero()) 3141 Consistent = false; 3142 } 3143 else if (isKnownPredicate(CmpInst::ICMP_EQ, A, B)) { 3144 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A); 3145 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C); 3146 if (!Aconst || !Cconst) return false; 3147 APInt Alpha = Aconst->getAPInt(); 3148 APInt Charlie = Cconst->getAPInt(); 3149 APInt CdivA = Charlie.sdiv(Alpha); 3150 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A"); 3151 const SCEV *A_K = findCoefficient(Src, CurLoop); 3152 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA))); 3153 Src = zeroCoefficient(Src, CurLoop); 3154 Dst = addToCoefficient(Dst, CurLoop, A_K); 3155 if (!findCoefficient(Dst, CurLoop)->isZero()) 3156 Consistent = false; 3157 } 3158 else { 3159 // paper is incorrect here, or perhaps just misleading 3160 const SCEV *A_K = findCoefficient(Src, CurLoop); 3161 Src = SE->getMulExpr(Src, A); 3162 Dst = SE->getMulExpr(Dst, A); 3163 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C)); 3164 Src = zeroCoefficient(Src, CurLoop); 3165 Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B)); 3166 if (!findCoefficient(Dst, CurLoop)->isZero()) 3167 Consistent = false; 3168 } 3169 LLVM_DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n"); 3170 LLVM_DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n"); 3171 return true; 3172 } 3173 3174 3175 // Attempt to propagate a point 3176 // constraint into a subscript pair (Src and Dst). 3177 // Return true if some simplification occurs. 3178 bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst, 3179 Constraint &CurConstraint) { 3180 const Loop *CurLoop = CurConstraint.getAssociatedLoop(); 3181 const SCEV *A_K = findCoefficient(Src, CurLoop); 3182 const SCEV *AP_K = findCoefficient(Dst, CurLoop); 3183 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX()); 3184 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY()); 3185 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n"); 3186 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K)); 3187 Src = zeroCoefficient(Src, CurLoop); 3188 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n"); 3189 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n"); 3190 Dst = zeroCoefficient(Dst, CurLoop); 3191 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n"); 3192 return true; 3193 } 3194 3195 3196 // Update direction vector entry based on the current constraint. 3197 void DependenceInfo::updateDirection(Dependence::DVEntry &Level, 3198 const Constraint &CurConstraint) const { 3199 LLVM_DEBUG(dbgs() << "\tUpdate direction, constraint ="); 3200 LLVM_DEBUG(CurConstraint.dump(dbgs())); 3201 if (CurConstraint.isAny()) 3202 ; // use defaults 3203 else if (CurConstraint.isDistance()) { 3204 // this one is consistent, the others aren't 3205 Level.Scalar = false; 3206 Level.Distance = CurConstraint.getD(); 3207 unsigned NewDirection = Dependence::DVEntry::NONE; 3208 if (!SE->isKnownNonZero(Level.Distance)) // if may be zero 3209 NewDirection = Dependence::DVEntry::EQ; 3210 if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive 3211 NewDirection |= Dependence::DVEntry::LT; 3212 if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative 3213 NewDirection |= Dependence::DVEntry::GT; 3214 Level.Direction &= NewDirection; 3215 } 3216 else if (CurConstraint.isLine()) { 3217 Level.Scalar = false; 3218 Level.Distance = nullptr; 3219 // direction should be accurate 3220 } 3221 else if (CurConstraint.isPoint()) { 3222 Level.Scalar = false; 3223 Level.Distance = nullptr; 3224 unsigned NewDirection = Dependence::DVEntry::NONE; 3225 if (!isKnownPredicate(CmpInst::ICMP_NE, 3226 CurConstraint.getY(), 3227 CurConstraint.getX())) 3228 // if X may be = Y 3229 NewDirection |= Dependence::DVEntry::EQ; 3230 if (!isKnownPredicate(CmpInst::ICMP_SLE, 3231 CurConstraint.getY(), 3232 CurConstraint.getX())) 3233 // if Y may be > X 3234 NewDirection |= Dependence::DVEntry::LT; 3235 if (!isKnownPredicate(CmpInst::ICMP_SGE, 3236 CurConstraint.getY(), 3237 CurConstraint.getX())) 3238 // if Y may be < X 3239 NewDirection |= Dependence::DVEntry::GT; 3240 Level.Direction &= NewDirection; 3241 } 3242 else 3243 llvm_unreachable("constraint has unexpected kind"); 3244 } 3245 3246 /// Check if we can delinearize the subscripts. If the SCEVs representing the 3247 /// source and destination array references are recurrences on a nested loop, 3248 /// this function flattens the nested recurrences into separate recurrences 3249 /// for each loop level. 3250 bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst, 3251 SmallVectorImpl<Subscript> &Pair) { 3252 assert(isLoadOrStore(Src) && "instruction is not load or store"); 3253 assert(isLoadOrStore(Dst) && "instruction is not load or store"); 3254 Value *SrcPtr = getLoadStorePointerOperand(Src); 3255 Value *DstPtr = getLoadStorePointerOperand(Dst); 3256 3257 Loop *SrcLoop = LI->getLoopFor(Src->getParent()); 3258 Loop *DstLoop = LI->getLoopFor(Dst->getParent()); 3259 3260 // Below code mimics the code in Delinearization.cpp 3261 const SCEV *SrcAccessFn = 3262 SE->getSCEVAtScope(SrcPtr, SrcLoop); 3263 const SCEV *DstAccessFn = 3264 SE->getSCEVAtScope(DstPtr, DstLoop); 3265 3266 const SCEVUnknown *SrcBase = 3267 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn)); 3268 const SCEVUnknown *DstBase = 3269 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn)); 3270 3271 if (!SrcBase || !DstBase || SrcBase != DstBase) 3272 return false; 3273 3274 const SCEV *ElementSize = SE->getElementSize(Src); 3275 if (ElementSize != SE->getElementSize(Dst)) 3276 return false; 3277 3278 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase); 3279 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase); 3280 3281 const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV); 3282 const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV); 3283 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine()) 3284 return false; 3285 3286 // First step: collect parametric terms in both array references. 3287 SmallVector<const SCEV *, 4> Terms; 3288 SE->collectParametricTerms(SrcAR, Terms); 3289 SE->collectParametricTerms(DstAR, Terms); 3290 3291 // Second step: find subscript sizes. 3292 SmallVector<const SCEV *, 4> Sizes; 3293 SE->findArrayDimensions(Terms, Sizes, ElementSize); 3294 3295 // Third step: compute the access functions for each subscript. 3296 SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts; 3297 SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes); 3298 SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes); 3299 3300 // Fail when there is only a subscript: that's a linearized access function. 3301 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 || 3302 SrcSubscripts.size() != DstSubscripts.size()) 3303 return false; 3304 3305 int size = SrcSubscripts.size(); 3306 3307 // Statically check that the array bounds are in-range. The first subscript we 3308 // don't have a size for and it cannot overflow into another subscript, so is 3309 // always safe. The others need to be 0 <= subscript[i] < bound, for both src 3310 // and dst. 3311 // FIXME: It may be better to record these sizes and add them as constraints 3312 // to the dependency checks. 3313 for (int i = 1; i < size; ++i) { 3314 if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr)) 3315 return false; 3316 3317 if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1])) 3318 return false; 3319 3320 if (!isKnownNonNegative(DstSubscripts[i], DstPtr)) 3321 return false; 3322 3323 if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1])) 3324 return false; 3325 } 3326 3327 LLVM_DEBUG({ 3328 dbgs() << "\nSrcSubscripts: "; 3329 for (int i = 0; i < size; i++) 3330 dbgs() << *SrcSubscripts[i]; 3331 dbgs() << "\nDstSubscripts: "; 3332 for (int i = 0; i < size; i++) 3333 dbgs() << *DstSubscripts[i]; 3334 }); 3335 3336 // The delinearization transforms a single-subscript MIV dependence test into 3337 // a multi-subscript SIV dependence test that is easier to compute. So we 3338 // resize Pair to contain as many pairs of subscripts as the delinearization 3339 // has found, and then initialize the pairs following the delinearization. 3340 Pair.resize(size); 3341 for (int i = 0; i < size; ++i) { 3342 Pair[i].Src = SrcSubscripts[i]; 3343 Pair[i].Dst = DstSubscripts[i]; 3344 unifySubscriptType(&Pair[i]); 3345 } 3346 3347 return true; 3348 } 3349 3350 //===----------------------------------------------------------------------===// 3351 3352 #ifndef NDEBUG 3353 // For debugging purposes, dump a small bit vector to dbgs(). 3354 static void dumpSmallBitVector(SmallBitVector &BV) { 3355 dbgs() << "{"; 3356 for (unsigned VI : BV.set_bits()) { 3357 dbgs() << VI; 3358 if (BV.find_next(VI) >= 0) 3359 dbgs() << ' '; 3360 } 3361 dbgs() << "}\n"; 3362 } 3363 #endif 3364 3365 // depends - 3366 // Returns NULL if there is no dependence. 3367 // Otherwise, return a Dependence with as many details as possible. 3368 // Corresponds to Section 3.1 in the paper 3369 // 3370 // Practical Dependence Testing 3371 // Goff, Kennedy, Tseng 3372 // PLDI 1991 3373 // 3374 // Care is required to keep the routine below, getSplitIteration(), 3375 // up to date with respect to this routine. 3376 std::unique_ptr<Dependence> 3377 DependenceInfo::depends(Instruction *Src, Instruction *Dst, 3378 bool PossiblyLoopIndependent) { 3379 if (Src == Dst) 3380 PossiblyLoopIndependent = false; 3381 3382 if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) || 3383 (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory())) 3384 // if both instructions don't reference memory, there's no dependence 3385 return nullptr; 3386 3387 if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) { 3388 // can only analyze simple loads and stores, i.e., no calls, invokes, etc. 3389 LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n"); 3390 return make_unique<Dependence>(Src, Dst); 3391 } 3392 3393 assert(isLoadOrStore(Src) && "instruction is not load or store"); 3394 assert(isLoadOrStore(Dst) && "instruction is not load or store"); 3395 Value *SrcPtr = getLoadStorePointerOperand(Src); 3396 Value *DstPtr = getLoadStorePointerOperand(Dst); 3397 3398 switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), 3399 MemoryLocation::get(Dst), 3400 MemoryLocation::get(Src))) { 3401 case MayAlias: 3402 case PartialAlias: 3403 // cannot analyse objects if we don't understand their aliasing. 3404 LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n"); 3405 return make_unique<Dependence>(Src, Dst); 3406 case NoAlias: 3407 // If the objects noalias, they are distinct, accesses are independent. 3408 LLVM_DEBUG(dbgs() << "no alias\n"); 3409 return nullptr; 3410 case MustAlias: 3411 break; // The underlying objects alias; test accesses for dependence. 3412 } 3413 3414 // establish loop nesting levels 3415 establishNestingLevels(Src, Dst); 3416 LLVM_DEBUG(dbgs() << " common nesting levels = " << CommonLevels << "\n"); 3417 LLVM_DEBUG(dbgs() << " maximum nesting levels = " << MaxLevels << "\n"); 3418 3419 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels); 3420 ++TotalArrayPairs; 3421 3422 unsigned Pairs = 1; 3423 SmallVector<Subscript, 2> Pair(Pairs); 3424 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); 3425 const SCEV *DstSCEV = SE->getSCEV(DstPtr); 3426 LLVM_DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n"); 3427 LLVM_DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n"); 3428 Pair[0].Src = SrcSCEV; 3429 Pair[0].Dst = DstSCEV; 3430 3431 if (Delinearize) { 3432 if (tryDelinearize(Src, Dst, Pair)) { 3433 LLVM_DEBUG(dbgs() << " delinearized\n"); 3434 Pairs = Pair.size(); 3435 } 3436 } 3437 3438 for (unsigned P = 0; P < Pairs; ++P) { 3439 Pair[P].Loops.resize(MaxLevels + 1); 3440 Pair[P].GroupLoops.resize(MaxLevels + 1); 3441 Pair[P].Group.resize(Pairs); 3442 removeMatchingExtensions(&Pair[P]); 3443 Pair[P].Classification = 3444 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), 3445 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), 3446 Pair[P].Loops); 3447 Pair[P].GroupLoops = Pair[P].Loops; 3448 Pair[P].Group.set(P); 3449 LLVM_DEBUG(dbgs() << " subscript " << P << "\n"); 3450 LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n"); 3451 LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n"); 3452 LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n"); 3453 LLVM_DEBUG(dbgs() << "\tloops = "); 3454 LLVM_DEBUG(dumpSmallBitVector(Pair[P].Loops)); 3455 } 3456 3457 SmallBitVector Separable(Pairs); 3458 SmallBitVector Coupled(Pairs); 3459 3460 // Partition subscripts into separable and minimally-coupled groups 3461 // Algorithm in paper is algorithmically better; 3462 // this may be faster in practice. Check someday. 3463 // 3464 // Here's an example of how it works. Consider this code: 3465 // 3466 // for (i = ...) { 3467 // for (j = ...) { 3468 // for (k = ...) { 3469 // for (l = ...) { 3470 // for (m = ...) { 3471 // A[i][j][k][m] = ...; 3472 // ... = A[0][j][l][i + j]; 3473 // } 3474 // } 3475 // } 3476 // } 3477 // } 3478 // 3479 // There are 4 subscripts here: 3480 // 0 [i] and [0] 3481 // 1 [j] and [j] 3482 // 2 [k] and [l] 3483 // 3 [m] and [i + j] 3484 // 3485 // We've already classified each subscript pair as ZIV, SIV, etc., 3486 // and collected all the loops mentioned by pair P in Pair[P].Loops. 3487 // In addition, we've initialized Pair[P].GroupLoops to Pair[P].Loops 3488 // and set Pair[P].Group = {P}. 3489 // 3490 // Src Dst Classification Loops GroupLoops Group 3491 // 0 [i] [0] SIV {1} {1} {0} 3492 // 1 [j] [j] SIV {2} {2} {1} 3493 // 2 [k] [l] RDIV {3,4} {3,4} {2} 3494 // 3 [m] [i + j] MIV {1,2,5} {1,2,5} {3} 3495 // 3496 // For each subscript SI 0 .. 3, we consider each remaining subscript, SJ. 3497 // So, 0 is compared against 1, 2, and 3; 1 is compared against 2 and 3, etc. 3498 // 3499 // We begin by comparing 0 and 1. The intersection of the GroupLoops is empty. 3500 // Next, 0 and 2. Again, the intersection of their GroupLoops is empty. 3501 // Next 0 and 3. The intersection of their GroupLoop = {1}, not empty, 3502 // so Pair[3].Group = {0,3} and Done = false (that is, 0 will not be added 3503 // to either Separable or Coupled). 3504 // 3505 // Next, we consider 1 and 2. The intersection of the GroupLoops is empty. 3506 // Next, 1 and 3. The intersectionof their GroupLoops = {2}, not empty, 3507 // so Pair[3].Group = {0, 1, 3} and Done = false. 3508 // 3509 // Next, we compare 2 against 3. The intersection of the GroupLoops is empty. 3510 // Since Done remains true, we add 2 to the set of Separable pairs. 3511 // 3512 // Finally, we consider 3. There's nothing to compare it with, 3513 // so Done remains true and we add it to the Coupled set. 3514 // Pair[3].Group = {0, 1, 3} and GroupLoops = {1, 2, 5}. 3515 // 3516 // In the end, we've got 1 separable subscript and 1 coupled group. 3517 for (unsigned SI = 0; SI < Pairs; ++SI) { 3518 if (Pair[SI].Classification == Subscript::NonLinear) { 3519 // ignore these, but collect loops for later 3520 ++NonlinearSubscriptPairs; 3521 collectCommonLoops(Pair[SI].Src, 3522 LI->getLoopFor(Src->getParent()), 3523 Pair[SI].Loops); 3524 collectCommonLoops(Pair[SI].Dst, 3525 LI->getLoopFor(Dst->getParent()), 3526 Pair[SI].Loops); 3527 Result.Consistent = false; 3528 } else if (Pair[SI].Classification == Subscript::ZIV) { 3529 // always separable 3530 Separable.set(SI); 3531 } 3532 else { 3533 // SIV, RDIV, or MIV, so check for coupled group 3534 bool Done = true; 3535 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) { 3536 SmallBitVector Intersection = Pair[SI].GroupLoops; 3537 Intersection &= Pair[SJ].GroupLoops; 3538 if (Intersection.any()) { 3539 // accumulate set of all the loops in group 3540 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops; 3541 // accumulate set of all subscripts in group 3542 Pair[SJ].Group |= Pair[SI].Group; 3543 Done = false; 3544 } 3545 } 3546 if (Done) { 3547 if (Pair[SI].Group.count() == 1) { 3548 Separable.set(SI); 3549 ++SeparableSubscriptPairs; 3550 } 3551 else { 3552 Coupled.set(SI); 3553 ++CoupledSubscriptPairs; 3554 } 3555 } 3556 } 3557 } 3558 3559 LLVM_DEBUG(dbgs() << " Separable = "); 3560 LLVM_DEBUG(dumpSmallBitVector(Separable)); 3561 LLVM_DEBUG(dbgs() << " Coupled = "); 3562 LLVM_DEBUG(dumpSmallBitVector(Coupled)); 3563 3564 Constraint NewConstraint; 3565 NewConstraint.setAny(SE); 3566 3567 // test separable subscripts 3568 for (unsigned SI : Separable.set_bits()) { 3569 LLVM_DEBUG(dbgs() << "testing subscript " << SI); 3570 switch (Pair[SI].Classification) { 3571 case Subscript::ZIV: 3572 LLVM_DEBUG(dbgs() << ", ZIV\n"); 3573 if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result)) 3574 return nullptr; 3575 break; 3576 case Subscript::SIV: { 3577 LLVM_DEBUG(dbgs() << ", SIV\n"); 3578 unsigned Level; 3579 const SCEV *SplitIter = nullptr; 3580 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint, 3581 SplitIter)) 3582 return nullptr; 3583 break; 3584 } 3585 case Subscript::RDIV: 3586 LLVM_DEBUG(dbgs() << ", RDIV\n"); 3587 if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result)) 3588 return nullptr; 3589 break; 3590 case Subscript::MIV: 3591 LLVM_DEBUG(dbgs() << ", MIV\n"); 3592 if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result)) 3593 return nullptr; 3594 break; 3595 default: 3596 llvm_unreachable("subscript has unexpected classification"); 3597 } 3598 } 3599 3600 if (Coupled.count()) { 3601 // test coupled subscript groups 3602 LLVM_DEBUG(dbgs() << "starting on coupled subscripts\n"); 3603 LLVM_DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n"); 3604 SmallVector<Constraint, 4> Constraints(MaxLevels + 1); 3605 for (unsigned II = 0; II <= MaxLevels; ++II) 3606 Constraints[II].setAny(SE); 3607 for (unsigned SI : Coupled.set_bits()) { 3608 LLVM_DEBUG(dbgs() << "testing subscript group " << SI << " { "); 3609 SmallBitVector Group(Pair[SI].Group); 3610 SmallBitVector Sivs(Pairs); 3611 SmallBitVector Mivs(Pairs); 3612 SmallBitVector ConstrainedLevels(MaxLevels + 1); 3613 SmallVector<Subscript *, 4> PairsInGroup; 3614 for (unsigned SJ : Group.set_bits()) { 3615 LLVM_DEBUG(dbgs() << SJ << " "); 3616 if (Pair[SJ].Classification == Subscript::SIV) 3617 Sivs.set(SJ); 3618 else 3619 Mivs.set(SJ); 3620 PairsInGroup.push_back(&Pair[SJ]); 3621 } 3622 unifySubscriptType(PairsInGroup); 3623 LLVM_DEBUG(dbgs() << "}\n"); 3624 while (Sivs.any()) { 3625 bool Changed = false; 3626 for (unsigned SJ : Sivs.set_bits()) { 3627 LLVM_DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n"); 3628 // SJ is an SIV subscript that's part of the current coupled group 3629 unsigned Level; 3630 const SCEV *SplitIter = nullptr; 3631 LLVM_DEBUG(dbgs() << "SIV\n"); 3632 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint, 3633 SplitIter)) 3634 return nullptr; 3635 ConstrainedLevels.set(Level); 3636 if (intersectConstraints(&Constraints[Level], &NewConstraint)) { 3637 if (Constraints[Level].isEmpty()) { 3638 ++DeltaIndependence; 3639 return nullptr; 3640 } 3641 Changed = true; 3642 } 3643 Sivs.reset(SJ); 3644 } 3645 if (Changed) { 3646 // propagate, possibly creating new SIVs and ZIVs 3647 LLVM_DEBUG(dbgs() << " propagating\n"); 3648 LLVM_DEBUG(dbgs() << "\tMivs = "); 3649 LLVM_DEBUG(dumpSmallBitVector(Mivs)); 3650 for (unsigned SJ : Mivs.set_bits()) { 3651 // SJ is an MIV subscript that's part of the current coupled group 3652 LLVM_DEBUG(dbgs() << "\tSJ = " << SJ << "\n"); 3653 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, 3654 Constraints, Result.Consistent)) { 3655 LLVM_DEBUG(dbgs() << "\t Changed\n"); 3656 ++DeltaPropagations; 3657 Pair[SJ].Classification = 3658 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), 3659 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), 3660 Pair[SJ].Loops); 3661 switch (Pair[SJ].Classification) { 3662 case Subscript::ZIV: 3663 LLVM_DEBUG(dbgs() << "ZIV\n"); 3664 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) 3665 return nullptr; 3666 Mivs.reset(SJ); 3667 break; 3668 case Subscript::SIV: 3669 Sivs.set(SJ); 3670 Mivs.reset(SJ); 3671 break; 3672 case Subscript::RDIV: 3673 case Subscript::MIV: 3674 break; 3675 default: 3676 llvm_unreachable("bad subscript classification"); 3677 } 3678 } 3679 } 3680 } 3681 } 3682 3683 // test & propagate remaining RDIVs 3684 for (unsigned SJ : Mivs.set_bits()) { 3685 if (Pair[SJ].Classification == Subscript::RDIV) { 3686 LLVM_DEBUG(dbgs() << "RDIV test\n"); 3687 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) 3688 return nullptr; 3689 // I don't yet understand how to propagate RDIV results 3690 Mivs.reset(SJ); 3691 } 3692 } 3693 3694 // test remaining MIVs 3695 // This code is temporary. 3696 // Better to somehow test all remaining subscripts simultaneously. 3697 for (unsigned SJ : Mivs.set_bits()) { 3698 if (Pair[SJ].Classification == Subscript::MIV) { 3699 LLVM_DEBUG(dbgs() << "MIV test\n"); 3700 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result)) 3701 return nullptr; 3702 } 3703 else 3704 llvm_unreachable("expected only MIV subscripts at this point"); 3705 } 3706 3707 // update Result.DV from constraint vector 3708 LLVM_DEBUG(dbgs() << " updating\n"); 3709 for (unsigned SJ : ConstrainedLevels.set_bits()) { 3710 if (SJ > CommonLevels) 3711 break; 3712 updateDirection(Result.DV[SJ - 1], Constraints[SJ]); 3713 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) 3714 return nullptr; 3715 } 3716 } 3717 } 3718 3719 // Make sure the Scalar flags are set correctly. 3720 SmallBitVector CompleteLoops(MaxLevels + 1); 3721 for (unsigned SI = 0; SI < Pairs; ++SI) 3722 CompleteLoops |= Pair[SI].Loops; 3723 for (unsigned II = 1; II <= CommonLevels; ++II) 3724 if (CompleteLoops[II]) 3725 Result.DV[II - 1].Scalar = false; 3726 3727 if (PossiblyLoopIndependent) { 3728 // Make sure the LoopIndependent flag is set correctly. 3729 // All directions must include equal, otherwise no 3730 // loop-independent dependence is possible. 3731 for (unsigned II = 1; II <= CommonLevels; ++II) { 3732 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) { 3733 Result.LoopIndependent = false; 3734 break; 3735 } 3736 } 3737 } 3738 else { 3739 // On the other hand, if all directions are equal and there's no 3740 // loop-independent dependence possible, then no dependence exists. 3741 bool AllEqual = true; 3742 for (unsigned II = 1; II <= CommonLevels; ++II) { 3743 if (Result.getDirection(II) != Dependence::DVEntry::EQ) { 3744 AllEqual = false; 3745 break; 3746 } 3747 } 3748 if (AllEqual) 3749 return nullptr; 3750 } 3751 3752 return make_unique<FullDependence>(std::move(Result)); 3753 } 3754 3755 3756 3757 //===----------------------------------------------------------------------===// 3758 // getSplitIteration - 3759 // Rather than spend rarely-used space recording the splitting iteration 3760 // during the Weak-Crossing SIV test, we re-compute it on demand. 3761 // The re-computation is basically a repeat of the entire dependence test, 3762 // though simplified since we know that the dependence exists. 3763 // It's tedious, since we must go through all propagations, etc. 3764 // 3765 // Care is required to keep this code up to date with respect to the routine 3766 // above, depends(). 3767 // 3768 // Generally, the dependence analyzer will be used to build 3769 // a dependence graph for a function (basically a map from instructions 3770 // to dependences). Looking for cycles in the graph shows us loops 3771 // that cannot be trivially vectorized/parallelized. 3772 // 3773 // We can try to improve the situation by examining all the dependences 3774 // that make up the cycle, looking for ones we can break. 3775 // Sometimes, peeling the first or last iteration of a loop will break 3776 // dependences, and we've got flags for those possibilities. 3777 // Sometimes, splitting a loop at some other iteration will do the trick, 3778 // and we've got a flag for that case. Rather than waste the space to 3779 // record the exact iteration (since we rarely know), we provide 3780 // a method that calculates the iteration. It's a drag that it must work 3781 // from scratch, but wonderful in that it's possible. 3782 // 3783 // Here's an example: 3784 // 3785 // for (i = 0; i < 10; i++) 3786 // A[i] = ... 3787 // ... = A[11 - i] 3788 // 3789 // There's a loop-carried flow dependence from the store to the load, 3790 // found by the weak-crossing SIV test. The dependence will have a flag, 3791 // indicating that the dependence can be broken by splitting the loop. 3792 // Calling getSplitIteration will return 5. 3793 // Splitting the loop breaks the dependence, like so: 3794 // 3795 // for (i = 0; i <= 5; i++) 3796 // A[i] = ... 3797 // ... = A[11 - i] 3798 // for (i = 6; i < 10; i++) 3799 // A[i] = ... 3800 // ... = A[11 - i] 3801 // 3802 // breaks the dependence and allows us to vectorize/parallelize 3803 // both loops. 3804 const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep, 3805 unsigned SplitLevel) { 3806 assert(Dep.isSplitable(SplitLevel) && 3807 "Dep should be splitable at SplitLevel"); 3808 Instruction *Src = Dep.getSrc(); 3809 Instruction *Dst = Dep.getDst(); 3810 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory()); 3811 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory()); 3812 assert(isLoadOrStore(Src)); 3813 assert(isLoadOrStore(Dst)); 3814 Value *SrcPtr = getLoadStorePointerOperand(Src); 3815 Value *DstPtr = getLoadStorePointerOperand(Dst); 3816 assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), 3817 MemoryLocation::get(Dst), 3818 MemoryLocation::get(Src)) == MustAlias); 3819 3820 // establish loop nesting levels 3821 establishNestingLevels(Src, Dst); 3822 3823 FullDependence Result(Src, Dst, false, CommonLevels); 3824 3825 unsigned Pairs = 1; 3826 SmallVector<Subscript, 2> Pair(Pairs); 3827 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr); 3828 const SCEV *DstSCEV = SE->getSCEV(DstPtr); 3829 Pair[0].Src = SrcSCEV; 3830 Pair[0].Dst = DstSCEV; 3831 3832 if (Delinearize) { 3833 if (tryDelinearize(Src, Dst, Pair)) { 3834 LLVM_DEBUG(dbgs() << " delinearized\n"); 3835 Pairs = Pair.size(); 3836 } 3837 } 3838 3839 for (unsigned P = 0; P < Pairs; ++P) { 3840 Pair[P].Loops.resize(MaxLevels + 1); 3841 Pair[P].GroupLoops.resize(MaxLevels + 1); 3842 Pair[P].Group.resize(Pairs); 3843 removeMatchingExtensions(&Pair[P]); 3844 Pair[P].Classification = 3845 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), 3846 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), 3847 Pair[P].Loops); 3848 Pair[P].GroupLoops = Pair[P].Loops; 3849 Pair[P].Group.set(P); 3850 } 3851 3852 SmallBitVector Separable(Pairs); 3853 SmallBitVector Coupled(Pairs); 3854 3855 // partition subscripts into separable and minimally-coupled groups 3856 for (unsigned SI = 0; SI < Pairs; ++SI) { 3857 if (Pair[SI].Classification == Subscript::NonLinear) { 3858 // ignore these, but collect loops for later 3859 collectCommonLoops(Pair[SI].Src, 3860 LI->getLoopFor(Src->getParent()), 3861 Pair[SI].Loops); 3862 collectCommonLoops(Pair[SI].Dst, 3863 LI->getLoopFor(Dst->getParent()), 3864 Pair[SI].Loops); 3865 Result.Consistent = false; 3866 } 3867 else if (Pair[SI].Classification == Subscript::ZIV) 3868 Separable.set(SI); 3869 else { 3870 // SIV, RDIV, or MIV, so check for coupled group 3871 bool Done = true; 3872 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) { 3873 SmallBitVector Intersection = Pair[SI].GroupLoops; 3874 Intersection &= Pair[SJ].GroupLoops; 3875 if (Intersection.any()) { 3876 // accumulate set of all the loops in group 3877 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops; 3878 // accumulate set of all subscripts in group 3879 Pair[SJ].Group |= Pair[SI].Group; 3880 Done = false; 3881 } 3882 } 3883 if (Done) { 3884 if (Pair[SI].Group.count() == 1) 3885 Separable.set(SI); 3886 else 3887 Coupled.set(SI); 3888 } 3889 } 3890 } 3891 3892 Constraint NewConstraint; 3893 NewConstraint.setAny(SE); 3894 3895 // test separable subscripts 3896 for (unsigned SI : Separable.set_bits()) { 3897 switch (Pair[SI].Classification) { 3898 case Subscript::SIV: { 3899 unsigned Level; 3900 const SCEV *SplitIter = nullptr; 3901 (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level, 3902 Result, NewConstraint, SplitIter); 3903 if (Level == SplitLevel) { 3904 assert(SplitIter != nullptr); 3905 return SplitIter; 3906 } 3907 break; 3908 } 3909 case Subscript::ZIV: 3910 case Subscript::RDIV: 3911 case Subscript::MIV: 3912 break; 3913 default: 3914 llvm_unreachable("subscript has unexpected classification"); 3915 } 3916 } 3917 3918 if (Coupled.count()) { 3919 // test coupled subscript groups 3920 SmallVector<Constraint, 4> Constraints(MaxLevels + 1); 3921 for (unsigned II = 0; II <= MaxLevels; ++II) 3922 Constraints[II].setAny(SE); 3923 for (unsigned SI : Coupled.set_bits()) { 3924 SmallBitVector Group(Pair[SI].Group); 3925 SmallBitVector Sivs(Pairs); 3926 SmallBitVector Mivs(Pairs); 3927 SmallBitVector ConstrainedLevels(MaxLevels + 1); 3928 for (unsigned SJ : Group.set_bits()) { 3929 if (Pair[SJ].Classification == Subscript::SIV) 3930 Sivs.set(SJ); 3931 else 3932 Mivs.set(SJ); 3933 } 3934 while (Sivs.any()) { 3935 bool Changed = false; 3936 for (unsigned SJ : Sivs.set_bits()) { 3937 // SJ is an SIV subscript that's part of the current coupled group 3938 unsigned Level; 3939 const SCEV *SplitIter = nullptr; 3940 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, 3941 Result, NewConstraint, SplitIter); 3942 if (Level == SplitLevel && SplitIter) 3943 return SplitIter; 3944 ConstrainedLevels.set(Level); 3945 if (intersectConstraints(&Constraints[Level], &NewConstraint)) 3946 Changed = true; 3947 Sivs.reset(SJ); 3948 } 3949 if (Changed) { 3950 // propagate, possibly creating new SIVs and ZIVs 3951 for (unsigned SJ : Mivs.set_bits()) { 3952 // SJ is an MIV subscript that's part of the current coupled group 3953 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, 3954 Pair[SJ].Loops, Constraints, Result.Consistent)) { 3955 Pair[SJ].Classification = 3956 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()), 3957 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()), 3958 Pair[SJ].Loops); 3959 switch (Pair[SJ].Classification) { 3960 case Subscript::ZIV: 3961 Mivs.reset(SJ); 3962 break; 3963 case Subscript::SIV: 3964 Sivs.set(SJ); 3965 Mivs.reset(SJ); 3966 break; 3967 case Subscript::RDIV: 3968 case Subscript::MIV: 3969 break; 3970 default: 3971 llvm_unreachable("bad subscript classification"); 3972 } 3973 } 3974 } 3975 } 3976 } 3977 } 3978 } 3979 llvm_unreachable("somehow reached end of routine"); 3980 return nullptr; 3981 } 3982