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". 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->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". 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 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 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 226 void llvm::reduceOperandsSkipDeltaPass(TestRunner &Test) { 227 runDeltaPass(Test, extractOperandsFromModule, 228 "Reducing operands by skipping over instructions"); 229 } 230