1 //===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the PHITransAddr class.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Analysis/PHITransAddr.h"
15 #include "llvm/Analysis/InstructionSimplify.h"
16 #include "llvm/Analysis/ValueTracking.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/raw_ostream.h"
23 using namespace llvm;
24
CanPHITrans(Instruction * Inst)25 static bool CanPHITrans(Instruction *Inst) {
26 if (isa<PHINode>(Inst) ||
27 isa<GetElementPtrInst>(Inst))
28 return true;
29
30 if (isa<CastInst>(Inst) &&
31 isSafeToSpeculativelyExecute(Inst))
32 return true;
33
34 if (Inst->getOpcode() == Instruction::Add &&
35 isa<ConstantInt>(Inst->getOperand(1)))
36 return true;
37
38 // cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
39 // if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
40 // cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
41 return false;
42 }
43
44 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const45 void PHITransAddr::dump() const {
46 if (!Addr) {
47 dbgs() << "PHITransAddr: null\n";
48 return;
49 }
50 dbgs() << "PHITransAddr: " << *Addr << "\n";
51 for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
52 dbgs() << " Input #" << i << " is " << *InstInputs[i] << "\n";
53 }
54 #endif
55
56
VerifySubExpr(Value * Expr,SmallVectorImpl<Instruction * > & InstInputs)57 static bool VerifySubExpr(Value *Expr,
58 SmallVectorImpl<Instruction*> &InstInputs) {
59 // If this is a non-instruction value, there is nothing to do.
60 Instruction *I = dyn_cast<Instruction>(Expr);
61 if (!I) return true;
62
63 // If it's an instruction, it is either in Tmp or its operands recursively
64 // are.
65 SmallVectorImpl<Instruction*>::iterator Entry =
66 std::find(InstInputs.begin(), InstInputs.end(), I);
67 if (Entry != InstInputs.end()) {
68 InstInputs.erase(Entry);
69 return true;
70 }
71
72 // If it isn't in the InstInputs list it is a subexpr incorporated into the
73 // address. Sanity check that it is phi translatable.
74 if (!CanPHITrans(I)) {
75 errs() << "Instruction in PHITransAddr is not phi-translatable:\n";
76 errs() << *I << '\n';
77 llvm_unreachable("Either something is missing from InstInputs or "
78 "CanPHITrans is wrong.");
79 }
80
81 // Validate the operands of the instruction.
82 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
83 if (!VerifySubExpr(I->getOperand(i), InstInputs))
84 return false;
85
86 return true;
87 }
88
89 /// Verify - Check internal consistency of this data structure. If the
90 /// structure is valid, it returns true. If invalid, it prints errors and
91 /// returns false.
Verify() const92 bool PHITransAddr::Verify() const {
93 if (!Addr) return true;
94
95 SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end());
96
97 if (!VerifySubExpr(Addr, Tmp))
98 return false;
99
100 if (!Tmp.empty()) {
101 errs() << "PHITransAddr contains extra instructions:\n";
102 for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
103 errs() << " InstInput #" << i << " is " << *InstInputs[i] << "\n";
104 llvm_unreachable("This is unexpected.");
105 }
106
107 // a-ok.
108 return true;
109 }
110
111
112 /// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
113 /// if we have some hope of doing it. This should be used as a filter to
114 /// avoid calling PHITranslateValue in hopeless situations.
IsPotentiallyPHITranslatable() const115 bool PHITransAddr::IsPotentiallyPHITranslatable() const {
116 // If the input value is not an instruction, or if it is not defined in CurBB,
117 // then we don't need to phi translate it.
118 Instruction *Inst = dyn_cast<Instruction>(Addr);
119 return !Inst || CanPHITrans(Inst);
120 }
121
122
RemoveInstInputs(Value * V,SmallVectorImpl<Instruction * > & InstInputs)123 static void RemoveInstInputs(Value *V,
124 SmallVectorImpl<Instruction*> &InstInputs) {
125 Instruction *I = dyn_cast<Instruction>(V);
126 if (!I) return;
127
128 // If the instruction is in the InstInputs list, remove it.
129 SmallVectorImpl<Instruction*>::iterator Entry =
130 std::find(InstInputs.begin(), InstInputs.end(), I);
131 if (Entry != InstInputs.end()) {
132 InstInputs.erase(Entry);
133 return;
134 }
135
136 assert(!isa<PHINode>(I) && "Error, removing something that isn't an input");
137
138 // Otherwise, it must have instruction inputs itself. Zap them recursively.
139 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
140 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
141 RemoveInstInputs(Op, InstInputs);
142 }
143 }
144
PHITranslateSubExpr(Value * V,BasicBlock * CurBB,BasicBlock * PredBB,const DominatorTree * DT)145 Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
146 BasicBlock *PredBB,
147 const DominatorTree *DT) {
148 // If this is a non-instruction value, it can't require PHI translation.
149 Instruction *Inst = dyn_cast<Instruction>(V);
150 if (!Inst) return V;
151
152 // Determine whether 'Inst' is an input to our PHI translatable expression.
153 bool isInput =
154 std::find(InstInputs.begin(), InstInputs.end(), Inst) != InstInputs.end();
155
156 // Handle inputs instructions if needed.
157 if (isInput) {
158 if (Inst->getParent() != CurBB) {
159 // If it is an input defined in a different block, then it remains an
160 // input.
161 return Inst;
162 }
163
164 // If 'Inst' is defined in this block and is an input that needs to be phi
165 // translated, we need to incorporate the value into the expression or fail.
166
167 // In either case, the instruction itself isn't an input any longer.
168 InstInputs.erase(std::find(InstInputs.begin(), InstInputs.end(), Inst));
169
170 // If this is a PHI, go ahead and translate it.
171 if (PHINode *PN = dyn_cast<PHINode>(Inst))
172 return AddAsInput(PN->getIncomingValueForBlock(PredBB));
173
174 // If this is a non-phi value, and it is analyzable, we can incorporate it
175 // into the expression by making all instruction operands be inputs.
176 if (!CanPHITrans(Inst))
177 return nullptr;
178
179 // All instruction operands are now inputs (and of course, they may also be
180 // defined in this block, so they may need to be phi translated themselves.
181 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
182 if (Instruction *Op = dyn_cast<Instruction>(Inst->getOperand(i)))
183 InstInputs.push_back(Op);
184 }
185
186 // Ok, it must be an intermediate result (either because it started that way
187 // or because we just incorporated it into the expression). See if its
188 // operands need to be phi translated, and if so, reconstruct it.
189
190 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
191 if (!isSafeToSpeculativelyExecute(Cast)) return nullptr;
192 Value *PHIIn = PHITranslateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
193 if (!PHIIn) return nullptr;
194 if (PHIIn == Cast->getOperand(0))
195 return Cast;
196
197 // Find an available version of this cast.
198
199 // Constants are trivial to find.
200 if (Constant *C = dyn_cast<Constant>(PHIIn))
201 return AddAsInput(ConstantExpr::getCast(Cast->getOpcode(),
202 C, Cast->getType()));
203
204 // Otherwise we have to see if a casted version of the incoming pointer
205 // is available. If so, we can use it, otherwise we have to fail.
206 for (User *U : PHIIn->users()) {
207 if (CastInst *CastI = dyn_cast<CastInst>(U))
208 if (CastI->getOpcode() == Cast->getOpcode() &&
209 CastI->getType() == Cast->getType() &&
210 (!DT || DT->dominates(CastI->getParent(), PredBB)))
211 return CastI;
212 }
213 return nullptr;
214 }
215
216 // Handle getelementptr with at least one PHI translatable operand.
217 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
218 SmallVector<Value*, 8> GEPOps;
219 bool AnyChanged = false;
220 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
221 Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB, DT);
222 if (!GEPOp) return nullptr;
223
224 AnyChanged |= GEPOp != GEP->getOperand(i);
225 GEPOps.push_back(GEPOp);
226 }
227
228 if (!AnyChanged)
229 return GEP;
230
231 // Simplify the GEP to handle 'gep x, 0' -> x etc.
232 if (Value *V = SimplifyGEPInst(GEPOps, DL, TLI, DT, AC)) {
233 for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
234 RemoveInstInputs(GEPOps[i], InstInputs);
235
236 return AddAsInput(V);
237 }
238
239 // Scan to see if we have this GEP available.
240 Value *APHIOp = GEPOps[0];
241 for (User *U : APHIOp->users()) {
242 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U))
243 if (GEPI->getType() == GEP->getType() &&
244 GEPI->getNumOperands() == GEPOps.size() &&
245 GEPI->getParent()->getParent() == CurBB->getParent() &&
246 (!DT || DT->dominates(GEPI->getParent(), PredBB))) {
247 if (std::equal(GEPOps.begin(), GEPOps.end(), GEPI->op_begin()))
248 return GEPI;
249 }
250 }
251 return nullptr;
252 }
253
254 // Handle add with a constant RHS.
255 if (Inst->getOpcode() == Instruction::Add &&
256 isa<ConstantInt>(Inst->getOperand(1))) {
257 // PHI translate the LHS.
258 Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
259 bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
260 bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
261
262 Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);
263 if (!LHS) return nullptr;
264
265 // If the PHI translated LHS is an add of a constant, fold the immediates.
266 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
267 if (BOp->getOpcode() == Instruction::Add)
268 if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
269 LHS = BOp->getOperand(0);
270 RHS = ConstantExpr::getAdd(RHS, CI);
271 isNSW = isNUW = false;
272
273 // If the old 'LHS' was an input, add the new 'LHS' as an input.
274 if (std::find(InstInputs.begin(), InstInputs.end(), BOp) !=
275 InstInputs.end()) {
276 RemoveInstInputs(BOp, InstInputs);
277 AddAsInput(LHS);
278 }
279 }
280
281 // See if the add simplifies away.
282 if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, DL, TLI, DT, AC)) {
283 // If we simplified the operands, the LHS is no longer an input, but Res
284 // is.
285 RemoveInstInputs(LHS, InstInputs);
286 return AddAsInput(Res);
287 }
288
289 // If we didn't modify the add, just return it.
290 if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))
291 return Inst;
292
293 // Otherwise, see if we have this add available somewhere.
294 for (User *U : LHS->users()) {
295 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U))
296 if (BO->getOpcode() == Instruction::Add &&
297 BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
298 BO->getParent()->getParent() == CurBB->getParent() &&
299 (!DT || DT->dominates(BO->getParent(), PredBB)))
300 return BO;
301 }
302
303 return nullptr;
304 }
305
306 // Otherwise, we failed.
307 return nullptr;
308 }
309
310
311 /// PHITranslateValue - PHI translate the current address up the CFG from
312 /// CurBB to Pred, updating our state to reflect any needed changes. If
313 /// 'MustDominate' is true, the translated value must dominate
314 /// PredBB. This returns true on failure and sets Addr to null.
PHITranslateValue(BasicBlock * CurBB,BasicBlock * PredBB,const DominatorTree * DT,bool MustDominate)315 bool PHITransAddr::PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB,
316 const DominatorTree *DT,
317 bool MustDominate) {
318 assert(DT || !MustDominate);
319 assert(Verify() && "Invalid PHITransAddr!");
320 if (DT && DT->isReachableFromEntry(PredBB))
321 Addr =
322 PHITranslateSubExpr(Addr, CurBB, PredBB, MustDominate ? DT : nullptr);
323 else
324 Addr = nullptr;
325 assert(Verify() && "Invalid PHITransAddr!");
326
327 if (MustDominate)
328 // Make sure the value is live in the predecessor.
329 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
330 if (!DT->dominates(Inst->getParent(), PredBB))
331 Addr = nullptr;
332
333 return Addr == nullptr;
334 }
335
336 /// PHITranslateWithInsertion - PHI translate this value into the specified
337 /// predecessor block, inserting a computation of the value if it is
338 /// unavailable.
339 ///
340 /// All newly created instructions are added to the NewInsts list. This
341 /// returns null on failure.
342 ///
343 Value *PHITransAddr::
PHITranslateWithInsertion(BasicBlock * CurBB,BasicBlock * PredBB,const DominatorTree & DT,SmallVectorImpl<Instruction * > & NewInsts)344 PHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
345 const DominatorTree &DT,
346 SmallVectorImpl<Instruction*> &NewInsts) {
347 unsigned NISize = NewInsts.size();
348
349 // Attempt to PHI translate with insertion.
350 Addr = InsertPHITranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
351
352 // If successful, return the new value.
353 if (Addr) return Addr;
354
355 // If not, destroy any intermediate instructions inserted.
356 while (NewInsts.size() != NISize)
357 NewInsts.pop_back_val()->eraseFromParent();
358 return nullptr;
359 }
360
361
362 /// InsertPHITranslatedPointer - Insert a computation of the PHI translated
363 /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
364 /// block. All newly created instructions are added to the NewInsts list.
365 /// This returns null on failure.
366 ///
367 Value *PHITransAddr::
InsertPHITranslatedSubExpr(Value * InVal,BasicBlock * CurBB,BasicBlock * PredBB,const DominatorTree & DT,SmallVectorImpl<Instruction * > & NewInsts)368 InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB,
369 BasicBlock *PredBB, const DominatorTree &DT,
370 SmallVectorImpl<Instruction*> &NewInsts) {
371 // See if we have a version of this value already available and dominating
372 // PredBB. If so, there is no need to insert a new instance of it.
373 PHITransAddr Tmp(InVal, DL, AC);
374 if (!Tmp.PHITranslateValue(CurBB, PredBB, &DT, /*MustDominate=*/true))
375 return Tmp.getAddr();
376
377 // We don't need to PHI translate values which aren't instructions.
378 auto *Inst = dyn_cast<Instruction>(InVal);
379 if (!Inst)
380 return nullptr;
381
382 // Handle cast of PHI translatable value.
383 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
384 if (!isSafeToSpeculativelyExecute(Cast)) return nullptr;
385 Value *OpVal = InsertPHITranslatedSubExpr(Cast->getOperand(0),
386 CurBB, PredBB, DT, NewInsts);
387 if (!OpVal) return nullptr;
388
389 // Otherwise insert a cast at the end of PredBB.
390 CastInst *New = CastInst::Create(Cast->getOpcode(), OpVal, InVal->getType(),
391 InVal->getName() + ".phi.trans.insert",
392 PredBB->getTerminator());
393 New->setDebugLoc(Inst->getDebugLoc());
394 NewInsts.push_back(New);
395 return New;
396 }
397
398 // Handle getelementptr with at least one PHI operand.
399 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
400 SmallVector<Value*, 8> GEPOps;
401 BasicBlock *CurBB = GEP->getParent();
402 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
403 Value *OpVal = InsertPHITranslatedSubExpr(GEP->getOperand(i),
404 CurBB, PredBB, DT, NewInsts);
405 if (!OpVal) return nullptr;
406 GEPOps.push_back(OpVal);
407 }
408
409 GetElementPtrInst *Result = GetElementPtrInst::Create(
410 GEP->getSourceElementType(), GEPOps[0], makeArrayRef(GEPOps).slice(1),
411 InVal->getName() + ".phi.trans.insert", PredBB->getTerminator());
412 Result->setDebugLoc(Inst->getDebugLoc());
413 Result->setIsInBounds(GEP->isInBounds());
414 NewInsts.push_back(Result);
415 return Result;
416 }
417
418 #if 0
419 // FIXME: This code works, but it is unclear that we actually want to insert
420 // a big chain of computation in order to make a value available in a block.
421 // This needs to be evaluated carefully to consider its cost trade offs.
422
423 // Handle add with a constant RHS.
424 if (Inst->getOpcode() == Instruction::Add &&
425 isa<ConstantInt>(Inst->getOperand(1))) {
426 // PHI translate the LHS.
427 Value *OpVal = InsertPHITranslatedSubExpr(Inst->getOperand(0),
428 CurBB, PredBB, DT, NewInsts);
429 if (OpVal == 0) return 0;
430
431 BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1),
432 InVal->getName()+".phi.trans.insert",
433 PredBB->getTerminator());
434 Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
435 Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
436 NewInsts.push_back(Res);
437 return Res;
438 }
439 #endif
440
441 return nullptr;
442 }
443