tclbdd

Check-in [88561d8ac3]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add prelude/postlude to code generation to reduce the temptation of global vars. Fix FDDD code gen for equalities, which was using the wrong namespace.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:88561d8ac3a4821d88c0837b7ae4f587b255086b
User & Date: kbk 2014-01-10 13:52:00
Context
2014-01-14
00:35
added != to datalog, and extended tclfddd to support it. check-in: bd3c0053ea user: kbk tags: trunk
2014-01-10
13:52
Add prelude/postlude to code generation to reduce the temptation of global vars. Fix FDDD code gen for equalities, which was using the wrong namespace. check-in: 88561d8ac3 user: kbk tags: trunk
02:18
Try to make installer work check-in: ce07ff5188 user: kbk tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to examples/reach2.tcl.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
45
46
47
48
49
50
51
52
53
54
55


56
57
58


59
60
61
62


63
64
65


66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
db relation seq st st2
db relation writes st v
db relation flowspast v st st2
db relation reaches v st st2
db relation uninitRead st v
db relation deadWrite st v

proc reaching_defs {} [bdd::datalog::compileProgram db {
 
    % A false entry node (node 0) sets every variable and flows
    % to node 1. If any of its variables are reachable, those are
    % variables possibly used uninitialized in the program.

    writes(0, _).
    writes(st,v) :- writes0(st,v).
................................................................................

    uninitRead(st, v) :- reaches(v, 0, st).

    % A variable write that reaches nowhere else is dead code

    deadWrite(st, v) :- writes(st, v), !reaches(v, st, _).

}]

# Report which variable definitions reach statement $i
proc query1 {i} [bdd::datalog::compileProgram db {


    reaches(v, st, $i)?
} d {
    lappend ::flowsto [lindex $::vnames [dict get $d v]] [dict get $d st]


}]

# Report which variable uses flow from statement $i
proc query2 {i} [bdd::datalog::compileProgram db {


    reaches(v, $i, st)?
} d {
    lappend ::flowsfrom [lindex $::vnames [dict get $d v]] [dict get $d st]


}]
    
puts [info body reaching_defs]

reaching_defs
puts [format {%-16s %2s  %-32s %-16s} PRODUCERS {} INSTRUCTIONS CONSUMERS]
set i 0
foreach stmt $program {
    set flowsto {}
    query1 $i
    set flowsfrom {}
    query2 $i
    puts [format "%-16s %2d: %-32s %-16s" \
	      [lsort -stride 2 -index 0 -ascii \
		   [lsort -stride 2 -index 1 -integer $flowsto]] \
	      $i \
	      $stmt \
	      [lsort -stride 2 -index 0 -ascii \
		   [lsort -stride 2 -index 1 -integer $flowsfrom]]]
    incr i
}







|







 







|



>
>


|
>
>




>
>


|
>
>








|
<
|
<









11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

83

84
85
86
87
88
89
90
91
92
db relation seq st st2
db relation writes st v
db relation flowspast v st st2
db relation reaches v st st2
db relation uninitRead st v
db relation deadWrite st v

proc reaching_defs {} [bdd::datalog::compileProgram db {} {
 
    % A false entry node (node 0) sets every variable and flows
    % to node 1. If any of its variables are reachable, those are
    % variables possibly used uninitialized in the program.

    writes(0, _).
    writes(st,v) :- writes0(st,v).
................................................................................

    uninitRead(st, v) :- reaches(v, 0, st).

    % A variable write that reaches nowhere else is dead code

    deadWrite(st, v) :- writes(st, v), !reaches(v, st, _).

} {}]

# Report which variable definitions reach statement $i
proc query1 {i} [bdd::datalog::compileProgram db {
    set flowsto {}
} {
    reaches(v, st, $i)?
} d {
    lappend flowsto [lindex $::vnames [dict get $d v]] [dict get $d st]
} {
    return $flowsto
}]

# Report which variable uses flow from statement $i
proc query2 {i} [bdd::datalog::compileProgram db {
    set flowsfrom {}
} {
    reaches(v, $i, st)?
} d {
    lappend flowsfrom [lindex $::vnames [dict get $d v]] [dict get $d st]
} {
    return $flowsfrom
}]
    
puts [info body reaching_defs]

reaching_defs
puts [format {%-16s %2s  %-32s %-16s} PRODUCERS {} INSTRUCTIONS CONSUMERS]
set i 0
foreach stmt $program {
    set flowsto [query1 $i]

    set flowsfrom [query2 $i]

    puts [format "%-16s %2d: %-32s %-16s" \
	      [lsort -stride 2 -index 0 -ascii \
		   [lsort -stride 2 -index 1 -integer $flowsto]] \
	      $i \
	      $stmt \
	      [lsort -stride 2 -index 0 -ascii \
		   [lsort -stride 2 -index 1 -integer $flowsfrom]]]
    incr i
}

Changes to library/datalog.tcl.

1515
1516
1517
1518
1519
1520
1521
1522


1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544

1545
1546
1547
1548
1549



1550

1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
	}
	yield $component

    }
    return
}

proc bdd::datalog::compileProgram {db programText args} {



    variable parser

    try {

	set program [bdd::datalog::program new]

	# Do lexical analysis of the program
	lassign [lex $programText] tokens values
	
	# Parse the program
	set parseTree [$parser parse $tokens $values $program]
	
	# Extract the facts, rules, and edges joining the rules from the parse
	if 0 {
	    set facts [$program getFacts]
	    set rules [$program getRules]
	    set outedges [$program getEdges]
	}
	
	set plan [$program planExecution]


	set intcode [$program translateExecutionPlan $db $plan]

	# TODO: Here is where optimization should happen. And optimization
	#       can be helped with Datalog?




	set result [$program generateCode $db $intcode {*}$args]


    } finally {

	$program destroy

    }
    return $result

}

package provide tclbdd::datalog 0.1







|
>
>












|
|
<
<
<
<
<
<


>


<
<
<
>
>
>
|
>











1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538






1539
1540
1541
1542
1543



1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
	}
	yield $component

    }
    return
}

proc bdd::datalog::compileProgram {db prelude programText args} {

    set postlude [lindex $args end]

    variable parser

    try {

	set program [bdd::datalog::program new]

	# Do lexical analysis of the program
	lassign [lex $programText] tokens values
	
	# Parse the program
	set parseTree [$parser parse $tokens $values $program]

	# Plan the execution






	set plan [$program planExecution]

	# Translate the execution plan to relational algebra
	set intcode [$program translateExecutionPlan $db $plan]




	# Generate code
	append result \
	    $prelude \n \
	    [$program generateCode $db $intcode {*}[lrange $args 0 end-1]] \n \
	    $postlude

    } finally {

	$program destroy

    }
    return $result

}

package provide tclbdd::datalog 0.1

Changes to library/tclfddd.tcl.

592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
	# the easy cases.

	set vlist {}
	foreach v $vars1 v2 $vars2 {
	    lappend vlist $v $v2
	}
	set vlist [lsort -stride 2 -integer -index 0 -decreasing $vlist]
	set code [list sys := $dest 1]
	foreach {v v2} $vlist {
	    append code \; [list sys nthvar :a $v]
	    append code \; [list sys nthvar :b $v2]
	    append code \; [list sys == :t :a :b]
	    append code \; [list sys & $dest $dest :t]
	}
	append code \; [list sys unset :a :b :t]
	return $code
    }

    # Method: forget
    #
    #	Removes relations from the database
    #







|

|
|
|
|

|







592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
	# the easy cases.

	set vlist {}
	foreach v $vars1 v2 $vars2 {
	    lappend vlist $v $v2
	}
	set vlist [lsort -stride 2 -integer -index 0 -decreasing $vlist]
	set code [list [namespace which sys] := $dest 1]
	foreach {v v2} $vlist {
	    append code \; [list [namespace which sys] nthvar :a $v]
	    append code \; [list [namespace which sys] nthvar :b $v2]
	    append code \; [list [namespace which sys] == :t :a :b]
	    append code \; [list [namespace which sys] & $dest $dest :t]
	}
	append code \; [list [namespace which sys] unset :a :b :t]
	return $code
    }

    # Method: forget
    #
    #	Removes relations from the database
    #