LLVM/Clang — CWE-407 Analysis
==============================

.. contents:: :local:

Overview
--------

LLVM is a widely used compiler infrastructure project; Clang is the C/C++/Objective-C frontend
built on top of it. During Link Time Optimization (LTO), LLVM's ``GlobalsModRef`` pass builds
a call graph to determine which globals are modified by each function. One CWE-407 defect site
was found in the LTO call-graph traversal. It is unpatched.

Defect Sites
------------

llvm-0001
~~~~~~~~~

**File:** ``llvm/lib/Analysis/GlobalsModRef.cpp:570``

**Pattern:**

.. code-block:: cpp

   // LTO call graph traversal — is_contained on vector of call graph nodes
   SmallVector<CallGraphNode *, 8> visiting;
   // ...
   void analyzeCallGraph(CallGraphNode *node) {
       if (is_contained(visiting, node)) return;  // O(V) — is_contained is std::find
       visiting.push_back(node);
       for (auto &edge : *node) {
           analyzeCallGraph(edge.second);
       }
       visiting.pop_back();
   }

**Why this is O(n):** ``is_contained`` (an LLVM ADT helper) calls ``std::find`` on the
``SmallVector``, which is a linear scan. Called once per node per DFS frame.

**Complexity:** ``O(V×E)`` where V = call graph nodes, E = call edges (during LTO)

**Patch:**

.. code-block:: cpp

   SmallPtrSet<CallGraphNode *, 8> visitingSet;
   SmallVector<CallGraphNode *, 8> visiting;   // keep for stack ordering

   void analyzeCallGraph(CallGraphNode *node) {
       if (!visitingSet.insert(node).second) return;  // O(1) hash set
       visiting.push_back(node);
       for (auto &edge : *node) {
           analyzeCallGraph(edge.second);
       }
       visiting.pop_back();
       visitingSet.erase(node);
   }

**Data structure change:** ``SmallVector<CGN*>`` + ``is_contained`` → ``SmallPtrSet<CGN*>`` + ``insert()``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let V = call graph nodes. ``is_contained`` scans a vector of up to V elements: O(V) per call.
With V calls during DFS: O(V²). ``SmallPtrSet::insert()`` returns a pair indicating whether
the element was newly inserted — O(1) amortized. Total: O(V). QED.

References
----------

* Defect ticket: ``tools/tickets/defects/llvm-0001.md``
