| 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-exception |
| 6 |
// |
| 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 |
|
| 18 |
using 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 needed |
| 22 |
/// to get to the reference, the more behind it is found in @p Collection. Each |
| 23 |
/// step could be its own reduction, therefore we consider later values "more |
| 24 |
/// reduced". |
| 25 |
static 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 |
|
| 45 |
static 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. array |
| 50 |
// 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". |
| 61 |
static 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 by |
| 88 |
/// countOperands() and extractOperandsFromModule() to ensure consistency |
| 89 |
/// between the two. |
| 90 |
static void |
| 91 |
opportunities(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, whether |
| 100 |
// @p RHS should be preferred over @p LHS in a reduced output. This is a |
| 101 |
// 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 a |
| 113 |
// chain of definitions, |
| 114 |
// |
| 115 |
// %a = .. |
| 116 |
// %b = op %a |
| 117 |
// %c = op %b |
| 118 |
// |
| 119 |
// every use of %b can be replaced by %a, but not by a use of %c. That is, a |
| 120 |
// use %c can be replaced in steps first by %b, then by %a, making %a the |
| 121 |
// "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. Unused |
| 130 |
// 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 as |
| 151 |
// 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 set |
| 156 |
// 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 original |
| 172 |
// value. This explicitly also rules out candidates with the same |
| 173 |
// reduction power. This is to ensure that repeated invocations of this |
| 174 |
// pass eventually reach a fixpoint without switch back and forth |
| 175 |
// 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 of |
| 183 |
// 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 |
|
| 195 |
void 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 most |
| 202 |
// reduced. Candidates with less reductive power can be interpreted as an |
| 203 |
// intermediate step that is immediately replaced with the more reduced |
| 204 |
// one. The number of shouldKeep() calls must be independent of the result |
| 205 |
// of previous shouldKeep() calls to keep the total number of calls |
| 206 |
// 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 candidate |
| 214 |
// set for the following operands. Delay it until after all candidates |
| 215 |
// 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 |
else |
| 226 |
P.first->set(P.second); |
| 227 |
} |
| 228 |
} |
| 229 |
} |