Index: llvm/include/llvm/IR/Dominators.h =================================================================== --- llvm/include/llvm/IR/Dominators.h +++ llvm/include/llvm/IR/Dominators.h @@ -130,6 +130,11 @@ } }; +struct DominanceSources { + SmallVector Edges; + SmallVector BBs; +}; + /// Concrete subclass of DominatorTreeBase that is used to compute a /// normal dominator tree. /// Index: llvm/include/llvm/Transforms/Scalar/GVN.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/GVN.h +++ llvm/include/llvm/Transforms/Scalar/GVN.h @@ -249,6 +249,20 @@ // of BlockRPONumber prior to accessing the contents of BlockRPONumber. bool InvalidBlockRPONumbers = true; + // A mapping from a known equivalence to all the sources of dominance where + // it is valid. + struct ValuePair : std::pair { + ValuePair(Value *LHS, Value *RHS) : std::pair(LHS, RHS) {} + bool operator<(const ValuePair &Other) const { + return first != Other.first ? first < Other.first : second < Other.second; + } + }; + std::map DominatedEquivalences; + + // Walk through DominatedEquivalences and replace any users found to have + // all predecessors dominated by the same equivalence. + bool inferCollectiveDominance(); + using LoadDepVect = SmallVector; using AvailValInBlkVect = SmallVector; using UnavailBlkVect = SmallVector; @@ -343,6 +357,9 @@ bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); bool replaceOperandsForInBlockEquality(Instruction *I) const; + bool replaceDominatedUsesWith(Value *From, Value *To, + const BasicBlockEdge &Root); + bool replaceDominatedUsesWith(Value *From, Value *To, const BasicBlock *BB); bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, bool DominatesByEdge); bool processFoldableCondBr(BranchInst *BI); Index: llvm/include/llvm/Transforms/Utils/Local.h =================================================================== --- llvm/include/llvm/Transforms/Utils/Local.h +++ llvm/include/llvm/Transforms/Utils/Local.h @@ -418,6 +418,12 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); +/// Replace each use of 'From' with 'To' if that use is dominated +/// collectively by Sources. Returns the number of replacements made. +unsigned replaceDominatedUsesWith(Value *From, Value *To, + DominatorTree &DT, + DominanceSources &Sources); + /// Return true if this call calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its Index: llvm/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/lib/Transforms/Scalar/GVN.cpp +++ llvm/lib/Transforms/Scalar/GVN.cpp @@ -1994,6 +1994,31 @@ return Changed; } +bool GVN::inferCollectiveDominance() { + bool Changed = false; + for (auto &I : DominatedEquivalences) { + DominanceSources &Sources = I.second; + if (Sources.Edges.size() + Sources.BBs.size() < 2) + continue; + Value *From = I.first.first; + Value *To = I.first.second; + Changed |= llvm::replaceDominatedUsesWith(From, To, *DT, Sources); + } + return Changed; +} + +bool GVN::replaceDominatedUsesWith(Value *From, Value *To, + const BasicBlockEdge &Root) { + DominatedEquivalences[{From, To}].Edges.push_back(Root); + return llvm::replaceDominatedUsesWith(From, To, *DT, Root); +} + +bool GVN::replaceDominatedUsesWith(Value *From, Value *To, + const BasicBlock *BB) { + DominatedEquivalences[{From, To}].BBs.push_back(BB); + return llvm::replaceDominatedUsesWith(From, To, *DT, BB); +} + /// The given values are known to be equal in every block /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with /// 'RHS' everywhere in the scope. Returns whether a change was made. @@ -2059,8 +2084,8 @@ if (!LHS->hasOneUse()) { unsigned NumReplacements = DominatesByEdge - ? replaceDominatedUsesWith(LHS, RHS, *DT, Root) - : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart()); + ? replaceDominatedUsesWith(LHS, RHS, Root) + : replaceDominatedUsesWith(LHS, RHS, Root.getStart()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; @@ -2122,9 +2147,8 @@ if (NotCmp && isa(NotCmp)) { unsigned NumReplacements = DominatesByEdge - ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root) - : replaceDominatedUsesWith(NotCmp, NotVal, *DT, - Root.getStart()); + ? replaceDominatedUsesWith(NotCmp, NotVal, Root) + : replaceDominatedUsesWith(NotCmp, NotVal, Root.getStart()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; // Cached information for anything that uses NotCmp will be invalid. @@ -2712,6 +2736,8 @@ for (BasicBlock *BB : RPOT) Changed |= processBlock(BB); + Changed |= inferCollectiveDominance(); + return Changed; } @@ -2722,6 +2748,7 @@ TableAllocator.Reset(); ICF->clear(); InvalidBlockRPONumbers = true; + DominatedEquivalences.clear(); } /// Verify that the specified instruction does not occur in our Index: llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/lib/Transforms/Utils/Local.cpp +++ llvm/lib/Transforms/Utils/Local.cpp @@ -2663,6 +2663,44 @@ return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates); } +unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, + DominatorTree &DT, + DominanceSources &Sources) { + unsigned Count = 0; + for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); + UI != UE;) { + Use &U = *UI++; + bool UseDominated = true; + BasicBlock *UBB = cast(U.getUser())->getParent(); + if (!UBB->hasNPredecessorsOrMore(1)) + continue; + for (auto PI = pred_begin(UBB), E = pred_end(UBB); PI != E; ++PI) { + bool PredDominated = false; + for (const BasicBlockEdge &E : Sources.Edges) + if (DT.dominates(E, *PI)) { + PredDominated = true; + break; + } + if (PredDominated) + continue; + for (const BasicBlock *SourceBB : Sources.BBs) + if (DT.dominates(SourceBB, *PI)) { + PredDominated = true; + break; + } + if (!PredDominated) { + UseDominated = false; + break; + } + } + if (UseDominated) { + U.set(To); + ++Count; + } + } + return Count; +} + bool llvm::callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI) { // Check if the function is specifically marked as a gc leaf function. Index: llvm/test/Transforms/builtin_constant.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/builtin_constant.ll @@ -0,0 +1,90 @@ +; RUN: opt < %s -O3 -S | FileCheck %s +; +; Check that the inline asm call has a constant 0 as argument. This can be +; inferred from the function which is derived from the Linux Kernel where +; nested __builtin_constant_p:s are present. Since the inline asm operand +; constraint is "i", the argument must really be a constant 0, or else +; compilation will fail. This is checked with '-O3' and not just '-gvn', +; since it seems there is a newgvn which is supposed to replace gvn someday. + +; CHECK-LABEL: @fun +; CHECK: tail call void asm sideeffect "", "i"(i32 0) + +@a = global i32 0 +@b = global i32 0 + +define void @fun() { +entry: + %tmp = alloca i32, align 4 + %0 = load i32, i32* @a + %shl = shl i32 %0, 12 + store i32 %shl, i32* @b + %1 = load i32, i32* @b + %cmp = icmp sgt i32 %1, -129 + br i1 %cmp, label %land.lhs.true, label %land.end + +land.lhs.true: ; preds = %entry + %2 = load i32, i32* @b + %cmp1 = icmp slt i32 %2, 128 + br i1 %cmp1, label %land.rhs, label %land.end + +land.rhs: ; preds = %land.lhs.true + %3 = load i32, i32* @b + %4 = call i1 @llvm.is.constant.i32(i32 %3) + br label %land.end + +land.end: ; preds = %land.rhs, %land.lhs.true, %entry + %5 = phi i1 [ false, %land.lhs.true ], [ false, %entry ], [ %4, %land.rhs ] + %land.ext = zext i1 %5 to i32 + %6 = call i1 @llvm.is.constant.i32(i32 %land.ext) + br i1 %6, label %cond.true, label %cond.false + +cond.true: ; preds = %land.end + %7 = load i32, i32* @b + %cmp2 = icmp sgt i32 %7, -129 + br i1 %cmp2, label %land.lhs.true3, label %if.end + +land.lhs.true3: ; preds = %cond.true + %8 = load i32, i32* @b + %cmp4 = icmp slt i32 %8, 128 + br i1 %cmp4, label %land.lhs.true5, label %if.end + +land.lhs.true5: ; preds = %land.lhs.true3 + %9 = load i32, i32* @b + %10 = call i1 @llvm.is.constant.i32(i32 %9) + br i1 %10, label %if.then, label %if.end + +cond.false: ; preds = %land.end + %11 = load i32, i32* @b + %cmp6 = icmp sgt i32 %11, -129 + br i1 %cmp6, label %land.lhs.true7, label %land.end10 + +land.lhs.true7: ; preds = %cond.false + %12 = load i32, i32* @b + %cmp8 = icmp slt i32 %12, 128 + br i1 %cmp8, label %land.rhs9, label %land.end10 + +land.rhs9: ; preds = %land.lhs.true7 + %13 = load i32, i32* @b + %14 = call i1 @llvm.is.constant.i32(i32 %13) + br label %land.end10 + +land.end10: ; preds = %land.rhs9, %land.lhs.true7, %cond.false + %15 = phi i1 [ false, %land.lhs.true7 ], [ false, %cond.false ], [ %14, %land.rhs9 ] + %16 = zext i1 %15 to i64 + %cond = select i1 %15, i32 1, i32 0 + store i32 %cond, i32* %tmp + %17 = load i32, i32* %tmp + %tobool = icmp ne i32 %17, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %land.end10, %land.lhs.true5 + %18 = load i32, i32* @b + call void asm sideeffect "", "i"(i32 %18) + br label %if.end + +if.end: ; preds = %if.then, %land.end10, %land.lhs.true5, %land.lhs.true3, %cond.true + ret void +} + +declare i1 @llvm.is.constant.i32(i32) #1