From 00940fb8544767ba5217922c4ba96677aabe9eb3 Mon Sep 17 00:00:00 2001 From: David Majnemer Date: Tue, 16 Aug 2016 18:48:37 +0000 Subject: [PATCH] Make MDNode::intersect faster than O(n * m) It is pretty easy to get it down to O(nlogn + mlogm). This implementation has the added benefit of automatically deduplicating entries between the two sets. llvm-svn: 278837 --- llvm/lib/IR/Metadata.cpp | 9 ++++----- llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll | 4 ++-- llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM2.ll | 2 +- 3 files changed, 7 insertions(+), 8 deletions(-) diff --git a/llvm/lib/IR/Metadata.cpp b/llvm/lib/IR/Metadata.cpp index 9168aa0..ad95bff 100644 --- a/llvm/lib/IR/Metadata.cpp +++ b/llvm/lib/IR/Metadata.cpp @@ -875,14 +875,13 @@ MDNode *MDNode::intersect(MDNode *A, MDNode *B) { if (!A || !B) return nullptr; - SmallVector MDs; - for (Metadata *MD : A->operands()) - if (is_contained(B->operands(), MD)) - MDs.push_back(MD); + SmallSetVector MDs(A->op_begin(), A->op_end()); + SmallPtrSet BSet(B->op_begin(), B->op_end()); + MDs.remove_if([&](Metadata *MD) { return !is_contained(BSet, MD); }); // FIXME: This preserves long-standing behaviour, but is it really the right // behaviour? Or was that an unintended side-effect of node uniquing? - return getOrSelfReference(A->getContext(), MDs); + return getOrSelfReference(A->getContext(), MDs.getArrayRef()); } MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) { diff --git a/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll b/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll index 9eacbde..1c65eed 100644 --- a/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll +++ b/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll @@ -12,11 +12,11 @@ ; CHECK-NEXT: %j.113 = phi i32 [ %j.016, %for.body3.ph ], [ %inc, %for.body3 ] ; CHECK-NEXT: %idxprom = zext i32 %j.113 to i64 ; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, i32* %var1, i64 %idxprom -; CHECK-NEXT: store i32 %add, i32* %arrayidx, align 4, !alias.scope !6, !noalias !6 +; CHECK-NEXT: store i32 %add, i32* %arrayidx, align 4, !alias.scope !2, !noalias !2 ; CHECK-NEXT: %add8 = add nsw i32 %add86, %add ; CHECK-NEXT: %inc = add nuw i32 %j.113, 1 ; CHECK-NEXT: %cmp2 = icmp ult i32 %inc, %itr -; CHECK-NEXT: br i1 %cmp2, label %for.body3, label %for.inc11.loopexit.loopexit5, !llvm.loop !7 +; CHECK-NEXT: br i1 %cmp2, label %for.body3, label %for.inc11.loopexit.loopexit5, !llvm.loop !5 define i32 @foo(i32* nocapture %var1, i32* nocapture readnone %var2, i32* nocapture %var3, i32 %itr) #0 { entry: %cmp14 = icmp eq i32 %itr, 0 diff --git a/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM2.ll b/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM2.ll index a48ee89..928a652 100644 --- a/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM2.ll +++ b/llvm/test/Transforms/LoopVersioningLICM/loopversioningLICM2.ll @@ -9,7 +9,7 @@ ; ; CHECK: for.cond1.for.inc17_crit_edge.us.loopexit5: ; preds = %for.body3.us ; CHECK-NEXT: %add14.us.lcssa = phi float [ %add14.us, %for.body3.us ] -; CHECK-NEXT: store float %add14.us.lcssa, float* %arrayidx.us, align 4, !alias.scope !7, !noalias !8 +; CHECK-NEXT: store float %add14.us.lcssa, float* %arrayidx.us, align 4, !alias.scope !0, !noalias !0 ; CHECK-NEXT: br label %for.cond1.for.inc17_crit_edge.us ; define i32 @foo(float* nocapture %var2, float** nocapture readonly %var3, i32 %itr) #0 { -- 2.7.4