xref: /openbsd-src/gnu/llvm/llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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 
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".
collectReferencedValues(Value * Root)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 
shouldReduceOperand(Use & Op)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->getCalledOperandUse() == &Op)
55       return false;
56   }
57   return true;
58 }
59 
60 /// Return a reduction priority for @p V. A higher values means "more reduced".
classifyReductivePower(Value * V)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
opportunities(Function & F,function_ref<void (Use &,ArrayRef<Value * >)> Callback)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 the operands-to-args.
153       for (Argument &Arg : F.args())
154         ReferencedVals.insert(&Arg);
155 
156       // After all candidates have been added, it doesn't need to be a set
157       // anymore.
158       std::vector<Value *> Candidates = ReferencedVals.takeVector();
159 
160       // Remove ineligible candidates.
161       llvm::erase_if(Candidates, [&, OpVal](Value *V) {
162         // Candidate value must have the same type.
163         if (OpVal->getType() != V->getType())
164           return true;
165 
166         // Only consider candidates that are "more reduced" than the original
167         // value. This explicitly also rules out candidates with the same
168         // reduction power. This is to ensure that repeated invocations of this
169         // pass eventually reach a fixpoint without switch back and forth
170         // between two opportunities with the same reductive power.
171         return !IsMoreReduced(V, OpVal);
172       });
173 
174       if (Candidates.empty())
175         continue;
176 
177       // collectReferencedValues pushed the more reductive values to the end of
178       // the collection, but we need them at the front.
179       std::reverse(Candidates.begin(), Candidates.end());
180 
181       // Independency of collectReferencedValues's idea of reductive power,
182       // ensure the the partial order of IsMoreReduced is enforced.
183       llvm::stable_sort(Candidates, IsMoreReduced);
184 
185       Callback(Op, Candidates);
186     }
187   }
188 }
189 
extractOperandsFromModule(Oracle & O,ReducerWorkItem & WorkItem)190 static void extractOperandsFromModule(Oracle &O, ReducerWorkItem &WorkItem) {
191   Module &Program = WorkItem.getModule();
192 
193   for (Function &F : Program.functions()) {
194     SmallVector<std::pair<Use *, Value *>> Replacements;
195     opportunities(F, [&](Use &Op, ArrayRef<Value *> Candidates) {
196       // Only apply the candidate the Oracle selected to keep that is the most
197       // reduced. Candidates with less reductive power can be interpreted as an
198       // intermediate step that is immediately replaced with the more reduced
199       // one. The number of shouldKeep() calls must be independent of the result
200       // of previous shouldKeep() calls to keep the total number of calls
201       // in-sync with what countOperands() has computed.
202       bool AlreadyReplaced = false;
203       for (Value *C : Candidates) {
204         bool Keep = O.shouldKeep();
205         if (AlreadyReplaced || Keep)
206           continue;
207 
208         // Replacing the operand value immediately would influence the candidate
209         // set for the following operands. Delay it until after all candidates
210         // have been determined.
211         Replacements.push_back({&Op, C});
212 
213         AlreadyReplaced = true;
214       }
215     });
216 
217     for (std::pair<Use *, Value *> P : Replacements) {
218       if (PHINode *Phi = dyn_cast<PHINode>(P.first->getUser()))
219         Phi->setIncomingValueForBlock(Phi->getIncomingBlock(*P.first), P.second);
220       else
221         P.first->set(P.second);
222     }
223   }
224 }
225 
reduceOperandsSkipDeltaPass(TestRunner & Test)226 void llvm::reduceOperandsSkipDeltaPass(TestRunner &Test) {
227   runDeltaPass(Test, extractOperandsFromModule,
228                "Reducing operands by skipping over instructions");
229 }
230