Method and apparatus for identifying and removing unused software procedures

Abstract

The present invention is a method and apparatus for identifying and removing unused software procedures from computer software loads at loadbuild time, and includes a compiler, linker, and other software loadbuild tools. The compiler has been adapted by the invention to define identify procedures that are unused by a software load by identifying all procedure calls, entry points, and required procedures in each module used by the software load and to incorporate this information into link records. Based on the information contained in the link records, a linker creates a temporal data structure referred to as a call graph that depicts the operational flow of the software load. The linker processes the call graph and determines those procedures that are called, and thus those procedures that are not called by a software load. The linker or other loadbuilding tool is adapted to remove each "not called" procedure from the linked files while maintaining the integrity of the procedure directories by using several different procedure shell methods or by using tombstone values in the procedure directories.

Claims

What is claimed is:

1. In a system for building a software load including starting with software modules containing procedures comprised of software code, compiling the modules and linking them to form the software load of linked sections each containing procedures and a procedure directory for providing access to the procedures, a method of identifying and removing unused software procedures from the software load, the method comprising:

a) defining each procedure in said modules;

b) defining each entry point of said software load;

c) defining each procedure call instruction of said modules;

d) defining all required procedures of said software load;

e) forming a link record for each said module comprising each said defined procedure, entry point, procedure call instruction; and required procedure;

f) creating a call graph of said software load;

g) creating a procedure management table;

h) processing said call graph to identify all called procedures of each module;

i) identifying all remaining procedures as not called in said procedure management table; and

j) rewriting, during linking of said modules to form linked segments, said segment to remove said not called procedures to form said software load having a reduced memory footprint.

2. A method for identifying and removing unused software procedures as recited in claim 1, wherein rewriting said not called procedures during building of said software load further comprising removing the computer code and leaving the header and trailer of each said not called procedures to form a procedure shell for each said not called procedure of each said segment.

3. A method for identifying and removing unused software procedures as recited in claim 1, wherein removing said not called procedures during building of said software load further comprises removing the computer code and leaving the header and trailer of each not called procedure, and replacing said computer code of each not called procedure with sufficient space so that each not called procedure can be patched back in.

4. A method for identifying and removing unused software procedures as recited in claim 1, wherein removing said not called procedures during building of said software load further comprises removing all not called procedures and placing a tombstone value in said procedure directory in said procedure entry locations corresponding to each said not called procedures so as to maintain the integrity of said procedure directory, wherein the use of a tombstone value optimizes memory recovery.

5. A method for identifying and removing unused software procedures as recited in claim 1, wherein removing said not called procedures during building of said software load further comprises forming one procedure shell for all not called procedures for each said segment.

6. A method for identifying and removing unused software procedures as recited in claim 5, wherein removing said not called procedures during building of said software load further comprises leaving in said procedure shell sufficient space so that one not called procedure can be patched back in.

7. A method for identifying and removing unused software procedures as recited in claim 4, wherein removing said not called procedures during building of said software load further comprises using the value zero(0) for the tombstone value.

8. An apparatus for building a software load based on software modules containing procedures, procedure call instructions, and entry points to the software load, the software load containing linked segments, comprising:

a) a linker comprising:

i) means for defining each said procedure in said modules;

ii) means for defining each said entry point of said software load;

iii) means for defining each said procedure call instruction of said modules;

iv) means for defining all required procedures of said software load; and

v) means for forming a link record for each said module comprising each said defined procedure, entry point, procedure call instruction; and required procedure; and

b) means for linking said modules comprising;

i) means for creating a call graph of said software load;

ii) means for creating a procedure management table;

iii) means for processing said call graph to identify all called procedures of each said segment;

iv) means for identifying all remaining procedures as not called in said procedure management table; and

v) means for rewriting, during linking of said modules to form said linked segments, said segment to remove said not called procedures to form said software load having a reduced memory footprint.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a method and apparatus for reducing the memory requirements of software loads, in particular, a method and apparatus for the identification and removal of unused procedures and use of procedure shells to maintain the integrity of the procedure table during computer software loadbuilding time.

2. Description of the Problem Solved

In the telephonic industry, consumer demand for additional telephonic functionality increases the software load on the telephonic computer hardware designated to execute such loads. The increase in software load decreases the remaining life of the computer hardware. At some point, the computer hardware cannot handle additional functionality and a telephonic vendor has to stop delivery of features, upgrade the hardware, or reduce the load while maintaining increased functionality. Thus, there is a need to provide computer software for increasing the software load capacity on telephonic computer hardware. Such computer software should extend the life of telephone switch hardware by reducing the hardware memory requirement of telephone switch software, and also reduce the memory requirement of computer software of Extended Peripheral Modules (XPMs). XPMS are the telephony hardware that implement many of the various telephony computer software applications. For example, XPMs can collect digits, link different telecompanies and private networks, track data, manage communication between trunks, manage residential telephone lines, and control telephone tone generation, as well as handling such software driven applications as speed dialing. The present invention relates to computer software and a method for preserving computer memory by recognizing those computer program procedures not used in a particular software load and then removing them during loadbuilding.

The term "loadbuilding" is used herein to refer to the compiling and linking of computer code to produce the final software load. The term "software load" is used herein to refer to the final computer software that is executed by computer hardware for a particular application. A software load is developed from high-level computer language referred to as source code. The source code file of a software load is compiled by one of a number of compilers as are well known in the field to produce an object code file. Object code files are linked together by a linker to produce the software load, which can then be executed by the machine (computer hardware such as a XPM or PC). In particular applications, the source code, for example, written in Pascal, is compiled into an intermediate language identified as pcode. Xysco.TM., a software building tool developed by Nortel, takes the link code file and converts time critical sections from pcode to object code.

Software loads are comprised of modules. A module is a portion of a software load that carries out a specific function and may be used alone or with other modules. Within each module are self-contained blocks of software called procedures. If a particular application or load requires a procedure in a particular module, the linker pulls in the entire module, along with all procedures contained in the module. By way of example, FIG. 1 illustrates three modules A, B, and C. Each module contains three procedures: ap1, ap2, and ap3; bp1, bp2, and bp3; and cp1, cp2, and cp3, respectively. It is understood that modules can contain substantially more than three procedures.

Referring again to FIG. 1, if software load L1 requires ap1, bp2, and cp2, a compiler would first compile source code to object code and then a linker or other suitable software building tool would link together the modules containing these procedures into software load L1, i.e., would place into L1 each module A, B, and C and all procedures contained therein. Similarly, software load L2 requires ap2, bp3, and cp3. Again, during loadbuilding, the linker would link together the modules containing these procedures to form software load L2, i.e., would place into L2 each module A, B, and C and all procedures contained therein. Despite the different procedures required by software loads L1 and L2 and despite each not needing all of the procedures contained in modules A, B, and C, during loadbuilding, the traditional linker links together all three modules A, B, and C, and all procedures contained therein to form software loads L1 and L2. Clearly, when building software loads, presently used linkers will create loads that take up valuable computer hardware memory for procedures that are not implemented when the load is executed. (The computer memory used by a particular software load is referred to herein as a "memory footprint.")

The present invention recognizes that it would be advantageous to, during this software loadbuilding process, for compilers, linkers, and other software loadbuilding tools such as Xsyco.TM. to identify the procedures that are not used in the final software load and remove them, thereby creating a smaller computer memory footprint having the same functionality as the software load built using traditional compilers, linkers, and other software building tools.

With the foregoing in mind, it becomes a general object of the present invention to extend the service life of hardware by removing unused procedures from a software load resident on such hardware.

It is another object of the present invention to recognize unused procedures contained within modules used to build particular software loads.

It is a further object of the present invention to define all procedures, all required procedures, and entry points within each module.

It is yet another object of the invention to remove unused procedures during the loadbuilding process.

It is a further object of the invention to use procedure shells to maintain the integrity of each linked segment and corresponding procedure directories.

It is an object of the invention to use a placeholder, or tombstone, in the procedure directory to maintain the integrity of the procedure directory.

SUMMARY OF THE INVENTION

The present invention solves the above problems by providing a method and apparatus for identifying and removing unused procedures from computer software loads, while maintaining the integrity of the procedure directory, at loadbuild time, and includes a compiler, linker, and other software loadbuild tools. The compiler is adapted to define all procedures contained within software modules and to incorporate them into module link records. The compiler is further adapted to identify all module procedure calls, entry points into the software load, and required procedures, and to create call and required procedure lists to also incorporate into link records. Based on the information contained in the link records, the linker of the present invention creates a temporal data structure referred to as a call graph and a procedure management table that records the operational flow of the software load and the "call"/"not called" status of each procedure contained in the link record. To determine the procedures that are unused ("not called") by a software load, the linker initially sets the status of each procedure of each module used by the software load to "not called", and goes through a call graph processing method to determine which procedures are actually "called" by the software load, updating the procedure management table as it proceeds through the call graph processing method. Once the linker completes the call graph processing operation, the procedure management table has identified the procedures that are "called" by a particular software load. The remaining procedures are "not called" and are, thus, recognized by the linker as those procedures to remove from the software load. The present invention removes each "not called" procedure from the linked files while maintaining the integrity of the procedure tables by using one of several different procedure shell methods or by using what is referred to herein as the tombstone method.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a functional block diagram showing the form, compilation of modules A, B, and C, main1, and main2 from source code files to object code files and linking of object code files to form main1 and main2 software loads.

FIG. 2 is a functional block block diagram showing the form of modules 1, 2, 3, main1, and main2 and the procedures contained therein.

FIG. 3 illustrates in block diagram form an exploded view of segment 2 and procedure 4 of linked software load main1.

FIG. 4 illustrates in block diagram form the removal of unused procedures from segment 2 of software load main1 in accordance with the empty procedure shell method of the present invention.

FIG. 5 illustrates in block diagram form the removal of unused procedures from segment 2 of software load main1 in accordance with the extended procedure shell method of the present invention.

FIG. 6 illustrates in block diagram form the removal of unused procedures from segment 2 of software load main1 in accordance with the single procedure shell method of the present invention.

FIGS. 7A, 7B, 8A, and 8B show in block diagram form the removal of unused procedures from segment 2 of software load main1 in accordance with the tombstone method of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT OF THE INVENTION

The present invention identifies and removes unused procedures from computer software loads. In the preferred embodiment, the present invention is used to remove unused procedures from the Pascal component of XPM loads at the loadbuild time. However, it is understood that the present invention can be used during software loadbuilding time as a general software code size reduction method.

1. Identification of Unused Procedures

The particular unused procedures that are targeted for removal at loadbuild time, in accordance with the present invention, depend on the particular load being built. It is recognized by the present invention that the list of unused procedures is different for each load, and that it is therefore necessary to identify the particular set of unused procedures at link time. First, however, the compiler must generate information for the linker. Traditionally, compilers only identify and pass to the linker a module's procedures that are called or referenced by other modules, and do not identify for the linker procedures that are strictly confined to the module. The present invention recognizes that in order to identify and remove unused procedures, every procedure in a module must be defined for the linker. To accomplish this task, the present invention adds unique computer code to the compiler that, upon execution, looks for and defines each procedure contained in a software program module, and incorporates the defined procedures into a link record.

It is further recognized by the present invention that in order to identify all unused procedures in a final software load, all procedure calls and entry points within each module must also be identified. An entry point refers to a procedure that is the doorway or start of the execution for the software load. There may be more than one entry point for each software load. Load entry points would include: (1) all segment initialization procedures; (2) an initiated task; (3) all handlers for an initiated task; and (4) any procedure exported to C++. The above set of entry point procedures would also include procedures called by these entry procedures or bound via procedure variants in these procedures. During the compilation, the compiler looks for and identifies all procedure calls and entry points within each module and incorporates a procedure call list for each such module into the link record.

It is also recognized by the present invention that most software loads require procedures that are not called by a particular module. These procedures are referred to herein as "required procedures." The compiler of the present invention includes unique computer code that enables the compiler to look for these required procedures. Required procedures can be identified, as shown in FIG. 2 as those files that the programmer has previously associated with the mark{$k}. For example, procedure 2p5 is marked as a required procedure. Additional required procedures also include, but may not be limited to, the following: 1) those not referenced in the load but called by the operating system or loader (e.g. the STAC procedure of the COMPRESS module, or the initialization procedure); and, 2) those reserved for later use (e.g. procedures reserved for patching). Software code of the compiler present invention, when executed would add each required procedure to link record.

In summary, to initiate the process for identifying those procedures that are unused by a particular software load, the compiler of the present invention: (1) looks for and defines each procedure contained in a software program module and generates a definitions list of all such procedures; (2) looks for all calls and entry points within the module and generates a call list for that module; (3) looks for all required procedures contained in the module and generates a list of such calls, and (4) creates link records for each module containing the defined procedures, call list, entry points, and required procedures list for processing by the linker.

By way of example, FIG. 2, depicts each module 1, 2, 3, main1, and main2, each containing procedures, and indicates those procedures that are required and called as follows. Module 1 contains procedures 1p1, 1p2, 1p3, and 1p4. FIG. 2 shows that procedure 1p4 calls 1p3. Module 2 contains procedures 2p1, 2p2, 2p3, 2p4, and 2p5. Module 2 shows that procedures 2p1, 2p3, and 2p4 call procedures 1p2, 2p2, and 2p3 respectively. Procedure 2p5 is shown as a required procedure of module 2 by the mark {$k} FIG. 2 further shows that module 3 contains procedures 3p1, 3p2, 3p3, and 3p4 and that procedure 3p1 calls 2p1, procedure 3p2 calls 1p1, procedure 3p3 calls two procedures, 3p1 and 1p2, and procedure 3p4 calls 2p3. Finally, main1 calls 3p3, 2p2, and 1p4, and main2 calls 3p4, 2p5, 2p4, and 3p2.

The compiler of the invention creates link records for each module as follows:

Module 1

Defines 1p1

Defines 1p2

Defines 1p3

Defines 1p4

1p4 calls 1p3

Module 2

Defines 2p1

Defines 2p2

Defines 2p3

Defines 2p4

Defines 2p5

2p1 calls 1p2

2p3 calls 2p2

2p4 calls 2p3

Required 2p5

Module 3

Defines 3p1

Defines 3p2

Defines 3p3

Defines 3p4

3p1 calls 2p1

3p2 calls 1p1

3p3 calls 3p1

3p3 calls 1p2

3p4 calls 2p3

Main1

Defines main

main calls 3p3

main calls 2p2

main calls 1p4

Required main

Main2

Defines main

main calls 3p4

main calls 2p5

main calls 2p4

main calls 3p2

Required main

The linker processes the link records created by the compiler and creates a temporal data structure referred to as a call graph. The call graph is referred to as "temporal" because it is not carried through and incorporated into the final software load. Call graphs show the operational flow of the software load. The call graph includes a node for each procedure contained in the link records. Each node contains the following information:

1. the module where the procedure is defined;

2. procedure name and number;

3 whether the procedure is required;

4. status (called, not called); and

5. list of callees.

The linker also creates a procedure management table, which consists of information from each procedure node for each module. The structure of the procedure management table is clearly set forth below. In the preferred embodiment of the invention, to determine which procedures are called, the following definitions and instructions are used by the linker of the invention, which definitions and instructions are included by way of example only.

called_proc_node_ptr= called_proc_node;

called_proc_node=record

called_proc: pm_proc_id; {segment #/procedure#}

next: called_proc_node_ptr;

end; {called_proc_node}

pm_call_status={pm_not_called, pm_called, pm_reprocessed; pm_removed);

pm_proc_type=(pm_unknown_proc, pm_asm_proc, pm_pcode_proc);

pm_mgmt_rec=record

{NOTE: proc num is determined by the cell-index.}

proc_name: alpha;

call status: pm_call_status;

called_procs : called_proc_note_ptr; {list of called procedures}

end; {pm_mgmt_rec}

Initially, the linker sets the status of each procedure to "not called." Once the linker determines that the procedure is called, it changes its status from "not called" to "called." In accordance with the call graph processing operation of the invention, the linker looks to the link records (as set forth above) for required procedures, and finds procedure 2p5 as a member of required list, and changes the status of the required procedure 2p5 from "not called" to "called" in the procedure management table. The linker then looks at 2p5's call list and determines that 2p5 does not call any procedures. The linker finds itself at the end of the 2p5's call list and its first call-processing loop, and begins its second loop by processing main program 1 from the required list.

The linker marks main1 as "called" and refers to the main1 procedure management table and finds that 3p3 is first listed on main1's call list. Linker then changes the status of 3p3 from "not called" to "called," and determines from the procedure management table whether 3p3 has a called list. If it does, it goes to the first called procedure in 3p3's called list, which is 3p1. The linker modifies the procedure management table by changing the status of 3p1 from "not called" to "called." Next, the procedure determines if 3p1 has a called list. If it does, it goes to the first called procedure in 3p1's called list, which is 2p1. The linker modifies the procedure management table by changing the status of 2p1 from "not called" to "called." The linker then determines that 2p1 calls 1p2, marks 1p2 as "called," and discovers that 1p2 does not have a called list, reaching the end of that particular branch of the call graph, whereupon it starts the third loop through the call graph processing.

The linker works itself back to 2p1 to determine if 2p1 has any more procedures in its call list, other than 1p2, which was processed in the second loop of the process. It determines that it does not and ends the third loop without marking any other procedures as "called."

In the fourth loop of the process, the linker works back to the 3p1 call list, and finds that there are no further calls, as 2p1 has already been processed and its status changed from "not called" to "called." It works further back and takes the next called procedure from 3p3 call list, which is 1p2. However, 1p2 has already been marked as called, and the loop is terminated.

The fifth loop essentially asks the question if there are any called procedures of 3p3 beyond ip2, and finds that there are none. At this point, the linker will again work back in the following sixth loop to main1 call list to see if there is a called procedure beyond the first called procedure 3p3, which is 2p2. In the sixth loop the process marks 2p2 as called, and traverses the call list for 2p2, and finds no called procedures.

In the last iteration, the linker processes the next called procedure of main1, which is 1p4, changes the status of 1p4 in the procedure management table from "not called" to "called," and traverses 1p4 call list to find 1p3 is called. The linker marks 1p3 as called, and traverses 2p3's call list to find no called procedures, thereby terminating the call graph processing operation of main1 . Importantly, the call graph processing operation of the invention is very efficient, because when a procedure has already been marked as "called," the entire call graph branch behind that already "called" procedure does not have to be processed later during the call graph processing operation, even if it is called within a different call graph branch. Thus, the further along in the call graph processing operation, the less processing that has to be done, because many of the procedures called in the operational flow of the software load, have been called, and thus processed earlier by the call graph processing operation of the invention. By way of further illustration of the above call graph processing operation, the linker loops through the above link records for modules 1-3 and main1 as follows. First illustrated is the call management table as it appears before the call graph processing of the invention.

     Procedure Management Table before Call Graph Processing
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           not called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           not called    1p2
                    2p2           not called
                    2p3           not called    2p3
                    2p4           not called    2p3
                    2p5           not called
           3        3p1           not called    2p1
                    3p2           not called    1p1
                    3p3           not called    3p1, 1p4
                    3p4           not called    2p3
         main1      main1         not called    3p3, 2p2, 1p4

           Procedure Management Table after First Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           not called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           not called    1p2
                    2p2           not called
                    2p3           not called    2p3
                    2p4           not called    2p3
                    2p5           called
                    3p1           not called    2p1
                    3p2           not called    1p1
                    3p3           not called    3p1, 1p4
                    3p4           not called    2p3
         main1      main1         not called    3p3, 2p2, 1p4

           Procedure Management Table after Second Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           called        1p2
                    2p2           not called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4

           Procedure Manageinent Table after Third Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           called        1p2
                    2p2           not called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4

           Procedure Management Table after Fourth Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           called        1p2
                    2p2           not called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4

           Procedure Management Table after Fifth Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           called        1p2
                    2p2           not called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4

           Procedure Management Table after Sixth Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           not called
                    1p4           not called    1p3
           2        2p1           called        1p2
                    2p2           called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4

          Procedure Management Table after Seventh Loop
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           called
                    1p4           called        1p3
           2        2p1           called        1p2
                    2p2           called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4


    Evaluation after Processing Graph Table for Software Load 1
       Mod table    Proc table    status        call list
           1        1p1           not called
                    1p2           called
                    1p3           called
                    1p4           called        1p3
           2        2p1           called        1p2
                    2p2           called
                    2p3           not called    2p2
                    2p4           not called    2p3
                    2p5           called
           3        3p1           called        2p1
                    3p2           not called    1p1
                    3p3           called        3p1, 1p2
                    3p4           not called    2p3
         main1      main1         called        3p3, 2p2, 1p4

    Method/  extended    empty   single                Memory
    load       shell     shell    shell   tombstone   recovered
    Eci        54 k      58 k     61 k       75 k     54 k-75 k
    Eli        74 k      79 k     83 k      101 k     74 k-101 k
    Odi        55 k      58 k     61 k       72 k     55 k-72 k
    Odt       104 k     113 k    122 k      154 k    104 k-154 k
    Ogi        86 k      91 k     96 k      113 k     86 k-113 k
    Olg        54 k      59 k     63 k       77 k     54 k-77 k
    Xli        67 k      73 k     77 k       93 k     67 k-93 k
    xm2        63 k      67 k     79 k       82 k     63 k-82 k
    Xsc        62 k      66 k     68 k       80 k     62 k-80 k

• Inventors
  Ledford, Bruce Alan; Stewart, Nicholas Richard;
• Assignee
  Nortel Networks Limited (Montreal, CA)
• Published
  Jun-12-2001
• Current US Classes:
  717/107
  717/157
  717/162
• Application #
  218814
• International Classes
  G06F 009/44
• Field of Search
  717/9
• Examiner
  Powell; Mark
• US Patent References:
  5457799
  5499340
  5828883
  5974249
  6023585
  6182283