# range_analyzer

**Repository Path**: rogerskelamen/range_analyzer

## Basic Information

- **Project Name**: range_analyzer
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-11-14
- **Last Updated**: 2025-12-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Range Analyzer

<div align="center">

**基于 Clang/LLVM 的静态值范围分析工具**

[![C++17](https://img.shields.io/badge/C%2B%2B-17-blue.svg)](https://isocpp.org/std/the-standard)
[![LLVM 14](https://img.shields.io/badge/LLVM-14-orange.svg)](https://llvm.org/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)

[功能特性](#功能特性) • [快速开始](#快速开始) • [架构设计](#架构设计) • [使用示例](#使用示例) • [文档](#文档)

</div>

---

## 项目简介

Range Analyzer 是一个静态程序分析工具，通过抽象解释技术推断 C/C++ 程序中整型变量的值范围。

**核心目标**：为高层次综合 (HLS) 提供变量位宽优化依据，通过精确的值范围分析确定变量的最小位宽需求，从而优化硬件面积。

```
源代码分析 → 值范围推断 → 位宽优化 → 硬件面积减少
```

## 功能特性

### 🔍 分析能力

| 特性           | 描述                                                 |
|----------------|------------------------------------------------------|
| **过程内分析** | 分析单个函数内的变量值范围                           |
| **过程间分析** | 三遍算法跨函数传播参数范围                           |
| **循环分析**   | for/while/do-while 循环，支持嵌套和复杂条件          |
| **累加分析**   | 识别 `sum += i`、`arr[i]++` 等累加模式并精确计算范围 |
| **条件分支**   | if-else 约束提取与范围收窄，分支合并                 |
| **数组分析**   | 初始化列表、循环填充、副作用传播                     |
| **静态变量**   | 跨调用稳态范围计算                                   |

### ⚡ 运算符支持

```
算术运算: +  -  *  /  %
位运算:   &  |  ^  ~  <<  >>
逻辑运算: &&  ||  !
比较运算: <  >  <=  >=  ==  !=
自增减:   ++x  x++  --x  x--
复合赋值: +=  -=  *=  /=  %=  &=  |=  ^=  <<=  >>=
三元运算: ? :
```

### 📊 累加模式识别

```cpp
sum += 5;           // 常数累加
sum += i;           // 循环变量累加（等差数列求和）
sum += arr[i];      // 数组元素累加
acc += a * i;       // 乘积累加
cond ? S++ : S--;   // 条件副作用
if (x > 0) cnt++;   // 条件增量
```

## 快速开始

### 环境要求

- **操作系统**: Linux (Ubuntu 20.04+)
- **编译器**: GCC 9+ 或 Clang 10+
- **依赖**: LLVM/Clang 14, CMake 3.15+, Ninja

### 安装依赖

```bash
# Ubuntu/Debian
sudo apt-get install llvm-14-dev libclang-14-dev clang-14 ninja-build cmake
```

### 编译

```bash
# 克隆项目
git clone <repository-url>
cd range_analyzer

# 编译
cmake -B build -S . -G Ninja
cmake --build build

# 验证
./build/range_analyzer --help
```

### 运行分析

```bash
# 使用脚本（推荐）
./scripts/run_analysis.sh test/unit/basic

# 或直接运行
./build/range_analyzer test/unit/loop/loop.cpp -o results.json -- -std=c++17

# 分析多个文件
./build/range_analyzer src1.cpp src2.cpp -o output.json -- -std=c++17
```

### 配置选项

```bash
# 日志级别 (0=静默, 3=默认, 5=详细)
./build/range_analyzer file.cpp --log-level 4 -- -std=c++17

# 环境变量配置
LOG_LEVEL=4 OUTPUT_FILE=my_results.json ./scripts/run_analysis.sh loop
```

## 架构设计

### 三层架构

```
┌─────────────────────────────────────────────────────────────┐
│  Layer 3: Coordination (协调层)                              │
│  ┌─────────────────┐  ┌─────────────────┐                   │
│  │ AnalysisPipeline │  │  RangeAnalyzer  │                   │
│  │   三遍分析编排    │  │   函数级协调器   │                   │
│  └─────────────────┘  └─────────────────┘                   │
└─────────────────────────────────────────────────────────────┘
                              ↓
┌─────────────────────────────────────────────────────────────┐
│  Layer 2: Analysis Engines (分析引擎层)                      │
│  ┌──────────────┐ ┌──────────────┐ ┌──────────────┐         │
│  │  statement/  │ │    loop/     │ │   variable/  │         │
│  │ ─────────────│ │ ─────────────│ │ ─────────────│         │
│  │ Statement    │ │ Loop         │ │ Variable     │         │
│  │ Condition    │ │ Accumulation │ │ FunctionCall │         │
│  │ Expression   │ │              │ │ Array        │         │
│  │              │ │              │ │ Constraint   │         │
│  └──────────────┘ └──────────────┘ └──────────────┘         │
└─────────────────────────────────────────────────────────────┘
                              ↓
┌─────────────────────────────────────────────────────────────┐
│  Layer 1: Infrastructure (基础设施层)                        │
│  ┌──────────────────────┐  ┌──────────────────────┐         │
│  │        core/         │  │        util/         │         │
│  │ ─────────────────────│  │ ─────────────────────│         │
│  │ ValueRange           │  │ JSONExporter         │         │
│  │ AnalysisContext      │  │ MathLibrary          │         │
│  │ AnalysisPipeline     │  │ ASTUtils             │         │
│  │ Logger               │  │                      │         │
│  │ StaticVariableTracker│  │                      │         │
│  └──────────────────────┘  └──────────────────────┘         │
└─────────────────────────────────────────────────────────────┘
```

### 三遍分析算法

```
Pass 1: Call Graph Construction
    │   构建调用图，记录函数调用关系
    ↓
    IPA Round 1: 初始参数范围传播
    ↓
Pass 2: Range Refinement  
    │   利用 IPA 结果细化局部范围
    ↓
    IPA Round 2: 传播精确参数范围
    ↓
Pass 3: Side-Effect Recording
    │   跟踪数组参数副作用
    ↓
    IPA Round 3: 最终传播
    ↓
    输出 JSON 结果
```

### 模块职责

| 模块 | 职责 |
|------|------|
| `AnalysisPipeline` | 三遍分析流程编排 |
| `RangeAnalyzer` | 函数级分析协调 |
| `StatementAnalyzer` | 语句类型分发与遍历 |
| `LoopAnalyzer` | 循环结构分析 |
| `AccumulationAnalyzer` | 累加模式检测与计算 |
| `ConditionAnalyzer` | 条件分支约束传播 |
| `ExpressionEvaluator` | 表达式抽象求值 |
| `VariableTracker` | 变量生命周期管理 |
| `FunctionCallAnalyzer` | 过程间调用分析 |
| `ArrayAnalyzer` | 数组元素范围跟踪 |
| `ConstraintSolver` | 约束求解与范围收窄 |
| `ValueRange` | 值范围数据结构 |
| `AnalysisContext` | 全局 IPA 上下文 |

## 使用示例

### 条件分支分析

```cpp
void example(int x) {  // x: [0, 99]
    int a = x;          // a: [0, 99]
    if (x > 50) {
        int b = x;      // b: [51, 99] ← 范围收窄
    } else {
        int c = x;      // c: [0, 50]  ← 范围收窄
    }
}
```

### 循环累加分析

```cpp
void sum_example() {
    int sum = 0;
    for (int i = 0; i < 10; i++) {  // i: [0, 9]
        sum += i;                    // sum: [0, 45] (0+1+...+9)
    }
}
```

### 数组分析

```cpp
void array_example() {
    int arr[5] = {1, 3, 5, 7, 9};   // arr: [1, 9]
    int x = arr[2];                  // x: [1, 9]
}
```

### 过程间分析

```cpp
void callee(int param) {     // param: [0, 19] (从调用点传播)
    int local = param * 2;   // local: [0, 38]
}

void caller() {
    for (int i = 0; i < 20; i++) {
        callee(i);           // 传播 i 的范围 [0, 19]
    }
}
```

## 输出格式

### JSON 输出

```json
[
  {
    "file": "/path/to/source.cpp",
    "function_name": "process",
    "var_name": "input",
    "var_type": "parameter",
    "data_type": "int",
    "value_range": "[0, 19]"
  },
  {
    "file": "/path/to/source.cpp",
    "function_name": "process",
    "var_name": "result",
    "var_type": "local",
    "data_type": "int",
    "value_range": "[0, 38]"
  }
]
```

### 控制台输出

```
═══════════════════════════════════════════════════════════
  Analysis Summary
═══════════════════════════════════════════════════════════

Total variables: 80
  Parameters: 12 (10 resolved)
  Local vars: 68 (65 resolved)

Coverage: 75/80 (93%)
Output: variable_ranges.json

Parameter Ranges:
─────────────────────────────────────────────────────────
  process::input = [0, 19]
  compute::x = [0, 99]
  compute::y = [5, 5]

═══════════════════════════════════════════════════════════
```

## 项目结构

```
range_analyzer/
├── include/                      # 头文件
│   ├── analysis/                 # 分析引擎层
│   │   ├── loop/                 # 循环分析
│   │   │   ├── LoopAnalyzer.h
│   │   │   ├── AccumulationAnalyzer.h
│   │   │   └── accumulation/     # 累加模式
│   │   ├── statement/            # 语句分析
│   │   │   ├── StatementAnalyzer.h
│   │   │   ├── ConditionAnalyzer.h
│   │   │   └── ExpressionEvaluator.h
│   │   └── variable/             # 变量分析
│   │       ├── VariableTracker.h
│   │       ├── FunctionCallAnalyzer.h
│   │       ├── ArrayAnalyzer.h
│   │       └── ConstraintSolver.h
│   ├── analyzer/                 # 协调层
│   │   └── RangeAnalyzer.h
│   └── infrastructure/           # 基础设施层
│       ├── core/                 # 核心组件
│       │   ├── ValueRange.h
│       │   ├── AnalysisContext.h
│       │   ├── AnalysisPipeline.h
│       │   ├── AnalysisConfig.h
│       │   ├── AnalysisState.h
│       │   ├── Logger.h
│       │   └── StaticVariableTracker.h
│       └── util/                 # 工具类
│           ├── JSONExporter.h
│           ├── MathLibrary.h
│           └── ASTUtils.h
├── src/                          # 源文件（结构同 include）
├── test/                         # 测试用例
│   ├── unit/                     # 单元测试
│   │   ├── basic/                # 基础变量
│   │   ├── loop/                 # 循环分析
│   │   ├── condition/            # 条件分支
│   │   ├── array/                # 数组分析
│   │   ├── accumulate/           # 累加模式
│   │   ├── function/             # 函数调用
│   │   └── ...
│   ├── real/                     # 真实算法测试
│   │   ├── cusums.cpp            # Cumulative Sums
│   │   ├── fir.cpp               # FIR 滤波器
│   │   ├── floyd_warshall.cpp
│   │   ├── nw.cpp                # Needleman-Wunsch
│   │   └── ...
│   └── run_all_tests.sh
├── docs/                         # 详细文档
│   ├── ARCHITECTURE.md           # 架构设计
│   ├── API_GUIDE.md              # API 指南
│   ├── ACCUMULATION_ANALYSIS.md  # 累加分析说明
│   ├── ARRAY_ANALYSIS.md         # 数组分析说明
│   └── MATH_LIBRARY_SUPPORT.md   # 数学库支持
├── scripts/
│   └── run_analysis.sh           # 分析脚本
├── CMakeLists.txt
└── README.md
```

## 测试

### 运行单元测试

```bash
# 运行所有测试
./test/run_all_tests.sh

# 运行特定测试集
./scripts/run_analysis.sh loop
./scripts/run_analysis.sh array
./scripts/run_analysis.sh accumulate

# 运行真实算法测试
./build/range_analyzer test/real/cusums.cpp -- -std=c++17
```

### 测试覆盖

| 测试集 | 描述 |
|--------|------|
| `basic` | 变量声明、赋值、算术运算 |
| `loop` | for/while 循环、嵌套循环 |
| `condition` | if-else 分支、约束传播 |
| `array` | 数组初始化、访问、修改 |
| `accumulate` | 累加模式识别与计算 |
| `function` | 函数调用、参数传播 |
| `side_effect` | 数组副作用跟踪 |
| `math_lib` | 数学库函数支持 |

## 命令行选项

```bash
./build/range_analyzer [选项] <源文件...> -- [编译器标志]

选项:
  -o <文件名>       输出JSON文件名（默认: variable_ranges.json）
  --log-level <0-5> 日志级别（0=静默, 3=默认, 5=详细）
  
示例:
  ./build/range_analyzer test/unit/loop/loop.cpp -- -std=c++17
  ./build/range_analyzer -o results.json --log-level 4 test/*.cpp -- -std=c++17
```

## 文档

- [架构设计](docs/ARCHITECTURE.md) - 详细架构说明和设计决策
- [API 指南](docs/API_GUIDE.md) - 核心 API 使用说明
- [累加分析](docs/ACCUMULATION_ANALYSIS.md) - 累加模式检测与计算
- [数组分析](docs/ARRAY_ANALYSIS.md) - 数组值范围分析
- [数学库支持](docs/MATH_LIBRARY_SUPPORT.md) - 数学函数范围处理
- [测试框架](test/TEST_FRAMEWORK.md) - 测试用例编写指南

## 技术规格

| 指标 | 值 |
|------|-----|
| C++ 标准 | C++17 |
| LLVM 版本 | 14+ |
| 分析精度 | ~95% 变量覆盖 |
| IPA 迭代上限 | 5 次 |
| 时间复杂度 | O(n) per function |

## 路线图

- [x] 基础值范围分析
- [x] 循环迭代分析
- [x] 条件分支约束传播
- [x] 数组元素范围跟踪
- [x] 过程间参数传播
- [x] 累加模式识别
- [x] 三遍分析算法
- [ ] 返回值范围传播
- [ ] 指针别名分析
- [ ] 索引敏感数组分析
- [ ] 符号化范围表示

## 贡献

欢迎提交 Issue 和 Pull Request！

## 许可

本项目采用 [MIT 许可证](LICENSE)。

---

<div align="center">

**Range Analyzer** - 精确的静态值范围分析，助力硬件优化

</div>