| /* |
| * Copyright (C) 2012 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "register_allocator.h" |
| #include "lir_function.h" |
| #include "lir_frame_info.h" |
| #include "lir_reg.h" |
| |
| #include "target_register_info.h" |
| |
| #include "logging.h" |
| #include "stl_util.h" |
| |
| namespace art { |
| namespace greenland { |
| |
| void RegisterAllocator::BuildKillInfo(LIRFunction& lir_func) { |
| //TODO: Build Register KillInfo |
| } |
| |
| static LIRBasicBlock::iterator |
| GetSourceIterator(LIRBasicBlock& sourceBB, LIRBasicBlock& targetBB) { |
| LIRBasicBlock::iterator it; |
| for (it = sourceBB.back(); it != sourceBB.begin(); --it) { |
| if (it->IsBranch() && (it->GetOperand(0).GetLabelTarget() == &targetBB)) |
| break; |
| } |
| return it; |
| } |
| |
| void RegisterAllocator::PHIElimination(LIRFunction& lir_func) { |
| for (LIRFunction::iterator bb = lir_func.begin(); bb != lir_func.end(); ++bb) { |
| if (bb->IsEmpty() || !bb->front().IsPHI()) |
| continue; |
| |
| LIRBasicBlock::iterator it; // current LIR |
| LIRBasicBlock::iterator next_it; // next LIR |
| for(it = bb->begin(); it != bb->end(); it = next_it) { |
| next_it = it; ++next_it; |
| if (!it->IsPHI()) |
| break; |
| |
| for (unsigned i = 1; i < it->GetNumOperands(); i+=2) { |
| const LIROperand& dst = it->GetOperand(0); |
| const LIROperand& src = it->GetOperand(i); |
| LIRBasicBlock* sourceBB = |
| const_cast<LIRBasicBlock*> (it->GetOperand(i + 1).GetLabelTarget()); |
| |
| LIR* lir = reg_info_.CreateCopy(lir_func, dst.GetReg(), src); |
| LOG(INFO) << "PHIElimination: Insert COPY into BB: " << sourceBB->GetName(); |
| sourceBB->insert(GetSourceIterator(*sourceBB, *bb), lir); |
| } |
| |
| bb->erase(it); |
| } |
| } |
| } |
| |
| RegisterAllocator::Storage |
| RegisterAllocator::AllocateStorage(LIRFunction &lir_func, unsigned vreg_idx) { |
| // The virtual register is allocated, return it. |
| if (allocated_map_.find(vreg_idx) != allocated_map_.end()) { |
| return allocated_map_[vreg_idx]; |
| } |
| |
| Storage s; |
| // Have free register(s). |
| if (!allocatable_list_.empty()) { |
| s.regTag = kPhyRegType; |
| s.index = allocatable_list_.front(); |
| allocatable_list_.pop_front(); |
| } |
| else { |
| s.regTag = kFrameType; |
| if (stackstorage_list_.empty()) { |
| // FIXME: Get register subword |
| s.index = lir_func.GetFrameInfo().AllocateStackObject(4); |
| } |
| else { |
| s.index = stackstorage_list_.front(); |
| stackstorage_list_.pop_front(); |
| } |
| } |
| allocated_map_[vreg_idx] = s; |
| return s; |
| } |
| |
| void RegisterAllocator::KeepStorage(const LIR& lir) { |
| unsigned reg_value = lir.GetOperand(0).GetReg(); |
| int frame_idx = lir.GetOperand(1).GetFrameIndex(); |
| |
| if (!LIRReg::IsVirtualReg(reg_value)) |
| return; |
| |
| unsigned vreg_idx = LIRReg::GetRegNo(reg_value); |
| |
| LOG(INFO) << "VIRTUAL REG " << vreg_idx << " Keep in Stack Frame [" << frame_idx << "];"; |
| |
| Storage s; |
| s.regTag = kInStackType; |
| s.index = frame_idx; |
| allocated_map_[vreg_idx] = s; |
| } |
| |
| void RegisterAllocator::FreeStorage(unsigned vreg_idx) { |
| //TODO: Check vreg_idx must be allocated |
| Storage s = allocated_map_[vreg_idx]; |
| |
| if (s.regTag == kInStackType) |
| return; |
| |
| if (s.regTag == kPhyRegType) |
| allocatable_list_.push_front(s.index); |
| else |
| stackstorage_list_.push_front(s.index); |
| |
| allocated_map_.erase(vreg_idx); |
| } |
| |
| void RegisterAllocator::InitializeAllocation(LIRFunction &lir_func) { |
| allocatable_list_ = reg_info_.GetAllocatableList(); |
| stackstorage_list_.clear(); |
| allocated_map_.clear(); |
| } |
| |
| void RegisterAllocator::PreRegisterAllocation(LIRFunction &lir_func) { |
| PHIElimination(lir_func); |
| } |
| |
| void |
| RegisterAllocator::HandleInsnCopy(LIRBasicBlock &bb, |
| LIRBasicBlock::iterator it, |
| LIRBasicBlock::iterator next_it) { |
| unsigned reg_dst = it->GetOperand(0).GetReg(); |
| unsigned reg_src = it->GetOperand(1).GetReg(); |
| |
| Storage stor_dst = {-1, kNoneType}; |
| Storage stor_src = {-1, kNoneType}; |
| unsigned vidx_dst = 0, vidx_src = 0; |
| |
| if (LIRReg::IsVirtualReg(reg_dst)) { |
| vidx_dst = LIRReg::GetRegNo(reg_dst); |
| LOG(INFO) << "VIRTUAL REG " << vidx_dst << " in COPY need allocated !!"; |
| stor_dst = AllocateStorage(bb.GetParent(), vidx_dst); |
| } |
| |
| if (LIRReg::IsVirtualReg(reg_src)) { |
| vidx_src = LIRReg::GetRegNo(reg_src); |
| LOG(INFO) << "VIRTUAL REG " << vidx_src << " in COPY need allocated !!"; |
| stor_src = AllocateStorage(bb.GetParent(), vidx_src); |
| } |
| |
| if ((LIRReg::IsPhysicalReg(reg_dst) || (stor_dst.regTag == kPhyRegType)) |
| && (LIRReg::IsPhysicalReg(reg_src) || (stor_src.regTag == kPhyRegType))) { |
| // MovRR |
| unsigned idx_dst = (LIRReg::IsPhysicalReg(reg_dst)) ? |
| LIRReg::GetRegNo(reg_dst) : stor_dst.index; |
| unsigned idx_src = (LIRReg::IsPhysicalReg(reg_src)) ? |
| LIRReg::GetRegNo(reg_src) : stor_src.index; |
| LOG(INFO) << "\t [COPY] create MOVE: move " << idx_dst << ", "<< idx_src; |
| LIR* lir = reg_info_.CreateMoveReg(bb.GetParent(), idx_dst, idx_src); |
| bb.insert(next_it, lir); |
| bb.erase(it); |
| |
| if(LIRReg::IsVirtualReg(reg_src)) { |
| FreeStorage(vidx_src); |
| } |
| return; |
| } |
| |
| if ((stor_dst.regTag == stor_src.regTag) && (stor_dst.index == stor_src.index)) { |
| // Redundant move |
| FreeStorage(vidx_dst); |
| FreeStorage(vidx_src); |
| bb.erase(it); |
| return; |
| } |
| |
| if (stor_dst.regTag != kPhyRegType && stor_src.regTag != kPhyRegType) { |
| unsigned idx = reg_info_.GetTempRegsiter(0); |
| LIR* lir = reg_info_.CreateLoadStack(bb.GetParent(), idx, stor_src.index); |
| bb.insert(it, lir); |
| lir = reg_info_.CreateStoreStack(bb.GetParent(), idx, stor_dst.index); |
| bb.insert(next_it, lir); |
| bb.erase(it); |
| return; |
| } |
| |
| if (stor_dst.regTag != kPhyRegType) { |
| unsigned idx = (LIRReg::IsPhysicalReg(reg_src)) ? |
| LIRReg::GetRegNo(reg_src) : stor_src.index; |
| LOG(INFO) << "\t [COPY] create StoreStack: move " << idx << ", "<< stor_dst.index; |
| LIR* lir = reg_info_.CreateStoreStack(bb.GetParent(), idx, stor_dst.index); |
| bb.insert(next_it, lir); |
| bb.erase(it); |
| return; |
| } |
| |
| if (stor_src.regTag != kPhyRegType) { |
| unsigned idx = (LIRReg::IsPhysicalReg(reg_dst)) ? |
| LIRReg::GetRegNo(reg_dst) : stor_dst.index; |
| LOG(INFO) << "\t [COPY] create LoadStack: move " << idx << ", "<< stor_src.index; |
| LIR* lir = reg_info_.CreateLoadStack(bb.GetParent(), idx, stor_src.index); |
| bb.insert(next_it, lir); |
| bb.erase(it); |
| return; |
| } |
| } |
| |
| void RegisterAllocator::FunctionRegisterAllocation(LIRFunction &lir_func) { |
| for (LIRFunction::iterator bb = lir_func.begin(); bb != lir_func.end(); ++bb) { |
| LIRBasicBlock::iterator it; // current LIR |
| LIRBasicBlock::iterator next_it; // next LIR |
| for (LIRBasicBlock::iterator it = bb->begin(); it != bb->end(); it = next_it) { |
| next_it = it; ++next_it; |
| |
| // Handle Incoming Args |
| if (reg_info_.IsLoadIncomingArgs(it)) { |
| KeepStorage(*it); |
| bb->erase(it); |
| continue; |
| } |
| |
| // Handle Copy |
| if (it->GetOpcode() == opcode::kCOPY) { |
| HandleInsnCopy(*bb, *it, *next_it); |
| continue; |
| } |
| |
| std::vector<unsigned> free_list; |
| //for (LIR::op_iterator opi = i->operands_begin(); opi != i->operands_end(); ++opi) { |
| for (unsigned i = 0 ; i < it->GetNumOperands(); i++) { |
| LIROperand& lir_opd = it->GetOperand(i); |
| unsigned temp_count = 0; |
| |
| if (!lir_opd.IsReg()) |
| continue; |
| |
| unsigned reg_value = lir_opd.GetReg(); |
| if (!LIRReg::IsVirtualReg(reg_value)) |
| continue; |
| unsigned vreg_idx = LIRReg::GetRegNo(reg_value); |
| LOG(INFO) << "\t" << "VIRTUAL REG " << vreg_idx << " need allocated !!"; |
| Storage s = AllocateStorage(lir_func, vreg_idx); |
| if (!s.regTag) { |
| LOG(INFO) << "\t" << "VIRTUAL REG " << vreg_idx << " is map to REG[" << s.index << "]!!"; |
| lir_opd.SetReg(s.index); |
| } else { |
| unsigned temp_idx = reg_info_.GetTempRegsiter(temp_count++); |
| if ( lir_opd.IsDef() ) { |
| LIR* lir = reg_info_.CreateStoreStack(lir_func, temp_idx, s.index); |
| bb->insert(next_it, lir); |
| lir_opd.SetReg(temp_idx); |
| } else { |
| LIR* lir = reg_info_.CreateLoadStack(lir_func, temp_idx, s.index); |
| bb->insert(it, lir); |
| lir_opd.SetReg(temp_idx); |
| } |
| |
| LOG(INFO) << "\t" << "VIRTUAL REG " << vreg_idx << " is map to Frame[" << s.index << "]!!"; |
| } |
| |
| if (lir_opd.IsKill()) { |
| free_list.push_back(vreg_idx); |
| LOG(INFO) << "\t" << "VIRTUAL REG " << vreg_idx << " is mark kill!!"; |
| } |
| } |
| |
| for (size_t i = 0 ; i < free_list.size(); i++) { |
| LOG(INFO) << "\t" << "VIRTUAL REG " << free_list[i] << " is kill!!"; |
| FreeStorage(free_list[i]); |
| } |
| } |
| } |
| } |
| |
| } // namespace greenland |
| } // namespace art |