[CFLAA] Add support for field offset in CFLGraph

[grievejia]

Summary

This patch introduces no functional changes.

We used to treat GEPs like bitcasts and ignore the offsets. Such an approach is inadequate if we were to move to a field-sensitive analysis. We use accumulateConstantOffset() in this patch to keep track of field offsets in CFLGraphBuilder when the given gep can be decomposed into a base and a constant offset.

To call accumulateConstantOffset() we need to perform a cast to GEPOperator in visitGetElementPtrInst(). This cast will fail when visitGetElementPtrInst() gets a ConstantExpr disguised as a GetElementPtrInst as its argument. I'm not 100% sure what the reason for the casting failure is, but a deeper problem here is that we handle ConstantExprs by casting them into their corresponding Instructions, and such a treatment is very hacky and fragile. I ended up fixing the problem by rewriting visitConstExpr() and letting it do its job in a proper manner.

More patches on field-sensitivity will come in the near future.

[george.burgess.iv]

Thanks for the patch!

lib/Analysis/CFLGraph.h

30

IIRC, some MSVC versions we support don't have a constexpr max() function, so this will break those bots. Please either use a static LLVM_CONSTEXPR variable, or wrap this in a function. :)

312

Please use cast<GEPOperator> instead of dyn_cast + assert.

498

Same "please use cast" comment

[grievejia]

Style fixes.

[george.burgess.iv]

LGTM; thanks again.

lib/Analysis/CFLGraph.h

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 
 namespace llvm {
 namespace cflaa {
 
+// We use UnknownOffset to represent pointer offsets that cannot be determined
+// at compile time. Note that MemoryLocation::UnknownSize cannot be used here
+// because we require a signed value.
+static LLVM_CONSTEXPR int64_t UnknownOffset =
+    std::numeric_limits<int64_t>::max();
+
+inline int64_t addOffset(int64_t LHS, int64_t RHS) {
+  if (LHS == UnknownOffset || RHS == UnknownOffset)
+    return UnknownOffset;
+  // FIXME: Do we need to guard against integer overflow here?
+  return LHS + RHS;
+}
+
 /// \brief The Program Expression Graph (PEG) of CFL analysis
 /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to
 /// describe flow-insensitive pointer-related behaviors. Given an LLVM function,
 /// the main purpose of this graph is to abstract away unrelated facts and
 /// translate the rest into a form that can be easily digested by CFL analyses.
 /// Each Node in the graph is an InstantiatedValue, and each edge represent a
 /// pointer assignment between InstantiatedValue. Pointer
 /// references/dereferences are not explicitly stored in the graph: we
 /// implicitly assume that for each node (X, I) it has a dereference edge to (X,
 /// I+1) and a reference edge to (X, I-1).
 class CFLGraph {
 public:
   typedef InstantiatedValue Node;
 
   struct Edge {
     Node Other;
+    int64_t Offset;
   };
 
   typedef std::vector<Edge> EdgeList;
 
   struct NodeInfo {
     EdgeList Edges, ReverseEdges;
     AliasAttrs Attr;
   };
public:
   }
 
   void addEdge(Node From, Node To, int64_t Offset = 0) {
     auto *FromInfo = getNode(From);
     assert(FromInfo != nullptr);
     auto *ToInfo = getNode(To);
     assert(ToInfo != nullptr);
 
-    FromInfo->Edges.push_back(Edge{To});
-    ToInfo->ReverseEdges.push_back(Edge{From});
+    FromInfo->Edges.push_back(Edge{To, Offset});
+    ToInfo->ReverseEdges.push_back(Edge{From, Offset});
   }
 
   const NodeInfo *getNode(Node N) const {
     auto Itr = ValueImpls.find(N.Val);
     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
       return nullptr;
     return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
   }
template <typename CFLAA> class CFLGraphBuilder {
   // Output of the builder
   CFLGraph Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
   // Helper class
   /// Gets the edges our graph should have, based on an Instruction*
   class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
     CFLAA &AA;
+    const DataLayout &DL;
     const TargetLibraryInfo &TLI;
 
     CFLGraph &Graph;
     SmallVectorImpl<Value *> &ReturnValues;
 
     static bool hasUsefulEdges(ConstantExpr *CE) {
       // ConstantExpr doesn't have terminators, invokes, or fences, so only
       // needs
void addDerefEdge(Value *From, Value *To, bool IsRead) {
         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
       }
     }
 
     void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
     void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
 
   public:
-    GetEdgesVisitor(CFLGraphBuilder &Builder)
-        : AA(Builder.Analysis), TLI(Builder.TLI), Graph(Builder.Graph),
+    GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
+        : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
           ReturnValues(Builder.ReturnedValues) {}
 
     void visitInstruction(Instruction &) {
       llvm_unreachable("Unsupported instruction encountered");
     }
 
     void visitReturnInst(ReturnInst &Inst) {
       if (auto RetVal = Inst.getReturnValue()) {
void visitAtomicRMWInst(AtomicRMWInst &Inst) {
       addStoreEdge(Val, Ptr);
     }
 
     void visitPHINode(PHINode &Inst) {
       for (Value *Val : Inst.incoming_values())
         addAssignEdge(Val, &Inst);
     }
 
+    void visitGEP(GEPOperator &GEPOp) {
+      uint64_t Offset = UnknownOffset;
+      APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
+                     0);
+      if (GEPOp.accumulateConstantOffset(DL, APOffset))
+        Offset = APOffset.getSExtValue();
+
+      auto *Op = GEPOp.getPointerOperand();
+      addAssignEdge(Op, &GEPOp, Offset);
+    }
+
     void visitGetElementPtrInst(GetElementPtrInst &Inst) {
-      auto *Op = Inst.getPointerOperand();
-      addAssignEdge(Op, &Inst);
+      auto *GEPOp = cast<GEPOperator>(&Inst);
+      visitGEP(*GEPOp);
     }
 
     void visitSelectInst(SelectInst &Inst) {
       // Condition is not processed here (The actual statement producing
       // the condition result is processed elsewhere). For select, the
       // condition is evaluated, but not loaded, stored, or assigned
       // simply as a result of being the condition of a select.
 
void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
       auto *From1 = Inst.getOperand(0);
       auto *From2 = Inst.getOperand(1);
       addAssignEdge(From1, &Inst);
       addAssignEdge(From2, &Inst);
     }
 
     void visitConstantExpr(ConstantExpr *CE) {
       switch (CE->getOpcode()) {
+      case Instruction::GetElementPtr: {
+        auto GEPOp = cast<GEPOperator>(CE);
+        visitGEP(*GEPOp);
+        break;
+      }
+      case Instruction::PtrToInt: {
+        auto *Ptr = CE->getOperand(0);
+        addNode(Ptr, getAttrEscaped());
+        break;
+      }
+      case Instruction::IntToPtr: {
+        addNode(CE, getAttrUnknown());
+        break;
+      }
+      case Instruction::BitCast:
+      case Instruction::AddrSpaceCast:
+      case Instruction::Trunc:
+      case Instruction::ZExt:
+      case Instruction::SExt:
+      case Instruction::FPExt:
+      case Instruction::FPTrunc:
+      case Instruction::UIToFP:
+      case Instruction::SIToFP:
+      case Instruction::FPToUI:
+      case Instruction::FPToSI: {
+        auto *Src = CE->getOperand(0);
+        addAssignEdge(Src, CE);
+        break;
+      }
+      case Instruction::Select: {
+        auto *TrueVal = CE->getOperand(0);
+        auto *FalseVal = CE->getOperand(1);
+        addAssignEdge(TrueVal, CE);
+        addAssignEdge(FalseVal, CE);
+        break;
+      }
+      case Instruction::InsertElement: {
+        auto *Vec = CE->getOperand(0);
+        auto *Val = CE->getOperand(1);
+        addAssignEdge(Vec, CE);
+        addStoreEdge(Val, CE);
+        break;
+      }
+      case Instruction::ExtractElement: {
+        auto *Ptr = CE->getOperand(0);
+        addLoadEdge(Ptr, CE);
+        break;
+      }
+      case Instruction::InsertValue: {
+        auto *Agg = CE->getOperand(0);
+        auto *Val = CE->getOperand(1);
+        addAssignEdge(Agg, CE);
+        addStoreEdge(Val, CE);
+        break;
+      }
+      case Instruction::ExtractValue: {
+        auto *Ptr = CE->getOperand(0);
+        addLoadEdge(Ptr, CE);
+      }
+      case Instruction::ShuffleVector: {
+        auto *From1 = CE->getOperand(0);
+        auto *From2 = CE->getOperand(1);
+        addAssignEdge(From1, CE);
+        addAssignEdge(From2, CE);
+        break;
+      }
+      case Instruction::Add:
+      case Instruction::Sub:
+      case Instruction::FSub:
+      case Instruction::Mul:
+      case Instruction::FMul:
+      case Instruction::UDiv:
+      case Instruction::SDiv:
+      case Instruction::FDiv:
+      case Instruction::URem:
+      case Instruction::SRem:
+      case Instruction::FRem:
+      case Instruction::And:
+      case Instruction::Or:
+      case Instruction::Xor:
+      case Instruction::Shl:
+      case Instruction::LShr:
+      case Instruction::AShr:
+      case Instruction::ICmp:
+      case Instruction::FCmp: {
+        addAssignEdge(CE->getOperand(0), CE);
+        addAssignEdge(CE->getOperand(1), CE);
+        break;
+      }
       default:
         llvm_unreachable("Unknown instruction type encountered!");
-// Build the switch statement using the Instruction.def file.
-#define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
-  case Instruction::OPCODE:                                                    \
-    this->visit##OPCODE(*(CLASS *)CE);                                         \
-    break;
-#include "llvm/IR/Instruction.def"
       }
     }
   };
 
   // Helper functions
 
   // Determines whether or not we an instruction is useless to us (e.g.
   // FenceInst)
if (!hasUsefulEdges(&Inst))
       return;
 
     Visitor.visit(Inst);
   }
 
   // Builds the graph needed for constructing the StratifiedSets for the given
   // function
   void buildGraphFrom(Function &Fn) {
-    GetEdgesVisitor Visitor(*this);
+    GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
 
     for (auto &Bb : Fn.getBasicBlockList())
       for (auto &Inst : Bb.getInstList())
         addInstructionToGraph(Visitor, Inst);
 
     for (auto &Arg : Fn.args())
       addArgumentToGraph(Arg);
   }