Coverage Report

Created: 2019-07-24 05:18

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