202 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements UnrolledInstAnalyzer class. It's used for predicting10// potential effects that loop unrolling might have, such as enabling constant11// propagation and other optimizations.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/Analysis/LoopUnrollAnalyzer.h"16#include "llvm/Analysis/ConstantFolding.h"17#include "llvm/Analysis/InstructionSimplify.h"18#include "llvm/Analysis/LoopInfo.h"19#include "llvm/Analysis/ScalarEvolutionExpressions.h"20#include "llvm/IR/Operator.h"21 22using namespace llvm;23 24/// Try to simplify instruction \param I using its SCEV expression.25///26/// The idea is that some AddRec expressions become constants, which then27/// could trigger folding of other instructions. However, that only happens28/// for expressions whose start value is also constant, which isn't always the29/// case. In another common and important case the start value is just some30/// address (i.e. SCEVUnknown) - in this case we compute the offset and save31/// it along with the base address instead.32bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {33 if (!SE.isSCEVable(I->getType()))34 return false;35 36 const SCEV *S = SE.getSCEV(I);37 if (auto *SC = dyn_cast<SCEVConstant>(S)) {38 SimplifiedValues[I] = SC->getValue();39 return true;40 }41 42 // If we have a loop invariant computation, we only need to compute it once.43 // Given that, all but the first occurance are free.44 if (!IterationNumber->isZero() && SE.isLoopInvariant(S, L))45 return true;46 47 auto *AR = dyn_cast<SCEVAddRecExpr>(S);48 if (!AR || AR->getLoop() != L)49 return false;50 51 const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);52 // Check if the AddRec expression becomes a constant.53 if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {54 SimplifiedValues[I] = SC->getValue();55 return true;56 }57 58 // Check if the offset from the base address becomes a constant.59 auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));60 if (!Base)61 return false;62 std::optional<APInt> Offset =63 SE.computeConstantDifference(ValueAtIteration, Base);64 if (!Offset)65 return false;66 SimplifiedAddress Address;67 Address.Base = Base->getValue();68 Address.Offset = *Offset;69 SimplifiedAddresses[I] = Address;70 return false;71}72 73/// Try to simplify binary operator I.74///75/// TODO: Probably it's worth to hoist the code for estimating the76/// simplifications effects to a separate class, since we have a very similar77/// code in InlineCost already.78bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {79 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);80 if (!isa<Constant>(LHS))81 if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))82 LHS = SimpleLHS;83 if (!isa<Constant>(RHS))84 if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))85 RHS = SimpleRHS;86 87 Value *SimpleV = nullptr;88 const DataLayout &DL = I.getDataLayout();89 if (auto FI = dyn_cast<FPMathOperator>(&I))90 SimpleV =91 simplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);92 else93 SimpleV = simplifyBinOp(I.getOpcode(), LHS, RHS, DL);94 95 if (SimpleV) {96 SimplifiedValues[&I] = SimpleV;97 return true;98 }99 return Base::visitBinaryOperator(I);100}101 102/// Try to fold load I.103bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {104 Value *AddrOp = I.getPointerOperand();105 106 auto AddressIt = SimplifiedAddresses.find(AddrOp);107 if (AddressIt == SimplifiedAddresses.end())108 return false;109 110 auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);111 // We're only interested in loads that can be completely folded to a112 // constant.113 if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())114 return false;115 116 Constant *Res =117 ConstantFoldLoadFromConst(GV->getInitializer(), I.getType(),118 AddressIt->second.Offset, I.getDataLayout());119 if (!Res)120 return false;121 122 SimplifiedValues[&I] = Res;123 return true;124}125 126/// Try to simplify cast instruction.127bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {128 Value *Op = I.getOperand(0);129 if (Value *Simplified = SimplifiedValues.lookup(Op))130 Op = Simplified;131 132 // The cast can be invalid, because SimplifiedValues contains results of SCEV133 // analysis, which operates on integers (and, e.g., might convert i8* null to134 // i32 0).135 if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {136 const DataLayout &DL = I.getDataLayout();137 if (Value *V = simplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {138 SimplifiedValues[&I] = V;139 return true;140 }141 }142 143 return Base::visitCastInst(I);144}145 146/// Try to simplify cmp instruction.147bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {148 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);149 150 // First try to handle simplified comparisons.151 if (!isa<Constant>(LHS))152 if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))153 LHS = SimpleLHS;154 if (!isa<Constant>(RHS))155 if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))156 RHS = SimpleRHS;157 158 if (!isa<Constant>(LHS) && !isa<Constant>(RHS) && !I.isSigned()) {159 auto SimplifiedLHS = SimplifiedAddresses.find(LHS);160 if (SimplifiedLHS != SimplifiedAddresses.end()) {161 auto SimplifiedRHS = SimplifiedAddresses.find(RHS);162 if (SimplifiedRHS != SimplifiedAddresses.end()) {163 SimplifiedAddress &LHSAddr = SimplifiedLHS->second;164 SimplifiedAddress &RHSAddr = SimplifiedRHS->second;165 if (LHSAddr.Base == RHSAddr.Base) {166 // FIXME: This is only correct for equality predicates. For167 // unsigned predicates, this only holds if we have nowrap flags,168 // which we don't track (for nuw it's valid as-is, for nusw it169 // requires converting the predicated to signed). As this is used only170 // for cost modelling, this is not a correctness issue.171 bool Res = ICmpInst::compare(LHSAddr.Offset, RHSAddr.Offset,172 I.getPredicate());173 SimplifiedValues[&I] = ConstantInt::getBool(I.getType(), Res);174 return true;175 }176 }177 }178 }179 180 const DataLayout &DL = I.getDataLayout();181 if (Value *V = simplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {182 SimplifiedValues[&I] = V;183 return true;184 }185 186 return Base::visitCmpInst(I);187}188 189bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {190 // Run base visitor first. This way we can gather some useful for later191 // analysis information.192 if (Base::visitPHINode(PN))193 return true;194 195 // The loop induction PHI nodes are definitionally free.196 return PN.getParent() == L->getHeader();197}198 199bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {200 return simplifyInstWithSCEV(&I);201}202