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
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 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".
25static SetVector<Value *> collectReferencedValues(Value *Root) {
26 SetVector<Value *> Refs;
27 std::deque<Value *> Worklist;
28 Worklist.push_back(x: Root);
29
30 while (!Worklist.empty()) {
31 Value *Val = Worklist.front();
32 Worklist.pop_front();
33 if (!Refs.insert(X: Val))
34 continue;
35
36 if (auto *O = dyn_cast<Operator>(Val)) {
37 for (Use &Op : O->operands())
38 Worklist.push_back(x: 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. array
50 // indexes)
51 if (isa<GEPOperator>(Val: Op.getUser()))
52 return false;
53 if (auto *CB = dyn_cast<CallBase>(Val: Op.getUser())) {
54 if (CB->isCallee(U: &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>(Val: V)) {
63 if (isa<UndefValue>(Val: 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>(Val: V))
73 return 3;
74
75 if (isa<GlobalValue>(Val: V))
76 return 2;
77
78 if (isa<Constant>(Val: V))
79 return 1;
80
81 if (isa<Instruction>(Val: 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.
90static void
91opportunities(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(V: RHS) - classifyReductivePower(V: 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>(Val: LHS);
123 auto *RHSInst = dyn_cast<Instruction>(Val: RHS);
124 if (LHSInst && RHSInst) {
125 if (DT.dominates(Def: LHSInst, User: 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>(Val: LHS);
132 auto *RHSArg = dyn_cast<Argument>(Val: 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: &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(Root: 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(R: llvm::make_pointer_range(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(C&: Candidates, P: [&, 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>(Val: 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(first: Candidates.begin(), last: 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(Range&: Candidates, C: 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, Callback: [&](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(Elt: {&Op, C});
217
218 AlreadyReplaced = true;
219 }
220 });
221
222 for (std::pair<Use *, Value *> P : Replacements) {
223 if (PHINode *Phi = dyn_cast<PHINode>(Val: P.first->getUser()))
224 Phi->setIncomingValueForBlock(BB: Phi->getIncomingBlock(U: *P.first), V: P.second);
225 else
226 P.first->set(P.second);
227 }
228 }
229}
230