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 "ReduceOperands.h"
10#include "llvm/IR/Constants.h"
11#include "llvm/IR/InstIterator.h"
12#include "llvm/IR/InstrTypes.h"
13#include "llvm/IR/Operator.h"
14#include "llvm/IR/PatternMatch.h"
15#include "llvm/IR/Type.h"
16
17using namespace llvm;
18using namespace PatternMatch;
19
20static void
21extractOperandsFromModule(Oracle &O, ReducerWorkItem &WorkItem,
22 function_ref<Value *(Use &)> ReduceValue) {
23 Module &Program = WorkItem.getModule();
24
25 for (auto &F : Program.functions()) {
26 for (auto &I : instructions(F: &F)) {
27 if (PHINode *Phi = dyn_cast<PHINode>(Val: &I)) {
28 for (auto &Op : Phi->incoming_values()) {
29 if (Value *Reduced = ReduceValue(Op)) {
30 if (!O.shouldKeep())
31 Phi->setIncomingValueForBlock(BB: Phi->getIncomingBlock(U: Op), V: Reduced);
32 }
33 }
34
35 continue;
36 }
37
38 for (auto &Op : I.operands()) {
39 if (Value *Reduced = ReduceValue(Op)) {
40 if (!O.shouldKeep())
41 Op.set(Reduced);
42 }
43 }
44 }
45 }
46}
47
48static bool isOne(Use &Op) {
49 auto *C = dyn_cast<Constant>(Val&: Op);
50 return C && C->isOneValue();
51}
52
53static bool isZero(Use &Op) {
54 auto *C = dyn_cast<Constant>(Val&: Op);
55 return C && C->isNullValue();
56}
57
58static bool isZeroOrOneFP(Value *Op) {
59 const APFloat *C;
60 return match(V: Op, P: m_APFloat(Res&: C)) &&
61 ((C->isZero() && !C->isNegative()) || C->isExactlyValue(V: 1.0));
62}
63
64static bool shouldReduceOperand(Use &Op) {
65 Type *Ty = Op->getType();
66 if (Ty->isLabelTy() || Ty->isMetadataTy())
67 return false;
68 // TODO: be more precise about which GEP operands we can reduce (e.g. array
69 // indexes)
70 if (isa<GEPOperator>(Val: Op.getUser()))
71 return false;
72 if (auto *CB = dyn_cast<CallBase>(Val: Op.getUser())) {
73 if (&CB->getCalledOperandUse() == &Op)
74 return false;
75 }
76 // lifetime intrinsic argument must be an alloca.
77 if (isa<LifetimeIntrinsic>(Val: Op.getUser()))
78 return false;
79 return true;
80}
81
82static bool switchCaseExists(Use &Op, ConstantInt *CI) {
83 SwitchInst *SI = dyn_cast<SwitchInst>(Val: Op.getUser());
84 if (!SI)
85 return false;
86 return SI->findCaseValue(C: CI) != SI->case_default();
87}
88
89void llvm::reduceOperandsOneDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
90 auto ReduceValue = [](Use &Op) -> Value * {
91 if (!shouldReduceOperand(Op))
92 return nullptr;
93
94 Type *Ty = Op->getType();
95 if (auto *IntTy = dyn_cast<IntegerType>(Val: Ty)) {
96 // Don't duplicate an existing switch case.
97 if (switchCaseExists(Op, CI: ConstantInt::get(Ty: IntTy, V: 1)))
98 return nullptr;
99 // Don't replace existing ones and zeroes.
100 return (isOne(Op) || isZero(Op)) ? nullptr : ConstantInt::get(Ty: IntTy, V: 1);
101 }
102
103 if (Ty->isFloatingPointTy())
104 return isZeroOrOneFP(Op) ? nullptr : ConstantFP::get(Ty, V: 1.0);
105
106 if (VectorType *VT = dyn_cast<VectorType>(Val: Ty)) {
107 if (isOne(Op) || isZero(Op) || isZeroOrOneFP(Op))
108 return nullptr;
109
110 Type *ElementType = VT->getElementType();
111 Constant *C;
112 if (ElementType->isFloatingPointTy()) {
113 C = ConstantFP::get(Ty: ElementType, V: 1.0);
114 } else if (IntegerType *IntTy = dyn_cast<IntegerType>(Val: ElementType)) {
115 C = ConstantInt::get(Ty: IntTy, V: 1);
116 } else {
117 return nullptr;
118 }
119 return ConstantVector::getSplat(EC: VT->getElementCount(), Elt: C);
120 }
121
122 return nullptr;
123 };
124 extractOperandsFromModule(O, WorkItem, ReduceValue);
125}
126
127void llvm::reduceOperandsZeroDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
128 auto ReduceValue = [](Use &Op) -> Value * {
129 if (!shouldReduceOperand(Op))
130 return nullptr;
131
132 // Avoid introducing 0-sized allocations.
133 if (isa<AllocaInst>(Val: Op.getUser()))
134 return nullptr;
135
136 // Don't duplicate an existing switch case.
137 if (auto *IntTy = dyn_cast<IntegerType>(Val: Op->getType()))
138 if (switchCaseExists(Op, CI: ConstantInt::get(Ty: IntTy, V: 0)))
139 return nullptr;
140
141 if (auto *TET = dyn_cast<TargetExtType>(Val: Op->getType())) {
142 if (isa<ConstantTargetNone, PoisonValue>(Val: Op))
143 return nullptr;
144 if (TET->hasProperty(Prop: TargetExtType::HasZeroInit))
145 return ConstantTargetNone::get(T: TET);
146 return nullptr;
147 }
148
149 // Don't replace existing zeroes.
150 return isZero(Op) ? nullptr : Constant::getNullValue(Ty: Op->getType());
151 };
152 extractOperandsFromModule(O, WorkItem, ReduceValue);
153}
154
155void llvm::reduceOperandsNaNDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
156 auto ReduceValue = [](Use &Op) -> Value * {
157 Type *Ty = Op->getType();
158 if (!Ty->isFPOrFPVectorTy())
159 return nullptr;
160
161 // Prefer 0.0 or 1.0 over NaN.
162 //
163 // TODO: Preferring NaN may make more sense because FP operations are more
164 // universally foldable.
165 if (match(V: Op.get(), P: m_NaN()) || isZeroOrOneFP(Op: Op.get()))
166 return nullptr;
167
168 if (VectorType *VT = dyn_cast<VectorType>(Val: Ty)) {
169 return ConstantVector::getSplat(EC: VT->getElementCount(),
170 Elt: ConstantFP::getQNaN(Ty: VT->getElementType()));
171 }
172
173 return ConstantFP::getQNaN(Ty);
174 };
175 extractOperandsFromModule(O, WorkItem, ReduceValue);
176}
177
178void llvm::reduceOperandsPoisonDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
179 auto ReduceValue = [](Use &Op) -> Value * {
180 Type *Ty = Op->getType();
181 if (auto *TET = dyn_cast<TargetExtType>(Val: Ty)) {
182 if (isa<ConstantTargetNone, PoisonValue>(Val: Op))
183 return nullptr;
184 return PoisonValue::get(T: TET);
185 }
186
187 return nullptr;
188 };
189
190 extractOperandsFromModule(O, WorkItem, ReduceValue);
191}
192