17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/IR/DataLayout.h"
19#include "llvm/IR/DebugInfoMetadata.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/IR/Module.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Transforms/Utils/BasicBlockUtils.h"
32static cl::opt<int, true>
34 cl::desc(
"Number of threads to use (0 = auto)"),
39 "polly-annotate-metadata-vectorize",
40 cl::desc(
"Append vectorize enable/disable metadata from polly"),
45 cl::desc(
"Scheduling type of parallel OpenMP for loops"),
46 cl::values(clEnumValN(OMPGeneralSchedulingType::StaticChunked,
"static",
48 clEnumValN(OMPGeneralSchedulingType::Dynamic,
"dynamic",
49 "Dynamic scheduling"),
50 clEnumValN(OMPGeneralSchedulingType::Guided,
"guided",
52 clEnumValN(OMPGeneralSchedulingType::Runtime,
"runtime",
53 "Runtime determined (OMP_SCHEDULE)")),
55 cl::init(OMPGeneralSchedulingType::Runtime), cl::Optional,
58static cl::opt<int, true>
60 cl::desc(
"Chunksize to use by the OpenMP runtime calls"),
90 DominatorTree &DT, BasicBlock *&ExitBB,
91 ICmpInst::Predicate Predicate,
93 bool LoopVectDisabled) {
94 Function *F = Builder.GetInsertBlock()->getParent();
95 LLVMContext &Context = F->getContext();
97 assert(LB->getType() == UB->getType() &&
"Types of loop bounds do not match");
98 IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
99 assert(LoopIVType &&
"UB is not integer?");
101 BasicBlock *BeforeBB = Builder.GetInsertBlock();
102 BasicBlock *GuardBB =
103 UseGuard ? BasicBlock::Create(Context,
"polly.loop_if", F) :
nullptr;
104 BasicBlock *HeaderBB = BasicBlock::Create(Context,
"polly.loop_header", F);
105 BasicBlock *PreHeaderBB =
106 BasicBlock::Create(Context,
"polly.loop_preheader", F);
109 Loop *OuterLoop = LI.getLoopFor(BeforeBB);
110 Loop *NewLoop = LI.AllocateLoop();
113 OuterLoop->addChildLoop(NewLoop);
115 LI.addTopLevelLoop(NewLoop);
119 OuterLoop->addBasicBlockToLoop(GuardBB, LI);
120 OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI);
123 NewLoop->addBasicBlockToLoop(HeaderBB, LI);
128 Annotator->
pushLoop(NewLoop, Parallel);
131 ExitBB = SplitBlock(BeforeBB, Builder.GetInsertPoint(), &DT, &LI);
132 ExitBB->setName(
"polly.loop_exit");
136 BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
137 DT.addNewBlock(GuardBB, BeforeBB);
140 Builder.SetInsertPoint(GuardBB);
142 LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
143 LoopGuard->setName(
"polly.loop_guard");
144 Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
145 DT.addNewBlock(PreHeaderBB, GuardBB);
147 BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB);
148 DT.addNewBlock(PreHeaderBB, BeforeBB);
152 Builder.SetInsertPoint(PreHeaderBB);
153 Builder.CreateBr(HeaderBB);
156 DT.addNewBlock(HeaderBB, PreHeaderBB);
157 Builder.SetInsertPoint(HeaderBB);
158 PHINode *IV = Builder.CreatePHI(LoopIVType, 2,
"polly.indvar");
159 IV->addIncoming(LB, PreHeaderBB);
160 Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
161 Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride,
"polly.indvar_next");
162 Value *LoopCondition =
163 Builder.CreateICmp(Predicate, IncrementedIV, UB,
"polly.loop_cond");
166 BranchInst *
B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
173 std::optional<bool> EnableVectorizeMetadata;
174 if (LoopVectDisabled)
175 EnableVectorizeMetadata =
false;
177 EnableVectorizeMetadata =
true;
181 IV->addIncoming(IncrementedIV, HeaderBB);
183 DT.changeImmediateDominator(ExitBB, GuardBB);
185 DT.changeImmediateDominator(ExitBB, HeaderBB);
188 Builder.SetInsertPoint(HeaderBB->getFirstNonPHIIt());
193 Value *LB, Value *UB, Value *Stride, SetVector<Value *> &UsedValues,
194 ValueMapT &Map, BasicBlock::iterator *LoopBody) {
197 BasicBlock::iterator BeforeLoop =
Builder.GetInsertPoint();
201 std::tie(IV, SubFn) =
createSubFn(Stride, Struct, UsedValues, Map);
202 *LoopBody =
Builder.GetInsertPoint();
203 Builder.SetInsertPoint(BeforeLoop);
221 std::string FunctionName = SubFn->getName().str();
222 std::replace(FunctionName.begin(), FunctionName.end(),
'.',
'_');
223 SubFn->setName(FunctionName);
233 SmallVector<Type *, 8> Members;
235 for (
Value *V : Values)
236 Members.push_back(V->getType());
238 const DataLayout &DL =
Builder.GetInsertBlock()->getModule()->getDataLayout();
243 BasicBlock &EntryBB =
Builder.GetInsertBlock()->getParent()->getEntryBlock();
244 BasicBlock::iterator IP = EntryBB.getFirstInsertionPt();
245 StructType *Ty = StructType::get(
Builder.getContext(), Members);
246 AllocaInst *Struct =
new AllocaInst(Ty, DL.getAllocaAddrSpace(),
nullptr,
247 "polly.par.userContext", IP);
249 for (
unsigned i = 0; i < Values.size(); i++) {
250 Value *Address =
Builder.CreateStructGEP(Ty, Struct, i);
251 Address->setName(
"polly.subfn.storeaddr." + Values[i]->getName());
252 Builder.CreateStore(Values[i], Address);
259 SetVector<Value *> OldValues, Type *Ty, Value *Struct,
ValueMapT &Map) {
260 for (
unsigned i = 0; i < OldValues.size(); i++) {
261 Value *Address =
Builder.CreateStructGEP(Ty, Struct, i);
262 Type *ElemTy = cast<GetElementPtrInst>(Address)->getResultElementType();
264 NewValue->setName(
"polly.subfunc.arg." + OldValues[i]->getName());
265 Map[OldValues[i]] = NewValue;
273 LLVMContext &
Ctx = F->getContext();
274 DISubprogram *DILScope =
275 dyn_cast_or_null<DISubprogram>(F->getMetadata(LLVMContext::MD_dbg));
278 return DILocation::get(
Ctx, 0, 0, DILScope);
polly dump Polly Dump Function
static cl::opt< int, true > XPollyChunkSize("polly-scheduling-chunksize", cl::desc("Chunksize to use by the OpenMP runtime calls"), cl::Hidden, cl::location(polly::PollyChunkSize), cl::init(0), cl::Optional, cl::cat(PollyCategory))
static cl::opt< int, true > XPollyNumThreads("polly-num-threads", cl::desc("Number of threads to use (0 = auto)"), cl::Hidden, cl::location(polly::PollyNumThreads), cl::init(0), cl::cat(PollyCategory))
cl::opt< bool > PollyVectorizeMetadata("polly-annotate-metadata-vectorize", cl::desc("Append vectorize enable/disable metadata from polly"), cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory))
static cl::opt< OMPGeneralSchedulingType, true > XPollyScheduling("polly-scheduling", cl::desc("Scheduling type of parallel OpenMP for loops"), cl::values(clEnumValN(OMPGeneralSchedulingType::StaticChunked, "static", "Static scheduling"), clEnumValN(OMPGeneralSchedulingType::Dynamic, "dynamic", "Dynamic scheduling"), clEnumValN(OMPGeneralSchedulingType::Guided, "guided", "Guided scheduling"), clEnumValN(OMPGeneralSchedulingType::Runtime, "runtime", "Runtime determined (OMP_SCHEDULE)")), cl::Hidden, cl::location(polly::PollyScheduling), cl::init(OMPGeneralSchedulingType::Runtime), cl::Optional, cl::cat(PollyCategory))
llvm::cl::OptionCategory PollyCategory
PollyIRBuilder & Builder
The IR builder we use to create instructions.
Function * createSubFnDefinition()
Create the definition of the parallel subfunction.
virtual void deployParallelExecution(Function *SubFn, Value *SubFnParam, Value *LB, Value *UB, Value *Stride)=0
Create the runtime library calls for spawn and join of the worker threads.
Value * createParallelLoop(Value *LB, Value *UB, Value *Stride, SetVector< Value * > &Values, ValueMapT &VMap, BasicBlock::iterator *LoopBody)
Create a parallel loop.
virtual std::tuple< Value *, Function * > createSubFn(Value *Stride, AllocaInst *Struct, SetVector< Value * > UsedValues, ValueMapT &VMap)=0
Create the parallel subfunction.
Type * LongType
The type of a "long" on this hardware used for backend calls.
void extractValuesFromStruct(SetVector< Value * > Values, Type *Ty, Value *Struct, ValueMapT &VMap)
Extract all values from the Struct and construct the mapping.
virtual Function * prepareSubFnDefinition(Function *F) const =0
Prepare the definition of the parallel subfunction.
AllocaInst * storeValuesIntoStruct(SetVector< Value * > &Values)
Create a struct for all Values and store them in there.
Helper class to annotate newly generated SCoPs with metadata.
void pushLoop(llvm::Loop *L, bool IsParallel)
Add a new loop L which is parallel if IsParallel is true.
void annotateLoopLatch(llvm::BranchInst *B, bool IsParallel, std::optional< bool > EnableVectorizeMetadata=std::nullopt) const
Annotate the loop latch B.
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
OMPGeneralSchedulingType PollyScheduling
StringRef PollySkipFnAttr
A function attribute which will cause Polly to skip the function.
llvm::DebugLoc createDebugLocForGeneratedCode(Function *F)
Create a DebugLoc representing generated instructions.
@ Value
MemoryKind::Value: Models an llvm::Value.
Value * createLoop(Value *LowerBound, Value *UpperBound, Value *Stride, PollyIRBuilder &Builder, LoopInfo &LI, DominatorTree &DT, BasicBlock *&ExitBlock, ICmpInst::Predicate Predicate, ScopAnnotator *Annotator=nullptr, bool Parallel=false, bool UseGuard=true, bool LoopVectDisabled=false)
Create a scalar do/for-style loop.
OMPGeneralSchedulingType
General scheduling types of parallel OpenMP for loops.
llvm::IRBuilder< llvm::ConstantFolder, IRInserter > PollyIRBuilder
llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > ValueMapT
Type to remap values.