Simple type hierachy analysis produce wrong results

[yiyuaner]

• I have searched open and closed issues for duplicates
• I made sure that I am not using an old project version (DO: pull Phasar, update git submodules, rebuild the project and check if the bug is still there)

---

Bug description

Given the input file type_graph_1.cpp:

#include <iostream>
struct A {
public:
  A(int a) : a(a) {}
  int a;  
};

struct B : public A {
public:
  B(int a, int b, int c) : A(a), b(b), c(c) {}
  int b;  
  int c;
};

int main() {
  A *a1 = new A(1);
  A *a2 = new A(2);
  B *b1 = new B(1, 2, 3);

  std::cout << a1->a << a2->a << b1->b << b1->c; 

  delete a1;
  delete a2;
  delete b1; 
}

phasar-cli does not discover that struct B is a subclass of struct A.

Steps to reproduce

Use the following commands:

• /bin/clang++-12 -O0 -S -emit-llvm type_graph_1.cpp -o type_graph_1.ll
• ~/work/phasar/build/bin/phasar-cli -m ./type_graph_1.ll --emit-th-as-json

The outputs shows that struct.A and struct.B are from the same type level:

    "psr.th": {
        "class.std::basic_ios": null,
        "class.std::basic_ostream": null,
        "class.std::basic_streambuf": null,
        "class.std::ctype": null,
        "class.std::ios_base": null,
        "class.std::ios_base::Init": null,
        "class.std::locale": null,
        "class.std::locale::_Impl": null,
        "class.std::locale::facet": null,
        "class.std::locale::facet.base": null,
        "class.std::num_get": null,
        "class.std::num_put": null,
        "struct.A": null,
        "struct.B": null,
        "struct.__locale_data": null,
        "struct.__locale_struct": null,
        "struct.std::ios_base::_Callback_list": null,
        "struct.std::ios_base::_Words": null
    }
}

Context (Environment)

I have built phasar with the latest commit [49f3310]. I have made some modifications for it to be built with LLVM 12, which I think is irrelevant to the issue:

diff --git a/CMakeLists.txt b/CMakeLists.txt
index cec3c624..e1698e41 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -230,7 +230,8 @@ include_directories(SYSTEM ${SQLITE3_INCLUDE_DIR})
 # LLVM
 if (NOT PHASAR_IN_TREE)
   # Only search for LLVM if we build out of tree
-  find_package(LLVM 14 REQUIRED CONFIG)
+  #find_package(LLVM 14 REQUIRED CONFIG)
+  find_package(LLVM 12 REQUIRED CONFIG)
   include_directories(SYSTEM ${LLVM_INCLUDE_DIRS})
   link_directories(${LLVM_LIB_PATH} ${LLVM_LIBRARY_DIRS})
 endif()
diff --git a/include/phasar/DataFlow/IfdsIde/EdgeFunctionUtils.h b/include/phasar/DataFlow/IfdsIde/EdgeFunctionUtils.h
index 018a7849..6a31e515 100644
--- a/include/phasar/DataFlow/IfdsIde/EdgeFunctionUtils.h
+++ b/include/phasar/DataFlow/IfdsIde/EdgeFunctionUtils.h
@@ -337,7 +337,8 @@ template <typename L, uint8_t N> struct JoinEdgeFunction {
       return false;
     }
 
-    return llvm::equal(LHS.OtherEF, RHS.OtherEF);
+    return std::equal(llvm::adl_detail::adl_begin(LHS.OtherEF), llvm::adl_detail::adl_end(LHS.OtherEF), 
+                     llvm::adl_detail::adl_begin(RHS.OtherEF), llvm::adl_detail::adl_end(RHS.OtherEF));
   }
 
   [[nodiscard]] static EdgeFunction<l_t> create(EdgeFunction<l_t> LHS,
diff --git a/lib/PhasarLLVM/ControlFlow/Resolver/Resolver.cpp b/lib/PhasarLLVM/ControlFlow/Resolver/Resolver.cpp
index 54dc3e0d..17a10f57 100644
--- a/lib/PhasarLLVM/ControlFlow/Resolver/Resolver.cpp
+++ b/lib/PhasarLLVM/ControlFlow/Resolver/Resolver.cpp
@@ -70,7 +70,8 @@ const llvm::StructType *psr::getReceiverType(const llvm::CallBase *CallSite) {
     return nullptr;
   }
 
-  if (Receiver->getType()->isOpaquePointerTy()) {
+ 
+  if (Receiver->getType()->isPointerTy()) {
     llvm::errs() << "WARNING: The IR under analysis uses opaque pointers, "
                     "which are not supported by phasar yet!\n";
     return nullptr;
diff --git a/unittests/PhasarLLVM/DataFlow/IfdsIde/InteractiveIDESolverTest.cpp b/unittests/PhasarLLVM/DataFlow/IfdsIde/InteractiveIDESolverTest.cpp
index 6ff07a20..6d74ea77 100644
--- a/unittests/PhasarLLVM/DataFlow/IfdsIde/InteractiveIDESolverTest.cpp
+++ b/unittests/PhasarLLVM/DataFlow/IfdsIde/InteractiveIDESolverTest.cpp
@@ -24,7 +24,7 @@ protected:
 }; // Test Fixture
 
 TEST_P(LinearConstant, ResultsEquivalentSolveUntil) {
-  HelperAnalyses HA(PathToLlFiles + GetParam(), EntryPoints);
+  HelperAnalyses HA(PathToLlFiles + GetParam().data(), EntryPoints);

   // Compute the ICFG to possibly create the runtime model
   auto &ICFG = HA.getICFG();
@@ -67,7 +67,7 @@ TEST_P(LinearConstant, ResultsEquivalentSolveUntil) {
 }
 
 TEST_P(LinearConstant, ResultsEquivalentSolveUntilAsync) {
-  HelperAnalyses HA(PathToLlFiles + GetParam(), EntryPoints);
+  HelperAnalyses HA(PathToLlFiles + GetParam().data(), EntryPoints);
 
   // Compute the ICFG to possibly create the runtime model
   auto &ICFG = HA.getICFG();

Did I invoke phasar-cli correctly or there was a potential bug? Hope for your help.

[MMory]

Hi @yiyuaner , this is indeed a bug in phasar. LLVM IR itself does not contain all of the information to conclude relationships between classes in all cases. For that we need IR compiled with debug information. An improved TH analysis that uses debug info is already in development.