src/greenland/register_allocator.cc - platform/art - Git at Google

 /*
  * 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
	/*
	* 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