llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-transforms Author: Momchil Velikov (momchil-velikov) <details> <summary>Changes</summary> RFC/discussion: https://lists.llvm.org/pipermail/llvm-dev/2021-September/152665.html This patch is a update of https://reviews.llvm.org/D110817 This patch implements simple hoisting of instructions from two single-predecessor blocks to their common predecessor, as a subroutine in the GVN pass. The patch pairs two instructions (A and B) with the same value number, moves A to the predecessor block, replaces all uses of B with A, and deletes B. Outline of the algorithm follows: Scan the then-block to collect hoist candidates ("then-" and "else-" prefixes are purely naming and have no connection to the condition in the predecessor block) Scan the else-block for hoist candidates, that match some already selected instruction from the then-block. During both scans, instructions which are not guaranteed to transfer control to the following instruction act as "hoist barriers" - after we encounter such an instruction, we select for potential hoisting/merge only instructions, which are safe to execute speculatively. Also instructions which read/write memory are not considered for hoisting, subject for a follow-up patch. The hoist barriers can itself be hoisted, opening opportunities for other instructions. For each hoist candidate pair, the immediately preceding hoist barriers from then- and else-blocks are recorded as prerequisites for hoisting the pair. Next we try hoist to hoist each candidate pair. We begin by trying to hoist dependencies of the then-instruction, which would be its immediately preceding hoist barrier and its operands. Each of these dependencies must already be in a dominating block or is itself paired with an instruction from the else-block. If we cannot hoist an dependency for whatever reason, the we stop trying to hoist the pair. Now that all the operands of the then-instruction are in a dominating block, we check the barriers/operands of the else-instruction. They all must already be in a dominating block, either initially or as a result of hoisting barriers/operands of the then-instruction. If any dependency is still in the else-block, we stop trying to hoist the pair. As a last step, we move the then-instruction to the predecessor block and delete the else-instruction. --- Patch is 55.08 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/210337.diff 18 Files Affected: - (modified) clang/test/CodeGen/attr-counted-by-with-sanitizers.c (+26-28) - (modified) llvm/include/llvm/Transforms/Scalar/GVN.h (+25) - (modified) llvm/lib/Transforms/Scalar/GVN.cpp (+231-1) - (modified) llvm/test/CodeGen/AMDGPU/memcpy-crash-issue63986.ll (+65-82) - (modified) llvm/test/CodeGen/NVPTX/gvn-scalar-pre-reg-pressure.ll (+2-2) - (modified) llvm/test/Transforms/GVN/2012-05-22-PreCrash.ll (+1-1) - (modified) llvm/test/Transforms/GVN/PRE/load-pre-across-backedge.ll (+2-2) - (modified) llvm/test/Transforms/GVN/PRE/local-pre.ll (+2-2) - (modified) llvm/test/Transforms/GVN/PRE/no-scalar-pre.ll (+4-4) - (modified) llvm/test/Transforms/GVN/PRE/phi-translate.ll (+2-2) - (modified) llvm/test/Transforms/GVN/PRE/pre-basic-add.ll (+3-3) - (modified) llvm/test/Transforms/GVN/PRE/pre-load-through-select.ll (+2-2) - (modified) llvm/test/Transforms/GVN/PRE/pre-no-cost-phi.ll (+2-2) - (modified) llvm/test/Transforms/GVN/PRE/pre-poison-add.ll (+2-2) - (modified) llvm/test/Transforms/GVN/freeze.ll (+1-1) - (modified) llvm/test/Transforms/GVN/gc_relocate.ll (+1-1) - (modified) llvm/test/Transforms/GVN/simple-gvn-hoist-limits.ll (+6-9) - (modified) llvm/test/Transforms/GVN/simple-gvn-hoist-scalars.ll (+72-35) ``````````diff diff --git a/clang/test/CodeGen/attr-counted-by-with-sanitizers.c b/clang/test/CodeGen/attr-counted-by-with-sanitizers.c index e840db632957e..81be6bdad9936 100644 --- a/clang/test/CodeGen/attr-counted-by-with-sanitizers.c +++ b/clang/test/CodeGen/attr-counted-by-with-sanitizers.c @@ -234,16 +234,16 @@ size_t test_return_bdos_cast_of_whole_struct(struct annotated *p) { // SANITIZE-WITH-ATTR: [[CONT1]]: // SANITIZE-WITH-ATTR-NEXT: [[FLEXIBLE_ARRAY_MEMBER_SIZE:%.*]] = shl i32 [[DOTCOUNTED_BY_LOAD]], 2 // SANITIZE-WITH-ATTR-NEXT: [[TMP1:%.*]] = icmp ult i32 [[INDEX]], [[DOTCOUNTED_BY_LOAD]], !nosanitize [[META6]] -// SANITIZE-WITH-ATTR-NEXT: [[IDXPROM:%.*]] = zext i32 [[INDEX]] to i64 +// SANITIZE-WITH-ATTR-NEXT: [[TMP2:%.*]] = zext i32 [[INDEX]] to i64 // SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP1]], label %[[CONT12:.*]], label %[[HANDLER_OUT_OF_BOUNDS8:.*]], !prof [[PROF7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS8]]: -// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB6:[0-9]+]], i64 [[IDXPROM]]) #[[ATTR7]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB6:[0-9]+]], i64 [[TMP2]]) #[[ATTR7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT12]]: // SANITIZE-WITH-ATTR-NEXT: [[RESULT:%.*]] = add i32 [[FLEXIBLE_ARRAY_MEMBER_SIZE]], 244 -// SANITIZE-WITH-ATTR-NEXT: [[TMP2:%.*]] = and i32 [[RESULT]], 252 -// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX10:%.*]] = getelementptr inbounds nuw [4 x i8], ptr [[ARRAY]], i64 [[IDXPROM]] -// SANITIZE-WITH-ATTR-NEXT: store i32 [[TMP2]], ptr [[ARRAYIDX10]], align 4, !tbaa [[INT_TBAA8]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP3:%.*]] = and i32 [[RESULT]], 252 +// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX10:%.*]] = getelementptr inbounds nuw [4 x i8], ptr [[ARRAY]], i64 [[TMP2]] +// SANITIZE-WITH-ATTR-NEXT: store i32 [[TMP3]], ptr [[ARRAYIDX10]], align 4, !tbaa [[INT_TBAA8]] // SANITIZE-WITH-ATTR-NEXT: [[DOTNOT79:%.*]] = icmp eq i32 [[DOTCOUNTED_BY_LOAD]], 3 // SANITIZE-WITH-ATTR-NEXT: br i1 [[DOTNOT79]], label %[[HANDLER_OUT_OF_BOUNDS18:.*]], label %[[CONT19:.*]], !prof [[PROF9:![0-9]+]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS18]]: @@ -251,37 +251,37 @@ size_t test_return_bdos_cast_of_whole_struct(struct annotated *p) { // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT19]]: // SANITIZE-WITH-ATTR-NEXT: [[ADD:%.*]] = add nuw nsw i32 [[INDEX]], 1 -// SANITIZE-WITH-ATTR-NEXT: [[TMP3:%.*]] = icmp samesign ult i32 [[ADD]], [[DOTCOUNTED_BY_LOAD]], !nosanitize [[META6]] -// SANITIZE-WITH-ATTR-NEXT: [[IDXPROM31:%.*]] = zext nneg i32 [[ADD]] to i64 -// SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP3]], label %[[CONT38:.*]], label %[[HANDLER_OUT_OF_BOUNDS34:.*]], !prof [[PROF7]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP4:%.*]] = icmp samesign ult i32 [[ADD]], [[DOTCOUNTED_BY_LOAD]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP5:%.*]] = zext nneg i32 [[ADD]] to i64 +// SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP4]], label %[[CONT38:.*]], label %[[HANDLER_OUT_OF_BOUNDS34:.*]], !prof [[PROF7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS34]]: -// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB8:[0-9]+]], i64 [[IDXPROM31]]) #[[ATTR7]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB8:[0-9]+]], i64 [[TMP5]]) #[[ATTR7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT38]]: // SANITIZE-WITH-ATTR-NEXT: [[RESULT25:%.*]] = add i32 [[FLEXIBLE_ARRAY_MEMBER_SIZE]], 240 -// SANITIZE-WITH-ATTR-NEXT: [[TMP4:%.*]] = and i32 [[RESULT25]], 252 -// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX36:%.*]] = getelementptr inbounds nuw [4 x i8], ptr [[ARRAY]], i64 [[IDXPROM31]] -// SANITIZE-WITH-ATTR-NEXT: store i32 [[TMP4]], ptr [[ARRAYIDX36]], align 4, !tbaa [[INT_TBAA8]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP6:%.*]] = and i32 [[RESULT25]], 252 +// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX36:%.*]] = getelementptr inbounds nuw [4 x i8], ptr [[ARRAY]], i64 [[TMP5]] +// SANITIZE-WITH-ATTR-NEXT: store i32 [[TMP6]], ptr [[ARRAYIDX36]], align 4, !tbaa [[INT_TBAA8]] // SANITIZE-WITH-ATTR-NEXT: [[DOTNOT:%.*]] = icmp ugt i32 [[FAM_IDX]], [[DOTCOUNTED_BY_LOAD]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: br i1 [[DOTNOT]], label %[[HANDLER_OUT_OF_BOUNDS45:.*]], label %[[CONT46:.*]], !prof [[PROF9]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS45]]: -// SANITIZE-WITH-ATTR-NEXT: [[TMP5:%.*]] = zext i32 [[FAM_IDX]] to i64, !nosanitize [[META6]] -// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB9:[0-9]+]], i64 [[TMP5]]) #[[ATTR7]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP7:%.*]] = zext i32 [[FAM_IDX]] to i64, !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB9:[0-9]+]], i64 [[TMP7]]) #[[ATTR7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT46]]: // SANITIZE-WITH-ATTR-NEXT: [[ADD59:%.*]] = add nuw nsw i32 [[INDEX]], 2 -// SANITIZE-WITH-ATTR-NEXT: [[TMP6:%.*]] = icmp samesign ult i32 [[ADD59]], [[DOTCOUNTED_BY_LOAD]], !nosanitize [[META6]] -// SANITIZE-WITH-ATTR-NEXT: [[IDXPROM60:%.*]] = zext nneg i32 [[ADD59]] to i64 -// SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP6]], label %[[CONT67:.*]], label %[[HANDLER_OUT_OF_BOUNDS63:.*]], !prof [[PROF7]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP8:%.*]] = icmp samesign ult i32 [[ADD59]], [[DOTCOUNTED_BY_LOAD]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP9:%.*]] = zext nneg i32 [[ADD59]] to i64 +// SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP8]], label %[[CONT67:.*]], label %[[HANDLER_OUT_OF_BOUNDS63:.*]], !prof [[PROF7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS63]]: -// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB10:[0-9]+]], i64 [[IDXPROM60]]) #[[ATTR7]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB10:[0-9]+]], i64 [[TMP9]]) #[[ATTR7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT67]]: -// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX65:%.*]] = getelementptr inbounds nuw [4 x i8], ptr [[ARRAY]], i64 [[IDXPROM60]] +// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX65:%.*]] = getelementptr inbounds nuw [4 x i8], ptr [[ARRAY]], i64 [[TMP9]] // SANITIZE-WITH-ATTR-NEXT: [[DOTTR:%.*]] = sub nsw i32 [[DOTCOUNTED_BY_LOAD]], [[FAM_IDX]] -// SANITIZE-WITH-ATTR-NEXT: [[TMP7:%.*]] = shl i32 [[DOTTR]], 2 -// SANITIZE-WITH-ATTR-NEXT: [[TMP8:%.*]] = and i32 [[TMP7]], 252 -// SANITIZE-WITH-ATTR-NEXT: store i32 [[TMP8]], ptr [[ARRAYIDX65]], align 4, !tbaa [[INT_TBAA8]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP10:%.*]] = shl i32 [[DOTTR]], 2 +// SANITIZE-WITH-ATTR-NEXT: [[TMP11:%.*]] = and i32 [[TMP10]], 252 +// SANITIZE-WITH-ATTR-NEXT: store i32 [[TMP11]], ptr [[ARRAYIDX65]], align 4, !tbaa [[INT_TBAA8]] // SANITIZE-WITH-ATTR-NEXT: ret void // // SANITIZE-WITHOUT-ATTR-LABEL: define dso_local void @test_assign_size_of_pointer_into_fam( @@ -483,15 +483,14 @@ size_t test_return_bdos_of_fam_in_anon_struct(struct anon_struct *p) { // SANITIZE-WITH-ATTR-NEXT: [[DOTCOUNTED_BY_LOAD:%.*]] = load i8, ptr [[TMP0]], align 4 // SANITIZE-WITH-ATTR-NEXT: [[TMP1:%.*]] = zext i8 [[DOTCOUNTED_BY_LOAD]] to i32, !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: [[TMP2:%.*]] = icmp ult i32 [[INDEX]], [[TMP1]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP3:%.*]] = zext i32 [[INDEX]] to i64 // SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP2]], label %[[CONT7:.*]], label %[[HANDLER_OUT_OF_BOUNDS:.*]], !prof [[PROF7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS]]: -// SANITIZE-WITH-ATTR-NEXT: [[TMP3:%.*]] = zext i32 [[INDEX]] to i64, !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB15:[0-9]+]], i64 [[TMP3]]) #[[ATTR7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT7]]: // SANITIZE-WITH-ATTR-NEXT: [[INTS:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 9 -// SANITIZE-WITH-ATTR-NEXT: [[IDXPROM:%.*]] = zext nneg i32 [[INDEX]] to i64 -// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds nuw i8, ptr [[INTS]], i64 [[IDXPROM]] +// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds nuw i8, ptr [[INTS]], i64 [[TMP3]] // SANITIZE-WITH-ATTR-NEXT: store i8 -1, ptr [[ARRAYIDX]], align 1, !tbaa [[CHAR_TBAA10:![0-9]+]] // SANITIZE-WITH-ATTR-NEXT: ret void // @@ -529,15 +528,14 @@ size_t test_return_bdos_of_anon_struct(struct union_of_fams *p) { // SANITIZE-WITH-ATTR-NEXT: [[COUNTED_BY_LOAD:%.*]] = load i8, ptr [[TMP0]], align 4 // SANITIZE-WITH-ATTR-NEXT: [[TMP1:%.*]] = zext i8 [[COUNTED_BY_LOAD]] to i32, !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: [[TMP2:%.*]] = icmp ult i32 [[INDEX]], [[TMP1]], !nosanitize [[META6]] +// SANITIZE-WITH-ATTR-NEXT: [[TMP3:%.*]] = zext i32 [[INDEX]] to i64 // SANITIZE-WITH-ATTR-NEXT: br i1 [[TMP2]], label %[[CONT14:.*]], label %[[HANDLER_OUT_OF_BOUNDS:.*]], !prof [[PROF7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[HANDLER_OUT_OF_BOUNDS]]: -// SANITIZE-WITH-ATTR-NEXT: [[TMP3:%.*]] = zext i32 [[INDEX]] to i64, !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: tail call void @__ubsan_handle_out_of_bounds_abort(ptr nonnull @[[GLOB16:[0-9]+]], i64 [[TMP3]]) #[[ATTR7]], !nosanitize [[META6]] // SANITIZE-WITH-ATTR-NEXT: unreachable, !nosanitize [[META6]] // SANITIZE-WITH-ATTR: [[CONT14]]: // SANITIZE-WITH-ATTR-NEXT: [[INTS:%.*]] = getelementptr inbounds nuw i8, ptr [[P]], i64 9 -// SANITIZE-WITH-ATTR-NEXT: [[IDXPROM:%.*]] = zext nneg i32 [[INDEX]] to i64 -// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds nuw i8, ptr [[INTS]], i64 [[IDXPROM]] +// SANITIZE-WITH-ATTR-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds nuw i8, ptr [[INTS]], i64 [[TMP3]] // SANITIZE-WITH-ATTR-NEXT: store i8 [[COUNTED_BY_LOAD]], ptr [[ARRAYIDX]], align 1, !tbaa [[CHAR_TBAA10]] // SANITIZE-WITH-ATTR-NEXT: ret void // diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h index 46c54363298a2..dd0fbcee1e253 100644 --- a/llvm/include/llvm/Transforms/Scalar/GVN.h +++ b/llvm/include/llvm/Transforms/Scalar/GVN.h @@ -322,6 +322,24 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { // List of critical edges to be split between iterations. SmallVector<std::pair<Instruction *, unsigned>, 4> ToSplit; + // A pair of instructions with the same value number to be hoisted and merged, + // together with their respective hoist barriers. A pair of insructions can be + // hoisted iff both their barriers (if not null) are hoisted as well. The + // `WeakVH` is used to track when the barrier instruction itself is hoisted. + struct HoistPair { + Instruction *ThenI = nullptr; + Instruction *ThenB = nullptr; + Instruction *ElseI = nullptr; + WeakVH ElseB = nullptr; + }; + + /// A mapping from value numbers to a pair of instructions. This map + /// stores pairs of instructions with the same value number, from two blocks + /// having a single common predecessor, for the duration of a single top level + /// iteration in `performHoist`. + using HoistMap = DenseMap<uint32_t, HoistPair>; + HoistMap HoistPairs; + public: GVNPass(GVNOptions Options = {}) : Options(Options) {} @@ -507,6 +525,13 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { bool performScalarPRE(Instruction *I); bool performPRE(Function &F); + void collectHoistCandidates(BasicBlock *ThenBB); + void matchHoistCandidates(BasicBlock *ElseBB); + void replaceInstruction(Instruction *I, Instruction *Repl); + std::pair<bool, bool> hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB, + BasicBlock *ElseBB, Instruction *ThenI); + bool performHoist(Function &F); + /// Main entry point for the GVN pass. Also used by the GVNLegacyPass. bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, const TargetLibraryInfo &RunTLI, AAResults &RunAA, diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 10b9dd77a3acb..b8bec704d9411 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -118,7 +118,8 @@ GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true)); static cl::opt<bool> GVNEnableMemorySSA("enable-gvn-memoryssa", cl::init(false)); - +static cl::opt<bool> GVNEnableSimpleGVNHoist("enable-simple-gvn-hoist", + cl::init(true)); static cl::opt<unsigned> ScanUsersLimit( "gvn-scan-users-limit", cl::Hidden, cl::init(100), cl::desc("The number of memory accesses to scan in a block in reaching " @@ -3723,6 +3724,230 @@ bool GVNPass::performPRE(Function &F) { return Changed; } +// Won't reorder above these instructions. +static bool isHoistBarrier(const Instruction &I) { + return I.mayWriteToMemory() || I.mayHaveSideEffects() || !isGuaranteedToTransferExecutionToSuccessor(&I); +} + +static bool isHoistCandidate(const Instruction &I) { + if (I.mayReadOrWriteMemory()) + return false; + if (!isa<CallBase>(I)) + return true; + const auto &CB = cast<CallBase>(I); + if (CB.isMustTailCall() || CB.cannotMerge()) + return false; + return true; +} + +void GVNPass::collectHoistCandidates(BasicBlock *BB) { + uint32_t Depth = 0; + Instruction *Barrier = nullptr; + for (Instruction &I : *BB) { + if (++Depth > MaxNumInsnsPerBlock) + break; + if (I.isTerminator()) + break; + if (isa<PHINode>(I)) + continue; + if (isHoistCandidate(I)) { + HoistPair &HP = HoistPairs[VN.lookupOrAdd(&I)]; + HP.ThenI = &I; + HP.ThenB = isSafeToSpeculativelyExecute(&I) ? nullptr : Barrier; + } + Barrier = isHoistBarrier(I) ? &I : Barrier; + } +} + +void GVNPass::matchHoistCandidates(BasicBlock *BB) { + uint32_t Depth = 0; + Instruction *Barrier = nullptr; + for (Instruction &I : *BB) { + if (++Depth > MaxNumInsnsPerBlock) + break; + if (I.isTerminator()) + break; + if (isa<PHINode>(I)) + continue; + if (isHoistCandidate(I)) { + uint32_t N = VN.lookupOrAdd(&I); + if (auto It = HoistPairs.find(N); + It != HoistPairs.end() && It->second.ElseI == nullptr) { + It->second.ElseI = &I; + It->second.ElseB = isSafeToSpeculativelyExecute(&I) ? nullptr : Barrier; + } + } + Barrier = isHoistBarrier(I) ? &I : Barrier; + } +} + +void GVNPass::replaceInstruction(Instruction *I, Instruction *Repl) { + LLVM_DEBUG(dbgs() << "Simple GVNHoist: replacing" << *I << " by" << *Repl + << '\n';); + patchReplacementInstruction(I, Repl); + ICF->removeUsersOf(I); + I->replaceAllUsesWith(Repl); + salvageKnowledge(I, AC); + salvageDebugInfo(*I); + if (MD) + MD->removeInstruction(I); + if (MSSAU) + MSSAU->removeMemoryAccess(I); + VN.erase(I); + ICF->removeInstruction(I); + LLVM_DEBUG(verifyRemoved(I)); + I->eraseFromParent(); + ++NumGVNInstr; +} + +// Only hoist instructions from the "then" block. +// Each hoisted instruction must be paired with an instruction from the "else" +// block. +std::pair<bool, bool> GVNPass::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB, + BasicBlock *ElseBB, Instruction *ThenI) { + // If the instruction is moved out of the "then" block there's nothing to do. + if (ThenI->getParent() != ThenBB) + return {false, false}; + + // Instruction must have already been selected for hoisting and matched with + // another instruction. + auto It = HoistPairs.find(VN.lookupOrAdd(ThenI)); + if (It == HoistPairs.end()) + return {false, true}; + + // Do not attempt to hoist a pair twice. If `ElseI` is nullptr, it means + // either there was no match for `ThenI` or there was already an attempt + // (successful or not) to hoist the pair. + Instruction *ElseI = It->second.ElseI; + if (ElseI == nullptr) + return {false, true}; + It->second.ElseI = nullptr; + + assert(ElseI->getParent() == ElseBB && "Instruction already removed"); + assert(!ThenI->mayReadOrWriteMemory() && !ElseI->mayReadOrWriteMemory() && + "Memory read/write instructions must not be hoisted."); + + bool Change = false; + + // Hoist the `Then` barrier, if any. + Instruction *ThenB = It->second.ThenB; + if (ThenB != nullptr && ThenB->getParent() == ThenBB) { + auto [LocalChange, StopHoisting] = hoistPair(DestBB, ThenBB, ElseBB, ThenB); + Change |= LocalChange; + if (StopHoisting) + return {Change, true}; + } + + // Check the `Else` barrier instruction, if any, was deleted from the `Else` + // block as a result of a previous hoisting. + if (dyn_cast_or_null<Instruction>(It->second.ElseB) != nullptr) + return {Change, true}; + + // Hoist operands. Begin by hoisting all of the operands of the "then" + // instruction, then check that all of the operands of the "else" instruction + // strictly dominate its block. + for (unsigned I = 0, N = ThenI->getNumOperands(); I < N; ++I) { + auto *Op = dyn_cast<Instruction>(ThenI->getOperand(I)); + if (Op == nullptr) + continue; + auto [LocalChange, StopHoisting] = hoistPair(DestBB, ThenBB, ElseBB, Op); + Change |= LocalChange; + if (StopHoisting) + return {Change, true}; + } + + for (unsigned I = 0, N = ElseI->getNumOperands(); I < N; ++I) { + auto *Op = dyn_cast<Instruction>(ElseI->getOperand(I)); + if (Op == nullptr) + continue; + if (Op->getParent() == ElseBB) + return {Change, true}; + } + + // Hoist one of the instructions and replace all uses of the other with it. + ICF->removeInstruction(ThenI); + ICF->insertInstructionTo(ThenI, DestBB); + ThenI->moveBefore(DestBB->getTerminator()->getIterator()); + replaceInstruction(ElseI, ThenI); + + return {true, false}; +} + +// Determine if an instruction should be used to initiate hoisting a +// dependency chain. The aim is to avoid separating instructions, for which it's +// (heuristically) considered better to keep them together, as it's common that +// they can be fused in some way. An instruction, which is denied hoisting by +// this function can still be hoisted if it appears as a dependency (e.g +// operand) of another hoisted instruction. +static bool shouldNotInitiateHoisting(const Instruction *I) { + // Don't separate GEP's from their loads/stores. + if (isa<GetElementPtrInst>(I)) + return true; + const bool IsBinop = isa<BinaryOperator>(I); + for (const User *U : I->users()) { + // Don't separate conditions from `br` or `select`. + if ((isa<CondBrInst>(U) || isa<SelectInst>(U)) && U->getOperand(0) == I) + return true; + // Don't separate a value from converting that value to a boolean by + // comparing it to zero. + if (!IsBinop) + continue; + const auto *ICmp = dyn_cast<ICmpInst>(U); + if (ICmp == nullptr || (ICmp->getPredicate() != CmpInst::ICMP_EQ && + ICmp->getPredicate() != CmpInst::ICMP_NE)) + continue; + const auto *Zero = dyn_cast<ConstantInt>(ICmp->getOperand(1)); + if (Zero != nullptr && Zero->isZero()) + return true; + } + return false; +} + +// Perform trivial hoisting of values from two blocks to their common +// predecessor. +bool GVNPass::performHoist(Function &F) { + LLVM_DEBUG(dbgs() << "Simple GVNHoist: ru... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/210337 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
