PureBasic Forums - English

Code: Select all

;- Procedure node
Structure SProc
  List *Calls.SProc()
  IsCalled.i ; Whether to include this procedure in the asm output
EndStructure

;- All procedures with their calls are stored in this list
NewMap AllProcedures.SProc()
; Except a "special" variable for collecting calls that occur outside any procedure
TopLevel.SProc

;- Add our procedures
; This can happen gradually during the single pass compilation
For I = 'a' To 'g'
  AllProcedures(Chr(i))
Next

;- Add procedure calls
; This can happen gradually during the single pass compilation.
; Because procedures cannot be called before they are defined/declared
; this and the previous step can be intertwined in a single pass!

; b() calls b()
AddElement(AllProcedures("b")\Calls())
AllProcedures("b")\Calls() = FindMapElement(AllProcedures(), "b")

; d() calls c()
AddElement(AllProcedures("d")\Calls())
AllProcedures("d")\Calls() = FindMapElement(AllProcedures(), "c")

; e() calls f()
AddElement(AllProcedures("e")\Calls())
AllProcedures("e")\Calls() = FindMapElement(AllProcedures(), "f")

; f() calls e()
AddElement(AllProcedures("f")\Calls())
AllProcedures("f")\Calls() = FindMapElement(AllProcedures(), "e")

; g() calls g()
AddElement(AllProcedures("g")\Calls())
AllProcedures("g")\Calls() = FindMapElement(AllProcedures(), "g")

; Toplevel calls f
AddElement(TopLevel\Calls())
TopLevel\Calls() = FindMapElement(AllProcedures(), "f")

; Toplevel calls g
AddElement(TopLevel\Calls())
TopLevel\Calls() = FindMapElement(AllProcedures(), "g")

;- Set \IsCalled to 0 for all procedures
; IsCalled is initialized to 0, so we don't need to do anything special

;- Traverse the map as a tree, to mark called procedures
Procedure TraverseAndMark(*N.SProc)
  ForEach *N\Calls()
    If Not *N\Calls()\IsCalled
      *N\Calls()\IsCalled = 1
      TraverseAndMark(*N\Calls())
    EndIf
  Next
EndProcedure

TraverseAndMark(TopLevel)

;- Traverse map as map again, to know which procedures were marked
ForEach AllProcedures()
  If AllProcedures()\IsCalled
    Debug MapKey(AllProcedures())
  EndIf
Next

Code: Select all

Procedure a() 
  ; NOT NEEDED
  ; never referenced  
EndProcedure

Procedure b()
  ; NOT NEEDED
  ; referenced only by itself (recursive)
  b()
EndProcedure

Procedure c()
  ; NOT NEEDED
  ; referenced by a function never referenced: d()
EndProcedure

Procedure d()
  ; NOT NEEDED
  ; never referenced
  c()
EndProcedure

Declare f()
Procedure e()
  ; NEEDED
  ; referenced and called by f()
  ; and also we have a mutual recursion here, to really test the algorithm
  f()
EndProcedure

Procedure f()
  ; NEEDED
  e()
EndProcedure

Procedure g()
  ; NEEDED
  ; referenced by itself and toplevel
  g()
EndProcedure

f()
g()

Code: Select all

Structure T_CALL_LIST
 flgCalled.i
 List CallList$()
EndStructure

Global NewList TopLevel$()
Global NewMap Procedures.T_CALL_LIST()

; simulate single pass  parse of a PB file

; add proc a() from its body declaration
AddMapElement(Procedures(), "a") 

; add proc b() from its body declaration
AddMapElement(Procedures(), "b") 
; we found it call itself, so we don't add that info

; add proc c() from its body declaration
AddMapElement(Procedures(), "c")

; add proc d() from its body declaration
AddMapElement(Procedures(), "d")
AddElement(Procedures()\CallList$())
Procedures()\CallList$() = "c" ; 

; add proc f() from its declare statement
AddMapElement(Procedures(), "f") ; 

; add proc e() from its declare statement
AddMapElement(Procedures(), "e") ; 

; add proc z() from its body declaration
AddMapElement(Procedures(), "z")
AddElement(Procedures()\CallList$())
Procedures()\CallList$() = "f" ; 
AddElement(Procedures()\CallList$())
Procedures()\CallList$() = "e" ; 

; we found proc e() body, it's already in the map so we retrieve it
FindMapElement(Procedures(),"e")
AddElement(Procedures()\CallList$())
Procedures()\CallList$() = "f" 
AddElement(Procedures()\CallList$())
Procedures()\CallList$() = "z" 

; we found proc f() body, it's already in the map so we retrieve it
FindMapElement(Procedures(),"f")
AddElement(Procedures()\CallList$())
Procedures()\CallList$() = "e"

; add proc g() from its body declaration
AddMapElement(Procedures(), "g")
; we found it call itself, so we don't add that info

; top level call to the proc f()
AddElement(TopLevel$())
TopLevel$() = "f" 

; top level call to the proc g()
AddElement(TopLevel$())
TopLevel$() = "g" 


Procedure FollowChain (proc$)
 Protected called$
 
 ForEach Procedures(proc$)\CallList$()
    called$ = Procedures()\CallList$()
    If Procedures(called$)\flgCalled = 0
        Procedures(called$)\flgCalled = 1
        FollowChain(called$)
    EndIf
 Next 
EndProcedure

; mark them
ForEach TopLevel$()    
    Procedures(TopLevel$())\flgCalled = 1    
    FollowChain(TopLevel$())       
Next

; show them
ForEach Procedures()
    If Procedures()\flgCalled        
        Debug MapKey(Procedures())
    EndIf
Next

Code: Select all

Procedure a()
  ; NOT NEEDED
  ; never called 
EndProcedure

Procedure b()
  ; NOT NEEDED
  ; referenced only by itself (recursive)
  b()
EndProcedure

Procedure c()
  ; NOT NEEDED
  ; referenced by a function never called: d()
EndProcedure

Procedure d()
  ; NOT NEEDED
  ; never called
  c()
EndProcedure

Declare f()
Declare e()

Procedure z()
  ; NEEDED
  ; called by e()
f()
e()
EndProcedure

Procedure e()
  ; NEEDED
  ; called by f(), z()
  f()
  z()
EndProcedure

Procedure f()  
  ; NEEDED
  ; called by toplevel, e(), z()
  e()
EndProcedure

Procedure g()
  ; NEEDED
  ; referenced by itself and called by toplevel
  g()
EndProcedure

f()
g()

Code: Select all

[23:05:42] e
[23:05:42] f
[23:05:42] g
[23:05:42] z