1 //===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Eliminate conditions based on constraints collected from dominating 10 // conditions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Scalar/ConstraintElimination.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/ScopeExit.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/Analysis/ConstraintSystem.h" 20 #include "llvm/Analysis/GlobalsModRef.h" 21 #include "llvm/Analysis/ValueTracking.h" 22 #include "llvm/IR/DataLayout.h" 23 #include "llvm/IR/Dominators.h" 24 #include "llvm/IR/Function.h" 25 #include "llvm/IR/GetElementPtrTypeIterator.h" 26 #include "llvm/IR/IRBuilder.h" 27 #include "llvm/IR/Instructions.h" 28 #include "llvm/IR/PatternMatch.h" 29 #include "llvm/InitializePasses.h" 30 #include "llvm/Pass.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/DebugCounter.h" 33 #include "llvm/Support/MathExtras.h" 34 #include "llvm/Transforms/Scalar.h" 35 36 #include <cmath> 37 #include <string> 38 39 using namespace llvm; 40 using namespace PatternMatch; 41 42 #define DEBUG_TYPE "constraint-elimination" 43 44 STATISTIC(NumCondsRemoved, "Number of instructions removed"); 45 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", 46 "Controls which conditions are eliminated"); 47 48 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max(); 49 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min(); 50 51 // A helper to multiply 2 signed integers where overflowing is allowed. 52 static int64_t multiplyWithOverflow(int64_t A, int64_t B) { 53 int64_t Result; 54 MulOverflow(A, B, Result); 55 return Result; 56 } 57 58 // A helper to add 2 signed integers where overflowing is allowed. 59 static int64_t addWithOverflow(int64_t A, int64_t B) { 60 int64_t Result; 61 AddOverflow(A, B, Result); 62 return Result; 63 } 64 65 namespace { 66 67 class ConstraintInfo; 68 69 struct StackEntry { 70 unsigned NumIn; 71 unsigned NumOut; 72 bool IsSigned = false; 73 /// Variables that can be removed from the system once the stack entry gets 74 /// removed. 75 SmallVector<Value *, 2> ValuesToRelease; 76 77 StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned, 78 SmallVector<Value *, 2> ValuesToRelease) 79 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned), 80 ValuesToRelease(ValuesToRelease) {} 81 }; 82 83 /// Struct to express a pre-condition of the form %Op0 Pred %Op1. 84 struct PreconditionTy { 85 CmpInst::Predicate Pred; 86 Value *Op0; 87 Value *Op1; 88 89 PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1) 90 : Pred(Pred), Op0(Op0), Op1(Op1) {} 91 }; 92 93 struct ConstraintTy { 94 SmallVector<int64_t, 8> Coefficients; 95 SmallVector<PreconditionTy, 2> Preconditions; 96 97 SmallVector<SmallVector<int64_t, 8>> ExtraInfo; 98 99 bool IsSigned = false; 100 bool IsEq = false; 101 102 ConstraintTy() = default; 103 104 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned) 105 : Coefficients(Coefficients), IsSigned(IsSigned) {} 106 107 unsigned size() const { return Coefficients.size(); } 108 109 unsigned empty() const { return Coefficients.empty(); } 110 111 /// Returns true if all preconditions for this list of constraints are 112 /// satisfied given \p CS and the corresponding \p Value2Index mapping. 113 bool isValid(const ConstraintInfo &Info) const; 114 }; 115 116 /// Wrapper encapsulating separate constraint systems and corresponding value 117 /// mappings for both unsigned and signed information. Facts are added to and 118 /// conditions are checked against the corresponding system depending on the 119 /// signed-ness of their predicates. While the information is kept separate 120 /// based on signed-ness, certain conditions can be transferred between the two 121 /// systems. 122 class ConstraintInfo { 123 DenseMap<Value *, unsigned> UnsignedValue2Index; 124 DenseMap<Value *, unsigned> SignedValue2Index; 125 126 ConstraintSystem UnsignedCS; 127 ConstraintSystem SignedCS; 128 129 const DataLayout &DL; 130 131 public: 132 ConstraintInfo(const DataLayout &DL) : DL(DL) {} 133 134 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) { 135 return Signed ? SignedValue2Index : UnsignedValue2Index; 136 } 137 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const { 138 return Signed ? SignedValue2Index : UnsignedValue2Index; 139 } 140 141 ConstraintSystem &getCS(bool Signed) { 142 return Signed ? SignedCS : UnsignedCS; 143 } 144 const ConstraintSystem &getCS(bool Signed) const { 145 return Signed ? SignedCS : UnsignedCS; 146 } 147 148 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); } 149 void popLastNVariables(bool Signed, unsigned N) { 150 getCS(Signed).popLastNVariables(N); 151 } 152 153 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const; 154 155 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, 156 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack); 157 158 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 159 /// constraints, using indices from the corresponding constraint system. 160 /// New variables that need to be added to the system are collected in 161 /// \p NewVariables. 162 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 163 SmallVectorImpl<Value *> &NewVariables) const; 164 165 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 166 /// constraints using getConstraint. Returns an empty constraint if the result 167 /// cannot be used to query the existing constraint system, e.g. because it 168 /// would require adding new variables. Also tries to convert signed 169 /// predicates to unsigned ones if possible to allow using the unsigned system 170 /// which increases the effectiveness of the signed <-> unsigned transfer 171 /// logic. 172 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0, 173 Value *Op1) const; 174 175 /// Try to add information from \p A \p Pred \p B to the unsigned/signed 176 /// system if \p Pred is signed/unsigned. 177 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B, 178 unsigned NumIn, unsigned NumOut, 179 SmallVectorImpl<StackEntry> &DFSInStack); 180 }; 181 182 /// Represents a (Coefficient * Variable) entry after IR decomposition. 183 struct DecompEntry { 184 int64_t Coefficient; 185 Value *Variable; 186 /// True if the variable is known positive in the current constraint. 187 bool IsKnownPositive; 188 189 DecompEntry(int64_t Coefficient, Value *Variable, 190 bool IsKnownPositive = false) 191 : Coefficient(Coefficient), Variable(Variable), 192 IsKnownPositive(IsKnownPositive) {} 193 }; 194 195 /// Represents an Offset + Coefficient1 * Variable1 + ... decomposition. 196 struct Decomposition { 197 int64_t Offset = 0; 198 SmallVector<DecompEntry, 3> Vars; 199 200 Decomposition(int64_t Offset) : Offset(Offset) {} 201 Decomposition(Value *V, bool IsKnownPositive = false) { 202 Vars.emplace_back(1, V, IsKnownPositive); 203 } 204 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars) 205 : Offset(Offset), Vars(Vars) {} 206 207 void add(int64_t OtherOffset) { 208 Offset = addWithOverflow(Offset, OtherOffset); 209 } 210 211 void add(const Decomposition &Other) { 212 add(Other.Offset); 213 append_range(Vars, Other.Vars); 214 } 215 216 void mul(int64_t Factor) { 217 Offset = multiplyWithOverflow(Offset, Factor); 218 for (auto &Var : Vars) 219 Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor); 220 } 221 }; 222 223 } // namespace 224 225 static Decomposition decompose(Value *V, 226 SmallVectorImpl<PreconditionTy> &Preconditions, 227 bool IsSigned, const DataLayout &DL); 228 229 static bool canUseSExt(ConstantInt *CI) { 230 const APInt &Val = CI->getValue(); 231 return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue); 232 } 233 234 static Decomposition 235 decomposeGEP(GetElementPtrInst &GEP, 236 SmallVectorImpl<PreconditionTy> &Preconditions, bool IsSigned, 237 const DataLayout &DL) { 238 // Do not reason about pointers where the index size is larger than 64 bits, 239 // as the coefficients used to encode constraints are 64 bit integers. 240 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64) 241 return &GEP; 242 243 if (!GEP.isInBounds()) 244 return &GEP; 245 246 Type *PtrTy = GEP.getType()->getScalarType(); 247 unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy); 248 MapVector<Value *, APInt> VariableOffsets; 249 APInt ConstantOffset(BitWidth, 0); 250 if (!GEP.collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) 251 return &GEP; 252 253 // Handle the (gep (gep ....), C) case by incrementing the constant 254 // coefficient of the inner GEP, if C is a constant. 255 auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand()); 256 if (VariableOffsets.empty() && InnerGEP && InnerGEP->getNumOperands() == 2) { 257 auto Result = decompose(InnerGEP, Preconditions, IsSigned, DL); 258 Result.add(ConstantOffset.getSExtValue()); 259 260 if (ConstantOffset.isNegative()) { 261 unsigned Scale = DL.getTypeAllocSize(InnerGEP->getResultElementType()); 262 int64_t ConstantOffsetI = ConstantOffset.getSExtValue(); 263 if (ConstantOffsetI % Scale != 0) 264 return &GEP; 265 // Add pre-condition ensuring the GEP is increasing monotonically and 266 // can be de-composed. 267 // Both sides are normalized by being divided by Scale. 268 Preconditions.emplace_back( 269 CmpInst::ICMP_SGE, InnerGEP->getOperand(1), 270 ConstantInt::get(InnerGEP->getOperand(1)->getType(), 271 -1 * (ConstantOffsetI / Scale))); 272 } 273 return Result; 274 } 275 276 Decomposition Result(ConstantOffset.getSExtValue(), 277 DecompEntry(1, GEP.getPointerOperand())); 278 for (auto [Index, Scale] : VariableOffsets) { 279 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL); 280 IdxResult.mul(Scale.getSExtValue()); 281 Result.add(IdxResult); 282 283 // If Op0 is signed non-negative, the GEP is increasing monotonically and 284 // can be de-composed. 285 if (!isKnownNonNegative(Index, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 286 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index, 287 ConstantInt::get(Index->getType(), 0)); 288 } 289 return Result; 290 } 291 292 // Decomposes \p V into a constant offset + list of pairs { Coefficient, 293 // Variable } where Coefficient * Variable. The sum of the constant offset and 294 // pairs equals \p V. 295 static Decomposition decompose(Value *V, 296 SmallVectorImpl<PreconditionTy> &Preconditions, 297 bool IsSigned, const DataLayout &DL) { 298 299 auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B, 300 bool IsSignedB) { 301 auto ResA = decompose(A, Preconditions, IsSigned, DL); 302 auto ResB = decompose(B, Preconditions, IsSignedB, DL); 303 ResA.add(ResB); 304 return ResA; 305 }; 306 307 // Decompose \p V used with a signed predicate. 308 if (IsSigned) { 309 if (auto *CI = dyn_cast<ConstantInt>(V)) { 310 if (canUseSExt(CI)) 311 return CI->getSExtValue(); 312 } 313 Value *Op0; 314 Value *Op1; 315 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) 316 return MergeResults(Op0, Op1, IsSigned); 317 318 return V; 319 } 320 321 if (auto *CI = dyn_cast<ConstantInt>(V)) { 322 if (CI->uge(MaxConstraintValue)) 323 return V; 324 return int64_t(CI->getZExtValue()); 325 } 326 327 if (auto *GEP = dyn_cast<GetElementPtrInst>(V)) 328 return decomposeGEP(*GEP, Preconditions, IsSigned, DL); 329 330 Value *Op0; 331 bool IsKnownPositive = false; 332 if (match(V, m_ZExt(m_Value(Op0)))) { 333 IsKnownPositive = true; 334 V = Op0; 335 } 336 337 Value *Op1; 338 ConstantInt *CI; 339 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) { 340 return MergeResults(Op0, Op1, IsSigned); 341 } 342 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) { 343 if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 344 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0, 345 ConstantInt::get(Op0->getType(), 0)); 346 if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 347 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1, 348 ConstantInt::get(Op1->getType(), 0)); 349 350 return MergeResults(Op0, Op1, IsSigned); 351 } 352 353 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() && 354 canUseSExt(CI)) { 355 Preconditions.emplace_back( 356 CmpInst::ICMP_UGE, Op0, 357 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1)); 358 return MergeResults(Op0, CI, true); 359 } 360 361 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) { 362 int64_t Mult = int64_t(std::pow(int64_t(2), CI->getSExtValue())); 363 auto Result = decompose(Op1, Preconditions, IsSigned, DL); 364 Result.mul(Mult); 365 return Result; 366 } 367 368 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) && 369 (!CI->isNegative())) { 370 auto Result = decompose(Op1, Preconditions, IsSigned, DL); 371 Result.mul(CI->getSExtValue()); 372 return Result; 373 } 374 375 if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) 376 return {-1 * CI->getSExtValue(), {{1, Op0}}}; 377 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) 378 return {0, {{1, Op0}, {-1, Op1}}}; 379 380 return {V, IsKnownPositive}; 381 } 382 383 ConstraintTy 384 ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 385 SmallVectorImpl<Value *> &NewVariables) const { 386 assert(NewVariables.empty() && "NewVariables must be empty when passed in"); 387 bool IsEq = false; 388 // Try to convert Pred to one of ULE/SLT/SLE/SLT. 389 switch (Pred) { 390 case CmpInst::ICMP_UGT: 391 case CmpInst::ICMP_UGE: 392 case CmpInst::ICMP_SGT: 393 case CmpInst::ICMP_SGE: { 394 Pred = CmpInst::getSwappedPredicate(Pred); 395 std::swap(Op0, Op1); 396 break; 397 } 398 case CmpInst::ICMP_EQ: 399 if (match(Op1, m_Zero())) { 400 Pred = CmpInst::ICMP_ULE; 401 } else { 402 IsEq = true; 403 Pred = CmpInst::ICMP_ULE; 404 } 405 break; 406 case CmpInst::ICMP_NE: 407 if (!match(Op1, m_Zero())) 408 return {}; 409 Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT); 410 std::swap(Op0, Op1); 411 break; 412 default: 413 break; 414 } 415 416 // Only ULE and ULT predicates are supported at the moment. 417 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT && 418 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT) 419 return {}; 420 421 SmallVector<PreconditionTy, 4> Preconditions; 422 bool IsSigned = CmpInst::isSigned(Pred); 423 auto &Value2Index = getValue2Index(IsSigned); 424 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(), 425 Preconditions, IsSigned, DL); 426 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(), 427 Preconditions, IsSigned, DL); 428 int64_t Offset1 = ADec.Offset; 429 int64_t Offset2 = BDec.Offset; 430 Offset1 *= -1; 431 432 auto &VariablesA = ADec.Vars; 433 auto &VariablesB = BDec.Vars; 434 435 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a 436 // new entry to NewVariables. 437 DenseMap<Value *, unsigned> NewIndexMap; 438 auto GetOrAddIndex = [&Value2Index, &NewVariables, 439 &NewIndexMap](Value *V) -> unsigned { 440 auto V2I = Value2Index.find(V); 441 if (V2I != Value2Index.end()) 442 return V2I->second; 443 auto Insert = 444 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1}); 445 if (Insert.second) 446 NewVariables.push_back(V); 447 return Insert.first->second; 448 }; 449 450 // Make sure all variables have entries in Value2Index or NewVariables. 451 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB)) 452 GetOrAddIndex(KV.Variable); 453 454 // Build result constraint, by first adding all coefficients from A and then 455 // subtracting all coefficients from B. 456 ConstraintTy Res( 457 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0), 458 IsSigned); 459 // Collect variables that are known to be positive in all uses in the 460 // constraint. 461 DenseMap<Value *, bool> KnownPositiveVariables; 462 Res.IsEq = IsEq; 463 auto &R = Res.Coefficients; 464 for (const auto &KV : VariablesA) { 465 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient; 466 auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive}); 467 I.first->second &= KV.IsKnownPositive; 468 } 469 470 for (const auto &KV : VariablesB) { 471 R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient; 472 auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive}); 473 I.first->second &= KV.IsKnownPositive; 474 } 475 476 int64_t OffsetSum; 477 if (AddOverflow(Offset1, Offset2, OffsetSum)) 478 return {}; 479 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT)) 480 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum)) 481 return {}; 482 R[0] = OffsetSum; 483 Res.Preconditions = std::move(Preconditions); 484 485 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new 486 // variables. 487 while (!NewVariables.empty()) { 488 int64_t Last = R.back(); 489 if (Last != 0) 490 break; 491 R.pop_back(); 492 Value *RemovedV = NewVariables.pop_back_val(); 493 NewIndexMap.erase(RemovedV); 494 } 495 496 // Add extra constraints for variables that are known positive. 497 for (auto &KV : KnownPositiveVariables) { 498 if (!KV.second || (Value2Index.find(KV.first) == Value2Index.end() && 499 NewIndexMap.find(KV.first) == NewIndexMap.end())) 500 continue; 501 SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0); 502 C[GetOrAddIndex(KV.first)] = -1; 503 Res.ExtraInfo.push_back(C); 504 } 505 return Res; 506 } 507 508 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred, 509 Value *Op0, 510 Value *Op1) const { 511 // If both operands are known to be non-negative, change signed predicates to 512 // unsigned ones. This increases the reasoning effectiveness in combination 513 // with the signed <-> unsigned transfer logic. 514 if (CmpInst::isSigned(Pred) && 515 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) && 516 isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 517 Pred = CmpInst::getUnsignedPredicate(Pred); 518 519 SmallVector<Value *> NewVariables; 520 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables); 521 if (R.IsEq || !NewVariables.empty()) 522 return {}; 523 return R; 524 } 525 526 bool ConstraintTy::isValid(const ConstraintInfo &Info) const { 527 return Coefficients.size() > 0 && 528 all_of(Preconditions, [&Info](const PreconditionTy &C) { 529 return Info.doesHold(C.Pred, C.Op0, C.Op1); 530 }); 531 } 532 533 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, 534 Value *B) const { 535 auto R = getConstraintForSolving(Pred, A, B); 536 return R.Preconditions.empty() && !R.empty() && 537 getCS(R.IsSigned).isConditionImplied(R.Coefficients); 538 } 539 540 void ConstraintInfo::transferToOtherSystem( 541 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, 542 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) { 543 // Check if we can combine facts from the signed and unsigned systems to 544 // derive additional facts. 545 if (!A->getType()->isIntegerTy()) 546 return; 547 // FIXME: This currently depends on the order we add facts. Ideally we 548 // would first add all known facts and only then try to add additional 549 // facts. 550 switch (Pred) { 551 default: 552 break; 553 case CmpInst::ICMP_ULT: 554 // If B is a signed positive constant, A >=s 0 and A <s B. 555 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) { 556 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn, 557 NumOut, DFSInStack); 558 addFact(CmpInst::ICMP_SLT, A, B, NumIn, NumOut, DFSInStack); 559 } 560 break; 561 case CmpInst::ICMP_SLT: 562 if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0))) 563 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack); 564 break; 565 case CmpInst::ICMP_SGT: 566 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1))) 567 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn, 568 NumOut, DFSInStack); 569 break; 570 case CmpInst::ICMP_SGE: 571 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) { 572 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack); 573 } 574 break; 575 } 576 } 577 578 namespace { 579 /// Represents either a condition that holds on entry to a block or a basic 580 /// block, with their respective Dominator DFS in and out numbers. 581 struct ConstraintOrBlock { 582 unsigned NumIn; 583 unsigned NumOut; 584 bool IsBlock; 585 bool Not; 586 union { 587 BasicBlock *BB; 588 CmpInst *Condition; 589 }; 590 591 ConstraintOrBlock(DomTreeNode *DTN) 592 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true), 593 BB(DTN->getBlock()) {} 594 ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not) 595 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false), 596 Not(Not), Condition(Condition) {} 597 }; 598 599 /// Keep state required to build worklist. 600 struct State { 601 DominatorTree &DT; 602 SmallVector<ConstraintOrBlock, 64> WorkList; 603 604 State(DominatorTree &DT) : DT(DT) {} 605 606 /// Process block \p BB and add known facts to work-list. 607 void addInfoFor(BasicBlock &BB); 608 609 /// Returns true if we can add a known condition from BB to its successor 610 /// block Succ. Each predecessor of Succ can either be BB or be dominated 611 /// by Succ (e.g. the case when adding a condition from a pre-header to a 612 /// loop header). 613 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const { 614 if (BB.getSingleSuccessor()) { 615 assert(BB.getSingleSuccessor() == Succ); 616 return DT.properlyDominates(&BB, Succ); 617 } 618 return any_of(successors(&BB), 619 [Succ](const BasicBlock *S) { return S != Succ; }) && 620 all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) { 621 return Pred == &BB || DT.dominates(Succ, Pred); 622 }); 623 } 624 }; 625 626 } // namespace 627 628 #ifndef NDEBUG 629 static void dumpWithNames(const ConstraintSystem &CS, 630 DenseMap<Value *, unsigned> &Value2Index) { 631 SmallVector<std::string> Names(Value2Index.size(), ""); 632 for (auto &KV : Value2Index) { 633 Names[KV.second - 1] = std::string("%") + KV.first->getName().str(); 634 } 635 CS.dump(Names); 636 } 637 638 static void dumpWithNames(ArrayRef<int64_t> C, 639 DenseMap<Value *, unsigned> &Value2Index) { 640 ConstraintSystem CS; 641 CS.addVariableRowFill(C); 642 dumpWithNames(CS, Value2Index); 643 } 644 #endif 645 646 void State::addInfoFor(BasicBlock &BB) { 647 WorkList.emplace_back(DT.getNode(&BB)); 648 649 // True as long as long as the current instruction is guaranteed to execute. 650 bool GuaranteedToExecute = true; 651 // Scan BB for assume calls. 652 // TODO: also use this scan to queue conditions to simplify, so we can 653 // interleave facts from assumes and conditions to simplify in a single 654 // basic block. And to skip another traversal of each basic block when 655 // simplifying. 656 for (Instruction &I : BB) { 657 Value *Cond; 658 // For now, just handle assumes with a single compare as condition. 659 if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) && 660 isa<ICmpInst>(Cond)) { 661 if (GuaranteedToExecute) { 662 // The assume is guaranteed to execute when BB is entered, hence Cond 663 // holds on entry to BB. 664 WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false); 665 } else { 666 // Otherwise the condition only holds in the successors. 667 for (BasicBlock *Succ : successors(&BB)) { 668 if (!canAddSuccessor(BB, Succ)) 669 continue; 670 WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false); 671 } 672 } 673 } 674 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I); 675 } 676 677 auto *Br = dyn_cast<BranchInst>(BB.getTerminator()); 678 if (!Br || !Br->isConditional()) 679 return; 680 681 Value *Cond = Br->getCondition(); 682 683 // If the condition is a chain of ORs/AND and the successor only has the 684 // current block as predecessor, queue conditions for the successor. 685 Value *Op0, *Op1; 686 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) || 687 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { 688 bool IsOr = match(Cond, m_LogicalOr()); 689 bool IsAnd = match(Cond, m_LogicalAnd()); 690 // If there's a select that matches both AND and OR, we need to commit to 691 // one of the options. Arbitrarily pick OR. 692 if (IsOr && IsAnd) 693 IsAnd = false; 694 695 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0); 696 if (canAddSuccessor(BB, Successor)) { 697 SmallVector<Value *> CondWorkList; 698 SmallPtrSet<Value *, 8> SeenCond; 699 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) { 700 if (SeenCond.insert(V).second) 701 CondWorkList.push_back(V); 702 }; 703 QueueValue(Op1); 704 QueueValue(Op0); 705 while (!CondWorkList.empty()) { 706 Value *Cur = CondWorkList.pop_back_val(); 707 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) { 708 WorkList.emplace_back(DT.getNode(Successor), Cmp, IsOr); 709 continue; 710 } 711 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) { 712 QueueValue(Op1); 713 QueueValue(Op0); 714 continue; 715 } 716 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { 717 QueueValue(Op1); 718 QueueValue(Op0); 719 continue; 720 } 721 } 722 } 723 return; 724 } 725 726 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition()); 727 if (!CmpI) 728 return; 729 if (canAddSuccessor(BB, Br->getSuccessor(0))) 730 WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false); 731 if (canAddSuccessor(BB, Br->getSuccessor(1))) 732 WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true); 733 } 734 735 static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) { 736 LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n"); 737 738 CmpInst::Predicate Pred = Cmp->getPredicate(); 739 Value *A = Cmp->getOperand(0); 740 Value *B = Cmp->getOperand(1); 741 742 auto R = Info.getConstraintForSolving(Pred, A, B); 743 if (R.empty() || !R.isValid(Info)){ 744 LLVM_DEBUG(dbgs() << " failed to decompose condition\n"); 745 return false; 746 } 747 748 auto &CSToUse = Info.getCS(R.IsSigned); 749 750 // If there was extra information collected during decomposition, apply 751 // it now and remove it immediately once we are done with reasoning 752 // about the constraint. 753 for (auto &Row : R.ExtraInfo) 754 CSToUse.addVariableRow(Row); 755 auto InfoRestorer = make_scope_exit([&]() { 756 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I) 757 CSToUse.popLastConstraint(); 758 }); 759 760 bool Changed = false; 761 if (CSToUse.isConditionImplied(R.Coefficients)) { 762 if (!DebugCounter::shouldExecute(EliminatedCounter)) 763 return false; 764 765 LLVM_DEBUG({ 766 dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n"; 767 dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned)); 768 }); 769 Constant *TrueC = 770 ConstantInt::getTrue(CmpInst::makeCmpResultType(Cmp->getType())); 771 Cmp->replaceUsesWithIf(TrueC, [](Use &U) { 772 // Conditions in an assume trivially simplify to true. Skip uses 773 // in assume calls to not destroy the available information. 774 auto *II = dyn_cast<IntrinsicInst>(U.getUser()); 775 return !II || II->getIntrinsicID() != Intrinsic::assume; 776 }); 777 NumCondsRemoved++; 778 Changed = true; 779 } 780 if (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients))) { 781 if (!DebugCounter::shouldExecute(EliminatedCounter)) 782 return false; 783 784 LLVM_DEBUG({ 785 dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n"; 786 dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned)); 787 }); 788 Constant *FalseC = 789 ConstantInt::getFalse(CmpInst::makeCmpResultType(Cmp->getType())); 790 Cmp->replaceAllUsesWith(FalseC); 791 NumCondsRemoved++; 792 Changed = true; 793 } 794 return Changed; 795 } 796 797 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B, 798 unsigned NumIn, unsigned NumOut, 799 SmallVectorImpl<StackEntry> &DFSInStack) { 800 // If the constraint has a pre-condition, skip the constraint if it does not 801 // hold. 802 SmallVector<Value *> NewVariables; 803 auto R = getConstraint(Pred, A, B, NewVariables); 804 if (!R.isValid(*this)) 805 return; 806 807 LLVM_DEBUG(dbgs() << "Adding '" << CmpInst::getPredicateName(Pred) << " "; 808 A->printAsOperand(dbgs(), false); dbgs() << ", "; 809 B->printAsOperand(dbgs(), false); dbgs() << "'\n"); 810 bool Added = false; 811 auto &CSToUse = getCS(R.IsSigned); 812 if (R.Coefficients.empty()) 813 return; 814 815 Added |= CSToUse.addVariableRowFill(R.Coefficients); 816 817 // If R has been added to the system, add the new variables and queue it for 818 // removal once it goes out-of-scope. 819 if (Added) { 820 SmallVector<Value *, 2> ValuesToRelease; 821 auto &Value2Index = getValue2Index(R.IsSigned); 822 for (Value *V : NewVariables) { 823 Value2Index.insert({V, Value2Index.size() + 1}); 824 ValuesToRelease.push_back(V); 825 } 826 827 LLVM_DEBUG({ 828 dbgs() << " constraint: "; 829 dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned)); 830 dbgs() << "\n"; 831 }); 832 833 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, ValuesToRelease); 834 835 if (R.IsEq) { 836 // Also add the inverted constraint for equality constraints. 837 for (auto &Coeff : R.Coefficients) 838 Coeff *= -1; 839 CSToUse.addVariableRowFill(R.Coefficients); 840 841 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, 842 SmallVector<Value *, 2>()); 843 } 844 } 845 } 846 847 static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, 848 SmallVectorImpl<Instruction *> &ToRemove) { 849 bool Changed = false; 850 IRBuilder<> Builder(II->getParent(), II->getIterator()); 851 Value *Sub = nullptr; 852 for (User *U : make_early_inc_range(II->users())) { 853 if (match(U, m_ExtractValue<0>(m_Value()))) { 854 if (!Sub) 855 Sub = Builder.CreateSub(A, B); 856 U->replaceAllUsesWith(Sub); 857 Changed = true; 858 } else if (match(U, m_ExtractValue<1>(m_Value()))) { 859 U->replaceAllUsesWith(Builder.getFalse()); 860 Changed = true; 861 } else 862 continue; 863 864 if (U->use_empty()) { 865 auto *I = cast<Instruction>(U); 866 ToRemove.push_back(I); 867 I->setOperand(0, PoisonValue::get(II->getType())); 868 Changed = true; 869 } 870 } 871 872 if (II->use_empty()) { 873 II->eraseFromParent(); 874 Changed = true; 875 } 876 return Changed; 877 } 878 879 static bool 880 tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, 881 SmallVectorImpl<Instruction *> &ToRemove) { 882 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B, 883 ConstraintInfo &Info) { 884 auto R = Info.getConstraintForSolving(Pred, A, B); 885 if (R.size() < 2 || !R.isValid(Info)) 886 return false; 887 888 auto &CSToUse = Info.getCS(R.IsSigned); 889 return CSToUse.isConditionImplied(R.Coefficients); 890 }; 891 892 bool Changed = false; 893 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) { 894 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and 895 // can be simplified to a regular sub. 896 Value *A = II->getArgOperand(0); 897 Value *B = II->getArgOperand(1); 898 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) || 899 !DoesConditionHold(CmpInst::ICMP_SGE, B, 900 ConstantInt::get(A->getType(), 0), Info)) 901 return false; 902 Changed = replaceSubOverflowUses(II, A, B, ToRemove); 903 } 904 return Changed; 905 } 906 907 static bool eliminateConstraints(Function &F, DominatorTree &DT) { 908 bool Changed = false; 909 DT.updateDFSNumbers(); 910 911 ConstraintInfo Info(F.getParent()->getDataLayout()); 912 State S(DT); 913 914 // First, collect conditions implied by branches and blocks with their 915 // Dominator DFS in and out numbers. 916 for (BasicBlock &BB : F) { 917 if (!DT.getNode(&BB)) 918 continue; 919 S.addInfoFor(BB); 920 } 921 922 // Next, sort worklist by dominance, so that dominating blocks and conditions 923 // come before blocks and conditions dominated by them. If a block and a 924 // condition have the same numbers, the condition comes before the block, as 925 // it holds on entry to the block. Also make sure conditions with constant 926 // operands come before conditions without constant operands. This increases 927 // the effectiveness of the current signed <-> unsigned fact transfer logic. 928 stable_sort( 929 S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) { 930 auto HasNoConstOp = [](const ConstraintOrBlock &B) { 931 return !B.IsBlock && !isa<ConstantInt>(B.Condition->getOperand(0)) && 932 !isa<ConstantInt>(B.Condition->getOperand(1)); 933 }; 934 bool NoConstOpA = HasNoConstOp(A); 935 bool NoConstOpB = HasNoConstOp(B); 936 return std::tie(A.NumIn, A.IsBlock, NoConstOpA) < 937 std::tie(B.NumIn, B.IsBlock, NoConstOpB); 938 }); 939 940 SmallVector<Instruction *> ToRemove; 941 942 // Finally, process ordered worklist and eliminate implied conditions. 943 SmallVector<StackEntry, 16> DFSInStack; 944 for (ConstraintOrBlock &CB : S.WorkList) { 945 // First, pop entries from the stack that are out-of-scope for CB. Remove 946 // the corresponding entry from the constraint system. 947 while (!DFSInStack.empty()) { 948 auto &E = DFSInStack.back(); 949 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut 950 << "\n"); 951 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); 952 assert(E.NumIn <= CB.NumIn); 953 if (CB.NumOut <= E.NumOut) 954 break; 955 LLVM_DEBUG({ 956 dbgs() << "Removing "; 957 dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(), 958 Info.getValue2Index(E.IsSigned)); 959 dbgs() << "\n"; 960 }); 961 962 Info.popLastConstraint(E.IsSigned); 963 // Remove variables in the system that went out of scope. 964 auto &Mapping = Info.getValue2Index(E.IsSigned); 965 for (Value *V : E.ValuesToRelease) 966 Mapping.erase(V); 967 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size()); 968 DFSInStack.pop_back(); 969 } 970 971 LLVM_DEBUG({ 972 dbgs() << "Processing "; 973 if (CB.IsBlock) 974 dbgs() << *CB.BB; 975 else 976 dbgs() << *CB.Condition; 977 dbgs() << "\n"; 978 }); 979 980 // For a block, check if any CmpInsts become known based on the current set 981 // of constraints. 982 if (CB.IsBlock) { 983 for (Instruction &I : make_early_inc_range(*CB.BB)) { 984 if (auto *II = dyn_cast<WithOverflowInst>(&I)) { 985 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); 986 continue; 987 } 988 auto *Cmp = dyn_cast<ICmpInst>(&I); 989 if (!Cmp) 990 continue; 991 992 Changed |= checkAndReplaceCondition(Cmp, Info); 993 } 994 continue; 995 } 996 997 ICmpInst::Predicate Pred; 998 Value *A, *B; 999 if (match(CB.Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) { 1000 // Use the inverse predicate if required. 1001 if (CB.Not) 1002 Pred = CmpInst::getInversePredicate(Pred); 1003 1004 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1005 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1006 } 1007 } 1008 1009 #ifndef NDEBUG 1010 unsigned SignedEntries = 1011 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; }); 1012 assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries && 1013 "updates to CS and DFSInStack are out of sync"); 1014 assert(Info.getCS(true).size() == SignedEntries && 1015 "updates to CS and DFSInStack are out of sync"); 1016 #endif 1017 1018 for (Instruction *I : ToRemove) 1019 I->eraseFromParent(); 1020 return Changed; 1021 } 1022 1023 PreservedAnalyses ConstraintEliminationPass::run(Function &F, 1024 FunctionAnalysisManager &AM) { 1025 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1026 if (!eliminateConstraints(F, DT)) 1027 return PreservedAnalyses::all(); 1028 1029 PreservedAnalyses PA; 1030 PA.preserve<DominatorTreeAnalysis>(); 1031 PA.preserveSet<CFGAnalyses>(); 1032 return PA; 1033 } 1034 1035 namespace { 1036 1037 class ConstraintElimination : public FunctionPass { 1038 public: 1039 static char ID; 1040 1041 ConstraintElimination() : FunctionPass(ID) { 1042 initializeConstraintEliminationPass(*PassRegistry::getPassRegistry()); 1043 } 1044 1045 bool runOnFunction(Function &F) override { 1046 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1047 return eliminateConstraints(F, DT); 1048 } 1049 1050 void getAnalysisUsage(AnalysisUsage &AU) const override { 1051 AU.setPreservesCFG(); 1052 AU.addRequired<DominatorTreeWrapperPass>(); 1053 AU.addPreserved<GlobalsAAWrapperPass>(); 1054 AU.addPreserved<DominatorTreeWrapperPass>(); 1055 } 1056 }; 1057 1058 } // end anonymous namespace 1059 1060 char ConstraintElimination::ID = 0; 1061 1062 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", 1063 "Constraint Elimination", false, false) 1064 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 1065 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 1066 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination", 1067 "Constraint Elimination", false, false) 1068 1069 FunctionPass *llvm::createConstraintEliminationPass() { 1070 return new ConstraintElimination(); 1071 } 1072