DependenceAnalysis.cpp Source File (original) (raw)

63using namespace llvm;

65#define DEBUG_TYPE "da"

70 STATISTIC(TotalArrayPairs, "Array pairs tested");

71 STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs");

72 STATISTIC(ZIVapplications, "ZIV applications");

73 STATISTIC(ZIVindependence, "ZIV independence");

74 STATISTIC(StrongSIVapplications, "Strong SIV applications");

75 STATISTIC(StrongSIVsuccesses, "Strong SIV successes");

76 STATISTIC(StrongSIVindependence, "Strong SIV independence");

77 STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");

78 STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");

79 STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");

80 STATISTIC(ExactSIVapplications, "Exact SIV applications");

81 STATISTIC(ExactSIVsuccesses, "Exact SIV successes");

82 STATISTIC(ExactSIVindependence, "Exact SIV independence");

83 STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");

84 STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");

85 STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");

86 STATISTIC(ExactRDIVapplications, "Exact RDIV applications");

87 STATISTIC(ExactRDIVindependence, "Exact RDIV independence");

88 STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications");

89 STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence");

90 STATISTIC(GCDapplications, "GCD applications");

92 STATISTIC(GCDindependence, "GCD independence");

93 STATISTIC(BanerjeeApplications, "Banerjee applications");

94 STATISTIC(BanerjeeIndependence, "Banerjee independence");

95 STATISTIC(BanerjeeSuccesses, "Banerjee successes");

96 STATISTIC(SameSDLoopsCount, "Loops with Same iteration Space and Depth");

100 cl::desc("Try to delinearize array references."));

102 "da-disable-delinearization-checks", cl::Hidden,

104 "Disable checks that try to statically verify validity of "

105 "delinearized subscripts. Enabling this option may result in incorrect "

106 "dependence vectors for languages that allow the subscript of one "

107 "dimension to underflow or overflow into another dimension."));

108

111 cl::desc("Maximum depth allowed for the recursive algorithm used to "

112 "explore MIV direction vectors."));

113

114namespace {

115

116

117enum class DependenceTestType {

119 StrongSIV,

120 WeakCrossingSIV,

121 ExactSIV,

122 WeakZeroSIV,

123 ExactRDIV,

124 SymbolicRDIV,

125 GCDMIV,

126 BanerjeeMIV,

127};

128

129}

130

132 "da-enable-dependence-test", cl::init(DependenceTestType::All),

134 cl::desc("Run only specified dependence test routine and disable others. "

135 "The purpose is mainly to exclude the influence of other "

136 "dependence test routines in regression tests. If set to All, all "

137 "dependence test routines are enabled."),

139 "Enable all dependence test routines."),

140 clEnumValN(DependenceTestType::StrongSIV, "strong-siv",

141 "Enable only Strong SIV test."),

142 clEnumValN(DependenceTestType::WeakCrossingSIV,

143 "weak-crossing-siv",

144 "Enable only Weak-Crossing SIV test."),

145 clEnumValN(DependenceTestType::ExactSIV, "exact-siv",

146 "Enable only Exact SIV test."),

147 clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv",

148 "Enable only Weak-Zero SIV test."),

149 clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv",

150 "Enable only Exact RDIV test."),

151 clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv",

152 "Enable only Symbolic RDIV test."),

153 clEnumValN(DependenceTestType::GCDMIV, "gcd-miv",

154 "Enable only GCD MIV test."),

155 clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv",

156 "Enable only Banerjee MIV test.")));

157

158

159

162 cl::desc("Check if the subscripts are monotonic. If it's not, dependence "

163 "is reported as unknown."));

164

168 "When printing analysis, dump the results of monotonicity checks."));

169

170

171

172

180

182

184 "Dependence Analysis", true, true)

190

192

195

199

207

209

211

218

219namespace {

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257enum class SCEVMonotonicityType {

258

260

261

262

263 Invariant,

264

265

266

267

268

269 MultivariateSignedMonotonic,

270};

271

272struct SCEVMonotonicity {

273 SCEVMonotonicity(SCEVMonotonicityType Type,

274 const SCEV *FailurePoint = nullptr);

275

276 SCEVMonotonicityType getType() const { return Type; }

277

278 const SCEV *getFailurePoint() const { return FailurePoint; }

279

280 bool isUnknown() const { return Type == SCEVMonotonicityType::Unknown; }

281

282 void print(raw_ostream &OS, unsigned Depth) const;

283

284private:

285 SCEVMonotonicityType Type;

286

287

288 const SCEV *FailurePoint;

289};

290

291

292

293

294

295struct SCEVMonotonicityChecker

296 : public SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity> {

297

298 SCEVMonotonicityChecker(ScalarEvolution *SE) : SE(SE) {}

299

300

301

302

303 SCEVMonotonicity checkMonotonicity(const SCEV *Expr,

304 const Loop *OutermostLoop);

305

306private:

307 ScalarEvolution *SE;

308

309

310 const Loop *OutermostLoop;

311

312

313 SCEVMonotonicity invariantOrUnknown(const SCEV *Expr);

314

315

316

317 bool isLoopInvariant(const SCEV *Expr) const;

318

319

320 SCEVMonotonicity createUnknown(const SCEV *FailurePoint) {

321 return SCEVMonotonicity(SCEVMonotonicityType::Unknown, FailurePoint);

322 }

323

324 SCEVMonotonicity visitAddRecExpr(const SCEVAddRecExpr *Expr);

325

326 SCEVMonotonicity visitConstant(const SCEVConstant *) {

327 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);

328 }

329 SCEVMonotonicity visitVScale(const SCEVVScale *) {

330 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);

331 }

332

333

334 SCEVMonotonicity visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {

335 return invariantOrUnknown(Expr);

336 }

337 SCEVMonotonicity visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {

338 return invariantOrUnknown(Expr);

339 }

340 SCEVMonotonicity visitAddExpr(const SCEVAddExpr *Expr) {

341 return invariantOrUnknown(Expr);

342 }

343 SCEVMonotonicity visitMulExpr(const SCEVMulExpr *Expr) {

344 return invariantOrUnknown(Expr);

345 }

346 SCEVMonotonicity visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {

347 return invariantOrUnknown(Expr);

348 }

349 SCEVMonotonicity visitTruncateExpr(const SCEVTruncateExpr *Expr) {

350 return invariantOrUnknown(Expr);

351 }

352 SCEVMonotonicity visitUDivExpr(const SCEVUDivExpr *Expr) {

353 return invariantOrUnknown(Expr);

354 }

355 SCEVMonotonicity visitSMaxExpr(const SCEVSMaxExpr *Expr) {

356 return invariantOrUnknown(Expr);

357 }

358 SCEVMonotonicity visitUMaxExpr(const SCEVUMaxExpr *Expr) {

359 return invariantOrUnknown(Expr);

360 }

361 SCEVMonotonicity visitSMinExpr(const SCEVSMinExpr *Expr) {

362 return invariantOrUnknown(Expr);

363 }

364 SCEVMonotonicity visitUMinExpr(const SCEVUMinExpr *Expr) {

365 return invariantOrUnknown(Expr);

366 }

367 SCEVMonotonicity visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {

368 return invariantOrUnknown(Expr);

369 }

370 SCEVMonotonicity visitUnknown(const SCEVUnknown *Expr) {

371 return invariantOrUnknown(Expr);

372 }

373 SCEVMonotonicity visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {

374 return invariantOrUnknown(Expr);

375 }

376

377 friend struct SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity>;

378};

379

380}

381

382

383

384

385

388 bool NormalizeResults) {

389 auto *F = DA->getFunction();

390

392 SCEVMonotonicityChecker Checker(&SE);

393 OS << "Monotonicity check:\n";

396 continue;

399 const Loop *OutermostLoop = L ? L->getOutermostLoop() : nullptr;

402 SCEVMonotonicity Mon = Checker.checkMonotonicity(AccessFn, OutermostLoop);

403 OS.indent(2) << "Inst: " << Inst << "\n";

404 OS.indent(4) << "Expr: " << *AccessFn << "\n";

405 Mon.print(OS, 4);

406 }

407 OS << "\n";

408 }

409

411 ++SrcI) {

412 if (SrcI->mayReadOrWriteMemory()) {

414 ++DstI) {

415 if (DstI->mayReadOrWriteMemory()) {

416 OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n";

417 OS << " da analyze - ";

418 if (auto D = DA->depends(&*SrcI, &*DstI,

419 true)) {

420

421#ifndef NDEBUG

422

423

424 for (unsigned Level = 1; Level <= D->getLevels(); Level++) {

425 const SCEV *Distance = D->getDistance(Level);

426 bool IsDistanceZero = Distance && Distance->isZero();

427 bool IsDirectionEQ =

429 assert(IsDistanceZero == IsDirectionEQ &&

430 "Inconsistent distance and direction.");

431 }

432#endif

433

434

435 if (NormalizeResults && D->normalize(&SE))

436 OS << "normalized - ";

437 D->dump(OS);

438 } else

439 OS << "none!\n";

440 }

441 }

442 }

443 }

444}

445

447 const Module *) const {

451}

452

455 OS << "Printing analysis 'Dependence Analysis' for function '" << F.getName()

456 << "':\n";

461}

462

463

464

465

466

468 return Src->mayReadFromMemory() && Dst->mayReadFromMemory();

469}

470

471

473 return Src->mayWriteToMemory() && Dst->mayWriteToMemory();

474}

475

476

478 return Src->mayWriteToMemory() && Dst->mayReadFromMemory();

479}

480

481

483 return Src->mayReadFromMemory() && Dst->mayWriteToMemory();

484}

485

486

487

488

489

491

492

493

494

497 bool PossiblyLoopIndependent,

498 unsigned CommonLevels)

499 : Dependence(Source, Destination, Assumes), Levels(CommonLevels),

500 LoopIndependent(PossiblyLoopIndependent) {

501 Consistent = true;

502 SameSDLevels = 0;

503 if (CommonLevels)

504 DV = std::make_unique<DVEntry[]>(CommonLevels);

505}

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

523 for (unsigned Level = 1; Level <= Levels; ++Level) {

524 unsigned char Direction = DV[Level - 1].Direction;

526 continue;

529 return true;

530 return false;

531 }

532 return false;

533}

534

537 return false;

538

539 LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";

542 for (unsigned Level = 1; Level <= Levels; ++Level) {

543 unsigned char Direction = DV[Level - 1].Direction;

544

545

551 DV[Level - 1].Direction = RevDirection;

552

553 if (DV[Level - 1].Distance != nullptr)

554 DV[Level - 1].Distance = SE->getNegativeSCEV(DV[Level - 1].Distance);

555 }

556

557 LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n";

559 return true;

560}

561

562

563

564

565

569

570

571

575

576

577

578

582

583

584

588

589

590

594

595

596

597

599 assert(0 < Level && Level <= static_cast<unsigned>(Levels) + SameSDLevels &&

600 "Level out of range");

601 return Level > Levels;

602}

603

604

605

606

607SCEVMonotonicity::SCEVMonotonicity(SCEVMonotonicityType Type,

608 const SCEV *FailurePoint)

609 : Type(Type), FailurePoint(FailurePoint) {

611 ((Type == SCEVMonotonicityType::Unknown) == (FailurePoint != nullptr)) &&

612 "FailurePoint must be provided iff Type is Unknown");

613}

614

615void SCEVMonotonicity::print(raw_ostream &OS, unsigned Depth) const {

617 switch (Type) {

618 case SCEVMonotonicityType::Unknown:

619 assert(FailurePoint && "FailurePoint must be provided for Unknown");

620 OS << "Unknown\n";

621 OS.indent(Depth) << "Reason: " << *FailurePoint << "\n";

622 break;

623 case SCEVMonotonicityType::Invariant:

624 OS << "Invariant\n";

625 break;

626 case SCEVMonotonicityType::MultivariateSignedMonotonic:

627 OS << "MultivariateSignedMonotonic\n";

628 break;

629 }

630}

631

632bool SCEVMonotonicityChecker::isLoopInvariant(const SCEV *Expr) const {

633 return !OutermostLoop || SE->isLoopInvariant(Expr, OutermostLoop);

634}

635

636SCEVMonotonicity SCEVMonotonicityChecker::invariantOrUnknown(const SCEV *Expr) {

637 if (isLoopInvariant(Expr))

638 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);

639 return createUnknown(Expr);

640}

641

642SCEVMonotonicity

643SCEVMonotonicityChecker::checkMonotonicity(const SCEV *Expr,

644 const Loop *OutermostLoop) {

646 "OutermostLoop must be outermost");

648 this->OutermostLoop = OutermostLoop;

649 return visit(Expr);

650}

651

652

653

654

655

656

657

658

659

660

661

662

663SCEVMonotonicity

664SCEVMonotonicityChecker::visitAddRecExpr(const SCEVAddRecExpr *Expr) {

666 return createUnknown(Expr);

667

670

671 SCEVMonotonicity StartMon = visit(Start);

672 if (StartMon.isUnknown())

673 return StartMon;

674

675 if (!isLoopInvariant(Step))

676 return createUnknown(Expr);

677

678 return SCEVMonotonicity(SCEVMonotonicityType::MultivariateSignedMonotonic);

679}

680

681

682

683

684

687 OS << "confused";

688 else {

690 OS << "consistent ";

692 OS << "flow";

694 OS << "output";

696 OS << "anti";

698 OS << "input";

701 if (SameSDLevels > 0) {

702 OS << " / assuming " << SameSDLevels << " loop level(s) fused: ";

704 }

705 }

706 OS << "!\n";

707

709 if (!Assumptions.isAlwaysTrue()) {

710 OS << " Runtime Assumptions:\n";

711 Assumptions.print(OS, 2);

712 }

713}

714

715

716

720 bool OnSameSD = false;

721 unsigned LevelNum = Levels;

722 if (IsSameSD)

723 LevelNum += SameSDLevels;

724 OS << " [";

725 for (unsigned II = 1; II <= LevelNum; ++II) {

727 OnSameSD = true;

729 OS << 'p';

731 if (Distance)

732 OS << *Distance;

734 OS << "S";

735 else {

738 OS << "*";

739 else {

741 OS << "<";

743 OS << "=";

745 OS << ">";

746 }

747 }

749 OS << 'p';

750 if (II < LevelNum)

751 OS << " ";

752 }

754 OS << "|<";

755 OS << "]";

756}

757

758

759

760

761

762

766

767

774

777

778

781

782

783 if (AObj == BObj)

785

786

787

790

791

792

794}

795

796

797

800 return LI->isUnordered();

802 return SI->isUnordered();

803 return false;

804}

805

806

807

808

809

810bool DependenceInfo::haveSameSD(const Loop *SrcLoop,

811 const Loop *DstLoop) const {

812 if (SrcLoop == DstLoop)

813 return true;

814

816 return false;

817

818 if (!SrcLoop || !SrcLoop->getLoopLatch() || !DstLoop ||

820 return false;

821

822 const SCEV *SrcUB = nullptr, *DstUP = nullptr;

823 if (SE->hasLoopInvariantBackedgeTakenCount(SrcLoop))

824 SrcUB = SE->getBackedgeTakenCount(SrcLoop);

825 if (SE->hasLoopInvariantBackedgeTakenCount(DstLoop))

826 DstUP = SE->getBackedgeTakenCount(DstLoop);

827

828 if (SrcUB != nullptr && DstUP != nullptr) {

829 Type *WiderType = SE->getWiderType(SrcUB->getType(), DstUP->getType());

830 SrcUB = SE->getNoopOrZeroExtend(SrcUB, WiderType);

831 DstUP = SE->getNoopOrZeroExtend(DstUP, WiderType);

832

834 return true;

835 }

836

837 return false;

838}

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902void DependenceInfo::establishNestingLevels(const Instruction *Src,

904 const BasicBlock *SrcBlock = Src->getParent();

905 const BasicBlock *DstBlock = Dst->getParent();

906 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);

907 unsigned DstLevel = LI->getLoopDepth(DstBlock);

908 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);

909 const Loop *DstLoop = LI->getLoopFor(DstBlock);

910 SrcLevels = SrcLevel;

911 MaxLevels = SrcLevel + DstLevel;

912 SameSDLevels = 0;

913 while (SrcLevel > DstLevel) {

915 SrcLevel--;

916 }

917 while (DstLevel > SrcLevel) {

919 DstLevel--;

920 }

921

922

923 while (SrcLoop != DstLoop) {

924 SameSDLevels++;

925 if (!haveSameSD(SrcLoop, DstLoop))

926 SameSDLevels = 0;

929 SrcLevel--;

930 }

931 CommonLevels = SrcLevel;

932 MaxLevels -= CommonLevels;

933}

934

935

936

937unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {

939}

940

941

942

943unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {

945 if (D > CommonLevels)

946

947

948 return D - CommonLevels + SrcLevels;

949 else

950 return D;

951}

952

953

954bool DependenceInfo::isLoopInvariant(const SCEV *Expression,

956

957

958

959

960 if (!LoopNest)

961 return true;

962

963

964

965 return SE->isLoopInvariant(Expression, LoopNest->getOutermostLoop());

966}

967

968

969

970void DependenceInfo::collectCommonLoops(const SCEV *Expression,

973 while (LoopNest) {

975 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))

976 Loops.set(Level);

978 }

979}

980

982

983 unsigned widestWidthSeen = 0;

984 Type *widestType;

985

986

987

988 for (Subscript *Pair : Pairs) {

989 const SCEV *Src = Pair->Src;

990 const SCEV *Dst = Pair->Dst;

993 if (SrcTy == nullptr || DstTy == nullptr) {

994 assert(SrcTy == DstTy &&

995 "This function only unify integer types and "

996 "expect Src and Dst share the same type otherwise.");

997 continue;

998 }

999 if (SrcTy->getBitWidth() > widestWidthSeen) {

1001 widestType = SrcTy;

1002 }

1003 if (DstTy->getBitWidth() > widestWidthSeen) {

1005 widestType = DstTy;

1006 }

1007 }

1008

1009 assert(widestWidthSeen > 0);

1010

1011

1012 for (Subscript *Pair : Pairs) {

1013 const SCEV *Src = Pair->Src;

1014 const SCEV *Dst = Pair->Dst;

1017 if (SrcTy == nullptr || DstTy == nullptr) {

1018 assert(SrcTy == DstTy &&

1019 "This function only unify integer types and "

1020 "expect Src and Dst share the same type otherwise.");

1021 continue;

1022 }

1023 if (SrcTy->getBitWidth() < widestWidthSeen)

1024

1025 Pair->Src = SE->getSignExtendExpr(Src, widestType);

1026 if (DstTy->getBitWidth() < widestWidthSeen) {

1027

1028 Pair->Dst = SE->getSignExtendExpr(Dst, widestType);

1029 }

1030 }

1031}

1032

1033

1034

1035

1036

1037void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {

1038 const SCEV *Src = Pair->Src;

1039 const SCEV *Dst = Pair->Dst;

1044 const SCEV *SrcCastOp = SrcCast->getOperand();

1045 const SCEV *DstCastOp = DstCast->getOperand();

1047 Pair->Src = SrcCastOp;

1048 Pair->Dst = DstCastOp;

1049 }

1050 }

1051}

1052

1053

1054

1055bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,

1058 if (!AddRec)

1059 return isLoopInvariant(Expr, LoopNest);

1060

1061

1062

1063

1064

1065

1066 const Loop *L = LoopNest;

1067 while (L && AddRec->getLoop() != L)

1068 L = L->getParentLoop();

1069 if (!L)

1070 return false;

1071

1074 if (!isLoopInvariant(Step, LoopNest))

1075 return false;

1076 if (IsSrc)

1078 else

1080 return checkSubscript(Start, LoopNest, Loops, IsSrc);

1081}

1082

1083

1084

1085bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,

1087 return checkSubscript(Src, LoopNest, Loops, true);

1088}

1089

1090

1091

1092bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,

1094 return checkSubscript(Dst, LoopNest, Loops, false);

1095}

1096

1097

1098

1099

1100DependenceInfo::Subscript::ClassificationKind

1101DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,

1102 const SCEV *Dst, const Loop *DstLoopNest,

1104 SmallBitVector SrcLoops(MaxLevels + 1);

1105 SmallBitVector DstLoops(MaxLevels + 1);

1106 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))

1107 return Subscript::NonLinear;

1108 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))

1109 return Subscript::NonLinear;

1110 Loops = SrcLoops;

1111 Loops |= DstLoops;

1112 unsigned N = Loops.count();

1113 if (N == 0)

1114 return Subscript::ZIV;

1115 if (N == 1)

1116 return Subscript::SIV;

1117 if (N == 2 && (SrcLoops.count() == 0 || DstLoops.count() == 0 ||

1118 (SrcLoops.count() == 1 && DstLoops.count() == 1)))

1119 return Subscript::RDIV;

1120 return Subscript::MIV;

1121}

1122

1123

1124

1125

1126

1127

1128

1129

1130

1131

1132

1134 const SCEV *Y) const {

1143 X = Xop;

1144 Y = Yop;

1145 }

1146 }

1147 }

1148 if (SE->isKnownPredicate(Pred, X, Y))

1149 return true;

1150

1151

1152

1153

1154

1155 const SCEV *Delta = SE->getMinusSCEV(X, Y);

1156 switch (Pred) {

1158 return Delta->isZero();

1160 return SE->isKnownNonZero(Delta);

1162 return SE->isKnownNonNegative(Delta);

1164 return SE->isKnownNonPositive(Delta);

1166 return SE->isKnownPositive(Delta);

1168 return SE->isKnownNegative(Delta);

1169 default:

1170 llvm_unreachable("unexpected predicate in isKnownPredicate");

1171 }

1172}

1173

1174

1175

1176

1177

1178

1179

1180

1181const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {

1182 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {

1183 const SCEV *UB = SE->getBackedgeTakenCount(L);

1184 return SE->getTruncateOrZeroExtend(UB, T);

1185 }

1186 return nullptr;

1187}

1188

1189

1190

1191const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L,

1192 Type *T) const {

1193 if (const SCEV *UB = collectUpperBound(L, T))

1195 return nullptr;

1196}

1197

1198

1199

1202 if (SE.willNotOverflow(Instruction::Sub, true, A, B))

1204 return nullptr;

1205}

1206

1207

1208

1211 if (SE.willNotOverflow(Instruction::Mul, true, A, B))

1213 return nullptr;

1214}

1215

1216

1217

1218

1219

1220

1223 if (!Ty)

1224 return nullptr;

1225

1229 return nullptr;

1230 return SE.getAbsExpr(A, true);

1231}

1232

1233

1239

1240

1241

1242

1243

1244

1245

1246

1247

1248

1249

1250bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,

1254 ++ZIVapplications;

1257 return false;

1258 }

1261 ++ZIVindependence;

1262 return true;

1263 }

1265 Result.Consistent = false;

1266 return false;

1267}

1268

1269

1270

1271

1272

1273

1274

1275

1276

1277

1278

1279

1280

1281

1282

1283

1284

1285

1286

1287

1288

1289

1290

1291

1292

1293

1294

1295

1296bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,

1297 const SCEV *DstConst, const Loop *CurSrcLoop,

1298 const Loop *CurDstLoop, unsigned Level,

1300 bool UnderRuntimeAssumptions) {

1302 return false;

1303

1307 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst);

1309 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst);

1311 ++StrongSIVapplications;

1312 assert(0 < Level && Level <= CommonLevels && "level out of range");

1314

1316 if (!Delta) {

1317 Result.Consistent = false;

1318 return false;

1319 }

1322

1323

1324 bool IsDeltaLarge = [&] {

1325 const SCEV *UpperBound = collectUpperBound(CurSrcLoop, Delta->getType());

1326 if (!UpperBound)

1327 return false;

1328

1329 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound);

1333 if (!AbsDelta || !AbsCoeff)

1334 return false;

1336 if (!Product)

1337 return false;

1339 }();

1340 if (IsDeltaLarge) {

1341

1342 ++StrongSIVindependence;

1343 ++StrongSIVsuccesses;

1344 return true;

1345 }

1346

1347

1351 APInt Distance = ConstDelta;

1352 APInt Remainder = ConstDelta;

1353 APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);

1354 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n");

1355 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");

1356

1357 if (Remainder != 0) {

1358

1359 ++StrongSIVindependence;

1360 ++StrongSIVsuccesses;

1361 return true;

1362 }

1363 Result.DV[Level].Distance = SE->getConstant(Distance);

1364 if (Distance.sgt(0))

1366 else if (Distance.slt(0))

1368 else

1370 ++StrongSIVsuccesses;

1371 } else if (Delta->isZero()) {

1372

1373

1374

1375 if (SE->isKnownNonZero(Coeff)) {

1377 dbgs() << "\t Coefficient proven non-zero by SCEV analysis\n");

1378 } else {

1379

1380 if (UnderRuntimeAssumptions) {

1381 const SCEVPredicate *Pred = SE->getComparePredicate(

1383 Result.Assumptions = Result.Assumptions.getUnionWith(Pred, *SE);

1384 LLVM_DEBUG(dbgs() << "\t Added runtime assumption: " << *Coeff

1385 << " != 0\n");

1386 } else {

1387

1388

1389 LLVM_DEBUG(dbgs() << "\t Would need runtime assumption " << *Coeff

1390 << " != 0, but not allowed. Failing this test.\n");

1391 return false;

1392 }

1393 }

1394

1397 ++StrongSIVsuccesses;

1398 } else {

1399 if (Coeff->isOne()) {

1400 LLVM_DEBUG(dbgs() << "\t Distance = " << *Delta << "\n");

1401 Result.DV[Level].Distance = Delta;

1402 } else {

1403 Result.Consistent = false;

1404 }

1405

1406

1407 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);

1408 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);

1409 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);

1410 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);

1411 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);

1412

1413

1414

1416 if ((DeltaMaybePositive && CoeffMaybePositive) ||

1417 (DeltaMaybeNegative && CoeffMaybeNegative))

1419 if (DeltaMaybeZero)

1421 if ((DeltaMaybeNegative && CoeffMaybePositive) ||

1422 (DeltaMaybePositive && CoeffMaybeNegative))

1424 if (NewDirection < Result.DV[Level].Direction)

1425 ++StrongSIVsuccesses;

1426 Result.DV[Level].Direction &= NewDirection;

1427 }

1428 return false;

1429}

1430

1431

1432

1433

1434

1435

1436

1437

1438

1439

1440

1441

1442

1443

1444

1445

1446

1447

1448

1449

1450

1451

1452

1453

1454

1455

1456

1457

1458

1459bool DependenceInfo::weakCrossingSIVtest(const SCEV *Coeff,

1460 const SCEV *SrcConst,

1461 const SCEV *DstConst,

1462 const Loop *CurSrcLoop,

1463 const Loop *CurDstLoop, unsigned Level,

1466 return false;

1467

1469 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n");

1470 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");

1471 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");

1472 ++WeakCrossingSIVapplications;

1473 assert(0 < Level && Level <= CommonLevels && "Level out of range");

1475 Result.Consistent = false;

1476 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);

1477 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");

1478 if (Delta->isZero()) {

1479 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;

1480 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;

1481 ++WeakCrossingSIVsuccesses;

1482 if ( Result .DV[Level].Direction) {

1483 ++WeakCrossingSIVindependence;

1484 return true;

1485 }

1486 Result.DV[Level].Distance = Delta;

1487 return false;

1488 }

1490 if (!ConstCoeff)

1491 return false;

1492

1493 if (SE->isKnownNegative(ConstCoeff)) {

1495 assert(ConstCoeff &&

1496 "dynamic cast of negative of ConstCoeff should yield constant");

1497 Delta = SE->getNegativeSCEV(Delta);

1498 }

1499 assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive");

1500

1502 if (!ConstDelta)

1503 return false;

1504

1505

1506

1507 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");

1508 LLVM_DEBUG(dbgs() << "\t ConstCoeff = " << *ConstCoeff << "\n");

1509 if (SE->isKnownNegative(Delta)) {

1510

1511 ++WeakCrossingSIVindependence;

1512 ++WeakCrossingSIVsuccesses;

1513 return true;

1514 }

1515

1516

1517

1518 if (const SCEV *UpperBound =

1519 collectUpperBound(CurSrcLoop, Delta->getType())) {

1520 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");

1521 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);

1522 const SCEV *ML =

1523 SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), ConstantTwo);

1526

1527 ++WeakCrossingSIVindependence;

1528 ++WeakCrossingSIVsuccesses;

1529 return true;

1530 }

1532

1533 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;

1534 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;

1535 ++WeakCrossingSIVsuccesses;

1536 if ( Result .DV[Level].Direction) {

1537 ++WeakCrossingSIVindependence;

1538 return true;

1539 }

1541 return false;

1542 }

1543 }

1544

1545

1546 APInt APDelta = ConstDelta->getAPInt();

1547 APInt APCoeff = ConstCoeff->getAPInt();

1548 APInt Distance = APDelta;

1549 APInt Remainder = APDelta;

1550 APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);

1551 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");

1552 if (Remainder != 0) {

1553

1554 ++WeakCrossingSIVindependence;

1555 ++WeakCrossingSIVsuccesses;

1556 return true;

1557 }

1558 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n");

1559

1560

1561 APInt Two = APInt(Distance.getBitWidth(), 2, true);

1562 Remainder = Distance.srem(Two);

1563 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");

1564 if (Remainder != 0) {

1565

1566 Result.DV[Level].Direction &= ~Dependence::DVEntry::EQ;

1567 ++WeakCrossingSIVsuccesses;

1568 }

1569 return false;

1570}

1571

1572

1573

1574

1575

1576

1577

1578

1579

1580

1581

1584 APInt A0(Bits, 1, true), A1(Bits, 0, true);

1585 APInt B0(Bits, 0, true), B1(Bits, 1, true);

1588 APInt Q = G0;

1591 while (R != 0) {

1592

1593 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;

1594 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;

1595 G0 = G1; G1 = R;

1596

1598 }

1599 G = G1;

1601 X = AM.slt(0) ? -A1 : A1;

1602 Y = BM.slt(0) ? B1 : -B1;

1603

1604

1605 R = Delta.srem(G);

1606 if (R != 0)

1607 return true;

1608 Q = Delta.sdiv(G);

1609 return false;

1610}

1611

1613 APInt Q = A;

1616 if (R == 0)

1617 return Q;

1618 if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))

1619 return Q;

1620 else

1621 return Q - 1;

1622}

1623

1625 APInt Q = A;

1628 if (R == 0)

1629 return Q;

1630 if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))

1631 return Q + 1;

1632 else

1633 return Q;

1634}

1635

1636

1637

1638

1639

1640

1641

1642

1643

1644

1645

1646

1647

1648

1649

1650

1651

1652

1653

1654

1655

1656

1657

1658

1659

1660

1661

1662

1663

1664

1665static std::pair<std::optional, std::optional>

1667 const std::optional &UB) {

1668 assert(A != 0 && "A must be non-zero");

1669 std::optional TL, TU;

1670 if (A.sgt(0)) {

1672 LLVM_DEBUG(dbgs() << "\t Possible TL = " << *TL << "\n");

1673

1674 if (UB) {

1675

1677 LLVM_DEBUG(dbgs() << "\t Possible TU = " << *TU << "\n");

1678 }

1679 } else {

1681 LLVM_DEBUG(dbgs() << "\t Possible TU = " << *TU << "\n");

1682

1683 if (UB) {

1684

1686 LLVM_DEBUG(dbgs() << "\t Possible TL = " << *TL << "\n");

1687 }

1688 }

1689 return std::make_pair(TL, TU);

1690}

1691

1692

1693

1694

1695

1696

1697

1698

1699

1700

1701

1702

1703

1704

1705

1706

1707

1708

1709

1710

1711bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,

1712 const SCEV *SrcConst, const SCEV *DstConst,

1713 const Loop *CurSrcLoop,

1714 const Loop *CurDstLoop, unsigned Level,

1717 return false;

1718

1720 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n");

1721 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n");

1722 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");

1723 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");

1724 ++ExactSIVapplications;

1725 assert(0 < Level && Level <= CommonLevels && "Level out of range");

1727 Result.Consistent = false;

1729 if (!Delta)

1730 return false;

1731 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");

1735 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)

1736 return false;

1737

1738

1739 APInt G, X, Y;

1740 APInt AM = ConstSrcCoeff->getAPInt();

1741 APInt BM = ConstDstCoeff->getAPInt();

1742 APInt CM = ConstDelta->getAPInt();

1744 if (findGCD(Bits, AM, BM, CM, G, X, Y)) {

1745

1746 ++ExactSIVindependence;

1747 ++ExactSIVsuccesses;

1748 return true;

1749 }

1750

1751 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n");

1752

1753

1754 std::optional UM;

1755

1756 if (const SCEVConstant *CUB =

1757 collectConstantUpperBound(CurSrcLoop, Delta->getType())) {

1758 UM = CUB->getAPInt();

1760 }

1761

1764 APInt TC = CM.sdiv(G);

1765 APInt TX = X * TC;

1766 APInt TY = Y * TC;

1770

1773

1774

1775

1776

1777

1778

1779

1780

1781

1782

1785

1786 auto CreateVec = [](const std::optional &V0,

1787 const std::optional &V1) {

1789 if (V0)

1791 if (V1)

1793 return Vec;

1794 };

1795

1798

1801

1803 return false;

1808

1809 if (TL.sgt(TU)) {

1810 ++ExactSIVindependence;

1811 ++ExactSIVsuccesses;

1812 return true;

1813 }

1814

1815

1817 APInt LowerDistance, UpperDistance;

1818

1819 if (TA.sgt(TB)) {

1820 LowerDistance = (TY - TX) + (TA - TB) * TL;

1821 UpperDistance = (TY - TX) + (TA - TB) * TU;

1822 } else {

1823 LowerDistance = (TY - TX) + (TA - TB) * TU;

1824 UpperDistance = (TY - TX) + (TA - TB) * TL;

1825 }

1826

1827 LLVM_DEBUG(dbgs() << "\t LowerDistance = " << LowerDistance << "\n");

1828 LLVM_DEBUG(dbgs() << "\t UpperDistance = " << UpperDistance << "\n");

1829

1830 APInt Zero(Bits, 0, true);

1831 if (LowerDistance.sle(Zero) && UpperDistance.sge(Zero)) {

1833 ++ExactSIVsuccesses;

1834 }

1835 if (LowerDistance.slt(0)) {

1837 ++ExactSIVsuccesses;

1838 }

1839 if (UpperDistance.sgt(0)) {

1841 ++ExactSIVsuccesses;

1842 }

1843

1844

1845 Result.DV[Level].Direction &= NewDirection;

1847 ++ExactSIVindependence;

1851}

1852

1853

1856 const APInt &ConstDividend = Dividend->getAPInt();

1857 const APInt &ConstDivisor = Divisor->getAPInt();

1858 return ConstDividend.srem(ConstDivisor) == 0;

1859}

1860

1861

1862

1863

1864

1865

1866

1867

1868

1869

1870

1871

1872

1873

1874

1875

1876

1877

1878

1879

1880

1881

1882

1883

1884

1885

1886

1887

1888

1889

1890

1891

1892bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff,

1893 const SCEV *SrcConst,

1894 const SCEV *DstConst,

1895 const Loop *CurSrcLoop,

1896 const Loop *CurDstLoop, unsigned Level,

1899 return false;

1900

1901

1902

1903

1904 LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");

1905 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n");

1906 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");

1907 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");

1908 ++WeakZeroSIVapplications;

1909 assert(0 < Level && Level <= MaxLevels && "Level out of range");

1911 Result.Consistent = false;

1912 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);

1913 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");

1914 if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {

1915 if (Level < CommonLevels) {

1918 ++WeakZeroSIVsuccesses;

1919 }

1920 return false;

1921 }

1923 if (!ConstCoeff)

1924 return false;

1925

1926

1927

1928 const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)

1929 ? SE->getNegativeSCEV(ConstCoeff)

1930 : ConstCoeff;

1931 const SCEV *NewDelta =

1932 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;

1933

1934

1935

1936 if (const SCEV *UpperBound =

1937 collectUpperBound(CurSrcLoop, Delta->getType())) {

1938 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");

1939 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);

1941 ++WeakZeroSIVindependence;

1942 ++WeakZeroSIVsuccesses;

1943 return true;

1944 }

1945 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {

1946

1947 if (Level < CommonLevels) {

1950 ++WeakZeroSIVsuccesses;

1951 }

1952 return false;

1953 }

1954 }

1955

1956

1957

1958 if (SE->isKnownNegative(NewDelta)) {

1959

1960 ++WeakZeroSIVindependence;

1961 ++WeakZeroSIVsuccesses;

1962 return true;

1963 }

1964

1965

1968 ++WeakZeroSIVindependence;

1969 ++WeakZeroSIVsuccesses;

1970 return true;

1971 }

1972 return false;

1973}

1974

1975

1976

1977

1978

1979

1980

1981

1982

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000

2001

2002

2003

2004

2005

2006bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff,

2007 const SCEV *SrcConst,

2008 const SCEV *DstConst,

2009 const Loop *CurSrcLoop,

2010 const Loop *CurDstLoop, unsigned Level,

2013 return false;

2014

2015

2016

2017 LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");

2018 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n");

2019 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");

2020 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");

2021 ++WeakZeroSIVapplications;

2022 assert(0 < Level && Level <= SrcLevels && "Level out of range");

2024 Result.Consistent = false;

2025 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);

2026 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");

2027 if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {

2028 if (Level < CommonLevels) {

2031 ++WeakZeroSIVsuccesses;

2032 }

2033 return false;

2034 }

2036 if (!ConstCoeff)

2037 return false;

2038

2039

2040

2041 const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)

2042 ? SE->getNegativeSCEV(ConstCoeff)

2043 : ConstCoeff;

2044 const SCEV *NewDelta =

2045 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;

2046

2047

2048

2049 if (const SCEV *UpperBound =

2050 collectUpperBound(CurSrcLoop, Delta->getType())) {

2051 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");

2052 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);

2054 ++WeakZeroSIVindependence;

2055 ++WeakZeroSIVsuccesses;

2056 return true;

2057 }

2058 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {

2059

2060 if (Level < CommonLevels) {

2063 ++WeakZeroSIVsuccesses;

2064 }

2065 return false;

2066 }

2067 }

2068

2069

2070

2071 if (SE->isKnownNegative(NewDelta)) {

2072

2073 ++WeakZeroSIVindependence;

2074 ++WeakZeroSIVsuccesses;

2075 return true;

2076 }

2077

2078

2081 ++WeakZeroSIVindependence;

2082 ++WeakZeroSIVsuccesses;

2083 return true;

2084 }

2085 return false;

2086}

2087

2088

2089

2090

2091

2092

2093

2094

2095bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,

2096 const SCEV *SrcConst, const SCEV *DstConst,

2097 const Loop *SrcLoop, const Loop *DstLoop,

2100 return false;

2101

2103 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n");

2104 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n");

2105 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");

2106 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");

2107 ++ExactRDIVapplications;

2108 Result.Consistent = false;

2109 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);

2110 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");

2114 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)

2115 return false;

2116

2117

2118 APInt G, X, Y;

2119 APInt AM = ConstSrcCoeff->getAPInt();

2120 APInt BM = ConstDstCoeff->getAPInt();

2121 APInt CM = ConstDelta->getAPInt();

2123 if (findGCD(Bits, AM, BM, CM, G, X, Y)) {

2124

2125 ++ExactRDIVindependence;

2126 return true;

2127 }

2128

2129 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n");

2130

2131

2132 std::optional SrcUM;

2133

2134 if (const SCEVConstant *UpperBound =

2135 collectConstantUpperBound(SrcLoop, Delta->getType())) {

2136 SrcUM = UpperBound->getAPInt();

2137 LLVM_DEBUG(dbgs() << "\t SrcUM = " << *SrcUM << "\n");

2138 }

2139

2140 std::optional DstUM;

2141

2142 if (const SCEVConstant *UpperBound =

2143 collectConstantUpperBound(DstLoop, Delta->getType())) {

2144 DstUM = UpperBound->getAPInt();

2145 LLVM_DEBUG(dbgs() << "\t DstUM = " << *DstUM << "\n");

2146 }

2147

2150 APInt TC = CM.sdiv(G);

2151 APInt TX = X * TC;

2152 APInt TY = Y * TC;

2156

2159

2160

2161

2162

2163

2164

2165

2166

2167

2168

2171

2174

2175 auto CreateVec = [](const std::optional &V0,

2176 const std::optional &V1) {

2178 if (V0)

2180 if (V1)

2182 return Vec;

2183 };

2184

2188 return false;

2189

2194

2195 if (TL.sgt(TU))

2196 ++ExactRDIVindependence;

2197 return TL.sgt(TU);

2198}

2199

2200

2201

2202

2203

2204

2205

2206

2207

2208

2209

2210

2211

2212

2213

2214

2215

2216

2217

2218

2219

2220

2221

2222

2223

2224

2225

2226

2227

2228

2229

2230

2231

2232

2233

2234

2235

2236

2237

2238

2239

2240

2241

2242bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,

2243 const SCEV *C1, const SCEV *C2,

2244 const Loop *Loop1,

2245 const Loop *Loop2) const {

2247 return false;

2248

2249 ++SymbolicRDIVapplications;

2256 const SCEV *N1 = collectUpperBound(Loop1, A1->getType());

2257 const SCEV *N2 = collectUpperBound(Loop2, A1->getType());

2258 LLVM_DEBUG(if (N1) dbgs() << "\t N1 = " << *N1 << "\n");

2259 LLVM_DEBUG(if (N2) dbgs() << "\t N2 = " << *N2 << "\n");

2260 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);

2261 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);

2262 LLVM_DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n");

2263 LLVM_DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n");

2264 if (SE->isKnownNonNegative(A1)) {

2265 if (SE->isKnownNonNegative(A2)) {

2266

2267 if (N1) {

2268

2269 const SCEV *A1N1 = SE->getMulExpr(A1, N1);

2270 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n");

2272 ++SymbolicRDIVindependence;

2273 return true;

2274 }

2275 }

2276 if (N2) {

2277

2278 const SCEV *A2N2 = SE->getMulExpr(A2, N2);

2279 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n");

2281 ++SymbolicRDIVindependence;

2282 return true;

2283 }

2284 }

2285 } else if (SE->isKnownNonPositive(A2)) {

2286

2287 if (N1 && N2) {

2288

2289 const SCEV *A1N1 = SE->getMulExpr(A1, N1);

2290 const SCEV *A2N2 = SE->getMulExpr(A2, N2);

2291 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);

2292 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");

2294 ++SymbolicRDIVindependence;

2295 return true;

2296 }

2297 }

2298

2299 if (SE->isKnownNegative(C2_C1)) {

2300 ++SymbolicRDIVindependence;

2301 return true;

2302 }

2303 }

2304 } else if (SE->isKnownNonPositive(A1)) {

2305 if (SE->isKnownNonNegative(A2)) {

2306

2307 if (N1 && N2) {

2308

2309 const SCEV *A1N1 = SE->getMulExpr(A1, N1);

2310 const SCEV *A2N2 = SE->getMulExpr(A2, N2);

2311 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);

2312 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");

2314 ++SymbolicRDIVindependence;

2315 return true;

2316 }

2317 }

2318

2319 if (SE->isKnownPositive(C2_C1)) {

2320 ++SymbolicRDIVindependence;

2321 return true;

2322 }

2323 } else if (SE->isKnownNonPositive(A2)) {

2324

2325 if (N1) {

2326

2327 const SCEV *A1N1 = SE->getMulExpr(A1, N1);

2328 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n");

2330 ++SymbolicRDIVindependence;

2331 return true;

2332 }

2333 }

2334 if (N2) {

2335

2336 const SCEV *A2N2 = SE->getMulExpr(A2, N2);

2337 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n");

2339 ++SymbolicRDIVindependence;

2340 return true;

2341 }

2342 }

2343 }

2344 }

2345 return false;

2346}

2347

2348

2349

2350

2351

2352

2353

2354

2355

2356bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,

2358 bool UnderRuntimeAssumptions) {

2363 if (SrcAddRec && DstAddRec) {

2364 const SCEV *SrcConst = SrcAddRec->getStart();

2365 const SCEV *DstConst = DstAddRec->getStart();

2368 const Loop *CurSrcLoop = SrcAddRec->getLoop();

2369 const Loop *CurDstLoop = DstAddRec->getLoop();

2370 assert(haveSameSD(CurSrcLoop, CurDstLoop) &&

2371 "Loops in the SIV test should have the same iteration space and "

2372 "depth");

2373 Level = mapSrcLoop(CurSrcLoop);

2374 bool disproven;

2375 if (SrcCoeff == DstCoeff)

2376 disproven =

2377 strongSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop, CurDstLoop,

2378 Level, Result, UnderRuntimeAssumptions);

2379 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))

2380 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,

2381 CurDstLoop, Level, Result);

2382 else

2383 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst,

2384 CurSrcLoop, CurDstLoop, Level, Result);

2385 return disproven || gcdMIVtest(Src, Dst, Result) ||

2386 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurSrcLoop,

2387 CurDstLoop);

2388 }

2389 if (SrcAddRec) {

2390 const SCEV *SrcConst = SrcAddRec->getStart();

2392 const SCEV *DstConst = Dst;

2393 const Loop *CurSrcLoop = SrcAddRec->getLoop();

2394 Level = mapSrcLoop(CurSrcLoop);

2395 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,

2396 CurSrcLoop, Level, Result) ||

2397 gcdMIVtest(Src, Dst, Result);

2398 }

2399 if (DstAddRec) {

2400 const SCEV *DstConst = DstAddRec->getStart();

2402 const SCEV *SrcConst = Src;

2403 const Loop *CurDstLoop = DstAddRec->getLoop();

2404 Level = mapDstLoop(CurDstLoop);

2405 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, CurDstLoop,

2406 CurDstLoop, Level, Result) ||

2407 gcdMIVtest(Src, Dst, Result);

2408 }

2410 return false;

2411}

2412

2413

2414

2415

2416

2417

2418

2419

2420

2421

2422

2423

2424

2425

2426bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,

2428

2429

2430

2431

2432

2433

2434 const SCEV *SrcConst, *DstConst;

2435 const SCEV *SrcCoeff, *DstCoeff;

2436 const Loop *SrcLoop, *DstLoop;

2437

2442 if (SrcAddRec && DstAddRec) {

2443 SrcConst = SrcAddRec->getStart();

2445 SrcLoop = SrcAddRec->getLoop();

2446 DstConst = DstAddRec->getStart();

2448 DstLoop = DstAddRec->getLoop();

2449 } else if (SrcAddRec) {

2450 if (const SCEVAddRecExpr *tmpAddRec =

2452 SrcConst = tmpAddRec->getStart();

2453 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);

2454 SrcLoop = tmpAddRec->getLoop();

2455 DstConst = Dst;

2456 DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE));

2457 DstLoop = SrcAddRec->getLoop();

2458 } else

2460 } else if (DstAddRec) {

2461 if (const SCEVAddRecExpr *tmpAddRec =

2463 DstConst = tmpAddRec->getStart();

2464 DstCoeff = tmpAddRec->getStepRecurrence(*SE);

2465 DstLoop = tmpAddRec->getLoop();

2466 SrcConst = Src;

2467 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));

2468 SrcLoop = DstAddRec->getLoop();

2469 } else

2471 } else

2473 return exactRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop, DstLoop,

2474 Result) ||

2475 gcdMIVtest(Src, Dst, Result) ||

2476 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop,

2477 DstLoop);

2478}

2479

2480

2481

2482

2483bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,

2488 Result.Consistent = false;

2489 return gcdMIVtest(Src, Dst, Result) ||

2490 banerjeeMIVtest(Src, Dst, Loops, Result);

2491}

2492

2493

2494

2495

2496

2497

2500 return Constant->getAPInt();

2503 if (Product->hasNoSignedWrap())

2504 return Constant->getAPInt();

2505 return std::nullopt;

2506}

2507

2508bool DependenceInfo::accumulateCoefficientsGCD(const SCEV *Expr,

2509 const Loop *CurLoop,

2510 const SCEV *&CurLoopCoeff,

2511 APInt &RunningGCD) const {

2512

2513

2514 if (RunningGCD == 1)

2515 return true;

2516

2518 if (!AddRec) {

2519 assert(isLoopInvariant(Expr, CurLoop) &&

2520 "Expected loop invariant expression");

2521 return true;

2522 }

2523

2527 if (AddRec->getLoop() == CurLoop) {

2528 CurLoopCoeff = Step;

2529 } else {

2531

2532

2533

2534 if (!ConstCoeff)

2535 return false;

2536

2537

2538

2540 }

2541

2542 return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);

2543}

2544

2545

2546

2547

2548

2549

2550

2551

2552

2553

2554

2555

2556

2557

2558

2559

2560

2561

2562

2563bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,

2566 return false;

2567

2569 ++GCDapplications;

2570 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());

2572

2573

2574

2575

2576

2577 const SCEV *Coefficients = Src;

2578 while (const SCEVAddRecExpr *AddRec =

2581

2582

2584 if (!ConstCoeff)

2585 return false;

2587 Coefficients = AddRec->getStart();

2588 }

2589 const SCEV *SrcConst = Coefficients;

2590

2591

2592

2593

2594

2595 Coefficients = Dst;

2596 while (const SCEVAddRecExpr *AddRec =

2599

2600

2602 if (!ConstCoeff)

2603 return false;

2605 Coefficients = AddRec->getStart();

2606 }

2607 const SCEV *DstConst = Coefficients;

2608

2611 if (!Delta)

2612 return false;

2613 LLVM_DEBUG(dbgs() << " Delta = " << *Delta << "\n");

2615 if (!Constant)

2616 return false;

2618 LLVM_DEBUG(dbgs() << " ConstDelta = " << ConstDelta << "\n");

2619 if (ConstDelta == 0)

2620 return false;

2621 LLVM_DEBUG(dbgs() << " RunningGCD = " << RunningGCD << "\n");

2622 APInt Remainder = ConstDelta.srem(RunningGCD);

2623 if (Remainder != 0) {

2624 ++GCDindependence;

2625 return true;

2626 }

2627

2628

2629

2630

2631

2632

2633

2634

2635

2636

2637

2638

2639

2640 LLVM_DEBUG(dbgs() << " ExtraGCD = " << ExtraGCD << '\n');

2641

2642 bool Improved = false;

2643 Coefficients = Src;

2644 while (const SCEVAddRecExpr *AddRec =

2646 Coefficients = AddRec->getStart();

2647 const Loop *CurLoop = AddRec->getLoop();

2648 RunningGCD = ExtraGCD;

2650 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);

2651

2652 if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||

2653 !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))

2654 return false;

2655

2656 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);

2657

2658

2660 if (!ConstCoeff)

2661

2662

2663 continue;

2665 LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");

2666 if (RunningGCD != 0) {

2667 Remainder = ConstDelta.srem(RunningGCD);

2668 LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");

2669 if (Remainder != 0) {

2670 unsigned Level = mapSrcLoop(CurLoop);

2671 Result.DV[Level - 1].Direction &= ~Dependence::DVEntry::EQ;

2672 Improved = true;

2673 }

2674 }

2675 }

2676 if (Improved)

2677 ++GCDsuccesses;

2679 return false;

2680}

2681

2682

2683

2684

2685

2686

2687

2688

2689

2690

2691

2692

2693

2694

2695

2696

2697

2698

2699

2700

2701

2702

2703

2704

2705

2706

2707

2708

2709

2710

2711

2712

2713

2714

2715bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,

2719 return false;

2720

2722 ++BanerjeeApplications;

2724 const SCEV *A0;

2725 CoefficientInfo *A = collectCoeffInfo(Src, true, A0);

2727 const SCEV *B0;

2728 CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);

2729 BoundInfo *Bound = new BoundInfo[MaxLevels + 1];

2730 const SCEV *Delta = SE->getMinusSCEV(B0, A0);

2731 LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');

2732

2733

2735 for (unsigned K = 1; K <= MaxLevels; ++K) {

2736 Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;

2739 findBoundsALL(A, B, Bound, K);

2740#ifndef NDEBUG

2744 else

2748 else

2750#endif

2751 }

2752

2753

2754 bool Disproved = false;

2756

2757 unsigned DepthExpanded = 0;

2758 unsigned NewDeps =

2759 exploreDirections(1, A, B, Bound, Loops, DepthExpanded, Delta);

2760 if (NewDeps > 0) {

2761 bool Improved = false;

2762 for (unsigned K = 1; K <= CommonLevels; ++K) {

2764 unsigned Old = Result.DV[K - 1].Direction;

2765 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;

2766 Improved |= Old != Result.DV[K - 1].Direction;

2767 if ( Result .DV[K - 1].Direction) {

2768 Improved = false;

2769 Disproved = true;

2770 break;

2771 }

2772 }

2773 }

2774 if (Improved)

2775 ++BanerjeeSuccesses;

2776 } else {

2777 ++BanerjeeIndependence;

2778 Disproved = true;

2779 }

2780 } else {

2781 ++BanerjeeIndependence;

2782 Disproved = true;

2783 }

2784 delete[] Bound;

2785 delete[] A;

2786 delete[] B;

2787 return Disproved;

2788}

2789

2790

2791

2792

2793

2794

2795unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,

2796 CoefficientInfo *B, BoundInfo *Bound,

2798 unsigned &DepthExpanded,

2799 const SCEV *Delta) const {

2800

2801

2802

2803

2805 LLVM_DEBUG(dbgs() << "Number of common levels exceeded the threshold. MIV "

2806 "direction exploration is terminated.\n");

2807 for (unsigned K = 1; K <= CommonLevels; ++K)

2810 return 1;

2811 }

2812

2813 if (Level > CommonLevels) {

2814

2816 for (unsigned K = 1; K <= CommonLevels; ++K) {

2818 Bound[K].DirSet |= Bound[K].Direction;

2819#ifndef NDEBUG

2823 break;

2826 break;

2829 break;

2832 break;

2833 default:

2835 }

2836#endif

2837 }

2838 }

2840 return 1;

2841 }

2842 if (Loops[Level]) {

2843 if (Level > DepthExpanded) {

2844 DepthExpanded = Level;

2845

2846 findBoundsLT(A, B, Bound, Level);

2847 findBoundsGT(A, B, Bound, Level);

2848 findBoundsEQ(A, B, Bound, Level);

2849#ifndef NDEBUG

2850 LLVM_DEBUG(dbgs() << "\tBound for level = " << Level << '\n');

2854 << '\t');

2855 else

2859 << '\n');

2860 else

2865 << '\t');

2866 else

2870 << '\n');

2871 else

2876 << '\t');

2877 else

2881 << '\n');

2882 else

2884#endif

2885 }

2886

2887 unsigned NewDeps = 0;

2888

2889

2891 NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,

2892 Delta);

2893

2894

2896 NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,

2897 Delta);

2898

2899

2901 NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,

2902 Delta);

2903

2905 return NewDeps;

2906 } else

2907 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,

2908 Delta);

2909}

2910

2911

2912bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,

2913 BoundInfo *Bound, const SCEV *Delta) const {

2914 Bound[Level].Direction = DirKind;

2915 if (const SCEV *LowerBound = getLowerBound(Bound))

2917 return false;

2918 if (const SCEV *UpperBound = getUpperBound(Bound))

2920 return false;

2921 return true;

2922}

2923

2924

2925

2926

2927

2928

2929

2930

2931

2932

2933

2934

2935

2936

2937

2938

2939void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,

2940 BoundInfo *Bound, unsigned K) const {

2942 nullptr;

2944 nullptr;

2945 if (Bound[K].Iterations) {

2947 SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), Bound[K].Iterations);

2949 SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), Bound[K].Iterations);

2950 } else {

2951

2954 SE->getZero(A[K].Coeff->getType());

2957 SE->getZero(A[K].Coeff->getType());

2958 }

2959}

2960

2961

2962

2963

2964

2965

2966

2967

2968

2969

2970

2971

2972

2973

2974

2975

2976void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,

2977 BoundInfo *Bound, unsigned K) const {

2979 nullptr;

2981 nullptr;

2982 if (Bound[K].Iterations) {

2983 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);

2984 const SCEV *NegativePart = getNegativePart(Delta);

2986 SE->getMulExpr(NegativePart, Bound[K].Iterations);

2987 const SCEV *PositivePart = getPositivePart(Delta);

2989 SE->getMulExpr(PositivePart, Bound[K].Iterations);

2990 } else {

2991

2992

2993 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);

2994 const SCEV *NegativePart = getNegativePart(Delta);

2995 if (NegativePart->isZero())

2997 const SCEV *PositivePart = getPositivePart(Delta);

2998 if (PositivePart->isZero())

3000 }

3001}

3002

3003

3004

3005

3006

3007

3008

3009

3010

3011

3012

3013

3014

3015

3016void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,

3017 BoundInfo *Bound, unsigned K) const {

3019 nullptr;

3021 nullptr;

3022 if (Bound[K].Iterations) {

3023 const SCEV *Iter_1 = SE->getMinusSCEV(

3024 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));

3025 const SCEV *NegPart =

3026 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));

3028 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);

3029 const SCEV *PosPart =

3030 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));

3032 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);

3033 } else {

3034

3035

3036 const SCEV *NegPart =

3037 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));

3038 if (NegPart->isZero())

3040 const SCEV *PosPart =

3041 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));

3042 if (PosPart->isZero())

3044 }

3045}

3046

3047

3048

3049

3050

3051

3052

3053

3054

3055

3056

3057

3058

3059

3060void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,

3061 BoundInfo *Bound, unsigned K) const {

3063 nullptr;

3065 nullptr;

3066 if (Bound[K].Iterations) {

3067 const SCEV *Iter_1 = SE->getMinusSCEV(

3068 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));

3069 const SCEV *NegPart =

3070 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));

3072 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);

3073 const SCEV *PosPart =

3074 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));

3076 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);

3077 } else {

3078

3079

3080 const SCEV *NegPart =

3081 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));

3082 if (NegPart->isZero())

3084 const SCEV *PosPart =

3085 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));

3086 if (PosPart->isZero())

3088 }

3089}

3090

3091

3092const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const {

3093 return SE->getSMaxExpr(X, SE->getZero(X->getType()));

3094}

3095

3096

3097const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const {

3098 return SE->getSMinExpr(X, SE->getZero(X->getType()));

3099}

3100

3101

3102

3103

3104DependenceInfo::CoefficientInfo *

3105DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,

3107 const SCEV *Zero = SE->getZero(Subscript->getType());

3108 CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];

3109 for (unsigned K = 1; K <= MaxLevels; ++K) {

3110 CI[K].Coeff = Zero;

3111 CI[K].PosPart = Zero;

3112 CI[K].NegPart = Zero;

3113 CI[K].Iterations = nullptr;

3114 }

3116 const Loop *L = AddRec->getLoop();

3117 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);

3119 CI[K].PosPart = getPositivePart(CI[K].Coeff);

3120 CI[K].NegPart = getNegativePart(CI[K].Coeff);

3121 CI[K].Iterations = collectUpperBound(L, Subscript->getType());

3122 Subscript = AddRec->getStart();

3123 }

3125#ifndef NDEBUG

3127 for (unsigned K = 1; K <= MaxLevels; ++K) {

3128 LLVM_DEBUG(dbgs() << "\t " << K << "\t" << *CI[K].Coeff);

3134 if (CI[K].Iterations)

3136 else

3139 }

3140 LLVM_DEBUG(dbgs() << "\t Constant = " << *Subscript << '\n');

3141#endif

3142 return CI;

3143}

3144

3145

3146

3147

3148

3149const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const {

3150 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];

3151 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {

3153 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);

3154 else

3155 Sum = nullptr;

3156 }

3157 return Sum;

3158}

3159

3160

3161

3162

3163

3164const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const {

3165 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];

3166 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {

3168 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);

3169 else

3170 Sum = nullptr;

3171 }

3172 return Sum;

3173}

3174

3175

3176

3177

3178

3185 Loop *SrcLoop = LI->getLoopFor(Src->getParent());

3186 Loop *DstLoop = LI->getLoopFor(Dst->getParent());

3187 const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop);

3188 const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop);

3189 const SCEVUnknown *SrcBase =

3191 const SCEVUnknown *DstBase =

3193

3194 if (!SrcBase || !DstBase || SrcBase != DstBase)

3195 return false;

3196

3198

3199 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,

3200 SrcSubscripts, DstSubscripts) &&

3201 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,

3202 SrcSubscripts, DstSubscripts))

3203 return false;

3204

3205 assert(isLoopInvariant(SrcBase, SrcLoop) &&

3206 isLoopInvariant(DstBase, DstLoop) &&

3207 "Expected SrcBase and DstBase to be loop invariant");

3208

3209 int Size = SrcSubscripts.size();

3211 dbgs() << "\nSrcSubscripts: ";

3212 for (int I = 0; I < Size; I++)

3213 dbgs() << *SrcSubscripts[I];

3214 dbgs() << "\nDstSubscripts: ";

3215 for (int I = 0; I < Size; I++)

3216 dbgs() << *DstSubscripts[I];

3217 });

3218

3219

3220

3221

3222

3224 SCEVMonotonicityChecker MonChecker(SE);

3225 const Loop *OutermostLoop = SrcLoop ? SrcLoop->getOutermostLoop() : nullptr;

3226 for (int I = 0; I < Size; ++I) {

3227 Pair[I].Src = SrcSubscripts[I];

3228 Pair[I].Dst = DstSubscripts[I];

3229 unifySubscriptType(&Pair[I]);

3230

3232 if (MonChecker.checkMonotonicity(Pair[I].Src, OutermostLoop).isUnknown())

3233 return false;

3234 if (MonChecker.checkMonotonicity(Pair[I].Dst, OutermostLoop).isUnknown())

3235 return false;

3236 }

3237 }

3238

3239 return true;

3240}

3241

3242

3243

3244

3245bool DependenceInfo::tryDelinearizeFixedSize(

3250 const SCEVUnknown *SrcBase =

3252 const SCEVUnknown *DstBase =

3254 assert(SrcBase && DstBase && SrcBase == DstBase &&

3255 "expected src and dst scev unknowns to be equal");

3256 });

3257

3258 const SCEV *ElemSize = SE->getElementSize(Src);

3259 assert(ElemSize == SE->getElementSize(Dst) && "Different element sizes");

3262 SrcSubscripts, SrcSizes, ElemSize) ||

3264 DstSubscripts, DstSizes, ElemSize))

3265 return false;

3266

3267

3268

3269 if (SrcSizes.size() != DstSizes.size() ||

3270 !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {

3271 SrcSubscripts.clear();

3272 DstSubscripts.clear();

3273 return false;

3274 }

3275

3276 assert(SrcSubscripts.size() == DstSubscripts.size() &&

3277 "Expected equal number of entries in the list of SrcSubscripts and "

3278 "DstSubscripts.");

3279

3282

3283

3284

3285

3286

3287

3288

3292 SrcSubscripts.clear();

3293 DstSubscripts.clear();

3294 return false;

3295 }

3296 }

3298 dbgs() << "Delinearized subscripts of fixed-size array\n"

3299 << "SrcGEP:" << *SrcPtr << "\n"

3300 << "DstGEP:" << *DstPtr << "\n";

3301 });

3302 return true;

3303}

3304

3305bool DependenceInfo::tryDelinearizeParametricSize(

3309

3312 const SCEVUnknown *SrcBase =

3314 const SCEVUnknown *DstBase =

3316 assert(SrcBase && DstBase && SrcBase == DstBase &&

3317 "expected src and dst scev unknowns to be equal");

3318

3319 const SCEV *ElementSize = SE->getElementSize(Src);

3320 if (ElementSize != SE->getElementSize(Dst))

3321 return false;

3322

3323 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);

3324 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);

3325

3328 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())

3329 return false;

3330

3331

3335

3336

3339

3340

3343

3344

3345 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||

3346 SrcSubscripts.size() != DstSubscripts.size())

3347 return false;

3348

3349

3350

3351

3352

3353

3354

3358 return false;

3359

3360 return true;

3361}

3362

3363

3364

3365#ifndef NDEBUG

3366

3368 dbgs() << "{";

3369 for (unsigned VI : BV.set_bits()) {

3370 dbgs() << VI;

3372 dbgs() << ' ';

3373 }

3374 dbgs() << "}\n";

3375}

3376#endif

3377

3379 FunctionAnalysisManager::Invalidator &Inv) {

3380

3383 return true;

3384

3385

3386 return Inv.invalidate<AAManager>(F, PA) ||

3389}

3390

3391

3392

3393

3394

3395

3396

3397

3398

3399

3400std::unique_ptr

3402 bool UnderRuntimeAssumptions) {

3404 bool PossiblyLoopIndependent = true;

3405 if (Src == Dst)

3406 PossiblyLoopIndependent = false;

3407

3408 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))

3409

3410 return nullptr;

3411

3413

3414 LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n");

3415 return std::make_unique(Src, Dst,

3417 }

3418

3421

3425

3426 LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n");

3427 return std::make_unique(Src, Dst,

3430

3432 return nullptr;

3434 break;

3435 }

3436

3439

3440

3441 LLVM_DEBUG(dbgs() << "can't analyze must alias with different sizes\n");

3442 return std::make_unique(Src, Dst,

3444 }

3445

3448 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);

3449 const SCEV *DstSCEV = SE->getSCEV(DstPtr);

3450 LLVM_DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n");

3451 LLVM_DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n");

3452 const SCEV *SrcBase = SE->getPointerBase(SrcSCEV);

3453 const SCEV *DstBase = SE->getPointerBase(DstSCEV);

3454 if (SrcBase != DstBase) {

3455

3456

3457

3458

3459

3460

3461 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");

3462 return std::make_unique(Src, Dst,

3464 }

3465

3466

3467

3468

3469

3470 Loop *SrcLoop = LI->getLoopFor(Src->getParent());

3471 Loop *DstLoop = LI->getLoopFor(Dst->getParent());

3472 if (!isLoopInvariant(SrcBase, SrcLoop) ||

3473 !isLoopInvariant(DstBase, DstLoop)) {

3474 LLVM_DEBUG(dbgs() << "The base pointer is not loop invariant.\n");

3475 return std::make_unique(Src, Dst,

3477 }

3478

3480 const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);

3481 const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);

3482

3483

3484 if (!SE->isKnownMultipleOf(SrcEv, EltSize, Assume) ||

3485 !SE->isKnownMultipleOf(DstEv, EltSize, Assume)) {

3486 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different offsets\n");

3487 return std::make_unique(Src, Dst,

3489 }

3490

3491

3492 if (!Assume.empty() && !UnderRuntimeAssumptions)

3493 return std::make_unique(Src, Dst,

3495

3496 unsigned Pairs = 1;

3498 Pair[0].Src = SrcEv;

3499 Pair[0].Dst = DstEv;

3500

3501 SCEVMonotonicityChecker MonChecker(SE);

3502 const Loop *OutermostLoop = SrcLoop ? SrcLoop->getOutermostLoop() : nullptr;

3504 if (MonChecker.checkMonotonicity(Pair[0].Src, OutermostLoop).isUnknown() ||

3505 MonChecker.checkMonotonicity(Pair[0].Dst, OutermostLoop).isUnknown())

3506 return std::make_unique(Src, Dst,

3508

3510 if (tryDelinearize(Src, Dst, Pair)) {

3512 Pairs = Pair.size();

3513 }

3514 }

3515

3516

3517 establishNestingLevels(Src, Dst);

3518

3519 LLVM_DEBUG(dbgs() << " common nesting levels = " << CommonLevels << "\n");

3520 LLVM_DEBUG(dbgs() << " maximum nesting levels = " << MaxLevels << "\n");

3521 LLVM_DEBUG(dbgs() << " SameSD nesting levels = " << SameSDLevels << "\n");

3522

3523

3524 CommonLevels += SameSDLevels;

3525 MaxLevels -= SameSDLevels;

3526 if (SameSDLevels > 0) {

3527

3528

3529 for (unsigned P = 0; P < Pairs; ++P) {

3531 Subscript::ClassificationKind TestClass =

3532 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),

3533 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), Loops);

3534

3535 if (TestClass != Subscript::ZIV && TestClass != Subscript::SIV &&

3536 TestClass != Subscript::RDIV) {

3537

3538 CommonLevels -= SameSDLevels;

3539 MaxLevels += SameSDLevels;

3540 SameSDLevels = 0;

3541 break;

3542 }

3543 }

3544 }

3545

3546 if (SameSDLevels > 0)

3547 SameSDLoopsCount++;

3548

3550 PossiblyLoopIndependent, CommonLevels);

3551 ++TotalArrayPairs;

3552

3553 for (unsigned P = 0; P < Pairs; ++P) {

3554 assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");

3555 assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");

3556 Pair[P].Loops.resize(MaxLevels + 1);

3557 Pair[P].GroupLoops.resize(MaxLevels + 1);

3558 Pair[P].Group.resize(Pairs);

3559 removeMatchingExtensions(&Pair[P]);

3560 Pair[P].Classification =

3561 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), Pair[P].Dst,

3562 LI->getLoopFor(Dst->getParent()), Pair[P].Loops);

3563 Pair[P].GroupLoops = Pair[P].Loops;

3564 Pair[P].Group.set(P);

3566 LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");

3567 LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");

3568 LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");

3571 }

3572

3573

3574 for (unsigned SI = 0; SI < Pairs; ++SI) {

3576 switch (Pair[SI].Classification) {

3577 case Subscript::NonLinear:

3578

3579 ++NonlinearSubscriptPairs;

3580 collectCommonLoops(Pair[SI].Src, LI->getLoopFor(Src->getParent()),

3581 Pair[SI].Loops);

3582 collectCommonLoops(Pair[SI].Dst, LI->getLoopFor(Dst->getParent()),

3583 Pair[SI].Loops);

3584 Result.Consistent = false;

3585 break;

3586 case Subscript::ZIV:

3588 if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))

3589 return nullptr;

3590 break;

3591 case Subscript::SIV: {

3593 unsigned Level;

3594 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result,

3595 UnderRuntimeAssumptions))

3596 return nullptr;

3597 break;

3598 }

3599 case Subscript::RDIV:

3601 if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))

3602 return nullptr;

3603 break;

3604 case Subscript::MIV:

3606 if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))

3607 return nullptr;

3608 break;

3609 }

3610 }

3611

3612

3614 for (unsigned SI = 0; SI < Pairs; ++SI)

3615 CompleteLoops |= Pair[SI].Loops;

3616 for (unsigned II = 1; II <= CommonLevels; ++II)

3617 if (CompleteLoops[II])

3618 Result.DV[II - 1].Scalar = false;

3619

3620

3621

3622

3623 for (unsigned II = 1; II <= Result.getLevels(); ++II) {

3625 if (Result.DV[II - 1].Distance == nullptr)

3626 Result.DV[II - 1].Distance = SE->getZero(SrcSCEV->getType());

3627 else

3628 assert(Result.DV[II - 1].Distance->isZero() &&

3629 "Inconsistency between distance and direction");

3630 }

3631

3632#ifndef NDEBUG

3633

3634

3635 const SCEV *Distance = Result.getDistance(II);

3636 if (Distance && Distance->isZero())

3638 "Distance is zero, but direction is not EQ");

3639#endif

3640 }

3641

3642 if (SameSDLevels > 0) {

3643

3644

3645 assert(CommonLevels >= SameSDLevels);

3646 CommonLevels -= SameSDLevels;

3647 MaxLevels += SameSDLevels;

3648 std::unique_ptrFullDependence::DVEntry\[\] DV, DVSameSD;

3649 DV = std::make_uniqueFullDependence::DVEntry\[\](CommonLevels);

3650 DVSameSD = std::make_uniqueFullDependence::DVEntry\[\](SameSDLevels);

3651 for (unsigned Level = 0; Level < CommonLevels; ++Level)

3652 DV[Level] = Result.DV[Level];

3653 for (unsigned Level = 0; Level < SameSDLevels; ++Level)

3654 DVSameSD[Level] = Result.DV[CommonLevels + Level];

3655 Result.DV = std::move(DV);

3656 Result.DVSameSD = std::move(DVSameSD);

3657 Result.Levels = CommonLevels;

3658 Result.SameSDLevels = SameSDLevels;

3659

3660 Result.Consistent = false;

3661 }

3662

3663 if (PossiblyLoopIndependent) {

3664

3665

3666

3667 for (unsigned II = 1; II <= CommonLevels; ++II) {

3669 Result.LoopIndependent = false;

3670 break;

3671 }

3672 }

3673 } else {

3674

3675

3676

3677 bool AllEqual = true;

3678 for (unsigned II = 1; II <= CommonLevels; ++II) {

3680 AllEqual = false;

3681 break;

3682 }

3683 }

3684 if (AllEqual && Result.Assumptions.getPredicates().empty())

3685 return nullptr;

3686 }

3687

3688 return std::make_unique(std::move(Result));

3689}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

Expand Atomic instructions

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define clEnumValN(ENUMVAL, FLAGNAME, DESC)

static cl::opt< DependenceTestType > EnableDependenceTest("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test.")))

static bool isLoadOrStore(const Instruction *I)

Definition DependenceAnalysis.cpp:798

static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)

Definition DependenceAnalysis.cpp:386

static bool isDependenceTestEnabled(DependenceTestType Test)

Returns true iff Test is enabled.

Definition DependenceAnalysis.cpp:1234

static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)

Definition DependenceAnalysis.cpp:1582

static void dumpSmallBitVector(SmallBitVector &BV)

Definition DependenceAnalysis.cpp:3367

static APInt ceilingOfQuotient(const APInt &A, const APInt &B)

Definition DependenceAnalysis.cpp:1624

static APInt floorOfQuotient(const APInt &A, const APInt &B)

Definition DependenceAnalysis.cpp:1612

static const SCEV * minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)

Returns A - B if it guaranteed not to signed wrap.

Definition DependenceAnalysis.cpp:1200

static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)

Definition DependenceAnalysis.cpp:763

static std::pair< std::optional< APInt >, std::optional< APInt > > inferDomainOfAffine(const APInt &A, const APInt &B, const std::optional< APInt > &UB)

Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible r...

Definition DependenceAnalysis.cpp:1666

static std::optional< APInt > getConstantCoefficient(const SCEV *Expr)

Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doe...

Definition DependenceAnalysis.cpp:2498

static const SCEV * absSCEVNoSignedOverflow(const SCEV *A, ScalarEvolution &SE)

Returns the absolute value of A.

Definition DependenceAnalysis.cpp:1221

static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)

Definition DependenceAnalysis.cpp:1854

static const SCEV * mulSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)

Returns A * B if it guaranteed not to signed wrap.

Definition DependenceAnalysis.cpp:1209

static cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references."))

static cl::opt< bool > EnableMonotonicityCheck("da-enable-monotonicity-check", cl::init(false), cl::Hidden, cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown."))

static cl::opt< bool > DumpMonotonicityReport("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc("When printing analysis, dump the results of monotonicity checks."))

static cl::opt< unsigned > MIVMaxLevelThreshold("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))

static cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))

Module.h This file contains the declarations for the Module class.

Loop::LoopBounds::Direction Direction

uint64_t IntrinsicInst * II

FunctionAnalysisManager FAM

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

static SymbolRef::Type getType(const Symbol *Sym)

A manager for alias analyses.

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

Class for arbitrary precision integers.

static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)

APInt abs() const

Get the absolute value.

bool sgt(const APInt &RHS) const

Signed greater than comparison.

unsigned getBitWidth() const

Return the number of bits in the APInt.

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

LLVM_ABI APInt sdiv(const APInt &RHS) const

Signed division function for APInt.

bool sle(const APInt &RHS) const

Signed less or equal comparison.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

LLVM_ABI APInt srem(const APInt &RHS) const

Function for signed remainder operation.

bool slt(const APInt &RHS) const

Signed less than comparison.

static APInt getZero(unsigned numBits)

Get the '0' value for the specified bit-width.

bool sge(const APInt &RHS) const

Signed greater or equal comparison.

The possible results of an alias query.

@ MayAlias

The two locations may or may not alias.

@ NoAlias

The two locations do not alias at all.

@ PartialAlias

The two locations alias, but only due to a partial overlap.

@ MustAlias

The two locations precisely alias each other.

This templated class represents "all analyses that operate over " (e....

Represent the analysis usage information of a pass.

void setPreservesAll()

Set by analyses that do not transform their input at all.

AnalysisUsage & addRequiredTransitive()

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...

void enableCrossIterationMode()

Assume that values may come from different cycle iterations.

bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_SLE

signed less or equal

@ ICMP_SGT

signed greater than

@ ICMP_SGE

signed greater or equal

This is an important base class in LLVM.

A parsed version of the target data layout string in and methods for querying it.

Legacy pass manager pass to access dependence information.

void getAnalysisUsage(AnalysisUsage &) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition DependenceAnalysis.cpp:212

bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Definition DependenceAnalysis.cpp:200

void print(raw_ostream &, const Module *=nullptr) const override

print - Print out the internal state of the pass.

Definition DependenceAnalysis.cpp:446

DependenceInfo & getDI() const

Definition DependenceAnalysis.cpp:208

DependenceAnalysisWrapperPass()

Definition DependenceAnalysis.cpp:193

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

Definition DependenceAnalysis.cpp:210

AnalysisPass to compute dependence information in a function.

LLVM_ABI Result run(Function &F, FunctionAnalysisManager &FAM)

Definition DependenceAnalysis.cpp:174

DependenceInfo - This class is the main dependence-analysis driver.

LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)

Handle transitive invalidation when the cached analysis results go away.

Definition DependenceAnalysis.cpp:3378

LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)

depends - Tests for a dependence between the Src and Dst instructions.

Definition DependenceAnalysis.cpp:3401

void dumpImp(raw_ostream &OS, bool IsSameSD=false) const

dumpImp - For debugging purposes.

Definition DependenceAnalysis.cpp:717

Dependence(Dependence &&)=default

SCEVUnionPredicate getRuntimeAssumptions() const

getRuntimeAssumptions - Returns the runtime assumptions under which this Dependence relation is valid...

virtual bool isConfused() const

isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...

virtual unsigned getSameSDLevels() const

getSameSDLevels - Returns the number of separate SameSD loops surrounding the source and destination ...

virtual const SCEV * getDistance(unsigned Level, bool SameSD=false) const

getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.

virtual bool isPeelLast(unsigned Level, bool SameSD=false) const

isPeelLast - Returns true if peeling the last iteration from this regular or SameSD loop level will b...

virtual bool isConsistent() const

isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...

virtual unsigned getLevels() const

getLevels - Returns the number of common loops surrounding the source and destination of the dependen...

virtual unsigned getDirection(unsigned Level, bool SameSD=false) const

getDirection - Returns the direction associated with a particular common or SameSD level.

virtual bool isScalar(unsigned Level, bool SameSD=false) const

isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...

Definition DependenceAnalysis.cpp:490

bool isFlow() const

isFlow - Returns true if this is a flow (aka true) dependence.

Definition DependenceAnalysis.cpp:477

virtual bool isPeelFirst(unsigned Level, bool SameSD=false) const

isPeelFirst - Returns true if peeling the first iteration from this regular or SameSD loop level will...

bool isInput() const

isInput - Returns true if this is an input dependence.

Definition DependenceAnalysis.cpp:467

bool isAnti() const

isAnti - Returns true if this is an anti dependence.

Definition DependenceAnalysis.cpp:482

virtual bool isLoopIndependent() const

isLoopIndependent - Returns true if this is a loop-independent dependence.

bool isOutput() const

isOutput - Returns true if this is an output dependence.

Definition DependenceAnalysis.cpp:472

void dump(raw_ostream &OS) const

dump - For debugging purposes, dumps a dependence to OS.

Definition DependenceAnalysis.cpp:685

virtual bool inSameSDLoops(unsigned Level) const

inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...

Class representing an expression and its matching format.

FullDependence - This class represents a dependence between two memory references in a function.

FullDependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &Assumes, bool PossiblyLoopIndependent, unsigned Levels)

Definition DependenceAnalysis.cpp:495

unsigned getDirection(unsigned Level, bool SameSD=false) const override

getDirection - Returns the direction associated with a particular common or SameSD level.

Definition DependenceAnalysis.cpp:566

bool isScalar(unsigned Level, bool SameSD=false) const override

isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...

Definition DependenceAnalysis.cpp:579

bool isDirectionNegative() const override

Check if the direction vector is negative.

Definition DependenceAnalysis.cpp:522

const SCEV * getDistance(unsigned Level, bool SameSD=false) const override

getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.

Definition DependenceAnalysis.cpp:572

DVEntry getDVEntry(unsigned Level, bool IsSameSD) const

getDVEntry - Returns the DV entry associated with a regular or a SameSD level.

bool isPeelLast(unsigned Level, bool SameSD=false) const override

isPeelLast - Returns true if peeling the last iteration from this regular or SameSD loop level will b...

Definition DependenceAnalysis.cpp:591

bool isPeelFirst(unsigned Level, bool SameSD=false) const override

isPeelFirst - Returns true if peeling the first iteration from this regular or SameSD loop level will...

Definition DependenceAnalysis.cpp:585

bool inSameSDLoops(unsigned Level) const override

inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...

Definition DependenceAnalysis.cpp:598

bool normalize(ScalarEvolution *SE) override

If the direction vector is negative, normalize the direction vector to make it non-negative.

Definition DependenceAnalysis.cpp:535

FunctionPass class - This class is used to implement most global optimizations.

Class to represent integer types.

unsigned getBitWidth() const

Get the number of bits in this IntegerType.

An instruction for reading from memory.

Analysis pass that exposes the LoopInfo for a function.

bool isOutermost() const

Return true if the loop does not have a parent (natural) loop.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

const LoopT * getOutermostLoop() const

Get the outermost loop in which this loop is contained.

unsigned getLoopDepth() const

Return the nesting level of this loop.

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

The legacy pass manager's analysis pass to compute loop information.

This class represents a loop nest and can be used to query its properties.

Represents a single loop in the control flow graph.

Representation for a specific memory location.

static LLVM_ABI MemoryLocation get(const LoadInst *LI)

Return a location with information about the memory reference by the given instruction.

LocationSize Size

The maximum size of the location, in address-units, or UnknownSize if the size is not known.

static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())

Return a location that may access any location before or after Ptr, while remaining within the underl...

AAMDNodes AATags

The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...

const Value * Ptr

The address of the start of the location.

A Module instance is used to store all the information related to an LLVM module.

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

This node represents a polynomial recurrence on the trip count of the specified loop.

const SCEV * getStart() const

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

const Loop * getLoop() const

const SCEV * getOperand() const

This class represents a constant integer value.

const APInt & getAPInt() const

bool hasNoSignedWrap() const

This class represents a composition of other SCEV predicates, and is the class that most clients will...

This class represents an analyzed expression in the program.

LLVM_ABI bool isOne() const

Return true if the expression is a constant one.

LLVM_ABI bool isZero() const

Return true if the expression is a constant zero.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

Analysis pass that exposes the ScalarEvolution for a function.

The main scalar evolution driver.

LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)

Return the SCEV object corresponding to -V.

LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)

LLVM_ABI const SCEV * removePointerBase(const SCEV *S)

Compute an expression equivalent to S - getPointerBase(S).

LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)

Return a SCEV expression for the specified value at the specified scope in the program.

LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)

Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?

LLVM_ABI const SCEV * getConstant(ConstantInt *V)

LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical multiply expression, or something simpler if possible.

LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...

iterator_range< const_set_bits_iterator > set_bits() const

int find_next(unsigned Prev) const

Returns the index of the next set bit following the "Prev" bit.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

An instruction for storing to memory.

The instances of the Type class are immutable: once they are created, they are never changed.

bool isIntegerTy() const

True if this is an instance of IntegerType.

LLVM Value Representation.

This class implements an extremely fast bulk output stream that can only output to a stream.

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Abstract Attribute helper functions.

const APInt & smin(const APInt &A, const APInt &B)

Determine the smaller of two APInts considered to be signed.

const APInt & smax(const APInt &A, const APInt &B)

Determine the larger of two APInts considered to be signed.

LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)

Compute GCD of two unsigned APInt values.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ BasicBlock

Various leaf nodes.

@ TB

TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...

ValuesClass values(OptsTy... Options)

Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

InstIterator< SymbolTableList< BasicBlock >, Function::iterator, BasicBlock::iterator, Instruction > inst_iterator

void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)

Collect parametric terms occurring in step expressions (first step of delinearization).

void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)

Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

const Value * getLoadStorePointerOperand(const Value *V)

A helper function that returns the pointer operand of a load or store instruction.

inst_iterator inst_begin(Function *F)

void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)

Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...

bool delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)

Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an acces...

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

inst_iterator inst_end(Function *F)

@ SMin

Signed integer min implemented in terms of select(cmp()).

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

bool validateDelinearizationResult(ScalarEvolution &SE, ArrayRef< const SCEV * > Sizes, ArrayRef< const SCEV * > Subscripts, const Value *Ptr=nullptr)

Check that each subscript in Subscripts is within the corresponding size in Sizes.

LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)

This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....

LLVM_ABI bool isIdentifiedObject(const Value *V)

Return true if this pointer refers to a distinct and identifiable object.

LLVM_ABI FunctionPass * createDependenceAnalysisWrapperPass()

createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.

Definition DependenceAnalysis.cpp:196

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

A special type used by analysis passes to provide an address that identifies that particular analysis...

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition DependenceAnalysis.cpp:454

Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...

This class defines a simple visitor class that may be used for various SCEV analysis purposes.