14c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar//===- LoopInterchange.cpp - Loop interchange pass------------------------===// 24c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// 34c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// The LLVM Compiler Infrastructure 44c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// 54c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// This file is distributed under the University of Illinois Open Source 64c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// License. See LICENSE.TXT for details. 74c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// 84c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar//===----------------------------------------------------------------------===// 94c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// 104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// This Pass handles loop interchange transform. 114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// This pass interchanges loops to provide a more cache-friendly memory access 124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// patterns. 134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// 144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar//===----------------------------------------------------------------------===// 154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/ADT/SmallVector.h" 174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/AliasAnalysis.h" 184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/AssumptionCache.h" 194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/BlockFrequencyInfo.h" 204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/CodeMetrics.h" 214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/DependenceAnalysis.h" 224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/LoopInfo.h" 234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/LoopIterator.h" 244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/LoopPass.h" 254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/ScalarEvolution.h" 264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/ScalarEvolutionExpander.h" 274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/ScalarEvolutionExpressions.h" 284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/TargetTransformInfo.h" 294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Analysis/ValueTracking.h" 304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Dominators.h" 314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Function.h" 324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/IRBuilder.h" 334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/InstIterator.h" 344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/IntrinsicInst.h" 356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar#include "llvm/IR/Module.h" 364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Pass.h" 374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/Debug.h" 384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Transforms/Scalar.h" 404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Transforms/Utils/BasicBlockUtils.h" 414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Transforms/Utils/LoopUtils.h" 424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Transforms/Utils/SSAUpdater.h" 434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarusing namespace llvm; 444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#define DEBUG_TYPE "loop-interchange" 464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarnamespace { 484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainartypedef SmallVector<Loop *, 8> LoopVector; 504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// TODO: Check if we can use a sparse matrix here. 524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainartypedef std::vector<std::vector<char>> CharMatrix; 534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// Maximum number of dependencies that can be handled in the dependency matrix. 554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic const unsigned MaxMemInstrCount = 100; 564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// Maximum loop depth supported. 584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic const unsigned MaxLoopNestDepth = 10; 594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstruct LoopInterchange; 614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#ifdef DUMP_DEP_MATRICIES 634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid printDepMatrix(CharMatrix &DepMatrix) { 644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (auto I = DepMatrix.begin(), E = DepMatrix.end(); I != E; ++I) { 654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::vector<char> Vec = *I; 664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (auto II = Vec.begin(), EE = Vec.end(); II != EE; ++II) 674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << *II << " "); 684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "\n"); 694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#endif 724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Loop *L, DependenceInfo *DI) { 754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar typedef SmallVector<Value *, 16> ValueVector; 764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ValueVector MemInstr; 774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Level > MaxLoopNestDepth) { 794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Cannot handle loops of depth greater than " 804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << MaxLoopNestDepth << "\n"); 814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // For each block. 854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end(); 864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BB != BE; ++BB) { 874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Scan the BB and collect legal loads and stores. 884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; 894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ++I) { 904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction *Ins = dyn_cast<Instruction>(I); 914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!Ins) 924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoadInst *Ld = dyn_cast<LoadInst>(I); 944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar StoreInst *St = dyn_cast<StoreInst>(I); 954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!St && !Ld) 964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Ld && !Ld->isSimple()) 984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (St && !St->isSimple()) 1004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 101f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MemInstr.push_back(&*I); 1024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Found " << MemInstr.size() 1064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << " Loads and Stores to analyze\n"); 1074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ValueVector::iterator I, IE, J, JE; 1094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) { 1114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (J = I, JE = MemInstr.end(); J != JE; ++J) { 1124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::vector<char> Dep; 1134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction *Src = dyn_cast<Instruction>(*I); 1144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction *Des = dyn_cast<Instruction>(*J); 1154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Src == Des) 1164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 1174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isa<LoadInst>(Src) && isa<LoadInst>(Des)) 1184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (auto D = DI->depends(Src, Des, true)) { 1204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Found Dependency between Src=" << Src << " Des=" << Des 1214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << "\n"); 1224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (D->isFlow()) { 1234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: Handle Flow dependence.Check if it is sufficient to populate 1244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // the Dependence Matrix with the direction reversed. 1254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Flow dependence not handled"); 1264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 1274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (D->isAnti()) { 1294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Found Anti dependence \n"); 1304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned Levels = D->getLevels(); 1314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar char Direction; 1324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned II = 1; II <= Levels; ++II) { 1334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *Distance = D->getDistance(II); 1344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEVConstant *SCEVConst = 1354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast_or_null<SCEVConstant>(Distance); 1364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (SCEVConst) { 1374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const ConstantInt *CI = SCEVConst->getValue(); 1384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (CI->isNegative()) 1394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '<'; 1404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else if (CI->isZero()) 1414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '='; 1424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 1434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '>'; 1444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Dep.push_back(Direction); 1454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else if (D->isScalar(II)) { 1464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = 'S'; 1474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Dep.push_back(Direction); 1484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { 1494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned Dir = D->getDirection(II); 1504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Dir == Dependence::DVEntry::LT || 1514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Dir == Dependence::DVEntry::LE) 1524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '<'; 1534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else if (Dir == Dependence::DVEntry::GT || 1544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Dir == Dependence::DVEntry::GE) 1554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '>'; 1564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else if (Dir == Dependence::DVEntry::EQ) 1574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '='; 1584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 1594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Direction = '*'; 1604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Dep.push_back(Direction); 1614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar while (Dep.size() != Level) { 1644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Dep.push_back('I'); 1654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DepMatrix.push_back(Dep); 1684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix.size() > MaxMemInstrCount) { 1694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount 1704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << " dependencies inside loop\n"); 1714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 1724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 178f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // We don't have a DepMatrix to check legality return false. 1794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix.size() == 0) 1804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 1814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 1824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 1834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// A loop is moved from index 'from' to an index 'to'. Update the Dependence 1854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// matrix by exchanging the two columns. 1866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx, 1876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned ToIndx) { 1884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned numRows = DepMatrix.size(); 1894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < numRows; ++i) { 1904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar char TmpVal = DepMatrix[i][ToIndx]; 1914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx]; 1924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DepMatrix[i][FromIndx] = TmpVal; 1934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 1954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// Checks if outermost non '=','S'or'I' dependence in the dependence matrix is 1974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// '>' 1986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row, 1996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Column) { 2004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i <= Column; ++i) { 2014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix[Row][i] == '<') 2024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix[Row][i] == '>') 2044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // All dependencies were '=','S' or 'I' 2074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 2094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// Checks if no dependence exist in the dependency matrix in Row before Column. 2116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, 2126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Column) { 2134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < Column; ++i) { 2144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix[Row][i] != '=' || DepMatrix[Row][i] != 'S' || 2154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DepMatrix[Row][i] != 'I') 2164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 2204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, 2226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned OuterLoopId, char InnerDep, 2236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar char OuterDep) { 2244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId)) 2264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerDep == OuterDep) 2294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // It is legal to interchange if and only if after interchange no row has a 2324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // '>' direction as the leftmost non-'='. 2334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I') 2354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerDep == '<') 2384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerDep == '>') { 2414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If OuterLoopId represents outermost loop then interchanging will make the 2424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 1st dependency as '>' 2434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterLoopId == 0) 2444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If all dependencies before OuterloopId are '=','S'or 'I'. Then 2474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // interchanging will result in this row having an outermost non '=' 2484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // dependency of '>' 2494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!containsNoDependence(DepMatrix, Row, OuterLoopId)) 2504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 2554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// Checks if it is legal to interchange 2 loops. 2576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar// [Theorem] A permutation of the loops in a perfect nest is legal if and only 2586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar// if 2594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// the direction matrix, after the same permutation is applied to its columns, 2604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// has no ">" direction as the leftmost non-"=" direction in any row. 2616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, 2626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned InnerLoopId, 2636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned OuterLoopId) { 2644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned NumRows = DepMatrix.size(); 2664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // For each row check if it is valid to interchange. 2674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned Row = 0; Row < NumRows; ++Row) { 2684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar char InnerDep = DepMatrix[Row][InnerLoopId]; 2694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar char OuterDep = DepMatrix[Row][OuterLoopId]; 2704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerDep == '*' || OuterDep == '*') 2714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, 2734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterDep)) 2744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 2774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 2784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) { 2804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Calling populateWorklist called\n"); 2824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopVector LoopList; 2834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *CurrentLoop = &L; 284f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops(); 285f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar while (!Vec->empty()) { 2864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // The current loop has multiple subloops in it hence it is not tightly 2874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // nested. 2884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Discard all loops above it added into Worklist. 289f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Vec->size() != 1) { 2904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopList.clear(); 2914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return; 2924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopList.push_back(CurrentLoop); 294f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CurrentLoop = Vec->front(); 295f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Vec = &CurrentLoop->getSubLoops(); 2964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopList.push_back(CurrentLoop); 298f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar V.push_back(std::move(LoopList)); 2994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 3004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) { 3024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PHINode *InnerIndexVar = L->getCanonicalInductionVariable(); 3034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerIndexVar) 3044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InnerIndexVar; 3054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr) 3064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return nullptr; 3074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 3084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PHINode *PhiVar = cast<PHINode>(I); 3094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Type *PhiTy = PhiVar->getType(); 3104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() && 3114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar !PhiTy->isPointerTy()) 3124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return nullptr; 3134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEVAddRecExpr *AddRec = 3144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar)); 3154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!AddRec || !AddRec->isAffine()) 3164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 3174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *Step = AddRec->getStepRecurrence(*SE); 3184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); 3194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!C) 3204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 3214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Found the induction variable. 3224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // FIXME: Handle loops with more than one induction variable. Note that, 3234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // currently, legality makes sure we have only one induction variable. 3244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return PhiVar; 3254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 3264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return nullptr; 3274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 3284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// LoopInterchangeLegality checks if it is legal to interchange the loop. 3304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarclass LoopInterchangeLegality { 3314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarpublic: 3324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE, 333f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA) 334f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), 335f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PreserveLCSSA(PreserveLCSSA), InnerLoopHasReduction(false) {} 3364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Check if the loops can be interchanged. 3384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId, 3394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CharMatrix &DepMatrix); 3404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Check if the loop structure is understood. We do not handle triangular 3414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// loops for now. 3424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool isLoopStructureUnderstood(PHINode *InnerInductionVar); 3434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool currentLimitations(); 3454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool hasInnerLoopReduction() { return InnerLoopHasReduction; } 3476948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 3484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarprivate: 3494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool tightlyNested(Loop *Outer, Loop *Inner); 3506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool containsUnsafeInstructionsInHeader(BasicBlock *BB); 3516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool areAllUsesReductions(Instruction *Ins, Loop *L); 3526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool containsUnsafeInstructionsInLatch(BasicBlock *BB); 3536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool findInductionAndReductions(Loop *L, 3546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> &Inductions, 3556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> &Reductions); 3564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterLoop; 3574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *InnerLoop; 3584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ScalarEvolution *SE; 360f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LoopInfo *LI; 361f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar DominatorTree *DT; 362f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool PreserveLCSSA; 3636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 3646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool InnerLoopHasReduction; 3654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar}; 3664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// LoopInterchangeProfitability checks if it is profitable to interchange the 3684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// loop. 3694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarclass LoopInterchangeProfitability { 3704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarpublic: 3714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE) 3724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar : OuterLoop(Outer), InnerLoop(Inner), SE(SE) {} 3734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 374f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// Check if the loop interchange is profitable. 3754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId, 3764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CharMatrix &DepMatrix); 3774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarprivate: 3794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar int getInstrOrderCost(); 3804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterLoop; 3824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *InnerLoop; 3834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Scev analysis. 3854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ScalarEvolution *SE; 3864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar}; 3874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 388f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// LoopInterchangeTransform interchanges the loop. 3894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarclass LoopInterchangeTransform { 3904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarpublic: 3914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE, 3924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInfo *LI, DominatorTree *DT, 393f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BasicBlock *LoopNestExit, 3946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool InnerLoopContainsReductions) 3954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), 3966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopExit(LoopNestExit), 3976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar InnerLoopHasReduction(InnerLoopContainsReductions) {} 3984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Interchange OuterLoop and InnerLoop. 4004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool transform(); 4014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void restructureLoops(Loop *InnerLoop, Loop *OuterLoop); 4024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop); 4034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarprivate: 4054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void splitInnerLoopLatch(Instruction *); 4064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void splitInnerLoopHeader(); 4074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool adjustLoopLinks(); 4084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void adjustLoopPreheaders(); 4094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool adjustLoopBranches(); 4106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred, 4116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *NewPred); 4124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterLoop; 4144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *InnerLoop; 4154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Scev analysis. 4174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ScalarEvolution *SE; 4184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInfo *LI; 4194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DominatorTree *DT; 4204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *LoopExit; 4216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool InnerLoopHasReduction; 4224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar}; 4234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 424f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// Main LoopInterchange Pass. 4254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstruct LoopInterchange : public FunctionPass { 4264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar static char ID; 4274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ScalarEvolution *SE; 4284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInfo *LI; 429de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DependenceInfo *DI; 4304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DominatorTree *DT; 431f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool PreserveLCSSA; 4324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInterchange() 433de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : FunctionPass(ID), SE(nullptr), LI(nullptr), DI(nullptr), DT(nullptr) { 4344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar initializeLoopInterchangePass(*PassRegistry::getPassRegistry()); 4354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void getAnalysisUsage(AnalysisUsage &AU) const override { 438f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addRequired<ScalarEvolutionWrapperPass>(); 439f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addRequired<AAResultsWrapperPass>(); 4404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar AU.addRequired<DominatorTreeWrapperPass>(); 4414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar AU.addRequired<LoopInfoWrapperPass>(); 442de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addRequired<DependenceAnalysisWrapperPass>(); 4434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar AU.addRequiredID(LoopSimplifyID); 4444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar AU.addRequiredID(LCSSAID); 4454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool runOnFunction(Function &F) override { 448de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipFunction(F)) 449de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 450de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 451f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 4524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 453de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI(); 4544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 4554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DT = DTWP ? &DTWP->getDomTree() : nullptr; 456f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); 457f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 4584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Build up a worklist of loop pairs to analyze. 4594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SmallVector<LoopVector, 8> Worklist; 4604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (Loop *L : *LI) 4624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar populateWorklist(*L, Worklist); 4634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n"); 4654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool Changed = true; 4664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar while (!Worklist.empty()) { 4674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopVector LoopList = Worklist.pop_back_val(); 4686948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Changed = processLoopList(LoopList, F); 4694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return Changed; 4714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool isComputableLoopNest(LoopVector LoopList) { 474de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Loop *L : LoopList) { 4754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L); 4764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (ExitCountOuter == SE->getCouldNotCompute()) { 4774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Couldn't compute Backedge count\n"); 4784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 4794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (L->getNumBackEdges() != 1) { 4814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "NumBackEdges is not equal to 1\n"); 4824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 4834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!L->getExitingBlock()) { 4854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Loop Doesn't have unique exit block\n"); 4864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 4874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 4904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 492de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned selectLoopForInterchange(const LoopVector &LoopList) { 4934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: Add a better heuristic to select the loop to be interchanged based 494f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // on the dependence matrix. Currently we select the innermost loop. 4954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return LoopList.size() - 1; 4964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 4974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool processLoopList(LoopVector LoopList, Function &F) { 4996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 5004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool Changed = false; 5014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CharMatrix DependencyMatrix; 5024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (LoopList.size() < 2) { 5034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n"); 5044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!isComputableLoopNest(LoopList)) { 5074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Not vaild loop candidate for interchange\n"); 5084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterMostLoop = *(LoopList.begin()); 5114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size() 5134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << "\n"); 5144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(), 516de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OuterMostLoop, DI)) { 5174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Populating Dependency matrix failed\n"); 5184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#ifdef DUMP_DEP_MATRICIES 5214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Dependence before inter change \n"); 5224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar printDepMatrix(DependencyMatrix); 5234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#endif 5244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch(); 5264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *OuterMostLoopLatchBI = 5274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator()); 5284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!OuterMostLoopLatchBI) 5294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Since we currently do not handle LCSSA PHI's any failure in loop 5324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // condition will now branch to LoopNestExit. 5334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: This should be removed once we handle LCSSA PHI nodes. 5344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Get the Outermost loop exit. 5364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *LoopNestExit; 5374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader()) 5384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1); 5394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 5404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0); 5414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (isa<PHINode>(LoopNestExit->begin())) { 5436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now " 5446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar "since on failure all loops branch to loop nest exit.\n"); 5454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 5474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned SelecLoopId = selectLoopForInterchange(LoopList); 549f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Move the selected loop outwards to the best possible position. 5504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = SelecLoopId; i > 0; i--) { 5514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool Interchanged = 5524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix); 5534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!Interchanged) 5544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return Changed; 5554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Loops interchanged reflect the same in LoopList 5564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::swap(LoopList[i - 1], LoopList[i]); 5574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Update the DependencyMatrix 5594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar interChangeDepedencies(DependencyMatrix, i, i - 1); 5606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DT->recalculate(F); 5614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#ifdef DUMP_DEP_MATRICIES 5624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Dependence after inter change \n"); 5634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar printDepMatrix(DependencyMatrix); 5644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#endif 5654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Changed |= Interchanged; 5664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return Changed; 5684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool processLoop(LoopVector LoopList, unsigned InnerLoopId, 5714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned OuterLoopId, BasicBlock *LoopNestExit, 5724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::vector<std::vector<char>> &DependencyMatrix) { 5734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 5744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId 5754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << " and OuterLoopId = " << OuterLoopId << "\n"); 5764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *InnerLoop = LoopList[InnerLoopId]; 5774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterLoop = LoopList[OuterLoopId]; 5784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 579f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, LI, DT, 580f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PreserveLCSSA); 5814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) { 5824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n"); 5834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Loops are legal to interchange\n"); 5864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE); 5874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) { 5884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Interchanging Loops not profitable\n"); 5894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 5904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 592f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, 5936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopNestExit, LIL.hasInnerLoopReduction()); 5944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LIT.transform(); 5954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Loops interchanged\n"); 5964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 5974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 5984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar}; 5994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} // end of namespace 6016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) { 6026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool { 6036948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *UserIns = dyn_cast<PHINode>(U); 604f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RecurrenceDescriptor RD; 605f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD); 6066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar }); 6076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 6086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 6096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool LoopInterchangeLegality::containsUnsafeInstructionsInHeader( 6106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *BB) { 6116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (auto I = BB->begin(), E = BB->end(); I != E; ++I) { 6126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Load corresponding to reduction PHI's are safe while concluding if 6136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // tightly nested. 6146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (LoadInst *L = dyn_cast<LoadInst>(I)) { 6156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!areAllUsesReductions(L, InnerLoop)) 6166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 6176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 6186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 6196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 6206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 6216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 6224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool LoopInterchangeLegality::containsUnsafeInstructionsInLatch( 6246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *BB) { 6254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (auto I = BB->begin(), E = BB->end(); I != E; ++I) { 6266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Stores corresponding to reductions are safe while concluding if tightly 6276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // nested. 6286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (StoreInst *L = dyn_cast<StoreInst>(I)) { 6296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *PHI = dyn_cast<PHINode>(L->getOperand(0)); 6306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!PHI) 6316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 6326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 6334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 6344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 6354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 6364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 6374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) { 6394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); 6404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 6414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); 6424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Checking if Loops are Tightly Nested\n"); 6444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // A perfectly nested loop will not have any branch in between the outer and 6464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // inner block i.e. outer header will branch to either inner preheader and 6474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // outerloop latch. 6484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *outerLoopHeaderBI = 6494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(OuterLoopHeader->getTerminator()); 6504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!outerLoopHeaderBI) 6514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 6524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned num = outerLoopHeaderBI->getNumSuccessors(); 6534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < num; i++) { 6544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader && 6554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch) 6564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 6574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 6584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n"); 6604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We do not have any basic block in between now make sure the outer header 661f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // and outer loop latch doesn't contain any unsafe instructions. 6626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (containsUnsafeInstructionsInHeader(OuterLoopHeader) || 6636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar containsUnsafeInstructionsInLatch(OuterLoopLatch)) 6644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 6654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Loops are perfectly nested \n"); 6674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We have a perfect loop nest. 6684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 6694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 6704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeLegality::isLoopStructureUnderstood( 6734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PHINode *InnerInduction) { 6744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned Num = InnerInduction->getNumOperands(); 6764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader(); 6774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < Num; ++i) { 6784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *Val = InnerInduction->getOperand(i); 6794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isa<Constant>(Val)) 6804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 6814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction *I = dyn_cast<Instruction>(Val); 6824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!I) 6834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 6844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: Handle triangular loops. 6854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // e.g. for(int i=0;i<N;i++) 6864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(int j=i;j<N;j++) 6874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i); 6884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerInduction->getIncomingBlock(IncomBlockIndx) == 6894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopPreheader && 6904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar !OuterLoop->isLoopInvariant(I)) { 6914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 6924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 6934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 6944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 6954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 6964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 6976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool LoopInterchangeLegality::findInductionAndReductions( 6986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Loop *L, SmallVector<PHINode *, 8> &Inductions, 6996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> &Reductions) { 7006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!L->getLoopLatch() || !L->getLoopPredecessor()) 7016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 7026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 703f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RecurrenceDescriptor RD; 704f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InductionDescriptor ID; 7056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *PHI = cast<PHINode>(I); 706f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (InductionDescriptor::isInductionPHI(PHI, SE, ID)) 7076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Inductions.push_back(PHI); 708f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) 7096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Reductions.push_back(PHI); 7106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else { 7116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG( 7126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar dbgs() << "Failed to recognize PHI as an induction or reduction.\n"); 7136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 7146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 7156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 7166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 7176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 7186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 7196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) { 7206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (auto I = Block->begin(); isa<PHINode>(I); ++I) { 7216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *PHI = cast<PHINode>(I); 7226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Reduction lcssa phi will have only 1 incoming block that from loop latch. 7236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (PHI->getNumIncomingValues() > 1) 7246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 7256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Instruction *Ins = dyn_cast<Instruction>(PHI->getIncomingValue(0)); 7266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Ins) 7276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 7286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Incoming value for lcssa phi's in outer loop exit can only be inner loop 7296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // exits lcssa phi else it would not be tightly nested. 7306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!isa<PHINode>(Ins) && isOuterLoopExitBlock) 7316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 7326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 7336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 7346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 7356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 7366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock, 7376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *LoopHeader) { 7386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) { 7396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Num = BI->getNumSuccessors(); 7406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar assert(Num == 2); 7416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (unsigned i = 0; i < Num; ++i) { 7426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (BI->getSuccessor(i) == LoopHeader) 7436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar continue; 7446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return BI->getSuccessor(i); 7456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 7466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 7476948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 7486948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 7496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 7504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// This function indicates the current limitations in the transform as a result 7514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar// of which we do not proceed. 7524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeLegality::currentLimitations() { 7534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 7554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); 7564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); 7574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); 7586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); 7594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PHINode *InnerInductionVar; 7616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> Inductions; 7626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> Reductions; 7636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) 7644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 7654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // TODO: Currently we handle only loops with 1 induction variable. 7676948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Inductions.size() != 1) { 7686948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "We currently only support loops with 1 induction variable." 7696948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar << "Failed to interchange due to current limitation\n"); 7704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 7716948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 7726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Reductions.size() > 0) 7736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar InnerLoopHasReduction = true; 7744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar InnerInductionVar = Inductions.pop_back_val(); 7766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Reductions.clear(); 7776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) 7786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 7794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7806948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Outer loop cannot have reduction because then loops will not be tightly 7816948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // nested. 7826948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Reductions.empty()) 7836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 7846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // TODO: Currently we handle only loops with 1 induction variable. 7856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Inductions.size() != 1) 7864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 7874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: Triangular loops are not handled for now. 7894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!isLoopStructureUnderstood(InnerInductionVar)) { 7904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Loop structure not understood by pass\n"); 7914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 7924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 7934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // TODO: We only handle LCSSA PHI's corresponding to reduction for now. 7956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *LoopExitBlock = 7966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader); 7976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true)) 7984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 7996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 8006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader); 8016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false)) 8024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 8034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: Current limitation: Since we split the inner loop latch at the point 8054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // were induction variable is incremented (induction.next); We cannot have 8064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // more than 1 user of induction.next since it would result in broken code 8074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // after split. 8084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // e.g. 8094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(i=0;i<N;i++) { 8104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(j = 0;j<M;j++) { 8114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // A[j+1][i+2] = A[j][i]+k; 8124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // } 8134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // } 8144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction *InnerIndexVarInc = nullptr; 8154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader) 8164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerIndexVarInc = 8174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1)); 8184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 8194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerIndexVarInc = 8204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0)); 8214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!InnerIndexVarInc) 8234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 8244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Since we split the inner loop latch on this induction variable. Make sure 8264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // we do not have any instruction between the induction variable and branch 8274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // instruction. 8284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 829de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool FoundInduction = false; 830de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const Instruction &I : reverse(*InnerLoopLatch)) { 831de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I)) 8324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 8334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We found an instruction. If this is not induction variable then it is not 8344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // safe to split this loop latch. 835de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!I.isIdenticalTo(InnerIndexVarInc)) 8364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 837de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 838de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar FoundInduction = true; 839de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 8404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 841f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The loop latch ended and we didn't find the induction variable return as 8424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // current limitation. 8434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!FoundInduction) 8444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 8454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 8474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 8484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId, 8504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned OuterLoopId, 8514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CharMatrix &DepMatrix) { 8524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) { 8544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId 8554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << "and OuterLoopId = " << OuterLoopId 8564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << "due to dependence\n"); 8574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 8584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 8594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Create unique Preheaders if we already do not have one. 8614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); 8624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 8634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Create a unique outer preheader - 8654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 1) If OuterLoop preheader is not present. 8664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 2) If OuterLoop Preheader is same as OuterLoop Header 8674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 3) If OuterLoop Preheader is same as Header of the previous loop. 8684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 4) If OuterLoop Preheader is Entry node. 8694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() || 8704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar isa<PHINode>(OuterLoopPreHeader->begin()) || 8714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar !OuterLoopPreHeader->getUniquePredecessor()) { 872f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OuterLoopPreHeader = 873f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA); 8744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 8754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() || 8774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopPreHeader == OuterLoop->getHeader()) { 878f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InnerLoopPreHeader = 879f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA); 8804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 8814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: The loops could not be interchanged due to current limitations in the 8834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // transform module. 8844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (currentLimitations()) { 8854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Not legal because of current transform limitation\n"); 8864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 8874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 8884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Check if the loops are tightly nested. 8906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!tightlyNested(OuterLoop, InnerLoop)) { 8916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "Loops not tightly nested\n"); 8926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 8936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 8946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 8954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 8964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 8974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarint LoopInterchangeProfitability::getInstrOrderCost() { 8994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned GoodOrder, BadOrder; 9004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BadOrder = GoodOrder = 0; 9014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end(); 9024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BI != BE; ++BI) { 903de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Instruction &Ins : **BI) { 9044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) { 9054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned NumOp = GEP->getNumOperands(); 9064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool FoundInnerInduction = false; 9074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool FoundOuterInduction = false; 9084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < NumOp; ++i) { 9094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i)); 9104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal); 9114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!AR) 9124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar continue; 9134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 9144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If we find the inner induction after an outer induction e.g. 9154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(int i=0;i<N;i++) 9164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(int j=0;j<N;j++) 9174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // A[i][j] = A[i-1][j-1]+k; 9184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // then it is a good order. 9194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (AR->getLoop() == InnerLoop) { 9204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We found an InnerLoop induction after OuterLoop induction. It is 9214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // a good order. 9224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar FoundInnerInduction = true; 9234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (FoundOuterInduction) { 9244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar GoodOrder++; 9254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar break; 9264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If we find the outer induction after an inner induction e.g. 9294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(int i=0;i<N;i++) 9304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // for(int j=0;j<N;j++) 9314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // A[j][i] = A[j-1][i-1]+k; 9324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // then it is a bad order. 9334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (AR->getLoop() == OuterLoop) { 9344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We found an OuterLoop induction after InnerLoop induction. It is 9354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // a bad order. 9364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar FoundOuterInduction = true; 9374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (FoundInnerInduction) { 9384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BadOrder++; 9394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar break; 9404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return GoodOrder - BadOrder; 9474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 9484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 9494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic bool isProfitabileForVectorization(unsigned InnerLoopId, 9504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned OuterLoopId, 9514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CharMatrix &DepMatrix) { 9524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: Improve this heuristic to catch more cases. 9534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If the inner loop is loop independent or doesn't carry any dependency it is 9544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // profitable to move this to outer position. 9554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned Row = DepMatrix.size(); 9564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < Row; ++i) { 9574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I') 9584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 9594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: We need to improve this heuristic. 9604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (DepMatrix[i][OuterLoopId] != '=') 9614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 9624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 9634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // If outer loop has dependence and inner loop is loop independent then it is 9644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // profitable to interchange to enable parallelism. 9654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 9664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 9674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 9684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId, 9694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned OuterLoopId, 9704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar CharMatrix &DepMatrix) { 9714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 972f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // TODO: Add better profitability checks. 9734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // e.g 9744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 1) Construct dependency matrix and move the one with no loop carried dep 9754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // inside to enable vectorization. 9764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 9774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // This is rough cost estimation algorithm. It counts the good and bad order 9784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // of induction variables in the instruction and allows reordering if number 9794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // of bad orders is more than good. 9804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar int Cost = 0; 9814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Cost += getInstrOrderCost(); 9824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Cost = " << Cost << "\n"); 9834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Cost < 0) 9844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 9854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 986f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // It is not profitable as per current cache profitability model. But check if 9874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // we can move this loop outside to improve parallelism. 9884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool ImprovesPar = 9894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix); 9904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return ImprovesPar; 9914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 9924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 9934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop, 9944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *InnerLoop) { 9954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E; 9964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ++I) { 9974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (*I == InnerLoop) { 9984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoop->removeChildLoop(I); 9994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return; 10004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 10014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1002f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar llvm_unreachable("Couldn't find loop"); 10034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 10044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid LoopInterchangeTransform::restructureLoops(Loop *InnerLoop, 10064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterLoop) { 10074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Loop *OuterLoopParent = OuterLoop->getParentLoop(); 10084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterLoopParent) { 10094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Remove the loop from its parent loop. 10104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar removeChildLoop(OuterLoopParent, OuterLoop); 10114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar removeChildLoop(OuterLoop, InnerLoop); 10124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopParent->addChildLoop(InnerLoop); 10134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { 10144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar removeChildLoop(OuterLoop, InnerLoop); 10154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LI->changeTopLevelLoop(OuterLoop, InnerLoop); 10164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 10174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar while (!InnerLoop->empty()) 10196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin())); 10204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoop->addChildLoop(OuterLoop); 10224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 10234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeTransform::transform() { 10254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "transform\n"); 10274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool Transformed = false; 10284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction *InnerIndexVar; 10294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerLoop->getSubLoops().size() == 0) { 10314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 10324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Calling Split Inner Loop\n"); 10334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PHINode *InductionPHI = getInductionVariable(InnerLoop, SE); 10344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!InductionPHI) { 10354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Failed to find the point to split loop latch \n"); 10364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 10374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 10384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader) 10404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1)); 10414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 10424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0)); 10434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 10454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Split at the place were the induction variable is 10464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // incremented/decremented. 10474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // TODO: This splitting logic may not work always. Fix this. 10484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar splitInnerLoopLatch(InnerIndexVar); 10494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "splitInnerLoopLatch Done\n"); 10504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1051f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Splits the inner loops phi nodes out into a separate basic block. 10524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar splitInnerLoopHeader(); 10534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "splitInnerLoopHeader Done\n"); 10544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 10554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Transformed |= adjustLoopLinks(); 10574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!Transformed) { 10584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "adjustLoopLinks Failed\n"); 10594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 10604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 10614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar restructureLoops(InnerLoop, OuterLoop); 10634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 10644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 10654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) { 10674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); 10684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopLatchPred = InnerLoopLatch; 10694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI); 10704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 10714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid LoopInterchangeTransform::splitInnerLoopHeader() { 10734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 10746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Split the inner loop header out. Here make sure that the reduction PHI's 10756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // stay in the innerloop body. 10764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); 10776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 10786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (InnerLoopHasReduction) { 10796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // FIXME: Check if the induction PHI will always be the first PHI. 10806948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *New = InnerLoopHeader->splitBasicBlock( 10816948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split"); 10826948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (LI) 10836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Loop *L = LI->getLoopFor(InnerLoopHeader)) 10846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar L->addBasicBlockToLoop(New, *LI); 10856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 10866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Adjust Reduction PHI's in the block. 10876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> PHIVec; 10886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (auto I = New->begin(); isa<PHINode>(I); ++I) { 10896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *PHI = dyn_cast<PHINode>(I); 10906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader); 10916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHI->replaceAllUsesWith(V); 10926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHIVec.push_back((PHI)); 10936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1094de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (PHINode *P : PHIVec) { 10956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar P->eraseFromParent(); 10966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 10976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else { 10986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI); 10996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 11004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & " 11024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar "InnerLoopHeader \n"); 11034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 11044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// \brief Move all instructions except the terminator from FromBB right before 11064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// InsertBefore 11074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) { 11084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto &ToList = InsertBefore->getParent()->getInstList(); 11094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto &FromList = FromBB->getInstList(); 11104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1111f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(), 1112f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar FromBB->getTerminator()->getIterator()); 11134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 11144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarvoid LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock, 11166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *OldPred, 11176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BasicBlock *NewPred) { 11186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) { 11196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *PHI = cast<PHINode>(I); 11206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Num = PHI->getNumIncomingValues(); 11216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (unsigned i = 0; i < Num; ++i) { 11226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (PHI->getIncomingBlock(i) == OldPred) 11236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHI->setIncomingBlock(i, NewPred); 11246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 11256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 11266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 11276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 11284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeTransform::adjustLoopBranches() { 11294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(dbgs() << "adjustLoopBranches called\n"); 11314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Adjust the loop preheader 11324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); 11334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); 11344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); 11354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); 11364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); 11374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 11384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor(); 11394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopLatchPredecessor = 11404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatch->getUniquePredecessor(); 11414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopLatchSuccessor; 11424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopLatchSuccessor; 11434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *OuterLoopLatchBI = 11454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(OuterLoopLatch->getTerminator()); 11464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *InnerLoopLatchBI = 11474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(InnerLoopLatch->getTerminator()); 11484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *OuterLoopHeaderBI = 11494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(OuterLoopHeader->getTerminator()); 11504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *InnerLoopHeaderBI = 11514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(InnerLoopHeader->getTerminator()); 11524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor || 11544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI || 11554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar !InnerLoopHeaderBI) 11564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 11574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *InnerLoopLatchPredecessorBI = 11594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator()); 11604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *OuterLoopPredecessorBI = 11614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator()); 11624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI) 11644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 1165f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor(); 1166f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!InnerLoopHeaderSuccessor) 11674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 11684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Adjust Loop Preheader and headers 11704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors(); 11724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < NumSucc; ++i) { 11734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader) 11744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader); 11754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 11764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar NumSucc = OuterLoopHeaderBI->getNumSuccessors(); 11784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < NumSucc; ++i) { 11794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch) 11804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopHeaderBI->setSuccessor(i, LoopExit); 11814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader) 1182f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor); 11834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 11844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Adjust reduction PHI's now that the incoming block has changed. 1186f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader, 11876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar OuterLoopHeader); 11886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 11894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI); 11904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopHeaderBI->eraseFromParent(); 11914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // -------------Adjust loop latches----------- 11934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader) 11944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1); 11954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 11964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0); 11974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 11984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors(); 11994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (unsigned i = 0; i < NumSucc; ++i) { 12004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch) 12014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor); 12024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 12034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with 12056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the value and remove this PHI node from inner loop. 12066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<PHINode *, 8> LcssaVec; 12076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) { 12086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *LcssaPhi = cast<PHINode>(I); 12096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LcssaVec.push_back(LcssaPhi); 12106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1211de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (PHINode *P : LcssaVec) { 12126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch); 12136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar P->replaceAllUsesWith(Incoming); 12146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar P->eraseFromParent(); 12156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 12166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 12174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader) 12184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1); 12194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 12204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0); 12214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor) 12234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor); 12244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 12254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor); 12264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch); 12286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 12294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) { 12304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch); 12314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { 12324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch); 12334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 12344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 12364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 12374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid LoopInterchangeTransform::adjustLoopPreheaders() { 12384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We have interchanged the preheaders so we need to interchange the data in 12404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // the preheader as well. 12414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // This is because the content of inner preheader was previously executed 12424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // inside the outer loop. 12434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); 12444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); 12454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); 12464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BranchInst *InnerTermBI = 12474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar cast<BranchInst>(InnerLoopPreHeader->getTerminator()); 12484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // These instructions should now be executed inside the loop. 12504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Move instruction into a new block after outer header. 12516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator()); 12524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // These instructions were not executed previously in the loop so move them to 12534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // the older inner loop preheader. 12544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar moveBBContents(OuterLoopPreHeader, InnerTermBI); 12554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 12564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarbool LoopInterchangeTransform::adjustLoopLinks() { 12584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Adjust all branches in the inner and outer loop. 12604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool Changed = adjustLoopBranches(); 12614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Changed) 12624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar adjustLoopPreheaders(); 12634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return Changed; 12644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 12654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarchar LoopInterchange::ID = 0; 12674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarINITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange", 12684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar "Interchanges loops for cache reuse", false, false) 1269f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 1270de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass) 12714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 1272f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 12734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 1274de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass) 12754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 12764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarINITIALIZE_PASS_END(LoopInterchange, "loop-interchange", 12784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar "Interchanges loops for cache reuse", false, false) 12794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 12804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarPass *llvm::createLoopInterchangePass() { return new LoopInterchange(); } 1281