Skip to content

Commit ccce853

Browse files
committedJul 7, 2017
[SafepointIRVerifier] NFC: Refactor code for identifying exclusive base type
Added a new Enum to identify if the base pointer is exclusively null or exlusively some constant or not exclusively any constant. Converted the base pointer identification method from recursive to iterative form. llvm-svn: 307340
1 parent 22a402f commit ccce853

File tree

1 file changed

+72
-37
lines changed

1 file changed

+72
-37
lines changed
 

‎llvm/lib/IR/SafepointIRVerifier.cpp

+72-37
Original file line numberDiff line numberDiff line change
@@ -220,44 +220,75 @@ static void TransferBlock(const BasicBlock *BB,
220220
dbgs() << "\n";);
221221
}
222222

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+
};
238235

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;
242253

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;
249287
}
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;
261292
}
262293

263294
static void Verify(const Function &F, const DominatorTree &DT) {
@@ -323,6 +354,10 @@ static void Verify(const Function &F, const DominatorTree &DT) {
323354
AnyInvalidUses = true;
324355
};
325356

357+
auto isNotExclusivelyConstantDerived = [](const Value *V) {
358+
return getBaseType(V) == BaseType::NonConstant;
359+
};
360+
326361
for (const BasicBlock &BB : F) {
327362
// We destructively modify AvailableIn as we traverse the block instruction
328363
// by instruction.
@@ -334,14 +369,14 @@ static void Verify(const Function &F, const DominatorTree &DT) {
334369
const BasicBlock *InBB = PN->getIncomingBlock(i);
335370
const Value *InValue = PN->getIncomingValue(i);
336371

337-
if (!isExclusivelyConstantDerived(InValue) &&
372+
if (isNotExclusivelyConstantDerived(InValue) &&
338373
!BlockMap[InBB]->AvailableOut.count(InValue))
339374
ReportInvalidUse(*InValue, *PN);
340375
}
341376
} else {
342377
for (const Value *V : I.operands())
343378
if (containsGCPtrType(V->getType()) &&
344-
!isExclusivelyConstantDerived(V) && !AvailableSet.count(V))
379+
isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
345380
ReportInvalidUse(*V, I);
346381
}
347382

0 commit comments

Comments
 (0)
Please sign in to comment.