# 优化模块 # 第一步: 常量传播 def constant_propagation(quads): #print("Running Constant Propagation") value_map = {} optimized = [] for quad in quads: op, arg1, arg2, dest = quad if op == '=' and arg1.isdigit(): # 常量赋值:如 (=, 32, _, _v0) value_map[dest] = arg1 elif op == '=': # 变量赋值:如 (=, _v0, _, age) if arg1 in value_map: new_quad = ('=', value_map[arg1], '_', dest) optimized.append(new_quad) value_map[dest] = value_map[arg1] else: optimized.append(quad) # 如果 dest 不再被使用,可以考虑删除该赋值 else: # 替换操作数中的变量为已知常量 new_arg1 = value_map.get(arg1, arg1) new_arg2 = value_map.get(arg2, arg2) if arg2 != '_' else '_' optimized.append((op, new_arg1, new_arg2, dest)) return optimized # 第二步: 公共子表达式消除 def common_subexpression_elimination(quads): #print("Running Common Subexpression Elimination") expr_map = {} optimized = [] temp_counter = 0 for quad in quads: op, arg1, arg2, dest = quad if op in ['+', '-', '*', '/']: expr_key = f"{arg1} {op} {arg2}" if expr_key in expr_map: # 复用已有结果 reused_var = expr_map[expr_key] optimized.append(('=', reused_var, '_', dest)) else: # 新表达式 temp_var = f"_t{temp_counter}" temp_counter += 1 expr_map[expr_key] = temp_var optimized.append((op, arg1, arg2, temp_var)) optimized.append(('=', temp_var, '_', dest)) else: optimized.append(quad) return optimized # 第三步: 死代码消除 def dead_code_elimination(quads): #print("Running Dead Code Elimination") used_vars = set() optimized = [] # 第一遍找出所有被使用的变量 for quad in quads: op, arg1, arg2, dest = quad if arg1 != '_' and not arg1.isdigit(): used_vars.add(arg1) if arg2 != '_' and not arg2.isdigit(): used_vars.add(arg2) # 第二遍删除未使用变量的赋值语句 for quad in quads: op, arg1, arg2, dest = quad if op == '=' and dest.startswith('_v') and dest not in used_vars: continue # 跳过无用的赋值语句 optimized.append(quad) return optimized # 第四步: 控制流优化 def control_flow_simplification(quads): # print("Running Control Flow Simplification") optimized = [] for quad in quads: op, arg1, arg2, dest = quad if op == 'if' and arg2 == 'goto': if arg1.isdigit(): if arg1 == '1': optimized.append(('goto', '_', '_', dest)) elif arg1 == '0': continue # 恒假,跳过该条件跳转 else: optimized.append(quad) else: optimized.append(quad) return optimized # 第五步: 寄存器重用 def register_reuse(quads): #print("Running Register Reuse (Improved)") # 计算活跃变量信息 live_info = compute_live_vars(quads) optimized = [] available_temps = [] # 可用于复用的临时变量池 for i, quad in enumerate(quads): op, arg1, arg2, dest = quad current_live = live_info[i] if op == '=': # 查看当前 dest 是否会被后续使用 is_dest_used_later = dest in current_live # 如果 dest 不再使用,可以加入可用池 if not is_dest_used_later and dest.startswith('_'): available_temps.append(dest) # 尝试复用已死的临时变量 reused = False for var in list(available_temps): if var not in [arg1, arg2] and var not in current_live: # 安全复用 optimized.append(('=', arg1, arg2, var)) available_temps.remove(var) if var != dest: available_temps.append(dest) # 原 dest 现在可回收 reused = True break if not reused: optimized.append(quad) if dest.startswith('_') and dest not in current_live: available_temps.append(dest) else: optimized.append(quad) return optimized def compute_live_vars(quads): """ 活跃变量分析:从后往前推导每个 quad 之后仍会使用的变量 """ live_vars = set() live_info = [] for quad in reversed(quads): op, arg1, arg2, dest = quad # 先移除 dest 的影响(因为 dest 被重新定义) if dest in live_vars: live_vars.remove(dest) # 如果操作数是变量,则加入活跃集合 if arg1 != '_' and not arg1.isdigit(): live_vars.add(arg1) if arg2 != '_' and not arg2.isdigit(): live_vars.add(arg2) # 把当前活跃变量集合复制一份保存下来 live_info.append(live_vars.copy()) # 从后往前遍历,所以需要反转结果 live_info.reverse() return live_info # 优化器整合 def optimize(quads): passes = [ ("Constant Propagation", constant_propagation), ("Common Subexpression Elimination", common_subexpression_elimination), ("Dead Code Elimination", dead_code_elimination), ("Control Flow Simplification", control_flow_simplification), ("Register Reuse", register_reuse), ] for name, opt_func in passes: # print(f"Running optimization pass: {name}") quads = opt_func(quads) return quads def output_ir_str(quads): lines = [] for i, quad in enumerate(quads): op, arg1, arg2, dest = quad quad = f"({op}, {arg1}, {arg2}, {dest})" lines.append(f"{i} {quad}") return "\n".join(lines)