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 SmallVector<PreconditionTy, 4> &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 decomposeGEP(GetElementPtrInst &GEP, 235 SmallVector<PreconditionTy, 4> &Preconditions, 236 bool IsSigned, const DataLayout &DL) { 237 // Do not reason about pointers where the index size is larger than 64 bits, 238 // as the coefficients used to encode constraints are 64 bit integers. 239 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64) 240 return &GEP; 241 242 if (!GEP.isInBounds()) 243 return &GEP; 244 245 // Handle the (gep (gep ....), C) case by incrementing the constant 246 // coefficient of the inner GEP, if C is a constant. 247 auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand()); 248 if (InnerGEP && GEP.getNumOperands() == 2 && 249 isa<ConstantInt>(GEP.getOperand(1))) { 250 APInt Offset = cast<ConstantInt>(GEP.getOperand(1))->getValue(); 251 auto Result = decompose(InnerGEP, Preconditions, IsSigned, DL); 252 253 auto GTI = gep_type_begin(GEP); 254 // Bail out for scalable vectors for now. 255 if (isa<ScalableVectorType>(GTI.getIndexedType())) 256 return &GEP; 257 int64_t Scale = static_cast<int64_t>( 258 DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize()); 259 260 Result.add(multiplyWithOverflow(Scale, Offset.getSExtValue())); 261 if (Offset.isNegative()) { 262 // Add pre-condition ensuring the GEP is increasing monotonically and 263 // can be de-composed. 264 Preconditions.emplace_back( 265 CmpInst::ICMP_SGE, InnerGEP->getOperand(1), 266 ConstantInt::get(InnerGEP->getOperand(1)->getType(), 267 -1 * Offset.getSExtValue())); 268 } 269 return Result; 270 } 271 272 Decomposition Result = GEP.getPointerOperand(); 273 gep_type_iterator GTI = gep_type_begin(GEP); 274 for (User::const_op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E; 275 ++I, ++GTI) { 276 Value *Index = *I; 277 278 // Bail out for scalable vectors for now. 279 if (isa<ScalableVectorType>(GTI.getIndexedType())) 280 return &GEP; 281 282 // Struct indices must be constants (and reference an existing field). Add 283 // them to the constant factor. 284 if (StructType *STy = GTI.getStructTypeOrNull()) { 285 // For a struct, add the member offset. 286 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 287 if (FieldNo == 0) 288 continue; 289 290 // Add offset to constant factor. 291 Result.add(int64_t(DL.getStructLayout(STy)->getElementOffset(FieldNo))); 292 continue; 293 } 294 295 // For an array/pointer, add the element offset, explicitly scaled. 296 unsigned Scale = DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize(); 297 298 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL); 299 IdxResult.mul(Scale); 300 Result.add(IdxResult); 301 302 // If Op0 is signed non-negative, the GEP is increasing monotonically and 303 // can be de-composed. 304 if (!isKnownNonNegative(Index, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 305 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index, 306 ConstantInt::get(Index->getType(), 0)); 307 } 308 return Result; 309 } 310 311 // Decomposes \p V into a vector of entries of the form { Coefficient, Variable 312 // } where Coefficient * Variable. The sum of the pairs equals \p V. The first 313 // pair is the constant-factor and X must be nullptr. If the expression cannot 314 // be decomposed, returns an empty vector. 315 static Decomposition decompose(Value *V, 316 SmallVector<PreconditionTy, 4> &Preconditions, 317 bool IsSigned, const DataLayout &DL) { 318 319 auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B, 320 bool IsSignedB) { 321 auto ResA = decompose(A, Preconditions, IsSigned, DL); 322 auto ResB = decompose(B, Preconditions, IsSignedB, DL); 323 ResA.add(ResB); 324 return ResA; 325 }; 326 327 // Decompose \p V used with a signed predicate. 328 if (IsSigned) { 329 if (auto *CI = dyn_cast<ConstantInt>(V)) { 330 if (canUseSExt(CI)) 331 return CI->getSExtValue(); 332 } 333 Value *Op0; 334 Value *Op1; 335 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) 336 return MergeResults(Op0, Op1, IsSigned); 337 338 return V; 339 } 340 341 if (auto *CI = dyn_cast<ConstantInt>(V)) { 342 if (CI->uge(MaxConstraintValue)) 343 return V; 344 return int64_t(CI->getZExtValue()); 345 } 346 347 if (auto *GEP = dyn_cast<GetElementPtrInst>(V)) 348 return decomposeGEP(*GEP, Preconditions, IsSigned, DL); 349 350 Value *Op0; 351 bool IsKnownPositive = false; 352 if (match(V, m_ZExt(m_Value(Op0)))) { 353 IsKnownPositive = true; 354 V = Op0; 355 } 356 357 Value *Op1; 358 ConstantInt *CI; 359 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) { 360 return MergeResults(Op0, Op1, IsSigned); 361 } 362 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) { 363 if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 364 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0, 365 ConstantInt::get(Op0->getType(), 0)); 366 if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 367 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1, 368 ConstantInt::get(Op1->getType(), 0)); 369 370 return MergeResults(Op0, Op1, IsSigned); 371 } 372 373 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() && 374 canUseSExt(CI)) { 375 Preconditions.emplace_back( 376 CmpInst::ICMP_UGE, Op0, 377 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1)); 378 return MergeResults(Op0, CI, true); 379 } 380 381 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) { 382 int64_t Mult = int64_t(std::pow(int64_t(2), CI->getSExtValue())); 383 auto Result = decompose(Op1, Preconditions, IsSigned, DL); 384 Result.mul(Mult); 385 return Result; 386 } 387 388 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) && 389 (!CI->isNegative())) { 390 auto Result = decompose(Op1, Preconditions, IsSigned, DL); 391 Result.mul(CI->getSExtValue()); 392 return Result; 393 } 394 395 if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) 396 return {-1 * CI->getSExtValue(), {{1, Op0}}}; 397 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) 398 return {0, {{1, Op0}, {-1, Op1}}}; 399 400 return {V, IsKnownPositive}; 401 } 402 403 ConstraintTy 404 ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 405 SmallVectorImpl<Value *> &NewVariables) const { 406 assert(NewVariables.empty() && "NewVariables must be empty when passed in"); 407 bool IsEq = false; 408 // Try to convert Pred to one of ULE/SLT/SLE/SLT. 409 switch (Pred) { 410 case CmpInst::ICMP_UGT: 411 case CmpInst::ICMP_UGE: 412 case CmpInst::ICMP_SGT: 413 case CmpInst::ICMP_SGE: { 414 Pred = CmpInst::getSwappedPredicate(Pred); 415 std::swap(Op0, Op1); 416 break; 417 } 418 case CmpInst::ICMP_EQ: 419 if (match(Op1, m_Zero())) { 420 Pred = CmpInst::ICMP_ULE; 421 } else { 422 IsEq = true; 423 Pred = CmpInst::ICMP_ULE; 424 } 425 break; 426 case CmpInst::ICMP_NE: 427 if (!match(Op1, m_Zero())) 428 return {}; 429 Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT); 430 std::swap(Op0, Op1); 431 break; 432 default: 433 break; 434 } 435 436 // Only ULE and ULT predicates are supported at the moment. 437 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT && 438 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT) 439 return {}; 440 441 SmallVector<PreconditionTy, 4> Preconditions; 442 bool IsSigned = CmpInst::isSigned(Pred); 443 auto &Value2Index = getValue2Index(IsSigned); 444 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(), 445 Preconditions, IsSigned, DL); 446 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(), 447 Preconditions, IsSigned, DL); 448 int64_t Offset1 = ADec.Offset; 449 int64_t Offset2 = BDec.Offset; 450 Offset1 *= -1; 451 452 auto &VariablesA = ADec.Vars; 453 auto &VariablesB = BDec.Vars; 454 455 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a 456 // new entry to NewVariables. 457 DenseMap<Value *, unsigned> NewIndexMap; 458 auto GetOrAddIndex = [&Value2Index, &NewVariables, 459 &NewIndexMap](Value *V) -> unsigned { 460 auto V2I = Value2Index.find(V); 461 if (V2I != Value2Index.end()) 462 return V2I->second; 463 auto Insert = 464 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1}); 465 if (Insert.second) 466 NewVariables.push_back(V); 467 return Insert.first->second; 468 }; 469 470 // Make sure all variables have entries in Value2Index or NewVariables. 471 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB)) 472 GetOrAddIndex(KV.Variable); 473 474 // Build result constraint, by first adding all coefficients from A and then 475 // subtracting all coefficients from B. 476 ConstraintTy Res( 477 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0), 478 IsSigned); 479 // Collect variables that are known to be positive in all uses in the 480 // constraint. 481 DenseMap<Value *, bool> KnownPositiveVariables; 482 Res.IsEq = IsEq; 483 auto &R = Res.Coefficients; 484 for (const auto &KV : VariablesA) { 485 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient; 486 auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive}); 487 I.first->second &= KV.IsKnownPositive; 488 } 489 490 for (const auto &KV : VariablesB) { 491 R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient; 492 auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive}); 493 I.first->second &= KV.IsKnownPositive; 494 } 495 496 int64_t OffsetSum; 497 if (AddOverflow(Offset1, Offset2, OffsetSum)) 498 return {}; 499 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT)) 500 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum)) 501 return {}; 502 R[0] = OffsetSum; 503 Res.Preconditions = std::move(Preconditions); 504 505 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new 506 // variables. 507 while (!NewVariables.empty()) { 508 int64_t Last = R.back(); 509 if (Last != 0) 510 break; 511 R.pop_back(); 512 Value *RemovedV = NewVariables.pop_back_val(); 513 NewIndexMap.erase(RemovedV); 514 } 515 516 // Add extra constraints for variables that are known positive. 517 for (auto &KV : KnownPositiveVariables) { 518 if (!KV.second || (Value2Index.find(KV.first) == Value2Index.end() && 519 NewIndexMap.find(KV.first) == NewIndexMap.end())) 520 continue; 521 SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0); 522 C[GetOrAddIndex(KV.first)] = -1; 523 Res.ExtraInfo.push_back(C); 524 } 525 return Res; 526 } 527 528 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred, 529 Value *Op0, 530 Value *Op1) const { 531 // If both operands are known to be non-negative, change signed predicates to 532 // unsigned ones. This increases the reasoning effectiveness in combination 533 // with the signed <-> unsigned transfer logic. 534 if (CmpInst::isSigned(Pred) && 535 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) && 536 isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 537 Pred = CmpInst::getUnsignedPredicate(Pred); 538 539 SmallVector<Value *> NewVariables; 540 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables); 541 if (R.IsEq || !NewVariables.empty()) 542 return {}; 543 return R; 544 } 545 546 bool ConstraintTy::isValid(const ConstraintInfo &Info) const { 547 return Coefficients.size() > 0 && 548 all_of(Preconditions, [&Info](const PreconditionTy &C) { 549 return Info.doesHold(C.Pred, C.Op0, C.Op1); 550 }); 551 } 552 553 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, 554 Value *B) const { 555 auto R = getConstraintForSolving(Pred, A, B); 556 return R.Preconditions.empty() && !R.empty() && 557 getCS(R.IsSigned).isConditionImplied(R.Coefficients); 558 } 559 560 void ConstraintInfo::transferToOtherSystem( 561 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, 562 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) { 563 // Check if we can combine facts from the signed and unsigned systems to 564 // derive additional facts. 565 if (!A->getType()->isIntegerTy()) 566 return; 567 // FIXME: This currently depends on the order we add facts. Ideally we 568 // would first add all known facts and only then try to add additional 569 // facts. 570 switch (Pred) { 571 default: 572 break; 573 case CmpInst::ICMP_ULT: 574 // If B is a signed positive constant, A >=s 0 and A <s B. 575 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) { 576 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn, 577 NumOut, DFSInStack); 578 addFact(CmpInst::ICMP_SLT, A, B, NumIn, NumOut, DFSInStack); 579 } 580 break; 581 case CmpInst::ICMP_SLT: 582 if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0))) 583 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack); 584 break; 585 case CmpInst::ICMP_SGT: 586 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1))) 587 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn, 588 NumOut, DFSInStack); 589 break; 590 case CmpInst::ICMP_SGE: 591 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) { 592 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack); 593 } 594 break; 595 } 596 } 597 598 namespace { 599 /// Represents either a condition that holds on entry to a block or a basic 600 /// block, with their respective Dominator DFS in and out numbers. 601 struct ConstraintOrBlock { 602 unsigned NumIn; 603 unsigned NumOut; 604 bool IsBlock; 605 bool Not; 606 union { 607 BasicBlock *BB; 608 CmpInst *Condition; 609 }; 610 611 ConstraintOrBlock(DomTreeNode *DTN) 612 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true), 613 BB(DTN->getBlock()) {} 614 ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not) 615 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false), 616 Not(Not), Condition(Condition) {} 617 }; 618 619 /// Keep state required to build worklist. 620 struct State { 621 DominatorTree &DT; 622 SmallVector<ConstraintOrBlock, 64> WorkList; 623 624 State(DominatorTree &DT) : DT(DT) {} 625 626 /// Process block \p BB and add known facts to work-list. 627 void addInfoFor(BasicBlock &BB); 628 629 /// Returns true if we can add a known condition from BB to its successor 630 /// block Succ. Each predecessor of Succ can either be BB or be dominated 631 /// by Succ (e.g. the case when adding a condition from a pre-header to a 632 /// loop header). 633 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const { 634 if (BB.getSingleSuccessor()) { 635 assert(BB.getSingleSuccessor() == Succ); 636 return DT.properlyDominates(&BB, Succ); 637 } 638 return any_of(successors(&BB), 639 [Succ](const BasicBlock *S) { return S != Succ; }) && 640 all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) { 641 return Pred == &BB || DT.dominates(Succ, Pred); 642 }); 643 } 644 }; 645 646 } // namespace 647 648 #ifndef NDEBUG 649 static void dumpWithNames(const ConstraintSystem &CS, 650 DenseMap<Value *, unsigned> &Value2Index) { 651 SmallVector<std::string> Names(Value2Index.size(), ""); 652 for (auto &KV : Value2Index) { 653 Names[KV.second - 1] = std::string("%") + KV.first->getName().str(); 654 } 655 CS.dump(Names); 656 } 657 658 static void dumpWithNames(ArrayRef<int64_t> C, 659 DenseMap<Value *, unsigned> &Value2Index) { 660 ConstraintSystem CS; 661 CS.addVariableRowFill(C); 662 dumpWithNames(CS, Value2Index); 663 } 664 #endif 665 666 void State::addInfoFor(BasicBlock &BB) { 667 WorkList.emplace_back(DT.getNode(&BB)); 668 669 // True as long as long as the current instruction is guaranteed to execute. 670 bool GuaranteedToExecute = true; 671 // Scan BB for assume calls. 672 // TODO: also use this scan to queue conditions to simplify, so we can 673 // interleave facts from assumes and conditions to simplify in a single 674 // basic block. And to skip another traversal of each basic block when 675 // simplifying. 676 for (Instruction &I : BB) { 677 Value *Cond; 678 // For now, just handle assumes with a single compare as condition. 679 if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) && 680 isa<ICmpInst>(Cond)) { 681 if (GuaranteedToExecute) { 682 // The assume is guaranteed to execute when BB is entered, hence Cond 683 // holds on entry to BB. 684 WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false); 685 } else { 686 // Otherwise the condition only holds in the successors. 687 for (BasicBlock *Succ : successors(&BB)) { 688 if (!canAddSuccessor(BB, Succ)) 689 continue; 690 WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false); 691 } 692 } 693 } 694 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I); 695 } 696 697 auto *Br = dyn_cast<BranchInst>(BB.getTerminator()); 698 if (!Br || !Br->isConditional()) 699 return; 700 701 Value *Cond = Br->getCondition(); 702 703 // If the condition is a chain of ORs/AND and the successor only has the 704 // current block as predecessor, queue conditions for the successor. 705 Value *Op0, *Op1; 706 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) || 707 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { 708 bool IsOr = match(Cond, m_LogicalOr()); 709 bool IsAnd = match(Cond, m_LogicalAnd()); 710 // If there's a select that matches both AND and OR, we need to commit to 711 // one of the options. Arbitrarily pick OR. 712 if (IsOr && IsAnd) 713 IsAnd = false; 714 715 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0); 716 if (canAddSuccessor(BB, Successor)) { 717 SmallVector<Value *> CondWorkList; 718 SmallPtrSet<Value *, 8> SeenCond; 719 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) { 720 if (SeenCond.insert(V).second) 721 CondWorkList.push_back(V); 722 }; 723 QueueValue(Op1); 724 QueueValue(Op0); 725 while (!CondWorkList.empty()) { 726 Value *Cur = CondWorkList.pop_back_val(); 727 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) { 728 WorkList.emplace_back(DT.getNode(Successor), Cmp, IsOr); 729 continue; 730 } 731 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) { 732 QueueValue(Op1); 733 QueueValue(Op0); 734 continue; 735 } 736 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { 737 QueueValue(Op1); 738 QueueValue(Op0); 739 continue; 740 } 741 } 742 } 743 return; 744 } 745 746 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition()); 747 if (!CmpI) 748 return; 749 if (canAddSuccessor(BB, Br->getSuccessor(0))) 750 WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false); 751 if (canAddSuccessor(BB, Br->getSuccessor(1))) 752 WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true); 753 } 754 755 static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) { 756 LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n"); 757 758 CmpInst::Predicate Pred = Cmp->getPredicate(); 759 Value *A = Cmp->getOperand(0); 760 Value *B = Cmp->getOperand(1); 761 762 auto R = Info.getConstraintForSolving(Pred, A, B); 763 if (R.empty() || !R.isValid(Info)){ 764 LLVM_DEBUG(dbgs() << " failed to decompose condition\n"); 765 return false; 766 } 767 768 auto &CSToUse = Info.getCS(R.IsSigned); 769 770 // If there was extra information collected during decomposition, apply 771 // it now and remove it immediately once we are done with reasoning 772 // about the constraint. 773 for (auto &Row : R.ExtraInfo) 774 CSToUse.addVariableRow(Row); 775 auto InfoRestorer = make_scope_exit([&]() { 776 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I) 777 CSToUse.popLastConstraint(); 778 }); 779 780 bool Changed = false; 781 if (CSToUse.isConditionImplied(R.Coefficients)) { 782 if (!DebugCounter::shouldExecute(EliminatedCounter)) 783 return false; 784 785 LLVM_DEBUG({ 786 dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n"; 787 dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned)); 788 }); 789 Constant *TrueC = 790 ConstantInt::getTrue(CmpInst::makeCmpResultType(Cmp->getType())); 791 Cmp->replaceUsesWithIf(TrueC, [](Use &U) { 792 // Conditions in an assume trivially simplify to true. Skip uses 793 // in assume calls to not destroy the available information. 794 auto *II = dyn_cast<IntrinsicInst>(U.getUser()); 795 return !II || II->getIntrinsicID() != Intrinsic::assume; 796 }); 797 NumCondsRemoved++; 798 Changed = true; 799 } 800 if (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients))) { 801 if (!DebugCounter::shouldExecute(EliminatedCounter)) 802 return false; 803 804 LLVM_DEBUG({ 805 dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n"; 806 dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned)); 807 }); 808 Constant *FalseC = 809 ConstantInt::getFalse(CmpInst::makeCmpResultType(Cmp->getType())); 810 Cmp->replaceAllUsesWith(FalseC); 811 NumCondsRemoved++; 812 Changed = true; 813 } 814 return Changed; 815 } 816 817 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B, 818 unsigned NumIn, unsigned NumOut, 819 SmallVectorImpl<StackEntry> &DFSInStack) { 820 // If the constraint has a pre-condition, skip the constraint if it does not 821 // hold. 822 SmallVector<Value *> NewVariables; 823 auto R = getConstraint(Pred, A, B, NewVariables); 824 if (!R.isValid(*this)) 825 return; 826 827 LLVM_DEBUG(dbgs() << "Adding '" << CmpInst::getPredicateName(Pred) << " "; 828 A->printAsOperand(dbgs(), false); dbgs() << ", "; 829 B->printAsOperand(dbgs(), false); dbgs() << "'\n"); 830 bool Added = false; 831 auto &CSToUse = getCS(R.IsSigned); 832 if (R.Coefficients.empty()) 833 return; 834 835 Added |= CSToUse.addVariableRowFill(R.Coefficients); 836 837 // If R has been added to the system, add the new variables and queue it for 838 // removal once it goes out-of-scope. 839 if (Added) { 840 SmallVector<Value *, 2> ValuesToRelease; 841 auto &Value2Index = getValue2Index(R.IsSigned); 842 for (Value *V : NewVariables) { 843 Value2Index.insert({V, Value2Index.size() + 1}); 844 ValuesToRelease.push_back(V); 845 } 846 847 LLVM_DEBUG({ 848 dbgs() << " constraint: "; 849 dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned)); 850 dbgs() << "\n"; 851 }); 852 853 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, ValuesToRelease); 854 855 if (R.IsEq) { 856 // Also add the inverted constraint for equality constraints. 857 for (auto &Coeff : R.Coefficients) 858 Coeff *= -1; 859 CSToUse.addVariableRowFill(R.Coefficients); 860 861 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, 862 SmallVector<Value *, 2>()); 863 } 864 } 865 } 866 867 static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, 868 SmallVectorImpl<Instruction *> &ToRemove) { 869 bool Changed = false; 870 IRBuilder<> Builder(II->getParent(), II->getIterator()); 871 Value *Sub = nullptr; 872 for (User *U : make_early_inc_range(II->users())) { 873 if (match(U, m_ExtractValue<0>(m_Value()))) { 874 if (!Sub) 875 Sub = Builder.CreateSub(A, B); 876 U->replaceAllUsesWith(Sub); 877 Changed = true; 878 } else if (match(U, m_ExtractValue<1>(m_Value()))) { 879 U->replaceAllUsesWith(Builder.getFalse()); 880 Changed = true; 881 } else 882 continue; 883 884 if (U->use_empty()) { 885 auto *I = cast<Instruction>(U); 886 ToRemove.push_back(I); 887 I->setOperand(0, PoisonValue::get(II->getType())); 888 Changed = true; 889 } 890 } 891 892 if (II->use_empty()) { 893 II->eraseFromParent(); 894 Changed = true; 895 } 896 return Changed; 897 } 898 899 static bool 900 tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, 901 SmallVectorImpl<Instruction *> &ToRemove) { 902 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B, 903 ConstraintInfo &Info) { 904 auto R = Info.getConstraintForSolving(Pred, A, B); 905 if (R.size() < 2 || !R.isValid(Info)) 906 return false; 907 908 auto &CSToUse = Info.getCS(R.IsSigned); 909 return CSToUse.isConditionImplied(R.Coefficients); 910 }; 911 912 bool Changed = false; 913 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) { 914 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and 915 // can be simplified to a regular sub. 916 Value *A = II->getArgOperand(0); 917 Value *B = II->getArgOperand(1); 918 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) || 919 !DoesConditionHold(CmpInst::ICMP_SGE, B, 920 ConstantInt::get(A->getType(), 0), Info)) 921 return false; 922 Changed = replaceSubOverflowUses(II, A, B, ToRemove); 923 } 924 return Changed; 925 } 926 927 static bool eliminateConstraints(Function &F, DominatorTree &DT) { 928 bool Changed = false; 929 DT.updateDFSNumbers(); 930 931 ConstraintInfo Info(F.getParent()->getDataLayout()); 932 State S(DT); 933 934 // First, collect conditions implied by branches and blocks with their 935 // Dominator DFS in and out numbers. 936 for (BasicBlock &BB : F) { 937 if (!DT.getNode(&BB)) 938 continue; 939 S.addInfoFor(BB); 940 } 941 942 // Next, sort worklist by dominance, so that dominating blocks and conditions 943 // come before blocks and conditions dominated by them. If a block and a 944 // condition have the same numbers, the condition comes before the block, as 945 // it holds on entry to the block. Also make sure conditions with constant 946 // operands come before conditions without constant operands. This increases 947 // the effectiveness of the current signed <-> unsigned fact transfer logic. 948 stable_sort( 949 S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) { 950 auto HasNoConstOp = [](const ConstraintOrBlock &B) { 951 return !B.IsBlock && !isa<ConstantInt>(B.Condition->getOperand(0)) && 952 !isa<ConstantInt>(B.Condition->getOperand(1)); 953 }; 954 bool NoConstOpA = HasNoConstOp(A); 955 bool NoConstOpB = HasNoConstOp(B); 956 return std::tie(A.NumIn, A.IsBlock, NoConstOpA) < 957 std::tie(B.NumIn, B.IsBlock, NoConstOpB); 958 }); 959 960 SmallVector<Instruction *> ToRemove; 961 962 // Finally, process ordered worklist and eliminate implied conditions. 963 SmallVector<StackEntry, 16> DFSInStack; 964 for (ConstraintOrBlock &CB : S.WorkList) { 965 // First, pop entries from the stack that are out-of-scope for CB. Remove 966 // the corresponding entry from the constraint system. 967 while (!DFSInStack.empty()) { 968 auto &E = DFSInStack.back(); 969 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut 970 << "\n"); 971 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); 972 assert(E.NumIn <= CB.NumIn); 973 if (CB.NumOut <= E.NumOut) 974 break; 975 LLVM_DEBUG({ 976 dbgs() << "Removing "; 977 dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(), 978 Info.getValue2Index(E.IsSigned)); 979 dbgs() << "\n"; 980 }); 981 982 Info.popLastConstraint(E.IsSigned); 983 // Remove variables in the system that went out of scope. 984 auto &Mapping = Info.getValue2Index(E.IsSigned); 985 for (Value *V : E.ValuesToRelease) 986 Mapping.erase(V); 987 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size()); 988 DFSInStack.pop_back(); 989 } 990 991 LLVM_DEBUG({ 992 dbgs() << "Processing "; 993 if (CB.IsBlock) 994 dbgs() << *CB.BB; 995 else 996 dbgs() << *CB.Condition; 997 dbgs() << "\n"; 998 }); 999 1000 // For a block, check if any CmpInsts become known based on the current set 1001 // of constraints. 1002 if (CB.IsBlock) { 1003 for (Instruction &I : make_early_inc_range(*CB.BB)) { 1004 if (auto *II = dyn_cast<WithOverflowInst>(&I)) { 1005 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); 1006 continue; 1007 } 1008 auto *Cmp = dyn_cast<ICmpInst>(&I); 1009 if (!Cmp) 1010 continue; 1011 1012 Changed |= checkAndReplaceCondition(Cmp, Info); 1013 } 1014 continue; 1015 } 1016 1017 ICmpInst::Predicate Pred; 1018 Value *A, *B; 1019 if (match(CB.Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) { 1020 // Use the inverse predicate if required. 1021 if (CB.Not) 1022 Pred = CmpInst::getInversePredicate(Pred); 1023 1024 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1025 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1026 } 1027 } 1028 1029 #ifndef NDEBUG 1030 unsigned SignedEntries = 1031 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; }); 1032 assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries && 1033 "updates to CS and DFSInStack are out of sync"); 1034 assert(Info.getCS(true).size() == SignedEntries && 1035 "updates to CS and DFSInStack are out of sync"); 1036 #endif 1037 1038 for (Instruction *I : ToRemove) 1039 I->eraseFromParent(); 1040 return Changed; 1041 } 1042 1043 PreservedAnalyses ConstraintEliminationPass::run(Function &F, 1044 FunctionAnalysisManager &AM) { 1045 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1046 if (!eliminateConstraints(F, DT)) 1047 return PreservedAnalyses::all(); 1048 1049 PreservedAnalyses PA; 1050 PA.preserve<DominatorTreeAnalysis>(); 1051 PA.preserveSet<CFGAnalyses>(); 1052 return PA; 1053 } 1054 1055 namespace { 1056 1057 class ConstraintElimination : public FunctionPass { 1058 public: 1059 static char ID; 1060 1061 ConstraintElimination() : FunctionPass(ID) { 1062 initializeConstraintEliminationPass(*PassRegistry::getPassRegistry()); 1063 } 1064 1065 bool runOnFunction(Function &F) override { 1066 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1067 return eliminateConstraints(F, DT); 1068 } 1069 1070 void getAnalysisUsage(AnalysisUsage &AU) const override { 1071 AU.setPreservesCFG(); 1072 AU.addRequired<DominatorTreeWrapperPass>(); 1073 AU.addPreserved<GlobalsAAWrapperPass>(); 1074 AU.addPreserved<DominatorTreeWrapperPass>(); 1075 } 1076 }; 1077 1078 } // end anonymous namespace 1079 1080 char ConstraintElimination::ID = 0; 1081 1082 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", 1083 "Constraint Elimination", false, false) 1084 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 1085 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 1086 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination", 1087 "Constraint Elimination", false, false) 1088 1089 FunctionPass *llvm::createConstraintEliminationPass() { 1090 return new ConstraintElimination(); 1091 } 1092