@@ -220,44 +220,75 @@ static void TransferBlock(const BasicBlock *BB,
220
220
dbgs () << " \n " ;);
221
221
}
222
222
223
- // / Return true if V is exclusively derived off a constant base, i.e. all
224
- // / operands of non-unary operators (phi/select) are derived off a constant
225
- // / base.
226
- static bool
227
- isExclusivelyConstantDerivedRecursive (const Value *V,
228
- DenseSet<const Value *> &Visited) {
229
- if (!Visited.insert (V).second )
230
- return true ;
231
-
232
- if (isa<Constant>(V))
233
- return true ;
234
-
235
- if (const auto *CI = dyn_cast<CastInst>(V))
236
- return isExclusivelyConstantDerivedRecursive (CI->stripPointerCasts (),
237
- Visited);
223
+ // / A given derived pointer can have multiple base pointers through phi/selects.
224
+ // / This type indicates when the base pointer is exclusively constant
225
+ // / (ExclusivelySomeConstant), and if that constant is proven to be exclusively
226
+ // / null, we record that as ExclusivelyNull. In all other cases, the BaseType is
227
+ // / NonConstant.
228
+ enum BaseType {
229
+ NonConstant = 1 , // Base pointers is not exclusively constant.
230
+ ExclusivelyNull,
231
+ ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
232
+ // set of constants, but they are not exclusively
233
+ // null.
234
+ };
238
235
239
- if (const auto *GEP = dyn_cast<GetElementPtrInst>(V))
240
- return isExclusivelyConstantDerivedRecursive (GEP->getPointerOperand (),
241
- Visited);
236
+ // / Return the baseType for Val which states whether Val is exclusively
237
+ // / derived from constant/null, or not exclusively derived from constant.
238
+ // / Val is exclusively derived off a constant base when all operands of phi and
239
+ // / selects are derived off a constant base.
240
+ static enum BaseType getBaseType (const Value *Val) {
241
+
242
+ SmallVector<const Value *, 32 > Worklist;
243
+ DenseSet<const Value *> Visited;
244
+ bool isExclusivelyDerivedFromNull = true ;
245
+ Worklist.push_back (Val);
246
+ // Strip through all the bitcasts and geps to get base pointer. Also check for
247
+ // the exclusive value when there can be multiple base pointers (through phis
248
+ // or selects).
249
+ while (!Worklist.empty ()) {
250
+ const Value *V = Worklist.pop_back_val ();
251
+ if (!Visited.insert (V).second )
252
+ continue ;
242
253
243
- // All operands of the phi and select nodes should be derived off a constant
244
- // base.
245
- if (const auto *PN = dyn_cast<PHINode>(V)) {
246
- return all_of (PN->incoming_values (), [&](const Value *InV) {
247
- return isExclusivelyConstantDerivedRecursive (InV, Visited);
248
- });
254
+ if (const auto *CI = dyn_cast<CastInst>(V)) {
255
+ Worklist.push_back (CI->stripPointerCasts ());
256
+ continue ;
257
+ }
258
+ if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
259
+ Worklist.push_back (GEP->getPointerOperand ());
260
+ continue ;
261
+ }
262
+ // Push all the incoming values of phi node into the worklist for
263
+ // processing.
264
+ if (const auto *PN = dyn_cast<PHINode>(V)) {
265
+ for (Value *InV: PN->incoming_values ())
266
+ Worklist.push_back (InV);
267
+ continue ;
268
+ }
269
+ if (const auto *SI = dyn_cast<SelectInst>(V)) {
270
+ // Push in the true and false values
271
+ Worklist.push_back (SI->getTrueValue ());
272
+ Worklist.push_back (SI->getFalseValue ());
273
+ continue ;
274
+ }
275
+ if (isa<Constant>(V)) {
276
+ // We found at least one base pointer which is non-null, so this derived
277
+ // pointer is not exclusively derived from null.
278
+ if (V != Constant::getNullValue (V->getType ()))
279
+ isExclusivelyDerivedFromNull = false ;
280
+ // Continue processing the remaining values to make sure it's exclusively
281
+ // constant.
282
+ continue ;
283
+ }
284
+ // At this point, we know that the base pointer is not exclusively
285
+ // constant.
286
+ return BaseType::NonConstant;
249
287
}
250
-
251
- if (const auto *SI = dyn_cast<SelectInst>(V))
252
- return isExclusivelyConstantDerivedRecursive (SI->getTrueValue (), Visited) &&
253
- isExclusivelyConstantDerivedRecursive (SI->getFalseValue (), Visited);
254
-
255
- return false ;
256
- }
257
-
258
- static bool isExclusivelyConstantDerived (const Value *V) {
259
- DenseSet<const Value*> Visited;
260
- return isExclusivelyConstantDerivedRecursive (V, Visited);
288
+ // Now, we know that the base pointer is exclusively constant, but we need to
289
+ // differentiate between exclusive null constant and non-null constant.
290
+ return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
291
+ : BaseType::ExclusivelySomeConstant;
261
292
}
262
293
263
294
static void Verify (const Function &F, const DominatorTree &DT) {
@@ -323,6 +354,10 @@ static void Verify(const Function &F, const DominatorTree &DT) {
323
354
AnyInvalidUses = true ;
324
355
};
325
356
357
+ auto isNotExclusivelyConstantDerived = [](const Value *V) {
358
+ return getBaseType (V) == BaseType::NonConstant;
359
+ };
360
+
326
361
for (const BasicBlock &BB : F) {
327
362
// We destructively modify AvailableIn as we traverse the block instruction
328
363
// by instruction.
@@ -334,14 +369,14 @@ static void Verify(const Function &F, const DominatorTree &DT) {
334
369
const BasicBlock *InBB = PN->getIncomingBlock (i);
335
370
const Value *InValue = PN->getIncomingValue (i);
336
371
337
- if (! isExclusivelyConstantDerived (InValue) &&
372
+ if (isNotExclusivelyConstantDerived (InValue) &&
338
373
!BlockMap[InBB]->AvailableOut .count (InValue))
339
374
ReportInvalidUse (*InValue, *PN);
340
375
}
341
376
} else {
342
377
for (const Value *V : I.operands ())
343
378
if (containsGCPtrType (V->getType ()) &&
344
- ! isExclusivelyConstantDerived (V) && !AvailableSet.count (V))
379
+ isNotExclusivelyConstantDerived (V) && !AvailableSet.count (V))
345
380
ReportInvalidUse (*V, I);
346
381
}
347
382
0 commit comments