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:
-
Methods starting with
transform_
, handling the major code transformations. -
Methods to obtain information on variables, such as their direction and whether they are defined or not.
-
Helper methods, among others those that indicate whether a node is of a certain class.
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:
-
Methods starting with
transform_
, handling the major code transformations. -
Methods to obtain information on variables, such as their direction and whether they are defined or not.
-
Helper methods, among others those that indicate whether a node is of a certain class.
Public Instance Methods
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
# 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
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
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
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
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
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)
-
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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