← Back to branch summary

~ubuntu-branches/ubuntu/maverick/blender/maverick

« back to all changes in this revision

Viewing changes to extern/fftw/genfft-k7/vDag.ml

  • Committer: Bazaar Package Importer
  • Author(s): Khashayar Naderehvandi, Khashayar Naderehvandi, Alessio Treglia
  • Date: 2009-01-22 16:53:59 UTC
  • mfrom: (14.1.1 experimental)
  • Revision ID: james.westby@ubuntu.com-20090122165359-v0996tn7fbit64ni
Tags: 2.48a+dfsg-1ubuntu1
https://launchpad.net/bugs/320045
[ Khashayar Naderehvandi ]
* Merge from debian experimental (LP: #320045), Ubuntu remaining changes:
  - Add patch correcting header file locations.
  - Add libvorbis-dev and libgsm1-dev to Build-Depends.
  - Use avcodec_decode_audio2() in source/blender/src/hddaudio.c

[ Alessio Treglia ]
* Add missing previous changelog entries.

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/fftw/genfft-k7/vDag.ml
 
1
(*
 
2
 * Copyright (c) 1997-1999 Massachusetts Institute of Technology
 
3
 * Copyright (c) 2000-2001 Stefan Kral
 
4
 *
 
5
 * This program is free software; you can redistribute it and/or modify
 
6
 * it under the terms of the GNU General Public License as published by
 
7
 * the Free Software Foundation; either version 2 of the License, or
 
8
 * (at your option) any later version.
 
9
 *
 
10
 * This program is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License
 
16
 * along with this program; if not, write to the Free Software
 
17
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
 *
 
19
 *)
 
20
 
 
21
(* Here, we have functions to transform a sequence of assignments
 
22
   (variable = expression) into a DAG (a directed, acyclic graph).
 
23
   The nodes of the DAG are the assignments, and the edges indicate
 
24
   dependencies.  (The DAG is analyzed in the scheduler to find an
 
25
   efficient ordering of the assignments.)
 
26
 
 
27
   This file also contains utilities to manipulate the DAG in various
 
28
   ways. *)
 
29
 
 
30
(* In the standard distribution of FFTW 2.1.3 there is a module called Dag.
 
31
   This module (Vdag) is an adaptation of that module (Dag) that operates
 
32
   on vsimdinstructions instead of expressions and assignments. *)
 
33
 
 
34
open Variable
 
35
open Number
 
36
open VSimdBasics
 
37
open List
 
38
 
 
39
(********************************************
 
40
 *  Dag structure
 
41
 ********************************************)
 
42
type color = RED | BLUE | BLACK | YELLOW
 
43
 
 
44
type dagnode = 
 
45
    { assigned             : vsimdinstroperand list;
 
46
      instruction          : vsimdinstr;
 
47
      input_variables      : VSimdInstrOperandSet.t;
 
48
      input_variables_raw  : VSimdRawVarSet.t;
 
49
      mutable successors   : dagnode list;
 
50
      mutable predecessors : dagnode list;
 
51
      mutable label        : int;
 
52
      mutable color        : color }
 
53
 
 
54
type dag = Dag of dagnode list
 
55
 
 
56
(* true if node uses v *)
 
57
let node_uses v node =
 
58
  VSimdInstrOperandSet.mem v node.input_variables
 
59
 
 
60
(* true if assignment of v clobbers any input of node *)
 
61
let node_clobbers node = function
 
62
  | V_SimdQVar(Output,k) ->
 
63
      VSimdRawVarSet.mem (V_SimdRawQVar k) node.input_variables_raw
 
64
  | V_SimdDVar(p,Output,k) ->
 
65
      VSimdRawVarSet.mem (V_SimdRawDVar(p,k)) node.input_variables_raw
 
66
  | _ -> false
 
67
 
 
68
(* true if nodeb depends on nodea *)
 
69
let depends_on nodea nodeb = 
 
70
  exists (fun i -> node_uses i nodeb) nodea.assigned || 
 
71
  exists (fun i -> node_clobbers nodea i) nodeb.assigned
 
72
 
 
73
(* transform an assignment list into a dag *)
 
74
let makedag alist =
 
75
  let dag = List.map
 
76
      (fun instr ->
 
77
        { assigned            = vsimdinstrToDstoperands instr;
 
78
          instruction         = instr;
 
79
          input_variables     = List.fold_right VSimdInstrOperandSet.add 
 
80
                                                (vsimdinstrToSrcoperands instr) 
 
81
                                                VSimdInstrOperandSet.empty;
 
82
          input_variables_raw = List.fold_right VSimdRawVarSet.add 
 
83
                                                (vsimdinstrToSrcrawvars instr)
 
84
                                                VSimdRawVarSet.empty;
 
85
          successors          = [];
 
86
          predecessors        = [];
 
87
          label               = 0;
 
88
          color               = BLACK })
 
89
      alist
 
90
  in begin
 
91
    List.iter (fun i ->
 
92
        List.iter (fun j ->
 
93
          if depends_on i j then begin
 
94
            i.successors <- j :: i.successors;
 
95
            j.predecessors <- i :: j.predecessors;
 
96
          end) dag) dag;
 
97
    Dag dag;
 
98
  end
 
99
 
 
100
let map f (Dag dag) = Dag (List.map f dag)
 
101
let for_all (Dag dag) f = 
 
102
  (* type system loophole *)
 
103
  let make_unit _ = () in
 
104
  make_unit (List.map f dag)
 
105
let to_list (Dag dag) = dag
 
106
let find_node f (Dag dag) = Util.find_elem f dag
 
107
 
 
108
(* breadth-first search *)
 
109
let rec bfs (Dag dag) node init_label =
 
110
  let _ =  node.label <- init_label in
 
111
  let rec loop = function
 
112
      [] -> ()
 
113
    | node :: rest ->
 
114
        let neighbors = node.predecessors @ node.successors in
 
115
        let m = Util.min_list (List.map (fun node -> node.label) neighbors) in
 
116
        if (node.label > m + 1) then begin
 
117
          node.label <- m + 1;
 
118
          loop (rest @ neighbors);
 
119
        end else
 
120
          loop rest
 
121
  in let neighbors = node.predecessors @ node.successors in
 
122
  loop neighbors
 
123