1#!/usr/bin/env ruby 2 3# Copyright (c) 2021-2022 Huawei Device Co., Ltd. 4# Licensed under the Apache License, Version 2.0 (the "License"); 5# you may not use this file except in compliance with the License. 6# You may obtain a copy of the License at 7# 8# http://www.apache.org/licenses/LICENSE-2.0 9# 10# Unless required by applicable law or agreed to in writing, software 11# distributed under the License is distributed on an "AS IS" BASIS, 12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13# See the License for the specific language governing permissions and 14# limitations under the License. 15 16require_relative 'basic_block' 17require_relative 'instruction' 18require_relative 'output' 19require_relative 'options' 20require_relative 'regmask' 21 22class CfBlock 23 attr_accessor :bb, :head_bb, :goto 24 attr_reader :kind, :depth 25 26 module Kind 27 IfThen = 0 28 IfElse = 1 29 While = 2 30 end 31 32 def initialize(kind, depth) 33 @kind = kind 34 @depth = depth 35 @head_bb = nil 36 @bb = nil 37 @goto = false 38 end 39 40 def set_succ(bb) 41 if @kind == Kind::While 42 @bb.set_false_succ(bb) 43 else 44 @bb.set_true_succ(bb) 45 end 46 end 47 48 def self.get_kind(inst) 49 @@opc_map ||= { If: Kind::IfThen, IfImm: Kind::IfThen, Else: Kind::IfElse, While: Kind::While, AddOverflow: Kind::IfThen, SubOverflow: Kind::IfThen } 50 @@opc_map[inst.opcode] 51 end 52end 53 54class UnresolvedVar 55 attr_reader :name 56 attr_accessor :inst 57 58 def initialize(name) 59 @name = name.to_sym 60 @inst = nil 61 end 62end 63 64class Label 65 attr_reader :refs, :name 66 attr_accessor :bb 67 68 def initialize(name, bb=nil) 69 @name = name 70 @bb = bb 71 @refs = [] 72 end 73end 74 75class Function 76 77 attr_reader :name, :mode, :validation, :enable_builder, :external_funcs, :arguments, :params, :constants, :basic_blocks 78 79 def initialize(name, params: {}, regmap: {}, mode: nil, regalloc_set: nil, regalloc_include: nil, regalloc_exclude: nil, 80 validate: nil, enable_builder: false, lang: 'PANDA_ASSEMBLY', &block) 81 @name = name 82 @mode = mode 83 @lang = lang 84 @regalloc_mask = regalloc_set ? regalloc_set : $default_mask 85 @regalloc_mask |= regalloc_include unless regalloc_include.nil? 86 @regalloc_mask &= ~regalloc_exclude unless regalloc_exclude.nil? 87 88 @instructions = [] 89 @basic_blocks = [] 90 @locals = {} 91 @current_depth = 0 92 @unresolved = {} 93 @cf_stack = [] 94 @labels = {} 95 if validate 96 @validation = Hash[validate.map {|k, v| [k, ((v.is_a?(Hash)) ? v[Options.arch] : v)] } ] 97 @validation.each { |name, v| raise "#{@name}: no target arch in validation value: #{name}" unless v } 98 end 99 @body = block 100 @external_funcs = [] 101 @enable_builder = enable_builder 102 103 self.define_singleton_method(:regmap) { regmap } 104 # Lists of special/global instructions 105 @arguments = [] 106 @registers = {} 107 @constants = {} 108 109 new_basic_block() 110 111 # Process function's arguments 112 @params = params 113 params.each_with_index do |(name, type), i| 114 inst = create_instruction(:Parameter) 115 inst.send(type) 116 inst.set_parameter_index(i) 117 @arguments << inst 118 let(name, inst) 119 end 120 end 121 122 # Return true if graph doesn't contain conditional basic block, i.e. with more than one successor. 123 def simple_control_flow? 124 @result ||= @basic_blocks.none? { |bb| bb.true_succ && bb.false_succ } 125 end 126 127 def compile 128 Options.compiling = true 129 instance_eval &@body 130 Options.compiling = false 131 resolve_variables 132 @basic_blocks.delete_if { |bb| bb.empty? && bb.preds.empty? } 133 end 134 135 def defines 136 Options.definitions 137 end 138 139 def create_instruction(opcode, inputs = []) 140 if opcode == :WhilePhi 141 raise "Wrong place of `WhilePhi` instruction" unless @cf_stack[-1].kind == CfBlock::Kind::While 142 raise "Invalid `While` block" if @cf_stack[-1].head_bb.nil? 143 block = @cf_stack[-1].head_bb 144 else 145 block = @current_block 146 end 147 inst = IRInstruction.new(opcode, inst_index(), block) 148 inst.add_inputs(inputs.map { |input| 149 (input.is_a? Integer or input.is_a? Float or input.is_a? String) ? get_or_create_constant(input) : input 150 }) 151 @instructions << inst unless inst.IsElse? 152 block.append inst unless inst.global? 153 inst 154 end 155 156 def get_or_create_constant(value) 157 constant = @constants[value] 158 return @constants[value] unless constant.nil? 159 @constants[value] = IRInstruction.new(:Constant, inst_index(), @current_block, Value: value).i64 160 end 161 162 def let(var_name, inst) 163 if inst.is_a? Integer or inst.is_a? String 164 inst = get_or_create_constant(inst) 165 end 166 resolved = @unresolved[var_name.to_sym] 167 if resolved 168 raise "Unresolved variable is defined more than once: #{var_name}" unless resolved.inst.nil? 169 resolved.inst = inst 170 end 171 @locals[var_name.to_sym] = inst 172 self.define_singleton_method(var_name.to_sym) do 173 @locals[var_name.to_sym] 174 end 175 inst 176 end 177 178 def inst_index 179 @inst_index ||= 0 180 @inst_index += 1 181 @inst_index - 1 182 end 183 184 def method_missing(method, *args, &block) 185 if Options.compiling && args.empty? && block.nil? 186 method = method.to_sym 187 var = UnresolvedVar.new(method) 188 @unresolved[method] = var 189 var 190 else 191 super 192 end 193 end 194 195 def generate 196 Output.printlni("COMPILE(#{@name}) {") 197 raise "Compilation mode is not specified" unless @mode 198 Output.println("if(GetGraph()->GetArch() != #{Options.cpp_arch}) LOG(FATAL, IRTOC) << \"Arch doesn't match\";") 199 Output.println("GetGraph()->SetRelocationHandler(this);") 200 Output.println("SetLanguage(compiler::SourceLanguage::#{@lang});") 201 Output.println("[[maybe_unused]] auto *graph = GetGraph();") 202 Output.println("[[maybe_unused]] auto *runtime = GetGraph()->GetRuntime();") 203 if @mode 204 ss = "GetGraph()->SetMode(GraphMode(0)" 205 @mode.each do |m| 206 ss += " | GraphMode::#{m.to_s}(true)" 207 end 208 ss += ");" 209 Output.println(ss) 210 end 211 Output.println("GetGraph()->SetArchUsedRegs(~0x#{@regalloc_mask.value.to_s(16)});") if @regalloc_mask 212 Output.println(%Q[SetExternalFunctions({"#{@external_funcs.join('", "')}"});]) if @external_funcs 213 Output.printlni("GRAPH(GetGraph()) {") 214 @arguments.each { |inst| inst.emit_ir } 215 @constants.each { |_, inst| inst.emit_ir } 216 @registers.each { |_, inst| inst.emit_ir } 217 @basic_blocks.each {|bb| bb.emit_ir } 218 Output.printlnd("}") 219 Output.printlnd("}") 220 end 221 222 def generate_builder 223 params = "Graph* graph, [[maybe_unused]] InstBuilder *inst_builder, BasicBlock** cur_bb, #{@params.keys.map.with_index { |_, i| "Inst* p_#{i}" }.join(', ')}" 224 params += ', ' unless @params.empty? 225 params += 'size_t pc, Marker marker' 226 Output.println("// NOLINTNEXTLINE(readability-function-size)") 227 Output.printlni("[[maybe_unused]] static Inst* Build#{@name}(#{params}) {") 228 Output.println("[[maybe_unused]] auto *runtime = graph->GetRuntime();") 229 @constants.each { |_, inst| inst.generate_builder } 230 Output.println("auto need_new_last_bb = (*cur_bb)->IsEmpty(); // create an empty BB or extract from an existing one?") 231 Output.println("auto* bb_#{@basic_blocks.last.index} = need_new_last_bb ? graph->CreateEmptyBlock() : (*cur_bb)->SplitBlockAfterInstruction((*cur_bb)->GetLastInst(), false);") 232 Output.println("ASSERT(bb_#{@basic_blocks.last.index}->GetGuestPc() == INVALID_PC);") 233 Output.println("bb_#{@basic_blocks.last.index}->SetGuestPc(pc);") 234 Output.println("bb_#{@basic_blocks.last.index}->CopyTryCatchProps(*cur_bb);") 235 Output.println("if ((*cur_bb)->IsMarked(marker)) {") 236 Output.println(" bb_#{@basic_blocks.last.index}->SetMarker(marker);") 237 Output.println("}") 238 Output.println("if ((*cur_bb)->IsLoopPreHeader()) {") 239 Output.println(" auto *loop = (*cur_bb)->GetNextLoop();") 240 Output.println(" (*cur_bb)->SetNextLoop(nullptr);") 241 Output.println(" loop->SetPreHeader(bb_#{@basic_blocks.last.index});") 242 Output.println(" bb_#{@basic_blocks.last.index}->SetNextLoop(loop);") 243 Output.println("}") 244 Output.println("if (need_new_last_bb) {") 245 Output.println(" for (auto succ : (*cur_bb)->GetSuccsBlocks()) {") 246 Output.println(" succ->ReplacePred(*cur_bb, bb_#{@basic_blocks.last.index});") 247 Output.println(" }") 248 Output.println(" (*cur_bb)->GetSuccsBlocks().clear();") 249 Output.println("}") 250 @basic_blocks[0...-1].each { |bb| 251 Output.println("auto* bb_#{bb.index} = graph->CreateEmptyBlock();") 252 Output.println("ASSERT(bb_#{bb.index}->GetGuestPc() == INVALID_PC);") 253 Output.println("bb_#{bb.index}->SetGuestPc(pc);") 254 Output.println("bb_#{bb.index}->CopyTryCatchProps(*cur_bb);") 255 Output.println("if ((*cur_bb)->IsMarked(marker)) {") 256 Output.println(" bb_#{bb.index}->SetMarker(marker);") 257 Output.println("}") 258 } if @basic_blocks.size > 1 259 Output.println("(*cur_bb)->AddSucc(bb_#{@basic_blocks.first.index});") 260 @basic_blocks.each do |bb| 261 name = "bb_#{bb.index}" 262 Output.println("#{name}->AddSucc(bb_#{bb.true_succ.index});") if bb.true_succ 263 Output.println("#{name}->AddSucc(bb_#{bb.false_succ.index});") if bb.false_succ 264 end 265 Output.printlni('if ((*cur_bb)->GetLoop() != nullptr) {') 266 Output.printlni('if (need_new_last_bb) {') 267 Output.println("(*cur_bb)->GetLoop()->AppendBlock(bb_#{@basic_blocks.last.index});") 268 Output.printlnd('}') 269 @basic_blocks[0...-1].each { |bb| Output.println("(*cur_bb)->GetLoop()->AppendBlock(bb_#{bb.index});") } 270 Output.printlnd('}') 271 Output.println("(*cur_bb) = bb_#{@basic_blocks.last.index};") 272 @basic_blocks.each(&:generate_builder) 273 Output.printlnd('}') 274 end 275 276 def self.setup 277 InstructionsData.instructions.each do |name, dscr| 278 # Some of the opcodes were already defined manually, e.g. Intrinsic 279 next if method_defined? name 280 281 define_method(name) do |*inputs, &block| 282 raise "Current basic block is nil" if @current_block.nil? 283 inst = create_instruction(name, inputs) 284 inst.annotation = Kernel.send(:caller)[0].split(':in')[0] 285 process_inst(inst, &block) 286 inst 287 end 288 end 289 end 290 291 def Intrinsic(name, *inputs) 292 inst = create_instruction(:Intrinsic, inputs).IntrinsicId("RuntimeInterface::IntrinsicId::INTRINSIC_#{name}") 293 process_inst(inst) 294 inst 295 end 296 297 def Label(name) 298 last_bb = @current_block 299 new_basic_block 300 last_bb.set_true_succ(@current_block) if last_bb.true_succ.nil? && !last_bb.terminator? 301 label = @labels[name] 302 if label 303 label.bb = @current_block 304 label.refs.each { |bb| bb.set_true_succ(@current_block) } 305 else 306 @labels[name] = Label.new(name, @current_block) 307 end 308 end 309 310 def Goto(name) 311 if @labels.key? name 312 label = @labels[name] 313 if label.bb 314 @current_block.set_true_succ(label.bb) 315 else 316 label.refs << @current_block 317 end 318 else 319 label = @labels[name] = Label.new(name) 320 label.refs << @current_block 321 end 322 cblock = @cf_stack[-1] 323 cblock.goto = true unless cblock.nil? 324 process_inst nil 325 end 326 327 def LiveIn(value) 328 value = regmap[value] if value.is_a?(Symbol) 329 res = @registers[value] 330 return res unless res.nil? 331 inst = create_instruction(:LiveIn).DstReg(value).ptr 332 @registers[value] = inst 333 end 334 335 def resolve_variables 336 @instructions.each do |inst| 337 inst.inputs.each_with_index do |input, i| 338 if input.is_a? UnresolvedVar 339 raise "Unresolved variable: #{input.name}" if input.inst.nil? 340 inst.inputs[i] = input.inst 341 elsif input.nil? 342 raise "Input is nil for: #{inst}, input" 343 end 344 end 345 end 346 347 @unresolved.each_pair do |name, var| 348 raise "Variable cannot be resolved: #{name}" if var.inst.nil? 349 end 350 end 351 352 def get_if_block(else_depth) 353 @cf_stack.reverse.each do |block| 354 return block if block.depth == else_depth && block.kind == CfBlock::Kind::IfThen 355 end 356 raise "`If` block not found" 357 end 358 359 def process_inst(inst, &block) 360 if !block.nil? 361 @current_depth += 1 362 cblock = CfBlock.new(CfBlock::get_kind(inst), @current_depth) 363 cblock.head_bb = @current_block 364 @cf_stack << cblock 365 new_basic_block() unless @current_block.empty? 366 367 if inst.IsIf? || inst.IsIfImm? || inst.IsWhile? || inst.IsAddOverflow? || inst.IsSubOverflow? 368 cblock.head_bb.set_true_succ(@current_block) 369 elsif inst.IsElse? 370 get_if_block(@current_depth).head_bb.set_false_succ(@current_block) 371 end 372 373 instance_eval &block 374 @current_depth -= 1 375 376 cblock.bb = @current_block 377 new_basic_block() 378 379 else 380 last_block = @cf_stack[-1] 381 return if !last_block.nil? && @current_depth == last_block.depth && last_block.kind == CfBlock::Kind::IfElse 382 @cf_stack.delete_if do |block| 383 next if block.depth <= @current_depth 384 385 if block.bb.true_succ.nil? 386 if block.kind == CfBlock::Kind::While 387 block.bb.set_true_succ(block.head_bb) 388 else 389 # If last instruction in the block is a terminator(e.g. Return), then don't set true successor, hence it 390 # will point to the end block, that is required by IR design. 391 block.bb.set_true_succ(@current_block) unless !block.bb.empty? && block.bb.last_instruction.terminator? 392 end 393 end 394 395 396 if block.head_bb.false_succ.nil? && (block.kind == CfBlock::Kind::IfThen || block.kind == CfBlock::Kind::While) 397 block.head_bb.set_false_succ(@current_block) 398 end 399 400 true 401 end 402 end 403 end 404 405 def new_basic_block 406 @bb_index ||= 2 407 @current_block = BasicBlock.new(@bb_index, self) 408 @bb_index += 1 409 @basic_blocks << @current_block 410 end 411 412end 413