class C::Node

This is an extension to the CAST Node class. This particular extension is for A-Darwin only methods. These methods are mainly used to extract loops and loop data from the CAST nodes.

This class provides an extension to the CAST node class, which is a parent class for all other CAST classes. The extension consists of three different types of methods:

This file provides the common methods that extend the CAST node class. These methods are used by both Bones and A-Darwin.

This class provides an extension to the CAST node class, which is a parent class for all other CAST classes. The extension consists of three different types of methods:

Public Instance Methods

add?() click to toggle source

This method returns ‘true’ if the node is of the ‘Add’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
187 def add?
188         return (self.class == C::Add)
189 end
addassign?() click to toggle source

This method returns ‘true’ if the node is of the ‘AddAssign’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
199 def addassign?
200         return (self.class == C::AddAssign)
201 end
alu?() click to toggle source

This method returns ‘true’ if the node is performing an ALU operation. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
274 def alu?
275         return add? || subtract? || addassign? || postinc? || postdec? || preinc? || predec? || binary_expression?
276 end
and?() click to toggle source

This method returns ‘true’ if the node is of the ‘And’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
145 def and?
146         return (self.class == C::And)
147 end
array?() click to toggle source

This method returns ‘true’ if the node is of the ‘Array’ class. Otherwise, it returns ‘false’.

   # File lib/castaddon/node_common.rb
72 def array?
73         return (self.class == C::Array)
74 end
assign?() click to toggle source

This method returns ‘true’ if the node is of the ‘Assign’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
235 def assign?
236         return (self.class == C::Assign)
237 end
assignment_expression?() click to toggle source

This method returns ‘true’ if the node’s class inherits from the ‘AssignmentExpression’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
261 def assignment_expression?
262         return (self.class.superclass == C::AssignmentExpression)
263 end
binary_expression?() click to toggle source

This method returns ‘true’ if the node’s class inherits from the ‘BinaryExpression’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
254 def binary_expression?
255         return (self.class.superclass == C::BinaryExpression)
256 end
block?() click to toggle source

This method returns ‘true’ if the node is of the ‘Block’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
127 def block?
128         return (self.class == C::Block)
129 end
call?() click to toggle source

This method returns ‘true’ if the node is of the ‘Call’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
108 def call?
109         return (self.class == C::Call)
110 end
declaration?() click to toggle source

This method returns ‘true’ if the node is of the ‘Declaration’ class. Otherwise, it returns ‘false’.

   # File lib/castaddon/node_common.rb
96 def declaration?
97         return (self.class == C::Declaration)
98 end
declarator?() click to toggle source

This method returns ‘true’ if the node is of the ‘Declarator’ class. Otherwise, it returns ‘false’.

   # File lib/castaddon/node_common.rb
90 def declarator?
91         return (self.class == C::Declarator)
92 end
direction(variable_name) click to toggle source

This method finds the direction of a variable based on the node information. The direction of a variable can be either:

  • in: - The variable is accessed read-only.

  • out: - The variable is accessed write-only.

The method takes the name of a variable and walks through the node to search for expressions (assignments and binary expressions). For each expression it takes the first and second part of the expression and stores it in a list. Afterwards, the expressions in the list are analysed for occurrences of the variable.

The method raises an error if the variable does not appear at all: it is neither input nor output.

    # File lib/castaddon/node_bones.rb
146 def direction(variable_name)
147         result = {:in => false, :out => false }
148         expressions = {:in => [], :out => []}
149         output_nodes = []
150         self.preorder do |node|
151                 
152                 # First find out if the current node actually contains the target variable somewhere
153                 name_match = false
154                 node.preorder do |match_node|
155                         name_match = true if (match_node.variable?) && (match_node.name == variable_name)
156                 end
157                 
158                 # If there is a match and the current node is of an assignment/binary/declarator type, we can start processing
159                 if (name_match) && (node.assignment_expression? || node.binary_expression? || node.declarator?)
160                         
161                         # First find out if this node can be considered an input (see sum/acc/temp register variable problem - chunk/example1 vs chunk/example5)
162                         possible_input = true
163                         node.preorder do |test_node|
164                                 output_nodes.each do |output_node|
165                                         possible_input = false if test_node =~ output_node
166                                 end
167                         end
168                         
169                         # Store the node's data in a list (input/output lists are separated)
170                         if node.assignment_expression?
171                                 output_nodes << node.lval
172                                 expressions[:out] << node.lval.remove_index
173                                 expressions[:in] << node.rval                if possible_input
174                                 if !node.assign?
175                                         expressions[:in] << node.lval              if possible_input
176                                 end
177                         elsif node.binary_expression?
178                                 expressions[:in] << node.expr1               if possible_input
179                                 expressions[:in] << node.expr2.remove_index  if possible_input
180                         elsif node.declarator? && node.init
181                                 expressions[:in] << node.init                if possible_input
182                         end
183                 end
184         end
185         
186         # Set the result according to the list of nodes
187         expressions.each do |key,expression_list|
188                 expression_list.each do |expression|
189                         expression.preorder do |node|
190                                 if (node.variable?) && (node.name == variable_name)
191                                         result[key] = true
192                                 end
193                         end
194                 end
195         end
196         
197         # Return the result
198         return Bones::INOUT if result[:in] && result[:out]
199         return Bones::INPUT if result[:in]
200         return Bones::OUTPUT if result[:out]
201         raise_error('Variable "'+variable_name+'" is neither input nor output')
202 end
equality?() click to toggle source

This method returns ‘true’ if the node is of the ‘Equal’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
157 def equality?
158         return (self.class == C::Equal)
159 end
for_statement?() click to toggle source

This method returns ‘true’ if the node is of the ‘For’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
133 def for_statement?
134         return (self.class == C::For)
135 end
function_declaration?() click to toggle source

This method returns ‘true’ if the node is of the ‘Declarator’ class with its ‘indirect_type’ equal to ‘Function’ . Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
121 def function_declaration?
122         return (self.class == C::Declarator && self.indirect_type.class == C::Function)
123 end
function_definition?() click to toggle source

This method returns ‘true’ if the node is of the ‘FunctionDef’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
114 def function_definition?
115         return (self.class == C::FunctionDef)
116 end
get_accesses(accesses = [],loop_data = [],if_statements = []) click to toggle source

This method retrieves all array references in the current node. It retrieves information on loops and on if-statements as well. This method is destructive on the current node. It is furthermore called recursively.

    # File lib/castaddon/node_adarwin.rb
 51 def get_accesses(accesses = [],loop_data = [],if_statements = [])
 52         
 53         # Iterate over all the nodes
 54         self.preorder do |node|
 55                 
 56                 # A loop has been found. Proceed as follows: 1) store the loop data, 2)
 57                 # call this method recursively on the loop body, and 3) remove the loop
 58                 # body from the node.
 59                 if node.for_statement? && node.stmt
 60                         next_loop_data = loop_data.clone
 61                         next_loop_data.push(node.get_single_loop)
 62                         node.stmt.clone.get_accesses(accesses,next_loop_data,if_statements)
 63                         node.remove_node(node.stmt)
 64                 
 65                 # An if-statement has been found. Proceed as follows: 1) store the (one or
 66                 # more) if-statement conditions, 2) call this method recursively on the
 67                 # if-statement body, and 3) remove the if-statement body from the node.
 68                 elsif node.if_statement?
 69                         next_if_statements = if_statements.clone
 70                         node.cond.get_conditions().each do |condition|
 71                                 next_if_statements.push(condition)
 72                         end
 73                         node.then.clone.get_accesses(accesses,loop_data,next_if_statements)
 74                         node.remove_node(node.then)
 75                 
 76                 # We haven't found an if-statement or loop in the current node, so it
 77                 # implies that we can search for an array reference.
 78                 # TODO: Array references as part of conditions or bounds of loops are not
 79                 # found in this way.
 80                 else
 81                 
 82                         # Collect all the writes we have seen so far. This is used to check for
 83                         # references that are 'register' references because they have been
 84                         # written before.
 85                         writes = accesses.map{ |e| e[:access] if e[:type] == 'write' }.flatten
 86                         
 87                         # Collect the potential references
 88                         to_search = []
 89                         if node.assignment_expression?
 90                                 to_search << [node.lval,'write',true]
 91                                 to_search << [node.lval,'read',false] if !node.assign?
 92                                 to_search << [node.rval,'read',false]
 93                         elsif node.binary_expression?
 94                                 to_search << [node.expr1,'read',false]
 95                                 to_search << [node.expr2,'read',false]
 96                         elsif node.declarator? && node.init
 97                                 to_search << [node.init,'read',false]
 98                         end
 99                         
100                         # Process the potential references into 'accesses' hashes
101                         to_search.each do |item|
102                                 if item[2] || (writes & item[0].get_index_nodes().flatten).empty?
103                                         item[0].get_index_nodes().each do |access|
104                                                 accesses << {
105                                                         :access => access,
106                                                         :name => access.get_array_name(),
107                                                         :indices => access.get_indices(),
108                                                         :type => item[1],
109                                                         :loop_data => loop_data,
110                                                         :if_statements => if_statements
111                                                 }
112                                         end
113                                 end
114                         end
115                 end
116         end
117         
118         # Return the array references as hashes
119         return accesses.uniq
120 end
get_all_loops() click to toggle source

This method retrieves all loops from a loop nest. The method is based on the get_single_loop method to extract the actual loop information.

    # File lib/castaddon/node_adarwin.rb
206 def get_all_loops()
207         loops = []
208         self.preorder do |node|
209                 loops << node.get_single_loop() if node.for_statement?
210         end
211         return loops
212 end
get_array_name() click to toggle source

This method retrieves the name of the array reference.

    # File lib/castaddon/node_adarwin.rb
235 def get_array_name()
236         self.preorder do |node|
237                 return node.expr.to_s if node.index? && !node.expr.index?
238         end
239 end
get_complexity() click to toggle source

This method returns the complexity of a piece of code in terms of the amount of ALU operations (multiplications, additions, etc.).

   # File lib/castaddon/node_bones.rb
49 def get_complexity
50         count = 0
51         self.preorder do |node|
52                 count += 1 if node.alu?
53         end
54         return count
55 end
get_conditions(results=[]) click to toggle source

This method retrieves the bounds for an if-statement. The method is called recursively if there are multiple conditions. TODO: What about ‘||’ (or) conditions? They are currently handles as ‘&&’. TODO: Are these all the possibilities (&&,||,>=,>,<=,<) for conditions?

    # File lib/castaddon/node_adarwin.rb
126 def get_conditions(results=[])
127         
128         # Recursive call for 'And' (&&) and 'or' (||) compound conditions
129         if and? || or?
130                 expr1.get_conditions(results)
131                 expr2.get_conditions(results)
132                 
133         # Greater than or equal (>=)
134         elsif more_or_equal?
135                 results << [simplify("#{expr1}")+'='+simplify("(#{expr2})"),'']
136                 
137         # Greater than (>)
138         elsif more?
139                 results << [simplify("#{expr1}")+'='+simplify("(#{expr2})+1"),'']
140                 
141         # Less than or equal (<=)
142         elsif less_or_equal?
143                 results << ['',simplify("#{expr1}")+'='+simplify("(#{expr2})")]
144                 
145         # Less than (<)
146         elsif less?
147                 results << ['',simplify("#{expr1}")+'='+simplify("(#{expr2})-1")]
148                 
149         # Equal (==)
150         elsif equality?
151                 results << ['','']#[simplify("#{expr1}"),simplify("(#{expr2})")]
152 
153         # Unsupported conditions
154         else
155                 raise_error("Unsupported if-condition: #{self.to_s}")
156         end
157 end
get_direct_loops(loop_data = []) click to toggle source

This method retrieves all directly following loops from a node, i.e. the loops belonging to a perfectly nested loop. It is a recursive method: it retrieves a first loop and calls the method again on the body of the loop. It collects all the data in the loop_data array.

   # File lib/castaddon/node_adarwin.rb
12 def get_direct_loops(loop_data = [])
13         
14         # Retrieve the next loop
15         new_loop = get_single_loop()
16         
17         # Don't continue if the loop is independent of the writes in the code. This
18         # is part of the selection process of what loops to be considered inner or
19         # outer loops.
20         if loop_data.length > 0
21                 written_indices = self.clone.get_accesses().map do |a|
22                         (a[:type] == "write") ? a[:indices].map{ |i| i.to_s } : []
23                 end
24                 if !written_indices.flatten.uniq.include?(new_loop[:var])
25                         return loop_data
26                 end
27         end
28         
29         # Push the new loop into the array
30         loop_data.push(new_loop)
31         
32         # Check whether the current is actually a loop.
33         # TODO: Is this check really needed or is this just a safety net?
34         if self.for_statement? && self.stmt
35                 body = self.stmt.stmts
36                 
37                 # Check whether or not there is another loop directly following and make
38                 # sure that the body is not empty.
39                 if body.length == 1 && body.first.for_statement?
40                         body.first.get_direct_loops(loop_data)
41                 end
42         end
43         
44         # Return all the loop data
45         return loop_data
46 end
get_functions() click to toggle source

Method to obtain a list of all functions in the code. If no functions can be found, an empty array is returned. For every function found, the function itself is pushed to the list. This method also makes sure that there is at least one function with the name ‘main’. If this is not the case, an error is raised.

   # File lib/castaddon/node_bones.rb
33 def get_functions
34         includes_main = false
35         function_list = []
36         self.preorder do |node|
37                 if node.function_definition?
38                         function_list.push(node)
39                         includes_main = true if (node.name == 'main' || node.name == Bones::VARIABLE_PREFIX+'main')
40                 end
41         end
42         raise_error('No "main"-function detected in the input file') if !includes_main
43         return function_list
44 end
get_index_nodes() click to toggle source

This method retrieves all nodes from the current node that are index node. Such nodes represent array references, e.g. in A, [i+3] is the index node.

    # File lib/castaddon/node_adarwin.rb
217 def get_index_nodes()
218         nodes = []
219         self.preorder do |node|
220                 nodes << node if node.index? && !node.parent.index?
221         end
222         return nodes
223 end
get_indices() click to toggle source

This method retrieves all indices of index nodes from the current node.

    # File lib/castaddon/node_adarwin.rb
226 def get_indices()
227         indices = []
228         self.postorder do |node|
229                 indices << node.index if node.index?
230         end
231         return indices
232 end
get_single_loop() click to toggle source

This method retrieves a single loop from the current node and collects its data: 1) the loop variable, 2) the lower-bound, 3) the upper-bound, and 4) the loop step. FIXME: For decrementing loops, should the min/max be swapped?

    # File lib/castaddon/node_adarwin.rb
163 def get_single_loop()
164         loop_datum = { :var => '', :min => '', :max => '', :step => ''}
165         if self.for_statement?
166                 
167                 # Get the loop start condition and the loop variable.
168                 # TODO: Add support for other types of initialisations, e.g. a declaration
169                 if self.init.assign?
170                         loop_datum[:var] = self.init.lval.name
171                         loop_datum[:min] = self.init.rval.get_value.to_s
172                 elsif self.init.declaration?
173                         loop_datum[:var] = self.init.declarators.first.name
174                         loop_datum[:min] = self.init.declarators.first.init.to_s
175                 else
176                         raise_error("Unsupported loop initialization: #{self.init}")
177                 end
178                 
179                 # Get the loop's upper-bound condition.
180                 # TODO: Add support for the unsupported cases.
181                 var_is_on_left = (self.cond.expr1.get_value == loop_datum[:var])
182                 loop_datum[:max] = case
183                         when self.cond.less? then (var_is_on_left) ? simplify("#{self.cond.expr2.get_value}-1") : "unsupported"
184                         when self.cond.more? then (var_is_on_left) ? "unsupported" : simplify("#{self.cond.expr1.get_value}-1")
185                         when self.cond.less_or_equal? then (var_is_on_left) ? "#{self.cond.expr2.get_value}" : "unsupported"
186                         when self.cond.more_or_equal? then (var_is_on_left) ? "unsupported" : "#{self.cond.expr1.get_value}"
187                 end
188                 raise_error("Unsupported loop condition: #{self.cond}") if loop_datum[:max] == "unsupported"
189                 
190                 # Get the loop iterator.
191                 # TODO: Investigate whether we can handle non-basic cases
192                 iterator = self.iter.to_s
193                 loop_datum[:step] = case iterator
194                         when "#{loop_datum[:var]}++" then '1'
195                         when "++#{loop_datum[:var]}" then '1'
196                         when "#{loop_datum[:var]}--" then '-1'
197                         when "--#{loop_datum[:var]}" then '-1'
198                         else simplify(self.iter.rval.to_s.gsub(loop_datum[:var],'0'))
199                 end
200         end
201         return loop_datum
202 end
get_value() click to toggle source

This method retrieves the value from the current node. The value can be an integer (in case of a constant) or a string (in case of a variable).

    # File lib/castaddon/node_adarwin.rb
256 def get_value()
257         return self.val if self.intliteral?
258         return self.name if self.variable?
259         return self.to_s
260 end
get_var_declarations() click to toggle source

This method retrieves all variable declarations

    # File lib/castaddon/node_adarwin.rb
242 def get_var_declarations()
243         vars = []
244         self.preorder do |node|
245                 if node.declaration?
246                         node.declarators.each do |decl|
247                                 vars << decl.name
248                         end
249                 end
250         end
251         return vars
252 end
has_conditional_statements?() click to toggle source

This method checks whether the given code has any conditional statements (if-statements)

    # File lib/castaddon/node_bones.rb
306 def has_conditional_statements?
307         self.preorder do |node|
308                 if node.if_statement?
309                         return true
310                 end
311         end
312         return false
313 end
if_statement?() click to toggle source

This method returns ‘true’ if the node is of the ‘If’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
139 def if_statement?
140         return (self.class == C::If)
141 end
index?() click to toggle source

This method returns ‘true’ if the node is of the ‘Index’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
102 def index?
103         return (self.class == C::Index)
104 end
intliteral?() click to toggle source

This method returns ‘true’ if the node is of the ‘IntLiteral’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
229 def intliteral?
230         return (self.class == C::IntLiteral)
231 end
lengths(result = []) click to toggle source

This is a helper method which calls itself recursively, depending on the dimensions of the variable. It stores the resulting array sizes in an array ‘result’.

    # File lib/castaddon/node_bones.rb
112 def lengths(result = [])
113         found = '('+self.length.to_s+')'
114         result.push(found)
115         return (self.type && self.type.array?) ? self.type.lengths(result) : result
116 end
less?() click to toggle source

This method returns ‘true’ if the node is of the ‘Less’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
163 def less?
164         return (self.class == C::Less)
165 end
less_or_equal?() click to toggle source

This method returns ‘true’ if the node is of the ‘LessOrEqual’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
175 def less_or_equal?
176         return (self.class == C::LessOrEqual)
177 end
more?() click to toggle source

This method returns ‘true’ if the node is of the ‘More’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
169 def more?
170         return (self.class == C::More)
171 end
more_or_equal?() click to toggle source

This method returns ‘true’ if the node is of the ‘MoreOrEqual’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
181 def more_or_equal?
182         return (self.class == C::MoreOrEqual)
183 end
node_exists?(target) click to toggle source

This method searches for a target node and checks whether it exists. The input to the method is the target node. The method walks through the node and checks whether:

  • The node’s class is the same as the target class (+node.class == target.class+)

  • The node has a parent (+node.parent != nil+)

  • The node is equal to the target node (+node.match?(target)+)

If all checks are successful, the method will return the value ‘true’ immediately. If the target node cannot be found, the method returns ‘false’.

    # File lib/castaddon/node_bones.rb
242 def node_exists?(target)
243         self.preorder do |node|
244                 if (node.class == target.class) && (node.parent != nil) && (node.match?(target))
245                         return true
246                 end
247         end
248         return false
249 end
or?() click to toggle source

This method returns ‘true’ if the node is of the ‘Or’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
151 def or?
152         return (self.class == C::Or)
153 end
parameter?() click to toggle source

This method returns ‘true’ if the node is of the ‘Parameter’ class. Otherwise, it returns ‘false’.

   # File lib/castaddon/node_common.rb
84 def parameter?
85         return (self.class == C::Parameter)
86 end
pointer?() click to toggle source

This method returns ‘true’ if the node is of the ‘Pointer’ class. Otherwise, it returns ‘false’.

   # File lib/castaddon/node_common.rb
78 def pointer?
79         return (self.class == C::Pointer)
80 end
postdec?() click to toggle source

This method returns ‘true’ if the node is of the ‘PostDec’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
217 def postdec?
218         return (self.class == C::PostDec)
219 end
postinc?() click to toggle source

This method returns ‘true’ if the node is of the ‘PostInc’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
205 def postinc?
206         return (self.class == C::PostInc)
207 end
predec?() click to toggle source

This method returns ‘true’ if the node is of the ‘PreDec’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
223 def predec?
224         return (self.class == C::PreDec)
225 end
preinc?() click to toggle source

This method returns ‘true’ if the node is of the ‘PreInc’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
211 def preinc?
212         return (self.class == C::PreInc)
213 end
preprocess(conditional=true) click to toggle source

Pre-process method. It currently pre-processes a piece of code (typically the kernel code) to replace particular code structures with others, which can be handled (better) by Bones. For now, the pre-process method performs the following transformations:

  • Replaces all incrementors (i++) outside for loops with an assignment (i=i+1).

  • Replaces all decrementors (i–) outside for loops with an assignment (i=i-1).

   # File lib/castaddon/node_bones.rb
17 def preprocess(conditional=true)
18         self.preorder do |node|
19                 if node.postinc? || node.preinc?
20                         node.replace_with(C::AssignmentExpression.parse(node.expr.to_s+' = '+node.expr.to_s+' + 1')) unless conditional && node.parent.for_statement?
21                 elsif node.postdec? || node.predec?
22                         node.replace_with(C::AssignmentExpression.parse(node.expr.to_s+' = '+node.expr.to_s+' - 1')) unless conditional && node.parent.for_statement?
23                 end
24         end
25 end
remove_index() click to toggle source

This method is a small helper function to remove index nodes from a node. It first clones to original node in order to not overwrite it, then walks the node and removes index nodes. Finally, it returns a new node.

    # File lib/castaddon/node_bones.rb
296 def remove_index
297         node_clone = self.clone
298         node_clone.preorder do |node|
299                 node.index.detach if node.index?
300         end
301         return node_clone
302 end
remove_loop(from,to) click to toggle source

This method walks through the node and finds the first for-loop. If it is found, it returns the contents of the for-loop and the name of the loop variable. Obtaining the loop variable is conditional because it can either be an assignment (‘k=0’) or a variable definition (‘int k=0’).

The method raises an error when no for-loop can be found. It also raises an error if the loop is not in canonical form.

    # File lib/castaddon/node_bones.rb
213 def remove_loop(from,to)
214         self.preorder do |node|
215                 if node.for_statement?
216                         from_statement = (node.init.assign?) ? node.init.rval : node.init.declarators[0].init
217                         from_loop = (from_statement.variable?) ? from_statement.name : from_statement.to_s
218                         to_loop = (node.cond.expr2.variable?) ? node.cond.expr2.name : ((node.cond.expr2.intliteral?) ? node.cond.expr2.val.to_s : node.cond.expr2.to_s)
219                         to_loop = to_loop.gsub(/\s/,'')
220                         to_loop = '('+to_loop+')-1' if node.cond.less?
221                         to_loop = simplify(to_loop)
222                         from_loop = simplify(from_loop)
223                         puts Bones::WARNING+'The loop iterator starts at: "'+from_loop+'" (expected "'+from+'")' if from_loop != from
224                         puts Bones::WARNING+'The loop iterator ends at: "'+to_loop+'" (expected "'+to+'")' if to_loop != to
225                         raise_error('The loop increment must be 1') if !(node.iter.unit_increment?)
226                         name = (node.init.assign?) ? node.init.lval.name : node.init.declarators.first.name
227                         return node.stmt, name
228                 end
229         end
230         raise_error('Unexpected number of for-loops')
231 end
remove_once(target) click to toggle source

This method is a small helper function to remove a node once.

   # File lib/castaddon/node_common.rb
49 def remove_once(target)
50         self.postorder do |node|
51                 if node == target
52                         node.detach
53                         return self
54                 end
55         end
56         return self
57 end
rename_variables(suffix,excludes) click to toggle source
    # File lib/castaddon/transformations.rb
141 def rename_variables(suffix,excludes)
142         self.preorder do |node|
143                 if (node.variable? || node.declarator?) && !(excludes.include?(node.name)) && (!node.parent.call?)
144                         node.name = node.name+suffix
145                 end
146         end
147 end
replace_variable(variable_name,replacement) click to toggle source

This method searches for a variable name in the node and replaces it with the method’s argument, which is given as a string. The node itself is modified. The method checks whether:

  • The node is a variable (node.variable?)

  • The variable has the correct name (+node.name == variable_name+)

  • The variable is not in a function call (+!node.parent.call?+)

   # File lib/castaddon/node_common.rb
13 def replace_variable(variable_name,replacement)
14         self.preorder do |node|
15                 node.name = replacement if (node.variable?) && (node.name == variable_name) && (!node.parent.call?)
16         end
17 end
search_and_replace_function_call(target,replacements) click to toggle source

This method searches for a target function call and replaces it with another. Both the target and the replacement function call are given as arguments to the method. The method walks through the node and checks whether:

  • The node’s class is the same as the target class (+node.class == target.class+)

  • The node has a parent which is a function call (node.parent.call?)

  • The node is equal to the target node (+node.match?(target)+)

If all checks are successful, the node will be replaced with the replacement node. The method will continue searching for other occurrences of the function call.

The method returns itself.

    # File lib/castaddon/node_bones.rb
263 def search_and_replace_function_call(target,replacements)
264         self.preorder do |node|
265                 if (node.class == target.class) && (node.parent.call?) && (node.match?(target))
266                         node.replace_with(replacements)
267                 end
268         end
269         return self
270 end
search_and_replace_function_definition(old_name,new_name) click to toggle source

This method searches for a target function name and replaces it with another name. Both the target and the replacement name are given as arguments to the method. The method walks through the node and checks whether:

  • The node’s class is a function definition or declaration

  • The node’s name is equal to the target node’s name

If the checks are successful, the node’s name will be replaced The method will continue searching for other occurrences of functions with the same name.

The method returns itself.

    # File lib/castaddon/node_bones.rb
283 def search_and_replace_function_definition(old_name,new_name)
284         self.preorder do |node|
285                 if (node.function_definition? || node.function_declaration?) && (node.name == old_name)
286                         node.name = new_name
287                 end
288         end
289         return self
290 end
search_and_replace_node(target,replacements) click to toggle source

This method searches for a target node and replaces it with a replacement node. Both the target node and the replacement node are given as arguments to the method. The method walks through the node and checks whether:

  • The node’s class is the same as the target class (+node.class == target.class+)

  • The node has a parent (+node.parent != nil+)

  • The node is equal to the target node (+node.match?(target)+)

If all checks are successful, the node will be replaced with the replacement node and the method will return immediately.

The method returns itself if the target node cannot be found.

   # File lib/castaddon/node_common.rb
31 def search_and_replace_node(target,replacements)
32         if (self.class == target.class) && (self.match?(target))
33                 return replacements
34         end
35         self.preorder do |node|
36                 if (node.class == target.class) && (node.match?(target))
37                         if (node.parent != nil)
38                                 node.replace_with(replacements)
39                         else
40                                 return replacements
41                         end
42                         return self
43                 end
44         end
45         return self
46 end
size(variable_name) click to toggle source

This method returns the sizes of a variable as defined at the initialization of the array. There are multiple possibilities:

  • Static arrays (e.g. int array)

  • Static arrays with defines (e.g. int input[N2])

  • Variable length arrays (e.g. float temp[m])

  • Dynamically allocated arrays (e.g. int *a = (int *)malloc(size*4))

    # File lib/castaddon/node_bones.rb
 81 def size(variable_name)
 82         self.preorder do |node|
 83                 if node.declarator? && node.name == variable_name
 84                         if node.indirect_type
 85                                 if node.indirect_type.array?
 86                                         return node.indirect_type.lengths
 87                                 elsif node.indirect_type.pointer?
 88                                         node.preorder do |inner_node|
 89                                                 if inner_node.call? && inner_node.expr.name == 'malloc'
 90                                                         if !node.indirect_type.type # This is a check to ensure single-pointer only
 91                                                                 string = '('+inner_node.args.to_s+'/sizeof('+node.type.to_s.gsub('*','').strip+'))'
 92                                                                 string.gsub!(/sizeof\(int\)\/sizeof\(int\)/,'1')
 93                                                                 string.gsub!(/sizeof\(unsigned int\)\/sizeof\(unsigned int\)/,'1')
 94                                                                 string.gsub!(/sizeof\(char\)\/sizeof\(char\)/,'1')
 95                                                                 string.gsub!(/sizeof\(unsigned char\)\/sizeof\(unsigned char\)/,'1')
 96                                                                 string.gsub!(/sizeof\(double\)\/sizeof\(double\)/,'1')
 97                                                                 string.gsub!(/sizeof\(float\)\/sizeof\(float\)/,'1')
 98                                                                 return [string]
 99                                                         end
100                                                 end
101                                         end
102                                 end
103                         end
104                 end
105         end
106         return []
107 end
statement?() click to toggle source

This method returns ‘true’ if the node is of the ‘ExpressionStatement’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
280 def statement?
281         return (self.class == C::ExpressionStatement) || (self.class == C::Declaration)
282 end
string?() click to toggle source

This method returns ‘true’ if the node is of the ‘StringLiteral’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
247 def string?
248         return (self.class == C::StringLiteral)
249 end
strip_brackets() click to toggle source

This method is a small helper function which simply strips any outer brackets from a node. If no outer brackets are found, then nothing happens and the node itself is returned.

   # File lib/castaddon/node_common.rb
62 def strip_brackets
63         return (self.block?) ? self.stmts : self
64 end
subtract?() click to toggle source

This method returns ‘true’ if the node is of the ‘Subtract’ class. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
193 def subtract?
194         return (self.class == C::Subtract)
195 end
transform_flatten(array) click to toggle source

This method transforms multi-dimensional arrays into 1D arrays. The target array variable list is given as argument. The method walks through the node. First, it checks whether:

  • The node represents an array access (node.index?)

  • The node has a parent node (node.parent)

Then, the method loops over all array variables. It then checks two more things:

  • Whether the given name is the same as the name found in the array access node (+node.variable_name == array.name+)

  • Whether the dimensions of the given array are the same as the dimensions of the node (+node.dimension == array.dimension+)

Then, the method is ready to perform the flattening. It first gets the index for the first dimension and then iterates over all remaining dimensions. For those dimensions, the index is multiplied by the size of the previous dimension.

The method performs the transformation on the node itself. Any old data is thus lost.

   # File lib/castaddon/transformations.rb
57 def transform_flatten(array)
58         self.preorder do |node|
59                 if (node.index?) && (node.parent)
60                         if (node.variable_name == array.name) && (node.dimension == array.dimensions)
61                                 
62                                 # Compute the new index
63                                 results = array.species.dimensions.each_with_index.map { |d,n| '('+node.index_at_dimension(n).to_s+')'+array.factors[n] }
64                                 replacement = array.name+'['+results.join(' + ')+']'
65                                 
66                                 # Replace the node
67                                 node.replace_with(C::Index.parse(replacement))
68                         end
69                 end
70         end
71 end
transform_merge_threads(amount,excludes) click to toggle source

Method to merge the computations of multiple threads.

    # File lib/castaddon/transformations.rb
130 def transform_merge_threads(amount,excludes)
131         self.preorder do |node|
132                 if node.statement?
133                         replacement = C::NodeArray.new
134                         amount.times do |i|
135                                 replacement.push(node.clone.rename_variables('_m'+i.to_s,excludes))
136                         end
137                         node.replace_with(replacement)
138                 end
139         end
140 end
transform_reduction(input_variable,shared_variable,id) click to toggle source

This method provides the transformations necessary to perform reduction type of operations. The transformations involved in this function are on variable names and index locations. The argument id specifies which transformation to be performed.

Accepted inputs at this point: 2, 3 and 4 (CUDA/OPENCL) Also accepted input: 8 (CUDA), 9 (OPENCL) (to create an atomic version of the code) TODO: Complete the atomic support, e.g. add support for multiplications and ternary operators

    # File lib/castaddon/transformations.rb
158 def transform_reduction(input_variable,shared_variable,id)
159         
160         # Pre-process assign-add type constructions
161         self.preorder do |node|
162                 if node.addassign?
163                         node.replace_with(C::Assign.parse(node.lval.to_s+'='+node.lval.to_s+'+'+node.rval.to_s))
164                 end
165         end
166         
167         # Create atomic code
168         if id == 8 || id == 9
169                 function_name = (id == 8) ? 'atomicAdd' : 'atomic_add'
170                 self.preorder do |node|
171                         if node.assign?
172                                 if node.lval.index? && node.lval.variable_name == shared_variable.name
173                                         if node.rval.add?
174                                                 if node.rval.expr1.variable_name == shared_variable.name
175                                                         node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr1.to_s+','+node.rval.expr2.to_s+')'))
176                                                 elsif node.rval.expr2.variable_name == shared_variable.name
177                                                         node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr2.to_s+','+node.rval.expr1.to_s+')'))
178                                                 end
179                                         elsif node.rval.subtract?
180                                                 if node.rval.expr1.variable_name == shared_variable.name
181                                                         node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr1.to_s+',-'+node.rval.expr2.to_s+')'))
182                                                 elsif node.rval.expr2.variable_name == shared_variable.name
183                                                         node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr2.to_s+',-'+node.rval.expr1.to_s+')'))
184                                                 end
185                                         elsif node.assign?
186                                                 
187                                         else
188                                                 raise_error('Unsupported atomic reduction operator: '+node.rval.type.inspect)
189                                         end
190                                 end
191                         end
192                 end
193                 return self
194         else
195         
196                 # Split the statement into an operation, the input, and the output
197                 results = []
198                 operation = self.stmts[0].expr.rval.class
199                 [self.stmts[0].expr.rval.expr1.detach,self.stmts[0].expr.rval.expr2.detach].each do |nodes|
200                         nodes.preorder do |node|
201                                 if (node.index?)
202                                         results[0] = nodes if node.variable_name == input_variable.name
203                                         results[1] = nodes if node.variable_name == shared_variable.name
204                                 end
205                         end
206                 end
207                 
208                 # Process the input part
209                 results[0].preorder do |node|
210                         if (node.index?) && (node.variable_name == input_variable.name)
211                                 temporary = C::Variable.parse(Bones::VARIABLE_PREFIX+'temporary')
212                                 results[0] = C::Index.parse(Bones::LOCAL_MEMORY+'['+Bones::VARIABLE_PREFIX+'offset_id]') if id == 3
213                                 results[0] = temporary if id == 5
214                                 if id == 2 || id == 4
215                                         if node.parent
216                                                 node.replace_with(temporary)
217                                         else
218                                                 results[0] = temporary
219                                         end
220                                 end
221                         end
222                 end
223                 
224                 # Process the output part
225                 results[1] = C::Variable.parse(Bones::PRIVATE_MEMORY)                          if id == 2 || id == 5
226                 results[1] = C::Index.parse(Bones::LOCAL_MEMORY+'['+Bones::LOCAL_ID+']')       if id == 3
227                 results[1] = '0'                                                               if id == 4
228                 
229                 # Merge the results together with the operation
230                 return C::Expression.parse(results[1].to_s+'+'+results[0].to_s) if id == 3 || id == 5
231                 case operation.to_s
232                         when 'C::Add'      then return C::Expression.parse(results[1].to_s+'+'+results[0].to_s)
233                         when 'C::Subtract' then return C::Expression.parse(results[1].to_s+'-'+results[0].to_s)
234                         else raise_error('Unsupported reduction operation '+operation.to_s+'.')
235                 end
236         end
237 end
transform_shuffle(arrays) click to toggle source

Method to shuffle a 2D array access (e.g. transform from A[j] into A[i]).

    # File lib/castaddon/transformations.rb
113 def transform_shuffle(arrays)
114         arrays.each do |array|
115         
116                 # Change the variable names
117                 self.stmts.preorder do |node|
118                         if (node.index?) && (node.parent)
119                                 if node.variable_name == array.name && node.expr.index?
120                                         replacement = node.variable_name.to_s+'['+node.index.to_s+']['+node.expr.index.to_s+']'
121                                         node.replace_with(C::Index.parse(replacement))
122                                 end
123                         end
124                 end
125         
126         end
127 end
transform_substitution(array,inout) click to toggle source

Method to transform array accesses into register accesses. This is only valid for the local loop body and could have been done by the actual compiler in a number of cases.

    # File lib/castaddon/transformations.rb
 76 def transform_substitution(array,inout)
 77         replacement = 'register_'+array.name
 78         original_name = ''
 79         
 80         # Change the variable names
 81         self.stmts.preorder do |node|
 82                 if (node.index?) && (node.parent)
 83                         
 84                         # First time replacement
 85                         if original_name == ''
 86                                 if node.variable_name == array.name
 87                                         node.replace_with(C::Variable.parse(replacement))
 88                                         original_name = node.to_s
 89                                 end
 90                                 
 91                         # Second, third, etc. replacement
 92                         else
 93                                 if original_name == node.to_s
 94                                         node.replace_with(C::Variable.parse(replacement))
 95                                 end
 96                         end
 97                 end
 98         end
 99         
100         # Add prologue and epilogue code
101         if original_name != ''
102                 if inout
103                         self.stmts[0].insert_prev(C::Declaration.parse(array.type_name+' '+replacement+'='+original_name+';'))
104                 else
105                         self.stmts[0].insert_prev(C::Declaration.parse(array.type_name+' '+replacement+';'))
106                 end
107                 self.stmts[self.stmts.length-1].insert_next(C::ExpressionStatement.parse(original_name+' = '+replacement+';'))
108         end
109 end
transform_use_local_memory(arrays) click to toggle source

Method to enable the use of local memory for a list of array variables which is given as an argument to the method. The method walks through the node. First, it checks whether:

  • The node represents an array access (node.index?)

  • The node has a parent node (node.parent)

Then, the method loops over all array variables. It checks one more thing: whether the array variable’s name is the same as the name found in the array access node.

If all conditions are met, the method performs two replacements:

  • The variable name is changed to correspond to local memory

  • The index names are changed to correspond to local indices

The method performs the transformation on the node itself. Any old data is thus lost.

   # File lib/castaddon/transformations.rb
24 def transform_use_local_memory(arrays)
25         self.preorder do |node|
26                 if (node.index?) && (node.parent)
27                         arrays.each do |array|
28                                 if node.variable_name == array.name
29                                         node.variable_name = Bones::LOCAL_MEMORY+'_'+array.name
30                                         array.species.dimensions.each_with_index do |dimension,num_dimension|
31                                                 node.replace_variable(Bones::GLOBAL_ID+'_'+num_dimension.to_s,Bones::LOCAL_ID+'_'+num_dimension.to_s)
32                                         end
33                                 end
34                         end
35                 end
36         end
37 end
undefined_variables() click to toggle source

This method returns a list of undefined variables in the node. It walks the node tree until it finds a node that full-fills the following:

  • The node is a variable (node.variable?)

  • The variable is not in a function call (+!node.parent.call?+)

  • The variable is not defined in the code (+!self.variable_type(node.name)+)

    # File lib/castaddon/node_bones.rb
124 def undefined_variables
125         variables = []
126         self.preorder do |node|
127                 variables.push(node.name) if (node.variable?) && (!node.parent.call?) && (!self.variable_type(node.name))
128         end
129         return variables.uniq
130 end
unit_increment?() click to toggle source

This method returns ‘true’ if the node is of the ‘PostInc’, ‘PreInc’ class or if it is of the ‘Assign’ class and adds with a value of 1. Otherwise, it returns ‘false’.

    # File lib/castaddon/node_common.rb
268 def unit_increment?
269         return (self.class == C::PostInc) || (self.class == C::PreInc) || (self.class == C::Assign && self.rval.class == C::Add && self.rval.expr2.class == C::IntLiteral && self.rval.expr2.val == 1)
270 end
variable?() click to toggle source

This method returns ‘true’ if the node is of the ‘Variable’ class. Otherwise, it returns ‘false’.

   # File lib/castaddon/node_common.rb
68 def variable? ; (self.class == C::Variable) end
variable_type(variable_name) click to toggle source

This method returns the type of a variable (e.g. int, float). The method requires the name of a variable as an argument. It first tries to find a declaration for the variable in by walking through the node. If it cannot find it, it will search for a parameter definition from a function call. If that cannot be found either, the method will return ‘nil’, meaning that the variable is not defined at all in the current node.

   # File lib/castaddon/node_bones.rb
65 def variable_type(variable_name)
66         self.preorder do |node|
67                 if node.declarator? || node.parameter?
68                         return node.type if node.name == variable_name
69                 end
70         end
71         return nil
72 end

Private Instance Methods

indent(s, levels=1) click to toggle source

Override the existing ‘indent’ method to set the indent size manually.

    # File lib/castaddon/node_common.rb
289 def indent s, levels=1
290         space = INDENT
291         s.gsub(/^/, space)
292 end