DependenceAnalysis.cpp Source File (original) (raw)

68using namespace llvm;

70#define DEBUG_TYPE "da"

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

76 STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs");

77 STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs");

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

79 STATISTIC(ZIVapplications, "ZIV applications");

80 STATISTIC(ZIVindependence, "ZIV independence");

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

97 STATISTIC(DeltaApplications, "Delta applications");

98 STATISTIC(DeltaSuccesses, "Delta successes");

99 STATISTIC(DeltaIndependence, "Delta independence");

100 STATISTIC(DeltaPropagations, "Delta propagations");

101 STATISTIC(GCDapplications, "GCD applications");

103 STATISTIC(GCDindependence, "GCD independence");

104 STATISTIC(BanerjeeApplications, "Banerjee applications");

105 STATISTIC(BanerjeeIndependence, "Banerjee independence");

106 STATISTIC(BanerjeeSuccesses, "Banerjee successes");

107

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

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

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

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

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

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

118

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

122 "explore MIV direction vectors."));

123

124

125

126

133}

134

136

138 "Dependence Analysis", true, true)

144

146

150}

151

154}

155

157 auto &AA = getAnalysis().getAAResults();

158 auto &SE = getAnalysis().getSE();

159 auto &LI = getAnalysis().getLoopInfo();

161 return false;

162}

163

165

167

173}

174

175

176

177

178

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

183 ++SrcI) {

184 if (SrcI->mayReadOrWriteMemory()) {

186 DstI != DstE; ++DstI) {

187 if (DstI->mayReadOrWriteMemory()) {

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

189 OS << " da analyze - ";

190 if (auto D = DA->depends(&*SrcI, &*DstI, true)) {

191

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

193 OS << "normalized - ";

194 D->dump(OS);

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

196 if (D->isSplitable(Level)) {

197 OS << " da analyze - split level = " << Level;

198 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);

199 OS << "!\n";

200 }

201 }

202 }

203 else

204 OS << "none!\n";

205 }

206 }

207 }

208 }

209}

210

212 const Module *) const {

214 getAnalysis().getSE(), false);

215}

216

219 OS << "'Dependence Analysis' for function '" << F.getName() << "':\n";

222 NormalizeResults);

224}

225

226

227

228

229

232}

233

234

235

238}

239

240

241

244}

245

246

247

250}

251

252

253

254

255

256

258 return false;

259}

260

261

262

263

264

266 bool PossiblyLoopIndependent,

267 unsigned CommonLevels)

268 : Dependence(Source, Destination), Levels(CommonLevels),

269 LoopIndependent(PossiblyLoopIndependent) {

270 Consistent = true;

271 if (CommonLevels)

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

273}

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

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

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

294 continue;

297 return true;

298 return false;

299 }

300 return false;

301}

302

305 return false;

306

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

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

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

312

313

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

320

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

322 DV[Level - 1].Distance =

324 }

325

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

328 return true;

329}

330

331

332

333

335 assert(0 < Level && Level <= Levels && "Level out of range");

336 return DV[Level - 1].Direction;

337}

338

339

340

342 assert(0 < Level && Level <= Levels && "Level out of range");

343 return DV[Level - 1].Distance;

344}

345

346

347

348

349

351 assert(0 < Level && Level <= Levels && "Level out of range");

352 return DV[Level - 1].Scalar;

353}

354

355

356

357

359 assert(0 < Level && Level <= Levels && "Level out of range");

360 return DV[Level - 1].PeelFirst;

361}

362

363

364

365

367 assert(0 < Level && Level <= Levels && "Level out of range");

368 return DV[Level - 1].PeelLast;

369}

370

371

372

374 assert(0 < Level && Level <= Levels && "Level out of range");

375 return DV[Level - 1].Splitable;

376}

377

378

379

380

381

382

383

384const SCEV *DependenceInfo::Constraint::getX() const {

385 assert(Kind == Point && "Kind should be Point");

386 return A;

387}

388

389

390

391

392const SCEV *DependenceInfo::Constraint::getY() const {

393 assert(Kind == Point && "Kind should be Point");

394 return B;

395}

396

397

398

399

400const SCEV *DependenceInfo::Constraint::getA() const {

401 assert((Kind == Line || Kind == Distance) &&

402 "Kind should be Line (or Distance)");

403 return A;

404}

405

406

407

408

409const SCEV *DependenceInfo::Constraint::getB() const {

410 assert((Kind == Line || Kind == Distance) &&

411 "Kind should be Line (or Distance)");

412 return B;

413}

414

415

416

417

418const SCEV *DependenceInfo::Constraint::getC() const {

419 assert((Kind == Line || Kind == Distance) &&

420 "Kind should be Line (or Distance)");

421 return C;

422}

423

424

425

426

427const SCEV *DependenceInfo::Constraint::getD() const {

428 assert(Kind == Distance && "Kind should be Distance");

429 return SE->getNegativeSCEV(C);

430}

431

432

433

434const Loop *DependenceInfo::Constraint::getAssociatedLoop() const {

435 assert((Kind == Distance || Kind == Line || Kind == Point) &&

436 "Kind should be Distance, Line, or Point");

437 return AssociatedLoop;

438}

439

440void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y,

441 const Loop *CurLoop) {

442 Kind = Point;

443 A = X;

444 B = Y;

445 AssociatedLoop = CurLoop;

446}

447

448void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB,

449 const SCEV *CC, const Loop *CurLoop) {

451 A = AA;

452 B = BB;

454 AssociatedLoop = CurLoop;

455}

456

457void DependenceInfo::Constraint::setDistance(const SCEV *D,

458 const Loop *CurLoop) {

459 Kind = Distance;

460 A = SE->getOne(D->getType());

461 B = SE->getNegativeSCEV(A);

462 C = SE->getNegativeSCEV(D);

463 AssociatedLoop = CurLoop;

464}

465

466void DependenceInfo::Constraint::setEmpty() { Kind = Empty; }

467

468void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) {

469 SE = NewSE;

471}

472

473#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

474

476 if (isEmpty())

477 OS << " Empty\n";

478 else if (isAny())

479 OS << " Any\n";

480 else if (isPoint())

481 OS << " Point is <" << *getX() << ", " << *getY() << ">\n";

482 else if (isDistance())

483 OS << " Distance is " << *getD() <<

484 " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n";

485 else if (isLine())

486 OS << " Line is " << *getA() << "*X + " <<

487 *getB() << "*Y = " << *getC() << "\n";

488 else

489 llvm_unreachable("unknown constraint type in Constraint::dump");

490}

491#endif

492

493

494

495

496

497

498

499

500

501bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {

502 ++DeltaApplications;

506 assert(->isPoint() && "Y must not be a Point");

507 if (X->isAny()) {

508 if (Y->isAny())

509 return false;

510 *X = *Y;

511 return true;

512 }

513 if (X->isEmpty())

514 return false;

515 if (Y->isEmpty()) {

516 X->setEmpty();

517 return true;

518 }

519

520 if (X->isDistance() && Y->isDistance()) {

523 return false;

525 X->setEmpty();

526 ++DeltaSuccesses;

527 return true;

528 }

529

530

531 if (isa(Y->getD())) {

532 *X = *Y;

533 return true;

534 }

535 return false;

536 }

537

538

539

540

541

542

543

544 assert(!(X->isPoint() && Y->isPoint()) &&

545 "We shouldn't ever see X->isPoint() && Y->isPoint()");

546

547 if (X->isLine() && Y->isLine()) {

552

554 Prod1 = SE->getMulExpr(X->getC(), Y->getB());

555 Prod2 = SE->getMulExpr(X->getB(), Y->getC());

557 return false;

559 X->setEmpty();

560 ++DeltaSuccesses;

561 return true;

562 }

563 return false;

564 }

566

575 dyn_cast(SE->getMinusSCEV(C1A2, C2A1));

577 dyn_cast(SE->getMinusSCEV(C1B2, C2B1));

579 dyn_cast(SE->getMinusSCEV(A1B2, A2B1));

581 dyn_cast(SE->getMinusSCEV(A2B1, A1B2));

582 if (!C1B2_C2B1 || !C1A2_C2A1 ||

583 !A1B2_A2B1 || !A2B1_A1B2)

584 return false;

593 APInt Xq = Xtop;

594 APInt Xr = Xtop;

599 if (Xr != 0 || Yr != 0) {

600 X->setEmpty();

601 ++DeltaSuccesses;

602 return true;

603 }

604 LLVM_DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n");

605 if (Xq.slt(0) || Yq.slt(0)) {

606 X->setEmpty();

607 ++DeltaSuccesses;

608 return true;

609 }

611 collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) {

612 const APInt &UpperBound = CUB->getAPInt();

613 LLVM_DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n");

614 if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) {

615 X->setEmpty();

616 ++DeltaSuccesses;

617 return true;

618 }

619 }

622 X->getAssociatedLoop());

623 ++DeltaSuccesses;

624 return true;

625 }

626 return false;

627 }

628

629

630 assert(!(X->isLine() && Y->isPoint()) && "This case should never occur");

631

632 if (X->isPoint() && Y->isLine()) {

633 LLVM_DEBUG(dbgs() << "\t intersect Point and Line\n");

638 return false;

640 X->setEmpty();

641 ++DeltaSuccesses;

642 return true;

643 }

644 return false;

645 }

646

647 llvm_unreachable("shouldn't reach the end of Constraint intersection");

648 return false;

649}

650

651

652

653

654

655

657 bool Splitable = false;

659 OS << "confused";

660 else {

662 OS << "consistent ";

664 OS << "flow";

666 OS << "output";

668 OS << "anti";

670 OS << "input";

672 OS << " [";

673 for (unsigned II = 1; II <= Levels; ++II) {

675 Splitable = true;

677 OS << 'p';

679 if (Distance)

680 OS << *Distance;

682 OS << "S";

683 else {

686 OS << "*";

687 else {

689 OS << "<";

691 OS << "=";

693 OS << ">";

694 }

695 }

697 OS << 'p';

698 if (II < Levels)

699 OS << " ";

700 }

702 OS << "|<";

703 OS << "]";

704 if (Splitable)

705 OS << " splitable";

706 }

707 OS << "!\n";

708}

709

710

711

712

713

714

719

720

727

728

731

732

733 if (AObj == BObj)

735

736

737

740

741

742

744}

745

746

747

748

749static

751 if (const LoadInst *LI = dyn_cast(I))

752 return LI->isUnordered();

753 else if (const StoreInst *SI = dyn_cast(I))

754 return SI->isUnordered();

755 return false;

756}

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

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

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

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

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

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

817 SrcLevels = SrcLevel;

818 MaxLevels = SrcLevel + DstLevel;

819 while (SrcLevel > DstLevel) {

821 SrcLevel--;

822 }

823 while (DstLevel > SrcLevel) {

825 DstLevel--;

826 }

827 while (SrcLoop != DstLoop) {

830 SrcLevel--;

831 }

832 CommonLevels = SrcLevel;

833 MaxLevels -= CommonLevels;

834}

835

836

837

838

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

841}

842

843

844

845

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

848 if (D > CommonLevels)

849

850

851 return D - CommonLevels + SrcLevels;

852 else

853 return D;

854}

855

856

857

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

860

861

862

863

865 return true;

866

867

868

870}

871

872

873

874

875

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

880 unsigned Level = LoopNest->getLoopDepth();

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

882 Loops.set(Level);

884 }

885}

886

888

889 unsigned widestWidthSeen = 0;

890 Type *widestType;

891

892

893

894 for (Subscript *Pair : Pairs) {

895 const SCEV *Src = Pair->Src;

896 const SCEV *Dst = Pair->Dst;

897 IntegerType *SrcTy = dyn_cast(Src->getType());

898 IntegerType *DstTy = dyn_cast(Dst->getType());

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

900 assert(SrcTy == DstTy && "This function only unify integer types and "

901 "expect Src and Dst share the same type "

902 "otherwise.");

903 continue;

904 }

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

907 widestType = SrcTy;

908 }

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

911 widestType = DstTy;

912 }

913 }

914

915

916 assert(widestWidthSeen > 0);

917

918

919 for (Subscript *Pair : Pairs) {

920 const SCEV *Src = Pair->Src;

921 const SCEV *Dst = Pair->Dst;

922 IntegerType *SrcTy = dyn_cast(Src->getType());

923 IntegerType *DstTy = dyn_cast(Dst->getType());

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

925 assert(SrcTy == DstTy && "This function only unify integer types and "

926 "expect Src and Dst share the same type "

927 "otherwise.");

928 continue;

929 }

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

931

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

934

936 }

937 }

938}

939

940

941

942

943

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

945 const SCEV *Src = Pair->Src;

946 const SCEV *Dst = Pair->Dst;

947 if ((isa(Src) && isa(Dst)) ||

948 (isa(Src) && isa(Dst))) {

954 Pair->Src = SrcCastOp;

955 Pair->Dst = DstCastOp;

956 }

957 }

958}

959

960

961

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

964 const SCEVAddRecExpr *AddRec = dyn_cast(Expr);

965 if (!AddRec)

966 return isLoopInvariant(Expr, LoopNest);

967

968

969

970

971

972

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

975 L = L->getParentLoop();

976 if (!L)

977 return false;

978

982 if (!isa(UB)) {

986 return false;

987 }

988 }

989 if (!isLoopInvariant(Step, LoopNest))

990 return false;

991 if (IsSrc)

993 else

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

996}

997

998

999

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

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

1003}

1004

1005

1006

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

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

1010}

1011

1012

1013

1014

1015

1016DependenceInfo::Subscript::ClassificationKind

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

1018 const SCEV *Dst, const Loop *DstLoopNest,

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

1023 return Subscript::NonLinear;

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

1025 return Subscript::NonLinear;

1026 Loops = SrcLoops;

1027 Loops |= DstLoops;

1028 unsigned N = Loops.count();

1029 if (N == 0)

1030 return Subscript::ZIV;

1031 if (N == 1)

1032 return Subscript::SIV;

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

1034 DstLoops.count() == 0 ||

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

1036 return Subscript::RDIV;

1037 return Subscript::MIV;

1038}

1039

1040

1041

1042

1043

1044

1045

1046

1047

1048

1049

1050

1052 const SCEV *Y) const {

1055 if ((isa(X) &&

1056 isa(Y)) ||

1057 (isa(X) &&

1058 isa(Y))) {

1064 X = Xop;

1065 Y = Yop;

1066 }

1067 }

1068 }

1070 return true;

1071

1072

1073

1074

1075

1077 switch (Pred) {

1079 return Delta->isZero();

1090 default:

1091 llvm_unreachable("unexpected predicate in isKnownPredicate");

1092 }

1093}

1094

1095

1096

1097

1098bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const {

1099

1100 auto *SType = dyn_cast(S->getType());

1101 auto *SizeType = dyn_cast(Size->getType());

1102 if (!SType || !SizeType)

1103 return false;

1104 Type *MaxType =

1105 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;

1108

1109

1111 if (const SCEVAddRecExpr *AddRec = dyn_cast(Bound)) {

1114 if (!isa(BECount)) {

1117 return true;

1118 }

1119 }

1120 }

1121

1122

1123 const SCEV *LimitedBound =

1126}

1127

1128bool DependenceInfo::isKnownNonNegative(const SCEV *S, const Value *Ptr) const {

1129 bool Inbounds = false;

1130 if (auto *SrcGEP = dyn_cast(Ptr))

1131 Inbounds = SrcGEP->isInBounds();

1132 if (Inbounds) {

1133 if (const SCEVAddRecExpr *AddRec = dyn_cast(S)) {

1135

1136

1139 return true;

1140 }

1141 }

1142 }

1143

1145}

1146

1147

1148

1149

1150

1151

1152

1153

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

1158 }

1159 return nullptr;

1160}

1161

1162

1163

1164

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

1166 Type *T) const {

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

1168 return dyn_cast(UB);

1169 return nullptr;

1170}

1171

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182

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

1187 ++ZIVapplications;

1190 return false;

1191 }

1194 ++ZIVindependence;

1195 return true;

1196 }

1198 Result.Consistent = false;

1199 return false;

1200}

1201

1202

1203

1204

1205

1206

1207

1208

1209

1210

1211

1212

1213

1214

1215

1216

1217

1218

1219

1220

1221

1222

1223

1224

1225

1226

1227

1228

1229

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

1231 const SCEV *DstConst, const Loop *CurLoop,

1233 Constraint &NewConstraint) const {

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

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

1241 ++StrongSIVapplications;

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

1243 Level--;

1244

1248

1249

1250 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {

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

1252 LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n");

1253 const SCEV *AbsDelta =

1255 const SCEV *AbsCoeff =

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

1259

1260 ++StrongSIVindependence;

1261 ++StrongSIVsuccesses;

1262 return true;

1263 }

1264 }

1265

1266

1267 if (isa(Delta) && isa(Coeff)) {

1268 APInt ConstDelta = cast(Delta)->getAPInt();

1269 APInt ConstCoeff = cast(Coeff)->getAPInt();

1270 APInt Distance = ConstDelta;

1271 APInt Remainder = ConstDelta;

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

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

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

1275

1276 if (Remainder != 0) {

1277

1278 ++StrongSIVindependence;

1279 ++StrongSIVsuccesses;

1280 return true;

1281 }

1283 NewConstraint.setDistance(SE->getConstant(Distance), CurLoop);

1284 if (Distance.sgt(0))

1286 else if (Distance.slt(0))

1288 else

1290 ++StrongSIVsuccesses;

1291 }

1292 else if (Delta->isZero()) {

1293

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

1295 NewConstraint.setDistance(Delta, CurLoop);

1297 ++StrongSIVsuccesses;

1298 }

1299 else {

1300 if (Coeff->isOne()) {

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

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

1303 NewConstraint.setDistance(Delta, CurLoop);

1304 }

1305 else {

1306 Result.Consistent = false;

1307 NewConstraint.setLine(Coeff,

1310 }

1311

1312

1318

1319

1320

1322 if ((DeltaMaybePositive && CoeffMaybePositive) ||

1323 (DeltaMaybeNegative && CoeffMaybeNegative))

1325 if (DeltaMaybeZero)

1327 if ((DeltaMaybeNegative && CoeffMaybePositive) ||

1328 (DeltaMaybePositive && CoeffMaybeNegative))

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

1331 ++StrongSIVsuccesses;

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

1333 }

1334 return false;

1335}

1336

1337

1338

1339

1340

1341

1342

1343

1344

1345

1346

1347

1348

1349

1350

1351

1352

1353

1354

1355

1356

1357

1358

1359

1360

1361

1362

1363

1364

1365

1366bool DependenceInfo::weakCrossingSIVtest(

1367 const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst,

1369 Constraint &NewConstraint, const SCEV *&SplitIter) const {

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

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

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

1374 ++WeakCrossingSIVapplications;

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

1376 Level--;

1377 Result.Consistent = false;

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

1380 NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);

1381 if (Delta->isZero()) {

1384 ++WeakCrossingSIVsuccesses;

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

1386 ++WeakCrossingSIVindependence;

1387 return true;

1388 }

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

1390 return false;

1391 }

1392 const SCEVConstant *ConstCoeff = dyn_cast(Coeff);

1393 if (!ConstCoeff)

1394 return false;

1395

1396 Result.DV[Level].Splitable = true;

1398 ConstCoeff = dyn_cast(SE->getNegativeSCEV(ConstCoeff));

1399 assert(ConstCoeff &&

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

1402 }

1404

1405

1409 LLVM_DEBUG(dbgs() << "\t Split iter = " << *SplitIter << "\n");

1410

1411 const SCEVConstant *ConstDelta = dyn_cast(Delta);

1412 if (!ConstDelta)

1413 return false;

1414

1415

1416

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

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

1420

1421 ++WeakCrossingSIVindependence;

1422 ++WeakCrossingSIVsuccesses;

1423 return true;

1424 }

1425

1426

1427

1428 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {

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

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

1432 ConstantTwo);

1435

1436 ++WeakCrossingSIVindependence;

1437 ++WeakCrossingSIVsuccesses;

1438 return true;

1439 }

1441

1444 ++WeakCrossingSIVsuccesses;

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

1446 ++WeakCrossingSIVindependence;

1447 return true;

1448 }

1449 Result.DV[Level].Splitable = false;

1451 return false;

1452 }

1453 }

1454

1455

1458 APInt Distance = APDelta;

1459 APInt Remainder = APDelta;

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

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

1462 if (Remainder != 0) {

1463

1464 ++WeakCrossingSIVindependence;

1465 ++WeakCrossingSIVsuccesses;

1466 return true;

1467 }

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

1469

1470

1472 Remainder = Distance.srem(Two);

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

1474 if (Remainder != 0) {

1475

1477 ++WeakCrossingSIVsuccesses;

1478 }

1479 return false;

1480}

1481

1482

1483

1484

1485

1486

1487

1488

1489

1490

1491

1492

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

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

1499 APInt Q = G0;

1502 while (R != 0) {

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

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

1505 G0 = G1; G1 = R;

1507 }

1508 G = G1;

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

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

1512

1513

1514 R = Delta.srem(G);

1515 if (R != 0)

1516 return true;

1517 Q = Delta.sdiv(G);

1518 return false;

1519}

1520

1522 APInt Q = A;

1525 if (R == 0)

1526 return Q;

1527 if ((A.sgt(0) && B.sgt(0)) ||

1528 (A.slt(0) && B.slt(0)))

1529 return Q;

1530 else

1531 return Q - 1;

1532}

1533

1535 APInt Q = A;

1538 if (R == 0)

1539 return Q;

1540 if ((A.sgt(0) && B.sgt(0)) ||

1541 (A.slt(0) && B.slt(0)))

1542 return Q + 1;

1543 else

1544 return Q;

1545}

1546

1547

1548

1549

1550

1551

1552

1553

1554

1555

1556

1557

1558

1559

1560

1561

1562

1563

1564

1565

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

1567 const SCEV *SrcConst, const SCEV *DstConst,

1568 const Loop *CurLoop, unsigned Level,

1570 Constraint &NewConstraint) const {

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

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

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

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

1576 ++ExactSIVapplications;

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

1578 Level--;

1579 Result.Consistent = false;

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

1582 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta,

1583 CurLoop);

1584 const SCEVConstant *ConstDelta = dyn_cast(Delta);

1585 const SCEVConstant *ConstSrcCoeff = dyn_cast(SrcCoeff);

1586 const SCEVConstant *ConstDstCoeff = dyn_cast(DstCoeff);

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

1588 return false;

1589

1590

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

1597

1598 ++ExactSIVindependence;

1599 ++ExactSIVsuccesses;

1600 return true;

1601 }

1602

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

1604

1605

1606 APInt UM(Bits, 1, true);

1607 bool UMValid = false;

1608

1610 collectConstantUpperBound(CurLoop, Delta->getType())) {

1611 UM = CUB->getAPInt();

1613 UMValid = true;

1614 }

1615

1624

1627 if (TB.sgt(0)) {

1630

1631 if (UMValid) {

1634 }

1635 } else {

1638

1639 if (UMValid) {

1642 }

1643 }

1644

1646 if (TA.sgt(0)) {

1647 if (UMValid) {

1650 }

1651

1654 } else {

1655 if (UMValid) {

1658 }

1659

1662 }

1663

1666

1668 return false;

1673

1674 if (TL.sgt(TU)) {

1675 ++ExactSIVindependence;

1676 ++ExactSIVsuccesses;

1677 return true;

1678 }

1679

1680

1682 APInt LowerDistance, UpperDistance;

1683 if (TA.sgt(TB)) {

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

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

1686 } else {

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

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

1689 }

1690

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

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

1693

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

1697 ++ExactSIVsuccesses;

1698 }

1699 if (LowerDistance.slt(0)) {

1701 ++ExactSIVsuccesses;

1702 }

1703 if (UpperDistance.sgt(0)) {

1705 ++ExactSIVsuccesses;

1706 }

1707

1708

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

1711 ++ExactSIVindependence;

1715}

1716

1717

1718

1719static

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

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

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

1725}

1726

1727

1728

1729

1730

1731

1732

1733

1734

1735

1736

1737

1738

1739

1740

1741

1742

1743

1744

1745

1746

1747

1748

1749

1750

1751

1752

1753

1754

1755

1756

1757

1758

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

1760 const SCEV *SrcConst,

1761 const SCEV *DstConst,

1762 const Loop *CurLoop, unsigned Level,

1764 Constraint &NewConstraint) const {

1765

1766

1767

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

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

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

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

1772 ++WeakZeroSIVapplications;

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

1774 Level--;

1775 Result.Consistent = false;

1777 NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta,

1778 CurLoop);

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

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

1781 if (Level < CommonLevels) {

1783 Result.DV[Level].PeelFirst = true;

1784 ++WeakZeroSIVsuccesses;

1785 }

1786 return false;

1787 }

1788 const SCEVConstant *ConstCoeff = dyn_cast(DstCoeff);

1789 if (!ConstCoeff)

1790 return false;

1791 const SCEV *AbsCoeff =

1794 const SCEV *NewDelta =

1796

1797

1798

1799 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {

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

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

1803 ++WeakZeroSIVindependence;

1804 ++WeakZeroSIVsuccesses;

1805 return true;

1806 }

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

1808

1809 if (Level < CommonLevels) {

1811 Result.DV[Level].PeelLast = true;

1812 ++WeakZeroSIVsuccesses;

1813 }

1814 return false;

1815 }

1816 }

1817

1818

1819

1821

1822 ++WeakZeroSIVindependence;

1823 ++WeakZeroSIVsuccesses;

1824 return true;

1825 }

1826

1827

1828 if (isa(Delta) &&

1829 isRemainderZero (cast(Delta), ConstCoeff)) {

1830 ++WeakZeroSIVindependence;

1831 ++WeakZeroSIVsuccesses;

1832 return true;

1833 }

1834 return false;

1835}

1836

1837

1838

1839

1840

1841

1842

1843

1844

1845

1846

1847

1848

1849

1850

1851

1852

1853

1854

1855

1856

1857

1858

1859

1860

1861

1862

1863

1864

1865

1866

1867

1868

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

1870 const SCEV *SrcConst,

1871 const SCEV *DstConst,

1872 const Loop *CurLoop, unsigned Level,

1874 Constraint &NewConstraint) const {

1875

1876

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

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

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

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

1881 ++WeakZeroSIVapplications;

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

1883 Level--;

1884 Result.Consistent = false;

1886 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta,

1887 CurLoop);

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

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

1890 if (Level < CommonLevels) {

1892 Result.DV[Level].PeelFirst = true;

1893 ++WeakZeroSIVsuccesses;

1894 }

1895 return false;

1896 }

1897 const SCEVConstant *ConstCoeff = dyn_cast(SrcCoeff);

1898 if (!ConstCoeff)

1899 return false;

1900 const SCEV *AbsCoeff =

1903 const SCEV *NewDelta =

1905

1906

1907

1908 if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {

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

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

1912 ++WeakZeroSIVindependence;

1913 ++WeakZeroSIVsuccesses;

1914 return true;

1915 }

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

1917

1918 if (Level < CommonLevels) {

1920 Result.DV[Level].PeelLast = true;

1921 ++WeakZeroSIVsuccesses;

1922 }

1923 return false;

1924 }

1925 }

1926

1927

1928

1930

1931 ++WeakZeroSIVindependence;

1932 ++WeakZeroSIVsuccesses;

1933 return true;

1934 }

1935

1936

1937 if (isa(Delta) &&

1938 isRemainderZero (cast(Delta), ConstCoeff)) {

1939 ++WeakZeroSIVindependence;

1940 ++WeakZeroSIVsuccesses;

1941 return true;

1942 }

1943 return false;

1944}

1945

1946

1947

1948

1949

1950

1951

1952

1953

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

1955 const SCEV *SrcConst, const SCEV *DstConst,

1956 const Loop *SrcLoop, const Loop *DstLoop,

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

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

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

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

1963 ++ExactRDIVapplications;

1964 Result.Consistent = false;

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

1967 const SCEVConstant *ConstDelta = dyn_cast(Delta);

1968 const SCEVConstant *ConstSrcCoeff = dyn_cast(SrcCoeff);

1969 const SCEVConstant *ConstDstCoeff = dyn_cast(DstCoeff);

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

1971 return false;

1972

1973

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

1980

1981 ++ExactRDIVindependence;

1982 return true;

1983 }

1984

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

1986

1987

1988 APInt SrcUM(Bits, 1, true);

1989 bool SrcUMvalid = false;

1990

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

1993 SrcUM = UpperBound->getAPInt();

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

1995 SrcUMvalid = true;

1996 }

1997

1998 APInt DstUM(Bits, 1, true);

1999 bool DstUMvalid = false;

2000

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

2003 DstUM = UpperBound->getAPInt();

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

2005 DstUMvalid = true;

2006 }

2007

2016

2019 if (TB.sgt(0)) {

2022 if (SrcUMvalid) {

2025 }

2026 } else {

2029 if (SrcUMvalid) {

2032 }

2033 }

2034

2036 if (TA.sgt(0)) {

2039 if (DstUMvalid) {

2042 }

2043 } else {

2046 if (DstUMvalid) {

2049 }

2050 }

2051

2053 return false;

2054

2057

2062

2063 if (TL.sgt(TU))

2064 ++ExactRDIVindependence;

2065 return TL.sgt(TU);

2066}

2067

2068

2069

2070

2071

2072

2073

2074

2075

2076

2077

2078

2079

2080

2081

2082

2083

2084

2085

2086

2087

2088

2089

2090

2091

2092

2093

2094

2095

2096

2097

2098

2099

2100

2101

2102

2103

2104

2105

2106

2107

2108

2109

2110

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

2112 const SCEV *C1, const SCEV *C2,

2113 const Loop *Loop1,

2114 const Loop *Loop2) const {

2115 ++SymbolicRDIVapplications;

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

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

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

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

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

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

2132

2133 if (N1) {

2134

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

2138 ++SymbolicRDIVindependence;

2139 return true;

2140 }

2141 }

2142 if (N2) {

2143

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

2147 ++SymbolicRDIVindependence;

2148 return true;

2149 }

2150 }

2151 }

2153

2154 if (N1 && N2) {

2155

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

2161 ++SymbolicRDIVindependence;

2162 return true;

2163 }

2164 }

2165

2167 ++SymbolicRDIVindependence;

2168 return true;

2169 }

2170 }

2171 }

2174

2175 if (N1 && N2) {

2176

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

2182 ++SymbolicRDIVindependence;

2183 return true;

2184 }

2185 }

2186

2188 ++SymbolicRDIVindependence;

2189 return true;

2190 }

2191 }

2193

2194 if (N1) {

2195

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

2199 ++SymbolicRDIVindependence;

2200 return true;

2201 }

2202 }

2203 if (N2) {

2204

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

2208 ++SymbolicRDIVindependence;

2209 return true;

2210 }

2211 }

2212 }

2213 }

2214 return false;

2215}

2216

2217

2218

2219

2220

2221

2222

2223

2224

2225

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

2228 const SCEV *&SplitIter) const {

2231 const SCEVAddRecExpr *SrcAddRec = dyn_cast(Src);

2232 const SCEVAddRecExpr *DstAddRec = dyn_cast(Dst);

2233 if (SrcAddRec && DstAddRec) {

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

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

2238 const Loop *CurLoop = SrcAddRec->getLoop();

2240 "both loops in SIV should be same");

2241 Level = mapSrcLoop(CurLoop);

2242 bool disproven;

2243 if (SrcCoeff == DstCoeff)

2244 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,

2245 Level, Result, NewConstraint);

2247 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,

2248 Level, Result, NewConstraint, SplitIter);

2249 else

2250 disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,

2251 Level, Result, NewConstraint);

2252 return disproven ||

2253 gcdMIVtest(Src, Dst, Result) ||

2254 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);

2255 }

2256 if (SrcAddRec) {

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

2259 const SCEV *DstConst = Dst;

2260 const Loop *CurLoop = SrcAddRec->getLoop();

2261 Level = mapSrcLoop(CurLoop);

2262 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,

2263 Level, Result, NewConstraint) ||

2264 gcdMIVtest(Src, Dst, Result);

2265 }

2266 if (DstAddRec) {

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

2269 const SCEV *SrcConst = Src;

2270 const Loop *CurLoop = DstAddRec->getLoop();

2271 Level = mapDstLoop(CurLoop);

2272 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,

2273 CurLoop, Level, Result, NewConstraint) ||

2274 gcdMIVtest(Src, Dst, Result);

2275 }

2277 return false;

2278}

2279

2280

2281

2282

2283

2284

2285

2286

2287

2288

2289

2290

2291

2292

2293

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

2296

2297

2298

2299

2300

2301

2302 const SCEV *SrcConst, *DstConst;

2303 const SCEV *SrcCoeff, *DstCoeff;

2304 const Loop *SrcLoop, *DstLoop;

2305

2308 const SCEVAddRecExpr *SrcAddRec = dyn_cast(Src);

2309 const SCEVAddRecExpr *DstAddRec = dyn_cast(Dst);

2310 if (SrcAddRec && DstAddRec) {

2311 SrcConst = SrcAddRec->getStart();

2313 SrcLoop = SrcAddRec->getLoop();

2314 DstConst = DstAddRec->getStart();

2316 DstLoop = DstAddRec->getLoop();

2317 }

2318 else if (SrcAddRec) {

2320 dyn_cast(SrcAddRec->getStart())) {

2321 SrcConst = tmpAddRec->getStart();

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

2323 SrcLoop = tmpAddRec->getLoop();

2324 DstConst = Dst;

2326 DstLoop = SrcAddRec->getLoop();

2327 }

2328 else

2330 }

2331 else if (DstAddRec) {

2333 dyn_cast(DstAddRec->getStart())) {

2334 DstConst = tmpAddRec->getStart();

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

2336 DstLoop = tmpAddRec->getLoop();

2337 SrcConst = Src;

2339 SrcLoop = DstAddRec->getLoop();

2340 }

2341 else

2343 }

2344 else

2346 return exactRDIVtest(SrcCoeff, DstCoeff,

2347 SrcConst, DstConst,

2348 SrcLoop, DstLoop,

2349 Result) ||

2350 gcdMIVtest(Src, Dst, Result) ||

2351 symbolicRDIVtest(SrcCoeff, DstCoeff,

2352 SrcConst, DstConst,

2353 SrcLoop, DstLoop);

2354}

2355

2356

2357

2358

2359

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

2365 Result.Consistent = false;

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

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

2368}

2369

2370

2371

2372

2373static

2375 if (const auto *Constant = dyn_cast(Expr))

2377 else if (const auto *Product = dyn_cast(Expr))

2378 if (const auto *Constant = dyn_cast(Product->getOperand(0)))

2380 return nullptr;

2381}

2382

2383

2384

2385

2386

2387

2388

2389

2390

2391

2392

2393

2394

2395

2396

2397

2398

2399

2400

2401

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

2405 ++GCDapplications;

2408

2409

2410

2411

2412

2413 const SCEV *Coefficients = Src;

2415 dyn_cast(Coefficients)) {

2417

2418

2421 return false;

2424 Coefficients = AddRec->getStart();

2425 }

2426 const SCEV *SrcConst = Coefficients;

2427

2428

2429

2430

2431

2432 Coefficients = Dst;

2434 dyn_cast(Coefficients)) {

2436

2437

2440 return false;

2443 Coefficients = AddRec->getStart();

2444 }

2445 const SCEV *DstConst = Coefficients;

2446

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

2451 if (const SCEVAddExpr *Sum = dyn_cast(Delta)) {

2452

2453 for (const SCEV *Operand : Sum->operands()) {

2454 if (isa(Operand)) {

2455 assert( && "Surprised to find multiple constants");

2456 Constant = cast(Operand);

2457 }

2458 else if (const SCEVMulExpr *Product = dyn_cast(Operand)) {

2459

2460

2462 if (!ConstOp)

2463 return false;

2466 ConstOpValue.abs());

2467 }

2468 else

2469 return false;

2470 }

2471 }

2473 return false;

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

2476 if (ConstDelta == 0)

2477 return false;

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

2480 APInt Remainder = ConstDelta.srem(RunningGCD);

2481 if (Remainder != 0) {

2482 ++GCDindependence;

2483 return true;

2484 }

2485

2486

2487

2488

2489

2490

2491

2492

2493

2494

2495

2496

2497

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

2499

2500 bool Improved = false;

2501 Coefficients = Src;

2503 dyn_cast(Coefficients)) {

2504 Coefficients = AddRec->getStart();

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

2506 RunningGCD = ExtraGCD;

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

2509 const SCEV *Inner = Src;

2510 while (RunningGCD != 1 && isa(Inner)) {

2511 AddRec = cast(Inner);

2513 if (CurLoop == AddRec->getLoop())

2514 ;

2515 else {

2516

2517

2520 return false;

2523 }

2525 }

2526 Inner = Dst;

2527 while (RunningGCD != 1 && isa(Inner)) {

2528 AddRec = cast(Inner);

2530 if (CurLoop == AddRec->getLoop())

2531 DstCoeff = Coeff;

2532 else {

2533

2534

2537 return false;

2540 }

2542 }

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

2544

2545

2548

2549

2550 continue;

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

2554 if (RunningGCD != 0) {

2555 Remainder = ConstDelta.srem(RunningGCD);

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

2557 if (Remainder != 0) {

2558 unsigned Level = mapSrcLoop(CurLoop);

2560 Improved = true;

2561 }

2562 }

2563 }

2564 if (Improved)

2565 ++GCDsuccesses;

2567 return false;

2568}

2569

2570

2571

2572

2573

2574

2575

2576

2577

2578

2579

2580

2581

2582

2583

2584

2585

2586

2587

2588

2589

2590

2591

2592

2593

2594

2595

2596

2597

2598

2599

2600

2601

2602

2603

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

2608 ++BanerjeeApplications;

2610 const SCEV *A0;

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

2613 const SCEV *B0;

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

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

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

2618

2619

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

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

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

2626#ifndef NDEBUG

2630 else

2634 else

2636#endif

2637 }

2638

2639

2640 bool Disproved = false;

2642

2643 unsigned DepthExpanded = 0;

2644 unsigned NewDeps = exploreDirections(1, A, B, Bound,

2645 Loops, DepthExpanded, Delta);

2646 if (NewDeps > 0) {

2647 bool Improved = false;

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

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

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

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

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

2654 Improved = false;

2655 Disproved = true;

2656 break;

2657 }

2658 }

2659 }

2660 if (Improved)

2661 ++BanerjeeSuccesses;

2662 }

2663 else {

2664 ++BanerjeeIndependence;

2665 Disproved = true;

2666 }

2667 }

2668 else {

2669 ++BanerjeeIndependence;

2670 Disproved = true;

2671 }

2672 delete [] Bound;

2673 delete [] A;

2674 delete [] B;

2675 return Disproved;

2676}

2677

2678

2679

2680

2681

2682

2683

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

2685 CoefficientInfo *B, BoundInfo *Bound,

2687 unsigned &DepthExpanded,

2688 const SCEV *Delta) const {

2689

2690

2691

2692

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

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

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

2699 return 1;

2700 }

2701

2702 if (Level > CommonLevels) {

2703

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

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

2708#ifndef NDEBUG

2712 break;

2715 break;

2718 break;

2721 break;

2722 default:

2724 }

2725#endif

2726 }

2727 }

2729 return 1;

2730 }

2731 if (Loops[Level]) {

2732 if (Level > DepthExpanded) {

2733 DepthExpanded = Level;

2734

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

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

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

2738#ifndef NDEBUG

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

2743 << '\t');

2744 else

2748 << '\n');

2749 else

2754 << '\t');

2755 else

2759 << '\n');

2760 else

2765 << '\t');

2766 else

2770 << '\n');

2771 else

2773#endif

2774 }

2775

2776 unsigned NewDeps = 0;

2777

2778

2780 NewDeps += exploreDirections(Level + 1, A, B, Bound,

2781 Loops, DepthExpanded, Delta);

2782

2783

2785 NewDeps += exploreDirections(Level + 1, A, B, Bound,

2786 Loops, DepthExpanded, Delta);

2787

2788

2790 NewDeps += exploreDirections(Level + 1, A, B, Bound,

2791 Loops, DepthExpanded, Delta);

2792

2794 return NewDeps;

2795 }

2796 else

2797 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta);

2798}

2799

2800

2801

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

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

2804 Bound[Level].Direction = DirKind;

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

2807 return false;

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

2810 return false;

2811 return true;

2812}

2813

2814

2815

2816

2817

2818

2819

2820

2821

2822

2823

2824

2825

2826

2827

2828

2829

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

2831 BoundInfo *Bound, unsigned K) const {

2834 if (Bound[K].Iterations) {

2837 Bound[K].Iterations);

2840 Bound[K].Iterations);

2841 }

2842 else {

2843

2850 }

2851}

2852

2853

2854

2855

2856

2857

2858

2859

2860

2861

2862

2863

2864

2865

2866

2867

2868

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

2870 BoundInfo *Bound, unsigned K) const {

2873 if (Bound[K].Iterations) {

2875 const SCEV *NegativePart = getNegativePart(Delta);

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

2878 const SCEV *PositivePart = getPositivePart(Delta);

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

2881 }

2882 else {

2883

2884

2886 const SCEV *NegativePart = getNegativePart(Delta);

2887 if (NegativePart->isZero())

2889 const SCEV *PositivePart = getPositivePart(Delta);

2890 if (PositivePart->isZero())

2892 }

2893}

2894

2895

2896

2897

2898

2899

2900

2901

2902

2903

2904

2905

2906

2907

2908

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

2910 BoundInfo *Bound, unsigned K) const {

2913 if (Bound[K].Iterations) {

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

2916 const SCEV *NegPart =

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

2920 const SCEV *PosPart =

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

2924 }

2925 else {

2926

2927

2928 const SCEV *NegPart =

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

2930 if (NegPart->isZero())

2932 const SCEV *PosPart =

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

2934 if (PosPart->isZero())

2936 }

2937}

2938

2939

2940

2941

2942

2943

2944

2945

2946

2947

2948

2949

2950

2951

2952

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

2954 BoundInfo *Bound, unsigned K) const {

2957 if (Bound[K].Iterations) {

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

2960 const SCEV *NegPart =

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

2964 const SCEV *PosPart =

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

2968 }

2969 else {

2970

2971

2972 const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));

2973 if (NegPart->isZero())

2975 const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));

2976 if (PosPart->isZero())

2978 }

2979}

2980

2981

2982

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

2985}

2986

2987

2988

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

2991}

2992

2993

2994

2995

2996

2997DependenceInfo::CoefficientInfo *

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

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

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

3003 CI[K].Coeff = Zero;

3004 CI[K].PosPart = Zero;

3005 CI[K].NegPart = Zero;

3006 CI[K].Iterations = nullptr;

3007 }

3008 while (const SCEVAddRecExpr *AddRec = dyn_cast(Subscript)) {

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

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

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

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

3015 Subscript = AddRec->getStart();

3016 }

3018#ifndef NDEBUG

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

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

3027 if (CI[K].Iterations)

3029 else

3032 }

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

3034#endif

3035 return CI;

3036}

3037

3038

3039

3040

3041

3042

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

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

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

3048 else

3049 Sum = nullptr;

3050 }

3051 return Sum;

3052}

3053

3054

3055

3056

3057

3058

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

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

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

3064 else

3065 Sum = nullptr;

3066 }

3067 return Sum;

3068}

3069

3070

3071

3072

3073

3074

3075

3076

3077

3078

3079

3080const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr,

3081 const Loop *TargetLoop) const {

3082 const SCEVAddRecExpr *AddRec = dyn_cast(Expr);

3083 if (!AddRec)

3085 if (AddRec->getLoop() == TargetLoop)

3087 return findCoefficient(AddRec->getStart(), TargetLoop);

3088}

3089

3090

3091

3092

3093

3094

3095

3096const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr,

3097 const Loop *TargetLoop) const {

3098 const SCEVAddRecExpr *AddRec = dyn_cast(Expr);

3099 if (!AddRec)

3100 return Expr;

3101 if (AddRec->getLoop() == TargetLoop)

3107}

3108

3109

3110

3111

3112

3113

3114

3115const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,

3116 const Loop *TargetLoop,

3118 const SCEVAddRecExpr *AddRec = dyn_cast(Expr);

3119 if (!AddRec)

3122 TargetLoop,

3124 if (AddRec->getLoop() == TargetLoop) {

3129 Sum,

3132 }

3136 addToCoefficient(AddRec->getStart(), TargetLoop, Value),

3139}

3140

3141

3142

3143

3144

3145

3146

3147

3148

3149

3150

3151

3152bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,

3155 bool &Consistent) {

3156 bool Result = false;

3157 for (unsigned LI : Loops.set_bits()) {

3158 LLVM_DEBUG(dbgs() << "\t Constraint[" << LI << "] is");

3160 if (Constraints[LI].isDistance())

3161 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);

3162 else if (Constraints[LI].isLine())

3163 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);

3164 else if (Constraints[LI].isPoint())

3165 Result |= propagatePoint(Src, Dst, Constraints[LI]);

3166 }

3168}

3169

3170

3171

3172

3173

3174

3175

3176bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst,

3177 Constraint &CurConstraint,

3178 bool &Consistent) {

3179 const Loop *CurLoop = CurConstraint.getAssociatedLoop();

3180 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");

3181 const SCEV *A_K = findCoefficient(Src, CurLoop);

3183 return false;

3184 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());

3186 Src = zeroCoefficient(Src, CurLoop);

3187 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");

3188 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");

3189 Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K));

3190 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");

3191 if (!findCoefficient(Dst, CurLoop)->isZero())

3192 Consistent = false;

3193 return true;

3194}

3195

3196

3197

3198

3199

3200

3201

3202bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst,

3203 Constraint &CurConstraint,

3204 bool &Consistent) {

3205 const Loop *CurLoop = CurConstraint.getAssociatedLoop();

3206 const SCEV *A = CurConstraint.getA();

3207 const SCEV *B = CurConstraint.getB();

3208 const SCEV *C = CurConstraint.getC();

3209 LLVM_DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C

3210 << "\n");

3213 if (A->isZero()) {

3214 const SCEVConstant *Bconst = dyn_cast(B);

3215 const SCEVConstant *Cconst = dyn_cast(C);

3216 if (!Bconst || !Cconst) return false;

3219 APInt CdivB = Charlie.sdiv(Beta);

3220 assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B");

3221 const SCEV *AP_K = findCoefficient(Dst, CurLoop);

3222

3224 Dst = zeroCoefficient(Dst, CurLoop);

3225 if (!findCoefficient(Src, CurLoop)->isZero())

3226 Consistent = false;

3227 }

3228 else if (B->isZero()) {

3229 const SCEVConstant *Aconst = dyn_cast(A);

3230 const SCEVConstant *Cconst = dyn_cast(C);

3231 if (!Aconst || !Cconst) return false;

3234 APInt CdivA = Charlie.sdiv(Alpha);

3235 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");

3236 const SCEV *A_K = findCoefficient(Src, CurLoop);

3238 Src = zeroCoefficient(Src, CurLoop);

3239 if (!findCoefficient(Dst, CurLoop)->isZero())

3240 Consistent = false;

3241 }

3243 const SCEVConstant *Aconst = dyn_cast(A);

3244 const SCEVConstant *Cconst = dyn_cast(C);

3245 if (!Aconst || !Cconst) return false;

3248 APInt CdivA = Charlie.sdiv(Alpha);

3249 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");

3250 const SCEV *A_K = findCoefficient(Src, CurLoop);

3252 Src = zeroCoefficient(Src, CurLoop);

3253 Dst = addToCoefficient(Dst, CurLoop, A_K);

3254 if (!findCoefficient(Dst, CurLoop)->isZero())

3255 Consistent = false;

3256 }

3257 else {

3258

3259 const SCEV *A_K = findCoefficient(Src, CurLoop);

3263 Src = zeroCoefficient(Src, CurLoop);

3264 Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B));

3265 if (!findCoefficient(Dst, CurLoop)->isZero())

3266 Consistent = false;

3267 }

3268 LLVM_DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n");

3269 LLVM_DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n");

3270 return true;

3271}

3272

3273

3274

3275

3276

3277bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst,

3278 Constraint &CurConstraint) {

3279 const Loop *CurLoop = CurConstraint.getAssociatedLoop();

3280 const SCEV *A_K = findCoefficient(Src, CurLoop);

3281 const SCEV *AP_K = findCoefficient(Dst, CurLoop);

3282 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());

3283 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());

3284 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");

3286 Src = zeroCoefficient(Src, CurLoop);

3287 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");

3288 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");

3289 Dst = zeroCoefficient(Dst, CurLoop);

3290 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");

3291 return true;

3292}

3293

3294

3295

3297 const Constraint &CurConstraint) const {

3298 LLVM_DEBUG(dbgs() << "\tUpdate direction, constraint =");

3300 if (CurConstraint.isAny())

3301 ;

3302 else if (CurConstraint.isDistance()) {

3303

3304 Level.Scalar = false;

3305 Level.Distance = CurConstraint.getD();

3307 if (!SE->isKnownNonZero(Level.Distance))

3313 Level.Direction &= NewDirection;

3314 }

3315 else if (CurConstraint.isLine()) {

3316 Level.Scalar = false;

3317 Level.Distance = nullptr;

3318

3319 }

3320 else if (CurConstraint.isPoint()) {

3321 Level.Scalar = false;

3322 Level.Distance = nullptr;

3325 CurConstraint.getY(),

3326 CurConstraint.getX()))

3327

3330 CurConstraint.getY(),

3331 CurConstraint.getX()))

3332

3335 CurConstraint.getY(),

3336 CurConstraint.getX()))

3337

3339 Level.Direction &= NewDirection;

3340 }

3341 else

3343}

3344

3345

3346

3347

3348

3360 dyn_cast(SE->getPointerBase(SrcAccessFn));

3362 dyn_cast(SE->getPointerBase(DstAccessFn));

3363

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

3365 return false;

3366

3368

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

3370 SrcSubscripts, DstSubscripts) &&

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

3372 SrcSubscripts, DstSubscripts))

3373 return false;

3374

3375 int Size = SrcSubscripts.size();

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

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

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

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

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

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

3383 });

3384

3385

3386

3387

3388

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

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

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

3393 unifySubscriptType(&Pair[I]);

3394 }

3395

3396 return true;

3397}

3398

3399

3400

3401

3402bool DependenceInfo::tryDelinearizeFixedSize(

3408 dyn_cast(SE->getPointerBase(SrcAccessFn));

3410 dyn_cast(SE->getPointerBase(DstAccessFn));

3411 assert(SrcBase && DstBase && SrcBase == DstBase &&

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

3413 });

3414

3418 SrcSizes) ||

3420 DstSizes))

3421 return false;

3422

3423

3424

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

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

3427 SrcSubscripts.clear();

3428 DstSubscripts.clear();

3429 return false;

3430 }

3431

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

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

3434 "DstSubscripts.");

3435

3438

3439

3440

3441

3442

3443

3444

3449 size_t SSize = Subscripts.size();

3450 for (size_t I = 1; I < SSize; ++I) {

3451 const SCEV *S = Subscripts[I];

3452 if (!isKnownNonNegative(S, Ptr))

3453 return false;

3454 if (auto *SType = dyn_cast(S->getType())) {

3456 ConstantInt::get(SType, DimensionSizes[I - 1], false));

3457 if (!isKnownLessThan(S, Range))

3458 return false;

3459 }

3460 }

3461 return true;

3462 };

3463

3464 if (!AllIndicesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||

3465 !AllIndicesInRange(DstSizes, DstSubscripts, DstPtr)) {

3466 SrcSubscripts.clear();

3467 DstSubscripts.clear();

3468 return false;

3469 }

3470 }

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

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

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

3475 });

3476 return true;

3477}

3478

3479bool DependenceInfo::tryDelinearizeParametricSize(

3483

3487 dyn_cast(SE->getPointerBase(SrcAccessFn));

3489 dyn_cast(SE->getPointerBase(DstAccessFn));

3490 assert(SrcBase && DstBase && SrcBase == DstBase &&

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

3492

3495 return false;

3496

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

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

3499

3500 const SCEVAddRecExpr *SrcAR = dyn_cast(SrcSCEV);

3501 const SCEVAddRecExpr *DstAR = dyn_cast(DstSCEV);

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

3503 return false;

3504

3505

3509

3510

3513

3514

3517

3518

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

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

3521 return false;

3522

3523 size_t Size = SrcSubscripts.size();

3524

3525

3526

3527

3528

3529

3530

3532 for (size_t I = 1; I < Size; ++I) {

3533 if (!isKnownNonNegative(SrcSubscripts[I], SrcPtr))

3534 return false;

3535

3536 if (!isKnownLessThan(SrcSubscripts[I], Sizes[I - 1]))

3537 return false;

3538

3539 if (!isKnownNonNegative(DstSubscripts[I], DstPtr))

3540 return false;

3541

3542 if (!isKnownLessThan(DstSubscripts[I], Sizes[I - 1]))

3543 return false;

3544 }

3545

3546 return true;

3547}

3548

3549

3550

3551#ifndef NDEBUG

3552

3554 dbgs() << "{";

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

3556 dbgs() << VI;

3558 dbgs() << ' ';

3559 }

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

3561}

3562#endif

3563

3566

3569 return true;

3570

3571

3575}

3576

3577

3578

3579

3580

3581

3582

3583

3584

3585

3586

3587

3588std::unique_ptr

3590 bool PossiblyLoopIndependent) {

3591 if (Src == Dst)

3592 PossiblyLoopIndependent = false;

3593

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

3595

3596 return nullptr;

3597

3599

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

3601 return std::make_unique(Src, Dst);

3602 }

3603

3608

3614

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

3616 return std::make_unique(Src, Dst);

3618

3620 return nullptr;

3622 break;

3623 }

3624

3625

3626 establishNestingLevels(Src, Dst);

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

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

3629

3630 FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);

3631 ++TotalArrayPairs;

3632

3633 unsigned Pairs = 1;

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

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

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

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

3640

3641

3642

3643

3644

3645

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

3647 return std::make_unique(Src, Dst);

3648 }

3649 Pair[0].Src = SrcSCEV;

3650 Pair[0].Dst = DstSCEV;

3651

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

3655 Pairs = Pair.size();

3656 }

3657 }

3658

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

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

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

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

3663 removeMatchingExtensions(&Pair[P]);

3664 Pair[P].Classification =

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

3666 Pair[P].Dst, LI->getLoopFor(Dst->getParent()),

3667 Pair[P].Loops);

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

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

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

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

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

3676 }

3677

3680

3681

3682

3683

3684

3685

3686

3687

3688

3689

3690

3691

3692

3693

3694

3695

3696

3697

3698

3699

3700

3701

3702

3703

3704

3705

3706

3707

3708

3709

3710

3711

3712

3713

3714

3715

3716

3717

3718

3719

3720

3721

3722

3723

3724

3725

3726

3727

3728

3729

3730

3731

3732

3733

3734

3735

3736

3737

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

3739 if (Pair[SI].Classification == Subscript::NonLinear) {

3740

3741 ++NonlinearSubscriptPairs;

3742 collectCommonLoops(Pair[SI].Src,

3744 Pair[SI].Loops);

3745 collectCommonLoops(Pair[SI].Dst,

3747 Pair[SI].Loops);

3748 Result.Consistent = false;

3749 } else if (Pair[SI].Classification == Subscript::ZIV) {

3750

3751 Separable.set(SI);

3752 }

3753 else {

3754

3755 bool Done = true;

3756 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {

3758 Intersection &= Pair[SJ].GroupLoops;

3759 if (Intersection.any()) {

3760

3761 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;

3762

3763 Pair[SJ].Group |= Pair[SI].Group;

3764 Done = false;

3765 }

3766 }

3768 if (Pair[SI].Group.count() == 1) {

3769 Separable.set(SI);

3770 ++SeparableSubscriptPairs;

3771 }

3772 else {

3773 Coupled.set(SI);

3774 ++CoupledSubscriptPairs;

3775 }

3776 }

3777 }

3778 }

3779

3784

3785 Constraint NewConstraint;

3786 NewConstraint.setAny(SE);

3787

3788

3789 for (unsigned SI : Separable.set_bits()) {

3791 switch (Pair[SI].Classification) {

3792 case Subscript::ZIV:

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

3795 return nullptr;

3796 break;

3797 case Subscript::SIV: {

3799 unsigned Level;

3800 const SCEV *SplitIter = nullptr;

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

3802 SplitIter))

3803 return nullptr;

3804 break;

3805 }

3806 case Subscript::RDIV:

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

3809 return nullptr;

3810 break;

3811 case Subscript::MIV:

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

3814 return nullptr;

3815 break;

3816 default:

3817 llvm_unreachable("subscript has unexpected classification");

3818 }

3819 }

3820

3821 if (Coupled.count()) {

3822

3823 LLVM_DEBUG(dbgs() << "starting on coupled subscripts\n");

3824 LLVM_DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n");

3826 for (unsigned II = 0; II <= MaxLevels; ++II)

3827 Constraints[II].setAny(SE);

3828 for (unsigned SI : Coupled.set_bits()) {

3829 LLVM_DEBUG(dbgs() << "testing subscript group " << SI << " { ");

3835 for (unsigned SJ : Group.set_bits()) {

3837 if (Pair[SJ].Classification == Subscript::SIV)

3838 Sivs.set(SJ);

3839 else

3840 Mivs.set(SJ);

3841 PairsInGroup.push_back(&Pair[SJ]);

3842 }

3843 unifySubscriptType(PairsInGroup);

3845 while (Sivs.any()) {

3846 bool Changed = false;

3847 for (unsigned SJ : Sivs.set_bits()) {

3848 LLVM_DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");

3849

3850 unsigned Level;

3851 const SCEV *SplitIter = nullptr;

3853 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,

3854 SplitIter))

3855 return nullptr;

3856 ConstrainedLevels.set(Level);

3857 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {

3858 if (Constraints[Level].isEmpty()) {

3859 ++DeltaIndependence;

3860 return nullptr;

3861 }

3862 Changed = true;

3863 }

3865 }

3866 if (Changed) {

3867

3871 for (unsigned SJ : Mivs.set_bits()) {

3872

3874 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,

3875 Constraints, Result.Consistent)) {

3877 ++DeltaPropagations;

3878 Pair[SJ].Classification =

3879 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),

3880 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),

3881 Pair[SJ].Loops);

3882 switch (Pair[SJ].Classification) {

3883 case Subscript::ZIV:

3885 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))

3886 return nullptr;

3888 break;

3889 case Subscript::SIV:

3890 Sivs.set(SJ);

3892 break;

3893 case Subscript::RDIV:

3894 case Subscript::MIV:

3895 break;

3896 default:

3898 }

3899 }

3900 }

3901 }

3902 }

3903

3904

3905 for (unsigned SJ : Mivs.set_bits()) {

3906 if (Pair[SJ].Classification == Subscript::RDIV) {

3908 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))

3909 return nullptr;

3910

3912 }

3913 }

3914

3915

3916

3917

3918 for (unsigned SJ : Mivs.set_bits()) {

3919 if (Pair[SJ].Classification == Subscript::MIV) {

3921 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))

3922 return nullptr;

3923 }

3924 else

3925 llvm_unreachable("expected only MIV subscripts at this point");

3926 }

3927

3928

3930 for (unsigned SJ : ConstrainedLevels.set_bits()) {

3931 if (SJ > CommonLevels)

3932 break;

3933 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);

3935 return nullptr;

3936 }

3937 }

3938 }

3939

3940

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

3943 CompleteLoops |= Pair[SI].Loops;

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

3945 if (CompleteLoops[II])

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

3947

3948 if (PossiblyLoopIndependent) {

3949

3950

3951

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

3954 Result.LoopIndependent = false;

3955 break;

3956 }

3957 }

3958 }

3959 else {

3960

3961

3962 bool AllEqual = true;

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

3965 AllEqual = false;

3966 break;

3967 }

3968 }

3969 if (AllEqual)

3970 return nullptr;

3971 }

3972

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

3974}

3975

3976

3977

3978

3979

3980

3981

3982

3983

3984

3985

3986

3987

3988

3989

3990

3991

3992

3993

3994

3995

3996

3997

3998

3999

4000

4001

4002

4003

4004

4005

4006

4007

4008

4009

4010

4011

4012

4013

4014

4015

4016

4017

4018

4019

4020

4021

4022

4024 unsigned SplitLevel) {

4026 "Dep should be splitable at SplitLevel");

4029 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());

4030 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());

4038

4039

4040 establishNestingLevels(Src, Dst);

4041

4042 FullDependence Result(Src, Dst, false, CommonLevels);

4043

4044 unsigned Pairs = 1;

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

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

4048 Pair[0].Src = SrcSCEV;

4049 Pair[0].Dst = DstSCEV;

4050

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

4054 Pairs = Pair.size();

4055 }

4056 }

4057

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

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

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

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

4062 removeMatchingExtensions(&Pair[P]);

4063 Pair[P].Classification =

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

4065 Pair[P].Dst, LI->getLoopFor(Dst->getParent()),

4066 Pair[P].Loops);

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

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

4069 }

4070

4073

4074

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

4076 if (Pair[SI].Classification == Subscript::NonLinear) {

4077

4078 collectCommonLoops(Pair[SI].Src,

4080 Pair[SI].Loops);

4081 collectCommonLoops(Pair[SI].Dst,

4083 Pair[SI].Loops);

4084 Result.Consistent = false;

4085 }

4086 else if (Pair[SI].Classification == Subscript::ZIV)

4087 Separable.set(SI);

4088 else {

4089

4090 bool Done = true;

4091 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {

4093 Intersection &= Pair[SJ].GroupLoops;

4094 if (Intersection.any()) {

4095

4096 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;

4097

4098 Pair[SJ].Group |= Pair[SI].Group;

4099 Done = false;

4100 }

4101 }

4103 if (Pair[SI].Group.count() == 1)

4104 Separable.set(SI);

4105 else

4106 Coupled.set(SI);

4107 }

4108 }

4109 }

4110

4111 Constraint NewConstraint;

4112 NewConstraint.setAny(SE);

4113

4114

4115 for (unsigned SI : Separable.set_bits()) {

4116 switch (Pair[SI].Classification) {

4117 case Subscript::SIV: {

4118 unsigned Level;

4119 const SCEV *SplitIter = nullptr;

4120 (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,

4121 Result, NewConstraint, SplitIter);

4122 if (Level == SplitLevel) {

4123 assert(SplitIter != nullptr);

4124 return SplitIter;

4125 }

4126 break;

4127 }

4128 case Subscript::ZIV:

4129 case Subscript::RDIV:

4130 case Subscript::MIV:

4131 break;

4132 default:

4133 llvm_unreachable("subscript has unexpected classification");

4134 }

4135 }

4136

4137 if (Coupled.count()) {

4138

4140 for (unsigned II = 0; II <= MaxLevels; ++II)

4141 Constraints[II].setAny(SE);

4142 for (unsigned SI : Coupled.set_bits()) {

4147 for (unsigned SJ : Group.set_bits()) {

4148 if (Pair[SJ].Classification == Subscript::SIV)

4149 Sivs.set(SJ);

4150 else

4151 Mivs.set(SJ);

4152 }

4153 while (Sivs.any()) {

4154 bool Changed = false;

4155 for (unsigned SJ : Sivs.set_bits()) {

4156

4157 unsigned Level;

4158 const SCEV *SplitIter = nullptr;

4159 (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,

4160 Result, NewConstraint, SplitIter);

4161 if (Level == SplitLevel && SplitIter)

4162 return SplitIter;

4163 ConstrainedLevels.set(Level);

4164 if (intersectConstraints(&Constraints[Level], &NewConstraint))

4165 Changed = true;

4167 }

4168 if (Changed) {

4169

4170 for (unsigned SJ : Mivs.set_bits()) {

4171

4172 if (propagate(Pair[SJ].Src, Pair[SJ].Dst,

4173 Pair[SJ].Loops, Constraints, Result.Consistent)) {

4174 Pair[SJ].Classification =

4175 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),

4176 Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),

4177 Pair[SJ].Loops);

4178 switch (Pair[SJ].Classification) {

4179 case Subscript::ZIV:

4181 break;

4182 case Subscript::SIV:

4183 Sivs.set(SJ);

4185 break;

4186 case Subscript::RDIV:

4187 case Subscript::MIV:

4188 break;

4189 default:

4191 }

4192 }

4193 }

4194 }

4195 }

4196 }

4197 }

4199 return nullptr;

4200}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

block Block Frequency Analysis

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

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

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

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

static bool isLoadOrStore(const Instruction *I)

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

static void dumpSmallBitVector(SmallBitVector &BV)

static const SCEVConstant * getConstantPart(const SCEV *Expr)

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

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

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

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

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

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

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."))

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

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

static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

uint64_t IntrinsicInst * II

static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")

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)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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

#define STATISTIC(VARNAME, DESC)

A manager for alias analyses.

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

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

A trivial helper function to check to see if the specified pointers are no-alias.

Class for arbitrary precision integers.

static 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.

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.

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....

API to communicate dependencies between analyses during invalidation.

bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)

Trigger the invalidation of some other analysis pass if not already handled and return whether it was...

A container for analyses that lazily runs them and caches their results.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

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),...

LLVM Basic Block Representation.

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...

bool runOnFunction(Function &F) override

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

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

print - Print out the internal state of the pass.

DependenceInfo & getDI() const

void releaseMemory() override

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

AnalysisPass to compute dependence information in a function.

Result run(Function &F, FunctionAnalysisManager &FAM)

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

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

Handle transitive invalidation when the cached analysis results go away.

const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)

getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...

std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)

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

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

virtual unsigned getDirection(unsigned Level) const

getDirection - Returns the direction associated with a particular level.

virtual bool isPeelFirst(unsigned Level) const

isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.

Instruction * getDst() const

getDst - Returns the destination instruction for this dependence.

virtual bool isConfused() const

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

virtual bool isSplitable(unsigned Level) const

isSplitable - Returns true if splitting this loop will break the dependence.

virtual const SCEV * getDistance(unsigned Level) const

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

virtual bool isScalar(unsigned Level) const

isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...

virtual bool isConsistent() const

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

virtual bool isPeelLast(unsigned Level) const

isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.

virtual unsigned getLevels() const

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

bool isFlow() const

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

bool isInput() const

isInput - Returns true if this is an input dependence.

bool isAnti() const

isAnti - Returns true if this is an anti dependence.

Instruction * getSrc() const

getSrc - Returns the source instruction for this dependence.

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.

void dump(raw_ostream &OS) const

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

Class representing an expression and its matching format.

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

unsigned getDirection(unsigned Level) const override

getDirection - Returns the direction associated with a particular level.

const SCEV * getDistance(unsigned Level) const override

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

bool isDirectionNegative() const override

Check if the direction vector is negative.

bool isSplitable(unsigned Level) const override

isSplitable - Returns true if splitting the loop will break the dependence.

FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, unsigned Levels)

bool isScalar(unsigned Level) const override

isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...

bool isPeelLast(unsigned Level) const override

isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.

bool isPeelFirst(unsigned Level) const override

isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.

bool normalize(ScalarEvolution *SE) override

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

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

const DataLayout & getDataLayout() const

Get the data layout of the module this function belongs to.

bool mayWriteToMemory() const LLVM_READONLY

Return true if this instruction may modify memory.

bool mayReadFromMemory() const LLVM_READONLY

Return true if this instruction may read memory.

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.

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.

unsigned getLoopDepth(const BlockT *BB) const

Return the loop nesting level of the specified block.

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.

Loop & getOutermostLoop() const

Return the outermost loop in the loop nest.

Represents a single loop in the control flow graph.

Representation for a specific memory location.

static MemoryLocation get(const LoadInst *LI)

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

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.

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

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 an addition of some number of SCEVs.

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

const SCEV * getStart() const

const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const

Return the value of this chain of recurrences at the specified iteration number.

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

This is the base class for unary integral cast operator classes.

This node represents multiplication of some number of SCEVs.

NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const

const SCEV * getOperand(unsigned i) const

This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...

This class represents an analyzed expression in the program.

ArrayRef< const SCEV * > operands() const

Return operands of this SCEV expression.

bool isOne() const

Return true if the expression is a constant one.

bool isZero() const

Return true if the expression is a constant zero.

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.

bool isKnownNonNegative(const SCEV *S)

Test if the given expression is known to be non-negative.

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

Return the SCEV object corresponding to -V.

const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)

bool isKnownNonPositive(const SCEV *S)

Test if the given expression is known to be non-positive.

bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

bool isKnownNonZero(const SCEV *S)

Test if the given expression is known to be non-zero.

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

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

const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)

const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

const SCEV * getZero(Type *Ty)

Return a SCEV for the constant 0 of a specific type.

uint64_t getTypeSizeInBits(Type *Ty) const

Return the size in bits of the specified type, for which isSCEVable must return true.

const SCEV * getConstant(ConstantInt *V)

const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

const SCEV * getOne(Type *Ty)

Return a SCEV for the constant 1 of a specific type.

bool isLoopInvariant(const SCEV *S, const Loop *L)

Return true if the value of the given SCEV is unchanging in the specified loop.

bool isKnownPositive(const SCEV *S)

Test if the given expression is known to be positive.

const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)

Get an add recurrence expression for the specified loop.

const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)

Get a canonical unsigned division expression, or something simpler if possible.

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

Return LHS-RHS.

bool hasLoopInvariantBackedgeTakenCount(const Loop *L)

Return true if the specified loop has an analyzable loop-invariant backedge-taken count.

const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

const SCEV * getPointerBase(const SCEV *V)

Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...

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.

const SCEV * getElementSize(Instruction *Inst)

Return the size of an element read or written by Inst.

const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)

Return a SCEV corresponding to a conversion of the input value to the specified type.

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

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

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.

bool any() const

Returns true if any bit is set.

size_type count() const

Returns the number of bits which are set.

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.

LLVM Value Representation.

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

#define llvm_unreachable(msg)

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

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.

APInt GreatestCommonDivisor(APInt A, APInt B)

Compute GCD of two unsigned APInt values.

@ C

The default llvm calling convention, compatible with C.

@ TB

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

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

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...

void initializeDependenceAnalysisWrapperPassPass(PassRegistry &)

const Value * getLoadStorePointerOperand(const Value *V)

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

const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)

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

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)...

raw_ostream & dbgs()

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

inst_iterator inst_end(Function *F)

bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)

Implementation of fixed size array delinearization.

constexpr unsigned BitWidth

bool isIdentifiedObject(const Value *V)

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

FunctionPass * createDependenceAnalysisWrapperPass()

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

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...

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

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

Direction

An enum for the direction of the loop.