[CFLAA] Make CFLAnders more conservative when it sees newly created values

[grievejia]

Summary

There was a patch https://reviews.llvm.org/D22981 that deals with how CFLAnders interacts with values it hasn't seen before. In that patch the workaround is to let getAttrs() return AttrUnknown when newly created values are queried on.

However, the aforementioned workaround fails to work for queries of the form mayAlias(L, N), where L is marked AttrNone and N is created after CFLAnders has executed. The sound was to handle the situation is to let the may-alias query return true (since N may be of the form "bitcast L to ...", "gep L, ...", etc.), but our current implementation will always return false because AttrNone values never may-alias AttrUnknown values.

This patch separate the new-value checks and attribute checks, so that soundness issues mentioned in the previous paragraph will not happen.

[george.burgess.iv]

LGTM, thanks for the patch!

lib/Analysis/CFLAndersAliasAnalysis.cpp

class CFLAndersAAResult::FunctionInfo {
   DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
 
   /// Map a value to its corresponding AliasAttrs
   DenseMap<const Value *, AliasAttrs> AttrMap;
 
   /// Summary of externally visible effects.
   AliasSummary Summary;
 
-  AliasAttrs getAttrs(const Value *) const;
+  Optional<AliasAttrs> getAttrs(const Value *) const;
 
 public:
   FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
                const ReachabilitySet &, AliasAttrMap);
 
   bool mayAlias(const Value *, uint64_t, const Value *, uint64_t) const;
   const AliasSummary &getAliasSummary() const { return Summary; }
 };
CFLAndersAAResult::FunctionInfo::FunctionInfo(
     const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
     const ReachabilitySet &ReachSet, AliasAttrMap AMap) {
   populateAttrMap(AttrMap, AMap);
   populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
   populateAliasMap(AliasMap, ReachSet);
   populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
 }
 
-AliasAttrs CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
+Optional<AliasAttrs>
+CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
   assert(V != nullptr);
 
-  // Return AttrUnknown if V is not found in AttrMap. Sometimes V can be created
-  // after the analysis gets executed, and we want to be conservative in
-  // those cases.
-  AliasAttrs Attr = getAttrUnknown();
   auto Itr = AttrMap.find(V);
   if (Itr != AttrMap.end())
-    Attr = Itr->second;
-  return Attr;
+    return Itr->second;
+  return None;
 }
 
 bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS,
                                                uint64_t LHSSize,
                                                const Value *RHS,
                                                uint64_t RHSSize) const {
   assert(LHS && RHS);
 
-  // Check AliasAttrs first since it's cheaper
-  auto AttrsA = getAttrs(LHS);
-  auto AttrsB = getAttrs(RHS);
+  // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
+  // after the analysis gets executed, and we want to be conservative in those
+  // cases.
+  auto MaybeAttrsA = getAttrs(LHS);
+  auto MaybeAttrsB = getAttrs(RHS);
+  if (!MaybeAttrsA || !MaybeAttrsB)
+    return true;
+
+  // Check AliasAttrs before AliasMap lookup since it's cheaper
+  auto AttrsA = *MaybeAttrsA;
+  auto AttrsB = *MaybeAttrsB;
   if (hasUnknownOrCallerAttr(AttrsA))
     return AttrsB.any();
   if (hasUnknownOrCallerAttr(AttrsB))
     return AttrsA.any();
   if (isGlobalOrArgAttr(AttrsA))
     return isGlobalOrArgAttr(AttrsB);
   if (isGlobalOrArgAttr(AttrsB))
     return isGlobalOrArgAttr(AttrsA);