Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -104,6 +104,7 @@ void initializeConstantHoistingLegacyPassPass(PassRegistry&); void initializeConstantMergeLegacyPassPass(PassRegistry&); void initializeConstantPropagationPass(PassRegistry&); +void initializeConstantFoldAnalysisLegacyPassPass(PassRegistry&); void initializeControlHeightReductionLegacyPassPass(PassRegistry&); void initializeCorrelatedValuePropagationPass(PassRegistry&); void initializeCostModelAnalysisPass(PassRegistry&); Index: include/llvm/Transforms/InstCombine/ConstantFoldAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Transforms/InstCombine/ConstantFoldAnalysis.h @@ -0,0 +1,59 @@ +//===-- ConstantFoldAnalysis.h - Constant Folding Analysis +//-------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass Analysis the each instruction and if have any constant numbers +// in any instruction will push that instruction and constant number into +// vector. This information will usefull when we are folding(creating big +// constants) the instructions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTFOLDANALYSIS_H +#define LLVM_TRANSFORMS_SCALAR_CONSTANTFOLDANALYSIS_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +// Struct contains the constant original value and Insrtucion, +// If constant value is able to cananicalized then current value +// will change otherwise both will be same. +struct ConstInst { + unsigned OriginalValue; + unsigned CurrentValue; + Instruction *ConstInstruction; +}; + +class ConstantFoldAnalysisLegacyPass : public FunctionPass { +public: + static char ID; // Pass identification + ConstantFoldAnalysisLegacyPass() : FunctionPass(ID) { + initializeConstantFoldAnalysisLegacyPassPass( + *PassRegistry::getPassRegistry()); + } + // return the list of Const Instructions. + SmallVector getConstInstList(); + bool runOnFunction(Function &F) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +class ConstantFoldAnalysisPass + : public PassInfoMixin { + friend AnalysisInfoMixin; + +public: + using Result = SmallVector; + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +FunctionPass *createConstantFoldAnalysisPass(); +} // namespace llvm +#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTFOLDANALYSIS_H Index: lib/Transforms/InstCombine/CMakeLists.txt =================================================================== --- lib/Transforms/InstCombine/CMakeLists.txt +++ lib/Transforms/InstCombine/CMakeLists.txt @@ -17,6 +17,7 @@ InstCombineShifts.cpp InstCombineSimplifyDemanded.cpp InstCombineVectorOps.cpp + ConstantFoldAnalysis.cpp ADDITIONAL_HEADER_DIRS ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms Index: lib/Transforms/InstCombine/ConstantFoldAnalysis.cpp =================================================================== --- /dev/null +++ lib/Transforms/InstCombine/ConstantFoldAnalysis.cpp @@ -0,0 +1,114 @@ +//===-- ConstantFoldAnalysis.cpp +//-------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass Analysis the each instruction and if have any constant numbers +// in any instruction will push that instruction and constant number into +// vector. This information will usefull when we are folding(creating big +// constants) the instructions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/InstCombine/ConstantFoldAnalysis.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" +using namespace llvm; + +#define DEBUG_TYPE "ConstantFoldAnalysis" + +SmallVector ConstInstList; + +static bool ProcessBlock(BasicBlock &BB) { + // iterate through each instruction + for (Instruction &I : BB) { + unsigned NumOps = I.getNumOperands(); + // iterate through each operand + for (unsigned i = 0; i < NumOps; i++) { + Value *Op1 = I.getOperand(i); + // checking if any operand is constant int in current instruction + auto *Op1C = dyn_cast(Op1); + if (Op1C) { + unsigned Op1ConstValue = Op1C->getUniqueInteger().getZExtValue(); + bool isConstThere = false; + if (ConstInstList.size() != 0) { + // we are iterating through the list of insructions + for (SmallVector::iterator it = ConstInstList.begin(); + it != ConstInstList.end(); ++it) { + if (it->ConstInstruction != &I) { + isConstThere = true; + } + } + } + if (ConstInstList.size() == 0 || isConstThere) { + // creating the object of struct + ConstInst CIObj; + CIObj.OriginalValue = Op1ConstValue; + CIObj.CurrentValue = Op1ConstValue; + CIObj.ConstInstruction = &I; + // pushing the struct object into vector list. + ConstInstList.push_back(CIObj); + } + } + } + } + return true; +} + +static bool iterativelyAnalyzeInstructions(Function &F) { + // Clear the ConstInstList Vector Elements before iterating through new + // function. + ConstInstList.clear(); + // Process all basic blocks. + for (BasicBlock &I : F) + ProcessBlock(I); + return true; +} + +PreservedAnalyses ConstantFoldAnalysisPass::run(Function &F, + FunctionAnalysisManager &AM) { + + iterativelyAnalyzeInstructions(F); + + return PreservedAnalyses::all(); +} + +// return the Constant Instruction list. +SmallVector ConstantFoldAnalysisLegacyPass::getConstInstList() { + return ConstInstList; +} + +bool ConstantFoldAnalysisLegacyPass::runOnFunction(Function &F) { + return iterativelyAnalyzeInstructions(F); +} + +void ConstantFoldAnalysisLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} + +char ConstantFoldAnalysisLegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(ConstantFoldAnalysisLegacyPass, "constantfoldanalysis", + "Constant Fold Analysis", false, false) + +INITIALIZE_PASS_END(ConstantFoldAnalysisLegacyPass, "constantfoldanalysis", + "Constant Fold Analysis", false, false) + +FunctionPass *llvm::createConstantFoldAnalysisPass() { + return new ConstantFoldAnalysisLegacyPass(); +} Index: lib/Transforms/InstCombine/InstCombineCompares.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCompares.cpp +++ lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -4880,7 +4880,8 @@ Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); unsigned Op0Cplxity = getComplexity(Op0); unsigned Op1Cplxity = getComplexity(Op1); - + + SmallVector CFA = getConstantFoldInstList(); /// Orders the operands of the compare so that they are listed from most /// complex to least complex. This puts constants before unary operators, /// before binary operators. @@ -4916,8 +4917,30 @@ if (Instruction *Res = canonicalizeICmpBool(I, Builder)) return Res; - if (ICmpInst *NewICmp = canonicalizeCmpWithConstant(I)) + if (ICmpInst *NewICmp = canonicalizeCmpWithConstant(I)) { + // numUses of 'I' instruction constant number. + unsigned constNumUses = Op1->getNumUses(); + // here we are iterate through constant instructions list, + // if 'I' instruction is maching with any one of the instruction in list, + // and numUses of constant number is more than one. + // Then update current(NewICmp) inst const value with CFA it current + // value and update the instruction also. + for (SmallVector::iterator it = CFA.begin(); + it != CFA.end(); + ++it ) { + // checking the current instruction(I) is match with any of the + // instruction in list. + if (it->ConstInstruction == &I && constNumUses > 1) { + auto *NewOpC = dyn_cast(NewICmp->getOperand(1)); + it->CurrentValue = NewOpC->getUniqueInteger().getZExtValue(); + it->ConstInstruction = NewICmp; + break; + } + } + // setting the updated CFA. + setConstantFoldInstList(CFA); return NewICmp; + } if (Instruction *Res = foldICmpWithConstant(I)) return Res; @@ -4970,8 +4993,31 @@ } } - if (Instruction *Res = foldICmpInstWithConstant(I)) - return Res; + // Here we are checking if constant current value(after cananicalized) + // and this instruction(I) constant value both should same, both + // instructions are should same, and Original value and this instruction + // constant value should not same, then Do not fold(create big constant) + // constant number else fold the instruction. + bool isFoldableInst = false; + for (SmallVector::iterator it = CFA.begin(); + it != CFA.end(); + ++it ) { + auto *OpCInt = dyn_cast(Op1); + if (!OpCInt) + break; + if (it->ConstInstruction == &I && + it->CurrentValue == OpCInt->getZExtValue() && + it->OriginalValue != OpCInt->getZExtValue()) { + isFoldableInst = true; + } + } + + // if the constant number is unsing more than one's in current + // function(as per above checkings) don't fold the + // instruction(do not create big constants). + if (!isFoldableInst) + if (Instruction *Res = foldICmpInstWithConstant(I)) + return Res; if (Instruction *Res = foldICmpInstWithConstantNotInt(I)) return Res; Index: lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- lib/Transforms/InstCombine/InstCombineInternal.h +++ lib/Transforms/InstCombine/InstCombineInternal.h @@ -41,6 +41,7 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/InstCombine/ConstantFoldAnalysis.h" #include #include @@ -282,12 +283,10 @@ public: /// A worklist of the instructions that need to be simplified. InstCombineWorklist &Worklist; - /// An IRBuilder that automatically inserts new instructions into the /// worklist. using BuilderTy = IRBuilder; BuilderTy &Builder; - private: // Mode in which we are running the combiner. const bool MinimizeSize; @@ -304,7 +303,7 @@ const DataLayout &DL; const SimplifyQuery SQ; OptimizationRemarkEmitter &ORE; - + SmallVector ConstantFoldInstList; // Optional analyses. When non-null, these can both be used to do better // combining and will be updated to reflect any changes. LoopInfo *LI; @@ -336,6 +335,15 @@ TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; } + // setting the constant fold instruction list + void setConstantFoldInstList(SmallVector CFA) { + ConstantFoldInstList = CFA; + } + + // return the constant fold instruction list + SmallVector getConstantFoldInstList() { + return ConstantFoldInstList; + } // Visitation implementation - Implement instruction combining for different // instruction types. The semantics are as follows: // Return Value: Index: lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- lib/Transforms/InstCombine/InstructionCombining.cpp +++ lib/Transforms/InstCombine/InstructionCombining.cpp @@ -96,6 +96,7 @@ #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/InstCombine/ConstantFoldAnalysis.h" #include #include #include @@ -3433,10 +3434,12 @@ return MadeIRChange; } + static bool combineInstructionsOverFunction( - Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, - AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, - OptimizationRemarkEmitter &ORE, bool ExpensiveCombines = true, + Function &F, InstCombineWorklist &Worklist, + AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, + DominatorTree &DT, OptimizationRemarkEmitter &ORE, + SmallVector CFA, bool ExpensiveCombines = true, LoopInfo *LI = nullptr) { auto &DL = F.getParent()->getDataLayout(); ExpensiveCombines |= EnableExpensiveCombines; @@ -3469,7 +3472,8 @@ InstCombiner IC(Worklist, Builder, F.optForMinSize(), ExpensiveCombines, AA, AC, TLI, DT, ORE, DL, LI); IC.MaxArraySizeForCombine = MaxArraySize; - + + IC.setConstantFoldInstList(CFA); if (!IC.run()) break; } @@ -3483,12 +3487,11 @@ auto &DT = AM.getResult(F); auto &TLI = AM.getResult(F); auto &ORE = AM.getResult(F); - + SmallVector CFA; auto *LI = AM.getCachedResult(F); - auto *AA = &AM.getResult(F); if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, - ExpensiveCombines, LI)) + CFA, ExpensiveCombines, LI)) // No changes, all analyses are preserved. return PreservedAnalyses::all(); @@ -3512,6 +3515,8 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); } bool InstructionCombiningPass::runOnFunction(Function &F) { @@ -3524,13 +3529,13 @@ auto &TLI = getAnalysis().getTLI(); auto &DT = getAnalysis().getDomTree(); auto &ORE = getAnalysis().getORE(); - + SmallVector CFA = getAnalysis().getConstInstList(); // Optional analyses. auto *LIWP = getAnalysisIfAvailable(); auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, - ExpensiveCombines, LI); + CFA, ExpensiveCombines, LI); } char InstructionCombiningPass::ID = 0; @@ -3543,6 +3548,7 @@ INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ConstantFoldAnalysisLegacyPass) INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine", "Combine redundant instructions", false, false) Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -2397,7 +2397,6 @@ // Change the PHI node into a select instruction. Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); - Value *Sel = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", InsertPt); PN->replaceAllUsesWith(Sel); Sel->takeName(PN); Index: test/Transforms/InstCombine/do_not_create_large_constants.ll =================================================================== --- /dev/null +++ test/Transforms/InstCombine/do_not_create_large_constants.ll @@ -0,0 +1,28 @@ +;RUN: llc %s -o - -verify-machineinstrs | FileCheck %s + +target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" +target triple = "aarch64-arm-none-eabi" + +; Function Attrs: minsize norecurse nounwind optsize readnone +;CHECK-LABEL: @test +;CHECK: mul +;CHECK-NEXT: orr +;CHECK-NEXT: asr +;CHECK-NEXT: cmp +;CHECK-NEXT: csel +;CHECK-NEXT: ret +define dso_local i32 @test(i32, i32) local_unnamed_addr #0 { + %3 = mul nsw i32 %1, %0 + %4 = ashr i32 %3, 8 + %5 = icmp slt i32 %4, 4096 + %6 = select i1 %5, i32 %4, i32 4096 + ret i32 %6 +} + +attributes #0 = { minsize norecurse nounwind optsize readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-a53" "target-features"="+aes,+crc,+crypto,+fp-armv8,+neon,+sha2" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!llvm.module.flags = !{!0} +!llvm.ident = !{!1} + +!0 = !{i32 1, !"wchar_size", i32 4} +!1 = !{!"clang version 9.0.0 (https://git.llvm.org/git/clang.git/ 2e53b8068e17d5347f6fc63e68faa2bf8531fb28) (https://git.llvm.org/git/llvm.git/ 4c1861d5b115a9ef6385f650b1ac70d75a7a29e5)"}