From 14b956f5300ad4c834c49f8b8ac32653b0281b68 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sat, 12 Jan 2019 09:09:15 +0000 Subject: [PATCH] Reapply "[DemandedBits] Use SetVector for Worklist" DemandedBits currently uses a simple vector for the worklist, which means that instructions may be inserted multiple times into it. Especially in combination with the deep lattice, this may cause instructions too be recomputed very often. To avoid this, switch to a SetVector. Reapplying with a smaller number of inline elements in the SmallSetVector, to avoid running into the SmallDenseMap issue described in D56455. Differential Revision: https://reviews.llvm.org/D56362 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@350997 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/DemandedBits.cpp | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-) diff --git a/lib/Analysis/DemandedBits.cpp b/lib/Analysis/DemandedBits.cpp index ba310d8d321..34f785fb02b 100644 --- a/lib/Analysis/DemandedBits.cpp +++ b/lib/Analysis/DemandedBits.cpp @@ -21,8 +21,7 @@ #include "llvm/Analysis/DemandedBits.h" #include "llvm/ADT/APInt.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ValueTracking.h" @@ -315,7 +314,7 @@ void DemandedBits::performAnalysis() { AliveBits.clear(); DeadUses.clear(); - SmallVector Worklist; + SmallSetVector Worklist; // Collect the set of "root" instructions that are known live. for (Instruction &I : instructions(F)) { @@ -330,7 +329,7 @@ void DemandedBits::performAnalysis() { Type *T = I.getType(); if (T->isIntOrIntVectorTy()) { if (AliveBits.try_emplace(&I, T->getScalarSizeInBits(), 0).second) - Worklist.push_back(&I); + Worklist.insert(&I); continue; } @@ -341,7 +340,7 @@ void DemandedBits::performAnalysis() { Type *T = J->getType(); if (T->isIntOrIntVectorTy()) AliveBits[J] = APInt::getAllOnesValue(T->getScalarSizeInBits()); - Worklist.push_back(J); + Worklist.insert(J); } } // To save memory, we don't add I to the Visited set here. Instead, we @@ -412,11 +411,11 @@ void DemandedBits::performAnalysis() { APInt ABNew = AB | ABPrev; if (ABNew != ABPrev || ABI == AliveBits.end()) { AliveBits[I] = std::move(ABNew); - Worklist.push_back(I); + Worklist.insert(I); } } } else if (I && !Visited.count(I)) { - Worklist.push_back(I); + Worklist.insert(I); } } } -- 2.50.1