Class: C::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/castaddon/node_bones.rb,
lib/castaddon/node_common.rb,
lib/castaddon/node_adarwin.rb,
lib/castaddon/transformations.rb

Overview

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.

Instance Method Summary collapse

Instance Method Details

#add? ⇒ Boolean

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

Returns:

  • (Boolean) 


181
182
183
 
# File 'lib/castaddon/node_common.rb', line 181

def add?
	return (self.class == C::Add)
end

#addassign? ⇒ Boolean

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

Returns:

  • (Boolean) 


193
194
195
 
# File 'lib/castaddon/node_common.rb', line 193

def addassign?
	return (self.class == C::AddAssign)
end

#alu? ⇒ Boolean

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

Returns:

  • (Boolean) 


268
269
270
 
# File 'lib/castaddon/node_common.rb', line 268

def alu?
	return add? || subtract? || addassign? || postinc? || postdec? || preinc? || predec? || binary_expression?
end

#and? ⇒ Boolean

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

Returns:

  • (Boolean) 


145
146
147
 
# File 'lib/castaddon/node_common.rb', line 145

def and?
	return (self.class == C::And)
end

#array? ⇒ Boolean

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

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/castaddon/node_common.rb', line 72

def array?
	return (self.class == C::Array)
end

#assign? ⇒ Boolean

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

Returns:

  • (Boolean) 


229
230
231
 
# File 'lib/castaddon/node_common.rb', line 229

def assign?
	return (self.class == C::Assign)
end

#assignment_expression? ⇒ Boolean

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

Returns:

  • (Boolean) 


255
256
257
 
# File 'lib/castaddon/node_common.rb', line 255

def assignment_expression?
	return (self.class.superclass == C::AssignmentExpression)
end

#binary_expression? ⇒ Boolean

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

Returns:

  • (Boolean) 


248
249
250
 
# File 'lib/castaddon/node_common.rb', line 248

def binary_expression?
	return (self.class.superclass == C::BinaryExpression)
end

#block? ⇒ Boolean

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

Returns:

  • (Boolean) 


127
128
129
 
# File 'lib/castaddon/node_common.rb', line 127

def block?
	return (self.class == C::Block)
end

#call? ⇒ Boolean

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

Returns:

  • (Boolean) 


108
109
110
 
# File 'lib/castaddon/node_common.rb', line 108

def call?
	return (self.class == C::Call)
end

#declaration? ⇒ Boolean

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

Returns:

  • (Boolean) 


96
97
98
 
# File 'lib/castaddon/node_common.rb', line 96

def declaration?
	return (self.class == C::Declaration)
end

#declarator? ⇒ Boolean

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

Returns:

  • (Boolean) 


90
91
92
 
# File 'lib/castaddon/node_common.rb', line 90

def declarator?
	return (self.class == C::Declarator)
end

#direction(variable_name) ⇒ Object

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.



146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
# File 'lib/castaddon/node_bones.rb', line 146

def direction(variable_name)
	result = {:in => false, :out => false }
	expressions = {:in => [], :out => []}
	output_nodes = []
	self.preorder do |node|
		
		# First find out if the current node actually contains the target variable somewhere
		name_match = false
		node.preorder do |match_node|
			name_match = true if (match_node.variable?) && (match_node.name == variable_name)
		end
		
		# If there is a match and the current node is of an assignment/binary/declarator type, we can start processing
		if (name_match) && (node.assignment_expression? || node.binary_expression? || node.declarator?)
			
			# First find out if this node can be considered an input (see sum/acc/temp register variable problem - chunk/example1 vs chunk/example5)
			possible_input = true
			node.preorder do |test_node|
				output_nodes.each do |output_node|
					possible_input = false if test_node =~ output_node
				end
			end
			
			# Store the node's data in a list (input/output lists are separated)
			if node.assignment_expression?
				output_nodes << node.lval
				expressions[:out] << node.lval.remove_index
				expressions[:in] << node.rval                if possible_input
				if !node.assign?
					expressions[:in] << node.lval              if possible_input
				end
			elsif node.binary_expression?
				expressions[:in] << node.expr1               if possible_input
				expressions[:in] << node.expr2.remove_index  if possible_input
			elsif node.declarator? && node.init
				expressions[:in] << node.init                if possible_input
			end
		end
	end
	
	# Set the result according to the list of nodes
	expressions.each do |key,expression_list|
		expression_list.each do |expression|
			expression.preorder do |node|
				if (node.variable?) && (node.name == variable_name)
					result[key] = true
				end
			end
		end
	end
	
	# Return the result
	return Bones::INOUT if result[:in] && result[:out]
	return Bones::INPUT if result[:in]
	return Bones::OUTPUT if result[:out]
	raise_error('Variable "'+variable_name+'" is neither input nor output')
end

#for_statement? ⇒ Boolean

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

Returns:

  • (Boolean) 


133
134
135
 
# File 'lib/castaddon/node_common.rb', line 133

def for_statement?
	return (self.class == C::For)
end

#function_declaration? ⇒ Boolean

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

Returns:

  • (Boolean) 


121
122
123
 
# File 'lib/castaddon/node_common.rb', line 121

def function_declaration?
	return (self.class == C::Declarator && self.indirect_type.class == C::Function)
end

#function_definition? ⇒ Boolean

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

Returns:

  • (Boolean) 


114
115
116
 
# File 'lib/castaddon/node_common.rb', line 114

def function_definition?
	return (self.class == C::FunctionDef)
end

#get_accesses(accesses = [], loop_data = [], if_statements = []) ⇒ Object

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.



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/castaddon/node_adarwin.rb', line 51

def get_accesses(accesses = [],loop_data = [],if_statements = [])
	
	# Iterate over all the nodes
	self.preorder do |node|
		
		# A loop has been found. Proceed as follows: 1) store the loop data, 2)
		# call this method recursively on the loop body, and 3) remove the loop
		# body from the node.
		if node.for_statement? && node.stmt
			next_loop_data = loop_data.clone
			next_loop_data.push(node.get_single_loop)
			node.stmt.clone.get_accesses(accesses,next_loop_data,if_statements)
			node.remove_node(node.stmt)
		
		# An if-statement has been found. Proceed as follows: 1) store the (one or
		# more) if-statement conditions, 2) call this method recursively on the
		# if-statement body, and 3) remove the if-statement body from the node.
		elsif node.if_statement?
			next_if_statements = if_statements.clone
			node.cond.get_conditions().each do |condition|
				next_if_statements.push(condition)
			end
			node.then.clone.get_accesses(accesses,loop_data,next_if_statements)
			node.remove_node(node.then)
		
		# We haven't found an if-statement or loop in the current node, so it
		# implies that we can search for an array reference.
		# TODO: Array references as part of conditions or bounds of loops are not
		# found in this way.
		else
		
			# Collect all the writes we have seen so far. This is used to check for
			# references that are 'register' references because they have been
			# written before.
			writes = accesses.map{ |e| e[:access] if e[:type] == 'write' }.flatten
			
			# Collect the potential references
			to_search = []
			if node.assignment_expression?
				to_search << [node.lval,'write',true]
				to_search << [node.lval,'read',false] if !node.assign?
				to_search << [node.rval,'read',false]
			elsif node.binary_expression?
				to_search << [node.expr1,'read',false]
				to_search << [node.expr2,'read',false]
			elsif node.declarator? && node.init
				to_search << [node.init,'read',false]
			end
			
			# Process the potential references into 'accesses' hashes
			to_search.each do |item|
				if item[2] || (writes & item[0].get_index_nodes().flatten).empty?
					item[0].get_index_nodes().each do |access|
						accesses << {
							:access => access,
							:name => access.get_array_name(),
							:indices => access.get_indices(),
							:type => item[1],
							:loop_data => loop_data,
							:if_statements => if_statements
						}
					end
				end
			end
		end
	end
	
	# Return the array references as hashes
	return accesses.uniq
end

#get_all_loops ⇒ Object

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.



202
203
204
205
206
207
208
 
# File 'lib/castaddon/node_adarwin.rb', line 202

def get_all_loops()
	loops = []
	self.preorder do |node|
		loops << node.get_single_loop() if node.for_statement?
	end
	return loops
end

#get_array_name ⇒ Object

This method retrieves the name of the array reference.



231
232
233
234
235
 
# File 'lib/castaddon/node_adarwin.rb', line 231

def get_array_name()
	self.preorder do |node|
		return node.expr.to_s if node.index? && !node.expr.index?
	end
end

#get_complexity ⇒ Object

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



49
50
51
52
53
54
55
 
# File 'lib/castaddon/node_bones.rb', line 49

def get_complexity
	count = 0
	self.preorder do |node|
		count += 1 if node.alu?
	end
	return count
end

#get_conditions(results = []) ⇒ Object

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?



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/castaddon/node_adarwin.rb', line 126

def get_conditions(results=[])
	
	# Recursive call for 'And' (&&) and 'or' (||) compound conditions
	if and? || or?
		expr1.get_conditions(results)
		expr2.get_conditions(results)
		
	# Greater than or equal (>=)
	elsif more_or_equal?
		results << [simplify("#{expr1}")+'='+simplify("(#{expr2})"),'']
		
	# Greater than (>)
	elsif more?
		results << [simplify("#{expr1}")+'='+simplify("(#{expr2})+1"),'']
		
	# Less than or equal (<=)
	elsif less_or_equal?
		results << ['',simplify("#{expr1}")+'='+simplify("(#{expr2})")]
		
	# Less than (<)
	elsif less?
		results << ['',simplify("#{expr1}")+'='+simplify("(#{expr2})-1")]
		
	# Unsupported conditions
	else
		raise_error("Unsupported if-condition: #{self.to_s}")
	end
end

#get_direct_loops(loop_data = []) ⇒ Object

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.



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/castaddon/node_adarwin.rb', line 12

def get_direct_loops(loop_data = [])
	
	# Retrieve the next loop
	new_loop = get_single_loop()
	
	# Don't continue if the loop is independent of the writes in the code. This
	# is part of the selection process of what loops to be considered inner or
	# outer loops.
	if loop_data.length > 0
		written_indices = self.clone.get_accesses().map do |a|
			(a[:type] == "write") ? a[:indices].map{ |i| i.to_s } : []
		end
		if !written_indices.flatten.uniq.include?(new_loop[:var])
			return loop_data
		end
	end
	
	# Push the new loop into the array
	loop_data.push(new_loop)
	
	# Check whether the current is actually a loop.
	# TODO: Is this check really needed or is this just a safety net?
	if self.for_statement? && self.stmt
		body = self.stmt.stmts
		
		# Check whether or not there is another loop directly following and make
		# sure that the body is not empty.
		if body.length == 1 && body.first.for_statement?
			body.first.get_direct_loops(loop_data)
		end
	end
	
	# Return all the loop data
	return loop_data
end

#get_functions ⇒ Object

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.



33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/castaddon/node_bones.rb', line 33

def get_functions
	includes_main = false
	function_list = []
	self.preorder do |node|
		if node.function_definition?
			function_list.push(node)
			includes_main = true if (node.name == 'main' || node.name == Bones::VARIABLE_PREFIX+'main')
		end
	end
	raise_error('No "main"-function detected in the input file') if !includes_main
	return function_list
end

#get_index_nodes ⇒ Object

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.



213
214
215
216
217
218
219
 
# File 'lib/castaddon/node_adarwin.rb', line 213

def get_index_nodes()
	nodes = []
	self.preorder do |node|
		nodes << node if node.index? && !node.parent.index?
	end
	return nodes
end

#get_indices ⇒ Object

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



222
223
224
225
226
227
228
 
# File 'lib/castaddon/node_adarwin.rb', line 222

def get_indices()
	indices = []
	self.postorder do |node|
		indices << node.index if node.index?
	end
	return indices
end

#get_single_loop ⇒ Object

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?



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/castaddon/node_adarwin.rb', line 159

def get_single_loop()
	loop_datum = { :var => '', :min => '', :max => '', :step => ''}
	if self.for_statement?
		
		# Get the loop start condition and the loop variable.
		# TODO: Add support for other types of initialisations, e.g. a declaration
		if self.init.assign?
			loop_datum[:var] = self.init.lval.name
			loop_datum[:min] = self.init.rval.get_value.to_s
		elsif self.init.declaration?
			loop_datum[:var] = self.init.declarators.first.name
			loop_datum[:min] = self.init.declarators.first.init.to_s
		else
			raise_error("Unsupported loop initialization: #{self.init}")
		end
		
		# Get the loop's upper-bound condition.
		# TODO: Add support for the unsupported cases.
		var_is_on_left = (self.cond.expr1.get_value == loop_datum[:var])
		loop_datum[:max] = case
			when self.cond.less? then (var_is_on_left) ? simplify("#{self.cond.expr2.get_value}-1") : "unsupported"
			when self.cond.more? then (var_is_on_left) ? "unsupported" : simplify("#{self.cond.expr1.get_value}-1")
			when self.cond.less_or_equal? then (var_is_on_left) ? "#{self.cond.expr2.get_value}" : "unsupported"
			when self.cond.more_or_equal? then (var_is_on_left) ? "unsupported" : "#{self.cond.expr1.get_value}"
		end
		raise_error("Unsupported loop condition: #{self.cond}") if loop_datum[:max] == "unsupported"
		
		# Get the loop iterator.
		# TODO: Investigate whether we can handle non-basic cases
		iterator = self.iter.to_s
		loop_datum[:step] = case iterator
			when "#{loop_datum[:var]}++" then '1'
			when "++#{loop_datum[:var]}" then '1'
			when "#{loop_datum[:var]}--" then '-1'
			when "--#{loop_datum[:var]}" then '-1'
			else simplify(self.iter.rval.to_s.gsub(loop_datum[:var],'0'))
		end
	end
	return loop_datum
end

#get_value ⇒ Object

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).



239
240
241
242
243
 
# File 'lib/castaddon/node_adarwin.rb', line 239

def get_value()
	return self.val if self.intliteral?
	return self.name if self.variable?
	return self.to_s
end

#has_conditional_statements? ⇒ Boolean

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

Returns:

  • (Boolean) 


306
307
308
309
310
311
312
313
 
# File 'lib/castaddon/node_bones.rb', line 306

def has_conditional_statements?
	self.preorder do |node|
		if node.if_statement?
			return true
		end
	end
	return false
end

#if_statement? ⇒ Boolean

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

Returns:

  • (Boolean) 


139
140
141
 
# File 'lib/castaddon/node_common.rb', line 139

def if_statement?
	return (self.class == C::If)
end

#index? ⇒ Boolean

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

Returns:

  • (Boolean) 


102
103
104
 
# File 'lib/castaddon/node_common.rb', line 102

def index?
	return (self.class == C::Index)
end

#intliteral? ⇒ Boolean

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

Returns:

  • (Boolean) 


223
224
225
 
# File 'lib/castaddon/node_common.rb', line 223

def intliteral?
	return (self.class == C::IntLiteral)
end

#lengths(result = []) ⇒ Object

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’.



112
113
114
115
116
 
# File 'lib/castaddon/node_bones.rb', line 112

def lengths(result = [])
	found = '('+self.length.to_s+')'
	result.push(found)
	return (self.type && self.type.array?) ? self.type.lengths(result) : result
end

#less? ⇒ Boolean

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

Returns:

  • (Boolean) 


157
158
159
 
# File 'lib/castaddon/node_common.rb', line 157

def less?
	return (self.class == C::Less)
end

#less_or_equal? ⇒ Boolean

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

Returns:

  • (Boolean) 


169
170
171
 
# File 'lib/castaddon/node_common.rb', line 169

def less_or_equal?
	return (self.class == C::LessOrEqual)
end

#more? ⇒ Boolean

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

Returns:

  • (Boolean) 


163
164
165
 
# File 'lib/castaddon/node_common.rb', line 163

def more?
	return (self.class == C::More)
end

#more_or_equal? ⇒ Boolean

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

Returns:

  • (Boolean) 


175
176
177
 
# File 'lib/castaddon/node_common.rb', line 175

def more_or_equal?
	return (self.class == C::MoreOrEqual)
end

#node_exists?(target) ⇒ Boolean

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’.

Returns:

  • (Boolean) 


242
243
244
245
246
247
248
249
 
# File 'lib/castaddon/node_bones.rb', line 242

def node_exists?(target)
	self.preorder do |node|
		if (node.class == target.class) && (node.parent != nil) && (node.match?(target))
			return true
		end
	end
	return false
end

#or? ⇒ Boolean

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

Returns:

  • (Boolean) 


151
152
153
 
# File 'lib/castaddon/node_common.rb', line 151

def or?
	return (self.class == C::Or)
end

#parameter? ⇒ Boolean

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

Returns:

  • (Boolean) 


84
85
86
 
# File 'lib/castaddon/node_common.rb', line 84

def parameter?
	return (self.class == C::Parameter)
end

#pointer? ⇒ Boolean

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

Returns:

  • (Boolean) 


78
79
80
 
# File 'lib/castaddon/node_common.rb', line 78

def pointer?
	return (self.class == C::Pointer)
end

#postdec? ⇒ Boolean

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

Returns:

  • (Boolean) 


211
212
213
 
# File 'lib/castaddon/node_common.rb', line 211

def postdec?
	return (self.class == C::PostDec)
end

#postinc? ⇒ Boolean

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

Returns:

  • (Boolean) 


199
200
201
 
# File 'lib/castaddon/node_common.rb', line 199

def postinc?
	return (self.class == C::PostInc)
end

#predec? ⇒ Boolean

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

Returns:

  • (Boolean) 


217
218
219
 
# File 'lib/castaddon/node_common.rb', line 217

def predec?
	return (self.class == C::PreDec)
end

#preinc? ⇒ Boolean

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

Returns:

  • (Boolean) 


205
206
207
 
# File 'lib/castaddon/node_common.rb', line 205

def preinc?
	return (self.class == C::PreInc)
end

#preprocess(conditional = true) ⇒ Object

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).



17
18
19
20
21
22
23
24
25
 
# File 'lib/castaddon/node_bones.rb', line 17

def preprocess(conditional=true)
	self.preorder do |node|
		if node.postinc? || node.preinc?
			node.replace_with(C::AssignmentExpression.parse(node.expr.to_s+' = '+node.expr.to_s+' + 1')) unless conditional && node.parent.for_statement?
		elsif node.postdec? || node.predec?
			node.replace_with(C::AssignmentExpression.parse(node.expr.to_s+' = '+node.expr.to_s+' - 1')) unless conditional && node.parent.for_statement?
		end
	end
end

#remove_index ⇒ Object

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.



296
297
298
299
300
301
302
 
# File 'lib/castaddon/node_bones.rb', line 296

def remove_index
	node_clone = self.clone
	node_clone.preorder do |node|
		node.index.detach if node.index?
	end
	return node_clone
end

#remove_loop(from, to) ⇒ Object

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.



213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/castaddon/node_bones.rb', line 213

def remove_loop(from,to)
	self.preorder do |node|
		if node.for_statement?
			from_statement = (node.init.assign?) ? node.init.rval : node.init.declarators[0].init
			from_loop = (from_statement.variable?) ? from_statement.name : from_statement.to_s
			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)
			to_loop = to_loop.gsub(/\s/,'')
			to_loop = '('+to_loop+')-1' if node.cond.less?
			to_loop = simplify(to_loop)
			from_loop = simplify(from_loop)
			puts Bones::WARNING+'The loop iterator starts at: "'+from_loop+'" (expected "'+from+'")' if from_loop != from
			puts Bones::WARNING+'The loop iterator ends at: "'+to_loop+'" (expected "'+to+'")' if to_loop != to
			raise_error('The loop increment must be 1') if !(node.iter.unit_increment?)
			name = (node.init.assign?) ? node.init.lval.name : node.init.declarators.first.name
			return node.stmt, name
		end
	end
	raise_error('Unexpected number of for-loops')
end

#remove_once(target) ⇒ Object

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



49
50
51
52
53
54
55
56
57
 
# File 'lib/castaddon/node_common.rb', line 49

def remove_once(target)
	self.postorder do |node|
		if node == target
			node.detach
			return self
		end
	end
	return self
end

#rename_variables(suffix, excludes) ⇒ Object 



141
142
143
144
145
146
147
 
# File 'lib/castaddon/transformations.rb', line 141

def rename_variables(suffix,excludes)
	self.preorder do |node|
		if (node.variable? || node.declarator?) && !(excludes.include?(node.name)) && (!node.parent.call?)
			node.name = node.name+suffix
		end
	end
end

#replace_variable(variable_name, replacement) ⇒ Object

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?+)



13
14
15
16
17
 
# File 'lib/castaddon/node_common.rb', line 13

def replace_variable(variable_name,replacement)
	self.preorder do |node|
		node.name = replacement if (node.variable?) && (node.name == variable_name) && (!node.parent.call?)
	end
end

#search_and_replace_function_call(target, replacements) ⇒ Object

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.



263
264
265
266
267
268
269
270
 
# File 'lib/castaddon/node_bones.rb', line 263

def search_and_replace_function_call(target,replacements)
	self.preorder do |node|
		if (node.class == target.class) && (node.parent.call?) && (node.match?(target))
			node.replace_with(replacements)
		end
	end
	return self
end

#search_and_replace_function_definition(old_name, new_name) ⇒ Object

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.



283
284
285
286
287
288
289
290
 
# File 'lib/castaddon/node_bones.rb', line 283

def search_and_replace_function_definition(old_name,new_name)
	self.preorder do |node|
		if (node.function_definition? || node.function_declaration?) && (node.name == old_name)
			node.name = new_name
		end
	end
	return self
end

#search_and_replace_node(target, replacements) ⇒ Object

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.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/castaddon/node_common.rb', line 31

def search_and_replace_node(target,replacements)
	if (self.class == target.class) && (self.match?(target))
		return replacements
	end
	self.preorder do |node|
		if (node.class == target.class) && (node.match?(target))
			if (node.parent != nil)
				node.replace_with(replacements)
			else
				return replacements
			end
			return self
		end
	end
	return self
end

#size(variable_name) ⇒ Object

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))



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/castaddon/node_bones.rb', line 81

def size(variable_name)
	self.preorder do |node|
		if node.declarator? && node.name == variable_name
			if node.indirect_type
				if node.indirect_type.array?
					return node.indirect_type.lengths
				elsif node.indirect_type.pointer?
					node.preorder do |inner_node|
						if inner_node.call? && inner_node.expr.name == 'malloc'
							if !node.indirect_type.type # This is a check to ensure single-pointer only
								string = '('+inner_node.args.to_s+'/sizeof('+node.type.to_s.gsub('*','').strip+'))'
								string.gsub!(/sizeof\(int\)\/sizeof\(int\)/,'1')
								string.gsub!(/sizeof\(unsigned int\)\/sizeof\(unsigned int\)/,'1')
								string.gsub!(/sizeof\(char\)\/sizeof\(char\)/,'1')
								string.gsub!(/sizeof\(unsigned char\)\/sizeof\(unsigned char\)/,'1')
								string.gsub!(/sizeof\(double\)\/sizeof\(double\)/,'1')
								string.gsub!(/sizeof\(float\)\/sizeof\(float\)/,'1')
								return [string]
							end
						end
					end
				end
			end
		end
	end
	return []
end

#statement? ⇒ Boolean

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

Returns:

  • (Boolean) 


274
275
276
 
# File 'lib/castaddon/node_common.rb', line 274

def statement?
	return (self.class == C::ExpressionStatement) || (self.class == C::Declaration)
end

#string? ⇒ Boolean

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

Returns:

  • (Boolean) 


241
242
243
 
# File 'lib/castaddon/node_common.rb', line 241

def string?
	return (self.class == C::StringLiteral)
end

#strip_brackets ⇒ Object

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.



62
63
64
 
# File 'lib/castaddon/node_common.rb', line 62

def strip_brackets
	return (self.block?) ? self.stmts : self
end

#subtract? ⇒ Boolean

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

Returns:

  • (Boolean) 


187
188
189
 
# File 'lib/castaddon/node_common.rb', line 187

def subtract?
	return (self.class == C::Subtract)
end

#transform_flatten(array) ⇒ Object

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.



57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/castaddon/transformations.rb', line 57

def transform_flatten(array)
	self.preorder do |node|
		if (node.index?) && (node.parent)
			if (node.variable_name == array.name) && (node.dimension == array.dimensions)
				
				# Compute the new index
				results = array.species.dimensions.each_with_index.map { |d,n| '('+node.index_at_dimension(n).to_s+')'+array.factors[n] }
				replacement = array.name+'['+results.join(' + ')+']'
				
				# Replace the node
				node.replace_with(C::Index.parse(replacement))
			end
		end
	end
end

#transform_merge_threads(amount, excludes) ⇒ Object

Method to merge the computations of multiple threads.



130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/castaddon/transformations.rb', line 130

def transform_merge_threads(amount,excludes)
	self.preorder do |node|
		if node.statement?
			replacement = C::NodeArray.new
			amount.times do |i|
				replacement.push(node.clone.rename_variables('_m'+i.to_s,excludes))
			end
			node.replace_with(replacement)
		end
	end
end

#transform_reduction(input_variable, output_variable, id) ⇒ Object

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



158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/castaddon/transformations.rb', line 158

def transform_reduction(input_variable,output_variable,id)
	
	# Pre-process assign-add type constructions
	if self.stmts[0].expr.addassign?
		self.stmts[0].expr.replace_with(C::Assign.parse(self.stmts[0].expr.lval.to_s+'='+self.stmts[0].expr.lval.to_s+'+'+self.stmts[0].expr.rval.to_s))
	end
	
	# Create atomic code
	if id == 8 || id == 9
		function_name = (id == 8) ? 'atomicAdd' : 'atomic_add'
		self.preorder do |node|
			if node.assign?
				if node.lval.index? && node.lval.variable_name == output_variable.name
					if node.rval.add?
						if node.rval.expr1.variable_name == output_variable.name
							node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr1.to_s+','+node.rval.expr2.to_s+')'))
						elsif node.rval.expr2.variable_name == output_variable.name
							node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr2.to_s+','+node.rval.expr1.to_s+')'))
						end
					elsif node.rval.subtract?
						if node.rval.expr1.variable_name == output_variable.name
							node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr1.to_s+',-'+node.rval.expr2.to_s+')'))
						elsif node.rval.expr2.variable_name == output_variable.name
							node.replace_with(C::Call.parse(function_name+'(&'+node.rval.expr2.to_s+',-'+node.rval.expr1.to_s+')'))
						end
					else
						raise_error('Unsupported atomic reduction operator: '+node.rval.type.inspect)
					end
				end
			end
		end
		return self
	else
	
		# Split the statement into an operation, the input, and the output
		results = []
		operation = self.stmts[0].expr.rval.class
		[self.stmts[0].expr.rval.expr1.detach,self.stmts[0].expr.rval.expr2.detach].each do |nodes|
			nodes.preorder do |node|
				if (node.index?)
					results[0] = nodes if node.variable_name == input_variable.name
					results[1] = nodes if node.variable_name == output_variable.name
				end
			end
		end
		
		# Process the input part
		results[0].preorder do |node|
			if (node.index?) && (node.variable_name == input_variable.name)
				temporary = C::Variable.parse(Bones::VARIABLE_PREFIX+'temporary')
				results[0] = C::Index.parse(Bones::LOCAL_MEMORY+'['+Bones::VARIABLE_PREFIX+'offset_id]') if id == 3
				results[0] = temporary if id == 5
				if id == 2 || id == 4
					if node.parent
						node.replace_with(temporary)
					else
						results[0] = temporary
					end
				end
			end
		end
		
		# Process the output part
		results[1] = C::Variable.parse(Bones::PRIVATE_MEMORY)                          if id == 2 || id == 5
		results[1] = C::Index.parse(Bones::LOCAL_MEMORY+'['+Bones::LOCAL_ID+']')       if id == 3
		results[1] = '0'                                                               if id == 4
		
		# Merge the results together with the operation
		return C::Expression.parse(results[1].to_s+'+'+results[0].to_s) if id == 3 || id == 5
		case operation.to_s
			when 'C::Add'      then return C::Expression.parse(results[1].to_s+'+'+results[0].to_s)
			when 'C::Subtract' then return C::Expression.parse(results[1].to_s+'-'+results[0].to_s)
			else raise_error('Unsupported reduction operation '+operation.to_s+'.')
		end
	end
end

#transform_shuffle(arrays) ⇒ Object

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



113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/castaddon/transformations.rb', line 113

def transform_shuffle(arrays)
	arrays.each do |array|
	
		# Change the variable names
		self.stmts.preorder do |node|
			if (node.index?) && (node.parent)
				if node.variable_name == array.name && node.expr.index?
					replacement = node.variable_name.to_s+'['+node.index.to_s+']['+node.expr.index.to_s+']'
					node.replace_with(C::Index.parse(replacement))
				end
			end
		end
	
	end
end

#transform_substitution(array, inout) ⇒ Object

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.



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/castaddon/transformations.rb', line 76

def transform_substitution(array,inout)
	replacement = 'register_'+array.name
	original_name = ''
	
	# Change the variable names
	self.stmts.preorder do |node|
		if (node.index?) && (node.parent)
			
			# First time replacement
			if original_name == ''
				if node.variable_name == array.name
					node.replace_with(C::Variable.parse(replacement))
					original_name = node.to_s
				end
				
			# Second, third, etc. replacement
			else
				if original_name == node.to_s
					node.replace_with(C::Variable.parse(replacement))
				end
			end
		end
	end
	
	# Add prologue and epilogue code
	if original_name != ''
		if inout
			self.stmts[0].insert_prev(C::Declaration.parse(array.type_name+' '+replacement+'='+original_name+';'))
		else
			self.stmts[0].insert_prev(C::Declaration.parse(array.type_name+' '+replacement+';'))
		end
		self.stmts[self.stmts.length-1].insert_next(C::ExpressionStatement.parse(original_name+' = '+replacement+';'))
	end
end

#transform_use_local_memory(arrays) ⇒ Object

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.



24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/castaddon/transformations.rb', line 24

def transform_use_local_memory(arrays)
	self.preorder do |node|
		if (node.index?) && (node.parent)
			arrays.each do |array|
				if node.variable_name == array.name
					node.variable_name = Bones::LOCAL_MEMORY+'_'+array.name
					array.species.dimensions.each_with_index do |dimension,num_dimension|
						node.replace_variable(Bones::GLOBAL_ID+'_'+num_dimension.to_s,Bones::LOCAL_ID+'_'+num_dimension.to_s)
					end
				end
			end
		end
	end
end

#undefined_variables ⇒ Object

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)+)



124
125
126
127
128
129
130
 
# File 'lib/castaddon/node_bones.rb', line 124

def undefined_variables
	variables = []
	self.preorder do |node|
		variables.push(node.name) if (node.variable?) && (!node.parent.call?) && (!self.variable_type(node.name))
	end
	return variables.uniq
end

#unit_increment? ⇒ Boolean

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’.

Returns:

  • (Boolean) 


262
263
264
 
# File 'lib/castaddon/node_common.rb', line 262

def unit_increment?
	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)
end

#variable? ⇒ Boolean

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

Returns:

  • (Boolean) 


68
 
# File 'lib/castaddon/node_common.rb', line 68

def variable? ; (self.class == C::Variable) end

#variable_type(variable_name) ⇒ Object

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.



65
66
67
68
69
70
71
72
 
# File 'lib/castaddon/node_bones.rb', line 65

def variable_type(variable_name)
	self.preorder do |node|
		if node.declarator? || node.parameter?
			return node.type if node.name == variable_name
		end
	end
	return nil
end