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