Skip to content

Extensions

Jump to bottom
florafong97 edited this page Apr 14, 2019 · 17 revisions

Extensions

For extensions, we implemented the inter-procedural NextBip, NextBip*, AffectsBip and AffctsBip*. These inter-procedural relationships gives a more accurate picture of the program path and how impact of assignment statements propogate throughout the SIMPLE program.

The generalized CFGBip was implemented as the underlying data structure for the above relations, which means there could be one or more calls to a procedure. Although this is harder to implement as compared to the simplified CFGBip, we still chose to use it since it allows for analysis of more types of programs.

The two proposed implementation for CFGBip were by graph explosion and with labelled edges.

Considerations CFGBip by graph explosion CFGBip with labelled edges Importance of Consideration
Space complexity Increases exponentially as number of calls increases Takes up same amount of space as original CFG Since we have unlimited space, this is not the main cause for concern
Ease of implementation Harder to implement: Have to do via recursion, or reverse topological sort to start building CFGBip from procedure that is not called Easier to implement: Iterate through Next edges and add Branch Ins with call statements and Branch Backs directly Limited time in this iteration makes this an important consideration
Ability to work with multiple inter-procedural relations All relations will be able to work on it AffectsBip* would only work on single call assumption as Affects* runs on modified Transitive Closure, which would not take labelled edges into account Important since implementing another alogrithm for another relation will take up more time

In the end, we went with CFGBip with labelled edges as we have limited time. So we decided to take the trade off of general AffectsBip* for an easier implementation for the other relations.

Generalized CFGBip with labelled edges

Construction of CFGBip:

  1. Get Next relations from PKB and iterate through through all edges in the Table SIMPLE code example and corresponding CFGs showing Next relations

NOTE

We define 3 sets of edges that exists in CFGBip:

  • Control Flow Link: Between two statements such that Next(s1, s2) is true
  • Branch In: Between a call statement c and first statement of called procedure
  • Branch Back: Between last executed statement (exit statement) in called procedure and statement control flows return to after execution of called procedure is done

  1. For every pair of edges (n, m) such that Next(n,m) is true,

  2. Depending on whether n is a call statement, we do the following.

Case 1: n is not a call statement

Add a Control Flow Link between n and m similar to Next relations Adding Control Flow Link to CFGBip when n is not a call statement

Case 2: n is a call statement

Add a Branch In between call statement and called procedure P with corresponding labels Adding Branch Ins with labels to CFGBip when n is a call statement with labels

Add Branch Backs with corresponding labels from exit statement in P to statement control flows return to after P finished executing.

If exit statement of procedure is a call statement, add a dummy node and relevant Branch Backs to it. Adding Branch Backs with labels to CFGBip when n is a call statement to achieve final CFGBip (removed control flow link shown for clarity)

Inter-procedural NextBip and NextBip*

Relationship NextBip defines control flow across all procedures in the whole SPA program

For two program lines n1 and n2 in the same or different procedures,

  • NextBip(n1, n2) holds if n2 can be executed immediately after n1 in some execution sequence.
  • NextBip*(n1, n2) holds if n2 can be executed after n1 in some execution sequence.

Implementation

NextBip

NextBip uses a truncated BFS algorithm to find the next immediate executed statement. Traverse the CFGBip as shown above from every statement number S.

When another statement number T is reached, we add the result (S, T) to the nextBip table. Unlike the regular BFS algorithm, we do not add T to the queue as we only want to find the statements that are executed immediately after S.

When a dummy node is reached, we add the dummy node to the queue and continue BFS traversal until we reach a statement number if it exists and the algorithm terminates. This follows the definition that NextBip(n1, nk) holds if there is a chain of nodes n1 -> n2 ... -> nk in CFGBip and n2..nk-1 are dummy nodes.

NextBip*

NextBip* is similar to Next* in the way it traverses the CFGBip with the modified BFS algorithm defined in Next* section above. A stack is introduced to keep track of the current traversal path so that it takes the correct Branch Backs out of the exit statement of called procedure.

At an exit statement with multiple Branch Backs, only the edge that contains a label that corresponds to the top of the stack would be taken.

  • Eg: With the CFGBip above, when we start traversal at 4, we push 4 into the stack. When the algorithm reaches 10, it would take the Branch Back with the label 4, add 5 to the queue and pop 4 from the stack.

If the stack is empty, all Branch Back paths are taken since no procedure Branch Ins are specified.

  • Eg: When we start traversal t 10, we add both dummy node and 5 to the queue as the stack is empty and no Branch Ins are specified.

Another modification of the BFS algorithm that is only specific to NextBip* is the case when a Branch In goes to a procedure that was already visited.

  • Eg: If we start traversal at 2, when the control path returns to 3, all statements in procedure B and C would already be visited. When control path moves on to 4, it would not visit procedure C again.

This would exclude the Branch Back from 10 to 4 and consqeuently statement 5 from the result which is an error. This is because previously when procedure C was processed, it was branched in from call statement 8, so the Branch Back for 4 was ignored.

Thus, when a Branch In goes into a procedure that was already visited, it would skip to the exit statment and add the correspondin Branch Back to the queue.

  • Eg: At 4, since C was already visited, we skip to the exit statement (10) and add 5 to the queue.

Inter-procedural AffectsBip and AffectsBip*

  • AffectsBip(a1, a2) holds if:
    • a1 and a2 are in the same or different procedures
    • a1 modifies a variable v which is used in a2
    • There is a control flow path from a1 to a2 on such that v is not modified (as defined by Modifies relationship) in any assignment, read, or procedure call statement onthat path
  • AffectsBip*(a1,a2) holds if:
    • AffectsBip(a1, a2) or
    • AffectsBip(a1, a) and AffectsBip*(a, a2) for some assignment a

Implementation

AffectsBip

AffectsBip is similar to NextBip* the way Affects is similar to Next*. AffectsBip will follow the algorithm of Affects but instead run this modified BFS traveral as described above on CFGBip

AffectsBip*

AffectsBip* currently works only under single call assumption on the simplified CFGBip as definied in SPA handout. Simplified AffectsBip* works on transitive closure on AffectsBip table. Since it is under single call assumption, there would only be one Branch In and one Branch Back for each called procedure, so it does not have to differentiate which Branch Back to take.

PQL Grammar for Inter-procedural relations *

To support querying of the above relations, the PQL Grammar should be extended as follows:

relRef: ModifiesP | ModifiesS | UsesP | UsesS | Calls | CallsT | Parent | ParentT | Follows | FollowsT | Next | NextT | Affects | AffectsT | NextBip | NextBipT | AffectsBip | AffectsBipT
NextBip : ‘NextBip’ ‘(’ lineRef ‘,’ lineRef ‘)’

NextBipT : ‘NextBip*’ ‘(’ lineRef ‘,’ lineRef ‘)’

AffectsBip : ‘AffectsBip’ ‘(’ stmtRef ‘,’ stmtRef ‘)’

AffectsBipT : ‘AffectsBip*’ ‘(’ stmtRef ‘,’ stmtRef ‘)’

Problems

As mentioned before, due to our Affects* algorithm running on a modified Transitive Closure, AffectsBip* would not work on generalized CFGBip. Thus only our AffectsBip* work under single call assumption.

Our extensions and problems does not affect the other full SPA components

Testing

Unit Tests

Test 1
TEST_CASE("Two procedures calling same procedure ending with call statement") {
	std::unique_ptr<PKB> pkb{ new PKB() };
	pkb->setProc("A", 1, 4);
	pkb->setProc("B", 4, 6);
	pkb->setProc("C", 6, 8);
	pkb->setProc("D", 8, 11);

	pkb->setNext(1, 2);
	pkb->setNext(2, 3);
	pkb->setNext(4, 5);
	pkb->setNext(6, 7);
	pkb->setNext(8, 9);
	pkb->setNext(9, 10);
	pkb->setStmtType(2, StatementType::Call);
	pkb->setCallProcName(2, "B");
	pkb->setStmtType(5, StatementType::Call);
	pkb->setCallProcName(5, "C");
	pkb->setStmtType(9, StatementType::Call);
	pkb->setCallProcName(9, "B");
	pkb->setProcExitStmt("A", std::vector<int> {3});
	pkb->setProcExitStmt("B", std::vector<int> {5});
	pkb->setProcExitStmt("C", std::vector<int> {7});
	pkb->setProcExitStmt("D", std::vector<int> {10});
	DesignExtractor::populateDesigns(pkb);

	//testing nextBip
	Table result = pkb->getNextBip();
	REQUIRE(result.size() == 9);
	REQUIRE(result.contains({ "1", "2" }));
	REQUIRE(result.contains({ "2", "4" }));
	REQUIRE(result.contains({ "4", "5" }));
	REQUIRE(result.contains({ "5", "6" }));
	REQUIRE(result.contains({ "6", "7" }));
	REQUIRE(result.contains({ "7", "3" }));
	REQUIRE(result.contains({ "8", "9" }));
	REQUIRE(result.contains({ "9", "4" }));
	REQUIRE(result.contains({ "7", "10" }));

	//testing nextBipT
	result = pkb->getNextBipT();
	REQUIRE(result.size() == 36);
	REQUIRE(result.contains({ "1", "2" }));
	REQUIRE(result.contains({ "1", "3" }));
	REQUIRE(result.contains({ "1", "4" }));
	REQUIRE(result.contains({ "1", "5" }));
	REQUIRE(result.contains({ "1", "6" }));
	REQUIRE(result.contains({ "1", "7" }));
	REQUIRE(result.contains({ "2", "3" }));
	REQUIRE(result.contains({ "2", "4" }));
	REQUIRE(result.contains({ "2", "5" }));
	REQUIRE(result.contains({ "2", "6" }));
	REQUIRE(result.contains({ "2", "7" }));
	REQUIRE(result.contains({ "4", "5" }));
	REQUIRE(result.contains({ "4", "6" }));
	REQUIRE(result.contains({ "4", "7" }));
	REQUIRE(result.contains({ "4", "3" }));
	REQUIRE(result.contains({ "4", "10" }));
	REQUIRE(result.contains({ "5", "3" }));
	REQUIRE(result.contains({ "5", "6" }));
	REQUIRE(result.contains({ "5", "7" }));
	REQUIRE(result.contains({ "5", "10" }));
	REQUIRE(result.contains({ "6", "3" }));
	REQUIRE(result.contains({ "6", "7" }));
	REQUIRE(result.contains({ "6", "10" }));
	REQUIRE(result.contains({ "7", "3" }));
	REQUIRE(result.contains({ "7", "10" }));
	REQUIRE(result.contains({ "8", "4" }));
	REQUIRE(result.contains({ "8", "5" }));
	REQUIRE(result.contains({ "8", "6" }));
	REQUIRE(result.contains({ "8", "7" }));
	REQUIRE(result.contains({ "8", "9" }));
	REQUIRE(result.contains({ "8", "10" }));
	REQUIRE(result.contains({ "9", "4" }));
	REQUIRE(result.contains({ "9", "5" }));
	REQUIRE(result.contains({ "9", "6" }));
	REQUIRE(result.contains({ "9", "7" }));
	REQUIRE(result.contains({ "9", "10" }));


}

Test Purpose: Ensure that NextBip and NextBip* are computed correctly with dummy nodes and multiple labelled edges.

Required Test Inputs: A PKB stub that stores knowledge of some source program.

Expected Test Results: All the Next and Next* relations are populated correctly as per the lines with REQUIRE in the above code snippet.

Test 2
TEST_CASE("One call in if statement list and one call in else statement list") {
	std::unique_ptr<PKB> pkb{ new PKB() };
	pkb->setProc("A", 1, 5);
	pkb->setProc("B", 5, 7);
	pkb->setProc("C", 7, 9);
	pkb->setNext(1, 2);
	pkb->setNext(1, 3);
	pkb->setNext(2, 4);
	pkb->setNext(3, 4);
	pkb->setNext(5, 6);
	pkb->setNext(7, 8);
	pkb->setStmtType(1, StatementType::If);
	pkb->setStmtType(2, StatementType::Call);
	pkb->setStmtType(3, StatementType::Call);
	pkb->setProcExitStmt("A", std::vector<int> {4});
	pkb->setProcExitStmt("B", std::vector<int> {6});
	pkb->setProcExitStmt("C", std::vector<int> {8});
	pkb->setStmtType(4, StatementType::Assign);
	pkb->setModifies(4, "w");
	pkb->setUses(4, "x");
	pkb->setStmtType(5, StatementType::Assign);
	pkb->setModifies(5, "y");
	pkb->setUses(5, "x");
	pkb->setStmtType(6, StatementType::Assign);
	pkb->setModifies(6, "x");
	pkb->setUses(6, "y");
	pkb->setStmtType(7, StatementType::Assign);
	pkb->setModifies(7, "z");
	pkb->setUses(7, "x");
	pkb->setStmtType(8, StatementType::Assign);
	pkb->setModifies(8, "x");

	WHEN("both calls same method") {
		pkb->setCallProcName(2, "B");
		pkb->setCallProcName(3, "B");

		DesignExtractor::populateDesigns(pkb);

		//testing affectsbip
		result = pkb->getAffectsBip();
		REQUIRE(result.size() == 2);
		REQUIRE(result.contains({ "6", "4" }));
		REQUIRE(result.contains({ "5", "6" }));

	}

	WHEN("both calls different method") {
		pkb->setCallProcName(2, "B");
		pkb->setCallProcName(3, "C");

		DesignExtractor::populateDesigns(pkb);

		//testing affectsbip
		result = pkb->getAffectsBip();
		REQUIRE(result.size() == 3);
		REQUIRE(result.contains({ "6", "4" }));
		REQUIRE(result.contains({ "8", "4" }));
		REQUIRE(result.contains({ "5", "6" }));

	}
}

Test Purpose: Ensure that AffectsBip are computed correctly under both single call and multiple call assumptions with multiple labelled edges.

Required Test Inputs: A PKB stub that stores knowledge of some source program.

Expected Test Results: All the Affects relations are populated correctly as per the lines with REQUIRE in the above code snippet.

Note: AffectsBip* is not tested as transitive closure was already tested in other unit tests

System Test

The testing process is done using the Autotester for automated testing. The tables below are the test strategies.

No. Test Strategy
1 Test specific to verify computation of NextBip, NextBip* and AffectsBip* relations
2 Test specific to verify population of relations in different nesting types (if nested in while, while nested in while, or others with more nesting levels)
3 Test specific to verify computations on procedure with multiple calls

SIMPLE source

procedure A {
    x = 1; \\1
    if (x > 0) then { \\2
        y = x + z; \\3
    } else {
        while (x < 0) { \\4
            x = x + 1; \\5
            call C; \\6
        }
        i = x + y; \\7
        call B; \\8
    }
}

procedure B {
    while (z < y) { \\9
        x = y + z - x; \\10
        read y; \\11
        while (x > 0) { \\12
            call C; \\13
        }
    }
    if (y > 0) then { \\14
        if (z > 1) then { \\15
            call C; \\16
        } else {
            x = x - 1; \\17
        }
    } else {
        if (y < 1) then { \\18
            x = y + z; \\19
        } else {
	    x = y + 1;
	}
    }
}

procedure C {
    if (x > 0) then { \\20
        x = 1; \\21
    } else {
        print x; \\22
    }
}

SIMPLE Queries

Test Purpose: As multiple types of returns and clauses are already tested in other system tests, the queries are focused on just basic correctness of extensions.

stmt s1,s2;

1) Select BOOLEAN such that NextBip (1, 15);
2) Select s1 such that NextBip(12, s)
3) Select s1 such that NextBip(s1, 15)
4) Select s1 such that NextBip*(s1, 4);
5) Select s1, s2 such that NextBip*(s1, s2)
6) Select s1 such that AffectsBip(s1, 1);
7) Select s1 such that AffectsBip(2, s1);
8) Select s1, s2 such that AffectsBip(s1, s2)

Clone this wiki locally