diff --git a/llvm/test/tools/llvm-reduce/operands-skip.ll b/llvm/test/tools/llvm-reduce/operands-skip.ll new file mode 100644 --- /dev/null +++ b/llvm/test/tools/llvm-reduce/operands-skip.ll @@ -0,0 +1,59 @@ +; RUN: llvm-reduce %s -o %t --delta-passes=operands-skip --test FileCheck --test-arg %s --test-arg --match-full-lines --test-arg --check-prefix=INTERESTING --test-arg --input-file +; RUN: FileCheck %s --input-file %t --check-prefixes=REDUCED + +; INTERESTING: store i32 43, i32* {{(%imm|%indirect)}}, align 4 +; REDUCED: store i32 43, i32* %imm, align 4 + +; INTERESTING: store i32 44, i32* {{(%imm|%indirect|%phi)}}, align 4 +; REDUCED: store i32 44, i32* %phi, align 4 + +; INTERESTING: store i32 45, i32* {{(%imm|%indirect|%phi|%val)}}, align 4 +; REDUCED: store i32 45, i32* %val, align 4 + +; INTERESTING: store i32 46, i32* {{(%imm|%indirect|%phi|%val|@Global)}}, align 4 +; REDUCED: store i32 46, i32* @Global, align 4 + +; INTERESTING: store i32 47, i32* {{(%imm|%indirect|%phi|%val|@Global|%arg2)}}, align 4 +; REDUCED: store i32 47, i32* %arg2, align 4 + +; INTERESTING: store i32 48, i32* {{(%imm|%indirect|%phi|%val|@Global|%arg2|%arg1)}}, align 4 +; REDUCED: store i32 48, i32* %arg1, align 4 + +; INTERESTING: store i32 49, i32* {{(%imm|%indirect|%phi|%val|@Global|%arg2|%arg1|null)}}, align 4 +; REDUCED: store i32 49, i32* null, align 4 + +; REDUCED: store i32 50, i32* %arg1, align 4 +; REDUCED: store i32 51, i32* %arg1, align 4 + +@Global = global i32 42 + +define void @func(i32* %arg1, i32* %arg2) { +entry: + %val = getelementptr i32, i32* getelementptr (i32, i32* @Global, i32 1), i32 2 + br i1 undef, label %branch, label %loop + +branch: + %nondominating1 = getelementptr i32, i32* %val, i32 3 + br label %loop + +loop: + %phi = phi i32* [ null, %entry ], [ %nondominating1, %branch ], [ %nondominating2, %loop ] + %imm = getelementptr i32, i32* %phi, i32 4 + %indirect = getelementptr i32, i32* %imm, i32 5 + + store i32 43, i32* %imm, align 4 ; Don't reduce to %indirect (not "more reduced" than %imm) + store i32 44, i32* %imm, align 4 ; Reduce to %phi + store i32 45, i32* %imm, align 4 ; Reduce to %val + store i32 46, i32* %imm, align 4 ; Reduce to @Global + store i32 47, i32* %imm, align 4 ; Reduce to %arg1 + store i32 48, i32* %imm, align 4 ; Reduce to %arg2 + store i32 49, i32* %imm, align 4 ; Reduce to null + + %nondominating2 = getelementptr i32, i32* %indirect, i32 6 + br i1 undef, label %loop, label %exit + +exit: + store i32 50, i32* %arg2, align 4 ; Reduce to %arg1 (compactify function arguments) + store i32 51, i32* %arg1, align 4 ; Don't reduce + ret void +} diff --git a/llvm/tools/llvm-reduce/CMakeLists.txt b/llvm/tools/llvm-reduce/CMakeLists.txt --- a/llvm/tools/llvm-reduce/CMakeLists.txt +++ b/llvm/tools/llvm-reduce/CMakeLists.txt @@ -34,6 +34,7 @@ deltas/ReduceOperandBundles.cpp deltas/ReduceSpecialGlobals.cpp deltas/ReduceOperands.cpp + deltas/ReduceOperandsSkip.cpp deltas/ReduceOperandsToArgs.cpp deltas/ReduceInstructionsMIR.cpp llvm-reduce.cpp diff --git a/llvm/tools/llvm-reduce/DeltaManager.cpp b/llvm/tools/llvm-reduce/DeltaManager.cpp --- a/llvm/tools/llvm-reduce/DeltaManager.cpp +++ b/llvm/tools/llvm-reduce/DeltaManager.cpp @@ -30,6 +30,7 @@ #include "deltas/ReduceModuleData.h" #include "deltas/ReduceOperandBundles.h" #include "deltas/ReduceOperands.h" +#include "deltas/ReduceOperandsSkip.h" #include "deltas/ReduceOperandsToArgs.h" #include "deltas/ReduceSpecialGlobals.h" #include "llvm/Support/CommandLine.h" @@ -58,6 +59,7 @@ DELTA_PASS("operands-one", reduceOperandsOneDeltaPass) \ DELTA_PASS("operands-undef", reduceOperandsUndefDeltaPass) \ DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass) \ + DELTA_PASS("operands-skip", reduceOperandsSkipDeltaPass) \ DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass) \ DELTA_PASS("attributes", reduceAttributesDeltaPass) \ DELTA_PASS("module-data", reduceModuleDataDeltaPass) diff --git a/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.h b/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.h @@ -0,0 +1,18 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSSKIP_H +#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSSKIP_H + +#include "Delta.h" + +namespace llvm { +void reduceOperandsSkipDeltaPass(TestRunner &Test); +} // namespace llvm + +#endif /* LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSSKIP_H */ diff --git a/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp b/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp @@ -0,0 +1,219 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "ReduceOperandsSkip.h" +#include "llvm/ADT/Sequence.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Operator.h" + +using namespace llvm; + +/// Collect all values that are directly or indirectly referenced by @p Root, +/// including Root itself. This is a BF search such that the more steps needed +/// to get to the reference, the more behind it is found in @p Collection. Each +/// step could be its own reduction, therefore we consider later values "more +/// reduced". +static SetVector collectReferencedValues(Value *Root) { + SetVector Refs; + std::deque Worklist; + Worklist.push_back(Root); + + while (!Worklist.empty()) { + Value *Val = Worklist.front(); + Worklist.pop_front(); + if (!Refs.insert(Val)) + continue; + + if (auto *O = dyn_cast(Val)) { + for (Use &Op : O->operands()) + Worklist.push_back(Op.get()); + } + } + + return Refs; +} + +/// Return a reduction priority for @p V. A higher values means "more reduced". +static int classifyReductivePower(Value *V) { + if (auto *C = dyn_cast(V)) { + if (isa(V)) + return 4; + if (C->isNullValue()) + return 7; + if (C->isOneValue()) + return 6; + return 5; + } + + if (isa(V)) + return 3; + + if (isa(V)) + return 2; + + if (isa(V)) + return 1; + + if (isa(V)) + return -1; + + return 0; +} + +/// Calls @p Callback for every reduction opportunity in @p F. Used by +/// countOperands() and extractOperandsFromModule() to ensure consistency +/// between the two. +static void +opportunities(Function &F, + function_ref)> Callback) { + if (F.isDeclaration()) + return; + + // Need DominatorTree to find out whether an SSA value can be referenced. + DominatorTree DT(F); + + // Return whether @p LHS is "more reduced" that @p RHS. That is, whether + // @p RHS should be preferred over @p LHS in a reduced output. This is a + // partial order, a Value may not be preferable over another. + auto IsMoreReduced = [&DT](Value *LHS, Value *RHS) -> bool { + // A value is not more reduced than itself. + if (LHS == RHS) + return false; + + int ReductivePowerDiff = + classifyReductivePower(RHS) - classifyReductivePower(LHS); + if (ReductivePowerDiff != 0) + return ReductivePowerDiff < 0; + + // LHS is more reduced if it is defined further up the dominance tree. In a + // chain of definitions, + // + // %a = .. + // %b = op %a + // %c = op %b + // + // every use of %b can be replaced by %a, but not by a use of %c. That is, a + // use %c can be replaced in steps first by %b, then by %a, making %a the + // "more reduced" choice that skips over more instructions. + auto *LHSInst = dyn_cast(LHS); + auto *RHSInst = dyn_cast(RHS); + if (LHSInst && RHSInst) { + if (DT.dominates(LHSInst, RHSInst)) + return true; + } + + // Compress the number of used arguments by prefering the first ones. Unused + // trailing argument can be removed by the arguments pass. + auto *LHSArg = dyn_cast(LHS); + auto *RHSArg = dyn_cast(RHS); + if (LHSArg && RHSArg) { + if (LHSArg->getArgNo() < RHSArg->getArgNo()) + return true; + } + + return false; + }; + + for (Instruction &I : instructions(&F)) { + for (Use &Op : I.operands()) { + Value *OpVal = Op.get(); + + // Collect refenced values as potential replacement candidates. + SetVector ReferencedVals = collectReferencedValues(OpVal); + + // Regardless whether referenced, add the function arguments as + // replacement possibility with the goal of reducing the number of (used) + // function arguments, possibly created by the the operands-to-args. + for (Argument &Arg : F.args()) + ReferencedVals.insert(&Arg); + + // After all candidates have been added, it doesn't need to be a set + // anymore. + std::vector Candidates = ReferencedVals.takeVector(); + + // Remove ineligible candidates. + llvm::erase_if(Candidates, [&, OpVal](Value *V) { + // Candidate value must have the same type. + if (OpVal->getType() != V->getType()) + return true; + + // Only consider candidates that are "more reduced" than the original + // value. This explicitly also rules out candidates with the same + // reduction power. This is to ensure that repeated invocations of this + // pass eventually reach a fixpoint without switch back and forth + // between two opportunities with the same reductive power. + return !IsMoreReduced(V, OpVal); + }); + + if (Candidates.empty()) + continue; + + // collectReferencedValues pushed the more reductive values to the end of + // the collection, but we need them at the front. + std::reverse(Candidates.begin(), Candidates.end()); + + // Independency of collectReferencedValues's idea of reductive power, + // ensure the the partial order of IsMoreReduced is enforced. + llvm::stable_sort(Candidates, IsMoreReduced); + + Callback(Op, Candidates); + } + } +} + +static void extractOperandsFromModule(Oracle &O, Module &Program) { + for (Function &F : Program.functions()) { + SmallVector> Replacements; + opportunities(F, [&](Use &Op, ArrayRef Candidates) { + // Only apply the candidate the Oracle selected to keep that is the most + // reduced. Candidates with less reductive power can be interpreted as an + // intermediate step that is immediately replaced with the more reduced + // one. The number of shouldKeep() calls must be independent of the result + // of previous shouldKeep() calls to keep the total number of calls + // in-sync with what countOperands() has computed. + bool AlreadyReplaced = false; + for (Value *C : Candidates) { + bool Keep = O.shouldKeep(); + if (AlreadyReplaced || Keep) + continue; + + // Replacing the operand value immediately would influence the candidate + // set for the following operands. Delay it until after all candidates + // have been determined. + Replacements.push_back({&Op, C}); + + AlreadyReplaced = true; + } + }); + + for (std::pair P : Replacements) + P.first->set(P.second); + } +} + +static int countOperands(Module *Program) { + int Count = 0; + + for (Function &F : Program->functions()) { + opportunities(F, [&](Use &Op, ArrayRef Candidates) { + Count += llvm::size(Candidates); + }); + } + + return Count; +} + +void llvm::reduceOperandsSkipDeltaPass(TestRunner &Test) { + errs() << "*** Reducing operands by skipping over instructions ...\n"; + int Count = countOperands(&Test.getProgram()); + runDeltaPass(Test, Count, extractOperandsFromModule); +}