230 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "ReduceOperandsSkip.h"10#include "llvm/ADT/SetVector.h"11#include "llvm/IR/Constants.h"12#include "llvm/IR/Dominators.h"13#include "llvm/IR/InstIterator.h"14#include "llvm/IR/Instructions.h"15#include "llvm/IR/Operator.h"16#include <queue>17 18using namespace llvm;19 20/// Collect all values that are directly or indirectly referenced by @p Root,21/// including Root itself. This is a BF search such that the more steps needed22/// to get to the reference, the more behind it is found in @p Collection. Each23/// step could be its own reduction, therefore we consider later values "more24/// reduced".25static SetVector<Value *> collectReferencedValues(Value *Root) {26 SetVector<Value *> Refs;27 std::deque<Value *> Worklist;28 Worklist.push_back(Root);29 30 while (!Worklist.empty()) {31 Value *Val = Worklist.front();32 Worklist.pop_front();33 if (!Refs.insert(Val))34 continue;35 36 if (auto *O = dyn_cast<Operator>(Val)) {37 for (Use &Op : O->operands())38 Worklist.push_back(Op.get());39 }40 }41 42 return Refs;43}44 45static bool shouldReduceOperand(Use &Op) {46 Type *Ty = Op->getType();47 if (Ty->isLabelTy() || Ty->isMetadataTy())48 return false;49 // TODO: be more precise about which GEP operands we can reduce (e.g. array50 // indexes)51 if (isa<GEPOperator>(Op.getUser()))52 return false;53 if (auto *CB = dyn_cast<CallBase>(Op.getUser())) {54 if (CB->isCallee(&Op))55 return false;56 }57 return true;58}59 60/// Return a reduction priority for @p V. A higher values means "more reduced".61static int classifyReductivePower(Value *V) {62 if (auto *C = dyn_cast<ConstantData>(V)) {63 if (isa<UndefValue>(V))64 return -2;65 if (C->isNullValue())66 return 7;67 if (C->isOneValue())68 return 6;69 return 5;70 }71 72 if (isa<Argument>(V))73 return 3;74 75 if (isa<GlobalValue>(V))76 return 2;77 78 if (isa<Constant>(V))79 return 1;80 81 if (isa<Instruction>(V))82 return -1;83 84 return 0;85}86 87/// Calls @p Callback for every reduction opportunity in @p F. Used by88/// countOperands() and extractOperandsFromModule() to ensure consistency89/// between the two.90static void91opportunities(Function &F,92 function_ref<void(Use &, ArrayRef<Value *>)> Callback) {93 if (F.isDeclaration())94 return;95 96 // Need DominatorTree to find out whether an SSA value can be referenced.97 DominatorTree DT(F);98 99 // Return whether @p LHS is "more reduced" that @p RHS. That is, whether100 // @p RHS should be preferred over @p LHS in a reduced output. This is a101 // partial order, a Value may not be preferable over another.102 auto IsMoreReduced = [&DT](Value *LHS, Value *RHS) -> bool {103 // A value is not more reduced than itself.104 if (LHS == RHS)105 return false;106 107 int ReductivePowerDiff =108 classifyReductivePower(RHS) - classifyReductivePower(LHS);109 if (ReductivePowerDiff != 0)110 return ReductivePowerDiff < 0;111 112 // LHS is more reduced if it is defined further up the dominance tree. In a113 // chain of definitions,114 //115 // %a = ..116 // %b = op %a117 // %c = op %b118 //119 // every use of %b can be replaced by %a, but not by a use of %c. That is, a120 // use %c can be replaced in steps first by %b, then by %a, making %a the121 // "more reduced" choice that skips over more instructions.122 auto *LHSInst = dyn_cast<Instruction>(LHS);123 auto *RHSInst = dyn_cast<Instruction>(RHS);124 if (LHSInst && RHSInst) {125 if (DT.dominates(LHSInst, RHSInst))126 return true;127 }128 129 // Compress the number of used arguments by prefering the first ones. Unused130 // trailing argument can be removed by the arguments pass.131 auto *LHSArg = dyn_cast<Argument>(LHS);132 auto *RHSArg = dyn_cast<Argument>(RHS);133 if (LHSArg && RHSArg) {134 if (LHSArg->getArgNo() < RHSArg->getArgNo())135 return true;136 }137 138 return false;139 };140 141 for (Instruction &I : instructions(&F)) {142 for (Use &Op : I.operands()) {143 if (!shouldReduceOperand(Op))144 continue;145 Value *OpVal = Op.get();146 147 // Collect refenced values as potential replacement candidates.148 SetVector<Value *> ReferencedVals = collectReferencedValues(OpVal);149 150 // Regardless whether referenced, add the function arguments as151 // replacement possibility with the goal of reducing the number of (used)152 // function arguments, possibly created by the operands-to-args.153 ReferencedVals.insert_range(llvm::make_pointer_range(F.args()));154 155 // After all candidates have been added, it doesn't need to be a set156 // anymore.157 auto Candidates = ReferencedVals.takeVector();158 159 // Remove ineligible candidates.160 llvm::erase_if(Candidates, [&, OpVal](Value *V) {161 // Candidate value must have the same type.162 if (OpVal->getType() != V->getType())163 return true;164 165 // Do not introduce address captures of intrinsics.166 if (Function *F = dyn_cast<Function>(V)) {167 if (F->isIntrinsic())168 return true;169 }170 171 // Only consider candidates that are "more reduced" than the original172 // value. This explicitly also rules out candidates with the same173 // reduction power. This is to ensure that repeated invocations of this174 // pass eventually reach a fixpoint without switch back and forth175 // between two opportunities with the same reductive power.176 return !IsMoreReduced(V, OpVal);177 });178 179 if (Candidates.empty())180 continue;181 182 // collectReferencedValues pushed the more reductive values to the end of183 // the collection, but we need them at the front.184 std::reverse(Candidates.begin(), Candidates.end());185 186 // Independency of collectReferencedValues's idea of reductive power,187 // ensure the partial order of IsMoreReduced is enforced.188 llvm::stable_sort(Candidates, IsMoreReduced);189 190 Callback(Op, Candidates);191 }192 }193}194 195void llvm::reduceOperandsSkipDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {196 Module &Program = WorkItem.getModule();197 198 for (Function &F : Program.functions()) {199 SmallVector<std::pair<Use *, Value *>> Replacements;200 opportunities(F, [&](Use &Op, ArrayRef<Value *> Candidates) {201 // Only apply the candidate the Oracle selected to keep that is the most202 // reduced. Candidates with less reductive power can be interpreted as an203 // intermediate step that is immediately replaced with the more reduced204 // one. The number of shouldKeep() calls must be independent of the result205 // of previous shouldKeep() calls to keep the total number of calls206 // in-sync with what countOperands() has computed.207 bool AlreadyReplaced = false;208 for (Value *C : Candidates) {209 bool Keep = O.shouldKeep();210 if (AlreadyReplaced || Keep)211 continue;212 213 // Replacing the operand value immediately would influence the candidate214 // set for the following operands. Delay it until after all candidates215 // have been determined.216 Replacements.push_back({&Op, C});217 218 AlreadyReplaced = true;219 }220 });221 222 for (std::pair<Use *, Value *> P : Replacements) {223 if (PHINode *Phi = dyn_cast<PHINode>(P.first->getUser()))224 Phi->setIncomingValueForBlock(Phi->getIncomingBlock(*P.first), P.second);225 else226 P.first->set(P.second);227 }228 }229}230