
Function CreateInvariantRepresentation (ControlFlowGraph cfg
Function f)
// Control Flow Graph cfgis the CFG of the program
// Node f is the entry point of the give
Stack returnStack= <empty> // a stack of nodes in cfg
Stack entryPointStack = <empty> // a stack of nodes in cfg
List stripList = <empty> // the output list of strips.
Node epf = EntryPoint(f)
Push(epf, entryPointStack)
While entryPointStackis not empty do
ep = Pop(entryPointStack)
If ep has not been traversed then
strip = Traverse(ep, returnStack, entryPointStack)
Add( strip, stripList)
End if
End while
Return stripList
End function
Function Traverse (Node entry, InputOutput Stack returnStack,
InputOutput Stack entryPointStack )
List Strip = <empty> // output strip (list of instructions)
Node bb = entry, firstBB, secondBB
While bb is not <empty> do
// add basic block to strip
Foreach Instruction instr in BasicBlock(bb) do
Add(instr, Strip)
End foreach
Mark bb as traversed
// sechedule BBs at edges of bb
Bool firstIsCall = (Edge(bb, First) is a call)
firstBB = RetrieveNode(Edge(bb, First), returnStack)
If firstBB is not <empty> then
secondBB = RerieveNode(Edge(bb, Second), returnStack)
Else
firstBB = RetrieveNode(Edge(bb, Second), returnStack)
secondBB = <empty>
End if
If firstBB is not <empty> then
if secondBB is not <empty> then
// schedule second node. If this is a call edge, push
called function's entry point node on return stack
// else push node on entry point stack
Stack stack = firstIsCall? returnStack: entryPointStack;
Push(secondBB, stack)
End if
End if
bb = firstBB
End while
// reached a traversed node or end of function
Return strips
End function
Function RetrieveNode(Edge edge, InputOutput Stack returnStack)
Node retrievedBB = <empty>
If edge exists and is direct then
// continue traversing this function
retrievedBB = Node(edge)
Else if edge is a return instruction (e.g. ‘blr’ in POWER arch.) then
// traverse back to caller
retrievedBB = Pop(returnStack)
End if
// do not proceed in this direction if node has been traversed already
If retievedBB is not <empty> and retriebedBB is not traversed then
Return retrievedBB
Else
Return <empty>
End if
End function

An example strip follows. In the example, the branch instructions, which are not part of the strips, are commented out.


Strip 6:
#13b2b29c ...

#

41 86 00 48

beq-

cr1,13b2b2e4 <.pevm_EXECC+0x504>

#13b2b2e4 ...

	e8 7d 00 08	ld	r3,8(r29)
	28 9b 05 7b	cmplwi	cr1,r27,1403
	e8 63 00 c8	ld	r3,200(r3)
	80 03 00 9c	lwz	r0,156(r3)
	70 00 00 40	andi.	r0,r0,64
#	41 82 00 14	beq-	13b2b30c <.pevm_EXECC+0x52c>

#13b2b30c ...

	a0 1c 00 34	lhz	r0,52(r28)
	70 03 00 40	andi.	r3,r0,64
#	40 82 00 34	bne-	13b2b348 <.pevm_EXECC+0x568>
	80 bc 00 50	lwz	r5,80(r28)
	e8 dc 00 56	lwa	r6,84(r28)
	e8 7d 00 08	ld	r3,8(r29)
	e8 9d 00 88	ld	r4,136(r29)
	39 20 00 00	li	r9,0
	e8 63 00 00	ld	r3,0(r3)
	38 e0 00 00	li	r7,0
	39 00 00 00	li	r8,0
	e8 84 00 00	ld	r4,0(r4)
#	4b 9f ed 45	bl	1352a080 <.kgicls>
	60 00 00 00	nop
	a0 1c 00 34	lhz	r0,52(r28)
	54 00 04 3c	rlwinm	r0,r0,0,16,30
	80 7c 00 58	lwz	r3,88(r28)
	2c 23 00 00	cmpdi	r3,0
	b0 1c 00 34	sth	r0,52(r28)
#	41 82 00 0c	beq-	13b2b364 <.pevm_EXECC+0x584>

#13b2b364 ...

	7f a3 eb 78	mr	r3,r29
	7f 64 db 78	mr	r4,r27
#	4b fe 8b b5	bl	13b13f20 <.pevm_handle_external_error>
	60 00 00 00	nop
#	48 00 01 34	b	13b2b4a8 <.pevm_EXECC+0x6c8>

Strip 7:

#13b2b35c ...

	e8 7d 00 b0	ld	r3,176(r29)
	93 c3 00 98	stw	r30,152(r3)

Strip 8:

#13b2b2fc ...

#	40 86 00 10	bne-	cr1,13b2b30c <.pevm_EXECC+0x52c>
	7f a3 eb 78	mr	r3,r29
#	4b fe 9e 9d	bl	13b151a0 <.pfrfoe_flush_oci_error>
	60 00 00 00	nop

At108, the generated strips of two implementations of a function are compared. The comparison can be a textual or character-by-character comparison. Incorrect transformations are identified from the comparison. For example, the strip or strips corresponding to the transformed or optimized code that do not match the strip or strips of the original code are identified as being incorrect.

The system and method of the present disclosure may be implemented and run on a general-purpose computer or computer system. The computer system may be any type of known or will be known systems and may typically include a processor, memory device, a storage device, input/output devices, internal buses, and/or a communications interface for communicating with other computer systems in conjunction with communication hardware and software, etc.

The terms “computer system” and “computer network” as may be used in the present application may include a variety of combinations of fixed and/or portable computer hardware, software, peripherals, and storage devices. The computer system may include a plurality of individual components that are networked or otherwise linked to perform collaboratively, or may include one or more stand-alone components. The hardware and software components of the computer system of the present application may include and may be included within fixed and portable devices such as desktop, laptop, and server. A module may be a component of a device, software, program, or system that implements some “functionality”, which can be embodied as software, hardware, firmware, electronic circuitry, or etc.

The embodiments described above are illustrative examples and it should not be construed that the present invention is limited to these particular embodiments. Thus, various changes and modifications may be effected by one skilled in the art without departing from the spirit or scope of the invention as defined in the appended claims.