南大-ICS2021 PA1~PA2.2 学习笔记记录

2024-08-21 19:28
文章标签 学习 笔记 记录 南大 pa1 ics2021 pa2.2

本文主要是介绍南大-ICS2021 PA1~PA2.2 学习笔记记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 代码github网址
  • ICS2021其他博客
  • 基础设施: 简易调试器
  • 表达式求值
    • 词法分析
    • 递归求值
    • 如何测试自己的代码
  • 监视点的实现
    • 扩展表达式求值的功能
    • 实现监视点
  • 阅读源码 2
    • 译码
    • 执行
    • 用RTL表示指令行为
    • 实现常用的库函数
    • 实现常用的库函数

代码github网址

https://github.com/xiao-tai/ics2021

ICS2021其他博客

南大-ICS2021 PA2.3 学习笔记&记录
南大-ICS2021 PA3.1 学习笔记&记录
南大ICS2021–实现库函数vsnprintf

基础设施: 简易调试器

这些都还比较简单实现, 具体可以查看nemu/src/sdb/sdb.c中的

  • cmd_c: 启动执行

  • cmd_q: 退出NEMU

  • cmd_si: 单步执行

  • cmd_x: 打印内存

  • cmd_p: 进行表达式求值, 具体实现看下节

表达式求值

主要文件为src/monitor/sdb/expr.c，具体可以查看我的github

词法分析

对于一下表达式:

"0x80100000+   ($a0 +5)*4 - *(  $t1 + 8) + number"

我们需要将各个单元(也就是token)给识别出来, 使用正则表达式可以方便的匹配出一些复杂的pattern, 代码框架中的init_regex()函数负责将定义的正则表达式进行验证, 函数在此处报错通常是因为使用了非法的正则表达式

在这里插入图片描述
本人所用到的正则表达式如下图

在这里插入图片描述

然后, 给定一个表达式, 通过make_token()来识别token类型, 将识别结果保存在一个tokens[i]中, 将对应的字符串保存在str[32]属性中, 类型保存在type属性中, 以上述表达式为例,

tokens[0].str = 0x80100000, tokens[0].type = TK_HEX_NUM, 以此类推, 这样一个表达式所有的taoken都识别完毕了.

递归求值

这里就是涉及到算法的知识了, 需要用到分治法, 这类方法在排序上也有一个经典的应用–快速排序算法. 表达式求值使用上, 我们需要先对短表达式求值, 再对长表达式求值, 所以要使用递归. 这里需要考虑括号的问题和运算符优先级的问题.

eval(p, q) {if (p > q) {/* Bad expression */}else if (p == q) {/* Single token.* For now this token should be a number.* Return the value of the number.*/}else if (check_parentheses(p, q) == true) {/* The expression is surrounded by a matched pair of parentheses.* If that is the case, just throw away the parentheses.*/return eval(p + 1, q - 1);}else {op = the position of 主运算符 in the token expression;val1 = eval(p, op - 1);val2 = eval(op + 1, q);switch (op_type) {case '+': return val1 + val2;case '-': /* ... */case '*': /* ... */case '/': /* ... */default: assert(0);}}
}

对于一个长表达式, 需要先找出主运算符, 本人计算主运算符逻辑是

  • 遍历p和q之间所有的运算符

  • 优先级高的运算符放到后面进行if判断, 因为主运算符是最后一步才进行运算的

// 获取主运算符的位置
int get_position(int p, int q) {int pos = 0;int num = 0;bool plus_or_sub = false;bool mul_or_div = false;bool minus = false;bool deref = false;for(int i = p; i <= q; i++) {if(tokens[i].type == '(')num++;if(tokens[i].type == ')')num--;if(num != 0)continue;if(tokens[i].type == TK_EQ) {return i;}// The lower the priority, the higher the judge will beif(tokens[i].type == '+' || tokens[i].type == '-') {pos = i;plus_or_sub = true;continue;}        if((tokens[i].type == '*' || tokens[i].type == '/') && !plus_or_sub) {pos = i;mul_or_div = true;continue;}if(tokens[i].type == TK_MINUS && !plus_or_sub && !mul_or_div && !minus) {pos = i;minus = true;}if(tokens[i].type == TK_DEREF && !plus_or_sub && !mul_or_div && !deref) {pos = i;deref = true;}}return pos;
}

如何测试自己的代码

写一个随机生成表达式的程序, 要求合法, 其实就是将生成的表达式, 例如1 + 2 + 3传入一个定义好的文件中

#include <stdio.h>int main() {unsigned result = 1 + 2 + 3;printf("%u\n", result);
}

监视点的实现

扩展表达式求值的功能

在递归求解表达式前, 要区分*是乘法运算符, 还是解引用, 所以在进行递归前, 先做一次判断, 以区分负号和减号, 乘号和解引用运算符:

for (int i = 0; i < nr_token; i++) {if(tokens[i].type == '-') {if(i == 0 || (tokens[i-1].type != ')' && tokens[i-1].type != TK_NUM))tokens[i].type = TK_MINUS;}if(tokens[i].type == '*') {if(i == 0 || (tokens[i-1].type != ')' && tokens[i-1].type != TK_NUM))tokens[i].type = TK_DEREF;}
}

实现监视点

使用两个链表维护一个监视点池, head负责维护使用中的监视点结构, free_负责维护空闲的监视点结构. 监视点的机构体如下:

typedef struct watchpoint {int NO;struct watchpoint *next;// 额外添加两个成员, 用于后续的扫描char exp[32]; //表达式uint32_t res;
} WP;

这时还需要增加监视点和删除监视点这两个函数, 同时还需要有扫描所有监视点的函数:

  • 增加监视点(new_wp): 申请一个空闲监视点, 并将表达式记录下来

  • 删除监视点(free_wp(int no)): 通过监视点编号删除监视点, 将其表达式设置为’\0’, 即代表该监视点不参与监视

  • 扫描监视点(check_all_wp()): 每当cpu_exec()执行一条指令时, 都会调用一次trace_and_difftest(), 所以在其中扫描一次所有监视点, 对其表达式进行求值, 如果结果发生变化, 就打印出来, 并将nemu_state.state变量设置为NEMU_STOP

具体见src/monitor/sdb/watchpoint.c

阅读源码 2

译码

译码上, 框架代码进行了多层抽象.

取指令的时候会把指令记录到s->isa.instr.val, 首先匹配opecode字段, 再匹配func3字段, 再匹配func7字段, 这样isa_fetch_decode()会返回唯一的idx, 用于表示执行的指令.

但是我们还不知道操作对象(比如立即数是多少, 使用哪个寄存器), 使用译码辅助函数

// 宏定义解开的样子
def_DHelper(name) = void decode_name(Decode *s)

每个译码辅助函数负责进行一种类型的操作数译码, 把指令中的操作数信息分别记录在译码信息s的dest成员, src1成员和src2成员中, 它们分别代表目的操作数和两个源操作数. nemu/include/cpu/decode.h中还定义了三个宏id_dest, id_src1和id_src2, 用于方便地访问它们.

同时为了更好的实现操作数译码和指令译码的解耦, 使用译码操作数辅助函数

def_DopHelper(name) = void decode_op_name(Decode *s, Operand *op, word_t val, bool flag)

  • decode_op_i: 通过译码的指令获得立即数

  • decode_op_r: 通过译码的指令获得寄存器

执行

在fetch_decode()中得到的执行辅助函数记录到s->EHelper中

在这里插入图片描述

执行辅助函数统一通过宏def_EHelper, 具体通过RTL指令来进行真正的执行

def_EHelper(name) = static inline void exec_name(Decode *s)

每个执行辅助函数都需要有一个标识该指令的ID以及一个表格辅助函数与之相对应, 这一点是通过一系列宏定义来实现的. 在nemu/src/isa/$ISA/include/isa-all-instr.h中定义用于表示指令列表的宏INSTR_LIST, 它定义了NEMU支持的所有指令.

用RTL表示指令行为

在NEMU中, RTL寄存器只有以下这些

  • 不同ISA的通用寄存器(在nemu/src/isa/$ISA/include/isa-def.h中定义)
  • 临时寄存器s0, s1, s2和t0(在nemu/include/rtl/rtl.h中定义)
  • 零寄存器rz(在nemu/include/rtl/rtl.h中定义), 它的值总是0

进入nemu/build/obj-riscv32-nemu-interpreter/src/cpu/cpu-exec.i查看具体的执行情况, g_exec_table如下:

static const void *g_exec_table[TOTAL_INSTR] = {[EXEC_ID_lui] = exec_lui,[EXEC_ID_lb] = exec_lb,[EXEC_ID_lbu] = exec_lbu,[EXEC_ID_lh] = exec_lh,[EXEC_ID_lhu] = exec_lhu,[EXEC_ID_lw] = exec_lw,[EXEC_ID_sw] = exec_sw,[EXEC_ID_sh] = exec_sh,[EXEC_ID_sb] = exec_sb,//.....
}

各个函数的具体实现位于src/isa/riscv32/instr/compute.h中, 通过以下指令查找得到:

xiaoxTai:nemu$ grep -r "rtl_add" ../src/isa/riscv32/instr/compute.h:  rtl_addi(s, ddest, dsrc1, id_src2->imm);
./src/isa/riscv32/instr/compute.h:  rtl_add(s, ddest, dsrc1, dsrc2);

在这里插入图片描述

所以实现一个新指令的步骤如下:

  1. 在nemu/src/isa/riscv32/instr/decode.c中添加正确的模式匹配规则
  2. 用RTL实现正确的执行辅助函数, 在./src/isa/riscv32/instr/compute.h或者instr文件夹下其他的头文件
  3. 在nemu/src/isa/riscv32/include/isa-all-instr.h中把指令添加到INSTR_LIST中
  4. 必要时在nemu/src/isa/riscv32/include/isa-exec.h添加相应的头文件, 言外之意就是第二步写在哪个头文件下, 就把那个头文件, 加到这个isa-exec.h中

在这里插入图片描述

接下来就是通过运行程序, 检查还有哪些指令没有实现, 安装好交叉编译环境, 通过执行

make ARCH=riscv32-nemu ALL=dummy run

运行结果打印的信息会提示你还有什么指令没有实现, 当然要通过在am-kernels/tests/cpu-tests/build/dummy-$ISA-nemu.txt进行搜索

实现常用的库函数

相关库函数的具体实现, 也是面试中出现频率较高的问题了, 主要在abstract-machine/klib/src/下

  • strcpy, memset等函数在string.c下

  • sprintf()在stdio.c下, 这个函数实现的讲解见我的另一篇博客

  • atoi, malloc在stdlib.c下
    果打印的信息会提示你还有什么指令没有实现, 当然要通过在am-kernels/tests/cpu-tests/build/dummy-$ISA-nemu.txt进行搜索

实现常用的库函数

相关库函数的具体实现, 也是面试中出现频率较高的问题了, 主要在abstract-machine/klib/src/下

  • strcpy, memset等函数在string.c下

  • sprintf()在stdio.c下, 这个函数实现的讲解见我的另一篇博客南大ICS2021–实现库函数vsnprintf

  • atoi, malloc在stdlib.c下

这篇关于南大-ICS2021 PA1~PA2.2 学习笔记记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1094065。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程（Gaussian Process，简称GP）是一种概率模型，用于描述一组随机变量的联合概率分布，其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数（或核函数） 1.3 核函数1.4 高斯过程回归（Gauss
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...
线性代数|机器学习-P36在图中找聚类

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大，需要补充太多的知识点，教授讲得内容跨越较大，一般一节课的内容是书本上的一章节内容，所以看视频比较吃力，需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构： Adjacency Matrix:行和列表示的是节点的位置，A[i,j]表示的第 i 个节点和第 j 个
阅读更多...
Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2