lib/IndependentBlocks.cpp

   1 //===------ IndependentBlocks.cpp - Create Independent Blocks in Regions --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Create independent blocks in the regions detected by ScopDetection.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 //
  14 #include "polly/LinkAllPasses.h"
  15 #include "polly/ScopDetection.h"
  16 #include "polly/Support/ScopHelper.h"
  17 #include "polly/Cloog.h"
  18
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/Analysis/RegionInfo.h"
  21 #include "llvm/Analysis/RegionPass.h"
  22 #include "llvm/Analysis/RegionIterator.h"
  23 #include "llvm/Analysis/ScalarEvolution.h"
  24 #include "llvm/Analysis/ValueTracking.h"
  25 #include "llvm/Transforms/Utils/Local.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/ADT/OwningPtr.h"
  28 #include "llvm/Assembly/Writer.h"
  29
  30 #define DEBUG_TYPE "polly-independent"
  31 #include "llvm/Support/Debug.h"
  32
  33 #include <vector>
  34
  35 using namespace polly;
  36 using namespace llvm;
  37
  38 namespace {
  39 struct IndependentBlocks : public FunctionPass {
  40   RegionInfo *RI;
  41   ScalarEvolution *SE;
  42   ScopDetection *SD;
  43   LoopInfo *LI;
  44
  45   BasicBlock *AllocaBlock;
  46
  47   static char ID;
  48
  49   IndependentBlocks() : FunctionPass(ID) {}
  50
  51   // Create new code for every instruction operator that can be expressed by a
  52   // SCEV.  Like this there are just two types of instructions left:
  53   //
  54   // 1. Instructions that only reference loop ivs or parameters outside the
  55   // region.
  56   //
  57   // 2. Instructions that are not used for any memory modification. (These
  58   //    will be ignored later on.)
  59   //
  60   // Blocks containing only these kind of instructions are called independent
  61   // blocks as they can be scheduled arbitrarily.
  62   bool createIndependentBlocks(BasicBlock *BB, const Region *R);
  63   bool createIndependentBlocks(const Region *R);
  64
  65   // Elimination on the Scop to eliminate the scalar dependences come with
  66   // trivially dead instructions.
  67   bool eliminateDeadCode(const Region *R);
  68
  69   //===--------------------------------------------------------------------===//
  70   /// Non trivial scalar dependences checking functions.
  71   /// Non trivial scalar dependences occur when the def and use are located in
  72   /// different BBs and we can not move them into the same one. This will
  73   /// prevent use from schedule BBs arbitrarily.
  74   ///
  75   /// @brief This function checks if a scalar value that is part of the
  76   ///        Scop is used outside of the Scop.
  77   ///
  78   /// @param Use  The use of the instruction.
  79   /// @param R    The maximum region in the Scop.
  80   ///
  81   /// @return Return true if the Use of an instruction and the instruction
  82   ///         itself form a non trivial scalar dependence.
  83   static bool isEscapeUse(const Value *Use, const Region *R);
  84
  85   /// @brief This function just checks if a Value is either defined in the same
  86   ///        basic block or outside the region, such that there are no scalar
  87   ///        dependences between basic blocks that are both part of the same
  88   ///        region.
  89   ///
  90   /// @param Operand  The operand of the instruction.
  91   /// @param CurBB    The BasicBlock that contains the instruction.
  92   /// @param R        The maximum region in the Scop.
  93   ///
  94   /// @return Return true if the Operand of an instruction and the instruction
  95   ///         itself form a non trivial scalar (true) dependence.
  96   bool isEscapeOperand(const Value *Operand, const BasicBlock *CurBB,
  97                        const Region *R) const;
  98
  99   //===--------------------------------------------------------------------===//
 100   /// Operand tree moving functions.
 101   /// Trivial scalar dependences can eliminate by move the def to the same BB
 102   /// that containing use.
 103   ///
 104   /// @brief Check if the instruction can be moved to another place safely.
 105   ///
 106   /// @param Inst The instruction.
 107   ///
 108   /// @return Return true if the instruction can be moved safely, false
 109   ///         otherwise.
 110   static bool isSafeToMove(Instruction *Inst);
 111
 112   typedef std::map<Instruction*, Instruction*> ReplacedMapType;
 113
 114   /// @brief Move all safe to move instructions in the Operand Tree (DAG) to
 115   ///        eliminate trivial scalar dependences.
 116   ///
 117   /// @param Inst         The root of the operand Tree.
 118   /// @param R            The maximum region in the Scop.
 119   /// @param ReplacedMap  The map that mapping original instruction to the moved
 120   ///                     instruction.
 121   /// @param InsertPos    The insert position of the moved instructions.
 122   void moveOperandTree(Instruction *Inst, const Region *R,
 123                        ReplacedMapType &ReplacedMap,
 124                        Instruction *InsertPos);
 125
 126   bool isIndependentBlock(const Region *R, BasicBlock *BB) const;
 127   bool areAllBlocksIndependent(const Region *R) const;
 128
 129   // Split the exit block to hold load instructions.
 130   bool splitExitBlock(Region *R);
 131
 132   bool translateScalarToArray(BasicBlock *BB, const Region *R);
 133   bool translateScalarToArray(Instruction *Inst, const Region *R);
 134   bool translateScalarToArray(const Region *R);
 135
 136   bool runOnFunction(Function &F);
 137   void verifyAnalysis() const;
 138   void verifyScop(const Region *R) const;
 139   void getAnalysisUsage(AnalysisUsage &AU) const;
 140 };
 141 }
 142
 143 bool IndependentBlocks::isSafeToMove(Instruction *Inst) {
 144   if (Inst->mayReadFromMemory() ||
 145       Inst->mayWriteToMemory())
 146     return false;
 147
 148   return isSafeToSpeculativelyExecute(Inst);
 149 }
 150
 151 void IndependentBlocks::moveOperandTree(Instruction *Inst, const Region *R,
 152                                         ReplacedMapType &ReplacedMap,
 153                                         Instruction *InsertPos) {
 154   BasicBlock *CurBB = Inst->getParent();
 155
 156   // Depth first traverse the operand tree (or operand dag, because we will
 157   // stop at PHINodes, so there are no cycle).
 158   typedef Instruction::op_iterator ChildIt;
 159   std::vector<std::pair<Instruction*, ChildIt> > WorkStack;
 160
 161   WorkStack.push_back(std::make_pair(Inst, Inst->op_begin()));
 162
 163   while (!WorkStack.empty()) {
 164     Instruction *CurInst = WorkStack.back().first;
 165     ChildIt It = WorkStack.back().second;
 166     DEBUG(dbgs() << "Checking Operand of Node:\n" << *CurInst << "\n------>\n");
 167     if (It == CurInst->op_end()) {
 168       // Insert the new instructions in topological order.
 169       if (!CurInst->getParent())
 170         CurInst->insertBefore(InsertPos);
 171
 172       WorkStack.pop_back();
 173     } else {
 174       // for each node N,
 175       Instruction *Operand = dyn_cast<Instruction>(*It);
 176       ++WorkStack.back().second;
 177
 178       // Can not move no instruction value.
 179       if (Operand == 0) continue;
 180
 181       DEBUG(dbgs() << "For Operand:\n" << *Operand << "\n--->");
 182
 183       // If the Scop Region does not contain N, skip it and all its operand and
 184       // continue. because we reach a "parameter".
 185       // FIXME: we must keep the predicate instruction inside the Scop, otherwise
 186       // it will be translated to a load instruction, and we can not handle load
 187       // as affine predicate at this moment.
 188       if (!R->contains(Operand) && !isa<TerminatorInst>(CurInst)) {
 189         DEBUG(dbgs() << "Out of region.\n");
 190         continue;
 191       }
 192
 193       // No need to move induction variable.
 194       if (isIndVar(Operand, LI)) {
 195         DEBUG(dbgs() << "is IV.\n");
 196         continue;
 197       }
 198
 199       // We can not move the operand, a non trivial scalar dependence found!
 200       if (!isSafeToMove(Operand)) {
 201         DEBUG(dbgs() << "Can not move!\n");
 202         continue;
 203       }
 204
 205       // Do not need to move instruction if it contained in the same BB with
 206       // the root instruction.
 207       // FIXME: Remember this in visited Map.
 208       if (Operand->getParent() == CurBB) {
 209         DEBUG(dbgs() << "No need to move.\n");
 210         // Try to move its operand.
 211         WorkStack.push_back(std::make_pair(Operand, Operand->op_begin()));
 212         continue;
 213       }
 214
 215       // Now we need to move Operand to CurBB.
 216       // Check if we already moved it.
 217       ReplacedMapType::iterator At = ReplacedMap.find(Operand);
 218       if (At != ReplacedMap.end()) {
 219         DEBUG(dbgs() << "Moved.\n");
 220         Instruction *MovedOp = At->second;
 221         It->set(MovedOp);
 222         // Skip all its children as we already processed them.
 223         continue;
 224       } else {
 225         // Note that NewOp is not inserted in any BB now, we will insert it when
 226         // it popped form the work stack, so it will be inserted in topological
 227         // order.
 228         Instruction *NewOp = Operand->clone();
 229         NewOp->setName(Operand->getName() + ".moved.to." + CurBB->getName());
 230         DEBUG(dbgs() << "Move to " << *NewOp << "\n");
 231         It->set(NewOp);
 232         ReplacedMap.insert(std::make_pair(Operand, NewOp));
 233         // Process its operands.
 234         WorkStack.push_back(std::make_pair(NewOp, NewOp->op_begin()));
 235       }
 236     }
 237   }
 238
 239   SE->forgetValue(Inst);
 240 }
 241
 242 bool IndependentBlocks::createIndependentBlocks(BasicBlock *BB,
 243                                                 const Region *R) {
 244   std::vector<Instruction*> WorkList;
 245   for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II)
 246     if (!isSafeToMove(II) && !isIndVar(II, LI))
 247       WorkList.push_back(II);
 248
 249   ReplacedMapType ReplacedMap;
 250   Instruction *InsertPos = BB->getFirstNonPHIOrDbg();
 251
 252   for (std::vector<Instruction*>::iterator I = WorkList.begin(),
 253       E = WorkList.end(); I != E; ++I)
 254     moveOperandTree(*I, R, ReplacedMap, InsertPos);
 255
 256   // The BB was changed if we replaced any operand.
 257   return !ReplacedMap.empty();
 258 }
 259
 260 bool IndependentBlocks::createIndependentBlocks(const Region *R) {
 261   bool Changed = false;
 262
 263   for (Region::const_block_iterator SI = R->block_begin(), SE = R->block_end();
 264        SI != SE; ++SI)
 265     Changed |= createIndependentBlocks(*SI, R);
 266
 267   return Changed;
 268 }
 269
 270 bool IndependentBlocks::eliminateDeadCode(const Region *R) {
 271   std::vector<Instruction*> WorkList;
 272
 273   // Find all trivially dead instructions.
 274   for (Region::const_block_iterator SI = R->block_begin(), SE = R->block_end();
 275       SI != SE; ++SI)
 276     for (BasicBlock::iterator I = (*SI)->begin(), E = (*SI)->end(); I != E; ++I)
 277       if (isInstructionTriviallyDead(I))
 278         WorkList.push_back(I);
 279
 280   if (WorkList.empty()) return false;
 281
 282   // Delete them so the cross BB scalar dependences come with them will
 283   // also be eliminated.
 284   while (!WorkList.empty()) {
 285     RecursivelyDeleteTriviallyDeadInstructions(WorkList.back());
 286     WorkList.pop_back();
 287   }
 288
 289   return true;
 290 }
 291
 292 bool IndependentBlocks::isEscapeUse(const Value *Use, const Region *R) {
 293   // Non-instruction user will never escape.
 294   if (!isa<Instruction>(Use)) return false;
 295
 296   return !R->contains(cast<Instruction>(Use));
 297 }
 298
 299 bool IndependentBlocks::isEscapeOperand(const Value *Operand,
 300                                         const BasicBlock *CurBB,
 301                                         const Region *R) const {
 302   const Instruction *OpInst = dyn_cast<Instruction>(Operand);
 303
 304   // Non-instruction operand will never escape.
 305   if (OpInst == 0) return false;
 306
 307   // Induction variables are valid operands.
 308   if (isIndVar(OpInst, LI)) return false;
 309
 310   // A value from a different BB is used in the same region.
 311   return R->contains(OpInst) && (OpInst->getParent() != CurBB);
 312 }
 313
 314 bool IndependentBlocks::splitExitBlock(Region *R) {
 315   // Split the exit BB to place the load instruction of escaped users.
 316   BasicBlock *ExitBB = R->getExit();
 317   Region *ExitRegion = RI->getRegionFor(ExitBB);
 318
 319   if (ExitBB != ExitRegion->getEntry())
 320     return false;
 321
 322   BasicBlock *NewExit = createSingleExitEdge(R, this);
 323
 324   std::vector<Region*> toUpdate;
 325   toUpdate.push_back(R);
 326
 327   while (!toUpdate.empty()) {
 328     Region *Reg = toUpdate.back();
 329     toUpdate.pop_back();
 330
 331     for (Region::iterator I = Reg->begin(), E = Reg->end(); I != E; ++I) {
 332       Region *SubR = *I;
 333
 334       if (SubR->getExit() == ExitBB)
 335         toUpdate.push_back(SubR);
 336     }
 337
 338     Reg->replaceExit(NewExit);
 339   }
 340
 341   RI->setRegionFor(NewExit, R->getParent());
 342   return true;
 343 }
 344
 345 bool IndependentBlocks::translateScalarToArray(const Region *R) {
 346   bool Changed = false;
 347
 348   for (Region::const_block_iterator SI = R->block_begin(), SE = R->block_end();
 349        SI != SE; ++SI)
 350     Changed |= translateScalarToArray(*SI, R);
 351
 352   return Changed;
 353 }
 354
 355 bool IndependentBlocks::translateScalarToArray(Instruction *Inst,
 356                                                const Region *R) {
 357   if (isIndVar(Inst, LI))
 358     return false;
 359
 360   SmallVector<Instruction*, 4> LoadInside, LoadOutside;
 361   for (Instruction::use_iterator UI = Inst->use_begin(),
 362        UE = Inst->use_end(); UI != UE; ++UI)
 363     // Inst is referenced outside or referenced as an escaped operand.
 364     if (Instruction *U = dyn_cast<Instruction>(*UI)) {
 365       BasicBlock *UParent = U->getParent();
 366
 367       if (isEscapeUse(U, R))
 368         LoadOutside.push_back(U);
 369
 370       if (isIndVar(U, LI))
 371         continue;
 372
 373       if (R->contains(UParent) && isEscapeOperand(Inst, UParent, R))
 374         LoadInside.push_back(U);
 375     }
 376
 377   if (LoadOutside.empty() && LoadInside.empty())
 378     return false;
 379
 380   // Create the alloca.
 381   AllocaInst *Slot = new AllocaInst(Inst->getType(), 0,
 382                                     Inst->getName() + ".s2a",
 383                                     AllocaBlock->begin());
 384   assert(!isa<InvokeInst>(Inst) && "Unexpect Invoke in Scop!");
 385   // Store right after Inst.
 386   BasicBlock::iterator StorePos = Inst;
 387   (void) new StoreInst(Inst, Slot, ++StorePos);
 388
 389   if (!LoadOutside.empty()) {
 390     LoadInst *ExitLoad = new LoadInst(Slot, Inst->getName()+".loadoutside",
 391                                       false, R->getExit()->getFirstNonPHI());
 392
 393     while (!LoadOutside.empty()) {
 394       Instruction *U = LoadOutside.pop_back_val();
 395       assert(!isa<PHINode>(U) && "Can not handle PHI node outside!");
 396       SE->forgetValue(U);
 397       U->replaceUsesOfWith(Inst, ExitLoad);
 398     }
 399   }
 400
 401   while (!LoadInside.empty()) {
 402     Instruction *U = LoadInside.pop_back_val();
 403     assert(!isa<PHINode>(U) && "Can not handle PHI node outside!");
 404     SE->forgetValue(U);
 405     LoadInst *L = new LoadInst(Slot, Inst->getName()+".loadarray",
 406                                false, U);
 407     U->replaceUsesOfWith(Inst, L);
 408   }
 409
 410   return true;
 411 }
 412
 413 bool IndependentBlocks::translateScalarToArray(BasicBlock *BB,
 414                                                const Region *R) {
 415   bool changed = false;
 416
 417   SmallVector<Instruction*, 32> Insts;
 418   for (BasicBlock::iterator II = BB->begin(), IE = --BB->end();
 419        II != IE; ++II)
 420     Insts.push_back(II);
 421
 422   while (!Insts.empty()) {
 423     Instruction *Inst = Insts.pop_back_val();
 424     changed |= translateScalarToArray(Inst, R);
 425   }
 426
 427   return changed;
 428 }
 429
 430 bool IndependentBlocks::isIndependentBlock(const Region *R,
 431                                            BasicBlock *BB) const {
 432   for (BasicBlock::iterator II = BB->begin(), IE = --BB->end();
 433        II != IE; ++II) {
 434     Instruction *Inst = &*II;
 435
 436     if (isIndVar(Inst, LI))
 437       continue;
 438
 439     // A value inside the Scop is referenced outside.
 440     for (Instruction::use_iterator UI = Inst->use_begin(),
 441          UE = Inst->use_end(); UI != UE; ++UI) {
 442       if (isEscapeUse(*UI, R)) {
 443         DEBUG(dbgs() << "Instruction not independent:\n");
 444         DEBUG(dbgs() << "Instruction used outside the Scop!\n");
 445         DEBUG(Inst->print(dbgs()));
 446         DEBUG(dbgs() << "\n");
 447         return false;
 448       }
 449     }
 450
 451     for (Instruction::op_iterator OI = Inst->op_begin(),
 452          OE = Inst->op_end(); OI != OE; ++OI) {
 453       if (isEscapeOperand(*OI, BB, R)) {
 454         DEBUG(dbgs() << "Instruction in function '";
 455               WriteAsOperand(dbgs(), BB->getParent(), false);
 456               dbgs() << "' not independent:\n");
 457         DEBUG(dbgs() << "Uses invalid operator\n");
 458         DEBUG(Inst->print(dbgs()));
 459         DEBUG(dbgs() << "\n");
 460         DEBUG(dbgs() << "Invalid operator is: ";
 461               WriteAsOperand(dbgs(), *OI, false);
 462               dbgs() << "\n");
 463         return false;
 464       }
 465     }
 466   }
 467
 468   return true;
 469 }
 470
 471 bool IndependentBlocks::areAllBlocksIndependent(const Region *R) const {
 472   for (Region::const_block_iterator SI = R->block_begin(), SE = R->block_end();
 473        SI != SE; ++SI)
 474     if (!isIndependentBlock(R, *SI))
 475       return false;
 476
 477   return true;
 478 }
 479
 480 void IndependentBlocks::getAnalysisUsage(AnalysisUsage &AU) const {
 481   // FIXME: If we set preserves cfg, the cfg only passes do not need to
 482   // be "addPreserved"?
 483   AU.addPreserved<DominatorTree>();
 484   AU.addPreserved<DominanceFrontier>();
 485   AU.addPreserved<PostDominatorTree>();
 486   AU.addRequired<RegionInfo>();
 487   AU.addPreserved<RegionInfo>();
 488   AU.addRequired<LoopInfo>();
 489   AU.addPreserved<LoopInfo>();
 490   AU.addRequired<ScalarEvolution>();
 491   AU.addPreserved<ScalarEvolution>();
 492   AU.addRequired<ScopDetection>();
 493   AU.addPreserved<ScopDetection>();
 494   AU.addPreserved<CloogInfo>();
 495 }
 496
 497 bool IndependentBlocks::runOnFunction(llvm::Function &F) {
 498   bool Changed = false;
 499
 500   RI = &getAnalysis<RegionInfo>();
 501   LI = &getAnalysis<LoopInfo>();
 502   SD = &getAnalysis<ScopDetection>();
 503   SE = &getAnalysis<ScalarEvolution>();
 504
 505   AllocaBlock = &F.getEntryBlock();
 506
 507   DEBUG(dbgs() << "Run IndepBlock on " << F.getName() << '\n');
 508
 509   for (ScopDetection::iterator I = SD->begin(), E = SD->end(); I != E; ++I) {
 510     const Region *R = *I;
 511     Changed |= createIndependentBlocks(R);
 512     Changed |= eliminateDeadCode(R);
 513     // This may change the RegionTree.
 514     Changed |= splitExitBlock(const_cast<Region*>(R));
 515   }
 516
 517   DEBUG(dbgs() << "Before Scalar to Array------->\n");
 518   DEBUG(F.dump());
 519
 520   for (ScopDetection::iterator I = SD->begin(), E = SD->end(); I != E; ++I)
 521     Changed |= translateScalarToArray(*I);
 522
 523   DEBUG(dbgs() << "After Independent Blocks------------->\n");
 524   DEBUG(F.dump());
 525
 526   verifyAnalysis();
 527
 528   return Changed;
 529 }
 530
 531 void IndependentBlocks::verifyAnalysis() const {
 532   for (ScopDetection::const_iterator I = SD->begin(), E = SD->end();I != E;++I)
 533     verifyScop(*I);
 534 }
 535
 536 void IndependentBlocks::verifyScop(const Region *R) const {
 537   assert (areAllBlocksIndependent(R) && "Cannot generate independent blocks");
 538 }
 539
 540 char IndependentBlocks::ID = 0;
 541 char &polly::IndependentBlocksID = IndependentBlocks::ID;
 542
 543 INITIALIZE_PASS_BEGIN(IndependentBlocks, "polly-independent",
 544                       "Polly - Create independent blocks", false, false)
 545 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 546 INITIALIZE_PASS_DEPENDENCY(RegionInfo)
 547 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 548 INITIALIZE_PASS_DEPENDENCY(ScopDetection)
 549 INITIALIZE_PASS_END(IndependentBlocks, "polly-independent",
 550                     "Polly - Create independent blocks", false, false)
 551
 552 Pass *polly::createIndependentBlocksPass() {
 553   return new IndependentBlocks();
 554 }