From 38596a94735a3b04f6752efcd370504ed8ce7e47 Mon Sep 17 00:00:00 2001 From: Davide Italiano Date: Fri, 20 Jan 2017 23:29:28 +0000 Subject: [PATCH] [NewGVN] Optimize processing for instructions found trivially dead. Don't call `isTriviallyDeadInstructions()` once we discover that an instruction is dead. Instead, set DFS number zero (as suggested by Danny) and forget about it (this also speeds up things as we won't try to reprocess that block). Differential Revision: https://reviews.llvm.org/D28930 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@292676 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/NewGVN.cpp | 22 +++++++++++++++++++--- 1 file changed, 19 insertions(+), 3 deletions(-) diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp index 54bf973d64b..d4e41e1c0ad 100644 --- a/lib/Transforms/Scalar/NewGVN.cpp +++ b/lib/Transforms/Scalar/NewGVN.cpp @@ -242,7 +242,12 @@ class NewGVN : public FunctionPass { #endif // DFS info. + // This contains a mapping from Instructions to DFS numbers. + // The numbering starts at 1. An instruction with DFS number zero + // means that the instruction is dead. DenseMap InstrDFS; + + // This contains the mapping DFS numbers to instructions. SmallVector DFSToInstr; // Deletion info. @@ -1504,7 +1509,12 @@ void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) { // congruence finding, and updating mappings. void NewGVN::valueNumberInstruction(Instruction *I) { DEBUG(dbgs() << "Processing instruction " << *I << "\n"); - if (isInstructionTriviallyDead(I, TLI)) { + + // There's no need to call isInstructionTriviallyDead more than once on + // an instruction. Therefore, once we know that an instruction is dead + // we change its DFS number so that it doesn't get numbered again. + if (InstrDFS[I] != 0 && isInstructionTriviallyDead(I, TLI)) { + InstrDFS[I] = 0; DEBUG(dbgs() << "Skipping unused instruction\n"); markInstructionForDeletion(I); return; @@ -1705,8 +1715,14 @@ bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC, // Walk through all the instructions in all the blocks in RPO. for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1; InstrNum = TouchedInstructions.find_next(InstrNum)) { - assert(InstrNum != 0 && "Bit 0 should never be set, something touched an " - "instruction not in the lookup table"); + + // This instruction was found to be dead. We don't bother looking + // at it again. + if (InstrNum == 0) { + TouchedInstructions.reset(InstrNum); + continue; + } + Value *V = DFSToInstr[InstrNum]; BasicBlock *CurrBlock = nullptr; -- 2.50.1