作业 4：类层次结构分析与过程间常量传播

实现类层次结构分析（CHA）

• dispatch ：根据方法调用者的类和方法签名寻找目标方法。

比较显然，是个递归算法。

递归的终止条件有两个，一个是如果一直找不到相应方法，不断递归到父类，最后递归到 Object 在向上递归就是 null ，Object 没有父类，此时返回空，说明找不到相应方法；另一个是如果当前类的方法中有能匹配方法签名的方法，并且该方法不是抽象方法，说明找到相应方法，返回该方法。

其他情况向当前类的父类递归。

/**
 * Looks up the target method based on given class and method subsignature.
 *
 * @return the dispatched target method, or null if no satisfying method
 * can be found.
 */
private JMethod dispatch(JClass jclass, Subsignature subsignature) {
    // TODO - finish me
    if (jclass == null) {
        return null;
    }
    if (jclass.getDeclaredMethod(subsignature) != null && !jclass.getDeclaredMethod(subsignature).isAbstract()) {
        return jclass.getDeclaredMethod(subsignature);
    }
    return dispatch(jclass.getSuperClass(), subsignature);
}

• resolve ：通过类的继承关系确定一个调用点的所有可能的目标方法。

/**
 * Resolves call targets (callees) of a call site via CHA.
 */
private Set<JMethod> resolve(Invoke callSite) {
    // TODO - finish me
    Set<JMethod> T = new HashSet<JMethod>();
    MethodRef m = callSite.getMethodRef();
    Subsignature subsignature = m.getSubsignature();
    JClass declaringClass = m.getDeclaringClass();
    CallKind callKind = CallGraphs.getCallKind(callSite);
    switch (callKind) {
        case STATIC -> {
            T.add(declaringClass.getDeclaredMethod(subsignature));
            break;
        }
        case SPECIAL -> {
            T.add(dispatch(declaringClass, subsignature));
            break;
        }
        case VIRTUAL, INTERFACE -> {
            ArrayDeque<JClass> subclasses = new ArrayDeque<>();
            HashSet<JClass> set = new HashSet<>();
            subclasses.addLast(declaringClass);
            set.add(declaringClass);
            while (!subclasses.isEmpty()) {
                JClass subclass = subclasses.pollFirst();
                T.add(dispatch(subclass, subsignature));
                for (JClass jClass : (hierarchy.getDirectSubclassesOf(subclass))) {
                    if (!set.contains(jClass)) {
                        set.add(jClass);
                        subclasses.addLast(jClass);
                    }
                }
                for (JClass jClass : (hierarchy.getDirectSubinterfacesOf(subclass))) {
                    if (!set.contains(jClass)) {
                        set.add(jClass);
                        subclasses.addLast(jClass);
                    }
                }
                for (JClass jClass : (hierarchy.getDirectImplementorsOf(subclass))) {
                    if (!set.contains(jClass)) {
                        set.add(jClass);
                        subclasses.addLast(jClass);
                    }
                }
            }
            break;
        }
    }
    return T;
}

• buildCallGraph ：构造调用图

代码中 DefaultCallGraph 既是个调用图 CG ，也能记录哪些方法访问过，即也是个 RM 。

private CallGraph<Invoke, JMethod> buildCallGraph(JMethod entry) {
    DefaultCallGraph callGraph = new DefaultCallGraph();
    callGraph.addEntryMethod(entry);
    // TODO - finish me
    ArrayDeque<JMethod> worklist = new ArrayDeque<>();
    worklist.addLast(entry);
    while (!worklist.isEmpty()) {
        JMethod m = worklist.pollFirst();
        if (!callGraph.contains(m)) {
            callGraph.addReachableMethod(m);
            Stream<Invoke> invokeStream = callGraph.callSitesIn(m);
            invokeStream.forEach(cs -> {
                for (JMethod targetMethod : resolve(cs)) {
                    if (targetMethod != null) {
                        callGraph.addEdge(new Edge<>(CallGraphs.getCallKind(cs), cs, targetMethod));
                        worklist.addLast(targetMethod);
                    }
                }
            });
        }
    }
    return callGraph;
}

实现过程间常量传播

• transferCallNode ：

@Override
protected boolean transferCallNode(Stmt stmt, CPFact in, CPFact out) {
    // TODO - finish me
    return out.copyFrom(in);
}

• transferNonCallNode ：

@Override
protected boolean transferNonCallNode(Stmt stmt, CPFact in, CPFact out) {
    // TODO - finish me
    
    return cp.transferNode(stmt, in, out);
}

• transferNormalEdge ：

@Override
protected CPFact transferNormalEdge(NormalEdge<Stmt> edge, CPFact out) {
    // TODO - finish me
    return out;
}

• transferCallToReturnEdge

@Override
protected CPFact transferCallToReturnEdge(CallToReturnEdge<Stmt> edge, CPFact out) {
    // TODO - finish me
    CPFact copy = out.copy();
    if (edge.getSource().getDef().isPresent()) {
        LValue lValue = edge.getSource().getDef().get();
        if (lValue instanceof Var lVar) {
            copy.remove(lVar);
        }
    }
    return copy;
}

• transferCallEdge

@Override
protected CPFact transferCallEdge(CallEdge<Stmt> edge, CPFact callSiteOut) {
    // TODO - finish me
    CPFact newCPFact = newInitialFact();
    JMethod callee = edge.getCallee();  // 被调用方法
    Stmt source = edge.getSource();
    if (source instanceof Invoke invoke) {
        InvokeExp invokeExp = invoke.getRValue();
        for (int i = 0; i < invokeExp.getArgCount(); i++) {
            Var actual = invokeExp.getArg(i);
            Value value = callSiteOut.get(actual);
            Var formal = callee.getIR().getParam(i);
            newCPFact.update(formal, value);
        }
    }
    return newCPFact;
}

• transferReturnEdge

@Override
protected CPFact transferReturnEdge(ReturnEdge<Stmt> edge, CPFact returnOut) {
    // TODO - finish me
    CPFact newCPFact = newInitialFact();
    Stmt callSite = edge.getCallSite();
    if (callSite.getDef().isPresent()) {
        Value value = Value.getUndef();  // 返回值
        for (Var returnVar : edge.getReturnVars()) {
            value = cp.meetValue(value, returnOut.get(returnVar));
        }
        LValue lValue = callSite.getDef().get();
        if (lValue instanceof Var lVar) {
            newCPFact.update(lVar, value);
        }
    }
    return newCPFact;
}

实现过程间 Worklist 求解器

• initialize

private void initialize() {
    // TODO - finish me
    for (Node node : icfg) {
        result.setInFact(node, analysis.newInitialFact());
        result.setOutFact(node, analysis.newInitialFact());
    }
    icfg.entryMethods().forEach(method -> {
        Node entryOf = icfg.getEntryOf(method);
        result.setOutFact(entryOf, analysis.newBoundaryFact(entryOf));
        result.setInFact(entryOf, analysis.newBoundaryFact(entryOf));
    });
}

• doSolve

private void doSolve() {
    // TODO - finish me
    workList = new ArrayDeque<>();
    for (Node node : icfg) {
        workList.add(node);
    }
    while (!workList.isEmpty()) {
        Node node = workList.poll();
        for (ICFGEdge<Node> nodeICFGEdge : icfg.getInEdgesOf(node)) {
            analysis.meetInto(analysis.transferEdge(nodeICFGEdge, result.getOutFact(nodeICFGEdge.getSource())), result.getInFact(node));
        }
        boolean f = analysis.transferNode(node, result.getInFact(node), result.getOutFact(node));
        if (f) {
            workList.addAll(icfg.getSuccsOf(node));
        }
    }
}

评测结果