From 52d7de892ec15cda1bbe9e86c96cb01a81203e90 Mon Sep 17 00:00:00 2001 From: Eric Schweitz Date: Wed, 20 Feb 2019 11:46:41 -0800 Subject: [PATCH] [flang] Fortran IR: staged pull request for the "upper layers" of the IR. The Fortran IR is hierarchical: A Program contains Procedures. Procedures contain Basic Blocks. Groups of Basic Blocks can be grouped as Regions. This structure follows those one finds in SIL and LLVM IR, etc. Original-commit: flang-compiler/f18@e2291016dffe76728879ba97d0bfadf2fcb557ed Reviewed-on: https://github.com/flang-compiler/f18/pull/293 Tree-same-pre-rewrite: false --- flang/lib/IntermediateRepresentation/basicblock.cc | 57 ++++++++++++++ flang/lib/IntermediateRepresentation/basicblock.h | 69 ++++++++++++++++ flang/lib/IntermediateRepresentation/procedure.cc | 86 ++++++++++++++++++++ flang/lib/IntermediateRepresentation/procedure.h | 80 +++++++++++++++++++ flang/lib/IntermediateRepresentation/program.cc | 48 ++++++++++++ flang/lib/IntermediateRepresentation/program.h | 55 +++++++++++++ flang/lib/IntermediateRepresentation/region.cc | 49 ++++++++++++ flang/lib/IntermediateRepresentation/region.h | 91 ++++++++++++++++++++++ 8 files changed, 535 insertions(+) create mode 100644 flang/lib/IntermediateRepresentation/basicblock.cc create mode 100644 flang/lib/IntermediateRepresentation/basicblock.h create mode 100644 flang/lib/IntermediateRepresentation/procedure.cc create mode 100644 flang/lib/IntermediateRepresentation/procedure.h create mode 100644 flang/lib/IntermediateRepresentation/program.cc create mode 100644 flang/lib/IntermediateRepresentation/program.h create mode 100644 flang/lib/IntermediateRepresentation/region.cc create mode 100644 flang/lib/IntermediateRepresentation/region.h diff --git a/flang/lib/IntermediateRepresentation/basicblock.cc b/flang/lib/IntermediateRepresentation/basicblock.cc new file mode 100644 index 0000000..2c33067 --- /dev/null +++ b/flang/lib/IntermediateRepresentation/basicblock.cc @@ -0,0 +1,57 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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 "program.h" +#include "stmt.h" + +namespace Fortran::IntermediateRepresentation { + +BasicBlock::BasicBlock(Region *parentRegion, BasicBlock *insertBefore) + : ChildMixin{parentRegion} { + parent->insertBefore(this, insertBefore); +} + +BasicBlock::~BasicBlock() { statementList_.clear(); } + +void BasicBlock::insertBefore(Statement *stmt, Statement *before) { + if (before) { + statementList_.insert(before->getIterator(), stmt); + } else { + statementList_.push_back(stmt); + } +} + +void BasicBlock::addPred(BasicBlock *bb) { + for (auto *p : predecessors_) { + if (p == bb) return; + } + predecessors_.push_back(bb); +} + +const Statement *BasicBlock::getTerminator() const { + if (statementList_.empty()) { + return nullptr; + } + const auto &lastStmt{statementList_.back()}; + return std::visit( + [&lastStmt](auto stmt) { + if constexpr (std::is_base_of_v) { + return &lastStmt; + } + return static_cast(nullptr); + }, + lastStmt.u); +} + +} diff --git a/flang/lib/IntermediateRepresentation/basicblock.h b/flang/lib/IntermediateRepresentation/basicblock.h new file mode 100644 index 0000000..22b948a3 --- /dev/null +++ b/flang/lib/IntermediateRepresentation/basicblock.h @@ -0,0 +1,69 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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. + +#ifndef FORTRAN_INTERMEDIATEREPRESENTATION_BASICBLOCK_H_ +#define FORTRAN_INTERMEDIATEREPRESENTATION_BASICBLOCK_H_ + +#include "mixin.h" +#include "region.h" +#include + +namespace Fortran::IntermediateRepresentation { + +struct Region; +struct Statement; + +struct BasicBlock final : public llvm::ilist_node, + public ChildMixin { + using StatementListType = llvm::iplist; + using iterator = StatementListType::iterator; + using const_iterator = StatementListType::const_iterator; + using reverse_iterator = StatementListType::reverse_iterator; + using const_reverse_iterator = StatementListType::const_reverse_iterator; + + BasicBlock(const BasicBlock &) = delete; + BasicBlock &operator=(const BasicBlock &) = delete; + ~BasicBlock(); + StatementListType &getSublist(Statement *) { return Statements(); } + void insertBefore(Statement *stmt, Statement *before = nullptr); + static BasicBlock *Create( + Region *parentRegion, BasicBlock *insertBefore = nullptr) { + return new BasicBlock(parentRegion, insertBefore); + } + const Statement *getTerminator() const; + Statement *getTerminator() { + return const_cast( + const_cast(this)->getTerminator()); + } + void SetRegion(Region *region) { parent = region; } + Region *GetRegion() const { return parent; } + void addPred(BasicBlock *bb); + std::vector &Predecessors() { return predecessors_; } + StatementListType &Statements() { return statementList_; } + BasicBlock *SplitEdge(BasicBlock *toBlock) { return nullptr; } + +private: + StatementListType statementList_; + std::vector predecessors_; + explicit BasicBlock(Region *parentRegion, BasicBlock *insertBefore); +}; + +inline std::list pred_list(BasicBlock &block) { + return std::list{ + block.Predecessors().begin(), block.Predecessors().end()}; +} + +} + +#endif diff --git a/flang/lib/IntermediateRepresentation/procedure.cc b/flang/lib/IntermediateRepresentation/procedure.cc new file mode 100644 index 0000000..64b4c73 --- /dev/null +++ b/flang/lib/IntermediateRepresentation/procedure.cc @@ -0,0 +1,86 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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 "procedure.h" + +namespace Fortran::IntermediateRepresentation { + +Procedure::Procedure(Program *program, FunctionType *ty, LinkageTypes lt, + unsigned addrSpace, const llvm::Twine &n, Procedure *before) + : ChildMixin{program}, procType_{ty}, linkage_{lt}, + addressSpace_{addrSpace}, name_{n.str()} { + Region::Create(this); + parent->insertBefore(this, before); +} + +Procedure::~Procedure() { regionList_.clear(); } + +Region *Procedure::insertBefore(Region *region, Region *before) { + if (before) { + regionList_.insert(before->getIterator(), region); + } else { + regionList_.push_back(region); + } + return region; +} + +template +static void AddCountScopes( + unsigned count, BasicBlock *block, T callback, semantics::Scope *scope) { + for (; count; --count) { + block->insertBefore( + new Statement(block, callback(scope)), block->getTerminator()); + } +} + +inline static void AddEnterScopes(unsigned count, BasicBlock *block) { + AddCountScopes( + count, block, ScopeEnterStmt::Create, /*TODO: thread scope? */ nullptr); +} + +inline static void AddExitScopes(unsigned count, BasicBlock *block) { + AddCountScopes( + count, block, ScopeExitStmt::Create, /*TODO: thread scope? */ nullptr); +} + +static bool DistinctScopes(Region *region1, Region *region2) { + return region1->HasScope() && region2->HasScope() && + region1->GetScope() != region2->GetScope(); +} + +void Procedure::FlattenRegions() { + for (auto &block : GetBlocks()) { + auto *region{block.GetRegion()}; + if (!region->IsOutermost()) { + for (auto *successor : succ_list(block)) { + auto *successorRegion{successor->GetRegion()}; + if (successorRegion != region && + DistinctScopes(successorRegion, region)) { + if (IsAncestor(region, successorRegion)) { + AddEnterScopes(RegionDepth(region, successorRegion), + successor->SplitEdge(&block)); + } else if (IsAncestor(successorRegion, region)) { + AddExitScopes(RegionDepth(successorRegion, region), + block.SplitEdge(successor)); + } else { + // TODO: edge to a cousin region + CHECK(false); + } + } + } + } + } +} + +} diff --git a/flang/lib/IntermediateRepresentation/procedure.h b/flang/lib/IntermediateRepresentation/procedure.h new file mode 100644 index 0000000..44a8e06 --- /dev/null +++ b/flang/lib/IntermediateRepresentation/procedure.h @@ -0,0 +1,80 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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. + +#ifndef FORTRAN_INTERMEDIATEREPRESENTATION_PROCEDURE_H_ +#define FORTRAN_INTERMEDIATEREPRESENTATION_PROCEDURE_H_ + +#include "mixin.h" +#include "program.h" +#include "region.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Twine.h" + +namespace Fortran::IntermediateRepresentation { + +struct Program; +struct Region; +struct GraphWriter; + +struct Procedure final : public llvm::ilist_node, + public ChildMixin { + friend GraphWriter; + friend Program; + friend Region; + using BasicBlockListType = llvm::iplist; + using RegionListType = llvm::iplist; + using iterator = BasicBlockListType::iterator; + using const_iterator = BasicBlockListType::const_iterator; + using reverse_iterator = BasicBlockListType::reverse_iterator; + using const_reverse_iterator = BasicBlockListType::const_reverse_iterator; + + Procedure(const Procedure &) = delete; + Procedure &operator=(const Procedure &) = delete; + ~Procedure(); + BasicBlockListType &GetBlocks() { return basicBlockList_; } + BasicBlockListType &getSublist(BasicBlock *) { return GetBlocks(); } + RegionListType &GetRegions() { return regionList_; } + RegionListType &getSublist(Region *) { return GetRegions(); } + iterator begin() { return basicBlockList_.begin(); } + const_iterator begin() const { return basicBlockList_.begin(); } + iterator end() { return basicBlockList_.end(); } + const_iterator end() const { return basicBlockList_.end(); } + Region *getLastRegion() { return ®ionList_.back(); } + BasicBlock *StartBlock() { return &basicBlockList_.front(); } + static Procedure *Create(Program *prog, FunctionType *ty, + LinkageTypes linkage, unsigned addrSpace = 0u, + const llvm::Twine &name = "", Procedure *before = nullptr) { + return new Procedure(prog, ty, linkage, addrSpace, name, before); + } + void setParent(Program *p) { parent = p; } + bool hasName() const { return !getName().empty(); } + llvm::StringRef getName() const { return name_; } + void FlattenRegions(); + +private: + RegionListType regionList_; + BasicBlockListType basicBlockList_; + FunctionType *procType_; + LinkageTypes linkage_; + unsigned addressSpace_; + const std::string name_; + + explicit Procedure(Program *program, FunctionType *ty, LinkageTypes lt, + unsigned addrSpace, const llvm::Twine &n, Procedure *before); + Region *insertBefore(Region *region, Region *before = nullptr); +}; + +} + +#endif diff --git a/flang/lib/IntermediateRepresentation/program.cc b/flang/lib/IntermediateRepresentation/program.cc new file mode 100644 index 0000000..2e6c547 --- /dev/null +++ b/flang/lib/IntermediateRepresentation/program.cc @@ -0,0 +1,48 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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 "program.h" + +namespace Fortran::IntermediateRepresentation { + +Program::Program(llvm::StringRef id) : name_{id} {} +Program::~Program() { procedureMap_.clear(); } + +void Program::insertBefore(Procedure *subprog, Procedure *before) { + if (before) { + procedureList_.insert(before->getIterator(), subprog); + } else { + procedureList_.push_back(subprog); + } +} + +Procedure *Program::getOrInsertProcedure( + llvm::StringRef name, FunctionType *procTy, AttributeList attrs) { + llvm::StringMapEntry *entry{nullptr}; + if (!name.empty()) { + auto iter{procedureMap_.find(name)}; + if (iter != procedureMap_.end()) { + return iter->getValue(); + } + entry = &*procedureMap_.insert({name, nullptr}).first; + name = entry->getKey(); + } + auto *subp{Procedure::Create(this, procTy, LinkageTypes::Public, 0u, name)}; + if (entry) { + entry->setValue(subp); + } + return subp; +} + +} diff --git a/flang/lib/IntermediateRepresentation/program.h b/flang/lib/IntermediateRepresentation/program.h new file mode 100644 index 0000000..9f543c8 --- /dev/null +++ b/flang/lib/IntermediateRepresentation/program.h @@ -0,0 +1,55 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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. + +#ifndef FORTRAN_INTERMEDIATEREPRESENTATION_PROGRAM_H_ +#define FORTRAN_INTERMEDIATEREPRESENTATION_PROGRAM_H_ + +#include "common.h" +#include "procedure.h" +#include "../evaluate/type.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Twine.h" +#include + +namespace Fortran::IntermediateRepresentation { + +struct Procedure; +struct GraphWriter; + +struct Program final { + friend GraphWriter; + using ProcedureListType = llvm::iplist; + using ProcedureMapType = llvm::StringMap; + + explicit Program(llvm::StringRef id); + ~Program(); + void insertBefore(Procedure *subprog, Procedure *before = nullptr); + ProcedureListType &getSublist(Procedure *) { return procedureList_; } + bool containsProcedure(llvm::StringRef name) { + return procedureMap_.find(name) != procedureMap_.end(); + } + std::string getName() const { return name_; } + Procedure *getOrInsertProcedure( + llvm::StringRef name, FunctionType *procTy, AttributeList attrs); + +private: + ProcedureListType procedureList_; + ProcedureMapType procedureMap_; + const std::string name_; +}; + +} + +#endif diff --git a/flang/lib/IntermediateRepresentation/region.cc b/flang/lib/IntermediateRepresentation/region.cc new file mode 100644 index 0000000..d93811e --- /dev/null +++ b/flang/lib/IntermediateRepresentation/region.cc @@ -0,0 +1,49 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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 "program.h" + +namespace Fortran::IntermediateRepresentation { + +Region::Region( + Procedure *procedure, Scope *scope, Region *inRegion, Region *insertBefore) + : ChildMixin{procedure}, basicBlockList_{procedure->GetBlocks()}, + enclosingRegion_{inRegion}, scope_{scope} { + if (enclosingRegion_) { + enclosingRegion_->getSublist(static_cast(nullptr)) + .push_back(this); + } else { + parent->insertBefore(this, insertBefore); + } +} + +Region::~Region() { basicBlockList_.clear(); } + +void Region::insertBefore(BasicBlock *block, BasicBlock *before) { + if (before) { + basicBlockList_.insert(before->getIterator(), block); + } else { + basicBlockList_.push_back(block); + } +} + +std::vector Region::getBlocks() { + std::vector result; + for (auto &block : basicBlockList_) { + if (block.getParent() == this) result.push_back(&block); + } + return result; +} + +} diff --git a/flang/lib/IntermediateRepresentation/region.h b/flang/lib/IntermediateRepresentation/region.h new file mode 100644 index 0000000..bcf5a4a --- /dev/null +++ b/flang/lib/IntermediateRepresentation/region.h @@ -0,0 +1,91 @@ +// Copyright (c) 2019, NVIDIA CORPORATION. All rights reserved. +// +// 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. + +#ifndef FORTRAN_INTERMEDIATEREPRESENTATION_REGION_H_ +#define FORTRAN_INTERMEDIATEREPRESENTATION_REGION_H_ + +#include "procedure.h" +#include "stmt.h" +#include "../semantics/semantics.h" + +namespace Fortran::IntermediateRepresentation { + +struct Procedure; +struct BasicBlock; + +struct Region final : public llvm::ilist_node, + public ChildMixin { + friend Procedure; + friend BasicBlock; + using BasicBlockListType = llvm::iplist; + using AllocatableListType = std::list; + using SubregionListType = llvm::iplist; + using iterator = SubregionListType::iterator; + using const_iterator = SubregionListType::const_iterator; + using reverse_iterator = SubregionListType::reverse_iterator; + using const_reverse_iterator = SubregionListType::const_reverse_iterator; + + Region(const Region &) = delete; + Region &operator=(const Region &) = delete; + ~Region(); + std::vector getBlocks(); + std::vector getSublist(BasicBlock *) { return getBlocks(); } + SubregionListType &getSublist(Region *) { return subregionList_; } + iterator begin() { return subregionList_.begin(); } + const_iterator begin() const { return subregionList_.begin(); } + iterator end() { return subregionList_.end(); } + const_iterator end() const { return subregionList_.end(); } + Region *GetEnclosing() const { return enclosingRegion_; } + bool IsOutermost() const { return GetEnclosing() == nullptr; } + static Region *Create(Procedure *procedure, Scope *scope = nullptr, + Region *inRegion = nullptr, Region *insertBefore = nullptr) { + return new Region(procedure, scope, inRegion, insertBefore); + } + bool HasScope() const { return scope_.has_value(); } + Scope *GetScope() const { return scope_ ? scope_.value() : nullptr; } + +private: + BasicBlockListType &basicBlockList_; + AllocatableListType allocatableList_; + SubregionListType subregionList_; // direct descendants + Region *enclosingRegion_; // parent in nesting tree + std::optional scope_; + + explicit Region(Procedure *procedure, Scope *scope, Region *inRegion, + Region *insertBefore); + void insertBefore(BasicBlock *block, BasicBlock *before); +}; + +inline bool IsAncestor(const Region *fromRegion, const Region *toRegion) { + CHECK(fromRegion && toRegion); + for (const auto *region{fromRegion->GetEnclosing()}; region; + region = region->GetEnclosing()) { + if (region == toRegion) return true; + } + return false; +} + +inline unsigned RegionDepth(const Region *fromRegion, const Region *toRegion) { + CHECK(IsAncestor(fromRegion, toRegion)); + unsigned result{0u}; + for (const auto *region{fromRegion}; region != toRegion; + region = region->GetEnclosing()) { + ++result; + } + return result; +} + +} + +#endif -- 2.7.4