From 3f182ff643ce72e81de129bc52249e08e1417f6d Mon Sep 17 00:00:00 2001 From: Benjamin Segovia Date: Thu, 15 Mar 2012 19:03:19 +0000 Subject: [PATCH] Started to implement values and ud | du chains --- backend/src/CMakeLists.txt | 4 +- backend/src/ir/context.cpp | 6 +- backend/src/ir/function.cpp | 10 ++- backend/src/ir/function.hpp | 22 ++++-- backend/src/ir/immediate.hpp | 6 +- backend/src/ir/liveness.cpp | 8 +- backend/src/ir/value.cpp | 67 ++++++++++++++++ backend/src/ir/value.hpp | 179 +++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 279 insertions(+), 23 deletions(-) create mode 100644 backend/src/ir/value.cpp create mode 100644 backend/src/ir/value.hpp diff --git a/backend/src/CMakeLists.txt b/backend/src/CMakeLists.txt index 9307d9f..3b8bc09 100644 --- a/backend/src/CMakeLists.txt +++ b/backend/src/CMakeLists.txt @@ -39,7 +39,9 @@ else (GBE_USE_BLOB) ir/register.cpp ir/register.hpp ir/function.cpp - ir/function.hpp) + ir/function.hpp + ir/value.cpp + ir/value.hpp) if (GBE_COMPILE_UTESTS) set (GBE_SRC diff --git a/backend/src/ir/context.cpp b/backend/src/ir/context.cpp index 9885c39..838ce9e 100644 --- a/backend/src/ir/context.cpp +++ b/backend/src/ir/context.cpp @@ -83,7 +83,7 @@ namespace ir { void Context::input(FunctionInput::Type type, Register reg, uint32_t elementSize) { GBE_ASSERTM(fn != NULL, "No function currently defined"); GBE_ASSERTM(reg < fn->file.regNum(), "Out-of-bound register"); - const FunctionInput input(type, reg, elementSize); + FunctionInput *input = GBE_NEW(FunctionInput, type, reg, elementSize); fn->inputs.push_back(input); } @@ -129,9 +129,7 @@ namespace ir { } // Append the instruction in the stream - Instruction *insnPtr = fn->newInstruction(); - - *insnPtr = insn; + Instruction *insnPtr = fn->newInstruction(insn); #if GBE_DEBUG std::string whyNot; GBE_ASSERTM(insn.wellFormed(*fn, whyNot), whyNot.c_str()); diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp index e3e343e..ad32180 100644 --- a/backend/src/ir/function.cpp +++ b/backend/src/ir/function.cpp @@ -36,6 +36,8 @@ namespace ir { Function::~Function(void) { for (auto it = blocks.begin(); it != blocks.end(); ++it) GBE_DELETE(*it); + for (auto it = inputs.begin(); it != inputs.end(); ++it) + GBE_DELETE(*it); } LabelIndex Function::newLabel(void) { @@ -67,13 +69,13 @@ namespace ir { void Function::computeCFG(void) { // Clear possible previously computed CFG - this->apply([this](BasicBlock &bb) { + this->foreachBlock([this](BasicBlock &bb) { bb.successors.clear(); bb.predecessors.clear(); }); // Update it. Do not forget that a branch can also jump to the next block BasicBlock *jumpToNext = NULL; - this->apply([this, &jumpToNext](BasicBlock &bb) { + this->foreachBlock([this, &jumpToNext](BasicBlock &bb) { if (jumpToNext) { jumpToNext->successors.insert(&bb); bb.predecessors.insert(jumpToNext); @@ -122,7 +124,7 @@ namespace ir { << plural(fn.blockNum()) << " ##" << std::endl; for (uint32_t i = 0; i < fn.blockNum(); ++i) { const BasicBlock &bb = fn.getBlock(i); - bb.apply([&out, &fn] (const Instruction &insn) { + bb.foreach([&out, &fn] (const Instruction &insn) { out << insn << std::endl; }); out << std::endl; @@ -135,7 +137,7 @@ namespace ir { this->first = this->last = NULL; } BasicBlock::~BasicBlock(void) { - this->apply([this] (Instruction &insn) { + this->foreach([this] (Instruction &insn) { this->fn.deleteInstruction(&insn); }); } diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp index e253499..1739378 100644 --- a/backend/src/ir/function.hpp +++ b/backend/src/ir/function.hpp @@ -63,7 +63,7 @@ namespace ir { } /*! Apply the given functor on all instructions */ template - INLINE void apply(const T &functor) const { + INLINE void foreach(const T &functor) const { Instruction *curr = first; while (curr) { functor(*curr); @@ -151,8 +151,9 @@ namespace ir { return index; } /*! Allocate a new instruction (with the growing pool) */ - INLINE Instruction *newInstruction(void) { - return new (insnPool.allocate()) Instruction(); + template + INLINE Instruction *newInstruction(Args... args) { + return new (insnPool.allocate()) Instruction(args...); } /*! Deallocate an instruction (with the growing pool) */ INLINE void deleteInstruction(Instruction *insn) { @@ -160,8 +161,8 @@ namespace ir { } /*! Get input argument */ INLINE const FunctionInput &getInput(uint32_t ID) const { - GBE_ASSERT(ID < inputNum()); - return inputs[ID]; + GBE_ASSERT(ID < inputNum() && inputs[ID] != NULL); + return *inputs[ID]; } /*! Get output register */ INLINE Register getOutput(uint32_t ID) const { @@ -196,14 +197,21 @@ namespace ir { void outImmediate(std::ostream &out, ImmediateIndex index) const; /*! Apply the given functor on all basic blocks */ template - INLINE void apply(const T &functor) const { + INLINE void foreachBlock(const T &functor) const { for (auto it = blocks.begin(); it != blocks.end(); ++it) functor(**it); } + /*! Apply the given functor on all instructions */ + template + INLINE void foreachInstruction(const T &functor) const { + for (auto it = blocks.begin(); it != blocks.end(); ++it) + (*it)->foreach(functor); + } + private: friend class Context; //!< Can freely modify a function std::string name; //!< Function name - vector inputs; //!< Input registers of the function + vector inputs;//!< Input registers of the function vector outputs; //!< Output registers of the function vector labels; //!< Each label points to a basic block vector immediates; //!< All immediate values in the function diff --git a/backend/src/ir/immediate.hpp b/backend/src/ir/immediate.hpp index a9ac133..53442d7 100644 --- a/backend/src/ir/immediate.hpp +++ b/backend/src/ir/immediate.hpp @@ -22,8 +22,8 @@ * * \author Benjamin Segovia */ -#ifndef __GBE_IR_VALUE_HPP__ -#define __GBE_IR_VALUE_HPP__ +#ifndef __GBE_IR_IMMEDIATE_HPP__ +#define __GBE_IR_IMMEDIATE_HPP__ #include "ir/type.hpp" #include "sys/platform.hpp" @@ -75,5 +75,5 @@ namespace ir { } /* namespace ir */ } /* namespace gbe */ -#endif /* __GBE_IR_VALUE_HPP__ */ +#endif /* __GBE_IR_IMMEDIATE_HPP__ */ diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp index 30ea5e6..eb049d0 100644 --- a/backend/src/ir/liveness.cpp +++ b/backend/src/ir/liveness.cpp @@ -29,7 +29,7 @@ namespace ir { Liveness::Liveness(Function &fn) : fn(fn) { // Initialize UEVar and VarKill for each block - fn.apply([this](const BasicBlock &bb) { this->initBlock(bb); }); + fn.foreachBlock([this](const BasicBlock &bb) { this->initBlock(bb); }); // Now with iterative analysis, we compute liveout sets this->computeLiveOut(); } @@ -43,7 +43,7 @@ namespace ir { GBE_ASSERT(liveness.find(&bb) == liveness.end()); BlockInfo *info = GBE_NEW(BlockInfo, bb); // Traverse all instructions to handle UEVar and VarKill - bb.apply([this, info](const Instruction &insn) { + bb.foreach([this, info](const Instruction &insn) { this->initInstruction(*info, insn); }); liveness[&bb] = info; @@ -214,7 +214,7 @@ namespace ir { static void printBlock(std::ostream &out, const Liveness::BlockInfo &info) { const BasicBlock &bb = info.bb; const Function &fn = bb.getParent(); - bb.apply([&out, &info](const Instruction &insn) { + bb.foreach([&out, &info](const Instruction &insn) { printInstruction(out, info, insn); }); // At the end of block, we also output the variables actually alive at the @@ -247,7 +247,7 @@ namespace ir { out << std::endl << std::endl; // skip a line // Print liveness in each block - fn.apply([&out, &liveness] (const BasicBlock &bb) { + fn.foreachBlock([&out, &liveness] (const BasicBlock &bb) { const Liveness::Info &info = liveness.getLiveness(); auto it = info.find(&bb); GBE_ASSERT(it != info.end()); diff --git a/backend/src/ir/value.cpp b/backend/src/ir/value.cpp new file mode 100644 index 0000000..b438fb4 --- /dev/null +++ b/backend/src/ir/value.cpp @@ -0,0 +1,67 @@ +/* + * Copyright © 2012 Intel Corporation + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see . + * + * Author: Benjamin Segovia + */ + +/** + * \file value.cpp + * \author Benjamin Segovia + */ + +#include "ir/value.hpp" +#include "ir/liveness.hpp" + +namespace gbe { +namespace ir { + + GraphUseDef::GraphUseDef(const Liveness &liveness) { + const Function &fn = liveness.getFunction(); + + // First create the chains and insert them in their respective maps + fn.foreachInstruction([this](const Instruction &insn) { + // sources == value uses + const uint32_t srcNum = insn.getSrcNum(); + for (uint32_t srcID = 0; srcID < srcNum; ++srcID) { + ValueUse *valueUse = this->newValueUse(insn, srcID); + UDChain *udChain = this->newUDChain(); + udChain->first = valueUse; + udGraph.insert(std::make_pair(*valueUse, udChain)); + } + // destinations == value defs + const uint32_t dstNum = insn.getDstNum(); + for (uint32_t dstID = 0; dstID < dstNum; ++dstID) { + ValueDef *valueDef = this->newValueDef(insn, dstID); + DUChain *duChain = this->newDUChain(); + duChain->first = valueDef; + duGraph.insert(std::make_pair(*valueDef, duChain)); + } + }); + + // Function arguments are also value definitions + const uint32_t inputNum = fn.inputNum(); + for (uint32_t inputID = 0; inputID < inputNum; ++inputID) { + const FunctionInput &input = fn.getInput(inputID); + ValueDef *valueDef = this->newValueDef(input); + DUChain *duChain = this->newDUChain(); + duChain->first = valueDef; + duGraph.insert(std::make_pair(*valueDef, duChain)); + } + } + +} /* namespace ir */ +} /* namespace gbe */ + diff --git a/backend/src/ir/value.hpp b/backend/src/ir/value.hpp new file mode 100644 index 0000000..fdd3c62 --- /dev/null +++ b/backend/src/ir/value.hpp @@ -0,0 +1,179 @@ +/* + * Copyright © 2012 Intel Corporation + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see . + * + * Author: Benjamin Segovia + */ + +/** + * \file value.hpp + * \author Benjamin Segovia + */ +#ifndef __GBE_IR_VALUE_HPP__ +#define __GBE_IR_VALUE_HPP__ + +#include "ir/instruction.hpp" +#include "ir/function.hpp" +#include "sys/set.hpp" +#include "sys/map.hpp" + +namespace gbe { +namespace ir { + + // Make UD-Chain and DU-Chain computations faster and easier + class Liveness; + + /*! A value definition is a destination of an instruction or a function + * argument. Since we support multiple destinations, we also add the + * destination ID. + */ + class ValueDef + { + public: + /*! Discriminates the kind of values */ + enum Type : uint32_t { + FUNCTION_INPUT = 0, + INSTRUCTION_DST = 1 + }; + /*! Build a value from an instruction destination */ + ValueDef(Instruction &insn, uint32_t dstID = 0u) : type(INSTRUCTION_DST) { + this->data.insn = &insn; + this->data.dstID = dstID; + } + /*! Build a value from a function argument */ + ValueDef(FunctionInput &input) : type(FUNCTION_INPUT) { + this->data.input = &input; + } + /*! Get the type of the value */ + INLINE Type getType(void) const { return type; } + /*! Get the instruction (only if this is a instruction value) */ + INLINE Instruction *getInstruction(void) const { + GBE_ASSERT(type == INSTRUCTION_DST); + return data.insn; + } + /*! Get the destination ID (only if this is a instruction value) */ + INLINE uint32_t getDstID(void) const { + GBE_ASSERT(type == INSTRUCTION_DST); + return data.dstID; + } + /*! Get the function input (only if this is a function argument) */ + INLINE FunctionInput *getFunctionInput(void) const { + GBE_ASSERT(type == FUNCTION_INPUT); + return data.input; + } + + private: + /*! Instruction or function argument */ + union Data { + /*! Instruction destination or ... */ + struct { + Instruction *insn; //> DUChain; + /*! All possible definitions for a use */ + typedef std::pair> UDChain; + + /*! Get the chains (in both directions) for the complete program */ + class GraphUseDef + { + public: + /*! Build the complete DU/UD graphs for the program included in liveness */ + GraphUseDef(const Liveness &liveness); + /*! The UDChain for each definition use */ + typedef map UDGraph; + /*! The DUChain for each definition */ + typedef map DUGraph; + private: + UDGraph udGraph; //!< All the UD chains + DUGraph duGraph; //!< All the DU chains + GrowingPool valueUsePool; //!< Allocate the value uses + GrowingPool valueDefPool; //!< Allocate the value defs + GrowingPool udChainPool; //!< Allocate all the ud-chains + GrowingPool duChainPool; //!< Allocate all the du-chains +#define DECL_ALLOCATE_DEALLOCATE(TYPE, POOL) \ + template \ + INLINE TYPE *new##TYPE(Args... args) { \ + return new (POOL.allocate()) TYPE(args...); \ + } \ + INLINE void delete##TYPE(TYPE *ptr) { POOL.deallocate(ptr); } + DECL_ALLOCATE_DEALLOCATE(ValueDef, valueDefPool) + DECL_ALLOCATE_DEALLOCATE(ValueUse, valueUsePool) + DECL_ALLOCATE_DEALLOCATE(UDChain, udChainPool) + DECL_ALLOCATE_DEALLOCATE(DUChain, duChainPool) +#undef DECL_ALLOCATE_DEALLOCATE + GBE_CLASS(GraphUseDef); + }; + +} /* namespace ir */ +} /* namespace gbe */ + +#endif /* __GBE_IR_VALUE_HPP__ */ + -- 2.7.4