From a28bd85aa9f540cb99be980e92d7c73e3fe96e6e Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Fri, 6 Apr 2012 15:31:09 +0000 Subject: Make GVN's propagateEquality non-recursive. No intended functionality change. The modifications are a lot more trivial than they appear to be in the diff! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154174 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/GVN.cpp | 203 ++++++++++++++++++++++-------------------- 1 file changed, 105 insertions(+), 98 deletions(-) (limited to 'lib/Transforms/Scalar/GVN.cpp') diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 38afe1b..fb733ad 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -1974,112 +1974,119 @@ unsigned GVN::replaceAllDominatedUsesWith(Value *From, Value *To, /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with /// 'RHS' everywhere in the scope. Returns whether a change was made. bool GVN::propagateEquality(Value *LHS, Value *RHS, BasicBlock *Root) { - if (LHS == RHS) return false; - assert(LHS->getType() == RHS->getType() && "Equal but types differ!"); + SmallVector, 4> Worklist; + Worklist.push_back(std::make_pair(LHS, RHS)); + bool Changed = false; - // Don't try to propagate equalities between constants. - if (isa(LHS) && isa(RHS)) - return false; + while (!Worklist.empty()) { + std::pair Item = Worklist.pop_back_val(); + LHS = Item.first; RHS = Item.second; + + if (LHS == RHS) continue; + assert(LHS->getType() == RHS->getType() && "Equality but unequal types!"); - // Prefer a constant on the right-hand side, or an Argument if no constants. - if (isa(LHS) || (isa(LHS) && !isa(RHS))) - std::swap(LHS, RHS); - assert((isa(LHS) || isa(LHS)) && "Unexpected value!"); - - // If there is no obvious reason to prefer the left-hand side over the right- - // hand side, ensure the longest lived term is on the right-hand side, so the - // shortest lived term will be replaced by the longest lived. This tends to - // expose more simplifications. - uint32_t LVN = VN.lookup_or_add(LHS); - if ((isa(LHS) && isa(RHS)) || - (isa(LHS) && isa(RHS))) { - // Move the 'oldest' value to the right-hand side, using the value number as - // a proxy for age. - uint32_t RVN = VN.lookup_or_add(RHS); - if (LVN < RVN) { + // Don't try to propagate equalities between constants. + if (isa(LHS) && isa(RHS)) continue; + + // Prefer a constant on the right-hand side, or an Argument if no constants. + if (isa(LHS) || (isa(LHS) && !isa(RHS))) std::swap(LHS, RHS); - LVN = RVN; + assert((isa(LHS) || isa(LHS)) && "Unexpected value!"); + + // If there is no obvious reason to prefer the left-hand side over the right- + // hand side, ensure the longest lived term is on the right-hand side, so the + // shortest lived term will be replaced by the longest lived. This tends to + // expose more simplifications. + uint32_t LVN = VN.lookup_or_add(LHS); + if ((isa(LHS) && isa(RHS)) || + (isa(LHS) && isa(RHS))) { + // Move the 'oldest' value to the right-hand side, using the value number as + // a proxy for age. + uint32_t RVN = VN.lookup_or_add(RHS); + if (LVN < RVN) { + std::swap(LHS, RHS); + LVN = RVN; + } + } + assert((!isa(RHS) || + DT->properlyDominates(cast(RHS)->getParent(), Root)) && + "Instruction doesn't dominate scope!"); + + // If value numbering later deduces that an instruction in the scope is equal + // to 'LHS' then ensure it will be turned into 'RHS'. + addToLeaderTable(LVN, RHS, Root); + + // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As + // LHS always has at least one use that is not dominated by Root, this will + // never do anything if LHS has only one use. + if (!LHS->hasOneUse()) { + unsigned NumReplacements = replaceAllDominatedUsesWith(LHS, RHS, Root); + Changed |= NumReplacements > 0; + NumGVNEqProp += NumReplacements; } - } - assert((!isa(RHS) || - DT->properlyDominates(cast(RHS)->getParent(), Root)) && - "Instruction doesn't dominate scope!"); - - // If value numbering later deduces that an instruction in the scope is equal - // to 'LHS' then ensure it will be turned into 'RHS'. - addToLeaderTable(LVN, RHS, Root); - // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As - // LHS always has at least one use that is not dominated by Root, this will - // never do anything if LHS has only one use. - bool Changed = false; - if (!LHS->hasOneUse()) { - unsigned NumReplacements = replaceAllDominatedUsesWith(LHS, RHS, Root); - Changed |= NumReplacements > 0; - NumGVNEqProp += NumReplacements; - } - - // Now try to deduce additional equalities from this one. For example, if the - // known equality was "(A != B)" == "false" then it follows that A and B are - // equal in the scope. Only boolean equalities with an explicit true or false - // RHS are currently supported. - if (!RHS->getType()->isIntegerTy(1)) - // Not a boolean equality - bail out. - return Changed; - ConstantInt *CI = dyn_cast(RHS); - if (!CI) - // RHS neither 'true' nor 'false' - bail out. - return Changed; - // Whether RHS equals 'true'. Otherwise it equals 'false'. - bool isKnownTrue = CI->isAllOnesValue(); - bool isKnownFalse = !isKnownTrue; - - // If "A && B" is known true then both A and B are known true. If "A || B" - // is known false then both A and B are known false. - Value *A, *B; - if ((isKnownTrue && match(LHS, m_And(m_Value(A), m_Value(B)))) || - (isKnownFalse && match(LHS, m_Or(m_Value(A), m_Value(B))))) { - Changed |= propagateEquality(A, RHS, Root); - Changed |= propagateEquality(B, RHS, Root); - return Changed; - } + // Now try to deduce additional equalities from this one. For example, if the + // known equality was "(A != B)" == "false" then it follows that A and B are + // equal in the scope. Only boolean equalities with an explicit true or false + // RHS are currently supported. + if (!RHS->getType()->isIntegerTy(1)) + // Not a boolean equality - bail out. + continue; + ConstantInt *CI = dyn_cast(RHS); + if (!CI) + // RHS neither 'true' nor 'false' - bail out. + continue; + // Whether RHS equals 'true'. Otherwise it equals 'false'. + bool isKnownTrue = CI->isAllOnesValue(); + bool isKnownFalse = !isKnownTrue; + + // If "A && B" is known true then both A and B are known true. If "A || B" + // is known false then both A and B are known false. + Value *A, *B; + if ((isKnownTrue && match(LHS, m_And(m_Value(A), m_Value(B)))) || + (isKnownFalse && match(LHS, m_Or(m_Value(A), m_Value(B))))) { + Worklist.push_back(std::make_pair(A, RHS)); + Worklist.push_back(std::make_pair(B, RHS)); + continue; + } - // If we are propagating an equality like "(A == B)" == "true" then also - // propagate the equality A == B. When propagating a comparison such as - // "(A >= B)" == "true", replace all instances of "A < B" with "false". - if (ICmpInst *Cmp = dyn_cast(LHS)) { - Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1); - - // If "A == B" is known true, or "A != B" is known false, then replace - // A with B everywhere in the scope. - if ((isKnownTrue && Cmp->getPredicate() == CmpInst::ICMP_EQ) || - (isKnownFalse && Cmp->getPredicate() == CmpInst::ICMP_NE)) - Changed |= propagateEquality(Op0, Op1, Root); - - // If "A >= B" is known true, replace "A < B" with false everywhere. - CmpInst::Predicate NotPred = Cmp->getInversePredicate(); - Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse); - // Since we don't have the instruction "A < B" immediately to hand, work out - // the value number that it would have and use that to find an appropriate - // instruction (if any). - uint32_t NextNum = VN.getNextUnusedValueNumber(); - uint32_t Num = VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, Op0, Op1); - // If the number we were assigned was brand new then there is no point in - // looking for an instruction realizing it: there cannot be one! - if (Num < NextNum) { - Value *NotCmp = findLeader(Root, Num); - if (NotCmp && isa(NotCmp)) { - unsigned NumReplacements = - replaceAllDominatedUsesWith(NotCmp, NotVal, Root); - Changed |= NumReplacements > 0; - NumGVNEqProp += NumReplacements; + // If we are propagating an equality like "(A == B)" == "true" then also + // propagate the equality A == B. When propagating a comparison such as + // "(A >= B)" == "true", replace all instances of "A < B" with "false". + if (ICmpInst *Cmp = dyn_cast(LHS)) { + Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1); + + // If "A == B" is known true, or "A != B" is known false, then replace + // A with B everywhere in the scope. + if ((isKnownTrue && Cmp->getPredicate() == CmpInst::ICMP_EQ) || + (isKnownFalse && Cmp->getPredicate() == CmpInst::ICMP_NE)) + Worklist.push_back(std::make_pair(Op0, Op1)); + + // If "A >= B" is known true, replace "A < B" with false everywhere. + CmpInst::Predicate NotPred = Cmp->getInversePredicate(); + Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse); + // Since we don't have the instruction "A < B" immediately to hand, work out + // the value number that it would have and use that to find an appropriate + // instruction (if any). + uint32_t NextNum = VN.getNextUnusedValueNumber(); + uint32_t Num = VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, Op0, Op1); + // If the number we were assigned was brand new then there is no point in + // looking for an instruction realizing it: there cannot be one! + if (Num < NextNum) { + Value *NotCmp = findLeader(Root, Num); + if (NotCmp && isa(NotCmp)) { + unsigned NumReplacements = + replaceAllDominatedUsesWith(NotCmp, NotVal, Root); + Changed |= NumReplacements > 0; + NumGVNEqProp += NumReplacements; + } } - } - // Ensure that any instruction in scope that gets the "A < B" value number - // is replaced with false. - addToLeaderTable(Num, NotVal, Root); + // Ensure that any instruction in scope that gets the "A < B" value number + // is replaced with false. + addToLeaderTable(Num, NotVal, Root); - return Changed; + continue; + } } return Changed; -- cgit v1.1