BlockGenerators.cpp | Explore in Territory

//===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the BlockGenerator and VectorBlockGenerator classes,
// which generate sequential code and vectorized code for a polyhedral
// statement, respectively.
//
//===----------------------------------------------------------------------===//

#include "polly/CodeGen/BlockGenerators.h"
#include "polly/CodeGen/IslExprBuilder.h"
#include "polly/CodeGen/RuntimeDebugBuilder.h"
#include "polly/Options.h"
#include "polly/ScopInfo.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/ScopHelper.h"
#include "polly/Support/VirtualInstruction.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "isl/ast.h"
#include <deque>

usingnamespacellvm;
usingnamespacepolly;

static cl::opt<bool> Aligned("enable-polly-aligned",
                             cl::desc("Assumed aligned memory accesses."),
                             cl::Hidden, cl::cat(PollyCategory));

bool PollyDebugPrinting;
static cl::opt<bool, true> DebugPrintingX(
    "polly-codegen-add-debug-printing",
    cl::desc("Add printf calls that show the values loaded/stored."),
    cl::location(PollyDebugPrinting), cl::Hidden, cl::cat(PollyCategory));

static cl::opt<bool> TraceStmts(
    "polly-codegen-trace-stmts",
    cl::desc("Add printf calls that print the statement being executed"),
    cl::Hidden, cl::cat(PollyCategory));

static cl::opt<bool> TraceScalars(
    "polly-codegen-trace-scalars",
    cl::desc("Add printf calls that print the values of all scalar values "
             "used in a statement. Requires -polly-codegen-trace-stmts."),
    cl::Hidden, cl::cat(PollyCategory));

BlockGenerator::BlockGenerator(
    PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
    AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap,
    ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
    : … { … }

Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
                                             ValueMapT &BBMap,
                                             LoopToScevMapT &LTS,
                                             Loop *L) const { … }

Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
                                   LoopToScevMapT &LTS, Loop *L) const { … }

void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
                                    ValueMapT &BBMap, LoopToScevMapT &LTS) { … }

Value *
BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                         ValueMapT &BBMap, LoopToScevMapT &LTS,
                                         isl_id_to_ast_expr *NewAccesses) { … }

Value *BlockGenerator::generateLocationAccessed(
    ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
    LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,
    Type *ExpectedType) { … }

Value *
BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
                                   LoopToScevMapT &LTS, ValueMapT &BBMap,
                                   __isl_keep isl_id_to_ast_expr *NewAccesses) { … }

Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const { … }

Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,
                                         ValueMapT &BBMap, LoopToScevMapT &LTS,
                                         isl_id_to_ast_expr *NewAccesses) { … }

void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,
                                        ValueMapT &BBMap, LoopToScevMapT &LTS,
                                        isl_id_to_ast_expr *NewAccesses) { … }

bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) { … }

void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
                                     ValueMapT &BBMap, LoopToScevMapT &LTS,
                                     isl_id_to_ast_expr *NewAccesses) { … }

void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) { … }

void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                              __isl_keep isl_id_to_ast_expr *NewAccesses) { … }

BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) { … }

BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
                                   ValueMapT &BBMap, LoopToScevMapT &LTS,
                                   isl_id_to_ast_expr *NewAccesses) { … }

void BlockGenerator::switchGeneratedFunc(Function *GenFn, DominatorTree *GenDT,
                                         LoopInfo *GenLI,
                                         ScalarEvolution *GenSE) { … }

void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                            ValueMapT &BBMap, LoopToScevMapT &LTS,
                            isl_id_to_ast_expr *NewAccesses) { … }

Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) { … }

Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) { … }

void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) { … }

void BlockGenerator::generateScalarLoads(
    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
    __isl_keep isl_id_to_ast_expr *NewAccesses) { … }

Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt,
                                              const isl::set &Subdomain) { … }

void BlockGenerator::generateConditionalExecution(
    ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject,
    const std::function<void()> &GenThenFunc) { … }

static std::string getInstName(Value *Val) { … }

void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                            ValueMapT &BBMap) { … }

void BlockGenerator::generateScalarStores(
    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
    __isl_keep isl_id_to_ast_expr *NewAccesses) { … }

void BlockGenerator::createScalarInitialization(Scop &S) { … }

void BlockGenerator::createScalarFinalization(Scop &S) { … }

void BlockGenerator::findOutsideUsers(Scop &S) { … }

void BlockGenerator::createExitPHINodeMerges(Scop &S) { … }

void BlockGenerator::invalidateScalarEvolution(Scop &S) { … }

void BlockGenerator::finalizeSCoP(Scop &S) { … }

BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
                                             BasicBlock *BBCopy) { … }

// This is to determine whether an llvm::Value (defined in @p BB) is usable when
// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
// does not work in cases where the exit block has edges from outside the
// region. In that case the llvm::Value would never be usable in in the exit
// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
// for the subregion's exiting edges only. We need to determine whether an
// llvm::Value is usable in there. We do this by checking whether it dominates
// all exiting blocks individually.
static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
                                      BasicBlock *BB) { … }

// Find the direct dominator of the subregion's exit block if the subregion was
// simplified.
static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) { … }

void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                               __isl_keep isl_id_to_ast_expr *IdToAstExp) { … }

PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
                                       ValueMapT &BBMap, Loop *L) { … }

Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
                                      ValueMapT &BBMap) { … }

void RegionGenerator::generateScalarStores(
    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
    __isl_keep isl_id_to_ast_expr *NewAccesses) { … }

void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
                                      PHINode *PHICopy, BasicBlock *IncomingBB,
                                      LoopToScevMapT &LTS) { … }

void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
                                         ValueMapT &BBMap,
                                         LoopToScevMapT &LTS) { … }
llvm/polly/lib/CodeGen/BlockGenerators.cpp
