llvm-project
218 строк · 7.3 Кб
1//===- LoopUnrollAnalyzer.cpp - Unrolling Effect Estimation -----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements UnrolledInstAnalyzer class. It's used for predicting
10// potential effects that loop unrolling might have, such as enabling constant
11// propagation and other optimizations.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/LoopUnrollAnalyzer.h"16#include "llvm/Analysis/InstructionSimplify.h"17#include "llvm/Analysis/LoopInfo.h"18#include "llvm/Analysis/ScalarEvolutionExpressions.h"19#include "llvm/IR/Operator.h"20
21using namespace llvm;22
23/// Try to simplify instruction \param I using its SCEV expression.
24///
25/// The idea is that some AddRec expressions become constants, which then
26/// could trigger folding of other instructions. However, that only happens
27/// for expressions whose start value is also constant, which isn't always the
28/// case. In another common and important case the start value is just some
29/// address (i.e. SCEVUnknown) - in this case we compute the offset and save
30/// it along with the base address instead.
31bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {32if (!SE.isSCEVable(I->getType()))33return false;34
35const SCEV *S = SE.getSCEV(I);36if (auto *SC = dyn_cast<SCEVConstant>(S)) {37SimplifiedValues[I] = SC->getValue();38return true;39}40
41// If we have a loop invariant computation, we only need to compute it once.42// Given that, all but the first occurance are free.43if (!IterationNumber->isZero() && SE.isLoopInvariant(S, L))44return true;45
46auto *AR = dyn_cast<SCEVAddRecExpr>(S);47if (!AR || AR->getLoop() != L)48return false;49
50const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);51// Check if the AddRec expression becomes a constant.52if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {53SimplifiedValues[I] = SC->getValue();54return true;55}56
57// Check if the offset from the base address becomes a constant.58auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));59if (!Base)60return false;61auto *Offset =62dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));63if (!Offset)64return false;65SimplifiedAddress Address;66Address.Base = Base->getValue();67Address.Offset = Offset->getValue();68SimplifiedAddresses[I] = Address;69return false;70}
71
72/// Try to simplify binary operator I.
73///
74/// TODO: Probably it's worth to hoist the code for estimating the
75/// simplifications effects to a separate class, since we have a very similar
76/// code in InlineCost already.
77bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {78Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);79if (!isa<Constant>(LHS))80if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))81LHS = SimpleLHS;82if (!isa<Constant>(RHS))83if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))84RHS = SimpleRHS;85
86Value *SimpleV = nullptr;87const DataLayout &DL = I.getDataLayout();88if (auto FI = dyn_cast<FPMathOperator>(&I))89SimpleV =90simplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);91else92SimpleV = simplifyBinOp(I.getOpcode(), LHS, RHS, DL);93
94if (SimpleV) {95SimplifiedValues[&I] = SimpleV;96return true;97}98return Base::visitBinaryOperator(I);99}
100
101/// Try to fold load I.
102bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {103Value *AddrOp = I.getPointerOperand();104
105auto AddressIt = SimplifiedAddresses.find(AddrOp);106if (AddressIt == SimplifiedAddresses.end())107return false;108ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;109
110auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);111// We're only interested in loads that can be completely folded to a112// constant.113if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())114return false;115
116ConstantDataSequential *CDS =117dyn_cast<ConstantDataSequential>(GV->getInitializer());118if (!CDS)119return false;120
121// We might have a vector load from an array. FIXME: for now we just bail122// out in this case, but we should be able to resolve and simplify such123// loads.124if (CDS->getElementType() != I.getType())125return false;126
127unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;128if (SimplifiedAddrOp->getValue().getActiveBits() > 64)129return false;130int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();131if (SimplifiedAddrOpV < 0) {132// FIXME: For now we conservatively ignore out of bound accesses, but133// we're allowed to perform the optimization in this case.134return false;135}136uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;137if (Index >= CDS->getNumElements()) {138// FIXME: For now we conservatively ignore out of bound accesses, but139// we're allowed to perform the optimization in this case.140return false;141}142
143Constant *CV = CDS->getElementAsConstant(Index);144assert(CV && "Constant expected.");145SimplifiedValues[&I] = CV;146
147return true;148}
149
150/// Try to simplify cast instruction.
151bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {152Value *Op = I.getOperand(0);153if (Value *Simplified = SimplifiedValues.lookup(Op))154Op = Simplified;155
156// The cast can be invalid, because SimplifiedValues contains results of SCEV157// analysis, which operates on integers (and, e.g., might convert i8* null to158// i32 0).159if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {160const DataLayout &DL = I.getDataLayout();161if (Value *V = simplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {162SimplifiedValues[&I] = V;163return true;164}165}166
167return Base::visitCastInst(I);168}
169
170/// Try to simplify cmp instruction.
171bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {172Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);173
174// First try to handle simplified comparisons.175if (!isa<Constant>(LHS))176if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))177LHS = SimpleLHS;178if (!isa<Constant>(RHS))179if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))180RHS = SimpleRHS;181
182if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {183auto SimplifiedLHS = SimplifiedAddresses.find(LHS);184if (SimplifiedLHS != SimplifiedAddresses.end()) {185auto SimplifiedRHS = SimplifiedAddresses.find(RHS);186if (SimplifiedRHS != SimplifiedAddresses.end()) {187SimplifiedAddress &LHSAddr = SimplifiedLHS->second;188SimplifiedAddress &RHSAddr = SimplifiedRHS->second;189if (LHSAddr.Base == RHSAddr.Base) {190LHS = LHSAddr.Offset;191RHS = RHSAddr.Offset;192}193}194}195}196
197const DataLayout &DL = I.getDataLayout();198if (Value *V = simplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {199SimplifiedValues[&I] = V;200return true;201}202
203return Base::visitCmpInst(I);204}
205
206bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {207// Run base visitor first. This way we can gather some useful for later208// analysis information.209if (Base::visitPHINode(PN))210return true;211
212// The loop induction PHI nodes are definitionally free.213return PN.getParent() == L->getHeader();214}
215
216bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {217return simplifyInstWithSCEV(&I);218}
219