diff --git a/llvm/test/tools/llvm-reduce/operands-to-args.ll b/llvm/test/tools/llvm-reduce/operands-to-args.ll new file mode 100644 --- /dev/null +++ b/llvm/test/tools/llvm-reduce/operands-to-args.ll @@ -0,0 +1,56 @@ +; RUN: llvm-reduce %s -o %t --delta-passes=operands-to-args --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 + +; REDUCED-LABEL: define void @func(i32 %k, i32* %Local, i32* %Global, float* %0) { + +; Keep one reference to the original value. +; INTERESTING: %[[LOCAL:Local[0-9]*]] = alloca i32, align 4 +; INTERESTING: store i32 42, i32* %[[LOCAL]], align 4 +; INTERESTING: store i32 42, i32* @Global, align 4 + +; Everything else must use the function argument. +; REDUCED: store i32 21, i32* %Local, align 4 +; REDUCED: store i32 21, i32* %Global, align 4 +; REDUCED: store i32 0, i32* %Local, align 4 +; REDUCED: store i32 0, i32* %Global, align 4 +; REDUCED: store float 0.000000e+00, float* %0, align 4 + +; Do not add any arguments for %Keep and @GlobalKeep. +; INTERESTING: %[[KEEP:LocalKeep[0-9]*]] = add i32 %k, 21 +; INTERESTING: store i32 %[[KEEP]], i32* @GlobalKeep, align 4 + +; INTERESTING-LABEL: define void @func_caller() { +; REDUCED: call void @func(i32 21, i32* undef, i32* undef, float* undef) + + +@Global = global i32 42 +@GlobalKeep = global i32 42 + +define void @func(i32 %k) { +entry: + %Local = alloca i32, align 4 + + store i32 42, i32* %Local, align 4 + store i32 42, i32* @Global, align 4 + + store i32 21, i32* %Local, align 4 + store i32 21, i32* @Global, align 4 + + store i32 0, i32* %Local, align 4 + store i32 0, i32* @Global, align 4 + + store float 0.000000e+00, float* bitcast (i32* @Global to float*), align 4 + + %LocalKeep = add i32 %k, 21 + store i32 %LocalKeep, i32* @GlobalKeep, align 4 + + ret void +} + + +define void @func_caller() { +entry: + call void @func(i32 21) + ret void +} + diff --git a/llvm/test/tools/llvm-reduce/remove-call-site-attributes.ll b/llvm/test/tools/llvm-reduce/remove-call-site-attributes.ll --- a/llvm/test/tools/llvm-reduce/remove-call-site-attributes.ll +++ b/llvm/test/tools/llvm-reduce/remove-call-site-attributes.ll @@ -1,6 +1,6 @@ ; Test that llvm-reduce can remove uninteresting operand bundles from calls. ; -; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t +; RUN: llvm-reduce --delta-passes=operand-bundles,attributes --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t ; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s ; CHECK-ALL: declare i32 @f1(i32, i32) 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 @@ -29,6 +29,7 @@ deltas/ReduceOperandBundles.cpp deltas/ReduceSpecialGlobals.cpp deltas/ReduceOperands.cpp + deltas/ReduceOperandsToArgs.cpp llvm-reduce.cpp DEPENDS 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 @@ -28,6 +28,7 @@ #include "deltas/ReduceModuleData.h" #include "deltas/ReduceOperandBundles.h" #include "deltas/ReduceOperands.h" +#include "deltas/ReduceOperandsToArgs.h" #include "deltas/ReduceSpecialGlobals.h" #include "llvm/Support/CommandLine.h" @@ -51,6 +52,7 @@ DELTA_PASS("arguments", reduceArgumentsDeltaPass) \ DELTA_PASS("instructions", reduceInstructionsDeltaPass) \ DELTA_PASS("operands", reduceOperandsDeltaPass) \ + DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass) \ DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass) \ DELTA_PASS("attributes", reduceAttributesDeltaPass) \ DELTA_PASS("module-data", reduceModuleDataDeltaPass) diff --git a/llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.h b/llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.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_REDUCEOPERANDSTOARGS_H +#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSTOARGS_H + +#include "Delta.h" + +namespace llvm { +void reduceOperandsToArgsDeltaPass(TestRunner &Test); +} // namespace llvm + +#endif /* LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSTOARGS_H */ diff --git a/llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.cpp b/llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.cpp @@ -0,0 +1,216 @@ +//===----------------------------------------------------------------------===// +// +// 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 "ReduceOperandsToArgs.h" +#include "Delta.h" +#include "llvm/ADT/Sequence.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Cloning.h" + +using namespace llvm; + +static bool canReplaceFunction(Function *F) { + return all_of(F->uses(), [](Use &Op) { + if (auto *CI = dyn_cast(Op.getUser())) + return &CI->getCalledOperandUse() == &Op; + return false; + }); +} + +static bool canReduceUse(Use &Op) { + Value *Val = Op.get(); + Type *Ty = Val->getType(); + + // Only replace operands that can be passed-by-value. + if (!Ty->isFirstClassType()) + return false; + + // Don't pass labels as arguments. + if (Ty->isLabelTy()) + return false; + + // No need to replace values that are already arguments. + if (isa(Val)) + return false; + + // Do not replace literals. + if (isa(Val)) + return false; + + // Do not convert direct function calls to indirect calls. + if (auto *CI = dyn_cast(Op.getUser())) + if (&CI->getCalledOperandUse() == &Op) + return false; + + return true; +} + +/// Goes over OldF calls and replaces them with a call to NewF. +static void replaceFunctionCalls(Function *OldF, Function *NewF) { + SmallVector Callers; + for (Use &U : OldF->uses()) { + auto *CI = cast(U.getUser()); + assert(&U == &CI->getCalledOperandUse()); + assert(CI->getCalledFunction() == OldF); + Callers.push_back(CI); + } + + // Call arguments for NewF. + SmallVector Args(NewF->arg_size(), nullptr); + + // Fill up the additional parameters with undef values. + for (auto ArgIdx : llvm::seq(OldF->arg_size(), NewF->arg_size())) { + Type *NewArgTy = NewF->getArg(ArgIdx)->getType(); + Args[ArgIdx] = UndefValue::get(NewArgTy); + } + + for (CallBase *CI : Callers) { + // Preserve the original function arguments. + for (auto Z : zip_first(CI->args(), Args)) + std::get<1>(Z) = std::get<0>(Z); + + // Also preserve operand bundles. + SmallVector OperandBundles; + CI->getOperandBundlesAsDefs(OperandBundles); + + // Create the new function call. + CallBase *NewCI; + if (auto *II = dyn_cast(CI)) { + NewCI = InvokeInst::Create(NewF, cast(II)->getNormalDest(), + cast(II)->getUnwindDest(), Args, + OperandBundles, CI->getName()); + } else { + assert(isa(CI)); + NewCI = CallInst::Create(NewF, Args, OperandBundles, CI->getName()); + } + NewCI->setCallingConv(NewF->getCallingConv()); + + // Do the replacement for this use. + if (!CI->use_empty()) + CI->replaceAllUsesWith(NewCI); + ReplaceInstWithInst(CI, NewCI); + } +} + +/// Add a new function argument to @p F for each use in @OpsToReplace, and +/// replace those operand values with the new function argument. +static void substituteOperandWithArgument(Function *OldF, + ArrayRef OpsToReplace) { + if (OpsToReplace.empty()) + return; + + SetVector UniqueValues; + for (Use *Op : OpsToReplace) + UniqueValues.insert(Op->get()); + + // Determine the new function's signature. + SmallVector NewArgTypes; + llvm::append_range(NewArgTypes, OldF->getFunctionType()->params()); + size_t ArgOffset = NewArgTypes.size(); + for (Value *V : UniqueValues) + NewArgTypes.push_back(V->getType()); + FunctionType *FTy = + FunctionType::get(OldF->getFunctionType()->getReturnType(), NewArgTypes, + OldF->getFunctionType()->isVarArg()); + + // Create the new function... + Function *NewF = + Function::Create(FTy, OldF->getLinkage(), OldF->getAddressSpace(), + OldF->getName(), OldF->getParent()); + + // In order to preserve function order, we move NewF behind OldF + NewF->removeFromParent(); + OldF->getParent()->getFunctionList().insertAfter(OldF->getIterator(), NewF); + + // Preserve the parameters of OldF. + ValueToValueMapTy VMap; + for (auto Z : zip_first(OldF->args(), NewF->args())) { + Argument &OldArg = std::get<0>(Z); + Argument &NewArg = std::get<1>(Z); + + NewArg.setName(OldArg.getName()); // Copy the name over... + VMap[&OldArg] = &NewArg; // Add mapping to VMap + } + + // Adjust the new parameters. + ValueToValueMapTy OldValMap; + for (auto Z : zip_first(UniqueValues, drop_begin(NewF->args(), ArgOffset))) { + Value *OldVal = std::get<0>(Z); + Argument &NewArg = std::get<1>(Z); + + NewArg.setName(OldVal->getName()); + OldValMap[OldVal] = &NewArg; + } + + SmallVector Returns; // Ignore returns cloned. + CloneFunctionInto(NewF, OldF, VMap, CloneFunctionChangeType::LocalChangesOnly, + Returns, "", /*CodeInfo=*/nullptr); + + // Replace the actual operands. + for (Use *Op : OpsToReplace) { + Value *NewArg = OldValMap.lookup(Op->get()); + auto *NewUser = cast(VMap.lookup(Op->getUser())); + NewUser->setOperand(Op->getOperandNo(), NewArg); + } + + // Replace all OldF uses with NewF. + replaceFunctionCalls(OldF, NewF); + + // Rename NewF to OldF's name. + std::string FName = OldF->getName().str(); + OldF->replaceAllUsesWith(ConstantExpr::getBitCast(NewF, OldF->getType())); + OldF->eraseFromParent(); + NewF->setName(FName); +} + +static void reduceOperandsToArgs(Oracle &O, Module &Program) { + SmallVector OperandsToReduce; + for (Function &F : make_early_inc_range(Program.functions())) { + OperandsToReduce.clear(); + for (Instruction &I : instructions(&F)) { + for (Use &Op : I.operands()) { + if (!canReduceUse(Op)) + continue; + if (O.shouldKeep()) + continue; + + OperandsToReduce.push_back(&Op); + } + } + + substituteOperandWithArgument(&F, OperandsToReduce); + } +} + +/// Counts the amount of operands in the module that can be reduced. +static int countOperands(Module &Program) { + int Count = 0; + + for (Function &F : Program.functions()) { + if (!canReplaceFunction(&F)) + continue; + for (Instruction &I : instructions(&F)) { + for (Use &Op : I.operands()) { + if (!canReduceUse(Op)) + continue; + Count += 1; + } + } + } + + return Count; +} + +void llvm::reduceOperandsToArgsDeltaPass(TestRunner &Test) { + outs() << "*** Converting operands to function arguments ...\n"; + int ArgCount = countOperands(Test.getProgram()); + return runDeltaPass(Test, ArgCount, reduceOperandsToArgs); +}